PagedAttention and KV Cache Memory Management

Updated Nov 16, 2026 · 5 min read
On this page

    A serving team has 50 GB of GPU memory set aside for the KV cache and a model that needs 128 KB of cache per token. On paper that is 380,000 tokens. Yet with an 8,192-token limit the server never runs more than about 40 requests at once, and reports the cache as "full". Each request had been given one contiguous slab sized for the maximum length, and most requests stop after a few hundred tokens. PagedAttention borrows the idea of virtual memory from operating systems: store the KV cache in small fixed-size blocks and give each request a table that maps its tokens to wherever those blocks live.

    How it works

    The problem: reserve-for-max

    Contiguous slabs sized for the maximum length leave most of the reserved memory empty, and the free gaps left over are too small to reuse.
    Contiguous slabs sized for the maximum length leave most of the reserved memory empty, and the free gaps left over are too small to reuse.

    The server doesn't know how long an answer will be, so a simple allocator reserves room for the maximum (prompt + max new tokens) in one contiguous piece. Three kinds of waste follow:

    • Reserved but unused: with a 2,048-token limit, a request that stops at 400 tokens leaves 1,648 slots empty, about 80% of its slab.
    • Internal fragmentation: slots reserved for tokens that will never be written.
    • External fragmentation: after requests finish, free memory is broken into gaps too small for a new slab.

    The vLLM paper (Kwon et al., SOSP 2023) measured that earlier systems left 60–80% of KV cache memory unused this way.

    Blocks and block tables

    Each request's logical blocks map through its block table to physical blocks anywhere in the pool.
    Each request's logical blocks map through its block table to physical blocks anywhere in the pool.
    1. GPU cache memory is split into a pool of physical blocks, each holding keys and values for a fixed number of tokens (16 is a common default) across all layers.
    2. Each request has a block table: logical block 0, 1, 2… → physical block number. Blocks don't need to be next to each other.
    3. A new block is taken from the free list only when the previous one fills up. When a request finishes, its blocks go straight back to the pool.
    4. The attention kernel is changed to follow the block table: for each logical block it fetches keys and values from the physical address. That custom kernel is the "PagedAttention" part.

    Waste is now at most one partly filled block per request: about 8 tokens on average with 16-token blocks, or 2% of a 400-token request. The paper reports under 4% waste overall and 2–4× higher throughput than earlier systems at the same latency, mainly because many more requests fit in a batch.

    Sharing blocks

    Two samples share the prompt's physical blocks through reference counts and get their own blocks once their outputs differ.
    Two samples share the prompt's physical blocks through reference counts and get their own blocks once their outputs differ.

    Because a block table is just a list of pointers, two requests can point at the same physical block. Each block keeps a reference count; if a request needs to write into a shared block, the server copies it first (copy-on-write). This makes these cheap:

    • Parallel sampling (n answers to one prompt): the prompt's cache is stored once.
    • Beam search: beams share their common history.
    • Shared prefixes across requests, such as a long system prompt: the basis of automatic prefix caching (see Prefix Caching).

    Trade-offs and costs

    • Kernel overhead. Gathering keys and values through a table is a little slower than reading one contiguous array. The paper measured attention kernel overhead of roughly 20–26%, small next to the gain from bigger batches.
    • Block size. Small blocks waste less but mean longer tables and less efficient memory reads; large blocks do the opposite. Defaults of 16–32 tokens work for most cases.
    • Preemption is still needed. Paging lets you admit more requests, so the cache can fill mid-generation. The server then swaps a request's blocks to CPU memory or frees them and recomputes later.
    • Engine complexity. Every kernel that touches the cache (attention, FP8 cache, speculative decoding) must understand block tables.

    In production

    • vLLM introduced it; SGLang (radix-tree cache), TensorRT-LLM (paged KV cache) and TGI have equivalents. You won't write it, but you will tune it: GPU memory fraction for the cache, block size, max sequences, and swap space.
    • Watch KV cache usage, the number of free blocks, preemptions and swaps per minute. Frequent preemption means contexts are longer than the cache was sized for.
    • When you report capacity, use real context-length distributions: paging makes capacity depend on actual lengths, not maximums.

    When to reach for it

    Whenever you explain how a modern server fits many requests on one GPU, debug "cache full" errors or preemptions, or design an inference platform. It also explains why n > 1 sampling and long shared system prompts are cheaper than they look.

    Example

    Same setup as the opening: 50 GB of cache, 128 KB per token, an 8,192-token limit, real requests averaging 400 tokens. Reserve-for-max fits 50 GB / (8,192 × 128 KB) ≈ 47 slabs, fewer after fragmentation, and about 95% of the reserved memory is never written. With 16-token blocks, each request holds about 400 + 8 tokens, so roughly 380,000 / 408 ≈ 930 requests could fit; the batch is now limited by compute and the latency target instead of memory.

    Common mistakes

    • Confusing PagedAttention with a faster attention formula. It is memory management for the KV cache; FlashAttention is the kernel trick for computing attention faster.
    • Thinking it reduces the cache per token. It doesn't; it removes waste. Grouped-query attention or an FP8 cache reduce per-token size.
    • Sizing capacity on maximum context length instead of the real distribution.
    • Ignoring preemption metrics after admitting more requests.

    Say this in the interview

    "Without paging, the server reserves a contiguous KV cache slab for each request's maximum length, and since most requests stop early, 60–80% of cache memory sits unused. PagedAttention splits the cache into fixed blocks of, say, 16 tokens, allocates them on demand, and gives each request a block table mapping logical to physical blocks, like virtual memory. The attention kernel reads through that table. Waste drops to under one block per request, so several times more requests fit in a batch, and blocks can be shared with copy-on-write for parallel sampling, beam search and common prefixes."

    Interview questions on this

    1. What kinds of memory waste does PagedAttention remove? Reservation for unknown output length, internal fragmentation and external fragmentation.
    2. How does the attention kernel find keys and values that aren't contiguous? It reads the request's block table and gathers each block from its physical address.
    3. How would you choose a block size? Trade waste (smaller is better) against table size and memory-read efficiency (larger is better); 16–32 tokens is typical.
    4. How is a shared system prompt stored once for many requests? Their block tables point at the same blocks, tracked by reference counts, with copy-on-write on modification.
    5. What happens when the pool runs out mid-generation? The scheduler preempts a request, either swapping its blocks to CPU or freeing them to recompute later.
    6. Why does PagedAttention raise throughput if it makes the kernel slower? It lets a much larger batch fit, and decode throughput scales with batch size.

    Used in

    • AI Engineering: Prefill, Decode and the KV Cache; Continuous Batching; Prefix Caching; FlashAttention; Implement a KV Cache for Generation.
    • AI System Design: Design an Inference Platform; Design ChatGPT.