II · THE IDEA · ARTIFICIAL INTELLIGENCE
Paged Attention for Efficient Memory Management
▶ Listen · narrated
When many requests share a GPU, memory reserved for attention caches often sits idle in fragments. Treating those caches like paged virtual memory lets a server pack far more of them in.
At a glance
- What it is
- Attention over a KV cache stored in non-contiguous fixed-size blocks
- OS parallel
- Logical pages mapped to physical frames, with a block table between them
- Main waste
- Fragmentation from reserving contiguous space per sequence up front
- Side benefit
- Blocks can be shared across sequences that reuse the same prefix
Think of the model’s memory for past tokens as a notebook that grows with every new word. The old habit was to tear out a huge fixed stack of pages for each conversation at the start, even if the chat might end quickly. Most of those pages stayed blank, and when a chat finished the gap left behind often did not fit the next conversation.
PagedAttention rules the notebook differently. Everyone shares one pile of identical small sheets. As a conversation needs room, it takes another sheet from the pile. Sheets for one chat need not sit next to each other. A simple contents list says which physical sheets belong to which chat and in which order. When the model must reread the past, it follows that list.
If two chats start with the same prompt, they can share the same sheets until their replies differ. Only then does a sheet get copied. The result is less blank paper sitting idle and more conversations fitting into the same desk.
In transformer decoding the KV cache stores, per layer, the projected keys and values for all prior positions so that attention at step t need not recompute them. Naïve serving allocates a contiguous KV tensor per sequence with shape sized to max_length. That creates internal fragmentation (unused slots within the reservation) and external fragmentation (free regions that cannot satisfy a new max_length slab).
PagedAttention partitions the cache into blocks of B tokens. Each sequence holds a block table: logical block indices → physical block IDs in a global GPU pool. Writes append within the current block; on overflow the allocator hands out another free physical block. The attention kernel is block-aware: it loads K/V by chasing the block table rather than assuming contiguity.
Block granularity also enables sharing. Prefill on a common prompt, parallel samples, or beam candidates can increment a reference count on the same physical blocks. Mutation after a fork uses copy-on-write so other references stay valid. Freed blocks return to the pool when the count hits zero.
Costs are indirection in the attention kernel, bookkeeping for the block table and refcounts, and possible partial-block waste bounded by one block per sequence. Benefits appear as higher achievable batch size and better utilisation under variable lengths—not as a change to the mathematical attention scores.
Look closer
Logical blocks, physical frames
Each sequence sees a tidy list of logical KV blocks as its cache grows token by token. Those logical blocks are mapped, through a block table, onto physical blocks carved from a GPU memory pool. Neighbouring logical blocks need not sit next to each other in device memory. The attention kernel follows the mapping at read time, so the model never requires one long contiguous slab per request.
Where the waste used to hide
Older serving designs often reserved a contiguous KV region sized for the maximum possible sequence length. Short prompts and early decoding steps left most of that reservation empty; once a request finished, the hole it left was often the wrong shape for the next arrival. Fixed-size blocks shrink internal waste inside a sequence and let the allocator fill gaps that would otherwise stay stranded between requests.
Sharing is a pointer change
When two outputs fork from the same prompt, or when beam candidates share a prefix, the corresponding physical blocks can be referenced more than once instead of copied. Reference counts track how many sequences still need a block; only when the count drops to zero does the block return to the free pool. Copy-on-write handles the moment a shared path diverges.
The story
Autoregressive serving has a memory problem that is easy to understate. For every active sequence the model must retain keys and values for every layer and every past token, because the next attention step will read them again. That KV cache often dominates GPU memory once batch size or context length rises, and it grows unevenly: one request may finish in a few dozen tokens while another runs toward the context limit.
A natural first design is to give each sequence a contiguous buffer large enough for the worst case. That is simple for the attention kernel, which can then stride through memory in a predictable way. It is also expensive. Most of the buffer sits empty for most of the request’s life. When the request ends, the free region is a single large hole only if nothing else is packed beside it; under load, free memory becomes a patchwork that will not fit the next full reservation even when the total free bytes would suffice. External fragmentation and internal fragmentation arrive together.
PagedAttention borrows the virtual-memory idea that operating systems have used for decades. Memory is divided into blocks of fixed size. A sequence’s KV cache is a list of logical block indices. A block table maps each logical index to a physical block in a central pool. When a new token is generated, the system writes its keys and values into the next slot of the current block, or allocates another physical block if the current one is full. The blocks that belong to one sequence may be scattered anywhere in the pool.
The attention computation must change to match. Instead of assuming one contiguous key and value tensor per sequence, the kernel walks the block table and gathers the relevant physical blocks. From the model’s point of view the history is still ordered; only the layout underneath is non-contiguous. That indirection is the cost of the scheme, paid so that the allocator can treat memory as a bag of interchangeable frames rather than a set of rigid per-request slabs.
Because allocation is block-grained, a sequence only holds memory for tokens it has actually produced, plus at most one partially filled block. When a request completes, its blocks return to the free list individually and can be reused by any other request. The same mechanism supports sharing: if several sequences begin from an identical prompt, they can point at the same physical blocks for that prefix. Divergence is handled by copy-on-write on the first block that differs. Parallel sampling and beam search become cheaper in memory for the same reason.
The practical effect on a busy server is higher packing density. More concurrent sequences fit in the same GPU memory, or the same concurrency leaves headroom for longer contexts. Throughput gains come less from faster arithmetic than from wasting fewer bytes on empty reservations and unusable holes. The idea is deliberately ordinary systems engineering applied to a structure that serving stacks had been treating as a single growable array.
Why it mattered then
As large language models moved from single-user demos into multi-tenant serving, the KV cache became the binding constraint on batch size. Pre-allocating contiguous space for every sequence was workable when few requests shared a device and contexts were short; it scaled poorly once operators tried to keep GPUs busy with many parallel generations. Fragmentation meant that measured free memory overstated how many new requests could actually start. PagedAttention addressed that gap with a familiar OS pattern, so serving systems could raise concurrency without waiting for larger devices or shorter prompts.
Why it matters now
Production inference still lives or dies by how densely the KV cache can be packed. Context windows keep growing, multi-turn chat keeps state alive longer, and techniques such as prefix reuse and speculative decoding multiply the value of block-level sharing. Any scheduler that admits dynamic batching benefits from memory that can be sliced and recombined without leaving stranded holes. The same block-table idea also clarifies capacity planning: operators reason in blocks and reference counts rather than in opaque per-request reservations, which makes memory behaviour more predictable under mixed workloads.
The surprising detail
The central trick is not a new attention formula but a layout change plus a kernel willing to chase a block table. Once KV memory is paged, sharing a prompt prefix across many outputs is mostly bookkeeping—reference counts and copy-on-write—rather than a separate model feature. Memory that used to be duplicated per beam or per sample can collapse to a single physical copy until paths diverge.
What is disputed
The original PagedAttention paper reports large gains in throughput and batch size for its serving system, but the exact improvement depends on workload mix, block size, model shape and how aggressive the baseline allocator was. Treat the mechanism as well-specified; treat any single speed-up figure as tied to that evaluation setup.
Remember this
PagedAttention stores the KV cache in fixed-size blocks mapped like virtual memory, so serving avoids contiguous pre-allocation waste and can share prefixes by reference.
Test yourself
A serving stack pre-allocates one contiguous KV buffer per request at the maximum sequence length. Under PagedAttention the same requests use fixed-size blocks from a shared pool. Give two distinct reasons the paged design can admit more concurrent sequences on the same GPU.
First, internal fragmentation shrinks: a sequence holds memory only for tokens already written, plus at most one partial block, instead of the entire max-length reservation. Second, external fragmentation shrinks: freed blocks are uniform and can back any sequence, so free memory is less likely to sit in holes the wrong shape for a new full buffer. A related bonus is prefix sharing—multiple sequences can reference the same physical blocks—which further reduces total KV bytes when prompts or beams overlap.
Go deeper
- [2309.06180] Efficient Memory Management for Large Language Model Serving with PagedAttention · arxiv.org
- [2310.06807] Longitudinal gOSNR Monitoring by Receiver-side Digital Signal Processing in Multi-Span Optical Transmission System · arxiv.org
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.