KV Cache — the flag comes down

Time to pay off Lesson 2's flag: generation runs the whole model once per token. Here's the horror show that would happen without today's mechanism.

Recall the machinery: to generate token 6, every token attends to previous tokens using Keys and Values (Topic 7). Naively, that means step 6 re-runs the full transformer over all six tokens — recomputing K and V vectors for tokens 1–5 that were already computed in steps 1–5. Step 100 recomputes 99 tokens' worth. Step 1,000 recomputes 999. Total work across a generation grows quadratically, almost all of it redundant.

The saving observation is beautifully simple: causal masking (Topic 7) means old tokens never see new ones — so their K and V vectors never change. Token 3's Keys and Values are identical at step 4, step 400, and step 4,000. Anything that never changes can be computed once and cached:

So the KV cache is exactly that: for every layer and every head, store each processed token's K and V vectors. Each generation step then does the minimum possible work — compute Q, K, V for the one new token, attend its Q against all cached K/V, append its own K/V to the cache, done. Per-step compute stops growing with conversation length (mostly), and generation becomes viable at all. Every chatbot you've ever used runs on this.

But the trade is memory, and the meeting-minutes analogy makes it visceral: instead of re-interviewing everyone in the room each time a new person speaks (recompute), the room keeps minutes (cache) — each new speaker just reads them. Wonderful. Except the minutes notebook grows with every utterance and starts occupying real shelf space. How much? The formula, worth deriving once:

bytes per token = 2 (K and V) × layers × KV-heads × head-dim × bytes-per-value

For Llama-2-7B era models (32 layers, 32 heads, dim 128, FP16): 2×32×32×128×2 = ~0.5 MB per token. A 4K conversation: 2 GB. A 32K conversation: 16 GB — more than the quantized model itself. The purple segment devouring the pantry.

This pain is why every modern model ships with GQA (Grouped-Query Attention) — the one architecture tweak you must know: instead of every query head having its own K/V, query heads share K/V in groups. Llama-3-8B keeps 32 query heads but only 8 KV heads — the multi-head "specialists" from Topic 7 keep their distinct questions (Q) but share notebooks (K/V) four-to-a-desk, at negligible quality cost. Cache per token: 2×32×8×128×2 = 128 KB — a 4× cut. Now 32K costs 4 GB (yesterday's diagram), 128K costs 16 GB. Further tricks stack on top: quantizing the cache itself (8-bit KV is common and cheap — Topic 24 logic applied to the notebook), and sliding-window schemes that cap how far back some layers look.

One more distinction crystallizes here, and it will organize Topic 34: processing the prompt is different from generating. The prompt's tokens all exist upfront, so their K/V can be computed in parallel in one big pass — this is prefill, and it's what you wait for before the first token appears. Then decode takes over: the one-token-at-a-time cached loop above. Two phases, utterly different characters. Hold that.

---