ALLMAcademy

D1

Prefill vs Decode, the KV Cache, and PagedAttention

12 min
  1. 01Explain why prefill is compute-bound (sets TTFT) while decode is bandwidth-bound (sets TPOT/ITL)
  2. 02Estimate KV-cache memory growth and explain why it, not weights, caps serving concurrency
  3. 03Describe how GQA/MQA and KV quantization shrink the KV footprint
  4. 04Explain how PagedAttention turns KV memory into a schedulable, fragmentation-free resource
Narration — Prefill vs Decode, the KV Cache, and PagedAttention
0:00 / 0:00

One request, two workloads

topic 3

A single generation runs in two phases on the same chip:

  • Prefill processes the whole prompt in one parallel pass. It is compute-bound and sets TTFT (time to first token).
  • Decode emits one token per step, re-reading the full weights plus the growing KV cache from HBM for a single-token matrix-vector multiply. That low arithmetic intensity makes it bandwidth-bound, and it sets TPOT/ITL (the inter-token gap — the terms are used interchangeably).
Prefill pegs compute; decode pegs bandwidthInteractive · 2D

The prompt slides in as one block (compute meter ~100%, TTFT stopwatch), then tokens emit one-by-one with a looping read-from-HBM arrow (bandwidth meter ~100%, TPOT gap).

Loading diagram…
Text description

The prompt slides in as one block (compute meter ~100%, TTFT stopwatch), then tokens emit one-by-one with a looping read-from-HBM arrow (bandwidth meter ~100%, TPOT gap).

The KV cache is the real ceiling

Why KV memory caps concurrency

Per-token KV size ≈ 2 × layers × kv_heads × head_dim × precision_bytes (the 2 is keys + values). It grows linearly with sequence length and batch size, and the aggregate often rivals or exceeds the weights at long context. Levers to shrink it: GQA shares one KV head across a group of query heads (~4–8× typical reduction), MQA collapses to a single shared KV head (largest reduction), and KV quantization trades a little quality for headroom.

PagedAttention

KV memory as paged virtual memory

PagedAttention stores KV in fixed-size, non-contiguous blocks addressed by a per-sequence block table, cutting reservation waste from a directional ~60–80% to a few percent. Copy-on-write prefix sharing lets sequences reuse identical prefix blocks (the mechanism behind automatic prefix caching), and under pressure it preempts via recompute or CPU-swap with LRU eviction.

Common MisconceptionDecode is slow because it does heavy compute per token.

CorrectionDecode is bandwidth-bound — it re-reads weights+KV from HBM for one matrix-vector multiply, leaving the FLOPs idle.

Common MisconceptionThe KV cache is tiny next to the model weights.

CorrectionAt long context × batch the aggregate KV cache rivals or exceeds the weights, which is why it caps concurrency.

Production failure modes

  • KV OOM under load triggering preemption and recompute storms.
  • Head-of-line blocking when a long prefill stalls everyone behind it.
  • A non-GQA model at long context blowing the memory budget.
  • Naive contiguous KV reservation fragmenting memory and rejecting new requests.

Retrieval Practice

Check one idea at a time

Question 1 of 2

Why is the decode phase memory-bandwidth-bound rather than compute-bound?