PagedAttention

Abstract

Serving an LLM is limited less by arithmetic than by how much key-value cache fits in GPU memory, and a conventional server wastes most of that capacity before a request generates anything: it reserves a contiguous region sized for the maximum possible sequence length and leaves the remainder unused. PagedAttention applies virtual memory to the KV cache. The cache is split into fixed-size blocks that live anywhere in the pool, and a per-request block table translates logical positions to physical blocks. This article derives why the waste is large, describes the block table and the address translation the attention kernel performs, and shows how the same indirection permits copy-on-write sharing of common prefixes. It assumes the cache sizing and decode arithmetic from The KV Cache and Attention Variants.

1. 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.

1.1 Why the cache dominates memory

The previous article derives the size of the cache: $2 L H_{kv} d_h T b$ bytes, which for a 32-layer multi-head model in BF16 is 512 KB for every token generated. At that rate the cache overtakes the weights within a few thousand tokens, so reserving by maximum sequence length rather than actual length wastes the resource that decides how many requests fit.

The arithmetic is worth making concrete before the fix is described. Take a 32-layer model with $H_{kv} = 32$, $d_h = 128$, in BF16, so a token costs 512 KB, and give the cache 247 GB. Now ask how many concurrent requests fit:

The left column — what reservation achieves — depends only on the reservation. The paged column depends only on what was actually written. At a 128K context with 128-token requests, reservation admits three concurrent requests where paging admits 3,854. That is not a percentage improvement; it is a different operating regime, and it is the entire argument of this article in one table.

One caveat, so the number is not over-read: 3,854 requests is a memory bound, not a throughput bound. A batch that large would be limited by bandwidth and by the scheduler long before it ran out of pages. What paging buys is that memory stops being the binding constraint first.

2. PagedAttention: Borrowing from Operating Systems

2.1 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.

2.2 Address translation and kernel access

Let a block hold $P$ token positions — the page size. 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.

2.3 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.

3. 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.

4. 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.

The indirection is not free. The kernel performs a table lookup per logical block, so accesses through scattered physical blocks are less regular than a contiguous read. That cost is paid at the kernel level and is where FlashInfer’s format-aware templates begin: FlashInfer consumes exactly the block tables described here and specializes the gather for each supported layout.

There is also a limit on what paging alone can achieve. It raises the memory ceiling but says nothing about which requests should occupy it, and the batch that keeps the device busy is far smaller than the capacity this allocator exposes. That decision belongs to the scheduler, which the next article takes up.

References

1. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP, 2023.