Efficient Memory Management for Large Language Model Serving with PagedAttention

The KV cache as pages, like an operating system.

An LLM serving system’s throughput is set by how many requests share the GPU’s memory at once. PagedAttention lays the KV cache out the way an operating system lays out RAM, fixed-size blocks plus a translation table, and packs roughly 96% of the reserved memory with real data instead of 20-38%.

Serving a large language model cheaply is a memory-allocator problem before it is a kernel problem, and the allocator most servers ship is sixty years behind the operating systems they run on.

A served language model spends most of its life decoding one token at a time. Per request, the work is tiny: a few dozen matrix-vector products that read the model weights and the request’s key-value cache, and emit a single integer. The model weights are the same for every request, so once they are loaded the GPU is mostly waiting on memory rather than running out of arithmetic. The only way to get more throughput is to run more requests in parallel and amortize that weight load.

But each in-flight request carries its own state. For a Transformer that state is the KV cache: the keys and values produced by every previous token, stored so the next token’s attention can read them without recomputing. On OPT-13B a single token of KV cache is about 800 KB (2 for K and V, times 5120 for the hidden width, times 40 layers, times 2 bytes for fp16); a 2048-token sequence is 1.6 GB. Pile up enough requests and KV cache, not weights, decides the batch size.

PagedAttention, out of UC Berkeley, makes one simple observation. Existing LLM servers store the KV cache the way a deep-learning framework stores any tensor, a single contiguous slab per request, and that layout wastes most of the slab. Borrow virtual memory and paging from operating systems, store the cache in non-contiguous fixed-size blocks, and you reclaim almost all of it. The system they build on top, vLLM, runs OPT and LLaMA at 2 to 4 times the throughput of the previous best, on the same hardware, with the same accuracy.

What follows works through why the KV cache dominates GPU memory, what the contiguous layout actually wastes, how paging maps onto attention, and what the resulting packing buys in throughput. The interactive figures run a small worked example for each piece so the claims stop being slogans.

The KV cache sets the batch size

The attention layer is the thing that ties tokens together. For an input position $i$ with hidden state $x_i$, the layer first projects three linear views, the query, key, and value:

The output at position $i$ is a softmax-weighted average over the value vectors at every earlier position:

That dependence on every earlier $k_j$ and $v_j$ is what makes the KV cache load-bearing. Generation runs in two phases. The prompt phase sees the whole input at once and produces all the prompt’s K and V vectors in a single matrix-matrix multiply, fast on a GPU. The generation phase then takes one token, computes its lone new $k$ and $v$, appends them to the cache, and runs equation (3) against the entire cache to produce one output. Then a new token. Then another. Each step is a thin matrix-vector product against a growing pile of bytes, which is why decoding is memory-bound: the arithmetic is small, the read is big.

For batching purposes the relevant number is the KV bytes per token, per layer. On OPT-13B that is $2 \times 5120 \times 2 = 20{,}480$ bytes per layer per token, multiplied by 40 layers to give about 800 KB per token; on a 2048-token sequence that grows to 1.6 GB. An A100 with 40 GB and 26 GB of weights leaves about 12 GB for KV, room for only a handful of full-length requests at once. The figure below holds one request and lets you walk it forward token by token, so you can feel how the read this step grows in lockstep with the cache. Watch the cache row stretch and the bottom bar grow: the work per step is exactly this much memory traffic, every step.

The KV cache problem is the canonical memory bottleneck of LLM serving, and it is the same fact that motivates two sibling lines of work this site covers. The closest neighbor is multi-query attention, which cuts the cache itself by sharing one set of keys and values across heads (and grouped-query attention in the Mistral page is the modern compromise). PagedAttention takes the opposite angle: leave the cache the size it is, and lay it out so almost none of the reserved bytes are wasted.

Three shapes of waste

Why does the old layout waste anything? Because to make attention legal, deep-learning frameworks expect a tensor to live in one contiguous span of memory, and the server does not know up front how long a request will be. Prior servers (FasterTransformer, Orca) handled the unknown length by allocating, at request arrival, a contiguous slab big enough for the worst case: the model’s maximum sequence length, 2048 tokens for OPT. Then the request runs and only a fraction of the slab ever fills.

That leaves three distinct chunks of dead memory, and the figure below makes them visible. Drag either request’s length and watch the bands shift:

The three names pin down distinct things: reservation is space the request will use eventually but has not filled yet, internal fragmentation is space inside the request’s slab that it will never fill (its actual output came in shorter than 2048), and external fragmentation is space between requests that the allocator could not pack tightly because the slabs come in different sizes. The paper measures all three across four systems on the ShareGPT trace and lays them out in figure 2 of the paper, which we redraw next.

Notice what the Oracle row implies. Even if a server somehow knew, at request arrival, exactly how many tokens each request would generate, the contiguous layout would still waste 60% of the KV memory. The allocator can only hand out slabs in sizes it can place contiguously, so even perfect length prediction cannot pack a heterogeneous workload. Allocation, not prediction, is the problem.

One more thing the contiguous layout cannot do: share. When two output samples from the same prompt would naturally use identical K and V vectors for the prompt portion, two contiguous slabs cannot point at the same bytes. The KV cache for the prompt gets duplicated per sample. This costs more than it sounds; the paper later measures up to 55% memory savings from sharing in beam search, savings the old layout simply cannot collect.

Borrow paging from the operating system

The paper notices that this is a problem operating systems already solved, sixty years ago. A process running in an OS does not get a single contiguous block of physical RAM. Its memory is split into fixed-size pages, each page lives wherever the OS decides to put it, and a per-process page table translates the program’s contiguous-looking virtual addresses into the scattered physical ones. Pages are allocated lazily, freed when the process is done with them, and shared between processes when the contents are identical (think a shared library). That machinery exists because OS designers, like LLM servers, had to manage many processes’ unpredictable memory in a fixed pool, and the contiguous layout broke for the same reasons.

PagedAttention transplants that machinery. A request’s KV cache becomes a list of fixed-size KV blocks; each block holds the K and V vectors for some small number of tokens (the paper picks 16 by default). The sequence sees a contiguous list of logical KV blocks; the GPU’s KV pool holds physical KV blocks at scattered addresses; a block table per request maps logical to physical. New blocks are allocated only when the sequence’s last logical block is full and a new token needs space. Internal fragmentation drops to at most one block per request. External fragmentation disappears entirely, because every block is the same size and any free block fits any new allocation. The vocabulary translates cleanly: tokens are bytes, KV blocks are pages, requests are processes.

The translation buys two things at once. First, the memory accounting: the wasted bytes go away because allocation is on-demand and uniform. Second, sharing: because a physical block is identified by an address and a reference count, two logical blocks (in different sequences) can point at the same physical block as long as nobody writes into it. That read-only sharing is what makes parallel sampling and beam search efficient, and the copy-on-write section below works through how a write is handled when sharing breaks.

PagedAttention: read the scattered blocks

Scattering the KV cache across blocks would normally break the attention kernel, which assumes its K and V tensors are contiguous so it can load them with one wide read. The paper’s name comes from the kernel change that makes the scattered layout legal. Equation (3) is rewritten over blocks:

Read the symbols slowly. The block size is $B$, the count of blocks already filled for the query at position $i$ is $\lceil i/B \rceil$, and $K_j = (k_{(j-1)B+1}, \dots, k_{jB})$ is the K matrix stacking the keys for the $j$-th block. $A_{ij}$ is the row of attention weights this query puts on block $j$, a length-$B$ vector. Equation (4) does the same mathematics as equation (3); it just groups the sum by block instead of by token, so the kernel can fetch one K block from its physical address, compute the partial scores, fetch the next, and so on.

The denominator is the only part that needs care. A softmax’s normalizer is a global sum over every score, so the kernel cannot finish the denominator until it has seen every block. The same running-max trick that powers FlashAttention works here: keep a running maximum and a running denominator, rescale the partial output every time the maximum bumps up. The output equals the contiguous-kernel result up to floating-point summation order, which is what the paper means by "no accuracy change."

The figure below shows one step of decoding in motion. The query is at the bottom; three of the request’s KV blocks live at scattered addresses in the physical pool above; the kernel walks the block table, fetches each block in turn, and folds its contribution into the running output:

What changes about the kernel’s real work? Three things. The block table costs an extra indirection per block: the kernel reads where to go before reading what to compute. The kernel also has to handle blocks of varying validity (the last block may be partly empty), and it can no longer do a single large stride load because the addresses change between blocks. Section 7.1 measures the total cost: a 20 to 26% slower attention kernel than the highly-tuned FasterTransformer baseline. That overhead is real, and it is the price of the layout. The end-to-end throughput improvement comes from packing more requests in, not from the attention being faster per call.

For grounding, here is the contiguous kernel that this replaces, and the paged version side by side, so the block-table loop is visible:

# attention with a contiguous K, V (the old way)
S = (q @ K.T) / sqrt(d)            # K shape: [seq_len, d]; q: [d]
A = softmax(S)                     # one row, all seq_len entries
o = A @ V                          # V shape: [seq_len, d]; o: [d]

# attention over BLOCKWISE K, V at non-contiguous addresses (eq 4)
o = zeros(d)                       # accumulator for this query token
denom = 0                          # running softmax denominator
m = -inf                           # running row-max for numeric safety
for j in block_table[req]:         # walk the LOGICAL blocks in order
    K_j, V_j = pool[j]             # fetch block j from wherever it sits
    s = (q @ K_j.T) / sqrt(d)      # [B] scores against this block
    m_new = max(m, max(s))
    p = exp(s - m_new)             # local softmax weights
    rescale = exp(m - m_new)
    o = rescale * o + p @ V_j      # fold in this block's contribution
    denom = rescale * denom + sum(p)
    m = m_new
return o / denom                   # exact softmax-weighted output

The block table, step by step

The block table is one list per request, of the same length as that request’s logical block count, mapping each logical index to a physical block id plus a fill counter (how many of the block’s $B$ token slots are written). Allocation rule: when a new token arrives and the last logical block has room, write into that block and bump its counter; when it is full, grab a fresh physical block from the pool’s free list and append a new logical entry to the table. Free rule: when the request finishes, return all its physical blocks to the pool.

The figure shows it running on a small example. The block size is 4, the prompt is "Four score and seven years ago our" (7 tokens), and the model decodes more tokens one at a time. Drag the decode step and watch the block table grow on the right and the new mappings fall into the pool’s scattered cells:

Three properties to notice as you drag. One, the pool fills only as the request needs space; if a request ends at 7 tokens it never reserves a 9th block. Two, the physical blocks the request uses are scattered; there is no attempt to keep them adjacent, because adjacency does not buy anything once equation (4) tolerates the indirection. Three, the last logical block is almost always partly empty (between 1 and $B-1$ wasted slots), so internal fragmentation drops to at most one block per request, a few percent at $B = 16$ for sequences of even modest length.

That bound is the reason the choice of block size matters. Small $B$ means almost no internal waste but more block-table entries to manage and more kernel calls per attention step. Large $B$ means fewer calls but more wasted space in the last block, and worse, less opportunity for sharing across sequences (two sequences with a shared prefix that splits mid-block cannot share the split block at all). The paper sweeps it in §7.2 and settles on $B = 16$: large enough for the kernel to do useful work per call, small enough that the partly-empty tail and the un-shareable split-block hits are both modest.

Sharing: copy-on-write across sequences

Once the KV cache is a list of pointers, the layout permits something the contiguous version cannot do: two logical blocks, in different sequences, can point at the same physical block. The paper uses this in three settings that all look the same once you frame them as block-table tricks.

The simplest is parallel sampling: a user sends a single prompt and asks for several different samples. Standard practice is to run the prompt phase once and then fork the model’s state into$n$ sequences that diverge as each samples its own next token. With contiguous slabs the prompt’s KV cache has to be duplicated $n$ times; with paged blocks each sample’s logical blocks for the prompt portion point at the same physical blocks, with a reference count tracking how many sequences share each one.

Diverging at the next-token boundary is fine if it falls on a block boundary, because the new token wants a fresh block anyway. But almost never does it. The last prompt block is usually partly empty, so the first generated token wants to write into a block that other samples are still reading. That is exactly the case virtual-memory systems solved with copy-on-write: the system intercepts the write, allocates a fresh physical block, copies the existing bytes into it, drops the reference count on the original, and redirects the writing sample’s logical pointer to the new copy. The other samples keep their reference to the original.

Beam search plays the same copy-on-write pattern out in a tree. A width-$k$ beam keeps the $k$ most probable candidate sequences at every step; many of them share long prefixes, and the prefixes drift apart and re-converge as candidates rise and fall. Section 4.4 details a beam-search example where the candidates form a directed graph of shared physical blocks, joined where the candidates agree and split where they differ, with the same copy-on-write rule whenever a write needs to land in a shared cell. The paper measures 37.6 to 55.2% memory saved on Alpaca traces from this single mechanism.

A subtler case is the shared prefix, an instruction or few-shot example glued to the front of every request in a workload. With paging, the server pre-computes the prefix’s KV blocks once and gives every arriving request a block table that starts with pointers to those frozen blocks (marked copy-on-write so nobody clobbers them). The translation example from §6.4 measures a 3.58x throughput improvement over Orca (Oracle) with a 5-shot, 341-token prefix, almost entirely from not recomputing the prefix’s KV cache for every request.

Preemption: when the pool runs out

Even with denser packing, the GPU’s KV pool is finite, so requests eventually saturate it. Two questions show up: which request to evict, and what to do with its blocks. vLLM’s scheduler is first-come-first-served and evicts the most recently arrived request first (so earlier requests are preserved). On the recovery side it offers two options and the paper measures both.

Swapping follows the classical OS recipe: copy the evicted blocks to host RAM through PCIe and copy them back when the request resumes. Recomputation throws the blocks away and regenerates them by replaying the prompt phase when the request restarts; this only works for KV cache, because the prompt is still available and the model is deterministic given the prompt, so a fresh prompt phase reconstructs the same K and V vectors. The two methods trade differently against block size. Recompute is roughly constant in block size (its cost is the prompt-phase compute), while swap gets cheaper with bigger blocks (one PCIe round-trip per block, so fewer trips with larger blocks). At the paper’s default $B = 16$ they sit within a few percent of each other on the OPT-13B ShareGPT trace (§7.3), so vLLM ships swapping but the choice is workload-dependent.

One eviction detail matters in practice: vLLM evicts at the granularity of a sequence group, not an individual block, because the sequences inside a group (parallel samples, beam candidates) share blocks. If you evict one candidate’s logical block without evicting its siblings, the reference count on the underlying physical block goes nowhere and no memory is freed. The scheduler kicks out a whole request’s family at once.

What the packing buys

The headline measurement, figure 12a in the paper, is normalized latency (seconds per generated token, averaged over requests) against request rate on OPT-13B and ShareGPT. Each system runs flat at low load and then knees upward as the in-flight set saturates GPU memory. vLLM’s knee sits 2 to 3 times further to the right than the best Orca variant; the same A100 holds more requests at any given latency target.

Same hardware, same model, same accuracy. The lift comes from running more requests at once: figure 13a in the paper measures the average concurrent batch as 30.4 for vLLM versus 7.0 to 13.6 for Orca, a 2.2 to 4.3 times wider batch. Throughput is essentially batch size, once each request is compute-cheap.

The improvement compounds in workloads that share KV cache. Parallel sampling at $n=6$ brings 6.1 to 9.8% raw memory savings from prompt sharing; beam search at $k=6$ brings 37.6 to 55.2%. The beam-search throughput lift over Orca (Oracle) goes from 1.3x in basic sampling to 2.3x at beam width 6. And the shared-prefix translation workload, where the prefix changes once per workload but each request’s inputs differ, hits 3.58x over Orca (Oracle) at a 5-shot, 341-token prefix. The longer the prefix, the more the old layout had to duplicate, and the more paging recovers.

Two limits to be exact about. First, the attention kernel itself is 20-26% slower per call (§7.1), so vLLM breaks even or loses on workloads where the GPU memory already comfortably holds the batch. Figure 12f, OPT-175B on Alpaca with 8 A100-80GBs, shows the curves converging because there is enough KV memory that even Orca (Pow2) can hold a deep batch. Second, the throughput claim is against the 2023 baselines (Orca, FasterTransformer); newer serving systems have since picked up paged management as a default, so the appropriate baseline today is "any modern serving system" rather than the original Orca. The paper’s lasting contribution is the layout idea, not the absolute 2-4x against those particular baselines.

Read at a distance, the paper takes an unsolved scheduling problem in LLM serving, notices it has the exact shape of an operating-system problem from the 1960s, and ports the solution across with the right amount of LLM-specific care: the all-or-nothing sequence-group eviction, the recompute fallback that swapping does not have access to, the kernel rewrite to tolerate non-contiguous blocks. It sits beside two siblings on the same cache. Multi-query attention shrinks the cache by sharing keys and values across heads. FlashAttention keeps a single call’s working set on chip. PagedAttention manages the long-lived cache across calls. Modern serving systems run all three at once, which is why a fresh draft of the same problem looks nothing like the 2023 baselines vLLM was measured against.