Paged Attention › Limitations and Practical Considerations

While PagedAttention represents a major advancement in LLM serving efficiency, it comes with trade-offs and limitations worth understanding in depth. No technique is universally superior, and a clear-eyed view of PagedAttention's limitations helps you make better deployment decisions and anticipate where the technique may not deliver its advertised benefits.

The most basic overhead is the block table indirection itself. Every attention computation must look up physical block locations from the block table before reading the KV data. On GPU hardware, this means an extra pointer dereference per block, which disrupts the memory access pattern that standard attention kernels have been optimized for. Modern GPU memory systems work best with sequential, coalesced access patterns; paged access introduces non-sequential accesses that can reduce effective memory bandwidth. For very short sequences (50-100 tokens), this overhead can outweigh the memory savings, because short sequences fit in one or two blocks and the fragmentation savings are minimal. Most serving workloads involve longer sequences where the memory efficiency gains far exceed the indexing overhead, but if your workload consists primarily of short requests, you should benchmark carefully before assuming PagedAttention will help.

Block size selection presents a tuning challenge with no universally correct answer. Smaller block sizes (8 or fewer tokens per block) reduce internal fragmentation: the worst case is that the last block is only partially filled, so smaller blocks limit the maximum wasted space. But smaller blocks mean longer block tables, more block-table lookups per attention step, and potentially worse memory access locality as more physical block boundaries are crossed during a single attention computation. Larger block sizes (32 tokens or more) are more efficient for the memory access pattern but guarantee more waste at block boundaries. The default block size of 16 tokens in vLLM represents a carefully chosen balance, tuned against real serving workloads, but your specific workload distribution may benefit from a different value. Workloads with highly variable sequence lengths often benefit from smaller blocks; uniform-length workloads can use larger blocks without meaningful fragmentation cost.

Implementing PagedAttention from scratch is complex. Custom CUDA kernels must handle the non-contiguous memory access patterns efficiently while maintaining the performance characteristics of optimized attention implementations. The kernel must correctly implement the online softmax algorithm, handle partial last blocks, and coalesce memory accesses as much as possible across threads within the same warp. These are non-trivial requirements, and subtle bugs can produce incorrect results that are difficult to detect without careful testing. This is why you should use established frameworks like vLLM, TensorRT-LLM, or similar rather than implementing PagedAttention from scratch. The engineering investment to get a production-quality implementation right is substantial.

A subtler limitation is that PagedAttention addresses memory capacity constraints but not the basic memory bandwidth limitations of KV cache access. Even with perfect memory utilization, the KV cache still requires significant memory bandwidth to read during attention computation. For long sequences and large models, this bandwidth cost can be the dominant bottleneck, and no amount of clever allocation can reduce it. Techniques covered in later chapters, such as KV cache compression, quantization, and multi-query attention, complement PagedAttention by reducing the amount of data that must be transferred, rather than just improving how that data is laid out.

Finally, there is a coordination overhead in multi-GPU serving. When a model is distributed across multiple GPUs using tensor parallelism, each GPU must maintain consistent block tables for the KV shards it holds. Block allocation and deallocation must be coordinated across all GPUs simultaneously, which adds communication overhead and complexity. Single-GPU serving enjoys the simplest possible block management, while large multi-GPU deployments must handle this synchronization carefully to avoid inconsistencies.