Efficient Memory Management for Large Language Model Serving with PagedAttention

How many requests can be batched, which is bounded by GPU memory for the KV cache. Existing systems wasted most of it: only 20–38% of KV cache memory held actual token states.

They stored each request’s KV cache contiguously and pre-allocated a chunk for the maximum possible length, because the output length is unknown. This causes reserved-but-unused slots, internal fragmentation (requests end shorter than reserved) and external fragmentation between chunks of different sizes, and prevents sharing between sequences.

An attention algorithm that lets a sequence’s keys and values live in non-contiguous memory: the KV cache is split into fixed-size blocks, like pages in an operating system’s virtual memory (blocks as pages, tokens as bytes, requests as processes), allocated on demand.

The prompt phase processes all prompt tokens at once (parallel matrix–matrix work, GPU-efficient) and builds their KV cache. The generation phase produces one token per iteration using the cached keys and values (matrix–vector work), which is memory-bound and dominates latency.

Per token: 2 (key and value) × 5,120 (hidden size) × 40 (layers) × 2 bytes (FP16) = 800 KB; a 2,048-token sequence needs up to 1.6 GB, so even a whole GPU fits only a few tens of requests. GPU compute also grows faster than memory capacity.

With block size \(B\), key block \(K_j\) holds keys of tokens \((j-1)B+1 \ldots jB\), likewise \(V_j\). The kernel fetches each block wherever it is stored, computes the query’s attention scores against \(K_j\) and combines them with \(V_j\); the result is identical to ordinary attention.

Each request has logical KV blocks filled left to right; a block table maps them to physical blocks anywhere in GPU memory and records how many slots are filled. A new physical block is allocated only when the last one is full, so waste per request is at most one partly filled block.

Samples from the same prompt map their prompt blocks to the same physical blocks with a reference count. When a sample needs to write into a shared block, copy-on-write gives it its own copy, as when an operating system forks a process.

Beam candidates share not only the prompt but also long common prefixes, and the sharing pattern changes each step like a process tree; blocks whose reference count drops to zero are freed. Previous systems had to copy large parts of the KV cache between candidates. Memory savings reached 37–55% for beam search vs 6–10% for parallel sampling on Alpaca.

The provider can keep the prefix’s KV cache in reserved physical blocks, like a shared library across processes; each request maps its first logical blocks to them (last block copy-on-write), so only the request-specific part of the prompt is computed.

With first-come-first-served scheduling, it preempts the latest requests, evicting all blocks of a sequence group at once (all-or-nothing, since they are always used together), and later recovers them by swapping blocks back from CPU memory or by recomputing the KV cache from prompt plus generated tokens.

At similar latency it sustained 2–4× the request rate of state-of-the-art systems such as Orca and up to 22× that of FasterTransformer; e.g. on ShareGPT with OPT-13B it batched 2.2× more requests than Orca with oracle knowledge of output lengths. Gains were largest for long sequences, large models and complex decoding.

Accessing block tables, extra branches and variable sequence lengths made the attention kernel 20–26% slower than FasterTransformer’s, but this affects only the attention operator, and end-to-end throughput is far higher.

Too small and the kernel can’t exploit GPU parallelism; too large and internal fragmentation grows and sharing becomes less likely. Block size 16 worked well across workloads and is vLLM’s default.

Swapping suffers with small blocks, because many small CPU–GPU transfers underuse PCIe bandwidth; recomputation’s cost is independent of block size. Recomputation wins for small blocks, swapping for large ones; for 16–64 they perform similarly.