Efficient Memory Management for Large Language Model Serving with PagedAttention

The memory you allocate but never use

A serving system has to put each request's KV cache somewhere, and the obvious place is a single contiguous slab of GPU memory. But a request's final length is unknown when it arrives, so the conservative choice is to reserve enough for the worst case: max_seq_len × kv_size_per_token. That reservation is where the memory goes to die. Internal fragmentation is the slack inside the slab — a request capped at 2048 tokens that stops after 128 leaves 1920 tokens' worth of reserved space untouched until the request finishes. External fragmentation is the slack between slabs — when requests of different reserved sizes come and go, the freed regions are the wrong shapes to host the next arrival, leaving holes nothing fits into. Measured on real workloads, the two together leave 60–80% of KV memory allocated but carrying no live token. Memory is the binding constraint on batch size, so that waste is throughput thrown away.

Paging the cache

PagedAttention borrows the fix operating systems found decades ago: stop demanding contiguity. The KV cache is divided into fixed-size blocks, each holding the keys and values for a small constant number of tokens — 16 is the paper's default. Blocks are allocated on demand as a sequence grows, one block at a time, and they can live anywhere in GPU memory. Nothing is ever reserved for a length the sequence may never reach. A sequence holds exactly as many blocks as its current length requires, plus at most one partially filled block at the tail.

Block tables: logical order, physical scatter

Because a sequence's blocks are scattered, something has to record where they actually are. Each sequence carries a block table mapping each logical block index — its position in the sequence's token order — to the physical block number where those keys and values reside. Attention walks the logical indices in order, follows each through the table to its physical block, and gathers the keys and values from there. The kernel sees a contiguous logical sequence; the hardware sees scattered physical blocks; the table is the indirection that reconciles them, exactly as a page table reconciles virtual and physical addresses.

Sharing a prefix without copying it

The indirection buys a second win. When two requests share a leading prefix — most often an identical system prompt — their early logical blocks can point at the same physical blocks, with a reference count tracking how many sequences depend on each. One copy of the prefix in memory serves all of them. When a shared sequence later diverges and needs to write into a shared block, the system performs copy-on-write: it duplicates just that one block, points the writing sequence at the private copy, and decrements the original's reference count. This is what makes beam search and parallel sampling cheap — the candidates share everything up to the point they actually differ, and only the divergent tail is ever duplicated.

The fragmentation arithmetic

With paged allocation the only waste left is the single partially filled block at the tail of each sequence. With a block size of 16 tokens, the worst-case slack per sequence is 15 tokens, and across realistic sequence lengths the wasted fraction falls below 4% — against the 60–80% of the contiguous scheme. That reclaimed memory does not sit idle; it is spent on more concurrent sequences. A larger effective batch size is precisely what raises decode utilization, so the memory win converts directly into a throughput win.

What it buys end to end

Folded into vLLM, PagedAttention delivers 2–4× the throughput of Hugging Face TGI on OPT-13B and LLaMA-13B at equal latency, with the gap widening as sequences get longer and as more requests share prefixes. The mechanism is mundane — fixed-size blocks, a level of indirection, reference-counted sharing — and that is the point: the hard part of LLM serving was never the attention math, it was managing the memory the cache lives in.