PagedAttention Explained: How vLLM Pages the KV Cache to Stop Memory Waste

On a busy model server, GPU memory often fills up before the GPU's compute is fully used. Each request keeps a KV cache that grows with every token, and storing it naively wastes most of the memory it reserves. PagedAttention fixes how that memory is handed out.

Picture a common setup. A team in Pune serves a customer-support chat assistant with vLLM on one 80 GB data-centre GPU. The setup is made up, but every number below comes from our own runs or a cited source.

After the model weights load, about 60 GiB is left for the KV cache (a made-up round number). GiB means gibibyte, 1,073,741,824 bytes. A typical chat uses under 1,000 tokens, but the server allows up to 8,192 per request.

If the server reserves a full 8,192-token strip for every request, only 60 requests fit at once. In our simulation of the same memory, paging fitted about 498 at once on average. This guide explains why that gap exists and how paging closes it.

You need six words. Each one is tied to the support assistant.

• Token: a small piece of text, often a word or part of a word. The model reads the prompt as tokens and writes its reply one token at a time.
• KV cache: for every token already seen, each layer of the model saves keys and values, which are lists of numbers. Later tokens look back at them instead of recomputing the whole chat.
• Prefill and decode: prefill processes the whole prompt in one go. Decode then produces one new token per step, and each step adds one more key and value per layer.
• Batch: the set of requests the GPU works on in the same step. More requests per step means more tokens for the same GPU time.
• Fragmentation: memory that is free in principle but cannot be used, because it is reserved, stuck inside someone's allocation or split into gaps that are too small.
• Block: a fixed-size chunk of KV cache that holds the keys and values of a fixed number of tokens. vLLM uses 16 tokens per block by default.

PagedAttention stores each request's KV cache in fixed-size blocks that can sit anywhere in GPU memory. Its attention kernel, a function that runs on the GPU, finds those blocks through a lookup table.

It comes from a 2023 paper on memory management for model serving, arXiv 2309.06180, which also introduced vLLM. The paper borrows from operating systems: think of blocks as pages, tokens as bytes and requests as processes.

Each request sees its KV cache as logical blocks numbered 0, 1, 2 and so on, filled left to right. Its block table records which physical block in GPU memory holds each logical block. A new physical block is taken from the free list only when the last one is full.

One detail for engineers: vLLM's design page on the original PagedAttention kernel is now marked historical. In 0.32.0, the attention backends read the same block tables, so the paging idea outlived that first kernel.

So the support assistant never reserves room for a reply that has not been written. A 900-token chat holds 57 blocks: 56 full ones and one with 4 of its 16 slots used.

An everyday picture helps. In a university exam, the old way hands every student a bound 32-page answer booklet, though most write 6 pages. The unused pages cannot go to anyone else.

The paged way hands out loose 4-page sheets. A student asks for another sheet only when the current one is full, and writes the sheet numbers in order on the cover. The cover list is the block table, and the only waste is the unused part of the last sheet.

Where the picture breaks: exam sheets are never shared, but KV blocks can be. Two requests with the same prompt can point at the same physical block, which the copy-on-write section explains.

Bytes per token = 2 x layers x KV heads x head size x bytes per number. The 2 counts one key and one value. Everything else comes from the model's shape and the number format of the cache.

A head is one of the parallel attention units in a layer, and head size is the length of its key vector. Many models use grouped-query attention, where several query heads share one key-value head, so KV heads can be fewer than attention heads.

Take a made-up but realistic shape: 32 layers, 8 KV heads, head size 128, and a 16-bit cache, which is 2 bytes per number. That gives 131,072 bytes, or 128 KiB, per token. KiB means 1,024 bytes.

def kv_bytes_per_token(layers, kv_heads, head_dim, dtype_bytes):
    # 2 = one key vector and one value vector per token, per layer
    return 2 * layers * kv_heads * head_dim * dtype_bytes


per_token = kv_bytes_per_token(layers=32, kv_heads=8, head_dim=128, dtype_bytes=2)
print(per_token, "bytes =", per_token // 1024, "KiB per token")
print(per_token * 8192 / 2**30, "GiB for one 8,192-token request")
print(60 * 2**30 // (per_token * 16), "blocks of 16 tokens fit in 60 GiB")

Running it prints 131072 bytes, 128 KiB per token, 1.0 GiB for one 8,192-token request and 30,720 blocks of 16 tokens in 60 GiB. That is 491,520 tokens of room in total.

The paper gives its own worked example for a 13-billion-parameter model with 40 layers and a hidden size of 5,120. It needs 2 x 5,120 x 40 x 2 bytes, about 800 KB per token, and up to 1.6 GB for a 2,048-token request.

Our script reproduces that: 819,200 bytes, which is exactly 800 KiB, and 1.56 GiB for 2,048 tokens. The cache is per request, so 60 chats of 8,192 tokens fill our whole 60 GiB budget.

Because the server must reserve memory before it knows how long the reply will be. The naive design, shown here because it is wrong for this workload, gives each request one contiguous strip sized for the maximum length.

The paper names three kinds of waste in this design. Earlier serving systems, it reports, used only 20.4% to 38.2% of their KV cache memory for actual token states.

• Reserved: slots held for tokens the request has not generated yet. They are empty for most of the request's life.
• Internal fragmentation: slots inside a request's strip that are never used, because the reply ended well before the maximum length.
• External fragmentation: free gaps between strips that are too small for the next request, even when their total is large enough.

Pause and predict: in our simulated support traffic, what share of the KV memory held real tokens when every request reserved 8,192 slots? Make a guess before reading on.

It was 12.3%. The workload had 3,000 made-up chats with a median of 886 tokens and a longest of 7,067. The other 87.7% was reserved but empty, and only 60 requests could run at once.

An oracle that knew each reply's final length and reserved exactly that did much better, but still not well. While requests were waiting, 13.3% of memory sat free on average, in gaps too small for the next request in line. On 2,630 steps the total free space was big enough, but no single gap was.

There is a quieter lesson in the reserve-8,192 run. When every reservation is the same size, a freed strip always fits the next request, so external fragmentation disappears. The price is massive internal fragmentation instead.

In our simulation paging raised the average batch from 60 to about 498 requests and finished the same work in 3,334 decode steps instead of 17,663. Fewer steps for the same tokens means a lower cost per token.

Each simulated step is one decode iteration, where every running request adds one token. The paged allocator hands out 16-token blocks on demand. When no block is free, it preempts the newest request: it frees its blocks and queues it to be rebuilt later.

What just happened? The paged runs keep almost every slot full of real tokens, so far more chats fit in each step. The oracle row shows exact sizing alone is not enough, because gaps still form between strips.

Now turn that into money with made-up figures. Suppose the GPU costs ₹250 an hour and every step takes 25 ms. Contiguous allocation then costs about ₹30 per million output tokens, and paging about ₹5.7.

That is roughly 0.19 times the cost, but treat it as an upper bound on the saving. The simulator assumes a step takes the same time at any batch size, and real decode steps slow down as the batch grows. It also treats prefill as free, so recomputing preempted requests adds no steps here.

Even if a step at batch 500 took twice as long, paging would still cost about 0.38 times as much per token. Measure your own step times before quoting a number.

Copy-on-write lets several sequences point at the same physical block and copies it only when one of them needs to write into it. Each block keeps a reference count, the number of sequences currently using it.

The paper uses this for parallel sampling, where one prompt produces several different replies, and for beam search. Beam search keeps several candidate continuations and drops the weak ones as it goes.

For parallel sampling, all samples first share the prompt's blocks, so each block's count equals the number of samples. When a sample writes into the shared, partly filled last block, the server takes a new block, copies the data and lowers the old block's count by one.

B = 16                      # tokens per block
free = list(range(1000))    # free physical block ids
ref = {}                    # physical block id: reference count


def new_block():
    b = free.pop(0)
    ref[b] = 1
    return b


def append_token(table, length):
    """Write one token's keys and values; return the new length."""
    if length % B == 0:                 # last block is full: get a new one
        table.append(new_block())
    elif ref[table[-1]] != 1:           # last block is shared: copy on write
        ref[table[-1]] -= 1
        table[-1] = new_block()         # a real server also copies the block's data here
    return length + 1


prompt = []
n = 0
for _ in range(1000):                   # 1,000-token prompt fills 63 blocks
    n = append_token(prompt, n)

samples = []
for _ in range(4):                      # fork 4 samples: share every block
    for b in prompt:
        ref[b] += 1
    samples.append((list(prompt), n))
for b in prompt:                        # the parent itself is done
    ref[b] -= 1

for step in range(200):                 # each sample writes 200 tokens
    samples = [(t, append_token(t, ln)) for t, ln in samples]

print("blocks in use:", sum(1 for c in ref.values() if c))
print("first block shared by", ref[prompt[0]], "samples")
print("last prompt block per sample:", [t[62] for t, _ in samples])

It prints 114 blocks in use, the first block shared by 4 samples, and last prompt blocks 63, 64, 65 and 62. Three samples got copies; the last writer kept the original, because by then its count had dropped to 1.

Without sharing, the same four replies needed 300 blocks in our cow_sim.py run, so sharing saved 62%. That figure is high because the prompt is long and the replies short.

The paper measured smaller but real savings on real datasets. Parallel sampling saved 6.1% to 9.8% of memory on a dataset of short instructions, and 16.2% to 30.5% on a dataset of real chats. Beam search saved 37.6% to 66.3% across the two.

How vLLM shares blocks today

vLLM 0.32.0 reaches the same goal by a different route. A request asking for n samples becomes n child requests, each with n set to 1, in vllm/v1/engine/parallel_sampling.py.

The children can then reuse the prompt through automatic prefix caching, which is on by default. Each full block gets a hash, a short fingerprint, built from its parent block's hash, its own tokens and extra keys. One such key is a cache salt, which keeps different tenants' caches apart.

A new request whose prompt starts with the same tokens finds those hashes and simply increases the blocks' reference counts. In the BlockPool source this is the touch method, and a freed block returns to the free list only when its count reaches 0.

The prefix caching docs say vLLM caches full blocks only. So for a typical model, a partly filled last block is never shared, and each request writes its own.

What full-block sharing means for a system prompt

Suppose all support chats start with the same 1,000-token system prompt. With 16-token blocks, 62 full blocks hold 992 tokens and can be shared. The last 8 tokens are computed again for every chat.

For 50 chats, that is 62 shared blocks plus 50 private tail blocks, 112 in all, instead of 3,150 without sharing. With 128-token blocks only 896 of the 1,000 tokens fall in full blocks, so less is reused.

The server preempts a running request: it frees that request's blocks and resumes it later. The paper offers two ways to resume, swapping blocks to CPU memory or recomputing them. vLLM 0.32.0 has no swap mode and recomputes.

Preemption happens because decode keeps growing every request. With paging, the server admits requests based on what they use now, so a busy step can need a new block when none is free.

The paper evicts all of a request's blocks or none of them, because a request needs all its KV cache to continue. It serves requests first come, first served, so the latest arrivals are preempted first.

• Swapping copies the evicted blocks to CPU RAM over PCIe, the link between the CPU and the GPU, and copies them back later. The paper bounds swap space by the GPU memory given to the KV cache.
• Recomputation drops the blocks. When the request resumes, its generated tokens are joined to the original prompt and the whole thing is prefilled again in one pass.

The paper found swapping slow with small blocks, because many small transfers use the PCIe link poorly. Recomputation did better at small block sizes, and the two were comparable from 16 to 64 tokens per block.

What the vLLM 0.32.0 source does

In vllm/v1/core/sched/scheduler.py, the default policy picks the request most recently added to the running list. The priority policy picks the lowest-priority request, where a larger number means lower priority, breaking ties by latest arrival.

The _preempt_request method frees the request's blocks, sets its computed token count to 0 and puts it at the front of the waiting queue. The engine arguments in 0.32.0 have no swap-space or preemption-mode option. This victim choice is read from source and undocumented as of 27 October 2026; pin your version.

With prefix caching on, freed blocks that carry a hash go to the back of the free list. So a preempted request can sometimes find part of its own prompt still cached when it resumes, and skip that part. A configured KV offloading or transfer connector can also supply cached blocks at that point.

In our simulator, the paged run with 16-token blocks preempted 522 times. They recomputed 149,240 tokens, about 4.6% of the 3.2 million tokens processed. That is the price of admitting requests on what they use now.

If preemptions are frequent, the docs suggest raising gpu_memory_utilization, lowering max_num_seqs or max_num_batched_tokens, or splitting the model across more GPUs with tensor or pipeline parallelism. KV cache offloading to CPU is a separate vLLM feature with its own settings.

Five settings decide how much KV memory you get and how it is cut into blocks. We read each default from the vLLM 0.32.0 source, released on PyPI on 18 October 2026, and checked the published engine arguments page where it lists them.

The cache config also has a hash algorithm for prefix caching, sha256 by default. Block 0 of the pool is a reserved null block, so a pool of 8 blocks has 7 free for requests. Both details come from the 0.32.0 source and are undocumented as of 27 October 2026.

How to check it worked

1. 1

   Start the server

   Run vllm serve with your model and any flags above. Keep the startup log; the KV sizing lines appear once the memory profile finishes.

2. 2

   Read the KV budget

   Find the line Available KV cache memory: X GiB. It is what remained of the gpu_memory_utilization share after weights, activations and CUDA graphs.

3. 3

   Read the capacity

   Find GPU KV cache size: N tokens, Maximum concurrency for M tokens per request: Yx. N divided by your block size is roughly the block count.

4. 4

   Cross-check the maths

   On a single GPU, divide the available bytes by your model's bytes per token. The result should be close to N.

5. 5

   Watch it under load

   The periodic stats line shows GPU KV cache usage as a percentage and, in intervals where any happen, Preemptions: N for that interval. The metric vllm:kv_cache_usage_perc, exposed for the Prometheus monitoring system, reports usage from 0 to 1.

Keep the default unless you have measured a reason. Small blocks waste less memory and share prefixes more finely, but very small blocks give the GPU too little work per block to read efficiently.

The paper tested this directly. Block sizes from 16 to 128 worked best on real chat traffic, while short requests did best at 16 or 32, because many requests were shorter than the larger blocks.

Our simulator shows the memory side. Average unused space in the last block grew from 7.4 tokens at size 16 to 252.7 tokens at size 512. At 512, 20.2% of memory sat reserved but empty, and the average batch fell to 397.

vLLM 0.32.0 also lets the attention backend overrule the default. When the chosen backend needs a different size, the log prints Setting kv cache block size to N.

Paging removes waste, not need. A request with 8,192 real tokens still needs 1 GiB in our made-up model, so long contexts still limit how many requests fit.

• Weights are a fixed cost. Paging only manages the memory left after the model loads.
• Reading through a block table costs time. The paper measured 20% to 26% higher attention kernel latency than an optimised contiguous kernel, which end-to-end gains outweighed.
• Paging decides where tokens live, not which requests run together. Batching policy is a separate topic.
• Preemption still hurts latency for the request that is pushed out, even though no work is lost permanently.

The SevyDevy guide on LLM inference system design covers continuous batching and the wider serving pipeline. This guide stays on the memory mechanics underneath it.

Start from the memory maths, then show why contiguous reservations fail, then describe blocks, sharing and preemption. Interviewers want the trade-offs, not the paper's name.

1. 1

   Size the KV cache

   Bytes per token is 2 x layers x KV heads x head size x bytes per number. For our made-up model, 128 KiB per token and 1 GiB per 8,192-token request.

2. 2

   Show the naive design failing

   Reserving the maximum length per request leaves most memory reserved but empty. Exact-size strips still leave gaps between requests.

3. 3

   Introduce blocks and block tables

   Fixed 16-token blocks from a free list, mapped per request by a block table. Waste is at most one partly filled block per request.

4. 4

   Add sharing

   Reference counts let parallel samples and common prefixes share blocks. Copy-on-write copies a block only when a sharer writes into it.

5. 5

   Handle running out

   Preempt the newest request, free its blocks and recompute it later with one prefill. Swapping to CPU is the alternative, slower with small blocks.

6. 6

   Close with the payoff

   More requests per step means more tokens per GPU-hour. Note the costs: kernel indirection, preemption latency and the block size trade-off.