Prefill and decode

Text generation is autoregressive: the model chooses one token at a time, and each token it chooses becomes part of the input to the step that chooses the next. That constraint applies to the answer and not to the question, because every token of the prompt is already known before any work starts. The two halves of one request therefore hand the hardware very different amounts of work that can proceed at the same time, and they are different enough to carry separate names.

This chapter is about where that difference comes from and what it costs. Prefill and decode do nearly the same arithmetic per token and run at rates that differ by more than two orders of magnitude on the same card, because one of them saturates the arithmetic units and the other spends 99% of its time waiting for weights to arrive from memory. Everything else in this topic — which latency metric to watch, what batching buys, why one timed request tells you almost nothing — follows from that split.

One pass over 2,000 positions, then 300 passes over one#

During prefill the server holds the whole prompt at once. Every one of a 2,000-token prompt's positions goes through every layer together, as a matrix of shape 2,000 × 4,096 rather than 2,000 separate vectors. Attention at each layer is a matrix multiplication over the full sequence with a causal mask, so position 1,847 can attend to everything before it in the same operation that computes position 12. The hardware sees large, dense matrix multiplications, which is exactly the shape a GPU is built for. Prefill ends with the first output token.

Decode has the opposite shape. Once that first token is sampled, the server runs the model again for exactly one new position — a matrix of shape 1 × 4,096 — attending back over the 2,000 prompt positions plus whatever it has generated so far. Then it samples, appends, and does it again. Three hundred output tokens are 300 sequential forward passes, and the serialisation is not an implementation choice that a better scheduler could remove, because token 214 is an input to the pass that produces token 215.

That dependency is what turns a property of the hardware into something a user feels, and the chain is short enough to check link by link. Each decode step needs the token the previous step produced, so no two steps of one sequence can be in flight at the same time. A sequence's decode time is therefore a sum over its steps rather than the maximum of them. Each step in that sum has a floor set by how long it takes to read the weights once. Put those together and the generation rate one user sees is bounded by memory bandwidth divided by model size, and no amount of additional hardware moves it by running steps concurrently, because at the moment a step begins the input to the next one does not exist yet. More hardware can help only by making each individual step cheaper — splitting the model across cards so that each card reads a fraction of the bytes. Prefill has the opposite property from top to bottom: its positions do not depend on one another within a layer, so they can be spread over whatever hardware is available, which is why the two phases respond so differently to every knob there is to turn.

Calling prefill "parallel" is a small simplification worth correcting immediately. The layers still run in sequence — layer 12 needs layer 11's output for every position — so what is parallel is the positions within each layer, not the depth of the network. Attention within prefill is also quadratic in sequence length rather than linear, so a 2,000-token prompt does four times the attention work of a 1,000-token one even though it does twice the feed-forward work. At 2,000 tokens on an 8-billion-parameter model the feed-forward terms dominate and prefill time looks close to linear in prompt length; at 32,000 tokens the quadratic term is no longer a rounding error, and prefill time starts bending upward faster than the token count does.

Each phase produces its own latency metric, and both are worth fixing now because the rest of this topic lives on them. Time to first token (TTFT) is how long from request to the first piece of output, and on a normally functioning server it is dominated by prefill. Inter-token latency (ITL) is the gap between consecutive output tokens during decode, sometimes reported as its reciprocal, the per-request generation rate in tokens per second. Total response time is a composition of the two:

total ≈ TTFT + (output_tokens − 1) × ITL

Anything that reports only the left-hand side has thrown away the information needed to explain a change in it.

Why decode is limited by memory bandwidth rather than arithmetic#

A forward pass through a dense transformer costs roughly two floating-point operations per parameter per token. For an 8-billion-parameter model that is about 16 GFLOP per token. It also requires reading every parameter out of the GPU's high-bandwidth memory — HBM, the pool of memory physically attached to the card — into the compute units, and in bfloat16, which spends two bytes per number, those 8 billion parameters occupy 16 GB.

Both of those quantities repay deriving rather than accepting, because every conclusion in this chapter is a ratio between them. Take the arithmetic first. Nearly all the work in a forward pass is matrix multiplication, and inside a matrix multiplication each weight meets each token's activation exactly once: one multiply, then one addition into a running sum. Two floating-point operations per parameter per token, which is where the factor of two comes from. Multiplying by 8 billion parameters gives about 16 GFLOP for a single token. It is "about" because this counts only the multiplications involving weights and ignores attention's own score-and-weighted-sum arithmetic, which uses no parameters; at short sequence lengths that omission is small, and it is the same omission that makes prefill look linear in prompt length until the sequence gets long.

Now the bytes. Every one of those parameters has to be physically present in the compute units to be multiplied by anything, and until it is fetched it sits in HBM. At two bytes each in bfloat16, 8 billion of them is 16 GB that must cross from memory into the arithmetic units before a pass can happen at all.

Those two requirements scale differently with how many tokens you process in one pass. The FLOPs scale with the token count. The weight read does not: you read the 16 GB once per forward pass regardless of whether that pass carries one token or two thousand.

The asymmetry deserves its own sentence, because the rest of the chapter is built on it. A weight fetched out of HBM lands in on-chip storage, and while it is sitting there it can be multiplied against as many token activations as the pass happens to be carrying. Fetching it once and using it two thousand times costs exactly the same memory traffic as fetching it once and using it once. So the bytes are set by the size of the model, the FLOPs are set by the size of the model times the number of tokens in the pass, and the token count appears in one of those two quantities and not the other.

PARAMS = 8e9
BYTES_PER_PARAM = 2          # bfloat16
HBM_BANDWIDTH = 3.35e12      # bytes/sec, H100 SXM
ACHIEVED_FLOPS = 4.2e14      # bf16 matmul, ~45% of peak in practice

def pass_cost(tokens):
    flops = 2 * PARAMS * tokens
    compute_s = flops / ACHIEVED_FLOPS
    memory_s = (PARAMS * BYTES_PER_PARAM) / HBM_BANDWIDTH
    return compute_s, memory_s

print(pass_cost(2000))  # (0.0762, 0.0048)  -> compute-bound by 16x
print(pass_cost(1))     # (0.000038, 0.0048) -> memory-bound by 125x

The prefill pass over 2,000 tokens needs 32 TFLOP of arithmetic and 16 GB of weight traffic. On an H100 SXM those cost about 76 ms and about 4.8 ms respectively, so arithmetic dominates and the memory system is comfortably keeping up.

Each of those timings is a single division, and both repay doing by hand once. The arithmetic side: 16 GFLOP for one token, multiplied by the 2,000 positions in the prompt, is 32 TFLOP. Divide 32 TFLOP by the 4.2e14 operations a second this card actually sustains on bfloat16 matrix multiplication — the achieved rate, not the headline peak, which no real kernel reaches — and the answer is about 76 ms. The memory side: 16 GB of weights divided by 3.35 terabytes a second of HBM bandwidth is about 4.8 ms. Compute comes out around sixteen times larger than memory, and since the two proceed at the same time, the pass takes as long as the slower of them. The memory system finishes its half of the work early and then has nothing to do.

The decode pass over one token needs 16 GFLOP and the same 16 GB of weight traffic. The arithmetic takes 38 microseconds. The weight read takes 4.8 milliseconds. The GPU spends more than 99% of that step waiting on memory bandwidth with its arithmetic units mostly idle, and no amount of faster math changes the answer, because the binding constraint is how fast 16 GB can be pulled out of HBM. The theoretical floor of 4.8 ms per token is 209 tokens per second; a measured 143 corresponds to about 68% bandwidth efficiency, which is ordinary once you account for kernel launch gaps, the fact that real memory systems do not hit their spec sheet, and the step's other read: the stored per-position state that the next chapter is about.

Those last two conversions are one division each as well. A floor of 4.8 ms per token means at most one token every 4.8 ms, and a second divided by 4.8 ms is 209 of them. The measured 143 divided by that ceiling of 209 is 68%, which is the share of the card's theoretical bandwidth that the decode step converts into tokens once every real cost is included.

The two phases can be compared in one number rather than four, and that number is what makes the reversal predictable instead of surprising. Ask how much work a pass does per byte it moves. A pass carrying some number of tokens does two operations per parameter per token, and it moves two bytes per parameter. Divide the first by the second and the parameter count cancels, and so does the factor of two, leaving one operation per byte for each token the pass happens to be carrying. The work-per-byte of a pass is its token count. Set against that, the hardware has a balance point of its own: this card sustains about 125 operations for every byte its memory system can deliver, which is what its achieved arithmetic rate divided by its bandwidth means. A pass carrying fewer tokens than that balance is demanding more bytes than it can find work for, and one carrying more is demanding more arithmetic than the bytes require. Decode carries one token, which is short of the balance by a factor of 125 — the number in the comment on the last line of the code above. Prefill carries 2,000, which is past it by about sixteen — the number in the line before. Every other result in this chapter is a consequence of those two figures landing on opposite sides of one threshold.

A database analogy makes the shape of that waste concrete. Reading 16 GB of weights to produce one token is a full table scan that returns a single row, and the cost of the scan is fixed no matter how small the answer is. A query planner faced with that situation looks for other queries that need the same scan and answers them from the one pass, which is precisely the move that batching makes later in this topic. Prefill is the same scan answering two thousand rows at once, which is why its per-token cost looks so much better even though the scan cost is identical.

That is an analogy, so it needs its limit stated. A database answers a scan that returns one row by building an index, and an index works because the answer depends on a small identifiable subset of the rows. There is no index to build here. A dense model uses every one of its parameters to produce every token, so no subset could be consulted in place of the whole; the 16 GB is not a pessimistic access pattern that a smarter lookup would avoid, it is the amount of information the next token genuinely depends on. What can be reduced is the size of each parameter rather than the number of them consulted, which is exactly why quantisation moves the number and why cleverer indexing has nothing to offer.

This is the single most useful fact here, because it explains results that otherwise look contradictory. Decode speed tracks memory bandwidth, so it improves when you buy a card with faster HBM, when you quantise the weights — store each number in 8 or 4 bits instead of 16, so that there are fewer bytes to move for the same model — or when you find a way to make one weight read serve more than one sequence. It does not improve much when you buy more FLOPs.

Two rows there deserve emphasis. The phases grow with different inputs, which is why a request's cost is not one number but two, and why a change to prompt template length and a change to max_tokens show up in completely different places. And they respond differently to batching, because a phase that is already saturating the arithmetic units has nothing left to give, while a phase that is 99% idle waiting on memory has enormous headroom the moment you find more work to do per weight read.

Four things the split is not#

It is not a distinction between the prompt being cheap and generation being expensive. Per token, prefill and decode do very nearly the same arithmetic; the 147× gap in throughput is entirely about how much of that arithmetic runs concurrently. Providers charging several times more per output token than per input token are pricing the fact that a decode token occupies the machine for far longer, not that it involves more computation.

It is not an artefact of hosted APIs that you can escape by running the model yourself. The same two phases exist in llama.cpp on a laptop, in a transformers loop in a notebook, and in every production serving engine, because the shape comes from the model and from autoregression rather than from anyone's serving architecture. What a hosted API changes is your visibility into the split, not its existence.

It is not what two neighbouring measurements report, and both get mistaken for it. GPU utilisation as reported by nvidia-smi is the fraction of time at least one kernel was resident, and during decode it will happily read 95% while the arithmetic units sit idle waiting on memory, so it tells you the GPU is busy and nothing about whether it is doing useful work. Tokens per second is likewise two different quantities that share a name: per-request decode rate, which is what a user experiences, and aggregate server throughput summed over all concurrent requests, which is what a capacity plan needs. Later chapters turn on the gap between them, and a benchmark that does not say which one it reports is not quotable.

And it is not a claim that prefill is always small. At 2,000 prompt tokens it was 4% of wall clock, but prefill cost grows with prompt length while decode cost does not, so a 100,000-token document prompt with a 50-token answer inverts the picture entirely — several seconds of prefill in front of a third of a second of generation. The ratio is a property of your workload's shape rather than of the model.

Two phases, two bottlenecks, two metrics. Prefill is compute-bound, scales with prompt length, and produces time to first token; decode is bandwidth-bound, scales with output length, and produces inter-token latency. Holding them apart is what converts "it got slower" into a statement about which phase moved and therefore which lever applies, and collapsing them into total response time is what makes so many latency results look contradictory.

There is an obvious question sitting under the decode numbers. If each output token requires a forward pass, and position 2,214 attends back over every position before it, why does the pass for token 300 cost roughly the same 7 ms as the pass for token 1 rather than 300 times more? A naive implementation would re-run the entire prefix through the network on every step. Real servers do not, because prefill leaves per-position state behind and decode reads that state instead of recomputing it — which is the subject of the next chapter, and the reason a first measurement against a fresh server is unrepresentative of everything after it.