Paged Attention: Virtual Memory for the KV Cache

Before paged attention, an inference server had to reserve key-value cache memory for a request's maximum possible length the moment it was admitted. A request that might generate four thousand tokens got four thousand tokens' worth of contiguous memory, whether it used it or not.

Most requests stop far earlier. The reserved-but-unused remainder could not be given to anyone else, because the next request also needed one contiguous run. The result was a server that reported plenty of free memory while refusing to admit anything, and concurrency that fell far short of what the hardware could actually hold.

The problem is fragmentation, not capacity

Three kinds of waste appear when the cache is allocated as contiguous slabs.

Internal waste is the gap between what was reserved and what was used. A request that reserved room for four thousand tokens and generated two hundred is sitting on unused space for its entire lifetime.

External waste is memory that is free but unusable. After a few requests come and go, the free memory is scattered in pieces, none of them large enough for a new contiguous reservation, so admission fails while the total free figure looks healthy.

Duplication is the third. Several requests sharing the same system prompt each held their own identical copy of that prefix's cache, because there was no way for two allocations to point at the same memory. What the cache stores makes clear how much that prefix can weigh at long context.

The fix borrowed from operating systems

Paged attention applies the idea behind virtual memory. Instead of one contiguous region per request, the cache is divided into small fixed-size blocks, each holding the keys and values for a handful of tokens.

Each request keeps a block table — an ordered list of which physical blocks hold its sequence. The blocks themselves can sit anywhere in memory, in any order. The attention kernel is written to follow the table rather than to assume the sequence is laid out end to end.

Allocation then becomes incremental. A request gets one block, fills it, and asks for another only when it needs one. A request that stops early simply never asked for the blocks it did not use, and the ones it held are returned to a shared pool the moment it finishes.

Waste falls to at most one partly filled block per request, which is negligible. External fragmentation disappears entirely, because every free block is interchangeable with every other.

Sharing comes almost for free

Once a sequence is described by a table of block references rather than a memory range, two sequences can reference the same block.

That makes prefix sharing straightforward. Ten requests with the same long system prompt point their first several blocks at one physical copy. The memory for that prefix is paid once, not ten times, and the prefill for it can be skipped as well.

Divergence is handled with copy-on-write. The shared blocks stay shared for as long as the sequences agree; the moment one generates something different it gets its own copy of the block being written. This is also how parallel sampling from a single prompt stays cheap — several candidate continuations share everything up to the branch point.

Provider-side prompt caching is the same idea persisted across requests rather than within a single batch, which is why the pricing for cached input is so much lower than for fresh input.

What it buys in practice

The direct effect is more concurrent sequences on the same hardware. Memory that was previously reserved and idle becomes memory holding real sessions.

The indirect effect is larger. Higher concurrency means bigger batches, and bigger batches mean the fixed cost of reading model weights is spread across more tokens. Paged attention improves throughput mostly by making continuous batching viable at aggressive admission levels, and the two are effectively one system.

It also makes admission decisions safer. Because memory is handed out in small increments, a server can admit a request without committing to its worst case, and can tell precisely how close it is to the ceiling.

What it does not fix

Paged attention does not shrink the cache. A token still costs whatever it costs per layer, and a long conversation still grows monotonically. It removes waste around the cache, not the cache itself.

Reducing the cache is an architecture question, handled by grouped-query attention or by the latent-attention compression used in models like Kimi K2.6. Those change how much each token costs; paging changes how efficiently that cost is packed.

There is also a small cost to paying attention through an indirection table rather than a flat array. Well-written kernels make it minor, and the concurrency gain dwarfs it, but it is not free.

Finally, when memory does run out the server still has to preempt — evict a sequence and recompute or swap its blocks later. Paging pushes that point much further out and makes recovery cheaper, but it does not remove the ceiling.

Why this matters if you are only calling an API

You will never configure a block size, but the behaviour explains things you observe.

It is part of why repeated prefixes are cheap and why reordering a prompt can change your bill. Stable content first, variable content last is not a stylistic preference — it is what keeps the shared blocks shared. A timestamp at the top of a system prompt breaks sharing for every request.

It also explains why long-context pricing exists at all. Occupancy, not arithmetic, is the scarce resource, and the cost of a large context window is mostly the cost of holding it.

If you self-host

Assume paged attention is on; every current serving stack implements some version of it. The settings worth attention are the fraction of memory reserved for the cache and the block size, and both should be tuned against your real context lengths rather than defaults.

Size the deployment for concurrent cache occupancy, not for the weights. A model that fits comfortably can still serve almost nobody if each session is holding hundreds of thousands of tokens of context, and this is the calculation that most often turns a promising self-hosting plan into an expensive one. Choosing a model to self-host should start from that figure.