E1.2 · LESSON 2 OF 6

Prefill

Trace a generation request through prefill and decode and distinguish latency, throughput and hardware bottlenecks.

THE IDEA

Prefill: reading the whole prompt at once

The first model phase is prefill: the model processes all the prompt tokens and stores the keys and values it will need for generation. Because the whole prompt is known, many positions can be computed together on a GPU, which makes this phase good at using the hardware. A rough cost is 2 · N · P floating-point operations for N parameters and a prompt of P tokens.

"Together" does not mean "independently": attention is causal, so each position may only use itself and earlier ones. The parallel computation must give the same answer as going one position at a time.

parameters (billions)7prompt tokens1,000GPU utilisation of a 10¹⁴ FLOP/s peak0.5

FLOPs ≈ 2 · N · P = 2 · 7e9 · 1,000 = 1.40e+13 time ≈ 1.40e+13 / 5.0e+13 = 0.28 s (all prompt positions are processed together)

demo prompt length5

Blue = token (row) may use token (column). Work is done for all rows at once, but only the lower triangle is allowed: 15 pairs for 5 tokens. Parallelism must respect the causal rule.

Change the model and the prompt. The grid shows what each token may look at.

Predict first. Can every prompt position be processed independently of the causal computation rules?

Chapter context

An autoregressive model first processes a prompt, then generates tokens whose identities determine later steps. Prefill and decode often have different hardware behavior, so a single tokens-per-second number does not describe the whole request.

TRY IT YOURSELF

Part 1. Do it hands-on

Estimate prefill FLOPs and time by hand, then write the cost model, the causal mask and a check that parallel and sequential agree.

parameters (billions)7prompt tokens1,000GPU utilisation of a 10¹⁴ FLOP/s peak0.5

FLOPs ≈ 2 · N · P = 2 · 7e9 · 1,000 = 1.40e+13 time ≈ 1.40e+13 / 5.0e+13 = 0.28 s (all prompt positions are processed together)

demo prompt length5

Blue = token (row) may use token (column). Work is done for all rows at once, but only the lower triangle is allowed: 15 pairs for 5 tokens. Parallelism must respect the causal rule.

FLOPs for 7e9 × 1000 seconds at 5e13 FLOP/s causal pairs for 4 tokens

To do: Prefill FLOPs ≈ 2 · N · P. A 7·10⁹-parameter model and a 1000-token prompt. Type the FLOPs (like 1.4e13)
To do: The GPU delivers an effective 5·10¹³ FLOP/s on this work. Seconds of prefill?
To do: Causal masking: prompt token i attends to tokens 1…i. For a 4-token prompt, how many (token, earlier-or-same token) pairs are computed?

Part 2. Do it in code

prefill_flops(N, P): 2·N·P.
prefill_seconds(N, P, flops_per_sec, utilization=1.0): prefill_flops / (flops_per_sec · utilization). utilization must be in (0, 1] (ValueError).
causal_pairs(P): the number of (token, earlier-or-same token) pairs: P(P+1)/2.
causal_mask(P): a (P, P) boolean array that is True where a token may attend (column ≤ row).
prefill_matches_sequential(X, W): X is (P, d) prompt vectors and W a (d, d) matrix. Compute a causal running sum of X @ W two ways: all positions at once (np.cumsum) and one position at a time in a loop. Return True if they agree.

import numpy as np

def prefill_flops(N, P):
    pass

def prefill_seconds(N, P, flops_per_sec, utilization=1.0):
    pass

def causal_pairs(P):
    pass

def causal_mask(P):
    pass

def prefill_matches_sequential(X, W):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can every prompt position be processed independently of the causal computation rules?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For roughly steady output gaps:

T_{request}\approx TTFT+(n_{out}-1)\,ITL.

For a simplified single-sequence dense weight scan, FLOPs≈2N and weight bytes≈Nb, giving arithmetic intensity≈2/b FLOPs per byte. This excludes activations, KV traffic and other work.

Worked example

A fictional request has TTFT=0.20 seconds and then emits four more tokens at 0.05-second intervals. Five outputs finish in 0.20+4×0.05=0.40 seconds. Steady decode rate is 1/0.05=20 tokens/second; total request output rate is 5/0.40=12.5 tokens/second. Both are valid measurements with different definitions.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
first,gap,count=.2,.05,5
elapsed=first+(count-1)*gap
assert isclose(elapsed,.4)
assert 1/gap == 20
assert isclose(count/elapsed,12.5)
assert 2/2 == 1

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

An average latency hides tail behavior. Prefill/decode bottlenecks depend on batch and shapes, not only phase names. Compare metric definitions before comparing serving engines.