VelServe: Taming LLM Decode Jitter with Tail-Calibrated Scheduling

VelServe suppresses decode jitter with tail-calibrated scheduling, greatly boosting LLM serving throughput while holding SLOs.
The article introduces VelServe, a tail-calibrated scheduler for interactive LLM serving. Decode jitter delays all requests in a batch, and long responses spanning hundreds of decode steps turn rare timeouts into many SLO violations, while existing schedulers ignore the latency tail. VelServe measures its own iteration latency tail to set per-step prefill budgets with headroom, pairs this with shortest-prompt-first and admission spacing, and achieves over 2.4× SLO goodput versus the strongest baseline.
Interactive LLM serving has strict SLO requirements for time to first token (TTFT) and time between tokens (TBT), but jitter in the decode phase—even rare timeouts—can drag down large batches of requests. VelServe proposes a tail-calibrated scheduler that dynamically adjusts the prefill workload at each decode step, substantially improving throughput while preserving latency targets.

Decode Jitter: The Overlooked SLO Killer
In streaming output and soft real-time applications, whether tokens can be delivered predictably directly determines user experience. The paper points out that decode jitter exists in both aggregated and disaggregated serving architectures. A single jitter event delays all requests in the batch, and long responses often span hundreds of decode steps—so even if timeout events themselves are rare, they accumulate into a large number of SLO violations.
This observation reveals a blind spot in existing scheduling strategies: they typically optimize for average or predicted latency while ignoring the tail of the latency distribution.
TTFT and TBT: Time To First Token (TTFT) refers to the time from when a request is issued to when the first output token is received, and is mainly affected by the prefill phase; Time Between Tokens (TBT) refers to the time interval between adjacent output tokens, determined by the duration of each step in the decode phase. In streaming applications, TTFT determines how quickly the user sees the beginning of the response, while TBT determines whether the text "flows" smoothly. The two usually have their own SLO targets (e.g., TTFT P99 < 1s, TBT P99 < 100ms), and the scheduler must satisfy both simultaneously.
SLO and goodput: SLO (Service Level Objective) is a service-level target, often expressed in quantile form, such as "99% of requests have TTFT no greater than a certain threshold." goodput (SLO-effective throughput) refers to the number of requests that satisfy the SLO per unit time, as distinct from raw throughput that does not consider latency constraints—it measures the capacity that is "truly usable" and is the core metric for evaluating scheduling strategies for soft real-time LLM serving.
The Dilemma of Aggregated Serving: Prefill Budgets Set Too Tight
In aggregated serving, SLO-aware schedulers set a prefill budget for each decode step until the predicted latency just meets the TBT target. This approach looks precise but in fact leaves no margin for prediction error or host stalls. Once the prediction is inaccurate, the entire batch misses its deadline.
VelServe's approach is "calibration": instead of relying on a single-point prediction, it measures the tail of its own iteration latency and uses that to decide how much prefill work each decode step should carry. The SLO itself determines how rare "late steps" can be, and the scheduler reserves sufficient headroom in each iteration accordingly to prevent timeouts and meet the target decode latency.
Aggregated and disaggregated architectures: In aggregated serving, prefill and decode are handled by the same set of GPU instances, and prefill for new requests competes for compute with the ongoing decode batch; disaggregated architectures split prefill and decode into different instance pools, with prefill results transferred to decode instances via KV Cache, allowing separate scaling but introducing transfer overhead and two-phase coordination problems. Under both architectures, the timing of prefill insertion perturbs the rhythm of decode steps, so jitter problems are pervasive.
Mutual interference between prefill and decode: Each decode step must generate one token for every request in the batch, and its duration is relatively fixed; if prefill work is inserted into a decode step, that step's duration increases significantly. Aggregated schedulers therefore set a prefill budget for each step (i.e., how many prefill tokens to insert). Too large a budget causes that step's TBT to time out, while too small a budget slows prefill progress and worsens TTFT—this is exactly the root cause of "set too tight."
Shortest Prompts First: Leaving Latency to the Requests That Need It Most
Reserving headroom slows prefill, and VelServe's response is to prioritize the shortest waiting prompt first. The paper offers a clever argument: when the TTFT deadline grows with prompt length, the long prompts that get deferred actually have the most time to spare. In other words, short prompts go first, and long prompts can afford to wait without violating their deadlines, so the overall SLO attainment rate improves.
In disaggregated architectures, VelServe instead adjusts the spacing of request admissions to ensure that no request needs to wait through more slow admission steps than its P99 target allows.
Shortest Waiting Prompt First: This strategy borrows the idea of Shortest Job First (SJF) from classical scheduling, but its goal is not to minimize average waiting time—it is to improve SLO attainment. The key is that the TTFT deadline usually grows with prompt length (long prompts are allowed a longer wait for the first token), so prioritizing short prompts and deferring long prompts can reduce overall violations without violating the long prompts' deadlines. The paper further combines this with tail calibration: the scheduler inserts prefill only when the reserved headroom allows, and selects insertion targets in order of prompt length, thereby improving the TTFT distribution while holding the TBT target.
Measured Performance: Significant Improvement in SLO-Effective Throughput
The paper evaluates on three attention families and a variety of workloads. On Qwen3-8B and DeepSeekAd-V4-Flash, VelServe's SLO-effective throughput (goodput) reaches 2.4–2.9× that of the strongest baseline; on DeepSeek-V2-Lite it reaches at least 4.4×. When prefill and decode are disaggregated across eight GPUs, VelServe satisfies SLOs for more than twice as many requests as the current best baseline.
These results show that tail-calibrated scheduling does not trade latency for throughput—it releases capacity that jitter was wasting while holding the SLO. For online LLM serving that pursues predictable token delivery, this approach is worth attention.
Key Takeaways
- Decode jitter delays all requests in the batch, and the cumulative effect is significant for long responses.
- VelServe dynamically calibrates each step's prefill budget using the measured tail of iteration latency.
- The shortest-prompt-first strategy exploits the fact that TTFT deadlines grow with length.
- In disaggregated deployments, admission spacing controls the number of P99 waiting steps.
- Across multiple model families, SLO goodput improves by more than 2.4× over baselines.
One-line Summary
VelServe suppresses decode jitter with tail-calibrated scheduling, substantially improving LLM serving throughput while holding SLOs.
Paragraph Summary
The article introduces VelServe—a tail-calibrated scheduler for interactive LLM serving. The paper points out that jitter in the decode phase delays all requests in the batch, and because long responses span hundreds of decode steps, rare timeouts accumulate into many SLO violations, while existing schedulers optimize only average or predicted latency and ignore the distribution tail. VelServe measures the tail of its own iteration latency to dynamically decide how much prefill work each decode step carries and reserves headroom against timeouts; combined with a shortest-prompt-first strategy and admission spacing control in disaggregated architectures, it achieves more than 2.4× SLO-effective throughput over the strongest baseline across multiple models and workloads, and doubles the number of SLO-satisfying requests in an eight-GPU disaggregated deployment.
Related articles

GLM 5.5 Arrives: Has Claude Cracked the 167-Year-Old Riemann Hypothesis?
Claude and a mathematician claim to have proved the 167-year-old Riemann Hypothesis, Zhipu's GLM 5.5 is imminent, Google's Loop agent surfaces, and Thinking Machines open-sources Inkling 2 Mini.

AI Coding Made Building Cheap, but Not Maintenance
AI coding agents make internal tools cheap to build but not to maintain. This article examines the hidden liabilities of tool sprawl and proposes three governance principles: inventory, ownership, and reuse first.

Microsoft SideWinder Strategic Commander: A Failed Innovation Attempt
A review of Microsoft's SideWinder Strategic Commander gaming peripheral: its design intent, usability flaws, and market positioning, and why peripheral innovation must respect user habits.