Walk me through what KV cache is, why LLM generation would be extremely slow without it, what exactly gets stored, how much memory it consumes at scale, and what tradeoffs it creates for serving systems.

Question

Accepted Answer

Why naive inference is catastrophically slow

LLMs generate one token at a time, autoregressively. To generate token t, the model attends to all previous tokens 0..t-1. Without a cache, this means re-running the full forward pass for every new token — including recomputing Q, K, V projections for every past token in every layer. For a 4k-token context, generating token 4000 requires recomputing all 4000 positions: O(n²) total work across the sequence.

What KV cache stores

During a transformer forward pass, each layer projects inputs into keys K and values V. These tensors depend only on the past tokens — once computed for position i with fixed weights, they never change.

KV cache stores K and V tensors for every layer as tokens are processed. For each new decode step:
1. Compute Q, K, V for the new token only
2. Append new K, V to the cache
3. Attend: Q_new × K_cached^T → attention weights → weighted sum over V_cached
4. Project to logits, sample next token

Per-step compute drops from O(n) projections + O(n²) attention to O(1) projection + O(n) attention.

Memory cost — the real constraint

Cache size per request = 2 × n_layers × seq_len × n_kv_heads × d_head × bytes

Llama-3 8B example (32 layers, GQA with 8 KV heads, d_head=128, float16):
2 × 32 × 8192 × 8 × 128 × 2 bytes ≈ 1.1 GB per request

A serving system handling 100 concurrent requests at 8k context needs ~110 GB for KV caches alone — often exceeding the model weights. This is why memory, not compute, is the primary constraint in LLM serving at scale.

Prefill vs decode phases

Prefill: the full prompt is processed in one parallel forward pass. All KV pairs computed and cached simultaneously. GPU compute-bound — fast because every position is parallelized.

Decode: one token generated per step, reading the full KV cache. Memory-bandwidth-bound — the bottleneck is streaming KV tensors from HBM, not FLOP throughput. Larger batches help: reading KV once and processing multiple queries amortizes bandwidth cost.

GQA/MQA: reducing cache size

Multi-Query Attention (MQA): all Q heads share one K,V pair. Cache shrinks by n_heads×. Fast but slightly lower quality.

Grouped-Query Attention (GQA): Q heads grouped, each group shares one K,V pair. Llama-3 uses 8 KV heads for 32 Q heads — 4× cache reduction with minimal quality loss. Now the default for production-scale models.

Serving systems that manage cache pressure

PagedAttention (vLLM): KV cache split into fixed-size pages like virtual memory. Eliminates fragmentation, enables on-demand allocation, and allows sharing prefix cache across requests — system prompts cached once, shared by all concurrent users.

Prefix caching: if multiple requests share a common prefix (e.g., a long system prompt), compute and cache it once, reuse across requests.

Common traps

- "KV cache makes attention O(1)" — wrong. It avoids recomputing old K/V, but each new token still attends over the full cached context: O(n).
- Ignoring memory bandwidth — decode throughput is often bottlenecked by reading the cache, not matrix multiplications.
- Treating context length as a quality-only setting — it directly controls memory per request and thus serving capacity.