Locality Is the Whole Game: The Memory Hierarchy and What a Kernel Does Not Read

The bytes that were never fetched

Ask why a kernel is fast and the usual answer counts operations. It is the wrong quantity. On contemporary accelerators the arithmetic units are almost never the scarce resource; the scarce resource is the path along which operands arrive. A useful performance claim is therefore not a statement about how much work a kernel does but about how few bytes it touches, and the most important line in an optimised implementation is frequently the load that is no longer there.

The trend that produced this situation is measurable rather than rhetorical. Gholami and colleagues, surveying twenty years of hardware, report that peak server FLOPS has scaled at roughly 3.0 times every two years while DRAM bandwidth scaled at 1.6 and interconnect bandwidth at 1.4 times over the same interval ^[4]. Compounded, those rates diverge violently. The consequence is not that arithmetic became free — it is that the ratio between what a chip can compute and what it can be fed has been moving in one direction for two decades, and every algorithm inherits that ratio whether or not its author thought about it.

The older evidence points the same way. The STREAM benchmark was built precisely to measure sustainable memory bandwidth rather than peak arithmetic rate, on the argument that “computer cpus are getting faster much more quickly than computer memory systems”; its documentation notes that several high-end machines of its era ran simple arithmetic kernels on out-of-cache operands at 4 to 5 per cent of rated peak, meaning they spent 95 per cent or more of their time waiting for cache misses ^[17]. That was a description of scientific computing in the 1990s. It reads today as a description of an unfused elementwise operation on a modern accelerator.

Five stores, and the distance between them

A memory hierarchy is not a storage system with a speed problem. It is a set of deliberately different stores, each trading capacity against access time, arranged so that the fastest one is small enough to be affordable and close enough to be quick.

At the top sit the registers, private to a thread and read at the rate the pipeline issues instructions. Below them is on-chip SRAM — cache, or an explicitly managed scratchpad, depending on the architecture’s philosophy. Below that is the high-bandwidth memory stacked next to the die. Below that is host memory across a peripheral link, and below that storage.

The gaps are the point, and they are non-uniform. Luo and colleagues microbenchmarked the Hopper and Ampere generations and measured average access latencies, in clock cycles, of 29.0 for shared memory, 40.7 for L1 and 263.0 for L2 on an H800, with global memory at 478.8; the corresponding A100 figures were 29.0, 37.9, 261.5 and 466.3 ^[7]. They summarise the shape as an L2 latency roughly 6.5 times that of L1 and a global-memory latency roughly 1.9 times that of L2. Note what this says: the expensive step is not the last one. Falling out of the first-level cache into L2 costs more, proportionally, than falling from L2 to DRAM. This kind of geometry is not published by vendors in usable detail, which is why an entire literature exists to recover it by microbenchmark ^[8].

Capacity and bandwidth move in the opposite direction, and by larger factors. The FlashAttention paper’s own summary of an A100 is the clearest published statement of the ladder: on-chip SRAM of roughly 20 MB at an estimated 19 TB/s, HBM of 40 GB at 1.5 TB/s, and CPU DRAM of more than 1 TB at 12.8 GB/s ^[1]. Between the first two rungs, capacity rises by about three orders of magnitude while bandwidth falls by about one. Between the second and third, capacity rises by more than one order of magnitude while bandwidth falls by more than two. The authors put it plainly: on-chip SRAM is an order of magnitude faster than HBM but many orders of magnitude smaller.

The tiers below that behave the same way. ZeRO-Infinity was built to exploit them explicitly, staging model state across GPU memory, CPU memory and NVMe; its authors observe that the largest dense models grew more than a thousandfold in three years while GPU memory grew fivefold, from 16 GB to 80 GB, and that fitting a trillion-parameter model for training required roughly 800 V100 GPUs simply to hold it ^[16]. A store you can afford and a store you can read quickly have been diverging for as long as anyone has been building these machines.

One inequality, and the point at which it bends

The quantity that decides which of these limits binds is arithmetic intensity: the number of arithmetic operations a kernel performs per byte it moves across a given level. Williams, Waterman and Patterson formalised the consequence as the roofline model, which relates attainable floating-point performance to operational intensity and memory bandwidth in a single visual bound ^[5]. Written as an inequality, attainable performance $P$ satisfies

with $P_{\max}$ the peak arithmetic rate, $I$ the arithmetic intensity in operations per byte, and $B$ the achievable bandwidth at the level that dominates. The two terms cross at a ridge point $I^{*} = P_{\max}/B$. Below it a kernel is memory-bound and its runtime is set by traffic; above it the kernel is compute-bound and traffic is hidden.

Everything else in this article follows from one observation about that ridge point: because $P_{\max}$ has been growing at roughly twice the rate of $B$ ^[4], $I^{*}$ has been climbing steadily. A kernel whose intensity was comfortably compute-bound on one generation can be memory-bound on the next without a single line of it changing. Hardware progress moves operations across the boundary in only one direction.

The classification this yields is coarse but reliable, and the FlashAttention authors state it cleanly: matrix multiplication with a large inner dimension is compute-bound, while elementwise operations such as activations and dropout, and reductions such as sum, softmax and layer normalisation, are memory-bound ^[1]. The arithmetic is easy to check. An elementwise addition of two half-precision tensors reads four bytes and writes two to perform one operation — an intensity of one sixth. Against a ridge point in the hundreds, such a kernel spends essentially all of its time waiting.

Evidence that this dominates real workloads rather than microbenchmarks comes from Ivanov and colleagues, who profiled transformer training and concluded that data movement is the key bottleneck; by optimising data layout and movement globally they reduced data movement by up to 22.91 per cent and obtained a 1.30 times improvement on a BERT encoder layer and 1.19 times on the whole model against state-of-the-art frameworks ^[9]. Those are speedups obtained without changing the mathematics at all.

Locality is a property of the algorithm, not the machine

Caches work only because programs reuse things. Temporal locality is the tendency to touch the same datum again soon; spatial locality is the tendency to touch its neighbours. Hardware is built to exploit both — lines rather than words are fetched, and recently used lines are retained — but hardware cannot create either. A cache accelerates an access pattern that already has reuse in it. Against a pattern with none, it adds latency and a line-granularity read amplification, and nothing else.

This is the sense in which locality is the whole game. The hierarchy is fixed by the time the code runs. What the programmer controls is the order of operations, and the order determines how much of the reuse latent in the computation is actually realised while the operand is still close by.

Matrix multiplication is the canonical demonstration because it has enormous latent reuse and a naive schedule that throws almost all of it away. Multiplying two $N \times N$ matrices performs about $2N^3$ operations on $3N^2$ words — an intensity proportional to $N$, which for large $N$ is spectacularly compute-bound in principle. Executed as three nested loops in the obvious order, though, each element of one input is re-read from main memory on every pass, and the realised intensity collapses toward a small constant. The available reuse and the exploited reuse are different quantities, and only the second appears in the roofline.

Tiling manufactures the locality that was not there

The repair is to restructure the loops so that the working set of the innermost computation is small enough to sit in a fast store and is used many times before being evicted. Partition the operands into $b \times b$ blocks and compute block by block. Three such blocks — two inputs and an accumulator — must be resident simultaneously, so the tile size is bounded by the fast-store capacity $M$ in words:

Taking $b$ as large as the constraint allows gives

Two things in that expression matter more than the constant. First, traffic falls linearly in $b$: doubling the tile halves the bytes moved, which is why tiling is the single highest-leverage transformation in dense linear algebra. Second, and less often noticed, traffic falls only as $M^{-1/2}$. Quadrupling the fast store buys a factor of two in traffic, not a factor of four. That square root is the reason architects cannot simply spend their way out of the problem with more SRAM, and it is worth holding on to when reading any claim that a larger cache will fix a bandwidth-bound kernel.

This is analysis, not measurement, and the analysis is optimistic in a specific way: it assumes the tile actually stays resident. Real caches are set-associative, so a tile whose rows are separated by an unfortunate stride can evict itself. The practical consequence is that the best block size is usually well below the one the capacity bound permits, and it is found empirically rather than derived. That empirical search is exactly what modern compilers automate; TVM was built around exposing such loop and memory transformations as a searchable space and fitting a learned cost model to guide the search rather than relying on hand-tuned vendor libraries ^[13].

Buying a round trip with arithmetic

Tiling addresses reuse inside one operation. Fusion addresses the traffic between operations. If several operations are applied in sequence to the same tensor, the naive schedule writes each intermediate out to main memory and reads it back for the next; the fused schedule loads the input once, keeps the intermediate in registers or scratchpad, and writes only the final result ^[1].

The arithmetic of when this is worth doing is stark. A round trip to HBM for one half-precision value costs four bytes of traffic. At the intensity ratios above, those four bytes are worth on the order of a hundred arithmetic operations before the trip becomes the cheaper option. This is why the correct instinct in a memory-bound region is almost the opposite of the one taught for compute-bound code: recomputing a value is usually cheaper than fetching it, and adding substantial redundant arithmetic to eliminate one materialised intermediate is normally a win rather than a compromise.

Milakov and Gimelshein’s treatment of softmax is the small, clean case. The textbook formulation makes several passes over the input — one to find the maximum, one to accumulate the exponential sum, one to normalise — and each pass is a separate trip through memory. Their online formulation computes the normaliser in a single pass by rescaling the running sum whenever a new maximum appears, at the cost of extra multiplications. They report softmax accelerating by up to 1.3 times, and softmax fused with a top-k selection by up to 5 times ^[10]. The extra arithmetic was not merely tolerable; it was the mechanism.

There is an important limit on naive fusion, and the FlashAttention authors state it precisely: during training, intermediate values often still have to be written to memory because the backward pass needs them, which reduces the effectiveness of fusion considerably ^[1]. Fusion alone cannot eliminate an intermediate that something later still requires. Eliminating it requires a second idea.

Attention, where recomputation beats storage

That second idea is recomputation, and attention is where it pays best.

Standard attention forms the score matrix $\mathbf{S} = \mathbf{Q}\mathbf{K}^{\top}$, applies a row-wise softmax to obtain $\mathbf{P}$, and multiplies by $\mathbf{V}$. Both $\mathbf{S}$ and $\mathbf{P}$ are $N \times N$, and standard implementations materialise them in main memory, which is quadratic in sequence length ^[1]. That materialisation is the problem. It is a large intermediate, it is written and read at least once, and the operations applied to it — masking, softmax, dropout — are exactly the memory-bound kind.

Rabe and Staats showed first that the quadratic memory cost is not intrinsic. Attention over a single query needs constant memory with respect to sequence length, and self-attention needs logarithmic memory; their practical implementation uses memory proportional to the square root of the sequence length, and at length 16,384 reduced self-attention’s memory overhead by 59 times for inference and 32 times for differentiation ^[11]. Time complexity remains quadratic — nothing here makes attention asymptotically cheaper in arithmetic. What changes is the footprint.

FlashAttention converted that observation into wall-clock speed by combining tiling with recomputation. Blocks of the inputs are loaded into on-chip SRAM, the softmax reduction is performed incrementally across blocks using the online normaliser, and the output is written back without the score matrix ever reaching main memory; for the backward pass, the softmax normalisation factors are kept from the forward pass so that attention can be recomputed on-chip, which the authors state is faster than reading the stored intermediate back from HBM. Their analysis gives $O(N^2 d^2 M^{-1})$ HBM accesses against $\Omega(Nd + N^2)$ for standard attention, with a matching lower bound showing no exact algorithm can do asymptotically better across all SRAM sizes ^[1]. The reported results were a 7.6 times speedup on the attention computation itself for GPT-2, 15 per cent faster end-to-end BERT-large training against the MLPerf 1.1 record, 3 times on GPT-2 and 2.4 times on long-range arena, plus qualitatively new capability at length: 61.4 per cent on Path-X at 16K and 63.1 per cent on Path-256 at 64K, both above chance for the first time.

The sentence worth dwelling on is the authors’ own: even with the increased FLOPs due to recomputation, the algorithm both runs faster and uses less memory. Faster and smaller, while doing strictly more arithmetic, with no approximation whatsoever. That combination is only possible because the currency being spent and the currency being saved are different, and only one of them is scarce.

The trade generalises. Chen and colleagues had already shown the same exchange in training generally: checkpointing a subset of activations and recomputing the rest yields memory proportional to the square root of network depth at the cost of one extra forward pass, taking a 1,000-layer residual network from 48 GB to 7 GB for about 30 per cent additional running time ^[12]. Attention is the case where the exchange happens to be free.

It also took three attempts to extract the available performance, which is itself evidence about difficulty rather than principle. FlashAttention-2 reported that the original reached only 25 to 40 per cent of theoretical peak FLOPs, attributed the gap to work partitioning between thread blocks and warps and to avoidable shared-memory traffic, and reached 50 to 73 per cent after repartitioning ^[2]. FlashAttention-3 reported 35 per cent utilisation on H100 for the prior version and achieved 1.5 to 2.0 times speedup, up to 740 TFLOPs/s at 75 per cent utilisation in FP16 and close to 1.2 PFLOPs/s in FP8 ^[3]. Each step is a further reduction in bytes moved at some level of the hierarchy, not a new mathematical result.

Capacity and bandwidth are not the same constraint

These two get conflated constantly, in vendor material and in engineering conversation alike, because both are reported in the same paragraph of a datasheet and both produce the complaint “we need more memory”. They are separate limits with separate symptoms and separate remedies.

Capacity determines what fits. Exceed it and the job fails outright, or falls back to a slower tier. Bandwidth determines how fast resident data can be streamed. Exceed the budget and nothing fails; the job simply runs at a fraction of peak while the arithmetic units idle.

Serving a language model exhibits both at once, which is why it is such a good teaching case. The key-value cache is a capacity problem: Kwon and colleagues found it grows and shrinks dynamically per request and is badly wasted by fragmentation and duplication, which caps the achievable batch size; managing it in pages, as an operating system manages virtual memory, brought waste to near zero and improved throughput by 2 to 4 times at the same latency ^[14]. Not one arithmetic operation changed. The gain came from fitting more requests in the same store.

The same cache is simultaneously a bandwidth problem, because generating each token requires streaming the weights and the accumulated cache through the arithmetic units. Pope and colleagues developed analytical models for exactly this partitioning trade, and reported 29 milliseconds per token during generation for PaLM 540B with int8 weights alongside 76 per cent model FLOPS utilisation during large-batch processing of input tokens ^[15]. That pair of numbers is the whole story in miniature: the same model on the same hardware sits near the compute roof in one phase and nowhere near it in the other, because the ratio of arithmetic to bytes differs between them.

A diagnostic follows. Halve the batch size and observe. If throughput per request improves, the binding constraint was capacity — you were paging, spilling or fragmenting. If time per request is unchanged and total throughput falls proportionally, the constraint was bandwidth. Multi-query and grouped-query attention relieve the first by shrinking the cache — Pope and colleagues report enabling context lengths up to 32 times larger — and relieve the second by reducing bytes streamed per token, but they are two distinct effects of one change and should be measured separately ^[15]. Offloading, conversely, buys capacity and spends bandwidth: ZeRO-Infinity’s staging across NVMe and CPU memory made otherwise impossible models trainable while sustaining over 25 petaflops on 512 V100 GPUs, which its authors characterise as roughly 40 per cent of peak ^[16].

Where the disagreement actually lies

Practitioners agree on the diagnosis and disagree on two design responses, and it is worth characterising the disagreement rather than resolving it.

The first is whether on-chip memory should be managed by hardware or by software. The GPU lineage bets on caches plus massive multithreading: keep enough concurrent work in flight that memory latency is hidden, and let hardware policy decide residency. The TPU took the opposite position — Jouppi and colleagues describe a 28 MiB software-managed on-chip memory and argue explicitly that omitting caches, out-of-order execution and prefetching produces a deterministic execution model better matched to a 99th-percentile latency requirement, since those features help average throughput more than guaranteed latency ^[6]. Both camps accept the roofline; they disagree about who should decide what stays resident, and the honest summary is that the answer depends on how predictable the workload’s access pattern is.

The second is whether the fusion and tiling decisions can be automated. Compiler research argues they can and should be searched rather than hand-written ^[13]. The attention record argues the other way in practice: three hand-engineered revisions were needed to move from 25 to 40 per cent of peak to roughly 75 per cent, and each depended on architecture-specific facts about warp scheduling and asynchrony ^{[2, 3]}. My reading is that both observations are correct at different points in a hardware generation’s life, but that is an interpretation, not a settled result.

Predictions, with the observations that would falsify them

These are forecasts, separated from the sourced analysis above. Horizon: 8 August 2029. The assumptions are that the divergence in scaling rates reported by Gholami and colleagues continues, that no memory technology closes the bandwidth gap by an order of magnitude, and that transformer-like architectures remain dominant.

One. The ridge point of mainstream accelerators — peak arithmetic rate divided by achievable bandwidth — will be higher in 2029 than in 2026, so more kernels will be memory-bound at the same intensity. Indicator: published microbenchmark studies in the style of Luo and colleagues. Disconfirmed if a mainstream training accelerator ships whose measured ridge point is lower than its predecessor’s.

Two. Recomputation-for-storage trades will spread beyond attention into other memory-bound primitives, appearing as default settings rather than opt-in flags. Indicator: framework defaults and kernel library documentation. Disconfirmed if the technique remains confined to attention and gradient checkpointing.

Three. Reported kernel performance will increasingly be accompanied by measured bytes moved or achieved bandwidth, not only TFLOPs, because a FLOPs figure alone cannot distinguish a fast kernel from a compute-bound one. Disconfirmed if leading kernel papers in 2029 still report throughput without any traffic or intensity measurement.

Four. The gap between automatically generated and hand-written kernels for fusion-heavy operations will narrow but not close within one hardware generation of a new architecture’s launch. Disconfirmed if a compiler-generated attention kernel matches the best hand-written implementation on a new architecture within six months of its availability.

What to take away

The hierarchy is not an implementation detail beneath the algorithm. It is the constraint the algorithm is written against, and it is the reason two implementations of identical mathematics can differ by an order of magnitude in wall-clock time.

Three habits follow. Compute the arithmetic intensity of an operation before optimising it, because it tells you which roof you are under and therefore which changes can possibly help. Treat capacity and bandwidth as separate budgets with separate diagnostics, because a fix for one is frequently neutral or harmful for the other. And when a memory-bound region is the bottleneck, look for arithmetic to spend rather than arithmetic to save — recomputing an intermediate on-chip is routinely cheaper than the round trip that would have retrieved it.

A dispensary keeps the same goods in four places and organises itself entirely around not walking. That is the whole design. A fast kernel is fast for the same reason: not because of what it computes, but because of what it never went to fetch.