The previous post rewrote Qwen2.5-0.5B in 70 lines of PyTorch and left two puzzles:
- Our generation loop took 55.7 seconds for 300 tokens, while
transformerstook only 8.9. - Passing one token through the model takes 28 ms, but passing 500 tokens at once takes only 380 ms, or 0.76 ms per token. The amount of computation per token is the same.
The first puzzle has a neat answer: the KV cache. The second goes deeper, and its answer explains almost everything about LLM speed: why the first token is slow, why APIs charge more for output tokens than input tokens, why models are compressed down to 8 or 4 bits, and why a server serving many people at once costs barely more.
The route: the two phases of an answer, adding a KV cache to the hand-written model, measuring what decode is really limited by, a decisive experiment with 16-bit numbers, how much memory the KV cache takes, what happens with long prompts, then the practical consequences.
Every number in this post was measured on a real machine, with Python 3.12, PyTorch 2.14 and transformers 5.20, on the CPU. The code is the version written in the previous post, plus a few lines.
The two phases of an answer
When you send a question, the model does two very different jobs:
- Prefill: read the whole prompt. Every prompt token is already known, so they go through the model in one pass, as a matrix with many rows. Prefill ends with the first token of the answer.
- Decode: generate the remaining tokens. Token n needs to know what token n − 1 is, so this can't be done in parallel: one token per step.
These two phases give the two numbers every LLM service tracks: time to first token (TTFT), set by prefill, and tokens per second while the text is flowing, set by decode. The chatbot in the Python series had its first token after 0.7 seconds, then text flowed steadily at about 17 tokens per second: those 0.7 seconds were prefill.
The KV cache: don't recompute what you've computed
The previous post's loop sent the whole sequence through the model at every step. But look at attention again: at each layer, each token produces a key and a value, and they depend only on that token and the tokens before it. When token 301 is added, the keys and values of the 300 earlier tokens don't change at all. Recomputing them is pure waste.
The KV cache keeps the keys and values of every past token, at every layer. Each decode step only needs to send one new token through the model; that token makes its own q, k and v, appends k and v to the cache, then looks at the whole cache. Changing the previous post's attention function:
def attention(x, i, positions, cache):
p = f"layers.{i}.self_attn."
seq = x.shape[0]
q = (x @ W[p + "q_proj.weight"].T + W[p + "q_proj.bias"]).view(seq, H, HD).transpose(0, 1)
k = (x @ W[p + "k_proj.weight"].T + W[p + "k_proj.bias"]).view(seq, KV, HD).transpose(0, 1)
v = (x @ W[p + "v_proj.weight"].T + W[p + "v_proj.bias"]).view(seq, KV, HD).transpose(0, 1)
q, k = rope(q, positions), rope(k, positions)
if i in cache: # keys and values of every earlier token, computed once
k = torch.cat([cache[i][0], k], dim=1)
v = torch.cat([cache[i][1], v], dim=1)
cache[i] = (k, v)
k, v = k.repeat_interleave(H // KV, dim=0), v.repeat_interleave(H // KV, dim=0)
scores = q @ k.transpose(-1, -2) / HD**0.5 # (14, new, all): the new tokens look at everything so far
total = k.shape[1]
causal = torch.ones(seq, total, dtype=torch.bool).triu(total - seq + 1)
weights = scores.masked_fill(causal, float("-inf")).softmax(-1)
return (weights @ v).transpose(0, 1).reshape(seq, D) @ W[p + "o_proj.weight"].T
def forward(ids, cache):
"""Only the new tokens go in; the cache holds what the model already knows about the earlier ones."""
start = cache[0][0].shape[1] if 0 in cache else 0
positions = torch.arange(start, start + len(ids))
x = W["embed_tokens.weight"][ids]
for i in range(LAYERS):
x = x + attention(rms_norm(x, W[f"layers.{i}.input_layernorm.weight"]), i, positions, cache)
x = x + mlp(rms_norm(x, W[f"layers.{i}.post_attention_layernorm.weight"]), i)
return rms_norm(x, W["norm.weight"]) @ W["embed_tokens.weight"].T
Three changes from the old version: k and v are appended to the cache, the starting position (start) comes from the cache length so RoPE rotates by the right angle, and the causal mask is now a rectangle (new tokens can see every old token, plus the new tokens before them). The generation loop becomes:
cache = {}
next_id = int(forward(prompt_ids, cache)[-1].argmax()) # prefill: the whole prompt at once
for _ in range(299):
next_id = int(forward([next_id], cache)[-1].argmax()) # decode: one token at a time
The same question as in the previous post, 300 tokens:
| After token 1 | 100 | 200 | 300 | |
|---|---|---|---|---|
| No cache | 0.14 s | 11.8 s | 30.4 s | 55.7 s |
| With cache | 0.08 s | 3.0 s | 6.0 s | 9.0 s |
transformers generate() |
8.9 s |
The 300 tokens generated are identical, token for token, to the version without a cache, and the time now grows in a straight line, about 30 ms per token, level with transformers. The first puzzle is solved. But that 30 ms is the real puzzle.
What limits decode
One decode step sends one token through the model. Count what it has to do:
- Compute: each parameter takes part in exactly one multiplication and one addition, so about 2 × 494 million ≈ 1 billion operations.
- Read memory: every parameter has to be read from RAM at least once. 494 million 32-bit floats is 1.98 GB.
Measured on the same machine, in two modes:
| Time | Operations per second | Weight bytes read per second | |
|---|---|---|---|
| Decode: 1 token | 27.6 ms | 36 billion | 72 GB/s |
| Prefill: 1,000 tokens at once | 634 ms | 1,600 billion | 3 GB/s |
To know whether 72 GB/s is a lot, measure the simplest possible thing: sum a 2 GB array (x.sum()). That does almost no computing, just reading. The result: 83 GB/s. That's this machine's raw RAM read speed.
So it's clear: when decoding, the model reads weights at 72 GB/s, 87% of the maximum RAM read speed, while its computation uses less than 1/40 of the computing power the same machine reaches during prefill. Decode isn't limited by computing power; it's limited by how fast weights can be pulled from memory into the processor. The processor spends most of its time waiting for data.
Prefill is the opposite. The weights are read once but used for 1,000 tokens, so every byte read in serves thousands of operations. There, the limit is computing power. The usual number for telling the two modes apart is operations per byte read: decode in 32-bit floats does about 2 operations per 4 bytes, so 0.5; prefill with 1,000 tokens does about 500. Every piece of hardware has a threshold somewhere in between: below it, you wait for memory; above it, you wait for the processor.
This is the answer to the second puzzle. The 28 ms for one token isn't computing time; it's the time to read 2 GB. Read 2 GB once and use it for 500 tokens, and each token only bears 1/500 of that cost.
The decisive experiment: 16-bit numbers
If the "decode waits for memory" hypothesis is right, halving the number of bytes in the weights should make decode almost twice as fast, even though the amount of computation doesn't change. And if "prefill waits for compute" is right, prefill should gain nothing. Running the same model with three number types:
| Number type | Weights | 1 token (decode) | 500 tokens (prefill) |
|---|---|---|---|
| float32 | 1.98 GB | 27.3 ms | 341 ms |
| bfloat16 | 0.99 GB | 16.5 ms | 3,711 ms |
| float16 | 0.99 GB | 16.3 ms | 2,501 ms |
Both predictions hold, more clearly than expected:
- Decode gets 1.7 times faster just because the weights are half the size. No computation was skipped; there are simply fewer bytes to pull through.
- Prefill gets 7–11 times slower. On this CPU, 16-bit matrix multiplication is much slower than 32-bit, and since prefill is limited by compute, it takes the full hit. Decode does the same slow 16-bit multiplications, but because it spends most of its time waiting for memory, the slowness is mostly hidden (the weight read speed only drops from 72 to 60 GB/s).
The same change, two opposite results, because the two phases are limited by two different things. GPUs have dedicated hardware for 16-bit multiplication, so prefill doesn't slow down like this there, but the logic is exactly the same. This is why models are quantized to 8 or 4 bits for serving: for decode, every bit removed is speed gained. The post on serving many users will measure that.
Decode slows down with length
With a cache, decode steps still aren't all equal. One decode step after prompts of different lengths:
| Context (tokens) | One decode step |
|---|---|
| 10 | 27.6 ms |
| 100 | 29.0 ms |
| 1,000 | 33.9 ms |
| 4,000 | 51.0 ms |
| 8,000 | 72.1 ms |
Besides the 1.98 GB of weights, every step also has to read the whole KV cache: the new token looks at the keys and values of every token before it. The longer the context, the bigger the cache, and at 8,000 tokens a decode step is almost three times slower. With large models and very long contexts, reading the KV cache can cost as much as reading the weights, or more.
How much memory the KV cache takes
Each token, at each layer, keeps one key and one value for each key/value head:
bytes per token = layers × 2 (k and v) × KV heads × head size × bytes per number
Computed from the config files of three Qwen2.5 models, in bfloat16:
| Model | Layers | Query / KV heads | KV cache per token | Without grouped-query | 32,768 tokens |
|---|---|---|---|---|---|
| 0.5B | 24 | 14 / 2 | 12 KiB | 84 KiB | 0.38 GiB |
| 7B | 28 | 28 / 4 | 56 KiB | 392 KiB | 1.75 GiB |
| 72B | 80 | 64 / 8 | 320 KiB | 2,560 KiB | 10 GiB |
A 32,000-token conversation with the 72B model holds 10 GiB of cache, for one user. Without grouped-query attention (previous post), that would be 80 GiB, 8 times as much. This is the real reason 14 query heads share just 2 key/value heads: not to compute faster, but to make the cache small enough to fit in memory and quicker to read at every decode step.
Long prompts: the attention matrix explodes
Prefill has a problem of its own. Measuring prefill time by prompt length, with the hand-written attention:
| Prompt | Prefill | Per token | scores matrix per layer |
|---|---|---|---|
| 1,000 | 843 ms | 0.84 ms | 0.06 GB |
| 4,000 | 7,656 ms | 1.91 ms | 0.90 GB |
| 8,000 | 87,942 ms | 10.99 ms | 3.58 GB |
From 4,000 to 8,000 tokens, the time doesn't double; it goes up 11 times. The culprit is the line scores = q @ k.transpose(-1, -2): it builds a 14 × seq × seq matrix, and at 8,000 tokens that matrix is 3.58 GB, plus a mask and a softmax result of the same size, at every layer. The machine has to juggle tens of GB of temporary data just to multiply it by v and throw it away.
Replace just that part with PyTorch's built-in function:
out = torch.nn.functional.scaled_dot_product_attention(q, k, v, is_causal=True, enable_gqa=True)
| Prompt | Hand-written attention | scaled_dot_product_attention |
|---|---|---|
| 1,000 | 843 ms | 634 ms |
| 4,000 | 7,656 ms | 3,162 ms |
| 8,000 | 87,942 ms | 8,709 ms |
The results are the same (largest logit difference 0.0001), but at 8,000 tokens it's 10 times faster. This function never builds the whole matrix: it splits q, k and v into small blocks, computes the softmax piece by piece, and accumulates the result. This is the idea behind FlashAttention: the computation is unchanged, but the temporary data always fits in fast memory. The same lesson again: what's expensive is moving data, not computing.
Attention's computation still grows with the square of the length, so going from 4,000 to 8,000 tokens is still more than twice as slow. That's why long prompts are still expensive, and why the first token of a question with a 100-page document attached arrives much later than for a bare question.
Practical consequences
Output tokens cost more than input tokens. Most APIs charge several times more for output tokens than for input tokens. Now we know why: input tokens go through prefill, together, each read of the weights shared across thousands of tokens; output tokens go through decode, one full read of the model per token.
Prompt caching. Many APIs offer "prompt caching": if many requests start with the same text (a long system instruction, reference documents), that part is charged less and the first token arrives sooner. That's exactly the KV cache above, just kept between requests: once the keys and values of the opening text are computed, there's no need to prefill it again. To benefit from it, put the fixed part at the start of the prompt and the changing part (the user's question) at the end.
Estimating the speed of any model. Because decode is limited by memory, there's a quick formula for maximum speed:
tokens per second (max) ≈ memory bandwidth ÷ bytes of weights
Checking against the model above: 83 GB/s ÷ 1.98 GB ≈ 42 tokens per second at most; the measured figure is 36 (27.6 ms per step). Applied to bigger models (these are estimates, not measurements): Qwen2.5-7B in bfloat16 weighs about 15 GB, so on this machine it would manage about 5 tokens per second at most. A data-center GPU with about 3,000 GB/s of memory bandwidth would manage about 200. When choosing hardware for running LLMs, the first number to look at isn't computing power but memory bandwidth and memory capacity (to hold the weights and the KV cache).
Serving many people is almost free. The second puzzle has another side. If 8 people are each waiting for their next token, the server can send 8 tokens (one per person) through the model together: the weights are read once for all 8. The previous post measured it: 1 token takes 28 ms, 10 tokens at once take 52 ms. Serving 10 people costs less than twice as much as serving 1. That's the foundation of batching, the subject of the post on serving many users.
Summary
| Concept | What it really is |
|---|---|
| Prefill | The whole prompt goes through the model in one pass; sets time to first token; limited by compute |
| Decode | One token per step; sets tokens per second; limited by memory bandwidth |
| KV cache | Keeps the keys and values of every past token; each decode step computes just one new token |
| The memory wall | Decode reads weights at 87% of the maximum RAM speed, using less than 1/40 of the compute |
| 16-bit | Half-size weights: decode 1.7× faster; prefill on a CPU many times slower |
| Cache size | Layers × 2 × KV heads × head size × bytes; 10 GiB for 32K tokens on a 72B model |
| Grouped-query attention | A cache 7–8 times smaller; the gain is in memory, not computation |
| FlashAttention | Never builds the whole attention matrix; 10× faster at 8,000 tokens |
| Speed estimate | Max tokens/second ≈ memory bandwidth ÷ bytes of weights |
The first three posts have covered the whole path of an answer: text into tokens, tokens through the model, and why that path is fast or slow. But where do the 494 million numbers in the weights file come from? The next post trains a model from scratch, on Vietnamese text, right on the CPU, to see how random numbers gradually turn into something that can write.