Paged Attention › Paged Attention

In the previous two chapters, we explored how KV caches accelerate autoregressive generation by avoiding redundant computation, and we examined the substantial memory costs this optimization incurs. As we saw, a single 70B parameter model can require over 2.5 GB of KV cache memory per sequence at full context length. When serving multiple concurrent requests, this memory demand becomes the primary bottleneck limiting throughput. The KV cache was supposed to be a performance win, and it is, but the way most systems implemented it created a new and equally severe problem that canceled out much of that gain.

The problem is memory fragmentation. Even when the GPU has sufficient total free memory, the way that memory is allocated and deallocated can leave large portions of it unusable. Imagine a parking lot where every car must park in a space exactly as large as the longest car ever recorded, even if the actual car is a compact. Most of that parking lot will be empty, and yet you'll keep turning away new cars because there's "no room." That is essentially what happens with traditional KV cache implementations, which can waste 60-80% of available GPU memory, dramatically reducing the number of sequences a server can process simultaneously.

PagedAttention, introduced by the vLLM project in 2023, solves this fragmentation problem by borrowing a basic concept from operating systems: virtual memory with paging. Instead of allocating contiguous memory blocks for each sequence's KV cache, PagedAttention breaks the cache into fixed-size pages that can be stored anywhere in memory. A simple translation table then maps the logical view of each sequence (a tidy, contiguous cache) to the physical reality (blocks scattered wherever space is available). This simple but powerful idea enables near-optimal memory utilization and has become the foundation for most modern LLM serving systems.

The impact of this design choice is concrete and dramatic. Systems using PagedAttention routinely achieve 2-4x higher request throughput compared to naive implementations, using exactly the same hardware and model. This improvement comes entirely from using memory more intelligently, not from any change to the model itself or to the underlying attention algorithm. You do not need a bigger GPU; you need a smarter allocator.

In this chapter, we build from the ground up. We start with why traditional allocation fails so badly, work through the paging concept in detail, examine how the attention algorithm must be modified to accommodate non-contiguous storage, and then look at how vLLM puts all these pieces together into a production serving system. Along the way, we work through concrete numerical examples and build a simulator that makes the abstract concepts tangible. By the end, you will understand what PagedAttention does, why it works, and when its trade-offs matter.