PagedAttention: paging the KV cache

PagedAttention stores each sequence's KV cache in fixed-size blocks that can live anywhere in GPU memory, and gives each sequence a block table mapping its logical blocks to physical ones, exactly as an operating system maps virtual pages to physical frames. The attention kernel follows the table. Because memory is allocated one small block at a time as tokens arrive, almost nothing is reserved in advance or lost to fragmentation, and because several tables can point at the same physical block, sequences can share cache for common prefixes. The result is more sequences in flight on the same GPU and therefore higher throughput in the memory-bound decode phase. PagedAttention was introduced with the vLLM serving engine and is now the default cache layout in open-source serving. It does not make attention itself faster; it makes the memory around it usable.

The problem: reservation and fragmentation#

Decode throughput depends on batch size, and batch size is bounded by how many sequences' caches fit in memory (the roofline article derives $B_{\max }$). Before 2023, serving systems stored each request's cache as one contiguous tensor. Since the final length is unknown when a request arrives, they reserved space for the maximum possible length. That loses memory three ways, which Kwon et al. (2023) named: reserved slots for tokens not yet generated, internal fragmentation for tokens that will never be generated because the request stops early, and external fragmentation between differently sized reservations. Their profiling found that only 20.4 to 38.2% of cache memory in existing systems held actual token states. For OPT-13B, at 800 KB per token, one 2,048-token reservation is 1.6 GB, so a 40 GB GPU held only a few dozen requests even when most were short.

Iteration-level scheduling, introduced by Orca (Yu et al., 2022), made the problem sharper. Orca let requests join and leave the batch at every decode step instead of waiting for a whole batch to finish, which is the basis of continuous batching. Once the scheduler can admit a request at any step, the only thing stopping it is free memory, so wasted memory translates directly into lost batch slots.

Kwon, Li, Zhuang, Sheng, Zheng, Yu, Gonzalez, Zhang and Stoica (2023) borrowed the operating-system answer: paging. Their system, vLLM, reported 2 to 4 times higher throughput than FasterTransformer and Orca at the same latency, with larger gains for longer sequences, larger models and more complex decoding such as beam search.

How it works#

Fix a block size $b$ in tokens. A block holds the keys and values of $b$ consecutive tokens for one layer (implementations usually allocate a block across all layers or keep per-layer pools with shared indices). Physical memory is a pool of identical blocks managed by a free list. Each sequence owns a block table: entry $j$ is the physical id of its $j$-th logical block.

on admit(request):
    n_blocks = ceil(prompt_len / b)
    if free_blocks < n_blocks + watermark: keep request waiting
    table[request] = [allocate() for _ in range(n_blocks)]       # prefill writes into them

each decode step, for each running sequence s:
    if len(s) % b == 0:                 # last block is full
        if no free block: preempt some sequence (swap its blocks to CPU or free them for recompute)
        table[s].append(allocate())
    write k, v of the new token into slot len(s) % b of block table[s][-1]
    attention kernel: for j in table[s]: load K_j, V_j from physical block, accumulate

on finish(s): for blk in table[s]: decrement refcount; if 0, return to free list

Attention over a block table is the ordinary attention sum regrouped by block. With $K_j$ and $V_j$ the keys and values in block $j$ and $A_{ij}$ the row of attention weights for query $i$ over that block, the paper writes

The math is unchanged; only the addresses are indirect. The kernel reads the block table, gathers each block, and accumulates the softmax across blocks with the same running-maximum trick used by FlashAttention.

The memory accounting

With paging, a sequence of length $S$ occupies $b\lceil S/b\rceil$ slots, wasting at most $b-1$ and on average about $(b-1)/2$ tokens. With per-request reservation of $S_{\max }$, it wastes $S_{\max }-S$. Over a batch, the utilisation of allocated cache memory is

For a mean live length $\bar{S}=1,000$ tokens, $b=16$ and $S_{\max }=4,096$: $U_{\text{paged}}\ge 98.5\%$ against $U_{\text{reserve}}=24.4\%$. Since $B_{\max }$ is inversely proportional to the memory per sequence, the batch can grow by up to $U_{\text{paged}}/U_{\text{reserve}}$, about 4× here. Whether throughput grows by the same factor depends on the roofline, as the simulation below shows.

Sharing and copy-on-write

Blocks carry reference counts. When a request asks for several samples of the same prompt, all samples' tables point to the prompt's blocks; when a sample needs to write into a shared block that is not full, the engine copies that one block and remaps it, so at most one block per sample is ever duplicated. Beam search shares even more, because beams fork and die mid-generation and their common history stays shared. Kwon et al. measured 6.1 to 9.8% memory saving for parallel sampling and 37.6 to 55.2% for beam search on the Alpaca trace (16.2 to 30.5% for parallel sampling on ShareGPT), and the throughput gain over an oracle-reservation Orca grew from 1.3× for plain sampling to 2.3× for beam search with width 6. The same mechanism shares a system prompt across different requests, which grew into prefix caching.

When memory runs out

Allocating on demand means memory can run out mid-generation. vLLM then preempts whole sequences (all or none of a sequence's blocks) in first-come-first-served order and recovers them later in one of two ways. Swapping copies the evicted blocks to CPU memory and back. Recomputation discards them and later re-runs the prompt plus the already generated tokens as one prefill, which is efficient because prefill is compute-bound and fast per token. In the paper's measurements recomputation was more efficient for small blocks, swapping for large ones, and recomputation's overhead was never more than 20% above swapping's latency. Engines also keep a small watermark of free blocks at admission so that running sequences can grow without immediately triggering preemption.

Block size and kernel overhead#

Paging is not free. The kernel must read the block table and gather from scattered addresses, and a block that is too small makes those gathers inefficient. Kwon et al. measured attention kernel latency 20 to 26% higher than FasterTransformer's contiguous kernel, which they judged acceptable because attention is a fraction of total step time and the larger batch more than pays for it. Block size trades three things: small blocks waste less and share more finely; large blocks give longer contiguous reads and smaller tables. In their measurements block sizes from 16 to 128 worked best on ShareGPT, while on the shorter Alpaca requests block sizes above 32 degraded performance, so vLLM defaults to 16.

Later work questions whether the indirection belongs in the kernel at all. vAttention (Prabhu et al., 2024) keeps each sequence's cache contiguous in virtual memory and maps physical pages on demand with CUDA's virtual memory management APIs, so unmodified attention kernels can be used; it reports up to 1.23× higher serving throughput than paged kernels from FlashAttention and FlashInfer. In practice the major kernel libraries, including FlashAttention and FlashInfer (Ye et al., 2025), now support paged layouts natively, which has removed most of the original overhead.

Worked example by hand#

Three sequences are live with 37, 1,203 and 450 tokens, on Llama 3 8B (128 KiB per token), with a maximum length of 4,096.

Reservation. $3\times 4,096=12,288$ slots, 1.61 GB, holding 1,690 real tokens: 13.8% utilisation.

Paging with $b=16$. The sequences need $\lceil 37/16\rceil =3$, $\lceil 1203/16\rceil =76$ and $\lceil 450/16\rceil =29$ blocks: 108 blocks, 1,728 slots, 226 MB. Waste is 11, 13 and 14 slots, 38 in total, so utilisation is 97.8%.

What that buys. In 60 GB of cache, reservation fits $60\times 10^9/(4096\times 131,072)=111$ sequences regardless of their length. Paging fits as many as their actual lengths allow: at a mean of 563 tokens (this example's mean), about 800. Whether the scheduler can use 800 depends on latency targets, but the memory is no longer the limit.

Simulation: batch size doubles, throughput does not#

To see what paging does to throughput rather than to memory, we simulated an iteration-level scheduler serving 2,000 requests on Llama 3 8B with one H100's bandwidth (seeded numpy; prompts log-normal with median 584 and 95th percentile 2,155 tokens, outputs log-normal with mean 374 and 95th percentile 1,118, maximum length 4,096). Each decode step costs the roofline time $(16.06\text{ GB}+\text{live tokens}\times 131,072\text{ B})/3.35\text{ TB/s}$; prefill is ignored because it is identical across policies. We compared reserving 4,096 tokens per request, an oracle that reserves each request's exact final length, and paging with a 5% admission watermark.

With 60 GB of cache, reserving the maximum gave an average running batch of 79 sequences at 39.6% memory utilisation (close to the upper end of the 20.4 to 38.2% Kwon et al. measured) and 9,460 output tokens per second. Paging with 16-token blocks ran an average of 149 sequences at 99.6% utilisation and 12,894 tokens per second: 1.88× the batch but only 1.36× the throughput. The reason is in the step-time formula. At a batch of 149 with these lengths, cached tokens already cost more bytes per step than the weights, so each extra sequence lengthens the step. Paging moves the system up the flattening part of the throughput curve. With a 20 GB budget, where the batch is smaller and weights dominate the step, the same comparison gave 35 versus 87 sequences and 5,490 versus 9,933 tokens per second, a 1.81× gain. Paging pays most where memory is scarcest: big models on small GPUs, long contexts, many samples per prompt.

Two further results from the same simulation. Block size mattered little between 16 and 128 tokens (12,990 versus 12,886 tokens per second with no watermark) but 512-token blocks cut utilisation to 87% and throughput to 12,585. The measured mean end-of-sequence waste was 7.4, 15.3, 63.9 and 257 tokens for blocks of 16, 32, 128 and 512, matching $(b-1)/2$. And the admission watermark mattered for preemption: with no watermark the scheduler preempted 251 sequences and would have had to recompute 196,631 tokens, about 6.4 seconds of H100 prefill at 50% MFU against 57.5 seconds of decode; a 1% watermark cut that to 17 preemptions, and 5% removed them entirely for a 0.7% throughput cost.

Fine-tuned models and adapters#

Adapters share the pool. Serving many LoRA adapters on one base model adds a second variable-size tenant to GPU memory: adapter weights of different ranks. S-LoRA (Sheng et al., 2023) extends paging to both, keeping adapter weights and KV blocks in one unified pool, and reports up to 4× throughput over naive multi-adapter serving and orders of magnitude more adapters per GPU. See multi-LoRA serving.

Shared blocks must come from the same weights. Copy-on-write sharing is safe among samples of the same request because they share a model. Across requests, a block computed under one adapter cannot be mapped into a sequence using another; prefix-sharing hashes include the adapter identity for this reason.

Output length drives preemption. Models trained with RL to reason at length, or fine-tunes that lost their stop behaviour, produce outputs far longer than the prompt. On-demand allocation keeps admitting requests based on their prompts, then runs out of blocks as outputs grow. If preemption counts rise after deploying a new fine-tune, compare its output-length distribution with the previous model before touching engine settings.

Quantised caches double the blocks. An FP8 cache halves the bytes per block, so the same memory holds twice as many blocks; nothing else about paging changes. See KV cache compression.

Tuning knobs#

Failure modes#

Preemption thrash. Sequences are repeatedly evicted and recomputed; GPU utilisation looks high but completed requests per second fall and TTFT for resumed requests spikes. Watch the engine's preemption counter. Raise the watermark, cap concurrency, or cap maximum output length.

Expecting a throughput miracle from a memory fix. Paging raises the batch, and throughput follows only while weight reads dominate step time, as the simulation showed. If the cache already dominates, the next lever is fewer bytes per token (FP8 cache, GQA models), not more sequences.

Kernel fallbacks. Some attention backends support paging only for certain head sizes, dtypes or block sizes, and fall back to slower paths otherwise. A model with an unusual head dimension, or a custom architecture produced by post-training surgery, can silently run a much slower kernel. Compare kernel times in a profile against a standard model of similar size.

Memory budget surprises. The pool is sized at start-up from free memory after weights and a profiling pass. Anything allocated later, such as a large adapter set, longer sampling buffers, or another process on the GPU, can cause out-of-memory errors that look unrelated to the cache. Leave headroom when adapters are loaded dynamically.

When it helps and what else to use#

Minimal implementation#

A block allocator and a gather-based reference attention show the whole mechanism. Production kernels do the gather inside the attention kernel instead of materialising it.

import torch, math

class BlockPool:
    def __init__(self, n_blocks, block, layers, kv_heads, head_dim, dtype=torch.bfloat16, device="cuda"):
        self.k = torch.empty(layers, n_blocks, block, kv_heads, head_dim, dtype=dtype, device=device)
        self.v = torch.empty_like(self.k)
        self.free = list(range(n_blocks)); self.ref = [0] * n_blocks; self.block = block
    def alloc(self):
        if not self.free: raise MemoryError("preempt a sequence")
        i = self.free.pop(); self.ref[i] = 1; return i
    def share(self, i): self.ref[i] += 1; return i
    def release(self, i):
        self.ref[i] -= 1
        if self.ref[i] == 0: self.free.append(i)

class Sequence:
    def __init__(self, pool): self.pool, self.table, self.len = pool, [], 0
    def fork(self):                                    # parallel sampling: share every block
        s = Sequence(self.pool); s.table = [self.pool.share(i) for i in self.table]; s.len = self.len; return s
    def append(self, k, v):                            # k, v: (layers, kv_heads, head_dim) for one token
        p, b = self.pool, self.pool.block
        if self.len % b == 0:
            self.table.append(p.alloc())
        elif p.ref[self.table[-1]] > 1:                # copy-on-write on a shared partial block
            old, new = self.table[-1], p.alloc()
            p.k[:, new], p.v[:, new] = p.k[:, old], p.v[:, old]
            p.release(old); self.table[-1] = new
        blk, slot = self.table[-1], self.len % b
        p.k[:, blk, slot], p.v[:, blk, slot] = k, v
        self.len += 1

def paged_attention(q, seq, layer):                    # q: (q_heads, head_dim), one decode token
    p = seq.pool; idx = torch.tensor(seq.table, device=q.device)
    K = p.k[layer, idx].flatten(0, 1)[: seq.len]      # gather blocks -> (len, kv_heads, head_dim)
    V = p.v[layer, idx].flatten(0, 1)[: seq.len]
    g = q.shape[0] // K.shape[1]
    K, V = K.repeat_interleave(g, 1), V.repeat_interleave(g, 1)
    w = torch.einsum("hd,shd->hs", q, K).div(math.sqrt(q.shape[-1])).softmax(-1)
    return torch.einsum("hs,shd->hd", w, V)

In vLLM the equivalent settings are the block size, the GPU memory utilisation fraction and the swap space; SGLang and TensorRT-LLM expose the same ideas with different names. In POFE, evaluation runs for sampling-heavy recipes such as best-of-n use a paged engine for exactly the copy-on-write reason above.

Further reading#

Kwon et al. (2023) is the PagedAttention and vLLM paper; its sections on fragmentation, sharing and the block-size and recomputation ablations are the source of the numbers here. Yu et al. (2022), Orca, introduced iteration-level scheduling, which is what made dynamic allocation essential. Prabhu et al. (2024), vAttention, argues for virtual-memory contiguity instead of paged kernels. Ye et al. (2025), FlashInfer, describes block-sparse and paged layouts inside a general attention engine. Sheng et al. (2023), S-LoRA, extends paging to adapter weights. Continue with prefix caching, which turns block sharing into a cache across requests.

Frequently asked questions#

References#

1. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, Ion Stoica (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention. arxiv.org/abs/2309.06180
2. Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, Byung-Gon Chun (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models. www.usenix.org/conference/osdi22/presentation/yu
3. Ramya Prabhu, Ajay Nayak, Jayashree Mohan, Ramachandran Ramjee, Ashish Panwar (2024). vAttention: Dynamic Memory Management for Serving LLMs without PagedAttention. arxiv.org/abs/2405.04437
4. Zihao Ye, Lequn Chen, Ruihang Lai, Wuwei Lin, Yineng Zhang, Stephanie Wang, Tianqi Chen, Baris Kasikci, Vinod Grover, Arvind Krishnamurthy, Luis Ceze (2025). FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving. arxiv.org/abs/2501.01005
5. Ying Sheng, Shiyi Cao, Dacheng Li, Coleman Hooper, Nicholas Lee, Shuo Yang, Christopher Chou, Banghua Zhu, Lianmin Zheng, Kurt Keutzer, Joseph E. Gonzalez, Ion Stoica (2023). S-LoRA: Serving Thousands of Concurrent LoRA Adapters. arxiv.org/abs/2311.03285
6. Llama Team, AI @ Meta (Aaron Grattafiori, Abhimanyu Dubey, et al.) (2024). The Llama 3 Herd of Models. arxiv.org/abs/2407.21783

Related reading