Chapter 2 — The KV Cache Challenge

Second post of the chapter-by-chapter walkthrough of LLM Primer VI: Scaling AI Systems. The chapter that names the data structure that eats every serving system's VRAM before the weights ever get a chance to.

Why this chapter exists

The autoregressive loop of Chapter 1 avoids quadratic work by remembering. At each decoding step, the model needs to attend to every previous token, and doing so from scratch would rerun the whole prefill each iteration — an N-fold multiplier over the length of a completion. The key-value cache is the workspace that saves that arithmetic. It stores the per-token K and V projections at every layer so that later tokens only compute their own K and V and read the earlier ones back. The cache is the reason decoding stays roughly O(N) rather than O(N²). It is also, in every production system I have looked at, the largest single consumer of VRAM. Chapter 2 walks the formula that governs its size, the architectural variants that shrink it, and the fragmentation problem that wrecks the naive way to allocate it.

One line: The KV cache trades arithmetic for memory — and the memory scales with batch, sequence length, layers, heads, and head dimension all at once, which is why serving clusters run out of VRAM before they run out of anything else.

2.1 The formula that governs cache size

KV memory for one sequence is 2 × L × H_kv × D × S × bytes: two tensors (K and V), L layers, H_kv key/value heads, head dimension D, sequence length S, and precision-bytes per element. Multiply by batch size for the fleet-level number. Every axis is multiplicative. Llama-3-70B with L=80, H_kv=8 (GQA), D=128, at S=8,192 and BF16, holds about 40 GB of cache per sequence — before batch. At batch 32, the cache alone approaches 1.3 TB, several times the weights themselves and several times the VRAM of an H100. Llama-2-70B, the last major MHA model, has H_kv=64 rather than 8 and its cache is eight times larger for the same configuration. The formula is not a curiosity; it is the number that determines how many concurrent users a chip can hold. Every other memory budget on the box — activations, framework overhead, temporary buffers — has to fit around it.

2.2 MHA, GQA, and MQA are cache-size design choices

The H_kv term is the term modern architectures have engineered down. Multi-head attention (MHA) uses one K and V head per query head; the cache is fat, the quality is highest, and each head can specialize its notion of what to attend to. Multi-query attention (MQA) collapses to a single shared K and V head; the cache shrinks by a factor of H, but the heads lose specialization and measurable quality is lost on longer contexts. Grouped-query attention (GQA), introduced in 2023 and now the dominant choice for Llama-3, Mistral, Mixtral, Qwen, and DeepSeek, partitions the query heads into G groups that share K and V; a typical G = H/8 gives an eightfold cache reduction at a quality cost small enough that evaluation suites cannot reliably see it. GQA is not free — it reduces the K/V projection parameter count too, and that budget gets redistributed elsewhere in the model — but empirically the redistribution rarely hurts. MLA (multi-latent attention, DeepSeek-V2) pushes further with a low-rank latent cache; it is the research direction, but production deployments in 2026 are GQA-dominant.

2.3 Naive allocation wastes most of the budget

The obvious way to allocate KV memory — reserve a contiguous slab per sequence, sized to the maximum possible length — fails on contact with real traffic. Most requests complete far short of the maximum; the reserved tail is dead memory. On Llama-3-70B with a 32K limit, a 1,000-token completion wastes 31 slabs' worth of KV cache. Batch 32 with an 8K limit and average length 800 leaves roughly 90 percent of the reserved KV cache unused at any given moment. Worse, the layout is inflexible: a new arrival cannot use another sequence's unused tail, because the tail is already committed. Concurrency collapses to whatever the worst-case budget allows, not what the average traffic could support. The problem is internal fragmentation — the same failure mode operating systems solved with paging in the 1960s. Chapter 8 shows how PagedAttention brings that solution across.

Worth holding onto: The KV cache — not the weights — is the reason a serving cluster's concurrency plateaus. Any technique that shrinks it (GQA, MLA, quantized KV, sliding windows, paging) buys concurrency at the same rate it buys memory back.

What Chapter 2 sets up

The cache formula and its axes will resurface every time later chapters have to reason about how many users fit on one GPU. Chapter 3 uses it to explain why VRAM capacity matters more than FLOPs when picking a serving GPU. Chapter 7 uses it to explain why continuous batching is bounded by the KV cache and not by the model. Chapter 8 uses it to justify PagedAttention, H2O eviction, and prefix caching — three techniques whose entire purpose is to make the cache behave more like a paged virtual memory and less like a slab of reserved bytes. The formula is the grammar of the rest of the book's memory arguments.

Next — Chapter 3: Data Center GPUs for Generative AI. The silicon that has to hold both the weights and the KV cache, read by mechanism rather than by spec sheet.

Want the full picture? The book chapter includes the full derivation of the KV formula, the pseudocode for a caching decoder step, a worked numerical example on Llama-3-70B at S=8,192 and batch 32, and the In Plain English sidebar comparing MHA, GQA, and MQA as filing-cabinet strategies. View LLM Primer VI on Amazon →