Explain the KV cache: prefill vs decode, why it grows, and how MQA/GQA and PagedAttention help.

TL;DR: During generation the model caches the key and value vectors of every past token, per layer and head, so it never recomputes them. This cache grows linearly with sequence length and batch size and is what actually caps concurrency, usually more than the weights do. Shrink it with MQA/GQA (share K/V across query heads), KV quantization, and PagedAttention (non-contiguous paged storage that kills fragmentation).

How to approach it. Separate the two phases first (prefill vs decode), because the cache exists to make decode cheap. Then quantify why it grows, and show that it, not the weights, bounds how many requests you can serve. The mitigations fall out of that.

A strong answer. Prefill vs decode. Generation has two phases with opposite cost profiles. Prefill processes the whole prompt in parallel, computing keys and values for every prompt token at every layer. It is compute-bound and cheap per token. Decode then emits one token at a time, and each new token must attend to all previous tokens. Without caching you would recompute every previous token's keys and values at every step, which is quadratic and wasteful. The KV cache stores those keys and values so each decode step only computes the new token's K/V and reuses the rest. That makes decode memory-bandwidth-bound (you stream the cache plus weights), not compute-bound.

Why it grows. The cache size is roughly 2 (K and V) × num_layers × num_kv_heads × head_dim × seq_len × batch × bytes. It scales linearly with both sequence length and batch. For a large model with long context and a real batch, this reaches tens of GB and often exceeds the headroom left after weights, so the KV cache, not the weights, is what limits concurrent sequences.

Mitigations. These attack different factors in that formula:

• MQA / GQA. Multi-Query Attention shares one K/V head across all query heads; Grouped-Query shares across groups. This cuts the num_kv_heads factor with minimal quality loss, which is why modern models ship GQA.
• KV quantization. Store K/V in INT8/FP8 to halve or quarter cache memory.
• PagedAttention (vLLM). Store the cache in fixed-size non-contiguous pages, like OS virtual memory, instead of one contiguous block per sequence. This kills the fragmentation and over-allocation of variable-length sequences, so you pack far more concurrent requests into the same memory.
• Continuous batching complements paging: finished sequences free their pages immediately for new requests.

The throughline: serving economics are decided at decode time by KV-cache memory and bandwidth, which is why every one of these optimizations exists.

Key takeaways

• Prefill is compute-bound and parallel; decode is memory-bandwidth-bound and sequential, and the cache is what makes decode cheap.
• Cache memory scales with layers × kv_heads × head_dim × seq_len × batch, and at real concurrency it caps throughput before weights do.
• GQA shrinks the kv_heads factor, quantization the bytes factor, PagedAttention the wasted slack.
• PagedAttention plus continuous batching is the combination that turns spare memory into higher batch size.

What interviewers probe next.

• "Why is decode memory-bound but prefill compute-bound?" Prefill does big parallel matmuls over the whole prompt; decode does one token at a time, dominated by reading the cache and weights from memory.
• "How much does GQA save?" Proportional to the head-sharing ratio: 8 query heads sharing 1 K/V head cuts that factor ~8x, with little quality impact.
• "PagedAttention vs naive allocation?" Naive pre-allocates max-length contiguous cache per sequence (huge waste); paging allocates on demand in small blocks, raising achievable batch size sharply.
• "Long-context cost?" Cache scales with seq_len, so very long contexts are expensive; combine GQA, quantization, and sometimes attention-window tricks.

Common mistakes.

• Thinking weights are the serving bottleneck; at real concurrency the KV cache usually is.
• Not distinguishing prefill (compute-bound) from decode (memory-bound).
• Forgetting the batch and sequence-length factors that make the cache blow up.
• Treating MQA/GQA as a quality trick rather than primarily a KV-cache memory reduction.