Paged KV-cache management
Explain PagedAttention’s allocator and kernel implications
Before you begin
Follow a linked prerequisite when you cannot explain it from memory. Background skills without links are stated as abilities rather than hidden terminology.
- KV memory formula
- Virtual pages and page tables
- Fragmentation
The 7-billion-parameter server reserves one contiguous key-value region for each request's maximum context length. A request that stops at 700 tokens can strand space reserved for tens of thousands of unused token positions. Other requests may leave differently sized holes after completion. A memory report can show substantial free bytes spread across regions while the allocator still cannot find one sufficiently large contiguous region for a new long request.
A paged allocator divides key-value storage into fixed-size physical blocks, such as blocks that hold 16 token positions. Each request owns a small table that maps logical token ranges—positions 0 through 15, 16 through 31, and so on—to physical blocks that need not be adjacent. Allocation logs report block assignments and releases; an attention kernel reads the block table to locate each requested token's keys and values.
A sequence's KV cache grows one token at a time but conventional contiguous allocation asks for a large continuous region in advance or moves data when growth exceeds it. Reserving maximum length wastes capacity; exact contiguous growth fragments memory and complicates relocation. Paging separates logical token order from physical blocks.
PagedAttention and vLLM separate a sequence's logical KV blocks from fixed-size physical cache blocks. A request's block table records the mapping. Physical blocks can be allocated as tokens arrive, released at completion, and shared under controlled ownership. Attention kernels follow the table instead of assuming one contiguous KV array.
The block-table design addresses internal and external memory waste in request-level KV allocation. PagedAttention does not require the GPU's hardware virtual-memory system to perform ordinary demand paging. The serving runtime manages block ownership, and the attention kernel interprets the logical-to-physical mapping explicitly.
Map logical token positions to physical blocks
Choose a block size B in tokens. Logical token position t belongs to logical block floor(t / B) and offset t mod B. The request's block table maps that logical block to a physical block number. The final address also includes layer, KV head, head dimension, datatype layout, and any tensor-parallel partitioning.
When a sequence appends a token and its current final block has a free slot, the new key and value are written at the next offset. When the block is full, the allocator assigns another physical block and appends its identifier to the block table. Completion returns uniquely owned blocks to the free pool after no in-flight kernel can access them.
A branch or shared prefix can make several logical sequences reference the same physical blocks. Reference counts protect those blocks. If a sequence must modify a shared partial block, copy-on-write creates a private block before the write. Fully immutable prefix blocks can remain shared without copying.
Choose block size from waste and execution cost
Smaller blocks reduce unused positions in the final block. Under a roughly uniform remainder, average tail waste is approximately (B - 1) / 2 tokens per sequence. Multiplying this value by active sequence count and KV bytes per token converts a small token number into actual device capacity.
Smaller blocks also create longer block tables, more allocator operations, and more address boundaries for attention. Larger blocks reduce metadata and can provide longer contiguous regions, but they strand more final-block capacity and make prefix sharing or eviction less granular. The kernel's vector and tile organization can favor particular block sizes.
Measure memory and execution together. Report physical allocated tokens, logical tokens, tail waste, free-block reserve, table bytes, allocation time, attention duration, and end-to-end goodput. A lower fragmentation percentage is not useful if the attention kernel or scheduler loses more capacity than the saved blocks provide.
Length distribution matters more than maximum context alone. If most requests end near multiples of a candidate block size, measured tail waste can be much lower than the uniform-remainder estimate. Prefix sharing also favors boundaries that align with repeated prompt segments. Use the analytical estimate to understand the mechanism and a replay to select the deployed size.
Protect ownership across scheduling and kernels
The allocator, scheduler, and kernel share one lifetime protocol. The scheduler must not admit work based on a block that another operation still owns. The allocator must not recycle a block while a queued or running kernel can read it. Cancellation must eventually free state without invalidating submitted work.
Eviction and preemption add more transitions. If a sequence's cache is discarded, the scheduler must record the range that needs recomputation. If state moves to host memory, the next scheduling decision must include transfer completion. If physical compaction relocates blocks, all references and in-flight-use rules must remain valid.
Attention reads logical context through block tables. The original PagedAttention design co-designed allocator and kernel behavior so non-contiguous physical storage remains usable. Treat the mapping format as a kernel interface. Changes to block size, cache dtype, or layout need both allocator tests and attention-performance measurements.
bytes = 2 × layers × KV heads × head dim × bytes/value × tokensAdd page tails, metadata, replication, workspaces, and safety headroom; subtract only real sharding or sharing.
Worked example: Choosing a KV block size
Request lengths vary widely, with many short conversations and a long tail. Candidate block sizes are 16 and 128 tokens.
- Estimate expected tail waste. Under a roughly uniform remainder, average unused space approaches half a block: about 7.5 versus 63.5 tokens per request.
- Convert wasted tokens into bytes using the model's per-token KV ledger and active concurrency. Large blocks may consume several GiB of otherwise usable capacity.
- Measure page-table size, allocation operations, and attention-kernel efficiency. The 16-token design may require more lookups and less contiguous vectorization.
- Replay real lengths and concurrency. Choose from goodput and memory headroom, not fragmentation percentage or kernel speed alone.
Conclusion: Block size affects allocator efficiency and attention access. Select the size that minimizes total system cost under the declared workload.
Common errors
- Calling paging virtual memory and assuming hardware manages it. The serving runtime and kernel explicitly implement this logical mapping.
- Ignoring block-tail waste because blocks are small. Per-token cache bytes and high concurrency can amplify modest waste.
- Compacting physical pages without respecting in-flight kernels and shared prefixes. Relocation is a synchronization and ownership problem.
Reference summary
Paged KV management divides cache storage into fixed-size physical token blocks. Each sequence has a table that maps logical blocks in token order to physical blocks. The allocator adds blocks as the sequence grows and releases them after safe completion.
Reference counts permit immutable prefix blocks to be shared. A branch that writes a shared partial block first creates a private copy. The attention kernel follows block tables, so block size and physical layout affect both allocator waste and kernel access cost.
- Smaller blocks reduce tail waste but increase metadata and address-translation overhead.
- Larger blocks improve sequential locality but strand more unused slots in final blocks.
- The attention kernel gathers logical token ranges through block tables rather than assuming one contiguous pointer.
- Allocator operations and scheduler decisions must remain inexpensive at high request rates.
- Reference counts and copy-on-write protect shared prefixes from mutation.
Knowledge check
What happens to memory waste and lookup overhead when KV block size is cut in half?
Show the answer guide
- Halving KV block size roughly halves the maximum unused tail capacity per sequence and lowers average internal fragmentation when sequence endpoints are not aligned to block boundaries.
- The same retained token count now needs about twice as many block identifiers. Block tables, reference counts, allocator operations, and metadata therefore increase.
- Attention kernels must perform more page translations and cross more block boundaries. Smaller contiguous runs can increase lookup instructions, reduce memory coalescing, and complicate prefetching.
- The net effect depends on sequence-length distribution and kernel implementation: memory capacity usually improves, while lookup and scheduling overhead usually rise. Measure both physical bytes and decode latency before selecting a block size.
Sweep KV page size under a fixed length distribution
Use a paged-KV simulator or model server with block sizes 8, 16, 32, and 64 tokens. Allocate a fixed trace of 2,000 concurrent sequence lengths sampled from declared buckets 1-64, 65-512, 513-4096, and 4097-16384, then run decode steps for the same active sequences.
Evidence to keep: Submit the length trace and allocator code or configuration, a table of logical tokens, physical token slots, tail waste, block-table entries, allocation operations, and decode latency for each block size, plus plots of fragmentation and latency. Identify the block size that best satisfies a declared memory reserve and TPOT limit.
Once pages can be shared safely, repeated prompt prefixes become reusable computation and memory rather than repeated prefill work.
Sources and further reading
The lesson explanations synthesize primary papers and official references. Follow the originals for proofs, exact APIs, architecture details, and version-sensitive behavior.
- Orca: Iteration-Level Scheduling↗
- PagedAttention / vLLM↗
- SGLang↗
- NVIDIA Nsight Systems User Guide↗
Official reference for capturing and reading CPU, CUDA API, GPU workload, and communication timelines.