vLLM borrowed virtual-memory ideas for the KV cache

Woosuk Kwon and coauthors introduced PagedAttention with vLLM in 2023. Autoregressive serving keeps key and value tensors for earlier tokens, but request lengths are unpredictable.

Reserving one contiguous region for each sequence wastes memory through over-allocation and fragmentation.

PagedAttention divides the cache into fixed-size blocks and maps logical blocks for each sequence to available physical blocks. New blocks can be allocated as a sequence grows, and shared prefixes can refer to shared physical data where the runtime supports it.

BLOCK MAPPINGLogical sequence order no longer requires contiguous storageThe block table preserves the sequence while physical blocks move independently.
A sequence fills its current logical blockThe runtime requests capacity for more KV state.
The block table finds physical storageThe next block may live anywhere in the available pool.
new tokens
Map another physical blockAppend it to the sequence's logical order.
shared prefix
Reference existing blocksAvoid storing the same retained prefix twice.
request continues
Read through the mappingAttention sees one logical sequence.
request ends
Release its block referencesReusable blocks return to the pool.

Paging changes placement and reuse. It does not remove retained token state or alter attention semantics.

The page table changes placement, not attention

KV-cache eviction discards cached token state under a memory limit. PagedAttention manages where retained state lives.

Prompt caching reuses prefix computation across requests, while PagedAttention is a serving-time memory layout that can help implement such sharing.

Neither mechanism decides which earlier tokens remain semantically important. Paging can reduce placement waste while the full logical cache continues to grow.

Uneven chat lengths create the practical case

A batch may contain one short completion and one conversation that continues for many tokens. Block allocation lets the longer request grow without reserving its maximum possible contiguous cache in advance.

The inference optimization guide places memory management beside batching and decoding techniques. The common misuse is claiming PagedAttention improves model quality; its purpose is to use serving memory more efficiently while preserving the same attention computation.

Block size creates its own tradeoff

Smaller blocks can reduce unused space at the end of a sequence but require more block-table entries and management work. Larger blocks reduce bookkeeping while increasing internal waste for short or recently finished sequences.

The best choice depends on the serving runtime and request-length distribution. A throughput claim without batch behavior and memory utilization does not show whether paging, scheduling, or another change produced the result.

Continue with these glossary entries: