PagedAttention is an attention and memory-management approach that stores a sequence's KV cache in blocks that need not be physically contiguous. A block table maps logical token blocks to their physical cache locations. The original work was introduced with vLLM; other engines may use related paged-cache designs with different implementations.
Start with the allocation problem
A simple server may reserve enough contiguous cache for a request's maximum context. If the request finishes early, much of that reservation is unused. Variable-size allocations and releases can also leave unusable gaps.
- Internal fragmentation: unused space inside an allocated unit.
- External fragmentation: free space exists but cannot satisfy a required contiguous allocation.
These are allocator problems, not an unavoidable requirement that all attention implementations reserve one giant block. Paged allocation reduces the need for maximum-length reservations and large contiguous regions.
Follow a block-table lookup
Assume blocks hold 16 token positions. A 35-token sequence needs three blocks with room for 48 positions; the final block has 13 unused slots.
| Logical token range | Logical block | Physical block in this example |
|---|---|---|
| 0–15 | 0 | 7 |
| 16–31 | 1 | 2 |
| 32–34 currently used | 2 | 11 |
The attention kernel follows the block table to read the right keys and values. Token order stays logical even though the physical blocks are scattered.
Read diagram source
flowchart LR
A[Sequence block 0] --> P7[Physical block 7]
B[Sequence block 1] --> P2[Physical block 2]
C[Sequence block 2] --> P11[Physical block 11]
If the hypothetical alternative reserved 512 token positions, the 35-token request would leave 477 unused slots. Paging leaves 13 in this example, plus block-table overhead. This arithmetic illustrates the benefit without promising a universal waste percentage. The PagedAttention paper reports results for its evaluated implementation and workloads.
Manage allocation, release, and pressure
- Allocate blocks when admitted work needs cache capacity.
- Extend the logical mapping as the sequence grows.
- Track shared-block references where sharing is supported.
- Release or retain blocks according to completion, cancellation, and cache policy.
- Apply a defined pressure policy when no block can be allocated.
A runtime may reject, preempt and recompute, offload, or use a supported cache hierarchy. Paging does not imply automatic operating-system-style swapping. For example, current vLLM V1 guidance describes recomputation as its default preemption mode. Verify the selected engine and version.
Smaller blocks reduce final-block waste but increase mapping and management overhead. Larger blocks can simplify handling while wasting more tail space. Kernel layout, hardware, and sharing behavior influence the useful choice.
Share a prefix without corrupting it
A block table can let multiple requests refer to the same compatible cached prefix. If shared state would be modified, copy-on-write creates a private copy before the modification. Merely appending a new block does not require copying every earlier block.
Suppose 100 requests share a 4,992-token prefix, exactly 312 blocks of 16 positions. A suitable prefix cache can hold those complete prefix blocks once and maintain request-specific suffixes. The potential reduction depends on whether that prefix is actually reused, resident, and compatible with the model and isolation rules.
A partial shared last block needs special care when requests append different tokens. Engines may choose to share only completed blocks or use appropriate copy-on-write handling. “Common text” is not sufficient: model revision, adapter, positions, token IDs, and relevant input state must agree. Review prefix-cache boundaries.
What improves, and what does not
| Claim | Accurate interpretation |
|---|---|
| More requests fit | Often possible because less cache space is wasted or duplicated |
| Throughput improves | Possible when cache capacity limited useful batching; measure other bottlenecks |
| Attention becomes cheaper mathematically | Paging does not inherently reduce the attention computation over retained tokens |
| Memory waste disappears | Tail waste, metadata, other allocations, and implementation constraints remain |
| Context becomes unlimited | Model context support and available memory remain finite |
Worked failure: a service reduces cache fragmentation but p95 latency stays high. The next investigation is queueing, prefill interference, compute, or communication—not a promise that an even smaller block will solve the problem. More admitted requests can actually worsen latency if compute was already saturated.
Interview practice
- What does a block table contain? The mapping from a sequence's logical cache blocks to physical storage locations, with implementation-specific metadata.
- Why are 35 tokens not exactly 35 slots in the example? Fixed-size blocks allocate three groups of 16, leaving unused capacity in the final block.
- Is PagedAttention semantic compression? No. It changes allocation and access, not which meaning the model retains.
- Why is copy-on-write needed? Shared cache state must remain unchanged for other requests when one request requires a mutation.
- Does paging guarantee CPU offload? No. Pressure handling is a separate runtime policy with its own costs.
- When might throughput fail to improve? When another resource already limits performance, or extra admitted work increases contention and misses latency targets.
Recall card and closing
Logical sequence → block table → physical cache → reference lifetime. Close with the memory saved, metadata and tail waste retained, and the measured effect on useful serving capacity.