Paged Attention: Virtual Memory for the KV Cache

A server cannot know how long a request will run. The answer might be one line or ten pages, and its KV cache grows by one token per step until it ends. Reserve the maximum for every request and most of the memory sits empty; reserve less and requests run out of room mid-answer. Paged attention gets out of that trap the way operating systems did decades ago: it cuts memory into small fixed pages and hands them out as they are needed. This piece shows how it works, how vLLM implements it, and what it saves in practice.

The problem: reserving the maximum

The KV cache piece sized the cache of Qwen3-8B at 144 KiB per token. On an NVIDIA GB10 (DGX Spark class), vLLM 0.30.0 with --gpu-memory-utilization 0.85 found room for 613,568 tokens of cache, and printed what that means if every request takes its full context:

GPU KV cache size: 613,568 tokens, Maximum concurrency for 40,960 tokens per request: 14.98x

40,960 tokens is vLLM's default maximum length for Qwen3-8B, taken from the model's config (max_position_embeddings), prompt and answer together. A server that reserves that much per request fits 14 of them. Yet the requests of our benchmark below use 4,164 tokens each: a 4,100-token prompt and up to 64 tokens of answer. A full reservation would leave 90% of each slot empty, and the fifteenth user would wait while most of the memory holds nothing.

Two other problems follow from reserving. Requests of different sizes leave holes between them that a new request may not fit into, even when the total free memory is enough: fragmentation. And two requests that start with the same system prompt each store their own copy of it.

Paging: blocks handed out as tokens arrive

Paged attention, introduced by vLLM's authors in the PagedAttention paper (SOSP 2023) and inspired, in their words, by "the classical virtual memory and paging techniques" of operating systems, replaces the reservation with three pieces:

1. Fixed-size blocks. At startup, the engine divides all the cache memory into blocks of a few tokens each: 16 tokens by default in vLLM (DEFAULT_BLOCK_SIZE). Our 613,568 tokens became 38,348 blocks.
2. A free list. Every block not in use waits in a queue. When a request needs room, it takes blocks from the front.
3. A block table per request. The request's tokens live in blocks scattered anywhere in memory; its block table lists them in order: "my block 0 is physical block 1, my block 1 is physical block 5", and so on.

A request gets just enough blocks for its prompt: cdiv(num_tokens, block_size), rounded up. Each time it fills its last block, it takes one more. When it finishes, its blocks go back to the free list. A request wastes at most the unused end of its last block: fewer than 16 tokens, instead of everything it did not use of its reservation.

Here are both approaches on the same memory and the same requests:

Things to try:

1. Press Play. With reservations, at most 4 requests run at once, and over the run about a third of the claimed memory is empty. With paging, up to 7 run on the same memory and less than a tenth of it is empty, so all 16 requests finish in 111 steps instead of 150.
2. Watch the preempted counter. Paging admits requests on what they need now. When they all grow and the memory runs out, the engine has to evict one of them. More on that cost below.
3. Change the block size. Larger blocks waste more at the end of each request (17% empty at 32 tokens); smaller blocks waste less but mean more blocks to track.
4. Turn on the shared prefix. All requests start with the same 48 tokens; with paging, those blocks are stored once, and up to 14 requests run at once.

The simulator is a toy model: tiny memory, one token per step per request, a whole prompt stored in one step. Its policy follows vLLM's: blocks on demand, the most recently admitted request preempted first, shared blocks counted by reference.

Finding a token: position, block, slot

Blocks scattered across memory mean the attention kernel can no longer find token n at "start + n". It has to translate, exactly as a CPU translates a virtual address through a page table. To write the key and value of token 53 of a request, with 16-token blocks:

vLLM computes these slots for every token of a step in one GPU kernel. Its central line is the formula of the figure (block_table.py):

slot_ids = block_numbers * block_size + slot_offsets

The attention kernels read the other way: for each request, they walk its block table and load the keys and values block by block. This indirection is the "paged" in paged attention, and the reason attention kernels for serving take a block table as an argument.

Inside vLLM: the block pool

The allocator lives in vLLM's BlockPool. It creates every block at startup and keeps the free ones in a FreeKVCacheBlockQueue, a doubly linked list. A few details are worth knowing:

• Block 0 is never handed out. The pool takes it at startup as a "null block", a placeholder for table entries that point at nothing.
• Allocation takes from the front of the free queue (get_new_blocks), and every allocated block gets a reference count.
• Freeing is ordered (free_blocks). A block whose count drops to zero goes back to the queue. If its contents can be reused (more on that next), it goes to the back, so it is evicted last; if not, to the front, so it is reused first.

That last point is where paging pays off a second time.

Sharing a prefix: one copy for many requests

Because a request only sees memory through its block table, two block tables can point at the same block. If two requests start with the same tokens (the same system prompt, the same document, the same few-shot examples), their first blocks hold exactly the same keys and values, and there is no reason to store them twice:

vLLM finds those shared blocks with hashes. Each full block gets a hash computed from its tokens and from the hash of the block before it (hash_block_tokens), so a block's hash identifies the whole prompt up to that block, not just its own 16 tokens. When a request arrives, vLLM hashes its prompt block by block and looks each hash up in a table of cached blocks. Every hit is a block it does not have to compute or store: the request's block table points at the existing block, and touch increments its reference count.

Three consequences of the design:

• Only full blocks are shared. A partial last block belongs to its request, which is still writing into it.
• A full hit still computes one token. The model needs the last prompt token's output to start the answer, so vLLM caps the hit at the prompt length minus one (kv_cache_manager.py), which can mean recomputing that last block.
• Blocks stay cached after their requests end. A freed block keeps its hash and goes to the back of the free queue. Until memory pressure reuses it, the next request with the same prefix still hits it.

This is prefix caching. It is on by default in vLLM (--no-enable-prefix-caching turns it off). SGLang does the same with its own structure, a radix tree over cached tokens (RadixAttention, on by default; --disable-radix-cache turns it off), and also stores the cache in pages (--page-size).

Measured: the same prompt, sixteen at a time

On the same machine and setup, we ran vLLM's benchmark and its prefix_repetition dataset: 64 requests, 16 in flight, each a 4,000-token prefix followed by 100 tokens of its own, and up to 64 tokens of answer.

$ vllm serve Qwen/Qwen3-8B --port 8001 --gpu-memory-utilization 0.85
$ vllm bench serve --model Qwen/Qwen3-8B --port 8001 \
    --dataset-name prefix_repetition --prefix-repetition-prefix-len 4000 \
    --prefix-repetition-suffix-len 100 --prefix-repetition-num-prefixes 1 \
    --prefix-repetition-output-len 64 --num-prompts 64 --max-concurrency 16 \
    --request-rate inf --seed 7

--prefix-repetition-num-prefixes 1 gives all 64 requests the same prefix; 64 gives each its own. We ran three cases, with zero failed requests and no preemption in any of them:

"Peak KV cache in use" is vLLM's own vllm:kv_cache_usage_perc metric, sampled every second. What it shows:

1. Paging alone is already frugal. Without sharing, 16 requests of 4,164 tokens need 16 × 261 blocks, 10.9% of the cache, and that is what vLLM used. Reserving 40,960 tokens each, the same 16 requests would not have fit at all.
2. Sharing divides the memory by ten. With one prefix, the 4,000 shared tokens (250 blocks) are stored once and each request adds about 11 blocks of its own: 426 blocks, 1.1%. The other 89% of the cache could hold far more requests.
3. Sharing also skips the work. A hit means those 4,000 tokens are not computed again: the mean time to first token falls from 4.3 s to 0.7 s, and the whole run takes 23 s instead of 84 s. The misses (10,419 tokens out of 262,403) are about one copy of the prefix plus the 64 private suffixes.
4. When nothing is shared, it costs nothing visible. With 64 different prefixes, prefix caching on behaves like prefix caching off: same memory, same times, within the noise of a single run.

The answers did not all reach 64 tokens (the model may stop earlier), so we compare times to first token and total time, not output rates. Note also that the second server, started without prefix caching, found 629,168 tokens of cache instead of 613,568: on a machine where the GPU shares memory with the system, the profile at startup depends on what else is using memory.

What paging costs

Paging is not free, and three costs are worth knowing when you tune a server:

• Preemption. Admitting requests on what they need now means that when they all grow, the memory can run out. vLLM then preempts a request: with the default policy, the most recently admitted one. Its blocks are freed and its progress reset to zero: it will be recomputed when it is admitted again (with prefix caching, its full blocks may still be cached by then). Watch the vllm:num_preemptions_total counter in production. A steadily rising count means the batch is larger than the memory can sustain; lower --max-num-seqs or give the cache more memory.
• The block size. Bigger blocks mean fewer table entries and larger memory reads per block, but more waste at the end of each request and coarser sharing (only full blocks are shared). The paper's authors found 16 "large enough to efficiently utilize the GPU and small enough to avoid significant internal fragmentation in most workloads", and made it vLLM's default. Change it only for a reason, such as an attention backend that requires a specific size.
• Indirection. Every attention read goes through the block table. The paper measured 20 to 26% higher attention kernel latency than a contiguous implementation of the time, and judged the overhead small because it touches only attention, not the matrix multiplications that dominate a step. It is also why paged attention needs dedicated kernels and why an engine's attention backends all take a block table.

For history: the PagedAttention paper reported 2 to 4 times the throughput of the systems of the time (FasterTransformer and Orca) at the same latency, mostly from fitting more requests in the same memory. Today, vLLM, SGLang, and TensorRT-LLM (its paged KV cache uses tokens_per_block) all manage the KV cache in blocks.

Next

Paging also changes how the scheduler can treat long prompts: it can process them in pieces, a chunk per step, without reserving anything up front. That is chunked prefill, the next piece in this series. Prefix caching gets a piece of its own later: how to structure prompts so they share blocks, how eviction decides what stays, and how far a hit rate moves cost and latency in agent and chat workloads.