Why naive decode would repeat itself
To predict token 50, attention compares the new token against every earlier token. Done naively, each decode step would re-process the entire sequence from scratch — token 2 reads 1 token, token 1000 reads 999. The total work grows with the square of the length, and you would recompute the same things over and over.
The fix is to remember. For each past token, attention needs two vectors — a key and a value. Those never change once computed, so we store them and reuse them. That store is the KV cache.
Diagram of attention as a query matched against keys and values with softmax weights.
How the cache turns the loop cheap
With a cache, prefill computes keys and values for the whole prompt once and stores them. Each decode step then computes the key and value for only the one new token, appends them, and attends over the cache. Per-step work becomes constant instead of growing — this is the single trick that makes long answers practical.
The catch: the cache eats your GPU
Nothing is free. The cache stores a key and value for every token, in every layer, for every attention head — so its size is *length × layers × heads × width × 2*. The KV cache memory cost climbs straight-line with conversation length, and for long contexts or many users it can dwarf the model weights themselves.
The KV cache grows with every factor at once — sequence length, layers, heads, and width — times two for the key and the value.
This is why GPU memory for LLMs is the budget that governs serving. A card holds the weights plus every active request's cache. When the cache fills the card, you cannot admit one more user — the GPU may be 90% idle on math yet completely out of room.
# rough KV cache size for one sequence, fp16 (2 bytes/number) bytes = n_tokens * n_layers * 2 * n_kv_heads * head_dim * 2 # = length * layers * (K and V) * heads * width * fp16 # e.g. 4096 tokens, 32 layers, 8 KV heads, 128 dim -> ~0.5 GB per request
Paging: borrow the trick operating systems already use
Early servers reserved a contiguous slab of memory for each request, sized for the longest answer it might give. Most answers are short, so most of that slab sat empty — wasted. KV cache paging (popularized as PagedAttention) fixes this by splitting the cache into small fixed-size blocks, the way an OS splits RAM into pages.
Blocks are handed out on demand and reclaimed the instant a request finishes, so almost no memory is stranded. The payoff is dramatic: paging routinely lets a GPU hold several times more concurrent requests, which directly raises how many users you can serve per card.
Flash attention: don't build the giant matrix
There is a second memory trap inside attention itself. The textbook recipe forms an length × length score matrix in memory before applying softmax — at long context that matrix can be gigabytes. Flash attention avoids ever materializing it: it streams attention in small tiles that fit in the GPU's tiny on-chip memory, computing the result block by block.
The textbook recipe materialises the length×length matrix QK^T before softmax; flash attention computes the same result without ever storing it whole.
The math is identical; only the memory traffic changes. By keeping work in fast on-chip memory instead of bouncing huge matrices to and from the card's main memory, flash attention speeds up prefill especially, where that score matrix is largest. Paging tames the KV cache; flash attention tames the attention computation. Together they decide how much you can fit.