An autoregressive request grows its KV cache as tokens arrive, but its final sequence length is not known when decoding begins. Reserving one contiguous region for the maximum possible sequence length ties memory to capacity that may never be used. PagedAttention changes that allocation boundary: a sequence is represented as logical KV blocks, while a block table maps those logical blocks to physical blocks that need not be adjacent in GPU memory.
The mechanism changes cache placement and allocation. It does not change the attention equation or reduce the model’s KV state per retained token.
Logical order is separate from physical placement
A sequence still has an ordered token history. PagedAttention groups that history into fixed-size logical blocks. Each logical block has a position in the sequence, but its backing physical block can reside anywhere in the managed KV-cache pool.
Conceptually, the mapping is:
sequence logical blocks: 0 1 2 3
| | | |
block table: 17 4 29 8
| | | |
physical KV blocks: [17] [04] [29] [08]The attention kernel uses the block table to locate keys and values for the logical sequence. Contiguous logical token order therefore does not require one contiguous physical allocation.
This indirection is the central systems property. A serving runtime can allocate another physical block when a sequence crosses a block boundary instead of reserving storage for its maximum possible future length at admission time.
Allocation waste moves to the block boundary
Fixed-size blocks do not eliminate internal fragmentation. The final logical block of a live sequence can be only partly occupied. The important difference is that unused capacity is bounded by the block granularity rather than by a reservation sized for an unknown future sequence.
Smaller blocks can reduce unused slots in the final block, but block size is not a free parameter. More blocks require larger block tables and more mapping work. Kernel layout, metadata traffic, allocator behavior, and hardware characteristics all affect the useful operating point.
The PagedAttention paper reports low KV-cache waste for its vLLM design, but that result belongs to the evaluated system and workloads. The architectural claim is narrower: block allocation permits physical capacity to follow actual sequence growth more closely than a single preallocated maximum-length region.
Noncontiguous storage requires an attention kernel that follows the map
Ordinary tensor kernels often assume that a sequence’s K and V tensors occupy predictable contiguous ranges. PagedAttention cannot preserve that assumption because adjacent logical blocks may map to unrelated physical addresses.
Its attention implementation therefore incorporates block-table lookup into KV access. For a query token, the kernel traverses the logical context and resolves each logical block to its physical backing before loading the relevant keys and values.
The extra indirection is real work. PagedAttention is not a claim that scattered memory is inherently faster than contiguous memory. Its systems benefits come from better cache-memory utilization and the larger or more flexible request sets that utilization can permit. Whether those gains dominate mapping and kernel overhead depends on the complete serving stack.
Block sharing can avoid duplicate KV state
Indirection also permits more than one logical sequence to reference the same physical KV block. This is useful when sequences share an identical prefix or when multiple decoding branches initially contain the same history.
Shared blocks can remain common while their contents are immutable. When a branch needs to modify data that must no longer be shared, the runtime can use copy-on-write semantics and give that branch separate physical storage.
The property is about storage identity, not approximate attention. A shared block represents KV state that is valid for each referencing sequence. If two sequences do not have semantically reusable KV state at the relevant positions, sharing physical bytes would not be correct merely because their token text looks similar.
Position-dependent transformations and model execution state therefore remain part of the cache-validity boundary.
Paging does not compress the mathematical KV cache
For a conventional full-attention model, retaining a token still requires the key and value state defined by the model architecture for the layers that cache them. PagedAttention changes the allocator and address translation used to store that state. It does not, by itself, prune tokens, quantize K or V, reduce head dimensions, or replace full attention with sparse attention.
That distinction separates paging from KV-cache compression. Compression methods may reduce the amount or precision of retained state and can introduce separate accuracy or kernel constraints. Paged allocation can coexist with such methods, but the mechanisms make different claims.
The same distinction applies to context limits. Efficient placement can allow a fixed memory budget to hold more active cache blocks, yet it does not alter the model’s configured context semantics.
The serving effect depends on memory pressure
KV-cache memory can limit the number of requests that fit concurrently during inference. In that regime, reducing reservation waste can admit a larger active batch or leave more room for sequences to grow. The original vLLM evaluation reported throughput gains over the systems it compared against, especially for workloads with longer sequences and more complex decoding patterns.
Those measurements are not a universal performance guarantee. Scheduler policy, model shape, KV precision, block size, GPU architecture, attention kernel, request-length distribution, prefix reuse, and latency targets can all change the result.
PagedAttention’s durable boundary is more specific: logical sequence continuity no longer requires physical KV-cache continuity. The block table preserves the logical view while the allocator places physical blocks according to available memory, allowing sequence growth and cache sharing without a single maximum-length contiguous reservation.