BEYOND THE FORWARD PASS · CHAPTER 02

Life of a Prompt

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.

~20 min read1 interactiveTested Python

What you'll learn

  • Why prefill is compute-bound and decode is memory-bound
  • How paged attention stores the cache in fixed-size blocks
  • Why one block id covers every layer — 3 blocks, not 3 × layers
  • How continuous batching reuses a slot the moment a sequence ends
  • How chunked prefill keeps a long prompt from stalling decode

Before you start

A hotel, not a reserved hall

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.

Prefill then decode

Prefill

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.

Decode

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.

Three prompts, one block size

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.

PromptTokensBlocksFree slots
brew two cups311
the river froze overnight622
pack the tent before dawn933
Together the three prompts occupy 6 blocks. The long prompt occupies 3 blocks, not 3 × 4 layers = 12.

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

MANIM One token is 1,024 bytes. Three prompts share 6 blocks — not × layers again.

Logical tokens, physical 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.

Free queueidle physical blocks
Allocate on prefill and on decode overflow
Page tablelogical token range → block id
Free on EOS or max-token stop

Interactive · Grow one sequence

How many physical blocks does P3 occupy as it decodes?

full block partial last block

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.

Fill a seat the moment it empties

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

MANIM When one sequence ends, admit the next — keep the GPU busy.

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.

Queries from the chunk, keys from the cache

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.

ChunkNew queriesKeys and values
1Q = 4KV = 4
2Q = 4KV = 8
3Q = 4KV = 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.

Llama 3 8B, same arithmetic

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.

Block counts you can re-run

paging.pybytes, blocks, free slots, chunked prefill
"""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

Mistakes learners make

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.

What to remember

  • Prefill is compute-bound. Decode is memory-bound. A good scheduler mixes them.
  • Paged attention carves the cache into fixed blocks addressed by a page table.
  • One block id covers all layers. Count blocks from tokens and block size, once.
  • Continuous batching frees and fills seats every iteration. Chunked prefill splits a long prompt so decode still gets a turn.

Check yourself

1. How many blocks does a 9-token prompt need at block size 4?

3 blocks. The last block holds 1 token and wastes 3 slots. You do not multiply by the 4 layers.

2. Why is decode memory-bound?

Each step reads the whole model and the whole cache to write one token per sequence. The math is tiny next to that traffic.

3. In chunk 3 of a 12-token prompt with chunk size 4, what are Q and KV lengths?

Q = 4 (the new chunk) and KV = 12 (cache plus chunk).

4. A sequence finishes. What happens to its blocks under continuous batching?

They return to the free queue immediately. A waiting prompt can prefill into them on the next iteration.

Go to the source

Keep going