Module 3 · Inference engineering · Chapter 23 · Free
How an LLM generates text: prefill, decode and the KV cache
One token at a time
A language model does not write a reply in one go. It works on tokens, which are chunks of text a little shorter than a word (Chapter 7). Given all the tokens so far, it produces a score for every possible next token, one token is picked from those scores, and that token is added to the end. Then the whole thing repeats with the longer sequence. A 300-token answer means 300 trips through the model.
This loop is called autoregressive generation: each output depends on everything before it, including the model's own earlier output. That one fact explains most of the performance behaviour in this module.
- Text is split into token ids. On the first pass these are all the prompt tokens. On later passes the newest token is added.
- Each id is looked up in a table and becomes a list of numbers (a vector) that the layers can compute with.
- Dozens of identical-shaped layers run in sequence. Each has an attention step, where a token looks at earlier tokens, and a feed-forward step that transforms each token on its own.
- To look back at earlier tokens, a layer needs two saved summaries of each one, called its key and value. Instead of recomputing them every step, they are stored in the KV cache and only the new token's pair is added.
- The last layer gives a score for every token in the vocabulary. A sampling rule (greedy, or random with a temperature) picks one.
- The new token is sent to the user and also appended to the input. The loop runs again until a stop token or a length limit.
Why a cache exists
In attention, every token compares itself with all earlier tokens to decide what to pay attention to. For that comparison each earlier token provides a key (used to decide how relevant it is) and a value (the content it contributes). These depend only on the tokens before them, and earlier tokens never change. So there is no reason to recompute them for every new token.
The KV cache is simply that saved set of keys and values, for every layer and every token seen so far. Each decode step computes a new key and value for one token, appends them, and reuses everything else. Without the cache, a 2,000-token reply would redo the work for the entire history 2,000 times. With it, each step does a small amount of new work, but must read the whole cache. Remember that last part. It matters in Chapter 24.
Prefill and decode
Generation has two distinct phases with very different behaviour.
- Prefill processes the whole prompt. All prompt tokens are known up front, so the GPU handles them together, in parallel, and fills the cache for all of them in one pass. It is heavy on arithmetic. It ends when the first output token is chosen.
- Decode then produces output one token per step. Each step depends on the token chosen in the previous step, so steps cannot run side by side. Each step does little arithmetic but reads the model weights and the whole cache.
Try it below. Step through a short example, then drag the slider to pretend the prompt is much longer and see which times change.
Generation animation (all times illustrative)
The eight boxes below stand in for the prompt. The slider changes only the timing model, not the boxes.
Prompt tokens, then generated tokens
KV cache (one block per token held)
Time per step (illustrative milliseconds)
Why long prompts delay the first word, and long answers take long
Time to first token (TTFT) is roughly the queue wait plus the prefill. A long prompt means more tokens to process in the prefill pass, so the user stares at a blank screen for longer. Parallelism helps the GPU, but it does not make the work free: ten times the prompt is still about ten times the computation.
After that, total time is roughly the number of output tokens times the time for one decode step. Each step is bounded by how fast the GPU can read its memory, and steps cannot overlap within one request. A 1,000-token answer needs 1,000 sequential steps. This is why streaming helps perceived speed (Chapter 17) but does not shorten the total, and why asking for "a brief answer" is a real performance lever.
The cache grows, and it eats memory
Each token adds a fixed amount of cache for every layer. For a decoder with grouped-query attention (a design where several attention heads share one set of keys and values), the size per token is:
2 (keys and values) x layers x KV heads x head dimension x bytes per number
With an illustrative model of 32 layers, 8 KV heads, a head dimension of 128 and 2-byte numbers, that is 2 x 32 x 8 x 128 x 2 = 131,072 bytes, or 128 KiB per token. An 8,000-token conversation then holds about 1 GiB of cache. Serve 32 such conversations at once and the cache alone is about 32 GiB, on top of the model weights. The cache grows with sequence length and with the number of simultaneous requests (batch size). That is usually what runs a server out of memory before it runs out of compute. Chapter 25 turns this into a calculator.
Mixture of experts, briefly
Some models replace each feed-forward block with many smaller ones called experts, plus a small router that picks a few experts for each token. Only the chosen experts do work for that token, so the compute per token can be much lower than the total parameter count suggests. The catch, which people often miss, is that different tokens pick different experts, so in general all the experts' weights must still be available in memory. The model is cheaper to compute but not proportionally smaller to hold. Attention and the KV cache work the same way as in a dense model.
Check your understanding
Recap
- Text is generated one token per step, and each step depends on the one before. That makes decode sequential.
- Prefill handles the prompt in parallel and fills the KV cache. Decode adds one token per step and reads the cache every time.
- The KV cache stores keys and values per layer per token. It grows with sequence length and batch size and competes with the weights for GPU memory.
- Long prompts hurt time to first token. Long outputs hurt total time. They are different problems with different fixes.
- Mixture of experts cuts compute per token, not the memory needed to hold all the weights.
Chapter quiz
Four questions. Score 70% or more to mark this chapter complete.