Efficient Memory Management for Large Language Model Serving with PagedAttention

When a large language model generates text, it produces one token at a time. At each step the model computes new key and value vectors for the attention mechanism. To avoid recomputing these vectors from scratch at every step, the system stores them in a key-value cache (KV cache). For a 13-billion-parameter model, a single request's KV cache can consume up to 1.7 GB of GPU memory.

The critical challenge is that the KV cache grows dynamically — one block of vectors per generated token — and its final size depends on the output length, which is unknown before generation finishes. Existing systems handle this by pre-allocating a contiguous memory region sized for the maximum possible sequence length. This causes three forms of waste.

First, internal fragmentation: the reserved region is almost always larger than the actual sequence, so the tail of each allocation is empty. Second, external fragmentation: as requests arrive and depart, the free memory becomes scattered into chunks too small for new allocations. Third, redundant duplication: techniques like parallel sampling and beam search generate multiple outputs from the same prompt, yet each copy stores its own full KV cache — even for the shared prefix.

Measurements on production systems show that these three wastes together consume 60–80% of KV cache memory. This directly limits the batch size, because fewer concurrent requests fit in GPU memory, which in turn reduces throughput.

Operating systems solved the exact same problem decades ago. In the 1960s, programs needed contiguous physical memory, which led to the same fragmentation nightmares. The solution was virtual memory with paging: give each program a contiguous logical address space, but map it to scattered physical pages through a page table. Programs see tidy consecutive addresses; the OS handles the messy physical layout.

PagedAttention imports this idea wholesale. Each request's KV cache is divided into fixed-size logical blocks (analogous to virtual pages). These logical blocks are mapped to physical blocks in GPU memory through a block table (analogous to a page table). The physical blocks do not need to be contiguous. The block manager allocates physical blocks on demand — one at a time — as new tokens are generated.

Think of it as giving each request a numbered notebook. The request writes on page 1, then page 2, then page 3. But page 1 might live on shelf A, page 2 on shelf G, and page 3 on shelf C. The block table is the index card that says "page 1 → shelf A, page 2 → shelf G, page 3 → shelf C." The request never notices the scattering.

Standard attention computes a weighted combination of all value vectors, where the weights come from the dot product of the query with each key. In a standard implementation, the keys and values for a single sequence are stored in contiguous tensors.

PagedAttention modifies the attention kernel so that keys and values are fetched block-by-block from non-contiguous physical locations. For each query vector, the kernel iterates through the block table, gathers the relevant key and value blocks, computes the partial attention within each block, and accumulates the result. The mathematical output is identical to standard attention — only the memory layout changes.

Concretely, let the block size be $B$ tokens. The KV cache for a sequence of length $T$ is divided into $\lceil T/B \rceil$ blocks. For each attention head, the keys in block $j$ form a matrix $K_j \in \mathbb{R}^{B \times d}$ and the values form $V_j \in \mathbb{R}^{B \times d}$, where $d$ is the head dimension. The attention for a single query $q$ is:

vLLM is a complete LLM serving system that uses PagedAttention as its memory foundation. The architecture has three key components: a centralized scheduler that decides which requests to process at each step, a KV cache manager (block manager) that handles allocation and deallocation of physical blocks, and a set of GPU workers that execute the model with the PagedAttention kernel.

The scheduler implements continuous batching (also called iteration-level scheduling): instead of waiting for an entire batch to finish before accepting new requests, it re-evaluates the active set at every single token-generation step. A request that finishes early immediately releases its blocks, and a new request can start in the same step. This eliminates the GPU idle time that plagued static batching.

The block manager tracks a free list of physical blocks, maintains reference counts for shared blocks, and performs copy-on-write when a shared block needs to be modified. It also handles preemption: when GPU memory runs low, the scheduler can pause a lower-priority request by either swapping its blocks to CPU memory or simply freeing them for recomputation later. This ensures the system never deadlocks due to memory pressure.

Many decoding strategies generate multiple output sequences from the same prompt. In parallel sampling, the model generates $n$ independent completions from the same input. In beam search, $k$ candidate sequences expand in parallel at each step. Both scenarios share a prefix: all sequences begin with the same prompt tokens and therefore share identical KV cache entries for those positions.

Without sharing, each sequence would duplicate the entire prompt's KV cache. With PagedAttention, all sequences point to the same physical blocks for the shared prefix. Only when a sequence needs to write a new token into a previously shared block does copy-on-write trigger: the system copies the block to a new physical location and updates that sequence's block table. This is identical to how Unix implements the fork() system call.

Measurements show 6–10% memory savings for parallel sampling and 37–55% savings for beam search. On the ShareGPT dataset with longer shared prefixes, savings reach up to 66% for beam search.

The authors evaluated vLLM against two state-of-the-art baselines: NVIDIA's FasterTransformer and Orca (the system that introduced continuous batching). They tested on OPT models (13B and 175B parameters) with real conversation datasets (ShareGPT and Alpaca).

Under basic sampling, vLLM achieved 2–4× higher throughput than FasterTransformer and 1.7–2.7× higher than Orca, with the same or lower latency. The improvement grew with longer sequences and larger models, because memory pressure is more severe in those settings. Under beam search, the gains were even larger due to copy-on-write sharing.

Memory waste measurements confirmed the mechanism: existing systems wasted 60.4–80.3% of KV cache memory, while vLLM wasted less than 4%. The only remaining waste is internal fragmentation in the last block of each sequence, bounded by the block size $B$.

PagedAttention's deepest contribution is not the 2–4× speedup — it is the reframing. Before this paper, LLM serving was treated as a pure ML systems problem. After it, the field recognized that memory management is the binding constraint, and that decades of OS research offer a ready toolkit. This shift in perspective opened the door to a generation of serving optimizations: prefix caching, radix attention, disaggregated prefill/decode, and speculative decoding — all of which build on the paged memory abstraction that this paper introduced.