Interactive LLM services must meet latency service-level objectives (SLOs) for the time to first token (TTFT) and the time between tokens (TBT), as streaming and soft real-time applications require predictable token delivery. We identify decode jitters in both aggregated and disaggregated serving. A jitter delays every request in the batch, and long responses span hundreds of steps, so even rare overruns cause many SLO violations. In aggregated serving, SLO-aware schedulers set each step's prefill budget until its predicted latency just meets the TBT target, leaving no room for mispredictions or host stalls. Disaggregation meets average TBT targets at a cost in capacity, yet the steps that admit new requests still run late. We present \sysname, a scheduler that calibrates how much prefill work each decode step carries using the measured tail of its own iteration latency. The SLO determines how rare a late step must be, and \sysname leaves enough headroom in each iteration to prevent overruns and meet the target decode latency. This headroom slows prefill, so \sysname serves the shortest waiting prompt first. When TTFT deadlines grow with prompt length, the long prompts it delays have the most time to spare. Under disaggregation, it spaces admissions so that no request waits on more slow admission steps than its P99 target allows. On three attention families and varying workloads, \sysname sustains 2.4--2.9× the SLO goodput of the strongest baseline on Qwen3-8B and DeepSeek-V4-Flash, and at least 4.4× on DeepSeek-V2-Lite. With prefill and decode disaggregated on eight GPUs, \sysname meets the SLO for more than twice as many requests as state-of-the-art baselines.
Figures & tables
Fig. 1: Decode jitters persist despite chunked prefill and disaggregation (DeepSeek-V4-Flash, replayed Mooncake trace). Each step of a staircase is one iteration, which gives every decoding request one token. (a) A Sarathi iteration that carries a prefill chunk runs past SD , so every decoding request receives a late token at once. (b) With prefill and decode disaggregated, the iteration that admits a newly prefilled request also runs past SD . Shaded: time past SD .
System
Token budget
Prompt order
vLLM
fixed (8192 tokens)
FCFS
Sarathi
fixed, profiled for the SLO
FCFS
SPF
fixed
shortest prompt first
Medha
up to SD , no margin
least slack
Niyama
up to slack, p99 margin †
deadline + work left
VelServe
up to SD minus measured tail
shortest left ‡
TABLE I: The two decisions of each scheduler we study. Adaptive budgets add prefill until the predicted iteration latency reaches the limit shown.
Fig. 2: With compressed attention, a decode costs about one prefill token (a) and context barely matters (b).
Fig. 3: Decode jitters stay out of each request’s P90 TBT (a) but reach its P99 (b), so far fewer requests meet SD .
System
Qwen3-8B
DS-V2-Lite
DS-V4-Flash
Niyama
1.71 / 2.15
1.00 / 1.11
8.37 / 12.40
Medha
0.00 / 1.36
0.00 / 1.60
0.00 / 3.97
VelServe
0.00 / 0.00
0.00 / 0.01
0.00 / 0.02
TABLE II: Iterations (%) planned / measured to run past SD (Mooncake-shaped lengths). Medha plans none, yet still jitters.
Fig. 4: Overview of VelServe . The planner ①–② runs every iteration, and the calibrator ③–⑤ runs in the background.
Fig. 5: How a short request S and a host stall fare under FCFS, SLO-aware scheduling and VelServe (schematic, one box per iteration).
Fig. 6: Margin rules on DeepSeek-V4-Flash. (a) Each rule overruns less often than its target (triangles: no overrun observed). (b) A p99 margin meets the P99 SLO, but the worst-gap bound needs VelServe ’s deeper margin.
Fig. 7: SLO attainment vs. load (TTFT deadline and per-request P99 TBT ≤150 ms). (a–c) Mixed; (d) replayed Mooncake trace, four slices pooled. Error bars: 95% Wilson interval over pooled requests.
Fig. 8: SLO goodput when each part of the SLO is tightened or relaxed, re-scoring the same runs (configured for 150 ms and a TTFT SLO scale of 3). Rows: (1) per-request P99 TBT bound; (2) worst-gap bound; (3) end-to-end deadline, with the TPOT SLO swept; (4) TTFT only, with the TTFT SLO scale κ swept. VelServe leads under both TBT bounds down to 150 ms, and rows 3–4 show that its margin costs no end-to-end or first-token goodput. Labels give VelServe ’s SLO goodput over the best baseline’s, and stars mark runs configured for 300 ms. In (d), the trace is dotted, and Niyama ran from 0.4 req/s.
Fig. 9: Ablation on Qwen3-8B (P99 TBT SLO, two seeds, error bars: seed range). Neither the order (A1) nor the budget (A2) alone exceeds 66%, and only both together (A3) stay above 90%.
Fig. 10: Only VelServe meets the full SLO (b) in every class.
Rate (req/s)
Scheduler
Margin
0.6
1.0
1.4
VelServe
online ( ≈ 48 ms)
99.3
99.6
96.4
frozen offline (9.4 ms)
66.4
47.6
35.6
frozen, other workload (29.3 ms)
99.3
83.1
91.8
Medha
none
100.0
57.6
25.7
29.3 ms, other workload
100.0
87.4
51.7
TABLE III: SLO attainment (%) when the margin is measured online, frozen, or moved into Medha (Qwen3-8B, Mixed, P99 TBT SLO, seeds 0–1). Frozen margins keep VelServe ’s budget rule and order. “Other workload”: the value measured with Mooncake-shaped lengths.
Fig. 11: (a) The step just above SD is the join, which VelServe avoids for more requests. (b) The decode gate alone explains this.
vLLM 0.30.0 (V1), CUDA 13.0, PyTorch 2.13; CUDA graphs up to 2304-token iterations, asynchronous scheduling, ≤ 256 running requests, 90% of memory for weights and KV
Models (attention; layers; weights; KV per token)
GQA
Qwen3-8B; 36; real weights, YaRN-extended to 128k; ≈ 144 KB
MLA
DeepSeek-V2-Lite; 27; real weights; ≈ 30 KB
CSA/HCA
DeepSeek-V4-Flash; 43; real weights of routed experts 0–63 of 256 per layer, router sliced to them (the per-GPU expert footprint of a 4-way expert-parallel shard); ≈ 10 KB
Workloads
Mixed : Poisson arrivals; prompts 128–2k tokens (75%), 8k–32k (20%) and 64k–120k (5%); outputs 64–512 tokens. Mooncake-shaped : Poisson arrivals; prompt and output lengths drawn from the Mooncake conversation trace [ 28 ] . Mooncake trace (CSA only): 150 consecutive requests of the same trace, replayed and time-scaled. Multi-turn : sessions of 3–6 turns over a 16k–96k-token document, plus short background requests. Agent trace (CSA): Mooncake tool-agent requests with the prefixes they share. Prefix caching is on for the last two only
Appendix
TABLE C.1: Setup of the colocated experiments. Appendix K describes the disaggregated deployment.
Model
TBT SLO
vLLM
Sarathi
SPF
Niyama
Medha
VelServe
× best
Qwen3-8B
P99 TBT
< 0.1
< 0.1
0.10
< 0.1
0.65
1.54
2.4 ×
(GQA)
Worst gap
< 0.1
< 0.1
0.10
< 0.1
0.18
1.50
8.4 ×
DeepSeek-V2-Lite
P99 TBT
< 0.125
0.14
0.19
< 0.125
0.67
≥ 3.00
≥ 4.4 ×
(MLA)
Worst gap
< 0.125
0.14
0.19
< 0.125
0.22
0.48
2.2 ×
DeepSeek-V4-Flash
P99 TBT
< 0.1
< 0.1
< 0.1
0.13
0.44
1.29
2.9 ×
(CSA/HCA)
Worst gap
< 0.1
< 0.1
< 0.1
< 0.1
0.44
1.29
2.9 ×
Appendix
TABLE D.1: SLO goodput in req/s at ≥ 90% attainment under the P99 TBT SLO and the worst-gap variant, both 150 ms (Mixed; last rows: Mooncake trace); same runs as Figure 7 . “ <r ”: below 90% already at the lowest rate r ; “ ≥r ”: never below 90%; ratios against such bounds are bounds.
Fig. D.1: SLO goodput as the per-request P99 TBT bound tightens, for every model and workload (TTFT SLO scale 3). Top: Mixed (labelled Chat+Doc mix). Bottom: Mooncake-shaped lengths, with the replayed trace dotted on DeepSeek-V4-Flash. Shading: VelServe ahead of the best baseline, with the ratio. Stars: configured for 300 ms.
Fig. D.2: Sensitivity to the TTFT target under the worst-gap bound. The TTFT SLO scale is 2 (top two rows) or 5 (bottom two rows). Layout as in Figure D.1 .
Model
System
1 s
2 s
5 s
10 s
30 s
Qwen3-8B
vLLM
< 0.1
< 0.1
< 0.1
0.10
0.10
Sarathi
< 0.1
0.10
0.10
0.16
0.80
SPF
0.10
0.15
0.48
1.02
1.03
Niyama
< 0.1
< 0.1
< 0.1
< 0.1
< 0.1
Medha
0.18
0.18
0.18
0.18
0.18
VelServe
1.08
1.08
1.08
1.08
1.08
Appendix
TABLE D.2: SLO goodput in req/s at ≥ 90% attainment (Mixed, worst gap ≤150 ms, TTFT SLO scale 3) when the minimum TTFT deadline SF0 is raised from 1 s (the SLO) to 30 s. Same runs and notation as Table D.1 .
Fig. D.3: Head-of-line blocking under FCFS (§ II-E ; DeepSeek-V4-Flash, Mixed). (a) Prefill throughput by prompt class, and the TTFT of each short request against its 1-s deadline. (b) Mean TTFT of short requests, split into their own prefill, waiting behind other prefills, and other delays.
Fig. D.4: Outcome of every request under the worst-gap SLO (150 ms) at three loads per workload. Panel titles give the load relative to VelServe ’s SLO goodput (“cap.”). Numbers: % of requests that met the SLO. Hatched: seeds stopped early below this load, counted as misses.
Fig. D.5: Standard serving metrics on Mixed, with no SLO: percentiles of first-token latency (TTFT) and inter-token latency (ITL) on a log scale, and output tokens per second, against arrival rate. A line ends where the system was stopped early.
Workload
Model
vLLM
Sarathi
SPF
Niyama
Medha
VelServe
× best
Mixed
Qwen3-8B
0.10
< 0.1
0.10
0.83
1.06
≥ 2.00
≥ 1.8 ×
V2-Lite
0.50
0.14
0.19
1.54
1.15
≥ 3.00
≥ 1.9 ×
V4-Flash
< 0.1
< 0.1
< 0.1
0.40
0.46
1.29
2.8 ×
Mooncake-sh.
Qwen3-8B
0.44
0.41
0.43
0.64
0.71
1.12
1.6 ×
V2-Lite
≥ 0.75
0.41
0.41
2.05
1.33
3.09
1.5 ×
V4-Flash
0.14
0.14
0.14
0.50
0.17
0.57
1.1 ×
Appendix
TABLE E.1: SLO goodput in req/s when the runs of Figures 7 and 8 are scored by an end-to-end deadline: first token within the TTFT deadline, last token within it plus (n−1)× a TPOT SLO of 150 ms. Same configurations and notation as Table D.1 .
Workload
Model
req/s
vLLM
Sarathi
SPF
Niyama
Medha
VelServe
Mixed
Qwen3-8B
0.4
3.2 / 21 (85)
3.6 / 22 (76)
3.3 / 22 (80)
3.2 / 20 (99)
3.3 / 21 (100)
3.3 / 21 (100)
Mixed
Qwen3-8B
0.8
12.3 / 35 (55)
20.4 / 39 (27)
11.3 / 42 (51)
11.3 / 35 (97)
13.5 / 39 (96)
13.0 / 38 (98)
Mixed
V2-Lite
0.5
1.9 / 10 (90)
5.8 / 23 (71)
4.7 / 23 (82)
1.9 / 11 (100)
3.1 / 20 (100)
2.2 / 13 (100)
Mixed
V2-Lite
1
2.5 / 12 (89)
10.6 / 28 (47)
8.4 / 27 (68)
2.9 / 16 (100)
4.8 / 22 (97)
3.7 / 19 (100)
Mixed
V4-Flash
0.2
6.1 / 24 (75)
10.9 / 31 (67)
9.2 / 30 (78)
4.0 / 8 (93)
4.7 / 10 (100)
4.6 / 9 (100)
Mixed
V4-Flash
0.4
4.7 / 15 (80)
12.2 / 35 (62)
8.9 / 35 (73)
6.3 / 31 (90)
8.5 / 35 (100)
7.9 / 36 (95)
Appendix
TABLE E.2: End-to-end request latency, arrival to last token, in seconds: median / P99 over completed requests (mean over seeds), and in parentheses the share of all requests (%) that meet the end-to-end deadline of Table E.1 . Same runs as Figures 7 and 8 ; –: not run at this rate.
Planned
Over
Residual (ms)
Model
System
>SD (%)
SD (%)
median
p99
Qwen3-8B
Niyama
1.71
2.15
+1.1
16
Medha
0.00
1.36
+4.9
20
VelServe
0.00
0.00
+1.0
16
V2-Lite
Niyama
1.00
1.11
+2.4
125
Medha
0.00
1.60
-1.2
25
Appendix
TABLE F.1: Iteration overruns on the same workload (Mooncake-shaped lengths, seed 0, SD=150 ms). Planned: % of iterations whose predicted time exceeds SD . Over: % whose measured time exceeds SD . Residual: measured minus predicted time of iterations that carry a prefill chunk, median and P99.
Fig. G.1: Design space: one decision varied around VelServe , the others held at VelServe ’s choice (Mixed, worst-gap bound at 150 ms, two seeds pooled). (a) Margin of the token budget (§ III-C , DeepSeek-V4-Flash); none and p99 are Medha’s and Niyama’s rules applied inside VelServe . (b) Prompt order (§ III-D , DeepSeek-V4-Flash). (c) Cost estimate (§ III-E ): token counts or the context-aware time model; bold: VelServe ’s choice. Bars: attainment; ticks: attainment if every TBT were 5 ms longer.
Rate (req/s)
0.6
0.8
1.0
1.2
1.4
1.6
Qwen3-8B
VelServe
99.3
98.4
99.6
97.5
96.4
87.3
margin frozen offline (9.4 ms)
66.4
–
47.6
–
35.6
–
margin frozen, from Mooncake-shaped lengths (29.3 ms)
99.3
–
83.1
–
91.8
–
Medha
100.0
–
57.6
–
25.7
–
+ 29.3 ms margin (from Mooncake-shaped lengths)
100.0
–
87.4
–
51.7
–
Appendix
TABLE H.1: SLO attainment (%, P99 TBT SLO, Mixed, seeds 0–1) with VelServe ’s margin frozen, or moved into Medha. Table III shows the Qwen3-8B rows at three rates. “–”: not run.
Rate (req/s)
0.4
0.6
0.8
1.0
1.4
1.8
VelServe
93.7
89.4
79.8
76.1
68.0
60.2
VelServe + promotion
94.5
85.1
79.5
72.8
64.8
57.1
Appendix
TABLE I.1: DeepSeek-V4-Flash with Mooncake-shaped lengths: SLO attainment (%) pooled over three seeds.
TTFT (s)
Slowdown
Timed
TTFT
TBT p99
SLO
Class
System
p50
p99
p50
out (%)
met (%)
(ms)
met (%)
Short ( < 8k)
vLLM
30.6
107
706.6
0.0
19.8
1200
14.3
Niyama
0.3
1.2
7.1
0.0
97.0
454
11.8
VelServe
0.2
0.4
5.3
0.0
99.8
126
99.8
Medium (8–32k)
vLLM
38.2
115
34.3
0.0
17.6
1216
10.5
Niyama
1.8
214
1.7
0.4
90.5
459
8.8
Appendix
TABLE I.2: Per-class latency over one 40-minute window (Qwen3-8B, Mixed, 1.0 req/s, identical arrivals). TTFT percentiles count a request with no first token within the 300-s timeout as > 300 s. Slowdown: TTFT divided by the prompt’s prefill time on an idle engine. TBT p99: over all gaps of the class. SLO met: TTFT deadline and own P99 TBT ≤ 150 ms.
Fig. J.1: Prefix caching. Left three columns: Multi-turn sessions over a long document, mean of two seeds. Right: DeepSeek-V4-Flash replaying the Mooncake agent trace. Top: attainment under the worst-gap bound (150 ms), with 95% Wilson intervals. Bottom: P99 TTFT of follow-up turns (log scale); right: share of prefix-reusing requests that meet their TTFT deadline.
Baselines
VelServe
Model
SLO
vLLM
Niyama
Medha
SGL-CA
blind
CA
CA-tok.
× best
Qwen3-8B
Strict
0.036
0.036
0.055
0.047
0.060
0.184
0.161
3.3 ×
(GQA)
Relaxed
0.036
0.037
0.084
0.047
0.093
0.184
0.161
2.2 ×
V2-Lite
Strict
0.051
< 0.048
0.105
0.053
0.093
0.276
0.070
2.6 ×
(MLA)
Relaxed
0.052
0.051
0.111
0.053
0.150
0.382
0.070
3.4 ×
V4-Flash
Strict
< 0.03
< 0.03
0.062
0.037
≥ 0.130
0.112
n/a
1.8 ×
Appendix
TABLE J.1: SLO goodput with prefix caching at ≥ 90% attainment (Multi-turn: sessions/s; agent trace, last two rows: req/s), and cache-aware VelServe ’s ratio over the strongest baseline (vLLM, Niyama, Medha, SGLang-CA = SGL-CA). Strict: the worst-gap bound of 150 ms used in the text; Relaxed: a looser TBT bound. n/a: not run.
Attainment (%)
TTFT (s)
TTLT (s)
TPOT (ms)
Gaps
System
SLO
TBT
TTFT
P50
P90
P99
P50
P90
P99
P50
P90
P99
>SD (%)
20 minutes, 1,200 requests
vLLM
15.6
19.6
74.6
2.38
7.35
17.57
14.6
25.5
44.4
33.7
40.7
60.9
3.25
Niyama
14.8
18.6
78.9
2.30
5.62
18.57
14.6
25.5
43.7
34.2
41.5
64.4
3.36
VelServe
35.1
45.3
75.1
3.25
7.10
19.83
14.2
24.2
42.4
30.4
36.1
40.5
1.57
vs. vLLM
+125%
+131%
+1%
+37%
− 3%
+13%
− 2%
− 5%
− 5%
− 10%
− 11%
− 34%
− 52%
Appendix
TABLE K.1: Disaggregated serving of DeepSeek-V4-Flash (§ IV-E ). Attainment: share of requests that meet the SLO, the P99 TBT target ( ≤ 150 ms) and the TTFT deadline. Latency percentiles are over requests; TPOT is a request’s mean time per output token after the first. Gaps: share of all token gaps longer than SD . Italic rows give the change relative to the row named, 100(x/xref−1) : higher is better for attainment, lower for latency and gaps. The ablation ran in a separate window, so compare its rows only with each other.
Parameter
Value here
Set by
Epoch period T
4 s
median of ntd/max(k(n),1) (2.15 s), rounded up on a 0.5⋅2j s grid
Cap on T
4 s
hand; did not bind
Gate off
join ≤SD−2 ms
join cost measured online (181–183 ms)
Opening window
0.15 s
fixed
Urgent sub-epoch
0.5 s
fixed
Urgent slack
0.25 s (rescue: 0.05 s)
fixed
Appendix
TABLE K.2: Parameters of the disaggregated extension and how each is set.
req/s
System
150
200
300
Misses
worst TBT p99 (ms)
0.2
Sarathi-Serve, official
0.96
0.96
0.96
1/0/0
40
Sarathi, ours
1.00
1.00
1.00
0/0/0
31
Niyama, official (tuned)
0.69
0.88
1.00
0/8/0
273
Niyama, ours
0.81
0.81
0.85
0/5/0
494
0.6
Sarathi-Serve, official
0.56
0.56
0.56
27/0/0
144
Sarathi, ours
0.77
0.77
0.77
14/0/0
85
Appendix
TABLE L.1: Official artifacts versus our versions: Qwen3-8B, Mixed, seed 0. Attainment under the worst-gap bound at 150/200/300 ms; misses at 150 ms split into TTFT only, TBT only and both.
LLM serving exhibits extreme length variability, making size-based scheduling difficult in practice. Recent LLM schedulers approximate SJF/SRPT using predicted decode lengths or ranks and primarily report mean-centric metrics such as TTFT and TBT. We show that these prediction-driven policies can be fragile under distribution shifts, bursty arrivals, and GPU memory pressure, while offering limited control over the tail latency (P90-P99) that dominates user experience, even with perfect decode-length knowledge. We introduce a distribution-aware, prediction-free scheduling framework that replaces explicit length prediction with soft priority boosting driven by lightweight statistical signals. Our design co-optimizes scheduling and cache-aware preemption to account for memory-coupled decode dynamics across workload mixes. Evaluated on production and open-source traces, our method reduces P99 TTLT by up to 35-50% relative to SRPT with perfect length knowledge and reduces TTFT by 34-47% across workloads, including reasoning-heavy and chat-heavy tasks. These results demonstrate a robust alternative for optimizing tail latency in online LLM serving.
Yueying Li, Yuanfan Chen, Jiayang Chen +6
Cornell University, Computer Science Department, NY, USA · Microsoft Azure System Research, WA, USA · Cornell University, Electrical and Computer Engineering Department, NY, USA +2
Disaggregated LLM serving runs prefill and decode on separate GPU pools to keep the two phases from interfering. In practice, this creates a new asymmetry: under bursty, heavy-tailed workloads prefill nodes saturate while decode nodes have compute underutilized, and on a production-style A100 cluster with 2 prefill and 2 decode nodes (2P2D), we find that prefill execution accounts for only 2-23% of P95 Time-to-First-Token (TTFT). Queuing and inter-node GPU-GPU KV-cache transfer account for the rest. We present a proactive prefill-deflecting scheduler that lets decode nodes serve prefill phase of requests as chunked-prefill steps interleaved with their in-flight decode batches. For each queued request, we estimate the TTFT it would see on the prefill node, and on every decode node, search for the largest chunk schedule that keeps in-flight decodes within their Time-Between-Tokens (TBT) SLO and deflect when the decode path helps tail latency. Because the prefill phase of deflected requests runs in place on the decode node, the inter-node KV transfer is eliminated. Implemented on vLLM and evaluated on production-style traces with DeepSeek-V2-Lite, our approach reduces P95 TTFT by upto 81% and raises SLO attainment by upto 79% over state-of-the-art disaggregated schedulers, at sub-millisecond per-request routing cost.
Continuous batching improves large language model (LLM) serving throughput, but long prompt prefills can delay decode iterations and violate inter-token latency objectives. Chunked prefill mitigates this interference, yet its chunk size is normally fixed: small chunks protect decode latency but repeatedly pay launch overhead, while large chunks improve prefill efficiency but create latency spikes. We introduce SLOWeave, an online scheduling method that selects the largest prefill chunk predicted to finish before the earliest active decode deadline. The decision requires no workload-specific chunk-size tuning and is computed by a logarithmic-time search over a monotone iteration-cost model. We prove that, whenever a decode-only iteration is feasible and the cost predictor is accurate, SLOWeave maximizes immediate prefill progress among decisions that preserve every active request's next-token deadline. We evaluate the method in a reproducible event-driven simulator and an iteration-level GPU runtime across chat, mixed-context, long-context, and bursty workloads. Under a 25ms time-per-output-token objective, SLOWeave improves goodput over the strongest fixed-chunk baseline by 39% on mixed requests and 38% on long-context requests. Under a stricter 10ms objective, the gains rise to 3.3× and 2.4×, respectively. These results isolate adaptive chunk sizing as a useful serving primitive and provide an implementation-ready controller for integration with iteration-level LLM runtimes.
Siyu Song, Qi Bai, Jinbo Hao +3
School of Computer Science and Technology, Beijing Institute of Technology · School of Computer Science and Engineering, Sun Yat-sen University · School of Computer Engineering, Jiangsu Ocean University