LLM·

VelServe — Tail-calibrated decode-step margin — What does it mean?

The news. On November 13, 2026, the arXiv paper "VelServe: Taming Decode Jitters in LLM Inference with Tail-Calibrated Scheduling" (arXiv 2611.18392) presented a scheduler plugin for vLLM 0.30's V1 scheduler, about 1k lines of Python. Under a 150 ms per-request P99 TBT target, with each model on one H100, it reached 2.4–2.9× the SLO goodput of the strongest baseline (Medha) on Qwen3-8B and DeepSeek-V4-Flash, and at least 4.4× on DeepSeek-V2-Lite. Read the paper →

Picture the sushi bar. The belt must finish a lap every 150 ms, and on each lap every seated diner gets exactly one plate. During the same lap the kitchen also preps orders for parties who just sat down. If the kitchen fills the lap with prep until the clock is exactly full, any surprise makes the lap late — and a late lap is a late plate for every diner at once. That is an LLM engine under chunked prefill. Each iteration carries one decode token for every running request plus chunks of waiting prompts up to a token budget, and continuous batching puts all of those requests on the same belt. So the iteration's duration is the time-between-tokens gap for the whole batch. A token budget fixes how much prep goes into a lap; it does not fix how long the lap takes.

The second amplification is time. A diner does not stay for one lap — a request that streams a long answer sits through hundreds. If 1% of steps run late, about 95% of 300-token answers meet at least one late step, and that figure assumes the late steps are independent. The paper reports they are not: a host stall delays a whole batch, and stalls arrive in bursts. This is the tail at scale — rare per component, common per request. It is also why the paper's SLO counts each request's own P99 TBT. A mean time per output token spreads one long pause over hundreds of short gaps, and a P99 pooled over all requests lets many smooth streams hide the few that stalled. In the paper's DeepSeek-V2-Lite runs at 150 ms, 89–98% of requests met the bound at their own P90 under two SLO-aware schedulers, but only 62–74% met it at their P99.

VelServe's answer is to leave part of every lap unplanned. It plans each iteration to the TBT target minus a margin Q, and it measures Q from the tail of its own recent iterations rather than from a model of the typical one. Every 500 iterations a background calibrator refits a linear cost model of iteration time — a fixed cost, a cost per prefill token, a cost per decode, and a term for context length. It then collects the residuals, meaning how much longer each iteration took than the model predicted, and sets Q at the residual that only a small target share of iterations exceed. The planner picks the largest token budget whose predicted time plus Q still fits under the target; in vLLM that cap is applied inside the scheduler's budget loop, which VelServe reorders and caps without touching batching or KV allocation. The margin has to come from VelServe's own iterations because it is a feedback loop: the margin sets the budget, the budget sets what each iteration contains, and those contents set the next round's residuals. On Qwen3-8B under load, the margin grew from its starting 2.3 ms to about 50 ms.

The margin has a price: less prep per lap means prompts finish prefill more slowly, which raises TTFT. VelServe pays it with ordering. It fills each step's budget with the prompts that have the fewest remaining tokens, because under a deadline that grows with prompt length, a long prompt has the most slack to give up. A short arrival preempts a running prefill at a chunk boundary, and the long prompt's KV cache stays on the GPU, so preemption only adds delay. The paper's ablation on Qwen3-8B shows the two pieces need each other: shortest-first order alone, or the margin alone, never served two-thirds of requests at any load, while both together kept attainment above 90% up to the highest load tested.

SchedulerPrefill budget per stepPrompt orderIterations measured past 150 ms (Qwen3-8B / DS-V2-Lite / DS-V4-Flash)
vLLMfixed, 8,192 tokens, Table Ifirst come, first servednot in Table II
Sarathi-Servefixed, profiled for the SLO, Table Ifirst come, first servednot in Table II
Medhafilled to the target, no margin, Table Ileast slack1.36% / 1.60% / 3.97%, Table II
Niyamafilled to the request's slack, plus a p99 margin added in this paper's implementation, Table Ideadline and work left2.15% / 1.11% / 12.40%, Table II
VelServefilled to the target minus a measured tail margin, Table Ishortest remaining prompt first0.00% / 0.01% / 0.02%, Table II

Table II draws prompt lengths from Mooncake, a public LLM serving trace. Medha plans no late iterations and still runs 1.4–4% of them late, because no margin absorbs its prediction errors. Niyama's are partly planned: its per-token deadlines bound a stream's average token rate, so a stream that ran ahead banks slack and the scheduler spends it on steps longer than 150 ms — some lasting a second.

Throughput: 10 req/s
1
2
3
4
5
6
7
8
9
10
Goodput: 3 req/s7 violated SLO
1
2
3
4×
5×
6×
7×
8×
9×
10×
Same system, same second — throughput looks healthy, goodput tells the truth

Those overruns are what the headline numbers measure. SLO goodput rose to 2.4–2.9× the best baseline on Qwen3-8B and DeepSeek-V4-Flash, and to at least 4.4× on DeepSeek-V2-Lite, where VelServe stayed above 90% attainment up to the highest rate the authors ran. The goodput framing is the point: a scheduler can push more tokens per second and still lose, because a request that misses its target does not count.

Under prefill/decode disaggregation the late step changes shape. Prompt chunks leave the decode GPUs, but the step that admits newly prefilled requests — a join — took 170–185 ms in the paper's eight-GPU DeepSeek-V4-Flash setup, so every join was itself a late step. Under plain vLLM there, every request met a 150 ms target on its mean time per output token (TPOT) while most requests missed the P99 TBT target. No budget can shorten a join, so VelServe limits how often each stream meets one: it holds arrived requests until a wall-clock epoch shared by all GPU ranks and admits them together, so one join serves many requests and the ranks, which advance in lockstep, stall once instead of separately. Joins kept every system below 90% attainment at that load; VelServe met the SLO for 35% of requests against 15–16% for vLLM and Niyama.

Here is the arithmetic that sets the margin, using the paper's constants and an illustrative mean answer length (ō) of 300 tokens. The target is a 150 ms P99 TBT; the calibration target is α = 0.99; half of the miss budget goes to TBT (β = 0.5); and in colocated runs a request may have k = 0 late gaps. Without a margin, a 1% overrun rate per step means 1 − 0.99300 ≈ 95% of answers meet at least one late step. VelServe instead targets an overrun rate of η = β(1 − α)(k + 1) / ō = 0.5 × 0.01 × 1 / 300 ≈ 0.0000167, about one step in 60,000. A 300-token answer then expects 300 × η = 0.005 late gaps, and by Markov's inequality — which needs no independence between steps — at most 0.5% of answers see one, provided the iterations each request lives through overrun at no more than that rate, within the reference load the calibration assumes. The price of that guarantee is the margin itself: on Qwen3-8B, about 50 ms of each 150 ms step is left unplanned.

Two limits from the paper are worth keeping in mind. The calibrator follows shifts in the stall distribution with a lag, and under sustained load some of the longest prompts still time out, which is the usual cost of shortest-first order. The join gate only helps when the TBT target is shorter than a join, and it was tested on one prefill/decode split, on one node and one engine. The idea outlasts this scheduler: when one shared step is a deadline for many consumers at once, plan it against the measured tail of its own latency, not against the predicted typical case.

Goes deeper in: LLM Serving → Serving Metrics & SLOs → Percentiles & Tail Latency

Related explainers

Frequently Asked Questions

Check what you knowMap your AI & GPU knowledge across every track — free, role-based