Learn / What is paged attention?

What is paged attention?

Paged attention is a memory-management technique that stores the KV cache in fixed-size blocks and maps each request's tokens to those blocks through a small lookup table — virtual memory, applied to GPU inference. Introduced by the vLLM project's PagedAttention work in 2023, it cut KV memory waste from the majority of the reservation to a few tokens per request, and it is now the baseline design of every serious inference engine.

The problem it solves

During generation the model stores a key and a value vector for every token it has seen. That cache grows one token at a time, to a final length nobody knows in advance, and must be freed the instant the request finishes: heap allocation, happening thousands of times per second, inside GPU memory.

Early engines dodged the problem by reserving one contiguous slab per request, sized for the maximum length the request might reach. The PagedAttention authors measured the result: only 20 to 40% of KV memory in existing systems held actual token state; the rest was reservation, padding, and fragmentation. A 200-token request against a 4,096-token maximum wastes 95% of its half-gigabyte slab. And wasted KV memory is lost concurrency: every wasted gigabyte is a batch slot another user could have occupied.

How it works

The fix is the one operating systems shipped in the 1960s: stop requiring contiguity. KV memory is chopped into fixed blocks (16 tokens each in the original design), the engine keeps a pool of free blocks, and each request gets a block table mapping its logical token positions to whichever physical blocks it was granted. Blocks of one sequence can be scattered anywhere in VRAM. When the attention kernel needs the entry for token position $p$ , it computes:

slot (p) = block_table [⌊ p /16 ⌋] \cdot 16 + (p mod 16)

Allocation is popping a block off the free list; freeing is pushing it back. Both are O(1), so the scheduler can do them on every generation step. A request that has produced $t$ tokens holds $⌈ t /16 ⌉$ blocks, so waste is bounded by one partial block: at most 15 tokens per sequence, versus hundreds of megabytes under contiguous reservation.

What it enables

Higher concurrency. Memory tracks actual length instead of feared length, so far more simultaneous requests fit on the same GPU.
Prefix sharing. Because the table is indirection, two requests with the same prefix can point at the same physical blocks with a reference count, which is what prompt caching is at the serving layer.
Preemption. Under memory pressure the engine can evict a request by returning its blocks to the pool and recomputing later, because giving memory back is as cheap as taking it.
Continuous batching. Refilling a batch slot the moment a request finishes only works if memory can be granted and reclaimed at token granularity — paging is what makes continuous batching practical.

The mechanics, with the worked memory arithmetic and diagrams, are in the deep dive: how paged attention and continuous batching actually work.

Frequently asked questions

Is paged attention the same thing as the KV cache?

No. The KV cache is what gets stored: a key and value vector per token, per layer. Paged attention is how that storage is managed: in fixed-size blocks through a block table instead of one contiguous slab per request.

Does paged attention slow the attention computation down?

The kernel must gather KV entries through the block table instead of reading them side by side, which costs a little indirection. Fused attention kernels hide that cost well, and the concurrency gained from eliminating memory waste far outweighs it.

Do all inference engines use paged attention?

Since vLLM introduced PagedAttention in 2023, block-based KV memory management has become the baseline for serious serving engines, including vLLM, SGLang, TensorRT-LLM, and Netra Runtime. Engines differ in what they build on top of it; see the published benchmark for how much that difference matters.