PagedAttention

Modern large language models are expensive to serve because autoregressive decoding maintains a growing key-value (KV) cache for every active request. PagedAttention addresses this memory-management problem by applying the core idea of virtual memory to KV-cache storage.

The KV-cache allocation problem

When an LLM server handles many concurrent requests, each request maintains a KV cache containing the keys and values needed for autoregressive decoding. The cache grows as tokens are generated, but its final length is unknown when a request begins.

Traditional serving systems reserved a contiguous region sized for each request’s maximum possible sequence length. A request that generated only 20 tokens could therefore reserve space for 2,048, producing substantial internal fragmentation and limiting the number of concurrent requests that fit in GPU memory.

flowchart LR
  R1["Request A<br/>20 generated tokens"] --> C1["Contiguous reservation<br/>2,048-token region"]
  R2["Request B<br/>variable length"] --> C2["Contiguous reservation<br/>2,048-token region"]
  C1 --> W["Mostly unused KV-cache capacity"]
  C2 --> W

Why the cache dominates memory

For one token, one transformer layer stores a key and a value vector. With $L$ layers, $H_{kv}$ key-value heads, head dimension $d$, and element width $b$ bytes, the KV-cache footprint for a sequence of $T$ tokens is

The factor of two accounts for both keys and values. For a 32-layer model with 32 KV heads, $d=128$, and BF16 storage ($b=2$), each token consumes 512 KiB of KV cache. At this scale, reserving memory according to a maximum sequence length rather than the actual generated length quickly dominates the server’s capacity.

PagedAttention: Borrowing from Operating Systems

The Insight: Virtual Memory for KV Caches

The PagedAttention paper observed that this problem is structurally identical to one the operating systems community solved decades ago: how to give processes the illusion of contiguous memory when physical memory is fragmented.

The solution mirrors OS virtual memory almost exactly. Instead of storing each request’s KV cache in one contiguous block, PagedAttention divides it into fixed-size blocks (analogous to memory pages). These blocks can be scattered anywhere in GPU memory. A block table (analogous to a page table) maps each request’s logical KV cache positions to physical block locations. The attention kernel is rewritten to look up this mapping when reading keys and values.

Memory is allocated one block at a time, on demand, as new tokens are generated. When a request finishes, its blocks are freed immediately for reuse.

flowchart LR
  REQ["Request A<br/>logical KV cache"] --> BT["Block table<br/>[7, 2, 11]"]
  BT --> P7["Physical block 7<br/>tokens 0-15"]
  BT --> P2["Physical block 2<br/>tokens 16-31"]
  BT --> P11["Physical block 11<br/>tokens 32-47"]

  subgraph GPU["GPU KV-cache pool"]
    P7
    P2
    P11
  end

Address translation and kernel access

Let a block hold $B$ token positions. For logical token position $t$, the attention kernel derives a logical block number and an in-block offset:

The request’s block table maps $q$ to a physical block identifier $p$. The key or value for token $t$ is therefore read from physical block $p$ at offset $r$, rather than from a contiguous base address plus $t$. In the original PagedAttention design, blocks contain a small fixed number of tokens, commonly 16; this keeps allocation granular enough to limit waste while avoiding excessive block-table and kernel-indirection overhead.

The attention kernel iterates over the request’s logical blocks, gathers the corresponding K and V vectors through the block table, and computes the usual attention reduction. The arithmetic is unchanged. The implementation cost is the extra address indirection and less regular memory access, which is substantially smaller than the capacity recovered from avoiding reservation and fragmentation.

flowchart LR
  T["Logical token t = 29"] --> X["q = floor(t / B) = 1<br/>r = t mod B = 13"]
  X --> TABLE["block_table[1] = 2"]
  TABLE --> KV["Physical block 2<br/>K[13], V[13]"]
  KV --> ATTN["Attention reduction"]

Copy-on-Write and Memory Sharing

The OS analogy goes further. Requests that share a common prefix — say, the same system prompt — can point to the same physical KV blocks. The blocks are shared read-only, and only duplicated (copy-on-write) when one request diverges from another. This is directly analogous to how fork() works in Unix: parent and child share memory pages until one writes to them.

For workloads like chatbots (where every request starts with the same system prompt) or beam search (where candidates share a long common prefix), this sharing dramatically reduces memory consumption.

flowchart LR
  subgraph SHARED["Shared, read-only prefix blocks"]
    P0["Block 4<br/>system prompt"] --> P1["Block 9<br/>shared prefix"]
  end
  A["Request A block table"] --> P0
  B["Request B block table"] --> P0
  A --> A1["Private block 12<br/>continuation A"]
  B --> B1["Private block 3<br/>continuation B"]

From PagedAttention to vLLM

PagedAttention was introduced by the vLLM project in its 2023 SOSP paper, Efficient Memory Management for Large Language Model Serving with PagedAttention. The technique was not merely an optimization incorporated into vLLM: it was the project’s central systems contribution and the basis for its original runtime design.

The recovered memory capacity permits larger batches and more concurrent requests, yielding 2–4x throughput improvements over the evaluated prior serving systems. vLLM subsequently became a widely used open-source LLM-serving engine, and PagedAttention remains the conceptual foundation for its KV-cache manager.

Implications

PagedAttention operates at the serving-system level: it improves memory capacity utilization without changing the attention computation itself. By transforming the KV cache from a contiguous allocation into an on-demand, block-addressed resource, it allows a server to sustain larger batches and more concurrent requests with the same GPU memory budget.

The design illustrates a broader ML-systems principle: established operating-system mechanisms can address bottlenecks created by model-serving access patterns. Here, virtual-memory-style indirection converts KV-cache fragmentation into a manageable allocation problem.