The pantry of pigeonholes: PagedAttention and the vLLM block manager

Contents

Part of the under the engine series. The scheduler post ended with a loose end: the scheduler has a second budget, the KV blocks, and when they run out it preempts. This post opens up that budget. It is the piece the KV cache post took for granted, what gets stored, in order to explain how it is managed in memory. And it is the one the FlashAttention post had been promising for months.

TL;DR

The KV cache grows a little with every token generated, and the problem was never its total size but the way it is reserved. The first servers asked, per request, for a contiguous chunk of HBM the size of the maximum possible context. Since almost no request reaches that maximum, the result was catastrophic: 60-80% of the HBM wasted on fragmentation. PagedAttention applies to the KV the oldest and most battle-tested idea in operating systems, paging: split the KV into fixed-size blocks (16 tokens by default), store them in non-contiguous HBM wherever there is room, and keep a block table that translates each sequence’s logical block into its physical one. Waste falls to ~4% (only the last block, half-filled). And since each block can be identified by the hash of its content, two requests that share a prefix point at the same physical block and share memory, with copy-on-write when one of them diverges: that is the engine of prefix caching. This post explains fragmentation with numbers, the block manager, the block table, COW, the block-size trade-off, the 10 knobs and the trap of confusing “fragmentation solved” with “zero waste”. On the generic 4×H100 SXM cluster.

Where you are: the pantry, underneath the scheduler

Go back to the kitchen of the previous post. The front-of-house manager assembles trays, but behind him there is a pantry where the ingredients each table accumulates over its meal are stored, its KV cache. The question in this post is how that pantry is organised.

The naive way: each table gets a whole contiguous shelf, sized for the greediest imaginable customer. The problem is obvious: a table that orders little leaves almost all of its shelf empty, but that shelf is already reserved and nobody else can use it. With many tables, the pantry fills up with half-empty shelves and no new table fits, even though the gaps added together leave plenty of room.

The PagedAttention way: the pantry is divided into small, identical pigeonholes. Each table is given the pigeonholes it needs, one at a time, wherever there is room, and they do not have to be next to each other. A map book records which physical pigeonholes each table has and in what order. When a table leaves, its pigeonholes go back to the pile. There are no half-empty shelves: the only waste is the last pigeonhole of each table, the half-filled one. That is, almost literally, the virtual memory of an operating system applied to the KV cache.

Why contiguous memory fragmented

Reserving contiguously and up front produces three distinct kinds of waste:

Reservation fragmentation. You set aside space for max_model_len (8192 tokens, say) even though the request will use 800. Reserved and never used.
Internal fragmentation. Within what you reserved, everything above what you actually use at any given moment.
External fragmentation. Gaps between contiguous reservations that are too small for a new request, even though added together they would be plenty.

The original vLLM paper measured that earlier systems wasted 60% to 80% of the KV memory through these three routes (Kwon et al., SOSP 2023). That is: on a GPU with room for 100 real requests, only 20-40 fitted. Paging attacks all three at once. It eliminates reservation waste (on-demand allocation) and external waste (blocks need not be contiguous), and leaves only a remainder of the internal kind: the last partial block.

The mechanism: blocks, block table and the kernel gather

The KV of a sequence is chopped into logical blocks of $b$ tokens (by default $b = 16$). Each logical block is mapped, via the block table, to a physical block somewhere in the HBM. The block table is the “map book”: a per-request list of which physical block corresponds to each logical one (vLLM implementation).

The key point is that the attention kernel knows how to read like that. Instead of assuming a contiguous KV tensor, the PagedAttention kernel receives the block table and does a gather: for each sequence it walks its physical blocks in logical order and reads K and V as if they were together. That is why PagedAttention is not just a data structure: it is a kernel that knows how to attend over paged memory. And that is why the attention backend and the block manager are tied together, the second deciding where the KV lives and the first knowing how to read it from there.

The block manager: the pantry librarian

The block manager (in V1, the KVCacheManager) is the one that keeps the map book. Its responsibilities:

Maintain a pool of free physical blocks (a queue of available blocks).
Allocate blocks to a sequence as it grows (a new block every $b$ tokens).
Free the blocks when the sequence finishes or is preempted.
Maintain the block tables (logical→physical) of each request.
Manage prefix caching: detect blocks with identical content and share them.
When free blocks run out, tell the scheduler to preempt (see the scheduler post).

When the block manager says “no blocks left”, the scheduler has to take somebody off the train. That is why the two budgets, tokens and blocks, are the two hands of the same engine.

Here is the elegant part. If two requests start with the same prefix, the same system prompt, the same context document, the first KV blocks of both are identical byte for byte. Why compute and store them twice?

vLLM gives each block a hash summarising its content (the tokens that formed it, plus the hash of the previous block, so that the hash captures position). It keeps a global table of blocks by hash. When a new request produces a block whose hash already exists, it allocates no new memory: it points its block table at the physical block that was already there (automatic prefix caching, vLLM).

Copy-on-write is the safeguard: while A and B share a block, neither can modify it. The moment one of the two needs to write something different into that block (because their sequences diverge, or in parallel sampling / beam search where several branches share a prefix), the block manager copies the block for that branch and only then writes (details, vLLM). It is the same COW that fork() uses in an OS: share until somebody writes.

The saving is direct: if 50 requests share a system prompt of 1,000 tokens, instead of 50 copies of that prefix’s KV there is one. How to maximise that saving in practice is the subject of the prefix cache hit rate post.

The maths that matter: how much KV, how many blocks

KV bytes per token. For a transformer block with $L$ layers, $h_{kv}$ KV heads (GQA), per-head dimension $d$ and $s$ bytes per element (2 in FP16):

$$\text{KV/token} = 2 \cdot L \cdot h_{kv} \cdot d \cdot s$$

For a Llama-70B ($L=80$, $h_{kv}=8$, $d=128$, FP16):

$$\text{KV/token} = 2 \cdot 80 \cdot 8 \cdot 128 \cdot 2 = 327680 \text{ bytes} \approx 320 \text{ KB}$$

A block of 16 tokens takes up $16 \times 320\,\text{KB} = 5.12$ MB.

How many requests fit. If after loading the weights ~120 GB of the node’s 320 are left for KV:

$$\text{KV tokens} = \frac{120 \cdot 10^9}{327680} \approx 366000 \text{ tokens} \approx 22900 \text{ blocks}$$

With average contexts of 4,000 tokens (250 blocks each), that is ~90 concurrent requests. That number, not max_num_seqs, is the real concurrency ceiling, and it is exactly the “block budget” of the scheduler.

The waste that remains. PagedAttention does not get to zero: each sequence wastes, on average, half a block (the last one, half-filled). With 16-token blocks and sequences of 4,000, that is $8 / 4000 = 0.2\%$ per sequence, and the famous aggregate “~4%” from the paper includes other overheads. The lesson: the waste does not disappear, it is bounded to the size of one block.

The block-size trade-off

The block_size (16 by default) is a trade-off, not a magic constant:

Block	Advantage	Drawback
Small (8)	less internal waste; finer-grained prefix sharing	more block table entries; more management and gather overhead
Large (32)	fewer metadata; more efficient gather	more waste in the last block; prefix caching shares at a coarser grain (fewer hits)

A large block shares worse: prefix caching can only reuse complete and identical blocks, so with 32-token blocks two prompts that agree on 20 tokens share nothing (they do not fill a common block), whereas with 8-token blocks they share two blocks. The default of 16 is the point vLLM found reasonable for most workloads; it is worth testing if your workload has short, heavily repeated prefixes.

The 10 knobs

#	Knob	What it controls	Cost if you overdo it
1	`block_size`	tokens per block	waste / overhead (see table)
2	`enable_prefix_caching`	sharing blocks by hash	almost none; usually on
3	`gpu_memory_utilization`	how many physical blocks there are	OOM if too high
4	`kv_cache_dtype` (FP8)	bytes per KV element	quality (measure, do not assume)
5	`swap_space`	blocks that fit on the host (SWAP)	PCIe traffic on preemption
6	`max_model_len`	maximum length per request	fewer requests if too high
7	eviction policy	who gets blocks taken away	prefix cache hit rate
8	sliding window	discarding old KV	quality on long contexts
9	TP / KV sharding	splitting the KV across GPUs	NVLink traffic
10	num_gpu_blocks (override)	forcing the block count	OOM or underuse

How it connects to the rest of the stack

With the scheduler. The “block budget” of the scheduler is administered by this block manager. When it says there are no blocks, the scheduler preempts (RECOMPUTE by default).

With the KV cache. The KV cache post explains what each token stores; this one, how it is placed in memory without fragmenting.

With prefix caching. COW and block hashes are the mechanism; hit rate engineering is how to squeeze it (prompt structure, prefix-aware routing).

With KV quantisation. Moving the KV to FP8 halves the bytes/token: the same node holds twice the tokens. It is the most direct lever on concurrency.

With the attention backend. The FlashAttention/FlashInfer kernel has to know how to attend over paged blocks; the block manager decides where they live, the kernel knows how to read them.

With disaggregated serving. Moving a request from a prefill pool to a decode pool in disaggregated serving is, at bottom, transferring its KV blocks between engines, over NVLink or over the network.

With multi-LoRA. In multi-LoRA serving, the base shares prefix KV between requests from different adapters as long as the prefix is identical.

Traps and things that are not what they seem

“PagedAttention eliminates waste.” It bounds it, it does not eliminate it. What remains is the last partial block per sequence (~half a block) plus the block table metadata. It is ~4% instead of 60-80%, but it is not zero. Sizing as if it were zero leaves you without a cushion.

“Bigger blocks always perform better.” The gather is somewhat more efficient, yes, but you lose sharing granularity: prefix caching shares worse and the waste in the last block grows. On workloads with many short repeated prefixes, small blocks can win.

“Prefix caching shares KV between users, that is a privacy problem.” It shares only blocks that are identical token by token (same system prompt, same document). It does not expose one user’s content to another: if the tokens do not match, there is no common block. What is worth watching is information leaking through timing side channels (a hit is faster than a miss), relevant only in very adversarial multi-tenant scenarios.

“FP8 in the KV is free: twice the concurrency.” It does double the tokens that fit, yes, but KV in FP8 degrades quality measurably on long contexts. It is a real lever, not a free lunch: quality has to be measured (FP8 end-to-end), not assumed.

“Going back to contiguous memory would be simpler and almost as good.” That is nostalgia for the contiguous tensor. The “simple” option reintroduces 60-80% fragmentation: on a GPU, that is the difference between 30 and 90 concurrent requests. The complexity of the block table pays for itself many times over.

SWAP versus RECOMPUTE when preempting. Configuring a lot of swap_space “so as not to lose KV” puts gigabyte transfers over PCIe on the critical path. In V1, RECOMPUTE is usually better; swap is for specific cases.

Conclusion

The bottleneck in serving an LLM was never only how much memory you have, but how you hand it out. The first servers treated the KV cache as a contiguous shelf per client and threw two thirds of the HBM in the bin without it showing up on any dashboard. PagedAttention stole from the operating system its best idea of fifty years ago, paging, and applied it at the exact place where it hurt: small pigeonholes, a map book, on-demand allocation and, as a bonus, the possibility that two requests starting the same way share the same pigeonholes until they stop resembling each other. The result is not magic: the waste is still there, but bounded to the size of one block instead of to the size of the worst imaginable case. And that difference, from 70% to 4%, is what turned a GPU serving thirty clients into one serving ninety, without touching the hardware. The pantry did not get bigger; it got better organised.

References

W. Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023): https://arxiv.org/pdf/2309.06180.
vLLM, Automatic Prefix Caching (design, block hashing): https://docs.vllm.ai/en/v0.8.1/design/automatic_prefix_caching.html.
vLLM, Automatic Prefix Caching — Implementation (block table, COW): https://docs.vllm.ai/en/v0.6.1/automatic_prefix_caching/details.html.
H. Elshafie, Paged Attention from First Principles: A View Inside vLLM: https://hamzaelshafie.bearblog.dev/paged-attention-from-first-principles-a-view-inside-vllm/.
vAttention: Dynamic Memory Management for Serving LLMs without PagedAttention (alternative, critical context): https://arxiv.org/pdf/2405.04437.