LLM & VLM courseBlog
78Track 5: LLM inference and serving · session 1 of 65

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.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: BeginnerBefore this: Sessions 6, 25, 26 and 42 (next-token prediction, counting FLOPs and memory, the KV cache idea, GPU architecture)

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:

\[ p(x_1, \dots, x_T) = \prod_{t=1}^{T} p_\theta\!\left(x_t \mid x_1, \dots, x_{t-1}\right) \tag{78.1} \]
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.

processed in this stepcached key \(k\)cached value \(v\)attention weight \(\alpha\)
  1. input: prompt \(x_1, \dots, x_P\), max new tokens \(n\)
  2. \(\text{cache} \leftarrow \text{empty}\)
  3. \(\text{logits} \leftarrow \text{model}(x_{1..P}, \text{cache})\) // PREFILL
  4. \(\text{out} \leftarrow [\,]\)
  5. repeat \(n\) times:
  6. \(y \leftarrow \argmax(\text{logits})\); append \(y\) to out
  7. if out has \(n\) tokens: stop
  8. \(\text{logits} \leftarrow \text{model}(y, \text{cache})\) // DECODE
  9. return out
Figure 1. The generation loop of Algorithm 1, computed live on a tiny random transformer (\(d = d_h = 4\), one layer, one head, 10 words, prompt “the cat sat on the”, greedy choice). Each column is one position. Top row: the tokens. Second row: positions that go through the model in this step. Middle: the KV cache, the 4 numbers of each key (orange) and value (green). Bottom: the attention weights \(\alpha_j\) of the newest query, formula (78.5). The right panel puts the live numbers into the formulas. The weights are random (the seed was chosen so the five greedy words read like a sentence); the computation is real.
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:

\[ W_{\text{naive}} = \sum_{i=0}^{n-1} (P + i) = nP + \frac{n(n-1)}{2}, \qquad W_{\text{cached}} = P + (n - 1) \tag{78.2} \]
Worked example: how much the cache saves

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:

\[ K^{(\ell)} = X^{(\ell)} W_K^{(\ell)}, \qquad V^{(\ell)} = X^{(\ell)} W_V^{(\ell)}, \qquad K^{(\ell)}, V^{(\ell)} \in \R^{P \times n_{kv} d_h} \tag{78.3} \]
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:

\[ F_{\text{prefill}} \approx 2 N P \; + \; 2\, L\, d_{\text{attn}}\, P^2 \tag{78.4} \]
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.

Worked example: prefill of a 2,000-token prompt on Llama 3 8B

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:

\[ \mathbf{o}_t = \softmax\!\left( \frac{\mathbf{q}_t\, [K_{\text{cache}}; \mathbf{k}_t]^\top}{\sqrt{d_h}} \right) [V_{\text{cache}}; \mathbf{v}_t] \tag{78.5} \]
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

\[ s_{\text{kv}} = 2 \cdot L \cdot n_{kv} \cdot d_h \cdot b \quad \text{bytes per token} \tag{78.6} \]

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.

memory lane: copy a tile from HBMcompute lane: use the tile
  1. for each tile \(W_t\) of \(W\) (16 tiles of \(1024 \times 1024\)):
  2. copy \(W_t\) and its share of \(X, Y\) // \(\text{bytes}/\beta\)
  3. \(Y \mathrel{+}= X W_t\) for all \(m\) rows // \(\text{FLOPs}/\pi\)
  4. time \(\approx \max(\text{bytes}/\beta,\ \text{FLOPs}/\pi)\) // (78.7)
Figure 2. The same \(4096 \times 4096\) BF16 weight matrix \(W\) (33.5 MB) in the two phases, simulated on an H100 SXM (989 TFLOP/s, 3.35 TB/s). Left: prefill, \(m = P\) rows share every tile. Right: decode at batch 1, \(m = 1\). Each lane shows when the memory system and the arithmetic units are busy; the tile grid shows tiles being copied or waiting (orange), in use (blue) and finished (green). The bytes include \(X\) and \(Y\), as in formula (78.8). Each side has its own time axis. In the code box, a purple bar marks the line the prefill side is running, a teal bar the decode side. This is an idealized model of one kernel; real kernels add overheads.
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:

\[ I = \frac{\text{FLOPs}}{\text{bytes moved}}, \qquad t \;\ge\; \max\!\left( \frac{\text{FLOPs}}{\pi}, \ \frac{\text{bytes}}{\beta} \right) \tag{78.7} \]
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\):

\[ I(m) = \frac{2 m d^2}{2\,(d^2 + 2 m d)} \;\approx\; m \quad \text{when } m \ll d \tag{78.8} \]

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.

Figure 3. The roofline of one GPU for a single \(4096 \times 4096\) BF16 linear layer. The slanted line is the memory limit \(I \cdot \beta\); the flat line is the compute limit \(\pi\). The dot shows your choice of \(m\); the gray marks show decode at batch 1 and a 2,000-token prefill. Both axes are logarithmic.
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:

\[ F_{\text{decode}} \approx 2 N B + 4\, L\, d_{\text{attn}}\, T B, \qquad \text{bytes}_{\text{decode}} \approx b N + B\, T\, s_{\text{kv}} \tag{78.9} \]
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:

\[ t_{\text{token}} \;\ge\; \frac{b\, N}{\beta_{\text{total}}} \tag{78.10} \]

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).

Worked example: the survey’s LLaMA-2-70B numbers

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.

weights read per stepKV cache read per steptotal tokens/stokens/s for one user
Figure 4. A roofline estimate of one decode step, using formulas (78.7) and (78.9) with datasheet peaks (BF16/FP16 weights and cache). Left: the bytes read in one step. Right: tokens per second against batch size for the chosen context; the dot is your batch size. These are best-case numbers; real systems are slower.
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:

\[ T_{\text{request}} \;\approx\; \text{TTFT} + (n - 1) \cdot \text{TPOT} \tag{78.11} \]
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.

prefill (TTFT) / compute timedecode steps / memory timeKV cache
  1. \(\text{clock} \leftarrow 0\); \(\text{cache} \leftarrow 0\) tokens
  2. 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)\)
  3. \(F \leftarrow 2NmB\) \(+\ 4 L d_{\text{attn}}\, m\,(T + m/2)\, B\)
  4. \(\text{bytes} \leftarrow bN + B\,(T + m)\, s_{\text{kv}}\)
  5. \(I \leftarrow F / \text{bytes}\); \(t \leftarrow \max(F/\pi,\ \text{bytes}/\beta)\)
  6. \(\text{clock} \leftarrow \text{clock} + t\); \(\text{cache} \leftarrow T + m\) tokens; emit 1 token per sequence
Figure 5. One request on Llama 3 8B, one H100, BF16, simulated step by step with the best-case roofline times of formulas (78.4), (78.7) and (78.9). Top: the compute time and the memory time of the current step; the longer one (solid) is the step time. Middle: the KV cache of all \(B\) sequences, against the 63.9 GB left next to the weights. Bottom: the timeline, one block per step. The first three steps are shown line by line; after that the animation jumps several steps per frame.
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

Algorithm 1: generation with prefill and decode
  1. input: prompt tokens \(x_1, \dots, x_P\), maximum new tokens \(n\), a rule to choose a token from logits
  2. cache \(\leftarrow\) empty, one (K, V) store per layer
  3. logits \(\leftarrow\) model(\(x_{1..P}\), cache, positions \(1..P\)) // PREFILL: causal mask, writes \(P\) entries, returns logits of the last position only
  4. out \(\leftarrow\) [ ]
  5. repeat \(n\) times:
  6.   \(y \leftarrow\) choose(logits); append \(y\) to out // greedy, sampling, ...
  7.   if \(y\) is end-of-sequence or out has \(n\) tokens: stop
  8.   logits \(\leftarrow\) model(\(y\), cache, position \(P + |\text{out}|\)) // DECODE: one token, reads all weights and the cache, appends 1 entry per layer
  9. return out
Algorithm 2: roofline estimate of one step
  1. 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\)
  2. FLOPs \(\leftarrow 2NmB + 4 L d_{\text{attn}}\, m\,(T + m/2)\, B\) // weights + causal attention; prefill: \(m = P,\ T = 0\); decode: \(m = 1\)
  3. bytes \(\leftarrow bN + B\,(T + m)\, s_{\text{kv}}\) // weights read once; cache read and written
  4. \(I \leftarrow\) FLOPs / bytes // compare with the ridge point \(\pi / \beta\)
  5. 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

SettingWhich phase dominatesWhat people do about it
Chat assistant, long answersDecode (TPOT)Large batches with continuous batching, quantized weights, speculative decoding
Summarization, RAG with long retrieved contextPrefill (TTFT), plus a large KV cachePrefix caching of shared documents, chunked prefill, prompt compression
Code completion in an editorBoth, with a strict TTFT budgetSmall models, reuse of the cache between keystrokes
Agents and multi-turn toolsRepeated prefill of a growing historyKeep 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-RAGPrefill: \(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 cacheFrame sampling, token pooling, caching the video’s KV once and asking many questions
Offline batch generation (synthetic data, RL rollouts, evaluation)Decode throughputVery 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_causal is 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
Prefill is the first forward pass over the whole prompt: all prompt tokens are processed in parallel with a causal mask, their keys and values are stored in the KV cache, and the logits of the last position give the first output token. Decode is every step after that: one new token per sequence goes through the model, attends to the cached keys and values, appends its own key and value, and produces the next logits.
Why is prefill compute-bound and decode memory-bound?core
In prefill, the \(P\) prompt tokens share each weight read, so each linear layer is a GEMM with about \(P\) FLOPs per byte, far above the GPU ridge point (about 295 on H100, 153 on A100). In decode at batch 1, each weight is read to do one multiply-add for one token, about 1 FLOP per byte, so the GPU waits for memory almost all the time. The time of a decode step is about \((\text{weight bytes} + \text{cache bytes}) / \beta\).
Estimate the decode speed of an 8B model in BF16 on one H100 at batch 1.core
Weights: about \(8.03 \times 10^9 \times 2 = 16.06\) GB. Bandwidth: 3.35 TB/s. Lower bound per token: \(16.06 / 3350 \approx 4.8\) ms, so at most about 209 tokens per second. Real systems reach a good fraction of this but not all of it. On an A100 (2.039 TB/s), the bound is 7.9 ms, about 127 tokens per second.
The survey says LLaMA-2-70B needs 140 GB and about 100 ms per token on 2 A100s. Explain both numbers.core
140 GB = \(70 \times 10^9\) parameters \(\times\) 2 bytes in FP16, so it needs two 80 GB GPUs. Two A100s read about 4.08 TB/s together, so the lower bound is \(140 / 4.078 \approx 34\) ms per token. The reported 100 ms is about 3 times that: tensor-parallel communication between the GPUs at every layer, kernel launch overhead, attention over the cache and imperfect bandwidth use add up. The arithmetic itself (\(1.4 \times 10^{11}\) FLOPs) would take only about 0.2 ms.
Why does batching help decode throughput but not prefill?core
Decode at small batch is memory-bound: the weight read costs the same for 1 or 64 sequences, so adding sequences raises FLOPs per byte and total tokens per second almost for free, until the KV-cache reads or the compute limit take over. Prefill is already compute-bound because its own \(P\) tokens share the weight read; adding more prompts adds proportional compute time, so throughput per GPU barely changes.
Does batching make decode compute-bound eventually?advanced
Only at short contexts. The KV-cache bytes grow as \(B T s_{\text{kv}}\) and are not shared, so for large \(B\) the intensity tends to \((2N + 4 L d_{\text{attn}} T)/(T s_{\text{kv}})\). For Llama 3 8B that is about 124 FLOPs/byte at \(T = 1024\) and 34 at \(T = 4096\), both below the H100 ridge of 295. So long-context decode stays memory-bound; reducing \(s_{\text{kv}}\) (GQA, MLA, KV quantization) is what helps. Memory capacity usually limits \(B\) before that.
What do TTFT and TPOT measure, and which phase drives each?basic
TTFT (time to first token) is the wait before the first output token: queueing plus prefill, so it grows with prompt length. TPOT (time per output token) is the average decode step time, driven by weight and cache bytes divided by bandwidth, and by the batch the request shares. A request takes about \(\text{TTFT} + (n - 1) \cdot \text{TPOT}\).
Without a KV cache, how does the cost of generating n tokens grow?core
Each step re-processes the full sequence, so the number of token passes is \(nP + n(n-1)/2\): quadratic in \(n\) for the weight work, and the attention work grows even faster (cubic in total). With the cache it is \(P + n - 1\) token passes, linear. For \(P = 1000\), \(n = 500\) that is 624,750 versus 1,499. The price is the cache memory, which grows linearly with sequence length and batch.
Why is the query not cached, only keys and values?basic
With causal attention, old positions never attend to new tokens, so their outputs never change. A query is used only to compute its own position’s output, which happens once. Keys and values of old positions are needed by every future query, so they are kept.
A long prompt (32K tokens) freezes other users’ streams in your server. Why, and what can you do?advanced
The prefill of 32K tokens is one long compute-bound step; if the scheduler runs it as a single iteration, all running decode sequences wait until it finishes, so their TPOT spikes. Fixes: chunked prefill (Sarathi), which splits the prompt into chunks mixed with decode steps; separating prefill and decode onto different GPUs (DistServe, Splitwise); prefix caching if the long prompt is shared; and limits on tokens per scheduler step.
How do speculative decoding and quantization each attack the decode bottleneck?advanced
Decode time \(\approx\) bytes read \(/\ \beta\) per useful token. Quantization reduces the bytes: INT4 weights are a quarter of FP16, so the bound per token drops about 4 times (ignoring dequantization overhead and the cache). Speculative decoding increases useful tokens per weight read: the big model verifies several drafted tokens in one pass (a small prefill-like step with \(m \gt 1\)), so when drafts are accepted it produces more than one token per read of its weights.

Exercises

  1. 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?
  2. 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)?
  3. Use formula (78.2) for \(P = 1000\) and \(n = 500\). How many times more token passes does the naive loop do?
  4. 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.
  5. 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\)?
  6. 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
1. \(s_{\text{kv}} = 2 \times 80 \times 8 \times 128 \times 2 = 327{,}680\) bytes (320 KiB). For 4,096 tokens: \(327{,}680 \times 4096 = 1.34\) GB. 2. \(16.06 \text{ GB} / 2.039 \text{ TB/s} = 7.88\) ms, so at most about 127 tokens/s. 3. Naive 624,750, cached 1,499: about 417 times more. 4. \(140 / (4 \times 2.039) = 17.2\) ms. The communication between GPUs grows with more GPUs and does not shrink, and each GPU’s matrices become smaller, so kernels use bandwidth less well. 5. TTFT is about 147 ms of about 0.65 s, so 22.5%. With \(n = 1000\) the decode part grows ten times and the prefill share falls to about 3%. 6. \((2N + 4 L d_{\text{attn}} T)/(T s_{\text{kv}}) = (1.606 \times 10^{10} + 5.37 \times 10^{8})/(1024 \times 131{,}072) \approx 124\) FLOPs/byte, below the ridge of 295: still memory-bound.

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

\[ t \ge \max\!\left(\frac{\text{FLOPs}}{\pi}, \frac{\text{bytes}}{\beta}\right), \quad F_{\text{prefill}} \approx 2NP + 2Ld_{\text{attn}}P^2, \quad \text{bytes}_{\text{decode}} \approx bN + BTs_{\text{kv}}, \quad s_{\text{kv}} = 2Ln_{kv}d_hb \]

References for this session

  1. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  2. Xiao & Zhu, NLP: Neural Networks and Large Language Models, chapter 11: Inference
  3. Austin et al., Google DeepMind (2025). How to Scale Your Model
  4. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  5. Xiao & Zhu, NLP: Neural Networks and Large Language Models, chapter 11: Inference
  6. Austin et al., Google DeepMind (2025). How to Scale Your Model
  7. Touvron et al. (2023). Llama 2: Open Foundation and Fine-Tuned Chat Models
  8. Llama Team, Meta (2024). The Llama 3 Herd of Models
  9. Williams et al. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures
  10. Ainslie et al. (2023). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints
  11. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  12. Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
  13. Agrawal et al. (2023). SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
  14. Zhong et al. (2024). DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving
  15. Patel et al. (2023). Splitwise: Efficient Generative LLM Inference Using Phase Splitting
  16. Leviathan et al. (2022). Fast Inference from Transformers via Speculative Decoding
  17. Liu et al. (2023). Improved Baselines with Visual Instruction Tuning