PagedAttention Block Tables: How vLLM Ends KV Cache Fragmentation

How many bytes one token costs

For a standard decoder, each token stores one key and one value vector per KV head in every layer. The size per token is therefore:

kv_bytes_per_token = 2 (K and V) * num_layers * num_kv_heads * head_dim * bytes_per_element

# 8B-class model with grouped-query attention, FP16 cache (illustrative)
2 * 32 layers * 8 kv_heads * 128 dims * 2 bytes = 131,072 bytes = 128 KiB per token

# same depth without GQA (32 kv_heads)
2 * 32 * 32 * 128 * 2                           = 512 KiB per token

# 10 GiB left for KV after weights and activations
10 GiB / 128 KiB = 81,920 tokens of context, shared by every running sequence

The vLLM paper gives the same calculation for a 13-billion-parameter OPT model: about 800 KB per token, so one 2,048-token sequence needs up to 1.6 GB. The point to carry forward is that KV memory is measured in tokens of context, and every running sequence draws from one shared budget. A server with 81,920 tokens of KV can hold 60 sequences of 1,350 tokens, or 8 sequences of 10,000 tokens, or any mix that adds up. The allocator's job is to make the sum of real tokens approach that number. Grouped-query attention, FP8 KV cache and smaller head dimensions all shrink the per-token cost; allocation policy decides how much of what remains is used.

Three kinds of waste in contiguous allocation

A contiguous allocator has to choose a slab size when the request is admitted, before anyone knows how long the answer will be. The safe choice is prompt + max_tokens, or even the model's maximum context length. That produces three separate losses, which the PagedAttention paper names explicitly:

• Reservation waste. Space for tokens that will be written later sits idle for the whole life of the sequence. A request whose answer will be 250 tokens holds room for 2,048 from its first step.
• Internal fragmentation. Most answers end long before max_tokens, so most of the slab is never written at all. With a mean prompt of 1,100 tokens, a mean output of 250 and a 2,048-token cap, a slab of about 3,150 tokens holds about 1,350 real ones at the end: 43% utilisation at best, and lower on average over the sequence's life.
• External fragmentation. Slabs of different sizes are freed in a different order than they were allocated, so free memory breaks into holes. A new 3,000-token request can be refused while 5,000 tokens are free in total, because no single hole is large enough.

The lab's first-fit allocator reproduces all three on its own. With the default contiguous setup on 10 GB, only about 45% of reserved memory holds tokens, around 17 sequences decode at once, and the scheduler reports thousands of steps on which the head of the queue was blocked even though enough total memory was free. Nothing is wrong with the GPU; the memory is spoken for by tokens that do not exist.

Block tables: paging for attention

PagedAttention borrows the idea operating systems use for process memory. The KV cache is split into fixed-size blocks, each holding the keys and values for a fixed number of tokens (16 by default in vLLM on most GPUs). A sequence owns a block table: a list that maps its logical blocks (tokens 0 to 15, 16 to 31, and so on) to physical blocks anywhere in the pool. The attention kernel reads the table and gathers keys and values block by block, so physical contiguity no longer matters.

# allocation only ever happens one block at a time
def append_token(seq, kv):
    if seq.num_tokens % BLOCK_SIZE == 0:          # last block is full (or there is none)
        if not free_blocks:
            preempt(newest_running_group())         # recompute or swap it later
        seq.block_table.append(free_blocks.pop())
    write_kv(seq.block_table[-1], seq.num_tokens % BLOCK_SIZE, kv)
    seq.num_tokens += 1

def free(seq):
    for b in seq.block_table:
        if decref(b) == 0:                         # shared blocks survive until the last owner leaves
            free_blocks.append(b)

Each of the three wastes disappears or shrinks to a bound. Nothing is reserved for future tokens, because a block is taken only when the previous one fills. Internal fragmentation is limited to the unfilled part of the last block, on average half a block per sequence: 8 tokens with 16-token blocks, which is 0.6% of a 1,350-token sequence. External fragmentation cannot happen, because every block is the same size and any free block satisfies any request. The paper reports that this brings waste under about 4% and raises throughput two to four times over the contiguous systems it compared against at similar latency. In the lab, switching the same 10 GB to the paged allocator lifts the share of allocated memory holding tokens to about 99%.

The memory map in the lab also shows the price that the block table quietly pays: a request's blocks end up scattered across physical memory as other sequences free theirs in a different order. For a contiguous allocator that would be fatal. For a block table it is irrelevant.

What block size really trades off

If small blocks waste less, why not one token per block? Because the attention kernel pays for indirection. Each block-table entry is a pointer the kernel has to load before it can fetch the keys behind it, and tiny blocks mean short, scattered memory reads that use the GPU's memory bandwidth poorly. Very large blocks bring internal fragmentation back: with 256-token blocks the average sequence wastes 128 tokens, close to 10% of a 1,350-token sequence, and short sequences waste far more in relative terms.

The table is calculated, not measured. The paper's own block-size ablation found 16 to be a good default: large enough to use the GPU efficiently and small enough to keep internal fragmentation low. It also measured the paged kernel itself as roughly 20 to 26% slower than a contiguous kernel in a microbenchmark, a cost repaid many times by the larger batch it enables. Some kernel backends support only particular block sizes, and some systems such as SGLang default to a page size of one token with kernels written for it, so check what your version and attention backend accept before changing the value.

Parallel sampling makes block size matter more than the table suggests. When one prompt is decoded into four samples, the full prompt blocks are shared, but the last partly filled prompt block must be copied for each sample on its first write. With large blocks, each copy duplicates most of a block. Mission two puts you in exactly that situation.

Sharing and copy-on-write

Because blocks are reference-counted, several sequences can point at the same physical block. vLLM uses this for parallel sampling (n greater than one) and beam search: all samples share the prompt's blocks, and a block is copied only when one owner needs to write into a block another owner still uses. This is copy-on-write at block granularity, and it is the reason the lab's paged allocator charges each sample a copy of the partial prompt block and nothing else.

The arithmetic is worth doing once. Four samples from a 1,100-token prompt with contiguous slabs store the prompt four times: 4,400 tokens before any output. With sharing, the prompt costs 1,100 tokens (68 full 16-token blocks plus one partial block copied per sample, so about 1,150 in total). The same mechanism generalises to sharing prefixes across requests: a system prompt or few-shot examples that every request starts with can live in blocks that many requests reference. That is automatic prefix caching, covered in the prefix caching guide in this series.

Paging introduces preemption

Paging changes the admission question. A contiguous allocator knows the worst case at admission and never runs out mid-sequence. A paged allocator admits a request when its current blocks fit, which is what makes it efficient, but it means the running set can collectively grow past the pool. When a sequence needs a new block and the free list is empty, the scheduler must evict someone. vLLM evicts the most recently admitted sequence group and later either recomputes its KV from scratch (prompt plus tokens generated so far, run as a prefill) or, in versions that support it, swaps its blocks to CPU memory and back.

Occasional preemption is fine. A storm is not: under memory pressure, a sequence can be admitted, grow, be evicted, be readmitted and pay its prefill again, while every running stream sees the extra prefill work in its step time. The usual triggers are traffic shifting toward longer outputs (report generation, code), a smaller KV budget after a model or precision change, or a too-generous max_num_seqs. In the lab, mission three starts on 2 GB with long-report users and dozens of preemptions. Lowering the running-sequence cap swaps preemptions for queueing; a modest amount of extra memory fixes both. Which one is right depends on whether you are short of memory or merely over-admitting.

Detection is straightforward if you export the scheduler's counters. Alert on the preemption rate, on KV cache usage that sits near 100% for long periods, and on waiting-queue depth. vLLM exposes metrics for these on its Prometheus endpoint; names have changed across versions, so check the metrics documentation for the release you run.

The knobs in real servers

Every major server now pages its KV cache. The names differ; the questions are the same. Treat the flags below as pointers and confirm names and defaults in your version's documentation.

Hugging Face TGI also uses a paged cache and sizes it from free memory, with admission bounded by --max-batch-total-tokens and related limits. In vLLM, the startup log reports how many KV tokens or blocks were allocated and the maximum concurrency that implies for the configured context length; record that line for every deployment, because it is the single most useful capacity number you have. A contiguous-virtual-memory alternative also exists: vAttention keeps the KV cache virtually contiguous and uses the GPU's virtual memory support to map physical pages on demand, which avoids rewriting attention kernels. The trade-offs are the same; only the mechanism differs.

A worked example: one replica for Belgavi's Book Store

The hypothetical Belgavi's Book Store runs a catalogue assistant on one GPU. After weights and activation headroom, suppose 24 GiB is left for KV, and the model costs 128 KiB per token. That is 196,608 tokens. Logs (synthetic here) show a mean prompt of 1,100 tokens with retrieval context, a mean answer of 250, and a p99 answer of about 1,150; the team set max_tokens to 2,048.

• Contiguous, reserve prompt + 2,048: about 3,150 tokens per request, so at most 62 sequences, fewer once holes appear. At the end of each sequence 43% of its slab is used; averaged over its life, less.
• Contiguous, reserve the 8,192-token context: 24 sequences. This is what a server sized for its maximum context length does.
• Paged, 16-token blocks: average live context is roughly 1,100 + 125 = 1,225 tokens, plus 8 tokens of tail waste, so about 159 sequences fit before preemption.

Memory is no longer the binding limit with paging; the per-token latency budget is. If the step-time model from the continuous batching guide says p95 time per output token crosses the target at 64 running sequences, then max_num_seqs should be about 64, and the replica has 2.5 times more KV than it needs at that concurrency. The team can spend that slack on longer contexts, keep it as protection against long-output surges, or move to a smaller and cheaper GPU. Mission four in the lab asks for exactly this decision: hold the burst latency targets on the smallest KV memory you can.

Failure modes and common mistakes

• Setting --max-model-len far above real traffic. With paging this no longer reserves memory per request, but the server still checks at startup that at least one maximum-length sequence fits, and some schedulers budget for it. Raise it when you need it, not by default.
• Treating --gpu-memory-utilization as a KV setting. In vLLM it is a fraction of total GPU memory that the instance may use, weights and activations included; KV gets what is left. Two instances on one GPU each need their own fraction.
• Changing block size without checking the backend. Some attention backends support only certain block sizes, and changing it can silently switch kernels.
• Ignoring preemption counters. Recompute preemption looks like random latency spikes in dashboards that only show TTFT and TPOT.
• Sizing by average output length. Paging means you no longer pay for the worst case at admission, but the running set still has to survive the moments when many sequences are long at once. Size with p95 or p99 concurrency, not the mean.

Run the lab: Contiguous vs paged KV: stop reserving memory you never write

The lab simulates sixty seconds of synthetic traffic on one GPU with either a contiguous first-fit allocator or a paged block allocator. The top of the canvas is the physical KV memory map: each cell is a slice of memory, coloured by the request that owns it, filled in proportion to live tokens, and dark red where memory is allocated but empty. The chart below tracks allocated and live memory over time. Start with the contiguous default, then work through the missions; each loads a broken setup and asks you to fix it the way you would on a real server.

Prefer a full-width view? Open the standalone lab. Your stars are saved in this browser and shown on the series hub.

What to do next

1. Compute KV bytes per token for every model you serve (2 × layers × KV heads × head dim × bytes) and write it next to the deployment config.
2. Find the startup log line that reports allocated KV tokens or blocks and maximum concurrency, and record it for each replica type.
3. Export and alert on KV cache usage, waiting-queue depth and preemption counts; check the metric names for your server version.
4. Set max_num_seqs from your per-token latency SLO, then check that p99 concurrency of real token lengths fits the KV pool without preemption.
5. Leave block size at the default unless a benchmark with your kernel backend shows a gain; never change it without checking supported values.
6. Try an FP8 KV cache in a canary if memory is the binding limit, and compare quality on your own evaluation set before rolling out.

Sources and further reading

• Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023)
• vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention (vLLM blog)
• vLLM documentation: engine arguments
• vAttention: Dynamic Memory Management for Serving LLMs without PagedAttention
• Orca: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022)

Related in this series:

• KV Cache Capacity Planning: How Many Concurrent Users Fit on One GPU
• Prefix Caching With Radix Trees: Reusing Prompt Work Across Requests
• KV Cache Preemption in vLLM: Swap, Recompute and Behavior Under Memory Pressure

Diagrams, examples and the lab model are original educational material. Lab numbers are calculated by a synthetic model, not measured on real hardware or services.

Views are my own and do not represent any employer, past or present.