LLM serving becomes a memory-management problem as soon as many requests with different prompt and generation lengths share the same accelerator. The model weights may fit comfortably, yet the key-value cache for active sequences can still determine how many requests remain resident at once.
PagedAttention addresses that pressure by changing how the KV cache is allocated and mapped. The important idea is not that every attention operation suddenly becomes cheaper. It is that cache storage no longer has to behave like one oversized contiguous reservation for each request.
What PagedAttention actually solves
The KV cache stores attention key and value tensors that the model will need again during autoregressive decoding. Reusing them avoids recalculating the same historical attention state at every token step, but the cache grows with the amount of context retained and the number of active sequences.
That growth is awkward for a serving system because sequence length is not known perfectly in advance. A request may finish quickly, continue for hundreds of tokens, or share part of its prompt with another request. If the runtime handles each request by reserving a large contiguous region sized for a worst-case sequence, useful GPU memory can sit idle inside reservations or become difficult to reuse when differently sized allocations are created and released.
The original PagedAttention paper describes fragmentation and redundant duplication as major sources of KV-cache waste that can limit batch size. PagedAttention treats this as an allocation problem: keep the sequence logically ordered, but let its cache live in fixed-size physical blocks that can be allocated as needed.
Why KV-cache allocation becomes a serving bottleneck
It helps to separate cache size from cache allocation. A large cache is not automatically wasteful. If every byte stores useful state and the system can reclaim it immediately when a sequence ends, the memory is doing useful work. The trouble appears when allocation policy forces the runtime to reserve more memory than the sequence currently needs or requires a large contiguous free region before another request can start.
Internal fragmentation is unused space inside an allocation that has already been reserved. An illustrative example is a request that reserves room for a much longer sequence than it eventually produces. The unused tail still belongs to that reservation until the runtime can reclaim it.
External fragmentation is different. Free memory may exist, but it is split into pieces that do not satisfy the next large contiguous allocation. The total free capacity can look healthy while the allocator still cannot place another request efficiently.
These effects matter because batching depends on keeping multiple active sequences in memory. Better KV-cache utilization can therefore increase the number of requests that fit on the same accelerator, even if the arithmetic performed for one token is unchanged.
How logical blocks, physical blocks and the block table work
PagedAttention borrows the core abstraction of virtual memory. A sequence sees a logically ordered cache, while the serving system is free to place the corresponding physical blocks wherever suitable space exists.
The runtime divides a sequence’s KV cache into logical blocks. Each logical block is associated with a physical block in GPU memory through a block table. From the sequence’s perspective, token positions remain ordered. From the allocator’s perspective, the physical blocks do not need to sit next to one another.
This extra level of indirection is what removes the contiguous-allocation requirement. When a sequence grows, the runtime can obtain another free physical block and add a new logical-to-physical mapping. It does not need to move the entire existing cache into a larger contiguous region merely because more tokens arrived.
The same design also makes reclamation straightforward. When a sequence finishes and a physical block is no longer referenced, that block can return to the shared pool. A later request can use it without waiting for a large neighboring region to become free.
A request lifecycle: allocation, growth, sharing and release
Consider a serving request from arrival through completion.
- Prompt processing creates cache state. During prefill, the model generates key and value tensors for the prompt. The serving engine assigns physical blocks and records their mapping in the request’s block table.
- Decode extends the logical sequence. New tokens append new cache state. When the current block fills, the runtime allocates another physical block rather than expanding one contiguous allocation.
- The scheduler can keep other requests resident. Because free blocks remain reusable across the pool, unused capacity is less likely to be trapped inside oversized request reservations.
- Compatible branches can share cache blocks. When multiple generated sequences share the same earlier state, a serving implementation can reference common blocks instead of storing identical copies. The original vLLM work describes flexible sharing within and across requests for this reason.
- Completion releases blocks. Once no live sequence needs a block, it can be returned to the allocator for another request.
The result is a cache that grows closer to actual usage rather than predicted maximum usage. That is especially valuable when request lengths vary widely, because the allocator does not have to know the final generation length before admitting the request.
What the original vLLM benchmark actually shows
The original vLLM evaluation reported roughly 2–4× higher throughput at a similar latency level than the comparison systems used in that study. That is an important result, but it should be read as evidence about the evaluated serving stack and workloads, not as a universal multiplier that every deployment will reproduce.
The mechanism behind the gain matters. Better KV-cache utilization can let the server batch more requests or keep more sequences resident. Higher batch capacity can improve aggregate throughput when memory was the constraint. If another deployment is compute-bound, scheduler-bound, network-bound, or already uses an efficient memory manager, the improvement can be smaller.
A sound production test therefore measures the service rather than assuming the paper’s headline ratio: stable concurrency, throughput, time to first token, inter-token latency, memory utilization and tail latency under the actual prompt-length distribution.
PagedAttention vs KV-cache quantization vs prefix caching
These techniques are often discussed together because they all affect inference memory, but they solve different problems.
| Technique | Main problem addressed | What changes | Typical benefit |
|---|---|---|---|
| PagedAttention | Allocation waste and fragmentation | Logical cache state is mapped to reusable physical blocks | More efficient placement and potentially higher resident concurrency |
| KV-cache quantization | Too many bytes per cached token | Cached values use a lower-precision representation | Lower cache footprint, with quality and kernel trade-offs |
| Prefix caching | Repeated work and storage for identical prompt prefixes | Previously computed prefix state is reused | Less repeated prefill work and duplicated cache state for matching prefixes |
Paging changes where and how cache memory is allocated. Quantization changes how densely the cached tensors are represented. Prefix caching changes whether the same prompt state has to be computed and stored again. A serving stack can use more than one of these techniques because their benefits are complementary rather than mutually exclusive.
This distinction also prevents a common diagnostic error. If the runtime already places cache blocks efficiently but still cannot fit enough long-context sequences, reducing bytes per cached token may matter more than changing the allocator. If the cache representation is already compact but memory is stranded by reservation and fragmentation, paging is the more direct fix.
Operational trade-offs and limits
Paged memory management is not free. The runtime has to maintain block metadata and perform logical-to-physical address mapping. Kernels and schedulers must understand the layout efficiently. Poor implementation can turn indirection into overhead or make memory savings difficult to translate into user-visible performance.
The value also depends on workload shape. Highly variable sequence lengths and high concurrency create stronger opportunities to recover wasted capacity. A small, predictable workload with ample memory may see little practical benefit because fragmentation was never the limiting factor.
Operators should also avoid treating PagedAttention as a replacement for every other inference optimization. It does not eliminate model-weight memory, fix an inefficient tokenizer, reduce network overhead, or guarantee lower latency for a compute-bound decode path. Its strongest claim is narrower: better management of a large, dynamic KV-cache allocation problem.
When PagedAttention is the right optimization
Start with measurement. If profiling shows that KV-cache allocation is limiting concurrency, that free memory is poorly reusable, or that maximum-length reservations are consuming capacity well before compute saturates, a paged cache manager directly targets the bottleneck.
If the dominant issue is cache bytes per token, evaluate quantization. If repeated system prompts or shared document prefixes dominate prefill, evaluate prefix caching. If several constraints apply, combine techniques and benchmark the complete serving path rather than looking for one universal optimization.
The practical test is simple: PagedAttention is valuable when better KV-cache placement lets the server turn previously stranded memory into useful concurrent work while preserving the latency and correctness requirements of the service.
