Why it matters
Reserving the maximum context for every sequence wastes most of the memory most of the time, and that waste caps how many requests a card can hold. PagedAttention borrows the operating system's answer: allocate small blocks on demand, keep a per-sequence mapping, and let sequences that share a prefix reference the same physical blocks. The gain is capacity, and the price is an indirection in the attention kernel.
Mental model
It is virtual memory for attention state: a sequence holds a page table and the allocator hands out frames as needed. The analogy breaks at the page fault, because there is no disk to fault to; when blocks run out the engine must preempt a sequence or reject the request.
How it works
A · block table
Logical positions map through the table; a partial last block wastes only its tail.
| logical | block |
|---|---|
| L0–3 | A0 |
| L4–7 | A1 |
| L8–11 | A2 |
| L12–15 | A3 |
Step · 1 of 8
A prompt cached in four blocks
A's 16-token prompt is placed in four blocks of four positions each. A per-sequence buffer sized to the maximum context would have reserved the whole window; here only the four blocks A needs are allocated.
Next: Decode fills a fifth, partial block
- Blocks used
- 4
- Sequences
- 1
- Block copies
- 0
- Tail waste (slots)
- 0
- Outcome
- —
Figure. Twenty-four physical blocks of four token positions each for one layer. The block tables are the indirection: logical positions map through a per-sequence table, so A and B can point at the same physical blocks and diverge with one copy. Counts and allocation are illustrative, not an engine trace. Table-lookup overhead and swap are not measured.
What to notice. Paging removes the reservation waste, not the ceiling. At step 5 the pool holds eight sequences and 18 of 96 token slots sit idle in partial tails; G's three blocks are full, which is why its next token needs a fourth. Sharing saves four full blocks at step 3, but the copy-on-write burst at step 6 needs three new blocks and evicts a running sequence. With no exhaustion policy (step 7) the next token has no block and the request dies after partial output; step 8 shows the alternative, a 429 before the first token.
Text version
One 24-slot physical block pool with four block tables. Step 1: A's 16-token prompt fills A0–A3. Step 2: A decodes two tokens into A4, whose tag reads 2/4, so two slots are reserved and unused. Step 3: B shares A0–A4 by reference; the reference count is two and no blocks are copied. Step 4: B appends at logical L18; A4 is copied to B5, which holds L16–18, and B writes there — A0–A3 stay shared, A4 becomes A-only, one copy. Step 5: six short sequences fill the remaining blocks; the pool is 24/24 and 18 of 96 token slots are tail waste; most sequences end in a partial block, while G's three blocks are full. Step 6: three branches diverge at once; three copies need three blocks and evict D's three blocks. Step 7: G's next token needs a fourth block; the pool has none and no policy is configured, so the block table shows L12 with no physical block and G fails mid-generation. Step 8: M is rejected at admission with 429 before its first token. Counters: blocks used 4, 5, 5, 6, 24, 24, 24, 24; sequences 1, 1, 2, 2, 8, 10, 10, 10; copies 0, 0, 0, 1, 1, 4, 4, 4; tail waste 0, 2, 2, 3, 18; outcome fail at step 7 and reject at step 8.
- Split the cache into blocks of a fixed number of tokens and size the block from the kernel's vectorisation, not from convenience.
- Give each sequence a block table mapping logical positions to physical blocks, and grow it as tokens are appended.
- Reference-count blocks so a shared prefix can be read by many sequences without duplication.
- Copy a block on write when a shared sequence diverges, so one branch cannot corrupt another's history.
- Make the attention kernel gather through the table, and measure the overhead against a contiguous implementation.
- Handle exhaustion explicitly: preempt, swap or reject, and record which path was taken.
Trade-offs
| Choice | Good for | Cost | Fails when |
|---|---|---|---|
| Small blocks | Less internal fragmentation | Larger tables and more lookups | Contexts are long and table overhead matters |
| Large blocks | Fewer lookups and a simpler kernel | Wasted space at the end of each sequence | Many short requests share a card |
| Copy-on-write sharing | Memory savings on common prefixes | Bookkeeping and copy cost on divergence | Every sequence diverges early |
| Swapping to host | Avoids rejecting work | Transfer latency inside the request | The latency budget is tight |
Good for
Less internal fragmentation
Cost
Larger tables and more lookups
Fails when
Contexts are long and table overhead matters
- Contexts are long and table overhead matters
- Many short requests share a card
- Every sequence diverges early
- The latency budget is tight
Figure. Each choice with what it buys, what it costs, and the case where it loses.
What to notice. The fourth column is the decision: if the losing case describes your situation, the choice is wrong.
Text version
Four trade-offs: Small blocks is good for Less internal fragmentation, costs Larger tables and more lookups, and fails when Contexts are long and table overhead matters. Large blocks is good for Fewer lookups and a simpler kernel, costs Wasted space at the end of each sequence, and fails when Many short requests share a card. Copy-on-write sharing is good for Memory savings on common prefixes, costs Bookkeeping and copy cost on divergence, and fails when Every sequence diverges early. Swapping to host is good for Avoids rejecting work, costs Transfer latency inside the request, and fails when The latency budget is tight
Failure modes
- Block-table overhead. Gather cost dominates for very long contexts and throughput falls below the contiguous baseline. Debug: compare tokens per second at increasing context length against a non-paged engine.
- Copy-on-write storm. Many sequences share a prefix and then diverge at once, copying blocks in a burst. Debug: count copy-on-write events per second against the divergence point distribution.
- Exhaustion without a policy. The allocator fails mid-generation and the request dies after producing part of an answer. Debug: force a small block pool in staging and observe the engine's behaviour at the boundary.
In production
Monitor allocated blocks, fragmentation at the tail and preemption events. Set a maximum context per request so the pool has a predictable worst case, and rehearse the exhaustion path rather than discovering it in an incident.
Common misconceptions
People think: Paging makes the cache free.
Actually: It removes reservation waste; total bytes still scale with live tokens, and the pool still has a hard ceiling.
People think: Paging is only about memory, not speed.
Actually: It changes the attention kernel's memory access pattern, which is why block size is also a performance parameter.
Interview angle
Explain the reservation problem first, then the block table, sharing and copy-on-write. A strong answer names fragmentation and exhaustion as the residual costs. Weak answers describe paging as a product feature without saying what problem it solves.
Sources
- Kwon et al., PagedAttention — the block-table design and its memory savings.
- vLLM documentation — block size, prefix caching and preemption in a production implementation.