Why your vLLM p99 latency blows up in production and how chunked prefill and scheduling fix it

PagedAttention is about KV cache memory. It is not a scheduler. The idea, from the vLLM paper (Kwon et al., 2023), is to treat the KV cache like virtual memory in an operating system. Instead of reserving one big block per sequence, it splits the cache into small fixed-size blocks that can sit anywhere in GPU memory. That cuts the space wasted on fragmentation, lets you keep more sequences in memory at once, and makes it cheap to share cache between sequences that share a prefix.

So where does latency come in? Only indirectly. Before PagedAttention, memory was usually the first limit you ran into on how many sequences you could hold in a batch, because each one had to over-reserve cache space for its worst-case length. Once memory stops being the thing that boxes you in, the scheduler has a lot more room to decide how to mix prefills and decodes. PagedAttention does not schedule anything. It just clears the runway so a good scheduler can do its job.

But clearing the memory constraint does not tell the scheduler how to fit a big prefill into the batch without stalling the decodes around it. That is the exact problem chunked prefill exists to solve.

Chunked prefill is the direct fix for the blocking problem. The idea is simple to say. Instead of running a long prefill all the way to the end in one iteration, you split it into smaller chunks of tokens. Then in each iteration you run one prefill chunk alongside the decodes that are already going. The decodes keep getting their turns, so the stream stays smooth, while the long prompt still makes steady progress in the background.

This is the “stall-free” scheduling idea from the Sarathi-Serve work (Agrawal et al.). In their tests, admitting prefills this way let a server handle up to 2.6x more traffic within the same latency target for Mistral-7B on a single A100, and up to 6.9x more for the much larger Falcon-180B spread across eight A100s, compared with Orca and vLLM.

The catch is chunk size, and this is where a lot of content stays too shallow. There is a real tradeoff:

• Chunks too small: decodes stay snappy, but the long prompt now needs many iterations to finish, so its own time to first token goes up. You also pay more per-iteration overhead and get less efficient prefill.
• Chunks too large: prefill finishes fast, but you are right back to the blocking you were trying to remove.

In vLLM you mostly control this through the per-iteration token budget (max_num_batched_tokens) with chunked prefill turned on. That budget is basically your chunk size dial. It is also the exact thing the Sarathi-Serve authors profile per deployment rather than hardcode; their experiments use budgets like 512 and 2048 and tune to the latency target, which is a sensible range to start testing from.

Chunked prefill is not the only answer to the prefill-versus-decode clash. There are three common approaches, and it is worth knowing where chunked prefill sits among them. Prefill-first just pauses the decodes to run the whole prefill, which is simple but causes the exact hitch shown above. Chunked prefill slices and interleaves, and it has become the default in most modern engines because it smooths latency without extra hardware. Disaggregation goes further and runs prefill and decode on separate pools of GPUs so the two phases never compete at all, which pays off mainly at very large scale. If you are on a single node, chunked prefill is almost always the right tool.

One more thing that usually gets missed: chunked prefill and PagedAttention interact. Chunking changes the memory access pattern of prefill, and it changes how your cache blocks fill up over time. These two are almost always explained on their own, but in a real deployment they compound. If you tune your token budget without thinking about cache behavior, you are only seeing half the picture.

Chunked prefill decides how the work gets sliced. Scheduling policy decides whose work runs first. Both shape the tail, and the second one is usually left on its default.

Here are the common policies and what they trade:

• FCFS (first come, first served): vLLM’s default. Simple and fair, but a burst of long prompts arriving together will still push everyone’s tail out, because nothing says “this decode is more urgent than that prefill.”
• Priority-based: You tag requests so some jump the queue. Handy when you have paid tiers or interactive traffic that must stay fast, but it can starve low-priority work if you are not careful.
• SLA-aware: The scheduler tries to hit a latency target per request instead of just ordering them. More work to run, but it is the only approach that goes straight at the number you actually care about.

The other half of scheduling is preemption, and this is where the tail really lives. When memory gets tight, the server has to kick out a sequence to keep going. vLLM can bring it back two ways: recompute its prefill from scratch later, or swap its KV cache out to CPU memory and back. Both are expensive. The key point is that they are rare. And rare, expensive events are exactly what set your p99. Your median request never gets preempted. The one that eats a huge penalty is the request sitting at your tail. So if you want to control p99, you control who gets preempted and how often. That is a scheduling decision.

Here is a rough guide to how the policies compare:

One common reason production numbers differ from benchmark results is that the benchmark was far cleaner than the real workload. This is not just a hunch. When researchers characterized real LLM serving traffic in ServeGen, they found that request arrivals are usually bursty, with a coefficient of variation above 1, which is another way of saying a fixed-rate or simple Poisson generator does not describe them well. The BurstGPT dataset makes the same point at scale: it collected more than 10 million real request traces from Azure’s OpenAI services over 213 days and found sudden bursts in how many requests are running at once. A synthetic test usually sends requests at a fixed rate, with uniform prompt lengths, from one client. Real traffic has three habits that break that:

• Bursty arrivals: Requests clump. Ten land in the same second, then nothing for three seconds. Bursts are when prefills pile up and block decodes.
• Mixed prompt lengths: A 50-token chat message and a 30,000-token document summary hit the same server. The long one is what stalls the short ones.
• Multi-tenant load: Lots of users share the GPU, so one person’s giant prompt becomes another person’s latency spike.

If you want your numbers to mean anything, test against traces that capture this, not against uniform load. Public datasets like BurstGPT and the Azure LLM inference traces give you real arrival patterns and real prompt and response length spreads. The test worth running is simple. Take one fixed config, run it under uniform load, then replay a real bursty trace through the same config. Report both. The published work already tells you what to expect: p50 barely moves while p99 climbs hard, because the tail is set by the bursts and the long prompts, not by the average request. That gap is what you should focus on. It is also the part almost no vendor benchmark shows you, which is exactly why publishing it earns trust.

Before you touch any config, work out which of the three problems you have. Look at your own traffic.

Are you prefill-bound? Your prompts are long compared to your outputs (RAG, document processing, long system prompts), and time to first token is your main complaint. Chunked prefill is your biggest lever here.

Are you decode-bound? Your outputs are long compared to your inputs (agents, long generations), and inter-token latency or throughput is the issue. Focus on batch size and memory headroom more than chunking.

Are you scheduling-bound? Your averages look fine but your tail gets worse under bursts. This is a policy and preemption problem.

Once you know which one you are, here are the first knobs to reach for, in order:

1. Turn on chunked prefill if you have long prompts and a tail problem. Start with the default token budget.
2. Tune max_num_batched_tokens (your chunk size dial). If decodes still stall, lower it. If prefills feel too slow and decodes are fine, raise it. Move it in steps and measure against your trace, not against a single request.
3. Set max_num_seqs to match the memory you actually have, so you preempt less often.
4. Pick a scheduling policy that fits your traffic. Leave FCFS on only if your load is truly uniform. Otherwise move to priority or SLA-aware.

A rough sense of when chunked prefill starts to matter: if your prompts are short (a few hundred tokens) and concurrency is low, it mostly adds overhead and you can skip it. As your prompts climb into the thousands of tokens, or concurrency rises to where prefills and decodes keep colliding, chunked prefill stops being optional and becomes the main thing keeping your tail flat. Do not chase magic numbers from a blog post, including this one. Measure your own traffic and let the numbers decide.

What causes p99 latency spikes in vLLM? Long prefills blocking decodes that are already running. When a big prompt starts processing, everyone else’s token generation waits for that iteration to finish. It is a scheduling problem, not a raw compute limit, and it shows up under the bursty, mixed traffic that synthetic benchmarks usually miss.

Is chunked prefill the same as continuous batching? No. Continuous batching schedules per iteration, so finished sequences leave and new ones join after each step. Chunked prefill goes further by splitting a long prefill into smaller pieces so it can run next to decodes instead of blocking them. You use both together.

Does PagedAttention reduce latency or just memory usage? Directly, it manages KV cache memory and cuts fragmentation. It does not schedule anything, so it does not fix latency on its own. It helps indirectly, because once memory is no longer the hard limit on batch size, the scheduler has more room to interleave prefill and decode well.

How do I choose a chunk size? Treat the per-iteration token budget (max_num_batched_tokens) as your dial. Too small keeps decodes snappy but slows prefill and adds overhead. Too large brings back the blocking you were trying to fix. Start with the default, then adjust in steps while testing against a realistic traffic trace.

Why do my benchmarks look fine but production does not? Your benchmark probably used evenly spaced, same-size requests. Production traffic is bursty, mixes short and long prompts, and shares the GPU across users. Re-run your benchmark against a real trace like the Azure LLM Inference Trace or BurstGPT and watch what happens to p99.

When should I not bother with chunked prefill? When your prompts are short and concurrency is low. In that case it mostly adds overhead. It earns its keep as prompts grow into the thousands of tokens and concurrency rises to where prefills and decodes keep colliding.

Tail latency is not a hardware problem you can buy your way out of. It is a scheduling problem. A long prefill blocks the decodes already in flight, preemption fires at the worst moment, and a benchmark built on uniform load hides all of it. Chunked prefill is the main lever for the first problem, a policy that fits your traffic handles the second, and testing against bursty traces is how you stop being surprised in production. Start by working out whether you are prefill-bound, decode-bound, or scheduling-bound, then change one knob at a time and measure the tail, not the median.

None of this needs fancy infrastructure. Chunked prefill, paged memory, and preemption are already built into vLLM and the other major engines, so most of the work is understanding what they do and tuning them to your traffic, not building anything from scratch. The teams that get predictable p99s are usually not the ones with the biggest GPUs. They are the ones who know which bound they are hitting, who test against traffic that looks like production instead of a clean loop, and who are honest about the tradeoffs when they share their numbers. And if a single node is no longer enough, the same ideas keep going: disaggregating prefill and decode onto separate pools is the next step up, and it builds on exactly the scheduling intuition covered here.

If you take one thing away, let it be this. The median is comfortable, but the tail is where your users actually live. Measure the tail, tune for it, and the rest of the stack gets much easier to reason about.

• Continuous Batching Mechanics: The Scheduler Behind vLLM, TGI, and SGLang
• Continuous Batching vs. Static Batching in LLM Inference
• How KV Caching Slashes LLM Inference Costs at Scale
• LLM Inference Optimization: Quantization to Speculative Decoding, Part 1