The generation loop: prefill and decode
An LLM writes its answer one token at a time. This session splits that loop into two phases: prefill, which reads the whole prompt in parallel and fills the KV cache, and decode, which makes one token per step and must read all the weights each time. You will learn to predict, with two numbers (weight bytes and memory bandwidth), why decoding is slow and how batching helps.
What you will learn
- How the autoregressive loop works, and why a KV cache turns quadratic repeated work into linear work
- Prefill: all prompt tokens in one pass, GEMMs, causal mask, logits only for the last position; why it is compute-bound
- Decode: one token per step, a GEMV against every weight matrix plus a read of the whole cache; why it is memory-bound
- Arithmetic intensity, the ridge point and the roofline, with real H100 and A100 numbers
- The survey’s example: why LLaMA-2-70B in FP16 needs 140 GB, and why one token takes tens of milliseconds on 2 A100s
- How batching shares the weight read, and why the KV cache keeps long-context decode memory-bound
- TTFT and TPOT, and how to estimate the latency of a request
Why this matters
You type a question into a chatbot. First there is a short wait. Then the answer appears word by word, at a steady speed. These two parts, the wait and the steady stream, come from two very different kinds of work inside the model. They are called prefill and decode.
Prefill is the model reading your whole prompt at once. All prompt tokens go through the network together, in parallel, and the model stores what it computed (the KV cache) so it never has to redo that work. Prefill ends with the first output token. Decode is everything after that: the model makes one token, appends it, makes the next one, and so on. Each decode step processes only one new token per sequence, but it must still read every weight of the model from GPU memory.
This difference decides almost everything in LLM inference. Prefill is limited by arithmetic (it is compute-bound). Decode is limited by how fast the GPU can read memory (it is memory-bound). The survey by Zhou et al. gives a concrete example: LLaMA-2-70B stored in FP16 needs 140 GB just for its weights, and generating one token on 2 NVIDIA A100 GPUs takes about 100 milliseconds. [Certain: both numbers are quoted from the survey, Section 2.] By the end of this session you will be able to derive the 140 GB yourself, compute a lower bound of about 34 ms for that token, and explain where the rest of the time goes.
Every later idea in this track builds on these two phases: the KV cache (session 80), latency metrics (session 81), the roofline (session 82), batching (session 84), quantization, speculative decoding, and serving systems such as vLLM. We continue from the post-training track (session 77), where we generated many samples during RL without asking how generation itself works. Now we open that box.
The generation loop
A decoder-only LLM is trained to predict the next token (see session 6). It gives a probability to a whole sequence by multiplying next-token probabilities:
- Read the symbols
- \(x_t\)
- the token at position \(t\) (an integer ID from the vocabulary)
- \(p_\theta(x_t \mid x_1, \dots, x_{t-1})\)
- the model’s probability for token \(x_t\), given all tokens before it; \(\theta\) are the weights
- \(T\)
- the length of the sequence
Generation uses formula (78.1) one factor at a time. Given a prompt of \(P\) tokens, the model computes the distribution of token \(P+1\), we choose one token from it (greedy, sampling, and so on; that choice is the topic of session 79), append it, and repeat. The loop stops when the model outputs an end-of-sequence token or when we reach a length limit. This is called autoregressive generation: each output becomes part of the next input.
There is a simple but slow way to run this loop: at every step, feed the whole sequence (prompt plus all tokens made so far) through the model again. That repeats a lot of work. Thanks to the causal mask, the hidden state at position \(i\) depends only on tokens \(1..i\). So when a new token is added, nothing at the old positions changes. The only thing the new position needs from the old positions is their keys and values in every attention layer. If we store those, each new step only has to process one token. The stored keys and values are the KV cache.
With the cache, the loop splits into two phases:
- Prefill (one step): run all \(P\) prompt tokens through the model at once, write their keys and values into the cache, and compute the distribution of the first output token.
- Decode (many steps): feed only the newest token, read the cache to attend to all earlier tokens, append the new key and value, and compute the next distribution.
Figure 1 runs this loop for real, inside your browser. It is a tiny one-layer transformer: width 4, one attention head, a vocabulary of 10 words. Its weights are random numbers with one decimal. Each step computes the actual keys, values, attention weights and logits, and the line of the loop that is running lights up. Switch the cache off to see how much work the naive loop repeats.
- input: prompt \(x_1, \dots, x_P\), max new tokens \(n\)
- \(\text{cache} \leftarrow \text{empty}\)
- \(\text{logits} \leftarrow \text{model}(x_{1..P}, \text{cache})\) // PREFILL
- \(\text{out} \leftarrow [\,]\)
- repeat \(n\) times:
- \(y \leftarrow \argmax(\text{logits})\); append \(y\) to out
- if out has \(n\) tokens: stop
- \(\text{logits} \leftarrow \text{model}(y, \text{cache})\) // DECODE
- return out
How to read Figure 1
Press Step. Step 2 is the prefill, part one: all five prompt rows go through the projections together, as one \((5 \times 4) \cdot (4 \times 4)\) matrix product, and five keys and values appear in the cache at once. Step 3 is the prefill, part two: the causal attention of the last position (purple bars), and the logits of that position only. Step 4 picks the word with the largest logit (“mat”, 1.17, just above “the”, 1.09). After that the loop alternates between line 6 (choose) and line 8 (decode): in each decode step one column is processed, one new key and value are appended, and one query attends to all cached keys. The live panel shows the work of each step: the prefill does 960 FLOPs for 288 bytes (3.33 FLOPs per byte), each decode step does about 1 FLOP per byte. The counter of positions processed ends at \(9 = 5 + 4\). With the cache switched off, every decode step re-processes the full sequence, the counter ends at \(35 = 5 + 6 + 7 + 8 + 9\), and the panel shows that the logits are exactly the same as with the cache.
We can write the work of the two loops as a count of positions that pass through the network. For a prompt of \(P\) tokens and \(n\) output tokens, the last output token is never fed back, so:
Figure 1 has \(P = 5\) and \(n = 5\): \(W_{\text{naive}} = 25 + 10 = 35\) and \(W_{\text{cached}} = 9\).
A more typical chat turn: \(P = 1000\), \(n = 500\). Then \(W_{\text{naive}} = 500{,}000 + 124{,}750 = 624{,}750\) and \(W_{\text{cached}} = 1{,}499\). The naive loop does about 417 times more weight work. The cost of the cache is memory: we must keep keys and values for all \(1{,}499\) positions. The rest of this session is about the two new kinds of steps the cache creates.
Prefill: read the whole prompt in parallel
In the prefill step the input is a matrix \(X \in \R^{P \times d}\): one row per prompt token, \(d\) numbers per row. Every linear layer multiplies this whole matrix by its weight matrix at once. In each attention layer \(\ell\), the step also computes the keys and values of all prompt positions and stores them:
- Read the symbols
- \(X^{(\ell)}\)
- the normalized hidden states that enter attention layer \(\ell\), one row per prompt token
- \(W_K^{(\ell)}, W_V^{(\ell)}\)
- the key and value projection matrices of that layer
- \(n_{kv}\), \(d_h\)
- the number of key/value heads and the size of each head (with grouped-query attention, \(n_{kv}\) is smaller than the number of query heads; see session 26)
Attention inside the prompt uses the causal mask, so position \(i\) attends to positions \(1..i\), exactly as in training. At the end, the model applies the output layer to the last position only, because only that position predicts the first new token. (In training, logits at all positions are needed. In inference, computing logits for all \(P\) positions wastes time and memory, especially with vocabularies of 128K tokens.)
The cost of prefill
Recall from session 25 that a forward pass costs about \(2N\) FLOPs per token for a model with \(N\) parameters (one multiply and one add per weight). Attention adds work that grows with the square of the prompt length. With the causal mask, about half of the score matrix is needed:
- Read the symbols
- \(N\)
- number of parameters; each is used once per token, for a multiply and an add
- \(P\)
- prompt length in tokens
- \(L\), \(d_{\text{attn}}\)
- number of layers and the total width of the query heads (\(n_h d_h\)); \(QK^\top\) and the weighted sum of values each cost \(2 d_{\text{attn}}\) FLOPs per pair of positions, and the causal mask keeps about \(P^2/2\) pairs
The important point is what prefill reads from memory. All \(P\) tokens use the same weights. So the weights are read from memory once and used \(P\) times. The work is large matrix–matrix multiplications (GEMMs), which GPUs are built for.
Llama 3 8B has \(N \approx 8.03 \times 10^9\) parameters, \(L = 32\) layers and \(d_{\text{attn}} = 4096\) (from its config.json). Weight FLOPs: \(2 \times 8.03 \times 10^9 \times 2000 = 3.21 \times 10^{13}\). Attention FLOPs: \(2 \times 32 \times 4096 \times 2000^2 = 1.05 \times 10^{12}\), only about 3% more.
On an H100 SXM (989 TFLOP/s dense BF16, 3.35 TB/s, numbers from session 42), the arithmetic takes at least \(3.31 \times 10^{13} / 9.89 \times 10^{14} \approx 33.5\) ms. Reading the 16.06 GB of BF16 weights takes only \(16.06 / 3350 \approx 4.8\) ms. The arithmetic is 7 times longer than the memory reading: prefill is compute-bound.
Decode: one token per step
In a decode step the input is a single row \(\mathbf{x}_t \in \R^{1 \times d}\) per sequence: the embedding of the token we just chose. In each layer, attention computes one query \(\mathbf{q}_t\), one key and one value, appends the key and value to the cache, and attends over everything in the cache:
- Read the symbols
- \(\mathbf{q}_t, \mathbf{k}_t, \mathbf{v}_t\)
- query, key and value of the new token (for one head)
- \(K_{\text{cache}}, V_{\text{cache}}\)
- the stored keys and values of all \(t-1\) earlier positions
- \([A; \mathbf{b}]\)
- append row \(\mathbf{b}\) at the bottom of matrix \(A\)
- no mask
- the newest token may see every earlier token, so the causal mask is not needed in decode
The new query is used once and thrown away; it is never cached. Only keys and values are reused by later tokens. The cache grows by one row per layer and per KV head at every step. Its size per token is
where the 2 counts K and V, and \(b\) is the bytes per number (2 for BF16 or FP16). For Llama 3 8B (\(L = 32\), \(n_{kv} = 8\), \(d_h = 128\)): \(s_{\text{kv}} = 131{,}072\) bytes = 128 KiB per token. For Llama 2 70B (\(L = 80\), \(n_{kv} = 8\), \(d_h = 128\)): 327,680 bytes = 320 KiB per token, or 1.34 GB for one sequence of 4,096 tokens. [Certain: computed from the published configs.] Session 80 studies this memory in depth.
Now look at the shapes in each linear layer. Prefill multiplies a \(P \times d\) matrix by a \(d \times d\) weight matrix. Decode at batch size 1 multiplies a \(1 \times d\) vector by the same matrix. This is a matrix–vector product (GEMV). Figure 2 runs both on a simulated GPU. The weight matrix is cut into 16 tiles. A GPU kernel copies one tile at a time from memory (HBM) to the chip, and the arithmetic units use the tile while the next one is being copied. Watch which of the two lanes is busy.
- for each tile \(W_t\) of \(W\) (16 tiles of \(1024 \times 1024\)):
- copy \(W_t\) and its share of \(X, Y\) // \(\text{bytes}/\beta\)
- \(Y \mathrel{+}= X W_t\) for all \(m\) rows // \(\text{FLOPs}/\pi\)
- time \(\approx \max(\text{bytes}/\beta,\ \text{FLOPs}/\pi)\) // (78.7)
How to read Figure 2
Press Play. On the decode side the orange memory lane is always busy and the blue compute lane shows only thin slivers: each tile takes about 0.63 µs to copy and only about 0.002 µs to use, so the arithmetic units are idle more than 99% of the time. The whole product takes about 10 µs and does 1.0 FLOP per byte. On the prefill side with \(P = 2000\), each tile takes about 4.2 µs of arithmetic, so the blue lane is always busy and the copies hide behind it: about 69 µs in total and 1,012 FLOPs per byte, compute-bound. Choose \(P = 256\): the intensity is about 228 FLOPs per byte, below the H100 ridge of 295, so now the memory lane is the one that never rests, even in prefill. With \(P = 16\) the prefill side looks like decode.
Arithmetic intensity and the roofline
To decide whether a step is limited by arithmetic or by memory, we compare two numbers. The arithmetic intensity of a piece of work is how many FLOPs it does per byte it moves between GPU memory (HBM) and the chip:
- Read the symbols
- \(I\)
- arithmetic intensity, in FLOPs per byte
- \(\pi\)
- the peak compute speed of the GPU (FLOP/s), for example 989 TFLOP/s on an H100 SXM in BF16
- \(\beta\)
- the memory bandwidth (bytes/s), for example 3.35 TB/s on an H100 SXM
- \(t\)
- a lower bound on the time of the step: the GPU can overlap arithmetic and memory reads, but it cannot beat either limit
The two limits are equal when \(I = \pi / \beta\). This is the ridge point: about 295 FLOPs/byte for an H100 SXM and 153 for an A100 80 GB. [Certain: ratios of NVIDIA datasheet numbers.] Work with intensity below the ridge is memory-bound; above it, compute-bound. This picture is the roofline model (Williams et al.); session 82 uses it for whole models.
For one linear layer \(Y = XW\) with \(X \in \R^{m \times d}\), \(W \in \R^{d \times d}\) and 2 bytes per number, we read \(W\) and \(X\) and write \(Y\):
Here \(m\) is the number of token rows that share one read of the weights: \(m = P\) in prefill, and \(m = B\) (the batch size) in decode. So the intensity is roughly the number of tokens processed per weight read. Prefill has \(m\) in the thousands. Decode at batch 1 has \(m = 1\). Figure 3 places both on the roofline.
How to read Figure 3
Start at \(m = 1\) (decode, one sequence): the intensity is about 1 FLOP/byte and the GPU reaches only 0.3% of its peak on an H100 (0.7% on an A100). Move the slider right. Each doubling of \(m\) roughly doubles the useful speed, as long as you are on the slanted part. The layer becomes compute-bound at about \(m = 345\) on the H100 and \(m = 165\) on the A100; after that, more tokens per read do not make each FLOP faster. A typical prefill (\(m\) in the thousands) sits on the flat part. Decode lives on the far left unless we batch many sequences.
Why decode at batch 1 reads all weights to make one token
Put the pieces together for one decode step with batch size \(B\) and \(T\) tokens already in each cache. The weights are read once per step, whatever \(B\) is. Each sequence reads its own cache:
- Read the symbols
- \(B\)
- batch size: how many sequences make one token each in this step
- \(T\)
- context length: tokens already in each sequence’s KV cache
- \(b N\)
- bytes of all weights (\(b = 2\) for BF16): read once per step and shared by the batch
- \(B T s_{\text{kv}}\)
- bytes of all KV caches: each sequence reads its own, so this is not shared
At \(B = 1\) and short context, the intensity is \(2N / 2N = 1\) FLOP per byte. That is 295 times below the H100 ridge. The arithmetic units are idle about 99.7% of the time, waiting for weights to arrive. So the speed of single-user decode is set by memory bandwidth alone:
where \(\beta_{\text{total}}\) is the summed bandwidth of all GPUs that hold a piece of the model (with tensor parallelism, each GPU reads only its own share of the weights, in parallel).
Memory. \(70 \times 10^9\) parameters \(\times\) 2 bytes (FP16) = 140 GB, the survey’s number. The exact count from the Llama 2 70B config (80 layers, width 8192, FFN width 28672, 64 query heads, 8 KV heads, vocabulary 32,000, untied embeddings) is 68.98 billion, so 138 GB. One A100 has 80 GB, so the model needs at least 2 GPUs. Together they have 160 GB, which leaves about 20 GB for the KV cache and activations: room for about 14 sequences of 4,096 tokens at 1.34 GB each.
Time. Two A100s read \(2 \times 2.039 = 4.078\) TB/s together. Formula (78.10): \(140 \text{ GB} / 4.078 \text{ TB/s} = 34.3\) ms per token, at most about 29 tokens per second. The arithmetic needs only \(2 \times 70 \times 10^9 = 1.4 \times 10^{11}\) FLOPs, which takes 0.22 ms at the two GPUs’ combined peak of 624 TFLOP/s. Memory reading is about 150 times longer than the arithmetic.
The gap. The survey reports about 100 ms, roughly 3 times our bound; the bound corresponds to about 34% of peak bandwidth. Real systems lose time to the communication between the two GPUs after each layer, to many small kernel launches, to attention over the cache, and to kernels that do not reach peak bandwidth. [Likely: the survey does not break the 100 ms down.] The lower bound is still the right first estimate: no software trick can make batch-1 decode faster than \(\text{bytes} / \beta\), except reading fewer bytes (quantization, smaller models) or making more tokens per read (batching, speculative decoding).
Batching: share the weight read
Formula (78.9) shows why batching is the main tool for decode throughput. The \(bN\) bytes are shared by all \(B\) sequences, so at short context the intensity is about \(B\), and the step time hardly changes as \(B\) grows. Total tokens per second grows almost linearly with \(B\). But the KV term \(B T s_{\text{kv}}\) grows with \(B\) too, and it is not shared. At long context it takes over. In the limit of very large \(B\), the intensity tends to \((2N + 4 L d_{\text{attn}} T)/(T s_{\text{kv}})\): about 124 FLOPs/byte for Llama 3 8B at \(T = 1024\), and only about 34 at \(T = 4096\). Both are below the H100 ridge, so decode with long contexts stays memory-bound at any batch size. Memory capacity also limits \(B\): all caches must fit next to the weights. Explore both effects in Figure 4.
How to read Figure 4
At \(B = 1\) the left bar is almost all weights, and the step takes about 4.8 ms for the 8B model (about 207 tokens/s at \(T = 1024\)). Increase \(B\): the green part grows, the step gets a little slower, but total tokens per second (orange) climbs fast, while each user’s speed (blue) drops only slowly. Now raise \(T\) to 4,096 or 8,192: the green part dominates and the orange curve flattens early. If the readout says the caches do not fit, that batch is impossible on this hardware. Switch to the 70B model to see the survey’s setting: about 34 ms per token at batch 1.
The latency of one request
A user sees the two phases as two different latencies. The time to first token (TTFT) is the time until the first output token appears; it is mostly the prefill (plus queueing in a real server). The time per output token (TPOT) is the average time of one decode step. The survey calls them first-token latency and per-output-token latency. For \(n\) output tokens:
- Read the symbols
- TTFT
- time to first token: grows with the prompt length \(P\), roughly linearly, plus a \(P^2\) attention part
- TPOT
- time per output token: set by the weight bytes and the cache bytes, almost independent of \(P\) for short prompts
- \(n\)
- number of output tokens; the first one comes from the prefill
Because one prefill token is about 150 to 300 times cheaper in time than one decode token, long answers are usually dominated by decode, while long prompts with short answers (summarization, retrieval, classification with an LLM, video question answering) are dominated by prefill. Figure 5 runs Algorithm 2 (below) once per step of a whole request, and shows for each step whether compute or memory sets the time.
- \(\text{clock} \leftarrow 0\); \(\text{cache} \leftarrow 0\) tokens
- for \(s = 0, \dots, n-1\): \(m \leftarrow (P \text{ if } s = 0 \text{ else } 1)\); \(T \leftarrow (0 \text{ if } s = 0 \text{ else } P + s - 1)\)
- \(F \leftarrow 2NmB\) \(+\ 4 L d_{\text{attn}}\, m\,(T + m/2)\, B\)
- \(\text{bytes} \leftarrow bN + B\,(T + m)\, s_{\text{kv}}\)
- \(I \leftarrow F / \text{bytes}\); \(t \leftarrow \max(F/\pi,\ \text{bytes}/\beta)\)
- \(\text{clock} \leftarrow \text{clock} + t\); \(\text{cache} \leftarrow T + m\) tokens; emit 1 token per sequence
How to read Figure 5
Press Step to walk through Algorithm 2 line by line. For the prefill (\(s = 0\), \(m = 2000\)) the compute bar is the long one: 33.5 ms of arithmetic against 4.9 ms of memory reading, intensity about 2,000 FLOPs per byte. For the first decode step (\(m = 1\), \(T = 2000\)) the picture flips: 4.87 ms of memory against 0.017 ms of arithmetic, about 1 FLOP per byte. Then press Play. With \(P = 2000\) and \(n = 500\), the total is about 2.47 s: the prefill is only 1.4% of the time, even though it handles four times as many tokens as the decode. Set \(n\) to 100 and \(P\) to 8,000: TTFT grows to about 147 ms and becomes 22.5% of the request. Raise \(B\): the decode steps get only a little slower, but the green cache grows \(B\) times; with long prompts and large \(B\) it no longer fits.
The algorithms and the code
- input: prompt tokens \(x_1, \dots, x_P\), maximum new tokens \(n\), a rule to choose a token from logits
- cache \(\leftarrow\) empty, one (K, V) store per layer
- logits \(\leftarrow\) model(\(x_{1..P}\), cache, positions \(1..P\)) // PREFILL: causal mask, writes \(P\) entries, returns logits of the last position only
- out \(\leftarrow\) [ ]
- repeat \(n\) times:
- \(y \leftarrow\) choose(logits); append \(y\) to out // greedy, sampling, ...
- if \(y\) is end-of-sequence or out has \(n\) tokens: stop
- logits \(\leftarrow\) model(\(y\), cache, position \(P + |\text{out}|\)) // DECODE: one token, reads all weights and the cache, appends 1 entry per layer
- return out
- input: parameters \(N\), layers \(L\), cache bytes per token \(s_{\text{kv}}\), new tokens per sequence \(m\), context \(T\), batch \(B\), GPU peak \(\pi\), bandwidth \(\beta\)
- FLOPs \(\leftarrow 2NmB + 4 L d_{\text{attn}}\, m\,(T + m/2)\, B\) // weights + causal attention; prefill: \(m = P,\ T = 0\); decode: \(m = 1\)
- bytes \(\leftarrow bN + B\,(T + m)\, s_{\text{kv}}\) // weights read once; cache read and written
- \(I \leftarrow\) FLOPs / bytes // compare with the ridge point \(\pi / \beta\)
- return \(\max(\text{FLOPs}/\pi,\ \text{bytes}/\beta)\) // formula (78.7): a lower bound
The PyTorch code below builds a tiny decoder (2 layers, width 32) with a hand-written KV cache. It generates 8 tokens with prefill and decode, generates them again with the naive loop, and checks that both give the same tokens and the same logits. It runs on a CPU in about a second.
import torch, torch.nn.functional as F torch.manual_seed(0) V, d, H, L = 50, 32, 4, 2 # vocab, width, heads, layers dh = d // H class Block(torch.nn.Module): def __init__(s): super().__init__() s.n1, s.n2 = torch.nn.LayerNorm(d), torch.nn.LayerNorm(d) s.qkv, s.o = torch.nn.Linear(d, 3 * d), torch.nn.Linear(d, d) s.ff = torch.nn.Sequential(torch.nn.Linear(d, 4 * d), torch.nn.GELU(), torch.nn.Linear(4 * d, d)) def forward(s, x, cache): # x: (B, T_new, d); cache: dict with "k","v" or empty B, T, _ = x.shape q, k, v = s.qkv(s.n1(x)).split(d, dim=-1) q, k, v = [t.view(B, T, H, dh).transpose(1, 2) for t in (q, k, v)] # (B, H, T_new, dh) if "k" in cache: # decode: append the new keys and values k = torch.cat([cache["k"], k], dim=2); v = torch.cat([cache["v"], v], dim=2) cache["k"], cache["v"] = k, v # the cache now covers all positions so far a = F.scaled_dot_product_attention(q, k, v, is_causal=(T > 1)) # prefill: causal mask; decode: 1 query sees all x = x + s.o(a.transpose(1, 2).reshape(B, T, d)) return x + s.ff(s.n2(x)) class TinyLM(torch.nn.Module): def __init__(s): super().__init__() s.emb, s.pos = torch.nn.Embedding(V, d), torch.nn.Embedding(64, d) s.blocks = torch.nn.ModuleList([Block() for _ in range(L)]) s.head = torch.nn.Linear(d, V) def forward(s, ids, caches, start): # start = number of positions already in the cache x = s.emb(ids) + s.pos(torch.arange(start, start + ids.shape[1])) for blk, c in zip(s.blocks, caches): x = blk(x, c) return s.head(x[:, -1]) # only the last position's logits are needed model = TinyLM().eval() prompt = torch.tensor([[3, 14, 15, 9, 26, 5]]) # P = 6 prompt tokens n_new = 8 @torch.no_grad() def generate_cached(ids): caches = [dict() for _ in range(L)] logits = model(ids, caches, 0) # PREFILL: all P tokens in one pass out, pos, work = [], ids.shape[1], ids.shape[1] while True: nxt = logits.argmax(-1, keepdim=True) # greedy choice out.append(nxt.item()) if len(out) == n_new: break logits = model(nxt, caches, pos) # DECODE: one token, reuse the cache pos += 1; work += 1 return out, work, caches[0]["k"].shape[2] @torch.no_grad() def generate_naive(ids): out, work = [], 0 for _ in range(n_new): logits = model(ids, [dict() for _ in range(L)], 0) # re-read the whole sequence every step work += ids.shape[1] nxt = logits.argmax(-1, keepdim=True) out.append(nxt.item()); ids = torch.cat([ids, nxt], dim=1) return out, work a, wa, cache_len = generate_cached(prompt) b, wb = generate_naive(prompt) print(a) print(a == b, "positions processed: cached", wa, "naive", wb, "cache length", cache_len) # the logits match too, not only the argmax caches = [dict() for _ in range(L)] full = torch.cat([prompt, torch.tensor([a[:3]])], dim=1) with torch.no_grad(): model(prompt, caches, 0) for i, t in enumerate(a[:3]): step_logits = model(torch.tensor([[t]]), caches, 6 + i) ref = model(full, [dict() for _ in range(L)], 0) print("max logit difference:", (step_logits - ref).abs().max().item())
With PyTorch 2.8 on a CPU this prints the token list [29, 6, 47, 23, 6, 47, 9, 5], then True positions processed: cached 13 naive 76 cache length 13, and a logit difference of about \(2 \times 10^{-7}\) (float32 rounding). The counts match formula (78.2) with \(P = 6\), \(n = 8\): \(6 + 7 = 13\) and \(48 + 28 = 76\). The exact token IDs may differ across PyTorch versions because the random initialization can change; the equality and the counts do not.
The roofline estimate of Algorithm 2 fits in a few lines of plain Python. It reproduces the numbers of the worked examples:
# Roofline estimate of prefill and decode time (a lower bound: peak FLOP/s and peak bandwidth) def step_time(N, L, n_kv, d_head, d_attn, new_tokens, context, batch, flops_peak, bandwidth, bytes_per=2): kv_per_token = 2 * L * n_kv * d_head * bytes_per # K and V, every layer flops = 2 * N * new_tokens * batch # weight matmuls flops += 4 * L * d_attn * new_tokens * (context + new_tokens / 2) * batch # QK^T and AV, causal bytes_ = bytes_per * N + batch * (context + new_tokens) * kv_per_token # read weights once, read/write KV return max(flops / flops_peak, bytes_ / bandwidth), flops / bytes_ llama3_8b = dict(N=8.03e9, L=32, n_kv=8, d_head=128, d_attn=4096) h100 = dict(flops_peak=989e12, bandwidth=3.35e12) t, ai = step_time(**llama3_8b, new_tokens=2000, context=0, batch=1, **h100) print(f"prefill 2000 tokens: {t*1e3:.1f} ms, intensity {ai:.0f} FLOP/byte") # 33.5 ms, 2032 t, ai = step_time(**llama3_8b, new_tokens=1, context=2000, batch=1, **h100) print(f"decode 1 token at context 2000: {t*1e3:.2f} ms, intensity {ai:.2f} FLOP/byte") # 4.87 ms, 1.05 t, ai = step_time(**llama3_8b, new_tokens=1, context=2000, batch=64, **h100) print(f"decode batch 64: {t*1e3:.2f} ms per step, {64/t:.0f} tokens/s in total") # 9.80 ms, 6528
Beyond the basic loop
Real serving systems keep the two phases but schedule them cleverly. A short map of what comes later in this track:
- Continuous batching (Orca, vLLM): new requests join the running decode batch at any step, and finished ones leave, so \(B\) stays large (session 135).
- Chunked prefill (Sarathi): a long prompt is cut into chunks that run together with decode steps, so one long prefill does not freeze everyone else’s token stream.
- Prefill–decode disaggregation (DistServe, Splitwise): run prefill and decode on different GPUs, because one phase wants compute and the other wants bandwidth and memory (session 137).
- Fewer bytes per token: weight quantization (INT8, INT4) cuts the \(bN\) term; GQA, MLA and KV quantization cut \(s_{\text{kv}}\).
- More tokens per weight read: speculative decoding lets a small draft model propose several tokens that the big model checks in one step, which raises \(m\) above 1 even for one user (session 128).
Where this is used
| Setting | Which phase dominates | What people do about it |
|---|---|---|
| Chat assistant, long answers | Decode (TPOT) | Large batches with continuous batching, quantized weights, speculative decoding |
| Summarization, RAG with long retrieved context | Prefill (TTFT), plus a large KV cache | Prefix caching of shared documents, chunked prefill, prompt compression |
| Code completion in an editor | Both, with a strict TTFT budget | Small models, reuse of the cache between keystrokes |
| Agents and multi-turn tools | Repeated prefill of a growing history | Keep the KV cache of the conversation prefix between turns |
| Image question answering (VLM) | Prefill grows with visual tokens: LLaVA-1.5 uses 576 tokens per image [Certain] | Fewer or merged visual tokens |
| Video QA, video captioning, key-moment detection, Video-RAG | Prefill: \(32 \times 576 = 18{,}432\) tokens (32 frames of 576), about 0.39 s of pure compute on an 8B model on one H100 even at peak, and 2.4 GB of cache | Frame sampling, token pooling, caching the video’s KV once and asking many questions |
| Offline batch generation (synthetic data, RL rollouts, evaluation) | Decode throughput | Very large batches; latency per user does not matter |
Common mistakes
- Computing logits for all prompt positions in prefill. With a 128K vocabulary and a long prompt, that is a huge extra matrix and a lot of memory. Only the last position is needed.
- Wrong positions in decode. The new token sits at position \(P + i\), not 0. Forgetting to pass the offset (for RoPE or learned positions) gives garbage after the prompt, while prefill still looks fine.
- Using the causal mask with a single decode query in a hand-written kernel. A causal mask built for a \(1 \times 1\) square lets the new token see only itself. In decode, the one query must see the whole cache. (In the code above,
is_causalis turned off when there is one new token.) - Estimating decode speed from FLOPs. “\(16\ \text{GFLOP per token} / 989\ \text{TFLOP/s} \Rightarrow 60{,}000\) tokens/s” is wrong by a factor of about 300 at batch 1. Use \(\text{bytes} / \beta\).
- Thinking that batching makes each user faster. Batching raises total throughput; each user’s TPOT gets slightly worse.
- Forgetting the KV cache in memory planning. The weights may fit, but 20 GB left on two A100s holds only about 14 sequences of 4,096 tokens for Llama 2 70B.
- Benchmarking with tiny prompts only. Short prompts hide the TTFT problem that real RAG and video inputs create.
Interview questions
What are prefill and decode?basic
Why is prefill compute-bound and decode memory-bound?core
Estimate the decode speed of an 8B model in BF16 on one H100 at batch 1.core
The survey says LLaMA-2-70B needs 140 GB and about 100 ms per token on 2 A100s. Explain both numbers.core
Why does batching help decode throughput but not prefill?core
Does batching make decode compute-bound eventually?advanced
What do TTFT and TPOT measure, and which phase drives each?basic
Without a KV cache, how does the cost of generating n tokens grow?core
Why is the query not cached, only keys and values?basic
A long prompt (32K tokens) freezes other users’ streams in your server. Why, and what can you do?advanced
How do speculative decoding and quantization each attack the decode bottleneck?advanced
Exercises
- Compute the KV cache size per token of Llama 2 70B in FP16 from its config (80 layers, 8 KV heads, head size 128). How much memory does one sequence of 4,096 tokens need?
- What is the best possible batch-1 decode speed (tokens per second) of Llama 3 8B in BF16 on one A100 80 GB (2.039 TB/s)?
- Use formula (78.2) for \(P = 1000\) and \(n = 500\). How many times more token passes does the naive loop do?
- If Llama 2 70B ran on 4 A100s with perfect tensor parallelism, what would the lower bound per token be? Name one reason the real speed-up is smaller than 2 times.
- Using Figure 5, set \(P = 8000\) and \(n = 100\). Which share of the request time is prefill? What happens to that share if \(n = 1000\)?
- For Llama 3 8B on an H100, compute the limit of decode arithmetic intensity for very large batches at \(T = 1024\). Is decode compute-bound there?
Answerscheck
Key takeaways
- Generation follows formula (78.1) one token at a time. The KV cache removes the repeated work: \(P + n - 1\) token passes instead of \(nP + n(n-1)/2\) (78.2).
- Prefill processes all prompt tokens at once with GEMMs, fills the cache (78.3) and costs about \(2NP\) FLOPs plus quadratic attention (78.4). It is compute-bound and sets the time to first token.
- Decode processes one token per sequence, reads all weights and the cache (78.5, 78.6), and has an arithmetic intensity of about \(B\) (78.8, 78.9). At batch 1 it is memory-bound: \(t \ge bN / \beta\) (78.10).
- The survey’s example: LLaMA-2-70B in FP16 is 140 GB; on 2 A100s the bandwidth bound is about 34 ms per token, and the reported time is about 100 ms.
- Batching shares the weight read and raises throughput, but the KV cache is not shared and keeps long-context decode memory-bound. A request takes about \(\text{TTFT} + (n - 1) \cdot \text{TPOT}\) (78.11).
Key formulas
References for this session
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Xiao & Zhu, NLP: Neural Networks and Large Language Models, chapter 11: Inference
- Austin et al., Google DeepMind (2025). How to Scale Your Model
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Xiao & Zhu, NLP: Neural Networks and Large Language Models, chapter 11: Inference
- Austin et al., Google DeepMind (2025). How to Scale Your Model
- Touvron et al. (2023). Llama 2: Open Foundation and Fine-Tuned Chat Models
- Llama Team, Meta (2024). The Llama 3 Herd of Models
- Williams et al. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures
- Ainslie et al. (2023). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
- Agrawal et al. (2023). SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
- Zhong et al. (2024). DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving
- Patel et al. (2023). Splitwise: Efficient Generative LLM Inference Using Phase Splitting
- Leviathan et al. (2022). Fast Inference from Transformers via Speculative Decoding
- Liu et al. (2023). Improved Baselines with Visual Instruction Tuning