KV Cache Paging

PagedAttention (used by vLLM) borrows an idea from OS virtual memory to manage the KV cache. What does it change versus reserving one contiguous buffer per sequence sized to the max sequence length, and what does that change enable?

It offloads the KV cache for a sequence's oldest tokens to CPU RAM once the sequence passes a length threshold, paging blocks back onto the GPU on demand exactly like OS disk swap, so GPU memory stays flat regardless of sequence length.

It eliminates the KV cache altogether by recomputing attention over the full prompt at every decoding step, trading extra FLOPs for zero cache memory.

It splits each sequence's KV cache into fixed-size blocks that can sit at non-contiguous physical memory locations, tracked through a per-sequence block (page) table; this bounds fragmentation to roughly the sequence's last partially-filled block, and lets requests sharing an identical prefix (e.g. a common system prompt, or parallel sampling from one prompt) share the same physical blocks via copy-on-write instead of duplicating them.

It compresses the KV cache in place with product-quantization codebooks trained per layer, cutting memory footprint roughly 4x at a small perplexity cost, independent of how the cache is laid out in memory.

It preallocates one shared contiguous buffer sized for the whole batch's worst-case total token count, then relies on a custom in-place defragmenting allocator rather than block tables to reclaim freed space between decoding steps.