Post

LLM Inference #6: Paged Attention

An LLM server stops admitting requests while a third of its KV memory looks free. Where that memory goes, how block tables get it back, and three places where vLLM no longer matches the PagedAttention paper.

LLM Inference #6: Paged Attention

Your dashboard says the eight-GPU server has KV capacity for about 120 typical requests. It stops admitting new ones at 80. The weights did not grow and nobody deployed anything. The queue builds while a third of the memory budget sits there, apparently free.

The memory is not missing. It is reserved for tokens that do not exist yet, and some of it is reserved for tokens that will never exist.

The batching article ended on this problem. Continuous batching pays off only if you keep enough sequences resident, and every resident sequence holds its KV cache on the GPU until it finishes. The scheduler must decide whether a request fits before it admits the request, and it does not know how long the answer will be.

The fix is an allocator, and it borrows its design from virtual memory. The vLLM details here come from the source rather than from the PagedAttention paper, which is from 2023 and no longer matches the code in three places.

One slab per request wastes most of the memory

The obvious layout gives each request one contiguous region, sized for the longest answer it may produce. Addressing is then cheap, because the address of position i is the base pointer plus i times the per-token size.

You do not know the output length when the request arrives. So “large enough” has to mean the maximum. With a limit of 8,192 tokens, every request reserves 8,192 tokens of space on arrival.

One contiguous slab per request, each sized for the worst case live KV, tokens that exist reserved for tokens that may never exist request A, 8K reserved request B, 8K reserved request C, 8K reserved 2K tokens live 1K tokens live 7K tokens live free and unusable Live tokens: 10K. Reserved tokens: 24K. Requests admitted: 3. Request D needs one unbroken slab. The leftover tail is real memory in the wrong shape, so D waits while the GPU runs at a third of the concurrency it could.

That picture has three problems.

Space for tokens that arrive later. A running sequence will use some of its reservation. You cannot lend that space out and take it back, because the region has to stay contiguous.

Space for tokens that never arrive. A request allowed 8,192 tokens that stops at 2,000 holds the other 6,192 until it finishes. This is the expensive one.

Holes. Sequences finish in a different order than they started, so free memory ends up in gaps. Each gap is too small for a new slab. The total free bytes look fine and none of them are usable.

Put a number on it

Llama 3.1 70B in BF16 has 80 layers, 8 KV heads, and head dimension 128. One cached token costs:

1
2 (K and V) x 80 layers x 8 KV heads x 128 dims x 2 bytes = 327,680 bytes = 320 KiB per token

A request allowed 8,192 tokens reserves 2.5 GiB. If it produces 2,048 tokens, it uses 0.625 GiB. The other 1.875 GiB stays reserved and untouched. Across 100 concurrent requests that is 187.5 GiB of KV capacity that nobody can use.

Virtual memory already solved this

The sequence does not need a lot of memory. It needs memory it does not have yet, in one piece, at an address that cannot move. Operating systems had the same problem in the 1960s.

What an operating system does what the process sees page 0 page 1 page 2 page 3 page table page 0 to frame 7 page 1 to frame 2 page 2 to frame 9 page 3 to frame 4 physical memory 0 1 2 3 4 5 6 7 8 9 10 11 The process sees one unbroken run of pages. The hardware keeps them wherever there was room. No free frame is ever the wrong shape, because every frame is the same size.

Now do the same thing to the KV cache. Cut each sequence’s cache into fixed-size blocks. Keep a block table per sequence that maps its block 0, 1, 2 and so on to whatever physical slots are free. The sequence keeps a strict order of positions, but those positions no longer have to sit next to each other in memory.

The same idea, applied to one sequence's KV cache what the sequence sees block 0, tokens 0-63 block 1, tokens 64-127 block 2, tokens 128-191 block 3, filling block table block 0 to slot 7 block 1 to slot 2 block 2 to slot 9 block 3 to slot 4 KV pool on the GPU free free 2 free 4 free free 7 free 9 free free To compute attention for the next token, the kernel walks the block table and reads K and V from each slot. The animation steps through that walk. The order of the slots in the pool does not matter. Block sizes here are 64 tokens, which is vLLM's current default.

Two different things came out of that paper. The block manager is an allocator. It owns fixed-size blocks, a free list, and the per-sequence block tables. PagedAttention is the attention kernel that reads K and V scattered across those blocks instead of from one flat run. You need both, and they are different code.

That second piece has aged. On NVIDIA hardware vLLM now runs FlashAttention by default, and the backend hands it a block_table tensor directly. The hand-written paged_attention CUDA kernel from the paper still exists, mostly on ROCm and older paths.

The analogy stops at the hardware. No MMU is involved. The block table is an ordinary tensor that the runtime maintains and the kernel indexes on every attention call, in software. There is no page fault and no demand paging from disk. A wrong mapping does not trap either, so the model reads the wrong keys and values and generates text that reads perfectly well.

Growth costs one block

A sequence grows by one token per step. The contiguous layout had to reserve for the worst case because a region cannot grow into memory that another request owns. With blocks, growth touches one block.

Growth takes one block, not one slab the sequence full full full new block free pool one slot, taken when the last block fills A sequence holds at most one partly filled block, which is always its last one. Every block before it is packed solid. The length limit no longer costs anything up front.

Wasted space per sequence is therefore less than one block, no matter how long the sequence runs or how high you set the length limit.

What waste is left

vLLM’s default block size is 64 tokens, set by DEFAULT_BLOCK_SIZE. For the Llama 3.1 70B numbers above, one block costs 64 x 320 KiB = 20 MiB across the model. A sequence that stops partway through its last block leaves at most 63 unused token slots. Averaged over arbitrary stopping points that is about 32 slots, or 10 MiB.

Compare that with the 1.875 GiB the contiguous slab was holding for the same request.

Wasted KV memory per request, 8K limit and 2K actual output contiguous slab 1.875 GiB 64-token blocks about 10 MiB, the unused tail of one block Across 100 concurrent requests: 187.5 GiB stranded against roughly 1 GiB of block tails. The bars are to scale. The green one is two pixels wide.

The holes disappear too. Every free block is interchangeable, so a hole can never be the wrong size. The allocator’s job drops from “find a large enough contiguous run” to “take the next block off the free list”.

The same memory, repacked contiguous 3 sequences paged 9 sequences Nothing about the GPU changed. The allocator stopped holding memory for tokens that do not exist. Illustrative. Your gain depends on how far your length limit sits above your typical output.

Picking a block size

Blocks are the unit of allocation, so their size trades two costs against each other.

The same 50-token sequence at two block sizes 4 tokens 13 block-table entries, 2 token slots wasted 64 tokens 1 block-table entry, 14 token slots wasted Small blocks waste less memory and cost more bookkeeping. The table gets longer, the kernel does more indexing, and memory access gets less regular. Large blocks trade the other way. vLLM moved its default from 16 to 64 as attention kernels got better at large blocks.

Block size also sets the granularity of cache hits. Two requests can share a block only if they agree on all 64 of its tokens.

Sharing blocks between requests

Once KV lives in blocks behind a table, two sequences can point at the same block. vLLM tracks this with ref_cnt on KVCacheBlock. A block with ref_cnt above zero cannot be reused by anyone else.

Identical prefixes are common in real traffic. Every request from one application starts with the same system prompt. Every turn of a chat repeats the whole conversation so far.

Two requests, one copy of the shared prefix ref_cnt = 2 system prompt system prompt request 1 its own tokens its own tokens request 2 its own tokens its own tokens Two block tables, one copy of the prefix keys and values. Request 2 also skips the prefill for those tokens. vLLM turns this on by default. enable_prefix_caching is True in vllm/config/cache.py.

Sharing works because KV is immutable once written. The keys and values for position 12 never change after the model computes position 12. vLLM finds shareable blocks by hashing the token IDs a block covers and looking the hash up in cached_block_hash_to_block.

When a request finishes, its blocks go back on a free list that keeps their contents and their hash. FreeKVCacheBlockQueue orders that list least-recently-used first, so a freed block survives until someone needs the space. A later request with the same prefix can still hit it.

When the pool is empty

Paging gives you more headroom, not infinite memory. Continuous batching admits requests until that headroom is gone, and the sequences already running keep growing. Eventually one of them asks for a block and the free list is empty.

What vLLM does when the free list is empty a running sequence needs a block, and there is none pick a victim: the last request in the running list free all of its blocks, set num_computed_tokens to 0, and put it back on the waiting queue The victim loses all of its KV at once. Half a sequence of KV on the GPU is no use to anyone. When it runs again it redoes its prefill, though prefix caching often returns some of its old blocks. Watch the preemption counter. A server that preempts often is admitting work it cannot hold. Source: _preempt_request in vllm/v1/core/sched/scheduler.py

The paper also describes swapping the victim’s blocks to CPU memory and copying them back later. The V1 engine dropped that path. Recompute is the only one left. The victim’s old blocks are often still on the free list when it returns, so the recompute is usually cheaper than a cold prefill.

Where the paper and the current code differ

The paper is from 2023. Three of its mechanisms are no longer what the code does.

Block size. The paper and most write-ups use 16 tokens. DEFAULT_BLOCK_SIZE is now 64. Larger blocks suit the attention kernels that shipped since.

Preemption. The paper offers swap-out and recompute. V1 implements recompute only. _preempt_request frees the blocks, sets num_computed_tokens to 0, and re-queues the request.

Sharing. The paper forks a sequence and copies the one block both children need to write, which is classic copy-on-write. V1 has no fork path. A request with n above 1 becomes n independent child requests in parallel_sampling.py, and they share the prompt through the ordinary prefix cache. Beam search moved out of the engine entirely and now sits in the entrypoints layer. Block copies still exist in V1, but only for a narrow case, which is a partial prefix-cache hit that lands inside a block.

In all three cases the blocks and the block table stayed, and the mechanism built on top of them was replaced by hashing and a shared cache.

What paging changes

“PagedAttention makes inference faster” is not quite right. What it produces is more usable KV positions per GB of GPU memory. Everything else follows from that, and only if memory was the limit.

If you were turning requests away for lack of KV, more requests now fit, so the batch gets bigger and throughput rises. That is where the paper’s 2x to 4x against Orca comes from. Time to first token can improve too, because queued requests get admitted sooner.

Per-token latency may not improve at all. It can get slightly worse, since the kernel now indexes through a block table and a larger batch makes each step longer. That is a trade of latency for throughput, and usually the right one.

If your bottleneck is compute, kernel launches, or the network, none of this helps. A GPU that was compute-bound stays compute-bound.

Output quality should not change. Same K and V, same positions, same mask, different addresses. Test that hardest, because a block-table or masking bug produces wrong text instead of a crash. Test across block boundaries, cancellations, preemption and resume, and shared prefixes.

Free HBM is not free blocks. vLLM sizes the pool once at startup from gpu_memory_utilization, and the pool shares the GPU with weights, activations, and workspace.

Summary

  • A contiguous KV cache forces you to reserve for the longest answer a request may give. Most of that reservation goes unused, and what is left over scatters into holes.
  • Paging cuts the cache into fixed-size blocks and adds a block table, which is what virtual memory does for processes.
  • Waste per sequence drops to the tail of one block. Holes disappear, because every free block is interchangeable.
  • Blocks are shared by reference count and found by hashing their tokens. vLLM enables prefix caching by default.
  • When the pool empties, vLLM frees a whole sequence’s blocks and recomputes it later. The swap path from the paper is gone.
  • The gain is concurrency. It shows up as throughput only if KV memory was the limit.

Next in this series: prefix caching, and what it costs to keep blocks around after a request finishes.

References

This post is licensed under CC BY 4.0 by the author.