Why the KV Cache Exists

Prefill vs decode left us with a puzzle: decode generates one token at a time, and each new token must attend to every previous token. Done naively, that means redoing the whole sequence’s attention at every step — an O(n²) disaster. The KV cache is the fix, and understanding the trade it makes is the bridge into Part 3.

The naive version, and why it’s wasteful

Recall attention: each token computes a Query, and attends to the Keys and Values of all tokens so far. To generate token 101, the new token’s Query must dot against the Keys of tokens 1–100, then blend their Values.

Naively, at each decode step you’d re-run the model over the entire sequence to regenerate all those K and V vectors:

  step 1: compute K,V for tokens [1]
  step 2: compute K,V for tokens [1,2]          ← recomputes token 1 again
  step 3: compute K,V for tokens [1,2,3]        ← recomputes 1,2 again
  ...
  step n: compute K,V for tokens [1..n]         ← recomputes everything, again

Total work across n steps: 1 + 2 + 3 + … + n ≈ n²/2. You’d recompute the same K and V vectors over and over — pure waste, since a past token’s K and V never change: token 5’s Key is the same whether you’re on step 6 or step 600.

The fix: cache K and V, reuse them

The insight: K and V for a token, once computed, are fixed. So compute each token’s K and V exactly once and store them. On the next step, you only compute K and V for the one new token, append them to the store, and attend against the whole cache.

  KV cache (per layer), grows by one column per step:

  step 100:  [ k1 k2 k3 ... k100 ]   [ v1 v2 v3 ... v100 ]   ← stored
  step 101:  new token → compute ONLY k101, v101
             append:    [ ...k100 | k101 ]  [ ...v100 | v101 ]
             new Query attends over the full cache  ✓ reuse, no recompute

Now each decode step does O(n) work (attend the one new Query over n cached entries) instead of O(n²) (rebuild everything). The total generation drops from ~n²/2 down to ~n per step — the difference between quadratic and linear, which at long sequences is the difference between viable and not.

Note

Prefill is where the cache gets populated: processing the whole prompt in one pass computes K and V for every prompt token and writes them all into the cache at once. Decode then just appends one column per step. So the two phases share one data structure — prefill fills it, decode extends it.

The trade: save compute, spend memory

Nothing is free. You stopped recomputing K and V — you save compute — but now you must store them for every token, every layer, every request. That memory is the KV cache, and it becomes the dominant runtime constraint in serving.

	Without KV cache	With KV cache
K/V computed per decode step	O(n) — redo every past token	O(1) — the new token only
Total decode compute	O(n²)	O(n)
Extra memory	~none	grows with sequence × batch × layers

This is the classic systems trade — compute for memory — and it lands on the wrong side of Part 1’s verdict. Decode is already memory-bound; the KV cache adds more memory pressure and more bandwidth to read each step. We accept it because the compute savings are enormous, but the consequence is that KV-cache memory, not model weights, often decides how many requests a GPU can serve at once.

Worked example: how fast does it grow?

A rough KV-cache size formula:

$$\text{bytes} = 2 \times n_{\text{layers}} \times n_{\text{tokens}} \times d_{\text{model}} \times \text{bytes per value}$$

The leading 2 is for K and V. Take Llama-3-8B (32 layers, d_model = 4,096), FP16 (2 bytes), one sequence of 8,192 tokens:

2 × 32 × 8,192 × 4,096 × 2 = ~4.3 GB

For one request. The model weights are ~16 GB; a single long-context request’s KV cache is already over a quarter of that. Run a batch of 16 such requests and the KV cache alone wants ~69 GB — more than four times the weights, and approaching an 80 GB H100’s entire capacity. The cache, not the model, is what fills the card.

One refinement is coming: this rough formula assumes classic multi-head attention, where every layer caches K and V at full d_model width. Llama-3-8B actually ships grouped-query attention, which shrinks the cached width ~4× (to ~1.1 GB per request here) — exactly the accounting the next part opens with.

This is the door into Part 3

Everything in the inference-efficiency core is, at bottom, about managing this memory: sizing it precisely, packing it without waste (PagedAttention), shrinking it, and sharing it across requests (prefix caching). The first stop quantifies it carefully — continue to KV Cache Math: Sizing the Dominant Cost.

The architect’s lens

Pull back from the mechanics and answer the five questions that turn an implementer into an architect:

• Why does it exist? Because a past token’s K and V never change, yet naive decode recomputes them every step — an O(n²) waste. The cache exists to compute each token’s K/V exactly once and reuse them.
• What problem does it solve? The quadratic blowup of autoregressive decode. Caching turns total decode compute from O(n²) into O(n) — at long context, the difference between viable and not.
• What are the trade-offs? It trades compute for memory. The cache grows with sequence × batch × layers, and because decode is already memory-bound, it adds exactly the scarce resource — so KV-cache memory, not model weights, often decides how many requests a GPU can serve.
• When should I avoid it? The cache itself is non-negotiable for decode — you never turn it off. What you avoid is the naive, unbounded version when memory is tight: the fix is to size, page (PagedAttention), shrink, and share it, not to drop it. And there’s nothing to gain in a single forward pass (an embedding or classification call) where no token is ever reused.
• What breaks if I remove it? Decode reverts to O(n²): per-token latency climbs with position, throughput collapses, and long-context generation becomes economically impossible. You’d reclaim the cache’s memory only to overspend compute and bandwidth on a path that was already memory-bound.

Check your understanding

1. Why is naive autoregressive decode O(n²), and what specifically gets wastefully recomputed?
2. What property of a past token’s Key and Value makes caching them valid?
3. With the KV cache, what is the per-step decode compute, and what is it without the cache?
4. State the trade the KV cache makes in one sentence, and explain why it’s uncomfortable given decode’s existing bottleneck.
5. From the worked example, what three factors does KV-cache size scale with, and why can the cache exceed the model weights in memory?

Show answers

1. Because naive decode re-runs attention over the entire growing sequence at every step, recomputing the K and V vectors of all previous tokens each time; summed over n steps that’s ~n²/2 work. The wasted part is re-deriving past tokens’ K and V, which never change.
2. A past token’s Key and Value are fixed once computed — they don’t depend on later tokens — so they can be computed once and reused on every subsequent step.
3. With the cache, each step computes K/V only for the new token (O(1)) and attends over n cached entries (O(n)). Without it, each step recomputes all past K/V, making per-step work O(n) and total O(n²).
4. It trades compute for memory: it stops recomputing K/V (saving compute) at the cost of storing them (spending memory). It’s uncomfortable because decode is already memory-bound, so the cache adds more of exactly the resource that’s scarce.
5. It scales with number of layers, number of tokens (sequence length), and batch size (× d_model × bytes-per-value). With long sequences and/or large batches these multiply quickly, so the cache can exceed the fixed model weights — e.g. ~4.3 GB for one 8,192-token request under the full-width (multi-head attention) formula.