PagedAttention gives you the idea — store the KV cache in fixed-size blocks instead of one contiguous slab, and a serving engine stops wasting memory on reserved-but-unused context. This article goes one level down, into the machinery that makes that idea pay: the block manager. How big should a block be, and what does that cost you in fragmentation versus bookkeeping? How does the block table translate logical positions into physical blocks, and how does reference counting let two requests share the same physical KV? What happens when a shared prefix — a system prompt every request carries — is computed once and reused? And when memory runs out, is it cheaper to recompute a sequence’s blocks or swap them to host RAM? We do the block accounting explicitly and work a prefix-caching example end to end.
From the concept to the block manager
The companion article, PagedAttention — Math + Memory Model, establishes the core move: the KV cache for a sequence no longer lives in one contiguous, max-length reservation but in a list of fixed-size blocks drawn from a shared pool, so you only pay for context you have actually generated. This piece assumes that and goes deeper into the component that implements it — the block manager. Its job is narrow but load-bearing: hand out physical blocks on demand, keep a per-sequence map from logical token positions to those physical blocks, track how many sequences point at each block, and decide what to evict when the pool is empty.
Everything interesting about paged serving throughput lives here, not in the attention kernel. The kernel just follows pointers; the block manager decides how much memory is wasted, whether two requests can share a prompt, and how gracefully the system degrades under pressure. Get it right and a fixed pool of GPU or CPU memory serves noticeably more concurrent sequences at the same latency.
Block size: the one knob that sets everything
A block holds a fixed number of tokens’ worth of keys and values — call it B, the block size in tokens (common values are 16 or 32). B is the single most consequential knob in the design, because it sits at the center of a direct trade-off. A small B wastes little memory on the partially filled last block, but produces many blocks per sequence — more block-table entries, more allocator calls, more pointer indirection. A large B keeps the table short and the allocator quiet, but the tail of every sequence rounds up to a full block, wasting the unused slots.
The number of blocks a sequence of length L needs is simply blocks = ⌈L / B⌉. That ceiling is the source of internal fragmentation: unless L is an exact multiple of B, the final block is under-filled. Crucially, paged serving turns the old problem — reserving L_max per sequence — into a tiny bounded one: at most B - 1 wasted tokens per sequence, regardless of how long the context might have grown.
The block-accounting math
Let us size a real cache. Take a model with n_layers = 32, n_kv_heads = 8 (grouped-query attention), head_dim = 128, stored in fp16 (2 bytes). Every token stores both a key and a value, so the bytes per token are:
bytes_per_token = 2(K,V) × n_layers × n_kv_heads × head_dim × bytes
= 2 × 32 × 8 × 128 × 2 = 131072 = 128 KiB / tokenWith B = 16, one block is 16 × 128 KiB = 2 MiB. Now the fragmentation cost. A partially filled final block wastes, averaged over many sequences, about B/2 tokens — here 8 tokens, or 1 MiB per sequence; across 200 concurrent sequences, roughly 200 MiB. Compare contiguous pre-allocation to L_max = 8192: a sequence only 512 tokens long would reserve (8192 - 512) × 128 KiB ≈ 960 MiB each — the paged scheme’s ~1 MiB of waste is roughly three orders of magnitude smaller. That gap is the entire reason paging exists.
The block table: logical to physical
Each sequence owns a block table — an array indexed by logical block number that stores the physical block ID holding those tokens. To find the KV for token position t, the engine computes logical_block = t / B and offset = t mod B, looks up physical = block_table[logical_block], and reads slot offset inside that physical block. This is exactly virtual-memory page-table translation, borrowed wholesale from operating systems — the block table is a page table and the pool is physical memory.
The payoff of this indirection is that a sequence’s blocks need not be contiguous or even in order; the allocator hands out whatever is free. That eliminates external fragmentation entirely — there is never a ‘large enough contiguous hole’ problem, because no allocation exceeds one block. The cost is the extra read to consult the table, whose length grows with ⌈L / B⌉ — why very small B inflates metadata.
Reference counting and copy-on-write
Because a physical block is addressed only through block tables, nothing stops two sequences’ tables from pointing at the same physical block. To make that safe, every physical block carries a reference count: the number of block tables currently referencing it. A block is returned to the free pool only when its count falls to zero. Allocation increments; freeing a sequence decrements every block it held.
Sharing is only safe while the shared blocks stay read-only. The moment one sharer needs to write into a shared block — append a token, or a beam-search branch diverges — the manager performs copy-on-write: allocate a fresh block, copy the shared contents in, point the writer’s table at the copy, and decrement the original’s count. Reference counting plus copy-on-write is the exact mechanism that makes prefix sharing and parallel-sampling forks of one prompt both correct and cheap — identical context stored once until someone actually diverges.
Prefix caching: sharing a common prompt
Prefix caching (automatic prefix sharing) is the highest-value use of reference counting. Many requests to the same deployment begin with an identical span — a long system prompt, a few-shot preamble, a retrieved document. Prefill recomputes that span’s KV every time, and every copy sits in the pool. Prefix caching detects the shared prefix, computes its KV once, and lets every request point its block table at those same physical blocks.
The critical deep-dive detail is that sharing is block-aligned. Only full blocks with identical contents can be shared; the single block straddling the boundary between the shared prefix and where requests diverge cannot be. Detection works by hashing block contents — each block is keyed by a hash of its own tokens chained with the hash of all preceding blocks, so two blocks match only when their entire prefix history matches. On a hit the manager bumps the reference count instead of allocating and skips the prefill; on a miss it computes and inserts, so the cache warms itself.
A worked prefix-caching example
Suppose a chat service prepends a 512-token system prompt to every request. With B = 16, that prefix is exactly 512 / 16 = 32 full blocks — cleanly aligned, so all 32 are shareable. Reusing the numbers above, the prefix’s KV is 512 × 128 KiB = 64 MiB, or 32 blocks of 2 MiB.
100 concurrent requests, 512-token shared prefix, B = 16
without sharing: 100 × 32 = 3200 blocks = 6336 MiB ≈ 6.2 GiB
with sharing: 1 × 32 = 32 blocks = 64 MiB (refcount = 100)
saved: 3168 blocks ≈ 6.2 GiB, and 99 × 512 ≈ 50,700 prefill tokensThe win is two-sided: 6.2 GiB of pool freed for more concurrent sequences, and roughly 50k prefill tokens skipped, cutting time-to-first-token for every cache-hitting request. Note the alignment sensitivity: had the prompt been 500 tokens, only 31 full blocks (496 tokens) would share; the 32nd, partly filled, stays private — a small tax that argues for keeping fixed preambles a multiple of B tokens.
Preemption: recompute vs swap to CPU
Demand is bursty, so a well-run pool will occasionally have no free block for a sequence that needs to append a token. Rather than fail, the manager preempts a victim sequence, reclaiming its blocks, and resumes it later. There are two ways to preserve the victim’s state, and the choice is a real trade-off.
Recomputation frees the blocks and, when the sequence is rescheduled, re-runs prefill over its tokens to rebuild the KV. It costs no extra memory and no data movement, but repeats compute — and because prefill is a parallel, compute-bound pass over all tokens at once, it is often cheaper than it sounds. Swapping instead copies the victim’s blocks out to host (CPU) RAM and back on resume. It never repeats compute, but pays twice for PCIe/bus bandwidth and needs a host-side swap area. Rule of thumb: recomputation wins for short sequences and when compute is cheaper than bandwidth; swapping wins for long sequences whose re-prefill would be very expensive.
The block allocator and throughput
The allocator sits on the hot path: every decode step may append a token and, once every B tokens, request a fresh block. To keep that cheap, real implementations hold the free pool as a free list or stack of block IDs, so allocate and free are O(1) pushes and pops, not searches. There is no compaction and no coalescing, precisely because uniform block size removes the need for them.
This is where the block-size trade-off resurfaces as a throughput question. Smaller B means blocks fill up faster, so allocations happen more often and block tables are longer, adding per-step overhead and pointer chasing in the kernel. Larger B quiets the allocator and shortens tables but coarsens both fragmentation and prefix-sharing granularity (you share only in B-token units). The manager also enables continuous batching: because sequences hold only the blocks they use, finished sequences free their blocks instantly and new ones slot into the freed capacity mid-batch — which is what keeps utilization, and tokens per second, high.
On CPU and small-model serving
On CPU-hosted small language models the block manager matters for a slightly different reason: memory is plentiful but bandwidth is the bottleneck, and the KV cache is read in full every decode step. Paging does not shrink that read, but prefix caching helps: skipping 50k prefill tokens is a large fraction of the work for a small model, and time-to-first-token dominates the felt latency of a local assistant.
The preemption calculus also shifts. Host RAM is the compute memory, so ‘swap to CPU’ loses its meaning; recomputation is the natural fallback, and for small models a re-prefill is fast. A sensible default: a modest block size (16 is a fine start), prefix caching on for any workload with fixed preambles, and recomputation as the preemption policy — keeping the allocator O(1), fragmentation near B/2 tokens per sequence, and the pool dense with useful context.