Autoregressive serving keeps a growing key-value state for every active sequence. If that state must occupy one contiguous physical region sized for a request, allocation becomes coupled to uncertain sequence length: reserving too much wastes capacity, while extending or relocating a growing region complicates memory management. PagedAttention changes that allocation boundary. A sequence is represented as logical KV blocks, while its physical blocks may reside at unrelated locations in the cache pool.

The mechanism is an indirection layer, not a different attention equation. Attention still consumes the keys and values associated with prior token positions. The serving system changes how those positions are mapped to physical storage.

A block table separates sequence order from storage order

Let a logical sequence contain fixed-capacity KV blocks:

logical blocks:   L0   L1   L2   L3
                   |    |    |    |
block table:       7   21    4   13
                   |    |    |    |
physical blocks:  P7  P21   P4  P13

The logical indices preserve token order. The block table supplies the physical block identifiers needed to locate cached keys and values. Physical adjacency is therefore not required for logical adjacency.

This separation permits a cache manager to allocate another free physical block when a sequence crosses a block boundary. It does not need to find a larger contiguous region containing the sequence’s entire KV state. In vLLM’s PagedAttention design, each KV block stores keys and values for a fixed number of tokens, and blocks belonging to one request can be non-contiguous in physical memory.

The indirection has a concrete execution cost: an attention implementation must consume mapping metadata and issue accesses against the paged layout. Kernel design therefore matters. A generic claim that paging removes fragmentation without any access-path consequence would be too broad; the benefit depends on an attention path built for the layout.

Allocation occurs at block granularity

Suppose each block can hold B token positions and a sequence currently retains T positions. Ignoring implementation-specific reserved regions, the sequence requires:

allocated_blocks = ceil(T / B)

Only the final allocated block can be partially filled under simple append-only growth. The unused token slots attributable to this block rounding are bounded by:

0 <= unused_slots < B

This is a different waste profile from reserving a request’s full maximum sequence capacity in advance. Allocation follows realized growth in block-sized increments.

The bound above describes logical occupancy inside allocated blocks, not total device-memory overhead. Real systems also carry block-table metadata, allocator state, alignment, cache-pool structure, and backend-specific storage. Block size therefore creates a trade: smaller blocks reduce tail slack but increase the number of block identifiers and mapping operations for a given sequence length; larger blocks reduce mapping cardinality but can leave more unused slots in the final block.

Physical reuse does not imply semantic reuse

Returning a physical block to the free pool is a storage-management event. Reusing the same block identifier for a later sequence does not make old KV state semantically valid for that sequence. The cache manager must associate active logical positions with the correct physical contents and must not expose stale state as current KV data.

This distinction becomes more important when a serving system also implements prefix caching. Prefix reuse is a separate semantic decision: cached state can be reused only when the implementation’s cache identity rules establish that the block corresponds to the required prefix and model context. Paged allocation merely makes physical blocks addressable and manageable; it does not, by itself, establish that two requests may share their KV values.

Reference counts, hashes, eviction policy, and copy-on-write behavior can be layered onto a paged cache, but those are policy and implementation choices beyond the basic logical-to-physical mapping.

Paging changes the scheduler’s memory boundary

With a shared physical block pool, active requests compete for blocks rather than for individually reserved contiguous regions. A scheduler can admit or extend requests according to available cache blocks and the serving engine’s reservation policy.

That makes memory pressure visible in discrete allocation units. A request that grows by one token may consume no new physical block if its current final block still has space, or one additional block when it crosses the boundary. The stepwise behavior matters for admission control because token growth and physical allocation are related but not identical at every decoding iteration.

This mechanism also fits dynamic batches. Requests can finish and release their blocks while other requests continue. Freed blocks can return to the pool without relocating the surviving requests’ logical sequences. The property comes from the mapping layer: logical sequence continuity no longer requires physical continuity.

Kernel compatibility is part of the mechanism

Paged KV storage is useful only if the attention execution path can address it correctly. vLLM exposes block tables to paged-attention kernels, and its documented cache layouts include a physical-block dimension. That is an implementation contract between cache management and the kernel, not a universal property of every transformer runtime.

Different backends can choose different physical layouts, block sizes, metadata formats, or kernel strategies while preserving the same architectural idea. Some may fuse address translation into the attention path; others may transform metadata or use backend-specific kernels. As a result, PagedAttention should be described at two levels: logical-to-physical block mapping is the architectural mechanism, while exact tensor layouts and access procedures belong to a particular implementation.

The practical boundary is narrow but important. PagedAttention does not shrink the mathematical KV state required by full attention, and it does not change which prior positions are semantically part of that state. It changes the physical allocation and addressing model so a logical sequence can grow across independently managed cache blocks.

Artificial Intelligence LLM Inference PagedAttention KV Cache Memory Management