We now know that a KV cache grows with every token. A serving system has another problem: requests do not all begin together, end together, or have the same length. If each request reserves one large contiguous memory area for its maximum possible answer, much of that reserved space sits unused.
Reserved space for unfinished answers can become wasted space.
The Contiguous Allocation Problem
Imagine three requests. Request A needs 6 tokens of cache, B needs 3, and C needs 5. If memory must give each request one continuous block sized for its maximum, completed or short requests can leave fragments that are hard to reuse for a new long request.
There are two forms of waste. Internal fragmentation is unused space inside an allocation, such as reserving room for sixteen tokens when only nine are present. External fragmentation is free space split into separate regions that cannot satisfy a required larger contiguous allocation.
These problems are about placing variable-size histories, not a requirement of the attention formula. If a request's keys are stored in order somewhere discoverable, attention can still use them. Paging gives the kernel a way to discover scattered blocks without moving the whole history into one new large area.
Some unused space is trapped inside reservations, and some sits between active regions.
This is similar to a familiar operating-system problem. Physical memory may have free pieces, but not one large free piece in the exact place a new allocation asks for.
Split the Cache Into Fixed Blocks
PagedAttention stores KV cache entries in fixed-size blocks. For example, one block may hold 16 token positions. A request does not need one uninterrupted physical region. It can use block 3 for its first 16 tokens and block 11 for its next 16 tokens.
A block holds a fixed number of token positions and the relevant cache features for the implementation's layout. The number of bytes per block depends on heads, head width, dtype, and whether layers are stored together or separately.
The sixteen-position example explains the concept; our hand calculation below uses four positions per block so every offset fits on the page. The actual engine's block size is an implementation choice. We should not assume that all versions or attention backends use the teaching size.
Logical token order does not require neighboring physical block addresses.
The word "paged" comes from virtual memory. A program sees a continuous virtual address range while the operating system maps pieces of it to physical pages. PagedAttention uses the same mapping idea for token blocks in a KV cache.
The Block Table Is the Map
Every request has a block table. It lists which physical cache block holds each logical portion of that request. A request's logical block indices might be 0, 1, and 2, mapped by table [9, 2, 14] to physical blocks 9, 2, and 14. The attention kernel uses this table to locate the correct K and V entries in token order.
The request sees tokens in order even when its blocks are scattered in GPU memory.
The cache remains semantically the same. The new query still attends to earlier keys and values. Only the storage layout and address lookup have changed.
Follow One Token Address
For a worked example, make each block hold four token positions and give request A nine cached tokens. Its logical blocks cover positions 0-3, 4-7, and 8-11. Only position 8 in the final block is filled so far.
Use block table [9,2,14]. To find token position 6, divide by the block size: . The logical block is 1 and the offset inside it is 2. Table entry 1 points to physical block 2. The kernel therefore reads physical block 2 at offset 2.
The word logical means the request's ordered view. Physical means the storage location used by the engine. Sorting the table by physical block number would scramble the token history rather than improve it.
A short Python calculation makes that translation explicit. No external package is needed.
block_size = 4
block_table = [9, 2, 14]
token_position = 6
logical_block, offset = divmod(token_position, block_size)
physical_block = block_table[logical_block]
assert (physical_block, offset) == (2, 2)The block table handles locations, not attention weights. After lookup, the newest query still scores the correct keys, applies its visibility rule, and mixes their matching values.
Growth Needs Only Another Free Block
When a request reaches the end of its current block, the engine allocates one more free block. It does not move the existing token history just to make one bigger contiguous region.
Blocks let a cache expand in pieces.
This is useful when many answers stream at different speeds. A short request can release its blocks as soon as it finishes, and a different request can reuse them.
At nine tokens, three four-token blocks provide twelve slots, so three slots in the final block are unused. The tenth, eleventh, and twelfth processed tokens fill them without another allocation. The thirteenth requires a fourth block.
For one unshared sequence with block size , the last block can waste at most token slots. Larger blocks can reduce table and bookkeeping overhead but waste more tail space. Smaller blocks reduce that tail waste but require more entries and more block management.
This is why paging reduces allocation waste without eliminating every overhead. The engine still stores a block table, maintains a pool of free blocks, and rounds allocations to the block size.
Batching Becomes More Flexible
An inference batch can contain requests whose cache blocks sit in many places. The kernel reads the per-request block tables and gathers the correct history. That storage flexibility supports a scheduler that adds and removes requests between steps. This scheduling policy, called continuous batching, is separate from the block-address lookup itself.
Each request has its own map, while the GPU still runs a shared batch step.
This does not remove the normal cache memory cost. The system still stores keys and values. It reduces waste caused by poor allocation layout and makes the available memory easier to share.
Prefix Sharing Is a Natural Extension
If two requests begin with the same long system prompt, their early cache blocks can be shared until the texts diverge. Request A and B then point to the same physical blocks for the common prefix and allocate different blocks only for their unique endings.
The shared prompt cache is computed and stored once.
Sharing requires careful bookkeeping. A shared block cannot be freed while any request still uses it. The engine tracks references so it knows when a block is truly available again.
Shared Blocks Must Not Be Changed in Place
A reference count records how many active users point to a shared block. Finishing one request reduces its count; it does not free a block still used by another request.
A partly filled shared block needs special care when branches append different tokens. With copy-on-write, the engine makes a private copy before changing the shared part. Full prefix blocks can stay shared while each branch grows its own suffix.
Prefix reuse also needs compatible computation: the same relevant token prefix, model state, position rules, and cache settings. Similar English meaning is not enough. Two prompts that tokenize differently cannot simply share their hidden-state cache because they look alike to a reader.
The PagedAttention paper explains the block mapping and sharing approach. Particular serving systems may impose additional rules, such as which full blocks they retain for reuse.
Why This Helps vLLM
vLLM is an inference engine that made PagedAttention widely known. Its aim is to serve more active generation requests efficiently by managing KV-cache memory in blocks and scheduling requests well.
It is not a different language model. A model still has its weights, attention layers, and cache requirements. vLLM changes how inference work and cache storage are managed.
A Tiny Block-Table Example
Suppose blocks hold four tokens. A nine-token request needs three logical blocks: positions 0 to 3, 4 to 7, and 8. Its block table might map them to physical blocks 9, 2, and 14. Attention follows logical order through the table, not physical numeric order.
Physical block numbers can look scrambled while logical token order stays correct.
PagedAttention and FlashAttention solve different problems. Paging decides where saved cache entries live and how requests map to them. FlashAttention organizes the arithmetic and movement of temporary attention data. A serving system can combine paged cache storage with attention kernels designed for that layout.
Neither method changes a request's token order or makes future output tokens available early. To check a paging implementation, compare its output with a contiguous reference while moving physical block locations. If only the locations changed, the mathematical result should not.
Recap
This is how PagedAttention manages a KV cache like virtual memory. It divides cache storage into fixed-size blocks and gives each request a block table that maps logical token ranges to physical blocks. A request can grow without moving its earlier cache.
This reduces allocation waste, supports flexible batching, and enables shared prefix blocks. Day 29 returns to the position information inside attention and explains RoPE.
