Beyond Prediction: Tail-Aware Scheduling for LLM Inference

×

TL;DR

Tail latency, not mean latency — and no length prediction needed

LLM serving exhibits extreme output-length variability. Existing schedulers approximate SJF/SRPT using predicted decode lengths — but these prediction-driven policies are fragile and, fundamentally, mean-optimal: they offer no guarantees on tail behavior. UniBoost replaces prediction with soft, continuous priority boosting and KV-cache-aware preemption. A single parameter γ interpolates between FCFS and SJF — and a mid setting beats both.

35–50%

lower P99 TTLT than SRPT with perfect length prediction

34–97%

lower P95 TTFT across reasoning- and chat-heavy workloads

2.9–8.7×

wider SLO threshold at 99% attainment — with zero length prediction

Key Insight

No single LLM scheduling policy dominates. The optimal strategy depends on the job size distribution and arrival burstiness . Optimizing for tail latency requires a scheduler that adaptively interpolates between two extremes: HoL-blocking mitigation (preempt long jobs) and starvation protection (guard long jobs).

The Problem

You can't schedule what you can't predict

Size-based policies (SJF/SRPT) are mean-optimal only when job sizes are known. In LLM serving,<br>they almost never are — and the mean is the wrong target anyway.

Decode length is fundamentally unpredictable. Run the same prompt through the same model 20 times<br>and the output length still swings by more than 2× (coefficient of variation up to 0.47 ),<br>purely from sampling stochasticity and numerical nondeterminism. Two requests with identical prefills can<br>diverge by orders of magnitude in completion time, and the size distribution shifts across workloads<br>and over time — especially for reasoning models that think, reflect, and call tools.

Reasoning workloads are heavy-tailed. Datasets like BigCodeBench and S1K exhibit extreme output<br>length variance — a single long-thinking request can be 10–100× longer than the median. Under such<br>distributions, SRPT causes priority inversion: a short request that arrives<br>slightly after a long one gets starved, inflating TTFT and P99 TTLT simultaneously.

No single policy dominates. FCFS is fair but slow; SRPT minimizes mean latency but has no<br>tail guarantees. Prediction-based hybrids (TRAIL, LTR) are fragile under distribution shift.<br>The right answer depends on the workload — and workloads change.

Figure 1 · Output token length distributions. WildChat, BigCodeBench, and S1K at different load points. Reasoning workloads exhibit extreme heavy-tailed behavior — a single policy cannot handle all regimes.

Figure 2a · HoL blocking under FCFS. A long request $A$ arrives at $t=0$, delaying short requests $B,C,D,E$. FCFS performs poorly; SRPT/LAS preempt $A$ to serve short jobs first.

Figure 2b · Starvation under SRPT. A burst of short jobs $B,C,D$ causes SRPT/LAS to repeatedly preempt long request $A$, inflating tail latency. FCFS maintains better fairness here.

Key Insight<br>The optimal scheduler for tail latency must adaptively interpolate between FCFS (optimal for<br>light-tailed workloads) and SRPT (optimal for heavy-tailed workloads) — without relying on explicit<br>length prediction. A single continuous knob &gamma; achieves this, and its sweet spot beats both<br>extremes on P99 latency.

Comparison with Prior Work

Table 1 · Comparison of LLM Scheduling Approaches

Policy / Work<br>Heavy-tailed<br>Light-tailed<br>No Size Pred.<br>Preemption Overhead<br>Tail-Aware by Design<br>TTLT Evaluated

Shortest Prefix First (vLLM)<br>△△<br>✗✗<br>✗✗

Rank-prediction SJF (LTR)<br>✓△<br>✗△<br>✗✗

Prediction-based SRPT (TRAIL)<br>✓△<br>✗△<br>✗✓

FCFS (vLLM default)<br>✗✓<br>✓✓<br>✗△

Skip-Join MLFQ / LAS<br>△△<br>✓△<br>✓△

UniBoost (Ours)<br>✓✓<br>✓✓<br>✓✓

✓ = supported; △ = partial; ✗ = not supported. UniBoost is the only scheduler that handles both heavy- and light-tailed workloads, requires no size prediction, accounts for preemption overhead, and is explicitly designed and evaluated for tail latency.

Method

A four-phase design for tail-aware LLM scheduling

Soft, continuous priority shaping — no length prediction required. One parameter &gamma; controls<br>the entire FCFS–SJF spectrum.

UniBoost is inspired by tail-optimal scheduling theory. Rather than hard size-based ranking (SJF/SRPT), it uses soft, continuous priority shaping: each request receives a smoothly varying score computed from lightweight signals, and requests are served in order of increasing arrival time minus boost. This boosting approach can provably suppress extreme delays under partial observability.

Applying boosting to LLM serving faces three practical challenges: (1) LLM inference is stateful and memory-coupled — KV caches make preemption expensive; (2) the optimal boost parameter depends on the workload distribution, which shifts across tasks; (3) prefill and decode phases have fundamentally different scheduling dynamics. UniBoost addresses all three through a staged design.

The Boost Priority Function

The &gamma;-Boost...