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.
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.
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.
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.
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.
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.
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”.
Picking a block size
Blocks are the unit of allocation, so their size trades two costs against each other.
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.
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.
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
- Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023. arXiv
- vLLM source, in
kv_cache_manager.py,block_pool.py,kv_cache_utils.py, andscheduler.py. - vLLM PagedAttention kernel design and the vLLM architecture walkthrough
- NVIDIA TensorRT-LLM KV cache management, a different block manager for the same problem
- Prabhu et al., vAttention, which keeps contiguous virtual addressing and pages the physical memory underneath. arXiv
- Meta Llama 3.1 model configuration, the source of the 320 KiB per token figure