Chapter 30 Model Inference: Prefill, Decode, KV Cache, and Quantization

30.1 Why does the first token take a different route?

The travel assistant has a prompt containing the updated 750-yuan limit. Chapter 29 tells us how to choose a token once logits are ready. It does not yet explain how the system obtains those logits, why the first visible token can take longer, or why a longer conversation occupies more memory even when model weights stay unchanged.

Here inference means running a trained model on inputs. Reasoning means solving a problem through steps of an argument. A model can run to produce a greeting, a calculation or a mistaken answer; all three involve inference, and only some involve useful reasoning. We will call the computational process model inference and measure its stages without mistaking elapsed time for evidence of thought.

30.2 Read the known prefix, then consume one new token at a time

Example 30.1 — Eight prompt positions. Suppose the already-tokenized prompt occupies eight positions, including any required special tokens. They are all known at the start. In a causal decoder, the computation at each position can use only that position and earlier ones, but the known input IDs allow the layer’s work across prompt positions to be arranged together. The final prompt position supplies logits for output token 1. This initial processing is prefill.

After choosing token 1, its ID becomes a new input. The next step processes that ID to obtain logits for token 2. Repeat for later output tokens. These steps are decode. Future output IDs are unknown, which creates the sequential dependency; having many processors does not by itself reveal the next ID before selection.

The simplest correct implementation reruns the whole growing prefix at every step. That is what our existing Mini GPT generator does. It is easy to inspect, but it recalculates many old intermediate values. In a deterministic causal model with fixed parameters and the same positional conventions, appending a future token does not change an earlier position’s representation. Its attention could never look forward. We can exploit that fact.

A KV cache retains each layer’s projected keys and values for positions already processed. During a new decode step, compute the new position’s Q, K and V, append its K/V, and compare its Q with the retained K, including its own new K. Use the corresponding V to form its mixture, then continue through later layers. We do not need to recompute old positions merely to obtain their K/V again. Positional transformations such as RoPE must be applied consistently when cached keys are produced and new queries are used.

Table 30.1 — A token is not cached before being consumed

Computation just completed	Input positions whose K/V are stored	Newly selectable output
Prefill of eight prompt positions	8	Token 1
Decode consuming token 1	9	Token 2
Decode consuming token 2	10	Token 3

Emitting token 1 does not instantly create its K/V in every layer. The subsequent forward pass does. This distinction prevents an off-by-one cache count at request completion. A particular server may retain or discard different amounts after stopping; its trace must state which point is measured.

Known prompt

1. Outside the modelArrival 0 → queue until 30 ms
2. An operationPrefill positions 1–8
3. A list of numbersK/V for 8 positions: 512 bytes
4. Text pieces150 ms: emit output 1

TTFT includes queueing: 150−0 = 150 ms.

First decode

1. Text piecesConsume output 1 as new input
2. An operationAppend new K/V; query 9 positions
3. A list of numbers9 positions: 576 bytes
4. Text pieces190 ms: emit output 2

An emitted ID does not already contain its layer-by-layer K/V.

Later outputs

1. Text pieces235 ms: output 3; cache length 10
2. Text pieces270 ms: output 4
3. An operationGaps 40,45,35 → mean 40 ms

Four outputs form three later intervals; one output would have no TPOT.

Figure 30.1 — Output selection precedes consumption of that token. Original book diagram · CC BY-SA 4.0.

Figure 30.1 joins the input and output timeline. The cache contains layer-specific numerical context, not previously written answer strings. It avoids old K/V recomputation, but the new query still interacts with retained context in ordinary full attention. Longer prefixes can therefore increase decode work even with caching.

30.3 Time the request from named boundaries

Example 30.2 — A supplied trace, not a hardware benchmark. Time is measured in milliseconds on one clock. Request arrival is 0, prefill begins at 30, and output tokens are emitted at 150, 190, 235 and 270. Assign no transport delay after these emission events; in a real user-visible trace, transport and buffering need their own timestamps.

The first-token wait is $150-0=150$ ms. This time to first token (TTFT) includes the 30 ms queue wait and the assigned 120 ms prefill-to-first-emission interval. Measuring only $150-30=120$ ms would omit the queue and answer a different question.

The three subsequent gaps are $190-150=40$, $235-190=45$, and $270-235=35$ ms. Their mean is $(40+45+35)/3=40$ ms. Four emitted tokens create three between-token intervals, which explains the denominator. With arrival a, emission times $t_1,\ldots,t_n$ and at least two emitted tokens, define

$$\mathrm{TTFT}=t_1-a,\qquad \mathrm{TPOT}=\frac{t_n-t_1}{n-1}.$$

Time per output token (TPOT) here means the mean interval after the first token. Substituting the trace gives $(270-150)/(4-1)=40$ ms. Some reports use other per-token conventions; a number labeled “latency” without its boundaries is not comparable. The reciprocal, $1000/40=25$ output tokens per second, describes this post-first-token pace, not the entire request’s throughput or a multi-request server rate.

The request ends at 270 ms. Dividing that full time by four gives 67.5 ms, a different average that includes the initial wait. If only one token is emitted, TTFT still exists but there is no between-token interval: TPOT is missing, not zero. A failed request that emits nothing belongs in an error count; dropping it silently can make latency and quality appear better.

30.4 Count the cache in bytes

Example 30.3 — A small cache you can enumerate. Assign two layers, two KV heads per layer, four coordinates per head and two bytes per coordinate. For eight processed positions and one request, the cache occupies

$$2\times1\times2\times8\times2\times4\times2=512\text{ bytes}.$$

Read the factors as K plus V, requests, layers, positions, KV heads, head width, bytes per value. One additional processed position adds $2\times2\times2\times4\times2=64$ bytes. Thus the rows in Table 30.1 require 512, 576 and 640 bytes.

For B requests of the same processed length T, L layers, $H_{\mathrm{kv}}$ KV heads, head width d and b bytes per value, the ideal payload is

$$M_{\mathrm{KV}}=2BLTH_{\mathrm{kv}}db.$$

Every dimension counts a different set of stored values. Query heads do not appear independently; Chapter 26 explained why GQA can have more query heads than KV heads. For unequal lengths, replace BT by the sum of the processed lengths across requests. Allocated blocks, padding, metadata and reserved future capacity can make actual allocation larger.

Now assign L = 24, $H_{\mathrm{kv}}=8$, d = 128, T = 4,096, B = 1 and b = 2. The product is 402,653,184 bytes, or 384 MiB. Two equally long independent requests need an ideal 768 MiB. This does not include weights, logits or workspace. Reducing weight precision alone leaves this cache count unchanged if cache precision remains two bytes.

A cache also has a validity condition. Editing the old 600-yuan prefix into a new 750-yuan prefix changes inputs; retained K/V at and after the changed position generally cannot be reused as though nothing happened. Different weights, adapters, tokenizer IDs, positions or attention rules can also invalidate reuse. A chat application’s stored messages are text records that may later be put into a prompt. They are not automatically the same object as a model’s KV cache. An answer cache stores a previous answer under a reuse rule. The KV cache stores neither permission to cancel an order nor a durable source of current policy truth.

30.5 Store a nearby value with fewer bits

When weights or caches are too large, quantization stores approximations using fewer possible numerical levels. We need to inspect the mapping before discussing a quality tradeoff.

Example 30.4 — Four values and one scale. Assign values $[-1.2,-0.2,0.7,1.8]$. Use four-bit integers from −7 to 7, leaving the extra signed code unused, with scale $s=0.5$ and zero point 0. Divide each value by 0.5, round to the nearest integer, then clip to the allowed range. Exact half-way cases use nearest-even rounding. None of these four inputs is a half-way case.

Table 30.2 — Derived storage values and signed errors

Original x	x / 0.5	Stored q	Reconstructed 0.5q	Reconstructed − original
−1.2	−2.4	−2	−1.0	+0.2
−0.2	−0.4	0	0.0	+0.2
0.7	1.4	1	0.5	−0.2
1.8	3.6	4	2.0	+0.2

For this symmetric mapping,

$$q=\operatorname{clip}(\operatorname{round}(x/s),-7,7),\qquad \hat x=sq.$$

The hat marks an approximation reconstructed from the integer q. The positive scale s says how far neighboring represented values are apart. Inside the unclipped range, nearest rounding has error at most $s/2=0.25$. At an outlier x = 8, the integer would be 16 and clips to 7, reconstructing 3.5. The error is −4.5, far beyond the rounding bound. That bound never covered clipping.

Four four-bit values need two bytes if tightly packed. A shared FP32 scale adds four bytes, making six bytes instead of the original four FP32 values’ sixteen bytes. Thus this tiny block does not achieve an eightfold storage reduction. Larger groups amortize scales, while smaller groups may better accommodate varied ranges but add metadata. General affine schemes also use a zero point, reconstructing a real value from scale times an integer offset. The exact format, grouping and which tensors are quantized must be specified.

30.6 Small errors can change a discrete choice

Assign two logits in candidate order Paris, Lyon: $[0.6,0.7]$. Greedy originally selects Lyon. Quantizing with scale 0.5 maps both to 0.5, creating a tie that selects Paris under Chapter 29’s order. The absolute error is small, yet the chosen token changes. A changed token then changes later inputs.

This is why “four bits” is not a quality result. Weight-only quantization, activation quantization and KV quantization affect different arrays. Dequantization, packing and specialized integer kernels also affect actual speed; fewer stored bits do not automatically mean every operation runs faster. Calibration data used to choose scales must be separated from final evaluation, and compare the same prompts, task criteria and output budgets. Outliers and near-tied decisions deserve explicit failure cases.

The scalar exercise reproduces all byte and timestamp calculations and the quantization mapping. It does not claim a quantized MG-2 checkpoint or GPU performance measurement. The actual MG-2 runs in Chapters 29 and 33 use the unchanged float64 full-prefix implementation. The supplied prefill/decode trace is a separate teaching scenario, so its 150 ms TTFT cannot be cited as Mini GPT’s measured latency.

A single request now has a lifecycle, a growing state and a numerical representation. Serving many requests introduces another layer: scheduling can reuse context and overlap work while making one user’s wait worse. The next chapter keeps those effects visible.

30.7 Summary

Prefill processes known prompt positions and supplies the first next-token logits; decode consumes chosen tokens sequentially. KV caching reuses layer-specific keys and values under matching computation conditions. TTFT and TPOT need explicit timestamps and denominators. Quantization trades representation size for bounded rounding error only within its unclipped range, and task quality must still be measured.

30.8 Exercises

1. A request arrives at 10 ms and emits tokens at 110, 160 and 220 ms. Calculate TTFT, both gaps, TPOT and complete-request duration.
2. How many cached positions exist immediately after prefill selects the first output for a ten-position prompt? How many after the next forward pass consumes that output?
3. Example 30.3’s larger cache uses four KV heads and four equally long requests. Keep other dimensions fixed. Compute ideal total cache bytes and MiB.
4. Quantize 0.75 and −0.75 using scale 0.5 and the stated tie rule. Then quantize 5. Explain why the last error has a different cause.
5. A report divides total request time by output count and labels the result “TPOT after the first token.” Explain how to correct it, including the one-token case.
6. An engine switches weights to four bits but keeps KV at two bytes. Which resource estimate changes? Why must the same changed-policy examples be rerun?

30.9 Reference answers

1. TTFT is $110-10=100$ ms; gaps are 50 and 60 ms; TPOT is $110/2=55$ ms; full duration is $220-10=210$ ms. The initial wait is excluded only from TPOT.
2. Ten positions after prefill, eleven after consuming the new token. Selection itself is not a forward pass through all layers for that new token.
3. Halving KV heads halves the per-request 384 MiB, then four requests multiply it by four: 768 MiB, or 805,306,368 bytes. Query-head count is not an extra factor.
4. The scaled values are 1.5 and −1.5; nearest-even rounding gives 2 and −2, reconstructing 1 and −1. For 5, the scaled value 10 clips to 7 and reconstructs 3.5. Its −1.5 error comes from exceeding the supported range, not just rounding between adjacent levels.
5. Subtract the first emission time from the last and divide by one fewer than the number emitted. For one token, report TPOT as missing. Preserve full-duration averages separately with their own labels.
6. Ideal weight payload changes, with scale/packing overhead added. The stated KV payload does not. Approximate weights can change logits and selected tokens, so correct use of the 750-yuan update must be re-evaluated rather than inferred from the original precision’s result.

30.10 References

• Shazeer, Fast Transformer Decoding: One Write-Head is All You Need, 2019. The incremental attention implementation makes stored K/V and head-sharing costs explicit.
• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, 2023. Section 4.1 distinguishes logical KV content from physical block allocation.
• Jacob et al., Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference, 2018. Section 2.1 defines scale/zero-point mappings; its mobile-network measurements are not LLM results for this book.