Paged Attention › Summary

PagedAttention transforms LLM inference efficiency by applying virtual memory principles to KV cache management. The key insights and techniques include:

• The fragmentation problem arises because traditional KV cache allocation reserves contiguous memory based on maximum sequence length. This causes internal fragmentation (unused space within allocations) and external fragmentation (scattered free blocks that cannot be combined). Together, these issues can waste 60-80% of available memory.

• Page-based allocation divides memory into fixed-size blocks that can be assigned to any sequence. A block table maps each sequence's logical blocks to their physical locations. This approach eliminates external fragmentation entirely and reduces internal fragmentation to at most one partial block per sequence.

• The PagedAttention algorithm modifies attention computation to work with non-contiguous KV storage. During attention, keys and values are gathered according to the block table. Optimized CUDA kernels perform this gathering efficiently using online softmax techniques, processing blocks one at a time without requiring an explicit gather step.

• Copy-on-write semantics enable memory-efficient beam search and other parallel decoding strategies. Sequences can share physical blocks for common prefixes, with new blocks allocated only when sequences diverge. This can reduce KV cache memory for beam search by 50% or more.

• Practical benefits include 2-4x higher throughput from increased batch sizes, support for continuous batching with dynamic request handling, preemption capabilities for priority scheduling, and near-optimal memory utilization that removes the capacity waste endemic to contiguous allocation.

• Limitations include block-table lookup overhead (small but non-zero), the complexity of choosing optimal block sizes, the implementation difficulty of production-quality paged attention CUDA kernels, and the fact that paging addresses capacity but not bandwidth.

These improvements have made PagedAttention the foundation of modern LLM serving systems including vLLM, TensorRT-LLM, and others. Understanding its design helps you configure these systems effectively, predict where they will perform well, and recognize the workload characteristics that determine how much benefit you will see in practice.