KV cache.

A cache you keep because attention looks backwards

Generation is a loop. The model has produced $t-1$ tokens and must produce the $t$-th. Self-attention at that position needs a query from the current token and a key and value from every position up to it:

with $M$ the causal mask. The naive loop recomputes $K$ and $V$ for the whole prefix at every step. That is pure waste, and the reason is worth stating precisely: the key and value at position $i$ are functions of the hidden state at position $i$ alone,

and causality guarantees $h_i$ never changes once produced. Nothing to the right can influence it. So $k_i$ and $v_i$ are constants for the rest of the sequence, and recomputing them is recomputing a value you already have.

Cache them and the per-step cost collapses. Generating $L$ tokens goes from

in attention FLOPs, and the projections $W_K h$, $W_V h$ go from $\Theta(L^2)$ to $\Theta(L)$. This is not a marginal optimisation — without it, long-context generation is not merely slow, it is infeasible. Every production inference stack does it, which is why the interesting question is never whether to cache but what the cache then costs you.

Two tensors per layer, and the arithmetic that follows

For one sequence the cache is a pair of tensors per layer, each of shape $[n_{kv},\,L,\,d_h]$ — number of key/value heads, positions so far, head dimension. Queries are not cached: the query for step $t$ is used once and discarded. Values are, because the weighted sum at every future step needs all of them.

The size formula

Counting elements: two tensors, $n_l$ layers, $n_{kv}$ heads, $d_h$ per head, $b$ bytes per element, $B$ sequences of length $L$:

Everything except $L$ and $B$ is fixed at architecture time. The per-token cost

is therefore a property of the model you can read straight off its config, and it is the number worth memorising for any model you deploy. For Llama-3.1-70B — 80 layers, 8 KV heads, $d_h=128$, bf16:

Note what is absent. The number of attention heads $n_h$ does not appear — only $n_{kv}$. That gap is the entire subject of §05. Nor does the model's parameter count: a wide, shallow model and a narrow, deep one with the same $n_l \cdot n_{kv} \cdot d_h$ have identical cache costs and very different weights.

Where the memory actually goes

Weights are a fixed cost you pay once per GPU. The cache is a variable cost you pay per concurrent user per token, and it is the one that decides how many of them you can serve. Below, real configurations read from their published config.json.

* MLA stores a single latent vector of 512 dims plus a 64-dim shared positional key per layer, not a per-head K and V — see §06. Weights are parameter count × 2 bytes. Cache @128k is one sequence at the model's full context window. Configurations read from each model's published config.json; GPT-2 XL's 128k figure is hypothetical, since its window is 1,024.

Why decoding wastes almost all of your FLOPs

The cache is not only a capacity problem. It is a bandwidth problem, and this is the part that surprises people who size clusters by TFLOPs.

Take one decode step, one layer, batch $B$, context $L$. The attention over the cache reads

and performs a $QK^\top$ and an $AV$, each $2BLn_h d_h$ FLOPs:

The ratio is the arithmetic intensity — how much work you extract per byte moved. Note that $B$, $L$ and $d_h$ all cancel:

This is a remarkable little result. The arithmetic intensity of decode attention is independent of context length and of batch size. You cannot batch your way out of it. It depends only on the query-to-KV head ratio and the bytes per element — which is to say, on two architectural decisions and a quantisation choice.

Fewer KV heads, held at the same quality

$n_{kv}$ appears linearly in both the size formula and the intensity formula, which makes it the highest-leverage number in the architecture. The obvious move is to shrink it — and the obvious risk is that you lose the representational diversity that made multi-head attention work.

GQA partitions $n_h$ query heads into $g$ groups sharing one KV head each, so $n_{kv}=g$ and the cache shrinks by $n_h/g$. The compression is exact and structural — there is no approximation in the attention itself, only fewer distinct keys and values to attend to. Crucially, it also raises arithmetic intensity by the same factor, so GQA buys capacity and speed:

Models are not usually trained from scratch as GQA. The standard recipe is uptraining: take an MHA checkpoint, mean-pool the key and value projections within each group, then continue training on a small fraction — around 5% — of the original budget. The mean-pool matters; picking one head per group and discarding the rest is markedly worse.

Caching a compressed latent instead of the keys

GQA removes heads. Multi-head Latent Attention removes the representation: it caches a single low-rank vector per token per layer and reconstructs every head's key and value from it on the fly. This is what lets DeepSeek-V3 — a 671B model — hold a smaller cache than an 8B Llama.

Project the hidden state down to a latent of dimension $d_c \ll n_h d_h$, and cache only that:

The obvious objection is that you have traded memory for compute — you now decompress $n_h$ keys and values on every step. The trick is that you never have to. Inside the score, the up-projection can be folded into the query projection ahead of time:

so attention scores are computed directly against the cached latents. $W^{UK}$ is a fixed weight matrix; it never needs to materialise a single key. The same absorption works on the value side into the output projection. This is the whole idea, and it is why MLA is not simply "compression with a decompression cost".

Rotary embeddings bake position into the key

RoPE applies a position-dependent rotation to queries and keys before the dot product. With $R_m$ the rotation for position $m$,

which is the property that makes it work: the score depends only on the relative offset $n-m$. But it also means the tensor you cache is $R_n k_n$, not $k_n$ — position is already inside the stored value. Two consequences follow, and both are practical.

The allocator, not the algorithm

Everything above concerns how much cache a token needs. This section is about how much a naive serving system wastes, which through 2023 was most of it.

The obvious implementation reserves a contiguous buffer per sequence at its maximum possible length, because the cache grows and reallocation is expensive. That single decision produces three separate wastes:

• Internal fragmentation. A request that could emit 2,048 tokens but stops at 200 holds a 2,048-token buffer for its lifetime. Most of the reservation is never touched.
• Reservation waste. Slots allocated for tokens not yet generated are unusable by anyone else, even though the memory is provably idle right now.
• External fragmentation. Variable-length contiguous buffers leave gaps too small for the next request, exactly like a filesystem.

Measured across real serving traces, systems built this way used roughly 20–40% of the KV memory they held. PagedAttention's contribution was to notice that this is a problem operating systems solved in the 1960s, and to apply the same answer: stop requiring contiguity.

The waste bound is worth writing down. With block size $\beta$, each sequence wastes at most $\beta - 1$ slots in its final block, so for $B$ sequences of mean length $\bar L$:

At $\beta=16$ and $\bar L = 512$ that is under 3%. The block size is a real trade-off rather than a free parameter: smaller blocks waste less but lengthen the block table and add indirection per attention step; larger blocks amortise the lookup but waste more and make prefix sharing coarser.

The second gain is the one that compounds. Because blocks are indirected, two sequences with a common prefix can point their block tables at the same physical blocks, with copy-on-write when they diverge. Parallel sampling, beam search and shared system prompts all stop duplicating memory. That is the bridge to §09.

The cheapest cache is one you already filled

Prefill is $\Theta(L^2)$ and dominates time-to-first-token on long prompts. But real traffic repeats itself heavily: a fixed system prompt on every request, the same few-shot examples, the same document re-queried, an agent loop replaying its entire history each turn. If a prefix has been computed before, its keys and values are still valid — position is baked in (§07), but a prefix starts at position 0 by definition, so the rotations are correct.

The security caveat. A cache shared across users is a side channel. If a hit is measurably faster than a miss, an attacker can test whether a particular prefix is already cached and learn what other users have sent. Production systems isolate the cache per tenant, or accept the leak knowingly.

Fewer bits per number

$b$ sits in the size formula as a plain multiplier, so halving it halves the cache and doubles arithmetic intensity. fp16 → fp8 is close to free on modern models and is the default in most serving stacks. Below that it stops being free, and the reason is structural rather than numerical.

Intensity assumes the $n_h/n_{kv}=8$ geometry of Llama-3.1-70B; the H100 ridge point is 295, so even 3-bit KV remains memory-bound. Quantisation buys capacity first and speed second. Errors accumulate: a quantised key written at position 10 is re-read for every subsequent token, so per-token error is not independent — this is why long-generation quality degrades more than a short-prompt benchmark suggests.

Keeping fewer tokens

Every technique so far stores all $L$ tokens more cheaply. The alternative is to stop storing some of them — turning a linear cost into a bounded one, at the price of information you cannot recover.

The honest framing is that these are lossy and the loss is workload-dependent. Eviction policies are scored on benchmarks where the dropped tokens turned out not to matter; needle-in-a-haystack retrieval is precisely the task where a heavy-hitter policy discards the needle, because it was never attended to until the question arrived. A policy chosen on summarisation can fail badly on retrieval, and the failure is silent.

Interleaving is the current compromise: a few full-attention layers among many local-attention ones keeps a path for long-range information while capping most of the cache. It is an architectural decision made at training time, not a serving switch.

Moving it off the GPU, and what is still unsolved