DEV Community

jidonglab
jidonglab

Posted on

PagedAttention: Why Static Batching Wastes Your KV Cache

Take a single A100 running Llama-2-13B. Run it with naive batching and you might serve 8 concurrent requests before you OOM. Swap the serving engine for vLLM, same GPU, same model, same weights — now you serve 20+. Nothing about the math of attention changed. What changed is how the KV cache is allocated in GPU memory. Old servers threw away most of it to fragmentation. PagedAttention is the trick that stops the bleeding, and it's why your KV cache stops being the bottleneck.

TL;DR

  • Naive LLM serving pre-reserves KV cache for each request's maximum possible length, so a 30-token reply inside a 2048-token reservation wastes ~98% of that block. The vLLM paper measured 60–80% of KV memory lost to fragmentation and over-reservation.
  • PagedAttention treats the KV cache like OS virtual memory: split it into fixed-size blocks (default 16 tokens), allocate blocks on demand, and map logical → physical blocks through a per-sequence block table.
  • This eliminates external fragmentation entirely and caps internal fragmentation at one partial block per sequence, so you fit far more concurrent sequences in the same VRAM.
  • Shared prefixes (system prompts, parallel samples, beam search) share physical blocks via copy-on-write — one copy of the prompt KV, not N.
  • Pair it with continuous batching (iteration-level scheduling) and tune gpu_memory_utilization and block_size; that combination is where the throughput actually comes from.

Why does static KV cache allocation waste so much memory?

Because it reserves for the worst case and frees nothing until the sequence ends. Every decode step, a transformer caches the key and value vectors for every token so it doesn't recompute attention over the whole prefix. That cache grows by one token's worth of K and V per step, per layer. The size is not small:

kv_bytes_per_token = 2 (K and V)
                   × num_layers
                   × num_kv_heads
                   × head_dim
                   × dtype_bytes

# Llama-2-13B, fp16, full multi-head attention:
# 2 × 40 × 40 × 128 × 2  ≈  819,200 bytes  ≈  0.8 MB per token
Enter fullscreen mode Exit fullscreen mode

At ~0.8 MB/token, a single 2048-token sequence needs about 1.6 GB of KV cache. That's the real constraint on concurrency — not FLOPs, memory.

Now the failure. A traditional server (think early HuggingFace TGI-style or the request-level batching in the original Orca setup) doesn't know how long a reply will be, so it reserves a contiguous slab sized to max_seq_len up front. Three things go wrong at once:

  • Internal fragmentation. You reserve 2048 tokens, the model emits 30 and hits a stop token. The other 2018 slots are yours, allocated, and useless until the request completes.
  • Reservation waste. Even tokens you will generate are reserved before they exist, so they sit idle for most of the request's life.
  • External fragmentation. Contiguous slabs of different sizes leave unusable gaps between them, exactly like malloc fragmentation.

Add it up and the paper's number — 60–80% of KV memory wasted — stops sounding surprising. You bought 80 GB of HBM and you're using 20 of it for actual tokens.

What does PagedAttention actually do differently?

It borrows virtual memory paging from operating systems. Instead of one contiguous KV region per sequence, the cache is carved into fixed-size blocks, each holding a fixed number of tokens (vLLM's default block_size is 16). A sequence's KV cache becomes a list of blocks that need not be contiguous in physical GPU memory. A block table per sequence maps logical block numbers to physical block numbers — the exact analogue of a page table mapping virtual pages to physical frames.

The consequences fall out directly:

  • Blocks are allocated on demand, one at a time as generation crosses a 16-token boundary. Nothing is reserved for tokens that don't exist yet.
  • External fragmentation disappears. All blocks are the same size, so any free block fits any sequence. There are no odd-sized gaps.
  • Internal fragmentation is bounded. The only waste is the unfilled tail of a sequence's last block — at most block_size - 1 tokens, so ≤15 tokens per sequence regardless of how long the sequence is.

The catch is that attention now reads K and V from physically scattered blocks, which a stock attention kernel can't do — it assumes contiguous memory. So PagedAttention ships a custom CUDA kernel that walks the block table and gathers KV per block during the attention computation. That kernel is the whole reason this is a serving-engine feature and not something you bolt on in Python.

How does copy-on-write eliminate duplicate prompt KV cache?

By letting multiple sequences point their block tables at the same physical blocks until one of them writes. This is where paging pays a second dividend.

Consider parallel sampling: one prompt, n=4 completions. The prompt's KV cache is identical for all four. Naive allocation stores it four times. With PagedAttention, all four sequences' block tables reference the same physical prompt blocks — one copy. When a sequence needs to diverge (it starts generating its own tokens into a shared block), the engine copies just that block and remaps the pointer. Copy-on-write, per block, exactly like fork().

The same mechanism covers beam search and shared system prompts across a batch. If every request in a batch begins with the same 800-token system prompt, you can store that prompt's KV once instead of once per request. For agent workloads that stuff huge identical preambles into every call, this is a large, free memory win — and it composes with prefix caching so the shared prefix isn't even recomputed.

Isn't continuous batching the thing that actually boosts throughput?

Yes — and this is the part people conflate with PagedAttention. They're two different ideas that vLLM combines. PagedAttention is about memory layout. Continuous batching (a.k.a. iteration-level scheduling, from the Orca paper) is about scheduling.

Static batching processes a batch to completion: 8 requests go in, the batch runs until every one finishes, and the whole batch is gated by the slowest, longest generation. A request that finishes at token 20 keeps its slot occupied while a neighbor grinds to token 2000.

Continuous batching schedules at the granularity of a single decode iteration. After each forward step, finished sequences leave the batch and waiting requests join immediately. No sequence waits for the batch's slowest member. GPU utilization stays high because the batch is continuously topped up.

These two features need each other. Continuous batching means sequences constantly enter and leave with wildly different lengths — which would shred a contiguous allocator with fragmentation. PagedAttention's uniform blocks make that churn cheap: a departing sequence frees blocks that any arriving sequence can immediately reuse. Paging makes fluid scheduling affordable; scheduling turns the freed memory into throughput.

What happens when the GPU runs out of KV blocks?

The scheduler preempts. Because vLLM admits requests aggressively to keep the batch full, it can overcommit and hit zero free blocks mid-generation. It has two recovery strategies:

  • Recomputation. Evict a sequence's KV blocks, and when it's rescheduled, recompute its KV cache from the tokens in one prefill pass. Cheap in memory, costs a recompute.
  • Swapping. Copy the evicted blocks to CPU RAM over PCIe, then copy back when rescheduled. No recompute, but you pay PCIe bandwidth.

Both cost latency, so preemption is a signal you're running too hot. If you see it in logs, either lower concurrency or raise the memory ceiling. Which brings us to config.

How do I configure vLLM to use this well?

The two knobs that matter most are gpu_memory_utilization and block_size.

from vllm import LLM

llm = LLM(
    model="meta-llama/Llama-2-13b-hf",
    # Fraction of VRAM vLLM may claim. Default 0.9.
    # Everything left after weights + activations becomes the KV block pool.
    gpu_memory_utilization=0.92,
    # Tokens per KV block. Default 16.
    # Smaller  -> less tail waste, larger block tables, more kernel overhead.
    # Larger   -> more internal fragmentation, simpler bookkeeping.
    block_size=16,
    max_num_seqs=256,          # cap on concurrent sequences
    enable_prefix_caching=True # reuse shared prompt KV across requests
)
Enter fullscreen mode Exit fullscreen mode 
# Same thing for the OpenAI-compatible server
vllm serve meta-llama/Llama-2-13b-hf \
  --gpu-memory-utilization 0.92 \
  --block-size 16 \
  --enable-prefix-caching \
  --max-num-seqs 256
Enter fullscreen mode Exit fullscreen mode

Practical guidance:

  • gpu_memory_utilization decides how big the block pool is. vLLM loads weights, measures activation peak, then hands the rest to the KV pool. Push it toward 0.90–0.95 for max concurrency; back off if you see CUDA OOM during activation spikes on long prompts.
  • block_size trades tail waste against overhead. The default 16 is right for most workloads. Larger blocks help kernel efficiency on very long sequences at the cost of more internal fragmentation.
  • enable_prefix_caching is close to free money whenever requests share a prefix — system prompts, few-shot preambles, RAG templates. It reuses both the memory (via shared blocks) and the compute (skips prefill on the shared span).
  • Watch the logs for preemptions and low KV cache usage %. Preemptions mean overcommit; chronically low usage means you can raise max_num_seqs.

The direct answer

Static LLM serving wastes your KV cache because it pre-reserves a contiguous block sized to each request's maximum length, then frees nothing until the request ends — losing 60–80% of KV memory to internal, reservation, and external fragmentation. PagedAttention fixes this by paging the KV cache into fixed-size blocks (default 16 tokens) mapped through per-sequence block tables, so memory is allocated on demand, external fragmentation vanishes, internal fragmentation is capped at one partial block per sequence, and identical prefixes share physical blocks via copy-on-write. Combine it with continuous batching, set gpu_memory_utilization near 0.9, enable prefix caching, and the same GPU serves roughly 2x the concurrent requests — not because attention got faster, but because you stopped throwing your KV cache away.

Top comments (0)