PagedAttention: Virtual Memory for the KV Cache

A serving engine cannot know how much KV cache a request will eventually need. Reserving its entire context limit up front is simple, but ties up memory that other requests could use. PagedAttention lets the cache grow in small blocks while attention still sees tokens in their original order.

The useful analogy is an operating system's page table: a logical address need not identify a contiguous physical allocation. Here the serving engine manages the table, and the attention kernel follows it in software. There is no CPU-style page fault on each new token.

Where contiguous allocation wastes space

Consider three requests with 25, 47, and 12 stored tokens, counting prompt tokens and generated tokens whose keys and values have been computed. If each reserves 2,048 slots, the engine allocates 6,144 slots for 84 tokens.

With 16-token blocks, the requests need two, three, and one blocks: 96 slots in total. The remaining 12 slots are padding in their final blocks. In this small example, paged allocation reserves one sixty-fourth as many slots. The calculation measures reserved capacity, not execution speed.

This is internal fragmentation: unused space inside an allocation. Variable-sized contiguous allocations can also suffer external fragmentation. For example, separate free regions of 1,500 and 800 slots cannot satisfy a contiguous 2,048-slot request even though they contain enough free space together. Fixed-size blocks avoid that particular placement problem.

The original PagedAttention paper measured substantial cache waste in the serving systems it compared and reported 2–4× throughput improvements for vLLM in its tested configurations.

A block table preserves token order

Each request has a list mapping logical block numbers to physical blocks in a shared pool. With a block size of 16, token position 37 belongs to logical block 2 at offset 5. If table[2] is 9, the kernel reads offset 5 of physical block 9.

Address calculation changes; the intended attention function does not.

For an unshared request of length $T$ and block size $B$, the allocation is

token slots. Waste is less than $B$ slots per request, not a constant for the entire server. Across many short requests, those partially filled blocks can still matter.

The block's byte size depends on the model's KV heads, head dimension, layers represented by the allocation, and storage dtype. It is not generally block_size × hidden_dimension: grouped-query attention stores fewer KV heads than query heads.

Growing a request

Suppose the 25-token request uses physical blocks [3, 7], the 47-token request uses [0, 5, 9], and the 12-token request uses [4]. A pool of 64 blocks has 58 blocks free after these six allocations. It has only 1,024 slots altogether, so the earlier reservation of 6,144 slots would not fit in this pool.

If the 47-token request stores ten more tokens, it grows to 57 tokens and needs a fourth block. The engine allocates P11 and extends its table to [0, 5, 9, 11]. Existing KV entries stay where they are. Twenty additional tokens would instead require five blocks.

Allocation does not guarantee that every admitted request can grow forever. If the pool fills, the scheduler needs an explicit policy: delay admission, preempt work, evict reusable cache entries, or otherwise recover capacity.

Sharing a prefix and copying a partial block

Two continuations of the same prompt can point to the same immutable prefix blocks. A reference count tracks how many users still need each block. This avoids both duplicate storage and, when cached computation can be reused, repeated prefill work.

A full shared block needs no copy when generation moves into a new block. For example, an 800-token prefix exactly fills fifty 16-token blocks; the next stored token can go into a new private block.

A partially filled shared final block is different. Suppose A and B share P0 with 16 tokens and P1 with eight tokens. Before B writes its next KV entry into P1, it needs a private copy. The engine copies the existing eight entries to P2, redirects B's table, adjusts reference counts, and writes the new entry to P2. A retains its original view.

Prefix reuse requires compatible model state, token positions, and exact relevant inputs; matching visible text alone is insufficient. Implementations may restrict reuse to complete blocks. SGLang's RadixAttention organizes reusable prefixes in a radix tree.

Block size is a kernel choice too

Smaller blocks reduce final-block padding, but require larger tables and may make the attention kernel less efficient. Larger blocks trade some capacity for coarser addressing and different memory-access behavior. Supported sizes and good choices depend on the backend, model, and workload.

Paged storage and FlashAttention's tiling can coexist, but a cache block is not automatically the same thing as an on-chip compute tile. The kernel must support the chosen layout.

The indexing rule in code

This small example checks allocation counts and address translation. It models bookkeeping only: it does not store actual KV tensors, implement copy-on-write, or schedule a GPU.

from math import ceil
 
block_size = 16
lengths = [25, 47, 12]
blocks = [ceil(n / block_size) for n in lengths]
assert blocks == [2, 3, 1]
assert sum(blocks) * block_size == 96
 
b_table = [0, 5, 9]
position = 37
logical_block, offset = divmod(position, block_size)
physical_block = b_table[logical_block]
assert (physical_block, offset) == (9, 5)
 
new_length = lengths[1] + 10
assert ceil(new_length / block_size) == 4
b_table.append(11)  # allocated from the free pool

Paging reduces wasted cache capacity. The next question is how much capacity remains after weights and runtime buffers: Memory Management for LLMs.

Additional reading

• PagedAttention and vLLM, Kwon et al. The original allocation, sharing, and evaluation design.
• vLLM PagedAttention design. How an attention kernel addresses blocks.
• SGLang, Zheng et al. RadixAttention and prefix reuse.