II · THE IDEA · ARTIFICIAL INTELLIGENCE
vLLM: PagedAttention for LLM Serving
▶ Listen · narrated
In LLM serving, the key-value cache often dominates GPU memory. How it is laid out decides how many requests fit — and how much of the card sits idle.
At a glance
- Problem
- KV cache pre-allocation wastes GPU memory through fragmentation
- Technique
- Store KV cache in fixed-size blocks, mapped like virtual pages
- System
- vLLM — a serving engine built around PagedAttention
- Payoff
- Higher batch size and throughput from the same GPU memory
Think of a busy library that once gave every reader a whole empty shelf long enough for the longest book imaginable. Most readers only needed a few inches, so most of every shelf sat empty, and when someone left, the gap was an odd size that the next person could not use.
PagedAttention gives readers fixed-size boxes instead. A short reply takes one box; a long one takes several. The boxes need not sit next to each other on the real shelf. A little card catalogue (the block table) remembers which boxes belong to which reader. When a reader finishes, their boxes go back on a free pile for anyone else.
The model still attends over the full conversation in order. Only the storage is chopped up. Because almost every box can be filled and reused, far more conversations fit in the same GPU memory, which is why a system such as vLLM can serve more users at once without changing the model’s maths.
Autoregressive LLM serving retains per-sequence key and value tensors for all prior tokens (the KV cache). Naive allocators reserve a contiguous device buffer per sequence at max length, causing internal fragmentation (unused tail capacity) and external fragmentation (non-reusable holes as sequences complete at different times). Effective batch size is then limited by stranded memory rather than by aggregate free bytes.
PagedAttention partitions KV storage into fixed-size blocks (analogous to pages). Each sequence holds a block table mapping logical block indices to physical block ids. Attention kernels resolve K/V through this indirection, so physical blocks need not be contiguous. Growth allocates one new block at a time; completion returns blocks to a global free list. Internal waste is capped at under one block per sequence; external fragmentation is largely removed for block-granular reuse.
Block tables also enable prefix sharing: beams or parallel samples reference the same physical blocks for a common prompt, with separate blocks only after divergence. vLLM implements this design as a serving engine. Limitations include kernel complexity for gather-based attention over scattered blocks, sensitivity to block size (too small increases map overhead; too large reintroduces internal waste), and workload-dependent gains when lengths are already uniform or concurrency is low.
Look closer
Contiguous reservation is the quiet bottleneck
Autoregressive decoding appends one token at a time, and each new token needs its key and value tensors kept for later attention. Conventional serving systems reserve a contiguous slab sized for the maximum possible sequence length up front. Most sequences never reach that length, so large stretches of reserved memory stay empty. Requests also finish at different times, leaving holes that a contiguous allocator cannot easily fill. The paper treats this as external and internal fragmentation — the same vocabulary operating systems use for physical RAM.
Blocks, not full sequences
PagedAttention splits each sequence’s KV cache into fixed-size blocks. Logical block indices for a request are translated through a block table to physical blocks that need not sit next to one another in GPU memory. Attention still reads the full logical sequence; only the storage layout changes. When a sequence grows, the engine allocates another block rather than copying an entire contiguous buffer. When it finishes, its blocks return to a free pool for other requests.
Sharing becomes cheap
Once KV memory is addressed by block tables, several logical sequences can point at the same physical blocks. Parallel sampling and beam search, which share a common prefix, no longer need separate full copies of that prefix’s cache. The paper emphasises this sharing as a direct consequence of the paging design, not an add-on allocator trick.
The story
Large language model serving is less about a single forward pass than about keeping many partially completed generations alive on one GPU. For every request in flight, the model must remember the keys and values already computed for earlier tokens; otherwise every new step would re-encode the whole prompt. That growing store is the KV cache. It is useful, large, and awkward to pack.
Older serving stacks treated each request’s cache as one contiguous allocation reserved for the worst-case length. The reservation had to be contiguous because the attention kernels expected a dense layout. The cost shows up immediately: a short chat reply still holds space for a long one; a finished request leaves a gap that the next arrival may be too large to occupy. Across a busy batch, a large fraction of the memory set aside for KV state can be stranded. Fewer concurrent sequences fit, so GPU compute sits underused while the memory budget looks full.
PagedAttention attacks the layout assumption rather than the attention maths. It borrows the virtual-memory idea that a process sees a contiguous address space while the hardware stores pages wherever free frames exist. Here the “page” is a block holding keys and values for a fixed number of tokens. Each request keeps a block table — a small map from its logical block indices to physical block ids on the GPU. When attention runs, the kernel uses that map to gather the right blocks; the sequence still looks contiguous to the algorithm, but the bytes need not be.
Allocation becomes incremental. A new request receives only the blocks its prompt needs. As decoding appends tokens, the engine hands out another block when the current one fills, instead of copying a whole growing buffer into a larger slab. When a request finishes, its blocks return to a free list and can be reused by unrelated requests. Internal waste is bounded by the unused slots inside a single block; external fragmentation shrinks because any free block can serve any request.
vLLM is the serving system built around this mechanism. Beyond packing, the block-table design makes prefix sharing natural: beam candidates or parallel samples that share an earlier prompt can reference the same physical blocks for that prefix, with copy-on-write behaviour when their paths diverge. Memory that once held duplicate prefixes can hold more distinct live requests instead.
The practical result reported in the paper is substantially higher throughput under the same GPU memory budget, because the limiting resource — KV cache capacity — is used more nearly to capacity. The attention computation itself is unchanged in mathematical form; what changes is where the keys and values live and how many sequences can coexist while they do.
Why it mattered then
By 2023, open-weight models such as those in the Llama family and Mistral 7B had made multi-request GPU serving a routine engineering problem rather than a rare research demo. Memory, not raw FLOPs, often set the concurrency ceiling. Existing systems still paid the fragmentation tax of contiguous KV reservations. PagedAttention arrived as a concrete answer: apply a well-understood OS technique to the dominant memory structure in autoregressive serving, and show that the kernel changes were feasible enough to ship in a working engine, vLLM.
Why it matters now
Serving stacks still live or die by KV cache efficiency. Context windows have grown, batching is the default path to acceptable cost per token, and techniques such as continuous batching assume that memory can be handed out and reclaimed finely. PagedAttention’s block model underpins how many production and open-source engines think about cache layout today. Anyone running open-weight models for more than one user at a time is still choosing, explicitly or by framework default, how that cache is carved up.
The surprising detail
The core insight is deliberately unoriginal in the best sense: the authors did not invent a new attention score, but treated GPU memory for KV state the way an operating system treats RAM — fixed-size pages, an indirection table, and a free list. The surprise is how much serving throughput was being left on the table by a layout convention that looked like a kernel detail rather than a model detail.
What is disputed
Throughput gains depend on workload shape — sequence-length distribution, sharing opportunities, and batching policy. The paper measures specific serving setups; absolute speedups will not transfer unchanged to every model size or traffic mix.
Remember this
PagedAttention stores the KV cache in non-contiguous blocks mapped by per-sequence tables, so GPU memory is no longer stranded by worst-case contiguous reservations.
Test yourself
A serving GPU has enough free KV memory in total for one more request, but the free space is split across several non-adjacent regions. Under contiguous KV allocation, what happens — and what changes if the same free space is organised as PagedAttention blocks?
With contiguous allocation the new request is rejected or stalled, because no single free slab is large enough even though the sum of free bytes would suffice. With PagedAttention the request can take any free blocks via its block table; physical adjacency is not required, so the same fragmented free memory can still admit the request (up to the last partially filled block’s internal waste).
Go deeper
- [2309.06180] Efficient Memory Management for Large Language Model Serving with PagedAttention · arxiv.org
- [2310.06825] Mistral 7B · arxiv.org
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.