PagedAttention and Continuous Batching Explained (2026)

PagedAttention stores each request's KV cache in small fixed-size blocks that can sit anywhere in GPU memory, the way an operating system pages virtual memory, so almost none of the cache is wasted on reservations. Continuous batching schedules work one decode step at a time, so finished requests leave the batch and new ones join immediately. Together they let one GPU serve far more concurrent requests, and they are the two ideas behind modern engines such as vLLM and SGLang.

This post explains the mechanism, works the memory math on a real model, and then covers the two features that build on top of paging: chunked prefill and prefix caching. It is part of our guide to LLM inference engines.

TL;DR

• The KV cache is the thing you are paging. It grows by one entry per token per request, and the old way of reserving it (one contiguous slab sized for the maximum length) wasted most of it. Paging fixes that.
• PagedAttention is a memory manager, not a faster kernel. Its win is fitting more requests in the same VRAM, which is what raises throughput. The vLLM authors report 2 to 4 times higher throughput than FasterTransformer and Orca at the same latency.
• Continuous batching is the scheduler half. Without it, one long answer holds the whole batch hostage. Every serious engine now does it, so you rarely choose it, you just need to know what it does to your latency.
• Chunked prefill and prefix caching are the two tuning levers. Chunked prefill protects inter-token latency from long prompts. Prefix caching removes repeated prefill for shared system prompts and documents.
• Verdict: if you serve more than a handful of concurrent users, use an engine with all four. Do not hand-roll batching around a plain Hugging Face generate loop.

Why the KV cache is the problem

During decoding, every layer keeps a key vector and a value vector for every token seen so far. That is the KV cache, and it is what lets each new token cost one step instead of a full re-read of the prompt. Its size per token is:

bytes per token = 2 (K and V) x layers x KV heads x head dimension x bytes per value

Two checks of that formula (both computed):

• OPT-13B, which the PagedAttention paper uses: 40 layers and a hidden size of 5,120 (from its Hugging Face config), 2 bytes per value. That gives 2 x 40 x 5,120 x 2 = 819,200 bytes, which is the 800 KB per token the paper states.
• Llama 3.1 8B: 32 layers, 8 KV heads (grouped-query attention) and a head dimension of 4,096 / 32 = 128, from its config. At FP16 that is 2 x 32 x 8 x 128 x 2 = 131,072 bytes, or 128 KiB per token. An 8,192-token sequence therefore holds about 1.07 GB of cache for one request (computed).

Grouped-query attention is why a modern 8B model costs far less per token than the older 13B model. It does not remove the problem, it just moves the number where you hit it.

The old way: one big reservation per request

Before paging, engines gave each request one contiguous buffer. You do not know how long the answer will be, so the buffer is sized for the maximum. The PagedAttention paper (Kwon et al., SOSP 2023) measured what that costs: in the systems it studied, only 20.4% to 38.2% of KV cache memory held actual token states. The rest was internal fragmentation (reserved but never used), external fragmentation (gaps the allocator cannot reuse) and over-provisioning. The vLLM launch post summarises it as existing systems wasting 60% to 80% of KV memory.

Less usable memory means a smaller batch, and a smaller batch means a GPU that spends its time streaming weights to serve few requests. Throughput is limited by memory management, not by arithmetic.

PagedAttention: a block table for the KV cache

PagedAttention splits each sequence's cache into fixed-size blocks (the paper sets a default block size of 16 tokens) and keeps a per-request block table that maps logical blocks to wherever the physical blocks actually are. The attention kernel reads through that table, so blocks do not need to be contiguous. Memory is allocated one block at a time as the sequence grows, so the only waste is the unused tail of each request's last block.

Two further properties come from having a block table:

• Sharing. Blocks can be shared between sequences. For parallel sampling and beam search, the paper reports memory savings of 6.1% to 9.8% and 37.6% to 55.2% respectively, using copy-on-write at block granularity when a shared block has to diverge.
• No relocation. Because blocks are independent, freeing one request frees whole blocks that any other request can take immediately.

Worked example (computed)

Take Llama 3.1 8B at FP16 on an 80 GB card, serving requests that mostly end up around 1,000 tokens long but could in principle reach 8,192.

The paged figure wastes 8 token slots per request (1,008 minus 1,000), about 1 MiB. The reservation figure wastes the other 7,192 slots. This is an upper bound on the gain, because real runs also spend memory on activations, CUDA graphs and fragmentation across block sizes, and because whether you can actually keep 424 requests busy depends on compute. But it shows the shape of the win: the same VRAM, roughly eight times as many sequences resident.

The same arithmetic is what the vLLM flags tune. --gpu-memory-utilization sets the 72 GB, --max-model-len caps the per-request maximum, and --block-size sets the block (see the vllm serve CLI reference in the sources).

Continuous batching: scheduling per step

Static batching groups requests, runs the group until every member finishes, then starts the next group. Output lengths differ, so short requests sit finished while long ones keep going.

A tiny example (computed): three requests in one static batch need 10, 50 and 200 output tokens. The batch runs 200 steps with three slots, which is 600 slot-steps, but only 10 + 50 + 200 = 260 of them do useful work. That is 43% utilization, and the 10-token request cannot return until step 200 if the server only responds when the batch ends.

Continuous batching, introduced as iteration-level scheduling in the Orca paper (OSDI 2022), changes the unit of scheduling from the request to the iteration. After every decode step the scheduler can retire finished requests and admit waiting ones. The Orca authors report a 36.9 times throughput improvement over NVIDIA FasterTransformer at the same latency on a GPT-3 175B model (their result, on their setup). vLLM combines the same idea with paging, so an admitted request only needs blocks, not a pre-sized slab.

The two features need each other. Continuous batching wants to admit new requests at any step, which is only cheap if admission is just allocating blocks. Paging wants many requests resident, which is only useful if the scheduler keeps them all moving.

Chunked prefill

A prompt is processed in one parallel pass (prefill), and that pass can be long. In a continuous batch it competes with other requests' decode steps, and a 30,000-token prefill can stall every user's token stream for its duration.

Chunked prefill splits a long prefill into pieces and mixes them with decodes in the same batch. The Sarathi paper that introduced it ("decode-maximal batching") reports, for its setups, up to 10 times higher decode throughput on LLaMA-13B on an A6000 and 1.25 times end-to-end throughput on LLaMA-33B on an A100.

In vLLM's V1 engine the scheduler serves all pending decodes first and spends the remaining max_num_batched_tokens budget on prefill, chunking a prompt that does not fit. The vLLM docs state it is enabled by default whenever possible, and give the tuning rule:

• A smaller max_num_batched_tokens (for example 2048) gives better inter-token latency, because less prefill sits in each step.
• A larger value gives better time to first token, because more prompt tokens are processed per step.
• For throughput, the docs suggest setting it above 8192, especially for smaller models on large GPUs.

Our guide to TTFT and tokens per second shows how to measure the trade this makes.

Prefix caching

If many requests start with the same tokens (a long system prompt, a shared document, the history of a chat), their KV blocks are identical and need not be recomputed.

vLLM hashes each full block from its parent block's hash, its own tokens and extra keys (LoRA ID, multimodal inputs, an optional per-request cache salt). A new request looks up its blocks by hash and reuses any that exist, and unreferenced blocks are evicted least-recently-used. Only full blocks are cached, so the tail of a prefix shorter than a block is recomputed. The default hash is sha256 (since v0.11), which matters in multi-tenant settings where a weak hash could collide, and the cache salt lets you isolate tenants.

Computed example: a 2,100-token prompt whose first 2,000 tokens are a shared system prompt contains 131 full 16-token blocks (2,096 tokens). The first 125 blocks (2,000 tokens) are shared, so only about 100 tokens of prefill remain on a cache hit. The vLLM docs are explicit about the limit: caching only shortens prefill. It does nothing for decode, so it helps less when responses are long, and it gives no benefit when requests do not share a prefix.

SGLang stores prompts and generated results in a radix tree (RadixAttention) with least-recently-used eviction of leaf nodes and a cache-aware scheduler. The SGLang authors report up to 5 times higher throughput than their baselines on their benchmarks (Llama-7B on one A10G, Mixtral-8x7B on eight), and say it works with continuous batching and paged attention.

Check whether prefix caching is on by default for your engine version before you rely on it: the vLLM pages we read describe the mechanism but we did not find a default stated there, so set the flag explicitly.

Which engines implement what

Attention kernels that understand paged KV layouts, such as FlashInfer, are what make reading through a block table fast. For choosing between engines, see vLLM vs TensorRT-LLM vs SGLang and the walkthrough in serving LLMs with vLLM.

Try the knobs

These flags come from the vllm serve CLI reference. Start from the defaults, then change one at a time while watching time to first token and inter-token latency:

vllm serve meta-llama/Llama-3.1-8B-Instruct \
  --gpu-memory-utilization 0.90 \
  --max-model-len 8192 \
  --max-num-batched-tokens 8192 \
  --enable-prefix-caching

Lower --max-model-len if the server reports too little KV cache for your concurrency, and watch the preemption count: when the cache runs out, vLLM V1 preempts requests and recomputes them later, which hurts latency. The docs list the fixes in order: raise --gpu-memory-utilization, lower --max-num-seqs or --max-num-batched-tokens, or add tensor parallelism.

Run it on a cloud GPU

Paging pays off most where VRAM is large, because the cache is what fills it. An H100 or H200 gives you the room to see the effect of each flag above.

FAQ

Is PagedAttention a different attention algorithm?

It computes the same attention. What changes is where the keys and values live: in non-contiguous blocks found through a block table. The paper reports no change in model accuracy.

What block size should I use?

The paper uses 16 tokens and vLLM exposes --block-size. Smaller blocks waste less on the last block but add table overhead, and some attention backends only support certain sizes, so leave it at the default unless a backend requires otherwise.

Does continuous batching increase latency?

It raises throughput by keeping the batch full, and each request waits less for a slot than under static batching. Per-step time does grow as the batch grows, so inter-token latency rises with concurrency. Measure at your real concurrency.

Do I need prefix caching if I have chunked prefill?

They solve different problems. Chunked prefill smooths latency when prompts are long. Prefix caching avoids recomputing prompts you have already seen. Many workloads want both.

Does prefix caching leak data between users?

Blocks are matched by hash, so only identical prefixes can hit. vLLM supports a per-request cache salt so only requests with the same salt share blocks, and a non-cryptographic hash raises collision risk in multi-tenant setups.

Does this apply to training?

No. This is an inference-time memory scheme for the KV cache. Training stores activations and gradients, which are a different problem.

Sources

• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention: https://arxiv.org/abs/2309.06180 (full text figures via https://ar5iv.labs.arxiv.org/html/2309.06180)
• vLLM launch post: https://vllm.ai/blog/2023-06-20-vllm
• vLLM paged attention design doc: https://docs.vllm.ai/en/latest/design/paged_attention.html
• vLLM automatic prefix caching design: https://docs.vllm.ai/en/latest/design/prefix_caching.html
• vLLM automatic prefix caching feature page: https://docs.vllm.ai/en/latest/features/automatic_prefix_caching.html
• vLLM optimization and tuning (chunked prefill, preemption): https://docs.vllm.ai/en/latest/configuration/optimization.html
• vLLM serve CLI reference: https://docs.vllm.ai/en/latest/cli/serve.html
• Yu et al., Orca (OSDI 2022): https://www.usenix.org/conference/osdi22/presentation/yu
• Agrawal et al., chunked prefills and decode-maximal batching: https://arxiv.org/abs/2308.16369
• SGLang RadixAttention post: https://www.lmsys.org/blog/2024-01-17-sglang/
• SGLang hyperparameter tuning docs: https://docs.sglang.io/advanced_features/hyperparameter_tuning.html
• OPT-13B config: https://huggingface.co/facebook/opt-13b/raw/main/config.json
• Llama 3.1 8B config: https://huggingface.co/NousResearch/Meta-Llama-3.1-8B/raw/main/config.json