How vLLM Serves Thousands: Paging, Batching and Caching

PagedAttention, continuous batching, chunked prefill and prefix caching, each built from the problem it solves and measured or simulated with real costs: from 48 to 415 requests on one GPU, pauses cut from 463 ms to 40 ms, and a 7x faster first token.

Part 1 ended with a rule: to make a GPU productive, decode many sequences at once. Part 2 ended with the catch: every sequence carries a KV cache that grows unpredictably, and the obvious way of storing it wasted most of the memory. Older serving systems used only 20.4% to 38.2% of their KV memory for real data.

In 2023 a team at UC Berkeley looked at this and noticed something familiar. A program that needs memory it cannot predict, a limited physical memory, lots of programs sharing it: that is exactly the problem operating systems solved in the 1960s. Their fix was called paging. The Berkeley team applied it to the KV cache, called it PagedAttention, and built a serving engine around it: vLLM.

This part walks through vLLM's four big ideas, each one built from the problem it solves:

1. PagedAttention: store the cache in small blocks, so almost nothing is wasted.
2. Continuous batching: let requests join and leave the batch at every step.
3. Chunked prefill: keep long prompts from freezing everyone else.
4. Prefix caching: never compute the same prompt twice.

Idea 1: store the cache in pages#

Your laptop runs dozens of programs, and none of them knows where in physical memory its data really lives. Each program sees a neat, continuous address space. Behind the scenes the operating system chops that space into small fixed-size pages and puts each page wherever there is room. A page table records where each one went. A program that needs more memory simply gets another page; nobody has to reserve the maximum up front.

vLLM does the same with the KV cache. The cache is cut into blocks of 16 tokens each (vLLM's default block size). A request's cache is a list of blocks, in order, but the blocks themselves can sit anywhere in GPU memory. A block table records the mapping.

Now look at what happens to the three kinds of waste from Part 2:

• Reserved slots disappear: a request gets a new block only when its last block fills up.
• Internal fragmentation shrinks to at most one partly filled block per request, fewer than 16 tokens.
• External fragmentation disappears: every block is the same size, so any free block fits any request.

The attention computation has to change a little, because a sequence's keys and values are no longer in one continuous stretch of memory. The PagedAttention kernel reads them block by block, following the block table. That indirection is the price of the idea: the paper measured the attention step itself at 20 to 26% slower than a highly optimised contiguous kernel. The authors judged it small because it only affects attention, not the rest of the model, and the memory it frees buys far more. Why 16 tokens per block? Big enough to keep the GPU busy, small enough that the last, partly filled block wastes little; the paper found 16 the best balance "in most workloads."

How much memory does it save?#

To see the effect, I simulated 200,000 requests on a single 80 GB GPU serving Llama 3.1 8B (128 KiB of cache per token, from Part 2). Prompt and answer lengths were drawn from wide, realistic spreads, and each request was caught at a random moment in its life. The question: of the memory each policy sets aside, how much actually holds tokens, and how many requests fit at once?

Paging does better than even the "oracle" that magically knows every answer's length, because the oracle still reserves space for tokens that have not been written yet. My simulation leaves out external fragmentation, which only makes the contiguous policies look better than they are.

The real system agrees. The vLLM paper measured existing systems at 20.4% to 38.2% useful KV memory and vLLM at 96.3%, and reported 2 to 4 times the throughput of the leading systems of the time "with the same level of latency."

Sharing blocks for free#

Blocks bring a bonus: two requests can point at the same physical block. Many requests share a beginning. Think of a chatbot's long system prompt, or one prompt sampled several times to get several answers. With paging, those shared tokens are stored once.

Each block carries a reference count. When a request needs to write into a block that others share, vLLM copies that one block first and then writes (copy-on-write, the same trick an operating system uses when a process forks). Everything else stays shared.

Idea 2: prefix caching#

Sharing within the requests running right now is good. Sharing across time is better. If a thousand users send requests that start with the same 2,000-token system prompt, why compute its keys and values a thousand times?

vLLM's automatic prefix caching keeps finished blocks around after a request ends. Each full 16-token block gets a hash built from its tokens and the hash of the block before it, so a hash identifies not just 16 tokens but the entire prefix leading up to them. When a new request arrives, vLLM looks up its blocks by hash, reuses every one it finds, and only runs prefill for the rest.

I measured the effect directly: a 2,048-token shared system prompt followed by a 64-token question.

That is 7 times faster, and the next token it predicts is identical: the largest difference in any output score between the two runs was exactly 0.0. The saved prefill is not an approximation; it is the same arithmetic, done once instead of twice.

Idea 3: continuous batching#

Batching (Part 1) is only useful if the batch stays full. The simple way to batch is static: gather 64 requests, run them together until they are all finished, then take the next 64. The problem is that answers have wildly different lengths. A request that finishes after 20 tokens leaves its slot empty while the batch waits for the one that runs to 2,000.

Continuous batching, introduced by the Orca system (Yu et al., OSDI 2022) as iteration-level scheduling, decides who is in the batch at every single step. The moment a request finishes, its slot goes to the next one in line.

I simulated 4,096 requests with realistic answer lengths through 64 slots:

Same requests, same slots, 4.6 times fewer steps. The exact ratio depends on how uneven the answer lengths are, but the direction never changes. Orca reported a 36.9x throughput improvement over NVIDIA FasterTransformer on GPT-3 175B "at the same level of latency."

Continuous batching and paging need each other. Requests joining and leaving at every step would shred a contiguous memory layout; with fixed-size blocks, a finished request just hands its blocks back to the free pool.

In vLLM's current engine (called V1, the default since version 0.8 in 2025), the batch for each step is flattened into one long "super sequence": every scheduled token from every request laid end to end, with position indices and attention masks keeping each request's tokens to themselves. No padding, no wasted slots.

Idea 4: chunked prefill#

There is one more collision to deal with. Prefill and decode have opposite personalities (Part 1). Decode steps are short and frequent. A prefill for a long prompt is one huge step. If a user sends an 8,192-token document while 16 other users are streaming answers, what happens?

Without any special handling, that prefill runs as one step, and every streaming user freezes until it is done. From their point of view the text just stops.

Chunked prefill cuts the long prompt into slices and adds one slice to each step, next to the regular decodes. Using the costs measured in Part 1 (16 decodes: 12.8 ms; a 512-token prefill: 27.4 ms; an 8,192-token prefill: 450.5 ms):

(These are estimates built by adding measured step costs, not a measured mixed batch. Later slices cost a little more than the first, because they attend to the slices before them, so the real chunked numbers would be slightly higher. The trade they show is the real one.)

The streaming users' worst pause drops from almost half a second to 40 ms. The price is that the long prompt's first token arrives later, because its prefill is now spread over 16 steps. That is the trade vLLM's documentation describes for its main knob here, --max-num-batched-tokens: smaller values give better inter-token latency, larger values give better time to first token.

This idea was developed in Sarathi-Serve (Agrawal et al., OSDI 2024), which reported 2.6x higher serving capacity than the vLLM of the time for Mistral-7B on one A100. In vLLM V1, chunked prefill is on by default, and the scheduler fills each step's token budget with decodes first, then prefill chunks.

When memory runs out anyway#

Paging makes memory go much further, but a GPU can still fill up: many long answers all growing at once. When a running request needs a new block and none is free, vLLM preempts someone. It frees that request's blocks and puts it back in the queue. When the request is scheduled again, its cache has to be rebuilt.

There are two ways to rebuild it: copy the blocks out to CPU memory and back (swapping), or simply throw them away and recompute them with a prefill (recomputation). Recomputation sounds wasteful, but the tokens already generated can be prefilled together with the original prompt in one compute-bound pass, and prefill is the fast phase. In vLLM V1 the default is recompute, which the docs say "has lower overhead in the V1 architecture."

The whole engine, in one loop#

Put it all together and vLLM's core is a surprisingly small loop that runs every few milliseconds:

1. Schedule. Decide what runs this step: first the running requests that need their next token, then chunks of waiting prompts, within a token budget and the free blocks available.
2. Forward pass. Flatten everything scheduled into one batch and run the model once.
3. Post-process. Append each sampled token to its request, return finished requests' blocks to the pool, and loop.

The knobs that matter#

Most of these ideas are on by default. These are the settings people actually tune:

Engine arguments change between releases, so check them against the version you run (vllm serve --help).

Beyond one GPU: two ideas to know#

Disaggregated prefill and decode. Chunked prefill makes the two phases share a GPU politely. The more radical option is to put them on different GPUs: some GPUs only prefill, others only decode, and the KV cache is sent from one to the other. DistServe (Zhong et al., OSDI 2024) showed this can serve up to 7.4x more requests, or meet 12.6x tighter latency targets, because each phase can be sized and tuned for its own bottleneck.

Speculative decoding. Part 1 measured that processing 16 tokens costs about the same as processing one (10.8 ms against 10.0 ms). Speculative decoding (Leviathan et al. and Chen et al., 2023) exploits that directly. A cheap drafter proposes the next few tokens, and the big model checks them all in one pass, keeping every guess up to the first one it disagrees with and correcting that one. With the right acceptance rule, the output follows exactly the same distribution as if the big model had written every token itself, so it is faster without being approximate. The gain depends on how often the guesses are right, and it shrinks when the GPU is already busy with a large batch, because the spare compute it spends is no longer spare. vLLM supports several drafters, including n-gram lookup, EAGLE and Medusa. Part 4 builds speculative decoding from scratch and measures it.

The series, on one page#

Every one of these ideas comes back to the two facts from Part 1: decode is limited by memory, not math, and a GPU is only productive when it is decoding many sequences at once. vLLM's whole design is a way of fitting as many sequences as possible into memory, and keeping every step full.

"""KV allocation policies and static vs continuous batching (pure Python + numpy)."""
import heapq, math
import numpy as np

rng = np.random.default_rng(42)

# ---- how much KV memory each policy wastes (Llama 3.1 8B on one 80 GB GPU)
PER_TOKEN = 2 * 32 * 8 * 128 * 2                    # 128 KiB, from the config
BUDGET = 0.9 * 80e9 - 8.03e9 * 2 - 4e9              # 90% of memory, minus weights and ~4 GB working memory
N, MAX_LEN, MAX_TOKENS, BLOCK = 200_000, 8192, 2048, 16
prompt = np.clip(rng.lognormal(math.log(512), 0.9, N), 16, 6000).astype(int)
output = np.clip(rng.lognormal(math.log(256), 0.9, N), 8, MAX_TOKENS).astype(int)
now = prompt + (rng.uniform(0, 1, N) * output).astype(int)   # a random moment in each request's life

policies = {
    "reserve max length": np.full(N, MAX_LEN),
    "reserve prompt + max_tokens": prompt + MAX_TOKENS,
    "reserve exact final length": prompt + output,
    "paged, 16-token blocks": np.ceil(now / BLOCK).astype(int) * BLOCK,
}
for name, reserved in policies.items():
    print(f"{name:28s} useful {now.sum() / reserved.sum():6.1%}   fits {BUDGET / (reserved.mean() * PER_TOKEN):5.0f} requests")

# ---- static vs continuous batching: 4,096 requests, 64 slots
SLOTS = 64
lens = np.clip(rng.lognormal(math.log(256), 0.9, 4096), 8, 2048).astype(int)
static = sum(lens[i:i + SLOTS].max() for i in range(0, len(lens), SLOTS))
free = [0] * SLOTS
for L in lens:
    heapq.heappush(free, heapq.heappop(free) + L)
continuous = max(free)
print(f"static {static:,} steps, continuous {continuous:,} steps, {static / continuous:.1f}x")

References#

1. W. Kwon et al. Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023.
2. G.-I. Yu et al. Orca: A Distributed Serving System for Transformer-Based Generative Models. OSDI 2022.
3. A. Agrawal et al. Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve. OSDI 2024.
4. Y. Zhong et al. DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving. OSDI 2024.
5. Y. Leviathan, M. Kalman, Y. Matias. Fast Inference from Transformers via Speculative Decoding. ICML 2023.
6. C. Chen et al. Accelerating Large Language Model Decoding with Speculative Sampling. 2023.
7. vLLM team. Inside vLLM: Anatomy of a High-Throughput LLM Inference System. 2025.
8. vLLM documentation: Optimization and tuning, Engine arguments.