BEYOND THE FORWARD PASS · CHAPTER 02
A serving stack does not run one prompt at a time. It pages the KV cache, batches whatever is ready, and prefills long prompts in chunks.
Static batching is a reserved dining hall: twelve seats, twelve guests, nobody new until everyone has finished. Paged attention is a hotel. Rooms are fixed size. Guests check in with a few rooms and ask for another when they fill. When a guest leaves, those rooms go back on the board the same minute.
The attention math does not change. Paging is memory management for the KV cache. The model still does the same softmax. The server just stops wasting empty seats on short prompts, and stops making long prompts wait for a giant contiguous slab.
The whole prompt goes through in one parallel pass. This builds the cache and emits the first new token. Heavy on math. Bounded by compute.
Each later token is one forward of a single new query against the cache. Little math, lots of memory traffic. Bounded by bandwidth.
A scheduler that only prefills, or that waits to decode until every sequence in the batch is ready, will idle the GPU. The rest of the chapter is how to mix the two.
Toy decoder: 4 layers, 4 KV heads, head dim 16, bf16. Block size 4 tokens. One block identifier names the same slice of sequence in every layer.
two tensors, times layers, times KV heads, times head size, times two bytes. One token of cache is 1,024 bytes.
A block of 4 tokens is therefore 4,096 bytes. The layer count is already inside the 1,024. Do not multiply by 4 again.
| Prompt | Tokens | Blocks | Free slots |
|---|---|---|---|
| brew two cups | 3 | 1 | 1 |
| the river froze overnight | 6 | 2 | 2 |
| pack the tent before dawn | 9 | 3 | 3 |
That last-block waste is real. Up to 3 of 4 slots can sit empty. Papers sometimes say paging removes fragmentation; they mean external fragmentation (the “I have 9 free slots but not in a row” kind). Internal fragmentation in the last block remains.
1024 B · block · 6 blocks
Each sequence owns a page table: position 0–3 → block 7, position 4–7 → block 2, and so on. Physical blocks live in a pool with a free queue. Isolation comes from the tables, not from “never share a block”. Prefix caching and copy-on-write do share blocks on purpose.
Interactive · Grow one sequence
How many physical blocks does P3 occupy as it decodes?
Swap space, if the server has it, holds preempted sequences’ KV blocks so a higher-priority decode can run. It is not optimizer state. Inference has no optimizer.
Static batching waits for every sequence in the batch to finish. Continuous batching (iteration-level scheduling) checks every decode step: if P1 just emitted EOS, its 1 block returns to the free queue and a waiting prompt can start prefilling in the next iteration.
static · free · admit
Decode usually has priority. A new prefill is admitted when there is room, often in a chunk, so a 9-token prompt cannot freeze the users who are already generating.
A 12-token prompt with chunk size 4 is three prefills, not one. The new queries come only from the current chunk. Keys and values are the cache so far plus the chunk.
| Chunk | New queries | Keys and values |
|---|---|---|
| 1 | Q = 4 | KV = 4 |
| 2 | Q = 4 | KV = 8 |
| 3 | Q = 4 | KV = 12 |
Between chunks the scheduler can run a decode step for everyone already in flight. Time-to-first-token for a long prompt goes up a little. Inter-token latency for everyone else stays flat.
32 layers, 8 KV heads, head dim 128, bf16. Cache per token is 128 KiB. A 16-token block is 2 MiB. One user at 4,096 tokens holds 512 MiB of cache — before anyone else sits down.
The weights are about 15 GiB and they are shared. The cache is per user. That is why the block pool, not the parameter file, usually decides how many conversations fit on one GPU.
"""Paged attention on a tiny toy model. One block id covers every layer. A 9-token sequence with block size 4 needs 3 blocks, not 3 × layers. That is the accounting this file locks down. Toy model: 4 layers, 4 KV heads, head dim 16, bf16. """ from math import ceil # Toy decoder used on the page. Small enough to count by hand. LAYERS = 4 KV_HEADS = 4 HEAD_DIM = 16 BYTES_PER_NUM = 2 # bf16 BLOCK_SIZE = 4 # tokens stored in one block def bytes_per_token(layers=LAYERS, kv_heads=KV_HEADS, head_dim=HEAD_DIM, byte_width=BYTES_PER_NUM): """2 (K and V) × layers × KV heads × head dim × bytes per number.""" return 2 * layers * kv_heads * head_dim * byte_width def bytes_per_block(block_size=BLOCK_SIZE, **kwargs): """One block stores `block_size` tokens, for every layer at once.""" return bytes_per_token(**kwargs) * block_size def blocks_needed(n_tokens, block_size=BLOCK_SIZE): """How many blocks a sequence of n_tokens occupies. A block id spans all layers, so we do not multiply by the layer count. """ return ceil(n_tokens / block_size) def free_slots(n_tokens, block_size=BLOCK_SIZE): """Unused token slots in the last block (internal fragmentation).""" used = n_tokens % block_size return 0 if used == 0 else block_size - used # Three prompts on the page. Token counts are assigned on purpose # so the block math is obvious. These are not a real tokenizer's ids. PROMPTS = { "brew two cups": 3, # 1 block, 1 slot free "the river froze overnight": 6, # 2 blocks, 2 slots free "pack the tent before dawn": 9, # 3 blocks, 3 slots free in the last one } def total_blocks(prompts=None, block_size=BLOCK_SIZE): prompts = PROMPTS if prompts is None else prompts return sum(blocks_needed(n, block_size) for n in prompts.values()) def chunked_prefill_steps(n_tokens, chunk_size): """Split a long prefill into chunks. Chunk t attends with queries from that chunk and keys/values from everything up to (and including) that chunk. """ steps = [] done = 0 while done < n_tokens: take = min(chunk_size, n_tokens - done) q_tokens = take kv_tokens = done + take steps.append((q_tokens, kv_tokens)) done += take return steps
Multiplying blocks by layers. A block id already spans every layer. Nine tokens at block size 4 is 3 blocks, not 12.
“Paging is a new attention formula.” The scores are the same. The change is how K and V are addressed in memory.
“Prompts never share a block.” Isolation is the page table. Prefix caching shares the prefix on purpose, then copy-on-write if one user diverges.
CPU swap as optimizer state. Inference has no optimizer. Swap holds preempted KV blocks.
3 blocks. The last block holds 1 token and wastes 3 slots. You do not multiply by the 4 layers.
Each step reads the whole model and the whole cache to write one token per sequence. The math is tiny next to that traffic.
Q = 4 (the new chunk) and KV = 12 (cache plus chunk).
They return to the free queue immediately. A waiting prompt can prefill into them on the next iteration.