PagedAttention Explained: Virtual Memory for the KV Cache

PagedAttention is a technique for managing the key-value cache of a large language model by splitting it into small, fixed-size blocks that do not need to be contiguous in GPU memory. It borrows the idea of paging from operating systems: each sequence has a logical view of its cache, and a block table maps those logical blocks onto physical blocks scattered anywhere in memory. The result is far less wasted memory, which lets an inference server fit more concurrent requests on the same GPU.

It was introduced alongside the vLLM inference engine and has since become a standard design pattern across LLM serving systems.

The problem: the KV cache is big and unpredictable

During generation, a transformer stores the key and value vectors for every previous token so it does not recompute them at each step. That store is the KV cache, and it grows by one entry per layer for every new token. For long contexts and many concurrent users, the KV cache, not the model weights, often decides how many requests a GPU can serve at once.

The difficulty is that the server does not know how long each response will be. Early serving systems handled that uncertainty by reserving one contiguous chunk of memory per request, sized for the maximum possible sequence length. That approach wastes memory in three ways:

• Reservation waste. A request that might produce thousands of tokens holds its full reservation from the first token, even though most of it sits empty for most of the request’s life.
• Internal fragmentation. A request that finishes early never uses the tail of its reservation at all.
• External fragmentation. As requests of different sizes start and finish, free memory breaks into gaps too small for a new contiguous reservation, even when the total free space would be enough.

Together these can leave a large share of KV cache memory allocated but unused.

How PagedAttention works

PagedAttention applies the same fix that virtual memory applies to RAM.

1. Fixed-size blocks. GPU memory for the KV cache is divided into blocks, each holding the keys and values for a fixed number of tokens, such as 16.
2. Logical blocks per sequence. Each request sees its cache as a sequence of logical blocks: tokens 0–15 in block 0, tokens 16–31 in block 1, and so on.
3. A block table. For each request, a block table maps logical block numbers to physical block locations. Physical blocks can be anywhere and in any order.
4. Allocate on demand. A new physical block is allocated only when the current last block fills up. Nothing is reserved in advance.
5. A block-aware attention kernel. The attention computation is rewritten to follow the block table, gathering keys and values from non-contiguous blocks instead of assuming one contiguous array.

With this layout, the only waste per request is the unused tail of its final block, which is bounded by the block size. External fragmentation disappears because every block is the same size, so any free block can serve any request.

Sharing blocks between sequences

Because the mapping is indirect, two sequences can point to the same physical block. That opens up memory savings beyond fragmentation:

• Parallel sampling. When a user requests several completions for one prompt, every completion shares the prompt’s blocks instead of holding its own copy.
• Beam search. Candidate beams that share a common history share the blocks for that history. Beam search creates many such overlapping sequences.
• Shared prefixes. Requests that start with the same system prompt or few-shot examples can reuse the same physical blocks for that prefix.

Shared blocks carry a reference count. When a sequence needs to write into a shared block, for example because its continuation diverges from a sibling’s, the system copies that block first and updates the writer’s block table. This is copy-on-write, applied at the granularity of a few tokens.

Contiguous allocation vs PagedAttention

	Contiguous per-request allocation	PagedAttention
Memory reserved	Up front, for the maximum length	On demand, one block at a time
Internal waste	Unused tail of the reservation	At most part of one block
External fragmentation	Yes	Effectively none
Sharing prompts across sequences	Requires copies	Shared blocks with copy-on-write
Attention kernel	Simple contiguous reads	Gathers through a block table
Concurrency on a fixed GPU	Lower	Higher

Why it matters for throughput

The point of saving memory is to batch more work together. Modern servers use continuous batching, adding new requests to the running batch as soon as others finish. Continuous batching is only as good as the memory manager beneath it: if a new request cannot get a contiguous region, it waits. With paged allocation, any free block is usable, so the scheduler can keep the batch full.

More concurrent sequences means better GPU utilization, since decode steps are often limited by memory bandwidth rather than compute. Serving more tokens per step amortizes the cost of reading the model weights.

Preemption and scheduling

On-demand allocation introduces a new situation: the GPU can run out of free blocks mid-generation. Paged systems handle that by preempting some sequences. Two common strategies:

• Swapping. Move a sequence’s blocks to CPU memory and bring them back later.
• Recomputation. Drop the sequence’s blocks and recompute them from the prompt and generated tokens when it resumes, which can be cheaper than swapping because the prefill pass is efficient.

The scheduler typically preempts the most recently arrived requests first so older ones can finish.

Trade-offs and related techniques

PagedAttention is not free. The block-table indirection makes the attention kernel more complex and can make memory access less regular. Block size is a tuning knob: smaller blocks waste less memory but add more table entries and more scattered reads; larger blocks do the opposite.

It also complements rather than replaces other attention optimizations. FlashAttention reduces memory traffic within the attention computation itself, and grouped-query attention shrinks the KV cache by sharing key and value heads. Production engines commonly combine all three.

The takeaway

PagedAttention treats the KV cache like virtual memory: fixed-size blocks, a per-sequence block table, and allocation only when needed. That removes most fragmentation, lets sequences share prompt blocks through copy-on-write, and gives continuous batching the free memory it needs to keep GPUs busy. The cost is a more complex attention kernel and a scheduler that must handle preemption when blocks run out.