Why architecture matters here
The architecture matters because KV-cache memory management is the binding constraint on LLM serving throughput, full stop. Modern GPUs have far more compute than they can use if requests are served one or two at a time; the way to keep the tensor cores busy is to batch many sequences together. But every sequence in the batch needs its KV cache resident in GPU memory simultaneously, so the number of sequences you can batch is capped by how efficiently you pack their caches. Waste 70% of KV memory to fragmentation and you batch a third as many requests and get a third of the throughput at the same hardware cost.
It matters because the waste in the naive design is structural, not incidental. Pre-allocating for the maximum sequence length wastes everything between the actual and the maximum length — internal fragmentation that grows with how much you overestimate. Allocating variable-sized contiguous chunks instead creates external fragmentation, where free memory exists but not in a contiguous piece large enough for the next request. Paging eliminates both: block-granular allocation caps internal waste at one block per sequence, and because any free block can satisfy any request, there is no external fragmentation at all.
It matters because the indirection through a block table is what makes sharing possible, and sharing is a second multiplier on top of the fragmentation win. A production endpoint serves thousands of requests that all begin with the same long system prompt; without sharing, each request stores its own identical copy of that prompt's KV cache. With paged blocks and reference counting, they all point at one copy, and the memory saved becomes room for more concurrent requests. The same mechanism makes parallel sampling and beam search cheap, because the branches share the common prefix's blocks until they diverge.
It matters because the design gives the scheduler a currency it can manage: blocks. When memory runs short, the serving system can preempt a sequence by freeing (or swapping out) its blocks and recomputing or restoring them later, because the block table captures exactly which memory a sequence owns. That turns an out-of-memory crash into a graceful, recoverable scheduling decision — the difference between a serving system that degrades under load and one that falls over.
Finally it matters because the abstraction is clean enough to reason about and to build on. The block table is a page table; the block manager is a memory allocator; copy-on-write is copy-on-write. Engineers already understand these primitives, so the KV cache stops being a bespoke, fragile slab and becomes a managed resource with well-understood behavior — which is exactly why PagedAttention spread from a research paper into the default serving architecture across the industry.
The architecture: every piece explained
The fundamental unit is the KV block: a fixed-size chunk of GPU memory holding the key and value vectors for a small, constant number of contiguous token positions — 16 is the common choice. All blocks are the same size, which is what makes them interchangeable and what turns allocation into simply handing out identical slots from a pool. A sequence's full KV cache is just an ordered list of these blocks, most of them completely full and at most one — the last — partially filled.
Each sequence owns a block table, the direct analogue of a page table. It is a small array mapping each logical block index (position 0-15 -> logical block 0, 16-31 -> logical block 1, and so on) to the physical block that currently holds those tokens' keys and values. When the attention kernel needs the KV for logical position 40, it consults the table to find which physical block holds logical block 2 and reads the right offset within it. The table is the indirection that lets the physical blocks be scattered anywhere while the logical view stays contiguous.
The block manager is the allocator and the reference counter. It owns the global pool of physical blocks, hands one out when a sequence's current block fills, and returns blocks to the free pool when a sequence completes or is preempted. Crucially it keeps a reference count per physical block, so a block shared by several sequences (a common prefix, several beam branches) is only truly freed when the last referrer releases it. That reference count is the mechanism behind copy-on-write sharing.
Copy-on-write sharing is the block manager's most powerful trick. When two sequences share a prefix, their block tables point at the same physical prefix blocks and the reference count reflects both. As long as both only read those blocks — which is the case while attending over the shared history — nothing is copied. The instant one sequence needs to write into a shared block (its generation diverges within a block that is still partially shared), the manager copies just that one block, points the writer's table at the copy, and decrements the original's count. Sharing is free until divergence, and divergence costs exactly one block copy.
Finally the attention kernel is written to consume this layout directly. Rather than requiring the KV cache in one contiguous tensor, the PagedAttention kernel takes the block table and gathers the relevant blocks on the fly as it computes attention scores, reading each block from wherever it physically lives. This is the piece that makes the whole scheme practical: the cache is never reassembled into contiguous form, so the paging is invisible to the math and costs only the small overhead of an extra indirection per block access.
End-to-end flow
Trace a request through the pager. It arrives with a prompt of, say, 300 tokens. The scheduler asks the block manager for enough blocks to hold the prompt's KV cache: 300 tokens at 16 per block is 19 blocks. The manager pulls 19 physical blocks from the free pool and writes their addresses into the request's new block table. The prefill pass then runs the whole prompt through the model in one shot, computing keys and values for all 300 positions and writing them into those 19 blocks via the table.
Now decode begins, one token per step. The model generates token 301, computes its key and value, and needs somewhere to put them. Logical block 18 (holding tokens 288-303) has room, so the KV go there and no new block is needed. The attention computation for this step gathers all 19 blocks through the table, attends over the full 301-token history, and produces the next token. Each subsequent step appends one token's KV; every 16 steps the current block fills and the manager hands out one fresh block, appended to the table.
Suppose this request shares its 300-token prefix with a second request that arrives moments later — same system prompt. Instead of allocating 19 new blocks and recomputing the prefix, the scheduler points the second request's block table at the same 19 physical blocks and bumps their reference counts to two. The second request skips almost all of prefill, starting generation from a shared cache. Both sequences read those blocks freely; neither writes into them because both are past the prefix and appending into their own private blocks.
Consider what happens when memory runs low mid-generation. The scheduler must admit a new high-priority request but the free pool is empty. It preempts a running sequence: it either swaps that sequence's blocks out to CPU memory (recording their contents) or discards them entirely, freeing them to the pool, and marks the sequence for later resumption. When capacity returns, the sequence is restored — swapped back in, or its KV recomputed from the prompt — and it continues. The block table made this clean, because it names exactly which memory to reclaim and how to rebuild it.
Finally the request finishes — it hits a stop token or the length limit. The scheduler tells the block manager to release the request's blocks. For blocks owned solely by this request, the reference count drops to zero and they return to the free pool immediately, available for the next arrival. For shared prefix blocks, the count merely decrements, and the memory stays live for the other sequences still using it. The pool breathes: blocks flow out on admission and back on completion, continuously, with no long-lived reservations and no fragmentation accumulating over time.