A server may run out of KV-cache capacity while many reserved token slots remain empty. Variable-length requests make advance reservation convenient but expensive: the server must allow growth without knowing exactly how much of that allowance each request will use.
PagedAttentionAn attention method that reads cached keys and values from separately allocated blocks. organizes a request's KV cache into fixed-size blocks that need not occupy one contiguous region. Logical-to-physical mappings let the serving system allocate blocks as needed and share suitable blocks across sequences. The paper describes copy-on-writeShare stored data until a writer needs its own changed copy. when shared blocks must diverge. PagedAttention paper
The PagedAttention paper reports 2–4× higher throughput than its FasterTransformer and Orca comparisons at equivalent latency in the evaluated configurations. Memory efficiency makes larger effective batches possible, but the end-to-end result also depends on serving kernels and workload. The accounting below isolates what the allocator changes before assigning it any throughput gain.
Count occupied tokens and allocated slots separately
Take three synthetic requests whose current lengths are 5, 9, and 17 tokens. Their useful cache contains 31 token positions. Suppose a simple contiguous policy reserves 32 positions for every request. It allocates 96 slots, leaving 65 unused at this snapshot.
With four-token pages, the requests need 2, 3, and 5 pages. Allocation falls to 40 slots, with nine unused tail slots. Eight-token pages allocate 48 slots, leaving 17 unused. Sixteen-token pages allocate 64 slots, leaving 33 unused.
The calculation is ceiling(length/page_size) × page_size per request. It illustrates internal tail waste, not a simulation of allocator holes or a measured vLLM memory footprint. The contiguous comparison specifically assumes maximum-length reservation; contiguous allocation does not inherently require reserving this much in every possible design.
Smaller pages reduce the final-page slack, but the arithmetic alone cannot select the best page size. Page-table metadata, lookup overhead, kernel access patterns, and allocation frequency also matter. A one-token page looks ideal if unused slots are the only cost in the model.
Sharing changes the accounting again
Now consider two requests of lengths 20 and 23 with an identical eight-token prefix. At page size four, separate allocation uses 20 + 24 = 44 slots. If the two complete prefix pages can be shared, physical allocation falls by eight slots to 36.
The logical requests still contain 43 token positions in total. Physical storage is lower because eight of those positions refer to the same cached prefix. This is a different effect from reducing unused capacity, so a chart should not lump both into one category called fragmentation.
A correct sharing decision requires more than similar text. The cached tensors must correspond to compatible model computation and the same prefix context. Once a branch writes a different continuation, shared mutable storage needs appropriate separation. The example only shares complete, unchanged prefix blocks and performs no copy-on-write simulation.
The included CPU calculation keeps these two effects distinct: page-tail slack for independent requests, then a separate complete-prefix sharing case. It never executes attention or predicts request throughput.
A practical cache study should also record growth over time, deallocation, admission decisions, and requests blocked by memory pressure. A favorable static snapshot cannot reveal whether a policy repeatedly forces eviction or recomputation during bursts.
A page-size optimum needs a cost beyond slack
The extended calculation adds a deliberately abstract per-block metadata cost. Let c be that cost in token-slot equivalents. The total objective is allocated token slots plus c times the number of blocks. This common unit is only an accounting convention; actual metadata bytes must be converted using the cache bytes per token for the intended model.
For the three request lengths, the best tested page size is one slot when c = 0, two slots when c = 0.25, four slots when c = 1, and eight slots when c = 4. Their respective total costs are 31, 38.25, 50, and 72 token-slot equivalents. Those optima are over the tested powers of two, not a universal recommendation for a vLLM block setting.
The result makes a boundary of the original demonstration explicit. Counting only unused slots makes tiny pages appear unconditionally attractive. Charging once per block can reverse the ranking without changing a single request length. A real decision also needs the cost of indirect accesses and the kernel's supported layouts, which need not be expressible as a fixed metadata charge.
Prefix sharing remains separate in the data. For the two branches of lengths 20 and 23, each additional complete four-token prefix block shared saves four physical slots. Neither the sum of logical token lengths nor the page-tail slack alone tells you the number of distinct cached tensors. Keeping those three quantities separate prevents a memory-efficiency chart from counting the same saving twice.