Section 11

Prefill and decode

The two phases of inference

Sources: Orca: A Distributed Serving System for Transformer-Based Generative Models — Yu et al., 2022; Efficient Memory Management for Large Language Model Serving with PagedAttention — Kwon et al., 2023

The naive generation loop from the last section has a particular structure that, once you notice it, divides inference into two very different regimes. The first call processes a long, parallel input (the prompt). In ordinary cached decoding, each subsequent call processes one new token. These two regimes (prefillprefillThe first forward pass that processes the entire prompt at once. Compute-bound, parallel over prompt tokens.See in glossary → and decodedecodeThe autoregressive phase: one forward pass per generated token. Memory-bandwidth-bound — the GPU mostly waits on weights.See in glossary →) have very different performance characteristics, and every later optimization in this essay is grounded in understanding why.

Prefill: parallel and compute-bound

When a request arrives with a 1,000-token prompt, we need to run the whole prompt through the model once to get to a state where we can start generating the next token. That first pass (called prefill) is happy news for the GPU:

  • All 1,000 tokens can be processed in parallel. The attention computation sees all of them; the MLP runs on all 1,000 hidden vectors at once.
  • A single forward pass does ~1,000 tokens’ worth of work per layer.
  • The matrix multiplications are big: the Q/K/V projections become a (1000, 4096) × (4096, 4096) matmul, which is a tensor-core’s dream.

For sufficiently long prompts or large prompt batches, prefill is usually compute-bound: the GPU’s arithmetic units are the bottleneck. On an H100, it can process tokens at thousands of tokens per second per request because much of the work fits cleanly into large matrix multiplies. Very short or unusual workloads can behave differently.

The latency you experience before the first token is the time to first tokenTTFTTime-to-First-Token — wall-clock from request submitted to first generated token returned. Dominated by prefill.See in glossary → (TTFT): wall-clock from request submitted to first generated token returned. Prefill is often a major part of TTFT for non-trivial prompts, alongside queueing, scheduling, and other serving overheads.

Decode: serial and memory-bound

After prefill, the final position’s logits let us sample the first generated token. Efficient decoding then repeats three steps: append one sampled token, run that one new token through all layers, and use the resulting logits to sample the following token. Processing only one new token per step relies on the KV cache introduced in the next section.

That one-token forward pass is the painful part. For a dense model, it still requires reading most parameters from HBM (about 16 GB for Llama-3-8B at fp16, ~140 GB for 70B) but the matrix multiplies are now tiny: (1, 4096) × (4096, 4096). The matrix units finish quickly and then wait. The bottleneck is not the math; it is how fast bytes can move from HBM into the matrix units.

This is memory-bound behavior. A rough upper-bound estimate for batch-1 dense decode divides HBM bandwidth by weight size: Llama-3-8B at fp16 is about 16 GB, and an H100 SXM has 3.35 TB/s of HBM bandwidth, giving 3,350 ÷ 16 ≈ 209 tokens per second before other overheads. Real throughput can be lower; with batching, one read of the weights can serve many requests and aggregate per-GPU throughput can be much higher.

The latency per token during decode is the inter-token latencyITLInter-Token Latency — gap between consecutive generated tokens during decode.See in glossary → (ITL): the gap between two consecutive output tokens.

Why this split matters

You can see the asymmetry in a back-of-envelope ratio called arithmetic intensity: roughly, FLOPs per byte read. Prefill can do hundreds of FLOPs per byte because the weights are reused across many tokens. Batch-1 decode is around 1 FLOP per byte of fp16/bf16 weight read when a multiply-add counts as two FLOPs, so it is highly memory-bound. The GPU’s hardware ratio (its FLOPs-per-byte capability) is hundreds. This is the gap inference engines are trying to close.

Inside one inference: prefill, then a stream of decodes
Step through a single request. Watch what changes from prefill to decode — and what stays the same.
Prefill
Sequence so far
Thecatsatonthesoft?
input to this pass just produced will be predicted
Input to this forward pass
6 tokens
All 6 prompt tokens at once, processed in parallel.
Output of this forward pass
1 new token
We only need logits at the last position to sample the next token. Prefill computes logits at every prompt position (training-style), but in inference we throw away all but the last.
Where the time goes this pass (Llama-3-8B on H100, ballpark)
Weight read from HBM4.78 ms · every parameter, once
Tensor-core compute0.10 ms · 2 · 8B · 6 = 96.0B FLOPs
Pass duration
4.78 ms
Compute utilization
2.0%
Tokens/sec
1256
Prefill is compute-bound: with 6 tokens in the batch, the tensor cores have real work to do and weight bandwidth isn't the bottleneck. The whole prompt gets processed in one shot.

Latency vs throughput: TTFT, ITL, throughput

Three metrics define a serving system’s performance:

  • TTFT (time to first token): primarily prefill time + queue time. What you notice when you press Enter.
  • ITL (inter-token latency): decode time per token, including time waiting for the GPU to finish a batched step. What you notice as the speed of the streaming text.
  • ThroughputthroughputTotal tokens generated per second across all concurrent requests. Often traded against per-request latency.See in glossary → (tokens/sec): total tokens generated per second across all concurrent requests. What the cloud bill cares about.

These three are in tension. Higher throughput usually means bigger batches, which means more queue time (worse TTFT) and slower per-step time (worse ITL). One of the central jobs of a scheduler is to manage this tradeoff in a way that respects whatever Service Level Objectives (SLOs) the service has, e.g. “p99 TTFT < 1 s, p99 ITL < 50 ms, maximize throughput within that envelope.”

What’s wrong with our naive loop

Right now, our generation loop redoes huge amounts of work. To predict token 1,001, we run the model on tokens 1–1,000 (already computed during prefill). To predict token 1,002, we run on 1–1,001 again. To predict 1,003, 1–1,002. The waste is repeatedly recomputing the projections and hidden states for the old context. With a cache, each prior token’s keys and values are computed once; each new token still has to attend over the growing cached context.

There has to be a better way, and there is. The model only ever attends to the past (causal mask). So once we’ve computed the keys and values for token 5, those values will never change as more tokens are appended. We can save them.

The cache of those saved KK and VV vectors is called the KV cacheKV cacheThe stored keys and values from all past tokens, so attention at step t only needs to compute Q for the new token.See in glossary →, and it is the single most important data structure in modern LLM serving. That’s the next section.