Paged attention in LLMs

Paged attention is a way of storing an LLM's KV cache in small fixed-size blocks instead of one long, unbroken stretch of memory. It exists because the unbroken version wastes an enormous amount of GPU memory, which caps how many people you can serve at once.

The cache being stored

While a model generates, it keeps the keys and values of every token it has seen so far. That store is the KV cache, and it is what lets the model avoid recomputing the same vectors on every step.

The cache grows by one token's worth of keys and values each step, and it lives in GPU memory for as long as the request does. Fitting more requests on a GPU is mostly a question of fitting more of these caches.

Why the memory gets wasted

Here is the awkward part: when a request arrives, nobody knows how long the reply will be. It could be 12 tokens or 900.

The simple approach is to reserve enough room for the longest reply you allow. If your limit is 2,048 tokens, every request gets 2,048 slots reserved up front, in one continuous run.

That produces two kinds of waste.

Waste inside the reservation. A request that answers in 60 tokens still holds all 2,048 slots. The other 1,988 sit reserved and unused for the whole request. Nothing else can touch them.

Waste between reservations. Because each reservation has to be one continuous run, free memory left between finished requests is often unusable. You might have three free gaps of 8, 6 and 10 slots — 24 slots free in total — and still be unable to admit a request needing 20 in a row. The memory is there. It just isn't in one piece.

The fix: stop demanding one continuous run

Paged attention borrows an old operating-system idea. Instead of one long reservation, the cache is cut into small blocks of a fixed size, and those blocks do not have to sit next to each other.

A request takes a block when it needs one. When that block fills up, it takes another from wherever there is space.

Think of a car park with numbered bays. Rather than roping off a whole row for a group that might not turn up in full, you hand out single bays as cars arrive and write down the numbers. The cars end up scattered. It does not matter, because the list tells you where each one is.

A worked example

Take a reply that comes out 14 tokens long:

Rain started just as the match reached its final over and everyone ran inside

Reserving for a 32-token maximum, and then paging the same reply into blocks of 5:

Reserved as one run, 18 of the 32 slots are wasted. Paged into blocks of 5, the reply needs three blocks — 15 slots — and wastes exactly one, in the tail of the last block.

	slots held	used	wasted
one contiguous reservation	32	14	18
three blocks of 5	15	14	1

The three blocks are filled like this:

block	tokens
0	Rain started just as the
1	match reached its final over
2	and everyone ran inside —

Keeping track: the block table

Once blocks are scattered, something has to remember where they are. That is the block table.

Each request gets one. It maps the block's position in the sequence — block 0, block 1, block 2 — to wherever that block physically sits in memory. When attention needs the keys and values for earlier tokens, it reads the table and follows it to each block in turn.

The sequence stays in order from the model's point of view. Only the physical layout is scattered.

Why this helps so much

Both kinds of waste mostly disappear.

Waste inside a request drops to whatever is left over in its final block. With blocks of 5, that is at most 4 slots per request, no matter how long the reply is — instead of hundreds.

Waste between requests disappears too. Every block is the same size, so any free block fits any request. There is no such thing as a gap that is the wrong shape.

The result is that far more requests fit in the same GPU memory, which is exactly what decides how many users a server can handle at once.

Sharing blocks

There is a bonus. Two requests that begin with the same tokens can point at the same physical blocks from their own block tables.

This happens whenever you generate several candidate replies for one prompt, as with parallel sampling or beam search. The shared prefix is stored once and read by all of them. Each request keeps its own table, so they stay independent — they just stop paying for duplicate copies of identical data.

The short version

• The KV cache holds the keys and values of every token so far, and it grows as the reply grows.
• Reply length is unknown up front, so the simple approach reserves the maximum in one continuous run.
• That wastes the unused tail of every reservation, and leaves free gaps too small or badly shaped to reuse.
• Paged attention splits the cache into fixed-size blocks that need not be adjacent.
• A block table records where each block sits, so the sequence still reads in order.
• Waste per request falls to the tail of the last block, and identical prefixes can share blocks outright.