PagedAttention

PagedAttention is the memory-management technique behind vLLM and most modern LLM serving engines. Instead of reserving one large contiguous buffer per request for its KV cache, it stores the cache in small fixed-size blocks that can sit anywhere in GPU memory, and keeps a per-request table that maps the sequence’s logical positions to those physical blocks, the same trick an operating system plays with virtual memory pages. Introduced by Kwon et al. in 2023, it removed the fragmentation that used to waste most of the KV cache and is a large part of why a single GPU can now serve several times more concurrent requests than it could before.

The Problem: Most of the KV Cache Was Empty Space

Serving throughput is set by batch size. Decoding is memory-bandwidth bound, so the more requests a GPU can decode together, the more work each pass over the weights accomplishes. Batch size, in turn, is capped by how many requests’ KV caches fit in memory, and those caches are big. For OPT-13B, the PagedAttention paper works out that one token’s cache takes 800 KB (2 for keys and values, times a hidden size of 5,120, times 40 layers, times 2 bytes in fp16), so a single 2,048-token request can need as much as 1.6 GB.

The trouble is that nobody knows a request’s final length when it arrives. Before PagedAttention, serving systems stored each request’s cache in one contiguous tensor and, to be safe, sized it for the maximum possible length. That produces three kinds of waste:

• Reservation: slots held for tokens that will be generated later sit empty for the request’s whole lifetime.
• Internal fragmentation: the request finishes at 300 tokens but reserved 2,048, and the unused tail is stranded.
• External fragmentation: buffers of different sizes are allocated and freed, leaving gaps between them that no new buffer fits into.

The paper measured how bad this was: in the existing systems it profiled, only 20.4% to 38.2% of KV cache memory held actual token states. The remaining 61.8% to 79.6% was overhead. Since KV memory bounds batch size and batch size bounds throughput, that waste translated directly into lost throughput. There was a second cost too: contiguous buffers cannot be shared, so generating four candidate replies to one prompt meant storing the prompt’s cache four times.

%%{init: {'theme': 'base'}}%%
graph LR
    classDef default fill:#ffffff,stroke:#4338CA,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef data    fill:#EEF0F7,stroke:#0D9488,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef process fill:#F7F8FC,stroke:#6366F1,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef output  fill:#4338CA,stroke:#4338CA,stroke-width:2px,color:#ffffff,rx:8px,ry:8px;

    subgraph Static["Static allocation (before)"]
        S1[Request arrives, length unknown]:::process --> S2[Reserve one contiguous buffer sized to max length]:::process
        S2 --> S3[Buffer: filled part plus a large empty reserved tail]:::data
        S3 --> S4[Gaps between buffers: external fragmentation]:::data
    end

    subgraph Paged["PagedAttention (after)"]
        P1[Request arrives]:::process --> P2[Allocate one small block]:::process
        P2 --> P3[Block fills up, allocate another anywhere in the pool]:::process
        P3 --> P4[Block table maps logical order to physical blocks]:::output
    end

The Idea: Virtual Memory for the KV Cache

PagedAttention borrows the operating system’s answer to the same problem. A process sees a clean contiguous address space while the OS quietly backs it with scattered physical pages, and a page table translates between the two. PagedAttention does this for the KV cache:

1. The cache is divided into blocks, each holding the keys and values for a fixed number of tokens (16 by default in vLLM).
2. A request’s sequence is a list of logical blocks, in order. Each is mapped, through that request’s block table, to a physical block somewhere in one shared pool. The paper describes each table entry as recording the corresponding physical block and the number of filled positions in it.
3. Blocks are allocated on demand: a new one is taken from the pool only when the current one fills up.
4. The attention kernel is given the block table and gathers keys and values from the scattered blocks, using pointer arithmetic on the physical block number, instead of reading one contiguous range.

Because blocks are allocated only as tokens arrive, the only memory a request can waste is the unfilled tail of its last block, at most block_size - 1 token slots. Because any free block will do, there is no external fragmentation at all. That is how the paper reaches “near-zero waste”: it bounds a request’s waste to a single block.

The whole mechanism is small enough to sketch in plain Python. This toy manager keeps a pool of physical block ids, a block table per sequence, and a reference count per block (which the next section needs):

# Scenario: the bookkeeping a paged KV cache does, reduced to plain Python.
# It tracks only which physical blocks belong to which sequence; a real engine
# stores the actual K/V tensors in those blocks on the GPU.
BLOCK_SIZE = 16

class BlockManager:
    def __init__(self, num_physical_blocks):
        self.free = list(range(num_physical_blocks))  # pool of physical block ids
        self.ref = {}                                 # physical block id -> reference count
        self.tables = {}                              # sequence id -> block table (list of block ids)
        self.lengths = {}                             # sequence id -> tokens stored

    def append_token(self, seq):
        n = self.lengths.get(seq, 0)
        table = self.tables.setdefault(seq, [])
        if n % BLOCK_SIZE == 0:                       # last block full (or first token): take a new one
            block = self.free.pop()
            self.ref[block] = 1
            table.append(block)
        elif self.ref[table[-1]] > 1:                 # partial block shared with another sequence
            self.ref[table[-1]] -= 1                  # copy-on-write: this sequence gets its own copy
            new = self.free.pop()
            self.ref[new] = 1
            table[-1] = new
        self.lengths[seq] = n + 1

    def fork(self, parent, child):                    # parallel sampling: share every block, copy nothing
        self.tables[child] = list(self.tables[parent])
        self.lengths[child] = self.lengths[parent]
        for b in self.tables[child]:
            self.ref[b] += 1

    def free_seq(self, seq):                          # blocks return to the pool when no one references them
        for b in self.tables.pop(seq):
            self.ref[b] -= 1
            if self.ref[b] == 0:
                self.free.append(b)
        del self.lengths[seq]

Interactive: How Block Size Trades Waste Against Bookkeeping

Block size is the one tunable in the design, and it pulls in two directions. Small blocks keep the wasted tail tiny and let requests share at fine granularity, but they mean more block-table entries and more indirection for the attention kernel to chase. Large blocks make the kernel’s memory reads more regular, but strand up to a block’s worth of slots per request and only let requests share whole blocks. The widget below models the capacity side: how many concurrent requests fit in a fixed KV budget under a static max-length allocator versus a paged one.

Set the typical request length to 512 tokens against an 8,192-token max and the static allocator is stranding 94% of every reservation, while the paged cache fits many times more requests in the same budget. Now pull the typical length up toward the max and the gap closes, because there is nothing left to waste. Then push the block size to 256 and watch the smallest shareable unit grow with it: capacity at the default settings drops by roughly a tenth, and every request now strands up to 255 slots and can only share prefixes in 256-token pieces. That asymmetry is why 16 is the default and why the paper’s ablation found block sizes from 16 to 128 performing best on ShareGPT, with smaller sizes better on shorter-sequence workloads. The model is deliberately simple (uniformly distributed unfilled tails, one request length, no weights or activations in the budget), so read it as the shape of the trade-off rather than a benchmark.

Sharing and Copy-on-Write

Paging does more than remove waste. Once a sequence is a list of block pointers, sharing memory between sequences is just two lists pointing at the same physical block. The paper uses this for three cases:

• Parallel sampling: several outputs from one prompt share every prompt block. Each block carries a reference count, and when one sample needs to write into a block that others still reference, it gets a private copy first (copy-on-write). Reported memory savings were 16.2% to 30.5% on ShareGPT and 6.1% to 9.8% on Alpaca.
• Beam search: candidate beams share their common history and diverge only where they differ, with savings of 44.3% to 66.3% on ShareGPT and 37.6% to 55.2% on Alpaca, since beams overlap far more than independent samples do.
• Shared prefixes: requests that begin with the same system prompt or few-shot examples can point at the same physical blocks. This is the seed of prefix caching, which turns block sharing from a within-request trick into a cross-request one.

Running the toy manager from earlier shows the effect. Prefill a 1,000-token prompt, fork three siblings, and let all four sequences generate 200 tokens:

# Scenario: four candidate replies to one 1,000-token prompt, each generating
# 200 more tokens. Compare physical blocks used with and without sharing.
mgr = BlockManager(num_physical_blocks=1000)
for _ in range(1000):
    mgr.append_token("s0")                # prefill the prompt once
for i in (1, 2, 3):
    mgr.fork("s0", f"s{i}")               # three siblings share every prompt block
for seq in ("s0", "s1", "s2", "s3"):
    for _ in range(200):
        mgr.append_token(seq)             # each diverges; the partial block is copied once

print(1000 - len(mgr.free))               # 114 physical blocks in use
print(4 * -(-1200 // 16))                 # 300 blocks if every sample stored its own copy

The four samples share 62 full prompt blocks and each owns 13 more of its own (the copied partial block plus its new tokens), so 114 blocks against 300 unshared. The savings grow with the prompt-to-output ratio, which is exactly why long-prompt workloads like RAG and document analysis benefit most.

Running Out of Blocks: Preemption

Because blocks are allocated on demand, the pool can run dry while requests are mid-generation, and the engine has to make room. The paper’s scheduler serves requests first-come-first-served and, when memory runs out, preempts the latest arrivals. Because a sequence’s blocks are all needed together to produce its next token, eviction is all-or-nothing: either all of a sequence’s blocks are evicted or none of them are. There are two ways to get the state back later:

• Swapping: copy the evicted blocks to CPU memory and copy them back when the request resumes.
• Recomputation: discard the blocks and re-run prefill over the prompt plus the tokens generated so far when the request resumes. The paper found recomputation overhead is never higher than 20% of swapping’s latency, and unlike swapping it does not get worse as blocks get smaller.

In practice, frequent preemption is a signal that you are over-admitting: too many concurrent sequences for the block pool. The fixes are the ones the capacity math suggests: a lower cap on concurrent sequences, a shorter max_model_len, a smaller or quantized KV cache (see KV cache optimization), or more memory.

What PagedAttention Does Not Do

It is easy to over-credit paging, so it helps to be precise about its scope. PagedAttention does not shrink the KV cache: a token’s keys and values take exactly as many bytes as before, and shrinking them is the job of grouped-query attention, latent-attention designs, and quantization (see KV cache optimization). It does not speed up the attention arithmetic either, and it is not a substitute for FlashAttention, which sits at a different layer of the stack: FlashAttention reorders the computation so attention stays in fast on-chip memory, while PagedAttention decides where the keys and values it reads are stored. The two compose; the vAttention paper’s baselines are exactly that combination, the “PagedAttention-based kernels of FlashAttention and FlashInfer.”

What paging does is remove waste. It makes the memory you already have hold requests instead of reservations, which raises the achievable batch size, and batch size is what turns a bandwidth-bound decode step into more useful work per byte read. That is a capacity gain, and it is why the technique shows up in serving benchmarks as throughput at a given latency rather than as a faster single request.

The Cost: Indirection, and the Alternatives

Paging is not free. The attention kernel can no longer stream through one contiguous range; it has to look up each block’s physical address and gather from scattered memory. The paper reports 20% to 26% higher attention kernel latency than FasterTransformer’s contiguous implementation. The trade was overwhelmingly positive because the memory saved lets much larger batches run: the paper’s headline is 2x to 4x higher throughput at the same latency versus FasterTransformer and Orca, with the gap widening for longer sequences, larger models, and more complex decoding algorithms. Later work has narrowed the kernel gap, notably FlashInfer, whose block-sparse format for KV storage was integrated into SGLang, vLLM, and MLC-Engine.

Another line of work asks whether the indirection is necessary at all. vAttention (Prabhu et al., ASPLOS 2025) keeps the KV cache contiguous in virtual memory and uses the GPU’s CUDA virtual memory APIs to back it with physical pages on demand, so unmodified attention kernels work and fragmentation in physical memory is still avoided. The authors report up to 1.23x higher throughput than the paged kernels of FlashAttention and FlashInfer.

What’s New (2025-2026)

• Paging became the default assumption, not an optimization. vLLM V1’s re-architecture kept the paged design and made prefix caching on by default, reporting less than 1% throughput loss even at a 0% hit rate, and “several times” better performance when hit rates are high. Block-level reuse is now the substrate that prefix caching is built on.
• Heterogeneous models broke the uniform-block assumption, and allocators adapted. Sliding-window layers, hybrid state-space layers, and multimodal encoders each want different amounts of cache per token. Jenga (Zhang et al., 2025) uses a two-level allocator based on the least common multiple of embedding sizes and layer-specific caching policies, and reports up to 79.6% better GPU memory utilization and up to 4.92x (1.80x on average) higher throughput on vLLM.
• The kernel side kept improving. FlashInfer (MLSys 2025) reported 29% to 69% lower inter-token latency than compiler backends and became a common attention backend, showing that block-sparse KV formats can be fast rather than merely convenient.
• Blocks now move across tiers. Because a block is a self-contained unit, engines can offload cold blocks to CPU memory, disk, or a remote store and reload them later. LMCache (2025) implements this as a KV cache layer that plugs into vLLM and SGLang and reports up to 15x throughput improvement on workloads like multi-round Q&A and document analysis.
• Block sharing is being extended past exact prefixes. Research on position-independent caching reuses cached blocks even when the surrounding text changes; see prefix caching and position-independent caching for how.

Practical Guidance

The reason PagedAttention mattered so much is that it changed what the bottleneck was. Before it, KV cache capacity was throttled less by how much memory a GPU had than by how badly that memory was managed, with most of it stranded in reservations and gaps. After it, capacity tracks what requests actually use, and everything built on top of it (sharing, prefix reuse, offloading, migration between machines) follows from the same move: treat the KV cache as a pool of small, addressable blocks rather than a private buffer per request.

from vllm import LLM, SamplingParams

# Scenario: an internal support assistant on a single 24 GB GPU. Weights take
# roughly 16 GB, leaving about 4 GiB for the KV cache. PagedAttention is always
# on in vLLM; these are the knobs that decide how big the block pool is.
llm = LLM(
    model="meta-llama/Llama-3.1-8B-Instruct",
    block_size=16,                 # tokens per KV block (the default)
    gpu_memory_utilization=0.90,   # fraction of GPU memory vLLM may claim
    max_model_len=8192,            # longest sequence it will admit, NOT a per-request reservation
    enable_prefix_caching=True,    # reuse full blocks across requests with a shared prefix
)

# Capacity math you can do by hand before launching:
kv_bytes_per_token = 2 * 32 * 8 * 128 * 2   # K and V x layers x kv_heads x head_dim x fp16 bytes
kv_budget = 4 * 2**30                        # ~4 GiB left after weights and activations
total_tokens = kv_budget // kv_bytes_per_token   # 32,768 tokens of KV cache
num_blocks = total_tokens // 16                  # 2,048 blocks of 16 tokens
# A static, max-length allocator would fit only 4 requests at 8,192 tokens each.
# Paged, 40 chats averaging 700 tokens need 40 * 44 = 1,760 blocks and all fit.

# Scenario: draft four candidate replies for one customer message. The four
# samples share the prompt's KV blocks; only newly generated tokens get new ones.
params = SamplingParams(n=4, temperature=0.9, max_tokens=200)
out = llm.generate("Customer: my invoice shows a duplicate charge...", params)
for candidate in out[0].outputs:
    print(candidate.text)