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

TL;DR: While generating, the model stores the key and value vectors for every prior token, per layer and head, to avoid recomputing them. That cache scales linearly with sequence length and batch size and is what truly limits concurrency, typically more than the weights do. Cut it with MQA/GQA (share K/V across query heads), KV quantization, and PagedAttention (non-contiguous paged storage that eliminates fragmentation).

How to approach it. Split 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, sets how many requests you can serve. The mitigations follow from 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 or FP8 instead of FP16 and the cache halves: both are eight-bit, so the payload ratio is exactly 2x, less the per-block scales you store alongside. Getting to 4x means either a 32-bit starting point or a 4-bit destination, so always state the source and destination precision. Quoting "2 to 4x" for eight-bit KV is the tell that someone has not written the arithmetic down.
• 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.