Efficient Memory Management for Large Language Model Serving with PagedAttention

Storing the KV cache in fixed-size blocks, like operating-system pages, raises LLM serving throughput 2-4×.

A language-model server can run only as many requests at once as their key-value caches fit in GPU memory. Earlier servers reserved one contiguous region per request, sized for the longest possible output, and real tokens filled 20-38% of it. vLLM hands out 16-token blocks as a request grows and looks them up through a per-request table, and real tokens fill 96%.

The SOSP 2023 paper that introduced vLLM: an attention kernel that reads keys and values from scattered memory blocks, and the block manager, copy-on-write sharing and preemption policy built around it.

A language model generates text one token at a time, and every new token attends to all the tokens before it. To avoid recomputing the past at every step, the server keeps each request's attention keys and values in GPU memory, the KV cache. Woosuk Kwon and eight coauthors, most of them at UC Berkeley, measured how existing servers lay that cache out, found that most of the reserved memory held nothing, and rebuilt the allocator on the virtual-memory design operating systems have used since the 1960s. Their server, vLLM, sustains 2-4× the request rate of FasterTransformer and Orca at the same latency, without changing model accuracy.

The page follows the paper's order. It starts with why KV memory, not arithmetic, caps a server's throughput, using the numbers for OPT-13B on one A100. It then covers the three ways the contiguous layout wastes that memory, the paged layout that removes them, and the attention kernel that reads the paged layout, and ends with sharing between sequences, preemption, and the measured results.

Why the KV cache limits LLM serving throughput

In Transformer attention, each position $i$ projects its hidden state $x_i$ into a query, a key and a value:

The output at position $i$ is a weighted average of the values at positions 1 through $i$, with weights from a softmax over the query-key dot products, each divided by $\sqrt{d}$, where $d$ is the dimension of a key vector:

Both sums run to $i$, so producing token $i+1$ needs every earlier key and value. A server handles a request in two phases. The prompt phase (also called prefill) runs the whole prompt through the model at once, computes the keys and values of all prompt tokens with large matrix-matrix multiplies, and produces the first output token. The generation phase then runs one step per output token: it computes the new token's query, key and value, appends the key and value to the cache, and evaluates (3) against the whole cache. Each step multiplies a single vector by every weight matrix, so the GPU spends most of the step reading weights from memory and little of it computing.

Batching fixes the arithmetic side: one read of the weights serves every request in the batch. The batch size is then limited by memory, because each request brings its own cache. For OPT-13B the cache of one token is

and OPT generates up to 2048 tokens, so one request's cache can reach 1.6 GB. On an A100 with 40 GB, the 13 billion FP16 weights take 26 GB, and the paper leaves 12 GB for KV caches (Table 1), which it counts as 15.7K token slots. The rest holds activations, the temporary tensors of the current step.

If the server reserves 2048 slots for every request, 15.7K slots hold 7 requests (15,700 / 2048 = 7.7). The paper's Orca (Max) baseline does exactly that, and its measured average batch is 7.00 requests on both of its datasets. ShareGPT conversations average 161 prompt tokens and 338 output tokens, 499 in total. A server that gives each request only the 16-token blocks it fills (499 tokens round up to 32 blocks, 512 slots) fits 15,700 / 512 ≈ 30 such requests. vLLM's measured average batch on ShareGPT is 30.42. The estimate ignores that running requests are partway through their outputs and that the batch also depends on how fast requests arrive, so read the match as rough.

With 2048-token reservations, the count stays at 7 for every request length, and at the ShareGPT average 76% of each reservation is empty. With blocks, the count rises from 7 at 2048 tokens to 30 at the ShareGPT average and 196 at the Alpaca average of 78 tokens.

Another way to fit more requests is to make each token's cache smaller. Multi-query attention gives all query heads one shared key and value, and grouped-query attention, used in Mistral 7B, shares one per group of heads. Those change the model; PagedAttention changes only how the server stores the cache, and works with any of them.

Where contiguous allocation wastes memory

Before vLLM, servers such as FasterTransformer and Orca stored each request's KV cache as one contiguous tensor, because deep-learning frameworks expect a tensor to occupy one contiguous range of memory. The final length of a request is unknown when it arrives, so the server reserves a range sized for the longest it might get, up to the model's limit of 2048 tokens (Sec. 3.1). The paper counts three kinds of waste in that design:

• Reservation: slots for tokens the request will generate later. They will be used, but until then no other request can have them.
• Internal fragmentation: slots the request will never use, because its output stopped short of the length the server reserved for. The server learns this only when the request finishes.
• External fragmentation: memory between reservations that the allocator cannot hand to anyone. The Orca baselines use a buddy allocator, which serves memory in power-of-two-sized chunks at aligned addresses (a 15-slot request gets a 16-slot chunk), so the leftovers inside and between chunks are too small or misaligned for the next request.

The paper's three Orca baselines differ only in how much they reserve. Orca (Max) reserves the full 2048 tokens. Orca (Pow2) reserves at most twice the true output length (an output of 25 tokens gets 32 slots). Orca (Oracle) knows the true output length in advance and reserves exactly that; no real server can, so it is an upper bound on what length prediction could achieve.

Under Max, the two requests take the whole pool even when their outputs are short, and most of it is internal fragmentation that stays unused until they finish. Oracle removes internal fragmentation, but at step 0 nearly all of its reservation is still empty, and the buddy allocator's rounding still costs slots. Under the paged policy, each request holds at most one partly filled block, and the rest of the pool stays free.

The paper measured this breakdown for the three baselines and vLLM during its main experiment (Sec. 6.2, Fig. 2):

Orca (Max) stores token states in 20.4% of its KV memory, and 57.3% is internal fragmentation. Pow2 cuts internal fragmentation to 13.6% but loses 41.6% to the allocator. Even Oracle stores token states in only 38.2%: 25.2% is reservation and 36.6% is external fragmentation and other. Perfect length prediction would still leave about 62% of the memory without token states. vLLM stores token states in 96.3%.

Contiguous slabs also cannot share. When a user asks for several samples of one prompt, every sample needs the prompt's keys and values, and they are identical across samples; with one slab per sequence, the server stores the prompt's cache once per sample. The paper later measures up to 55% memory saved by sharing in beam search.

How PagedAttention works: paging the KV cache

Operating systems met the same problem with process memory. A process sees one contiguous range of virtual addresses. The OS splits that range into fixed-size pages, places each page in any free physical page frame of RAM, and keeps a per-process page table that translates one into the other. Frames are allocated when a page is first touched, freed when the process exits, and shared between processes when the contents are identical, as with a shared library. The idea goes back to the Atlas computer's one-level storage system (Kilburn et al., 1962).

vLLM applies the same design to the KV cache, with tokens in the role of bytes, KV blocks in the role of pages, and requests in the role of processes:

• At startup, the block engine on each GPU allocates one large region of GPU memory and divides it into physical KV blocks, each with room for the keys and values of $B$ tokens. The default is $B = 16$.
• Each request sees its cache as a list of logical KV blocks, filled left to right: tokens 1-16 in logical block 0, tokens 17-32 in block 1, and so on.
• A per-request block table maps each logical block to a physical block id and records how many of its $B$ slots are filled.
• A new physical block is taken from the free list only when the request's last block is full, and all of a request's blocks return to the free list when it finishes.

For OPT-13B, one 16-token block holds 16 × 800 KB = 12.5 MB of keys and values across all 40 layers, so the 12 GB budget is about 980 blocks. Paging bounds the waste: reservation and internal fragmentation can only occur in a request's last block, at most $B - 1$ slots (15 at the default size). A 499-token request fills 31 blocks and 3 slots of a 32nd, leaving 13 empty slots, 2.5% of its 512. External fragmentation disappears, because all blocks have the same size and any free block can serve any request.

A process's pages can sit anywhere in RAM because the CPU's memory hardware translates every address. Attention has no such hardware: a standard kernel reads a request's keys as one array, so the paper also needs a kernel that follows the block table, the subject of the next section.

The attention kernel over blocks

PagedAttention, the paper's name for this kernel, regroups equation (3) by block. With block size $B$, write $K_j$ for the keys of the $j$-th block, the $B$ vectors $k_{(j-1)B+1}, \dots, k_{jB}$, and $V_j$ for its values. Then $A_{ij}$, the length-$B$ row of weights that query $i$ puts on block $j$, and the output are

The exponential applies to each of the $B$ scores in the row $q_i^\top K_t$, and the all-ones vector $\mathbf{1}$ sums the $B$ results, so the denominator is the same sum of exponentials as in (3), grouped into $\lceil i/B \rceil$ blocks. (The paper prints $\mathbf{1}$ inside the exponential; the Provenance panel at the end explains why it belongs outside.) The output sums the same $a_{ij} v_j$ terms as (3), also grouped by block. Nothing is approximated, so the outputs match a contiguous kernel up to the order of floating-point additions, and model accuracy is unchanged.

A contiguous kernel computes (3) over one tensor per request:

# contiguous layout: request r's keys and values are one [len, d] tensor each
a = softmax(K[r] @ q / sqrt(d))          # [len] attention weights, eq (3)
o = a @ V[r]                             # [d] output for this decode step

The paged kernel loops over the block table and reads each block from its physical address. In the CUDA kernel of vLLM's first release, the work for one query and one attention head runs in two passes over the blocks, with one GPU warp (32 threads) reading each block. The first pass computes every score and keeps them in fast on-chip memory; the softmax runs over all of them at once; the second pass multiplies each block's values by its weights and adds them up. In Python-like form:

# paged layout: one decode step for request r (after vLLM v0.1.0's CUDA kernel)
# block_table[r] lists the physical block ids of r's KV cache, in logical order
scores = []
for j, phys in enumerate(block_table[r]):      # pass 1: scores, block by block
    n = min(B, ctx_len - j * B)                # the last block may be part-filled
    K_j = k_cache[phys][:n]                    # [n, d] keys, from wherever phys is
    scores += list(K_j @ q / sqrt(d))          # q.k / sqrt(d) per token
m = max(scores)                                # subtract the max so exp can't overflow
p = [exp(s - m) for s in scores]
a = [x / sum(p) for x in p]                    # the weights a_ij of eq (3), exactly
o = zeros(d)
for j, phys in enumerate(block_table[r]):      # pass 2: weighted sum of values
    n = min(B, ctx_len - j * B)
    V_j = v_cache[phys][:n]                    # [n, d] values
    o += a[j * B : j * B + n] @ V_j            # V_j A_ij^T, one term of eq (4)
return o

Take the paper's running example. The prompt is "Four score and seven years ago our", the model has generated "fathers brought", and the current token is "forth", position $i = 10$. With $B = 4$, its keys span ⌈10/4⌉ = 3 blocks: "Four score and seven", "years ago our fathers", and "brought forth" with two empty slots, which the kernel skips. The figure runs both passes on made-up scores and one-dimensional values, and compares the result with the contiguous formula.

Reading through the block table costs time. Section 7.1 measures the paged kernel at 20-26% higher latency than FasterTransformer's attention kernel, which it was adapted from. The paper lists three causes: reading the block table, extra branches, and handling requests of different lengths in one batch. Only the attention operator pays it; the matrix multiplies that dominate a step are untouched, and vLLM runs larger batches, so end-to-end throughput still rises. Section 5.1 lists the kernels written to keep the overhead down: the paged attention kernel itself, which reads blocks and computes attention in one fused kernel; a kernel that reshapes new keys and values and writes them into their blocks in one launch; and one that batches all the block copies of copy-on-write into a single launch.

The prompt phase does not use the paged kernel. It computes the prompt's keys and values with a conventional attention kernel, for which the paper cites FlashAttention as an example, and then stores them into blocks. FlashAttention reduces the memory and memory traffic of one attention call by tiling; PagedAttention manages where the cache lives between calls.

The block table during decoding

The paper walks through one request with $B = 4$ (Sec. 4.3, Fig. 6). The 7-token prompt needs two logical blocks, and the block manager maps them to physical blocks 7 and 1. Block 0 is full; block 1 holds 3 tokens and has one slot left. The first generated token, "fathers", takes that slot, and the table entry's fill count goes from 3 to 4. The next token, "brought", finds the last block full, so the manager takes physical block 3 from the free list and adds a third entry to the table.

Watch three things as you drag. Physical blocks are taken only when a token needs one, so a request that stops early never holds the blocks it would have used. The physical blocks need not be adjacent, because the kernel follows the table. And at most the last logical block has empty slots, between 1 and $B - 1$. With many requests running, their blocks interleave in the pool, and the scheduler sends each step's block tables to the GPUs together with the input tokens.

The block size sets a trade-off. Small blocks waste fewer slots per request, but each warp then reads only a few tokens per block and the kernel does more lookups. Large blocks keep the GPU busy, but a request's last block can be mostly empty, and two sequences can share only whole blocks, so a shared prefix that ends mid-block leaves that block unshared. Alpaca requests average 78 tokens, so a 256-token block leaves about 70% of each request's memory empty.

On ShareGPT, block sizes from 16 to 128 give the lowest latency. On Alpaca, 16 and 32 work well and larger blocks degrade quickly, because most sequences are shorter than one block. Sizes 1 to 4 are slow on both. The paper picks 16 as the default: large enough to keep the GPU busy, small enough that the last block wastes little on most workloads (Sec. 7.2).

On several GPUs the paper uses Megatron-LM-style tensor parallelism, where each GPU holds a subset of the attention heads. One KV cache manager in the central scheduler keeps the block tables for all of them. Every GPU uses the same physical block ids and stores only its own heads' keys and values in each block (Sec. 4.6).

Sharing blocks between sequences

Because a request reaches its cache only through block ids, two sequences can list the same physical block in their tables. vLLM gives every physical block a reference count, the number of logical blocks that point at it, and frees a block when its count reaches 0. The paper uses this for parallel sampling, beam search and shared prefixes.

Parallel sampling. A user asks for several completions of one prompt. vLLM computes the prompt's cache once and maps every sample's logical prompt blocks to the same physical blocks. The full blocks are only ever read, but the last prompt block usually has free slots, and each sample's first new token goes into it. vLLM uses copy-on-write, as an OS does for a shared page: when a sequence writes to a block with reference count above 1, vLLM allocates a new physical block, copies the contents into it, lowers the original's count by 1, and the write goes to the copy. The next writer finds a count of 1 and writes in place.

Whichever sample writes first gets the copy. In the paper's Fig. 8 that is sample A1, and A2 writes into the original. Either way at most one block is copied per sample, while the prompt's full blocks stay shared for the life of the request. On Alpaca with OPT-13B, sharing saves 6.1-9.8% of KV memory for 2 to 6 parallel samples (Sec. 6.3, Fig. 15).

Beam search. A beam of width $k$ keeps the $k$ most probable candidate sequences at each step, and candidates share long prefixes. In the paper's example with $k = 4$, all candidates share the prompt block, three of them share the next two blocks, and when two candidates drop out of the top 4, their blocks' counts fall and vLLM frees the blocks that reach 0. Earlier servers copied large parts of one candidate's cache into another's slab when the beam reshuffled; with shared blocks only the block being written is copied. Sharing saves 37.6-55.2% of KV memory for beam widths 2 to 6 on Alpaca, and 44.3-66.3% on ShareGPT.

Shared prefix. Many applications put the same instructions or few-shot examples in front of every prompt. The service provider computes the prefix's cache once and keeps its physical blocks reserved, like a shared library. A new request maps its first logical blocks to them, with the last of those blocks marked copy-on-write since the request's own tokens may continue it, and the prompt phase runs only on the user's part of the input.

The model and the kernel receive only a list of physical block ids per sequence, and the sharing patterns stay inside the block manager, so vLLM can batch requests with different decoding methods (plain sampling, parallel sampling, beam search) in one step.

Preemption: swap or recompute

Allocating on demand means the pool can run out partway through: every running request may need a new block in the same step. vLLM then preempts requests. Scheduling is first-come, first-served: the earliest arrivals are served first, and the latest arrivals are preempted first. Eviction is all-or-nothing per sequence, since a request needs its entire cache to compute the next token. The sequences of one request, such as the candidates of a beam, form a sequence group that is always preempted and rescheduled together, because they share blocks. While any preempted request is waiting, vLLM accepts no new requests.

A preempted request's blocks can be recovered in two ways:

• Swapping copies the blocks to CPU memory over PCIe, the CPU-GPU link, and copies them back when the request resumes. Because preempted requests block new admissions, the number of blocks on the CPU never exceeds the number of GPU blocks, which bounds the swap space.
• Recomputation discards the blocks. When the request resumes, its prompt and the tokens it has generated so far are concatenated into one new prompt, and a single prompt phase rebuilds the whole cache. Rebuilding 500 tokens this way costs one parallel pass, not 500 sequential steps.

The two modes trade differently against block size (Sec. 7.3, Fig. 19). Swapping moves one block per PCIe transfer, so small blocks mean many small transfers that use little of the PCIe bandwidth, and swapping is expensive at small block sizes. Recomputation does not touch the blocks, so its cost is the same for every block size. In the paper's microbenchmark, recomputation is never more than 20% slower than swapping, and for block sizes 16 to 64 the two give about the same end-to-end performance. The paper names no default. The v0.1.0 code recomputes requests with one sequence and swaps groups with several, because it had no way to recompute a group whose sequences share blocks.

Results: throughput, batch size and sharing

The evaluation serves OPT-13B on one A100, OPT-66B on four, OPT-175B (the size of GPT-3) on eight A100-80GB GPUs, and LLaMA-13B for the shared-prefix test. Requests come from ShareGPT conversations and the Alpaca instruction dataset; ShareGPT prompts are 8.4× longer and outputs 5.8× longer on average. Arrival times are random with a chosen average rate (a Poisson process). The metric is normalized latency, each request's end-to-end latency divided by its number of output tokens and averaged over requests, in seconds per token. A server that keeps up stays near a flat baseline; past the highest rate it can sustain, requests queue and the curve shoots up.

On ShareGPT, vLLM sustains 1.7-2.7× the request rate of Orca (Oracle) and 2.7-8× that of Orca (Max) at similar latency, across the three OPT sizes, and up to 22× that of FasterTransformer, which has no iteration-level scheduling (letting requests join and leave the batch at every step) and reserves memory like Orca (Max). The batch sizes behind it are in Fig. 13a, OPT-13B on ShareGPT at 2 requests per second: vLLM averages 30.42 requests in a batch, against 13.62 for Orca (Oracle), 9.81 for Pow2 and 7.00 for Max, so 2.2× Oracle's batch and 4.3× Max's. On Alpaca at 30 requests per second the averages are 132.44, 72.75, 43.24 and 7.00. The Alpaca results follow the same trend, except OPT-175B (Fig. 12f), where 264 GB of KV memory holds enough of Alpaca's short requests that the system is limited by compute, and vLLM's advantage over Oracle and Pow2 is smaller. On OPT-13B the traced Alpaca curves also put vLLM closer to Oracle than on ShareGPT, about 1.3× at 0.5 s/token in Figure 9.

Sharing adds to the gain. With OPT-13B on Alpaca, vLLM's throughput advantage over Orca (Oracle) grows from 1.3× with ordinary sampling to 2.3× with beam width 6. In the shared-prefix test, LLaMA-13B translates English to German (WMT16) behind a prefix of instructions and examples: with one 80-token example, vLLM reaches 1.67× the throughput of Orca (Oracle), and with five examples totalling 341 tokens, 3.58×. The paper does not split that gain between sharing the prefix's blocks and skipping its prompt computation. In a chatbot test, where prompts are cut to the last 1024 tokens of the conversation, vLLM sustains 2× the request rate of all three Orca variants, which all reserve 1024 output slots because of buddy-allocator rounding.

These numbers are for OPT and LLaMA models on A100s, against FasterTransformer and the authors' reimplementation of Orca as they stood in 2023. Iteration-level scheduling comes from Orca, and vLLM uses it too; the paper credits the gain over Orca to fitting more requests in memory. Serving systems built since have widely adopted paged KV caches, which is this page's observation, not a claim of the paper; a 2026 comparison would be against servers that already page.