Technical Summary: Beyond Prediction: Tail-Aware Scheduling for LLM Inference

1. Problem Statement

Large Language Model (LLM) serving faces a critical challenge in managing extreme variability in request lengths, particularly with the rise of reasoning-augmented models that exhibit multi-step generation, self-reflection, and adaptive termination. This variability renders size-based scheduling policies (like Shortest Job First - SJF, or Shortest Remaining Processing Time - SRPT) fragile.

Current state-of-the-art schedulers rely on predicting output lengths or remaining tokens to approximate SJF/SRPT. However, the paper identifies three fundamental issues with this approach:

1. Prediction Fragility: Output length prediction is inherently difficult due to high variance in token generation (stochasticity and non-determinism), making policies brittle under distribution shifts and bursty arrivals.
2. Metric Mismatch: Policies optimized for mean latency (e.g., mean TTFT/TBT) often exhibit poor tail latency behavior (P90–P99). In LLM serving, user experience is governed by tail latencies (Time-To-Last-Token, TTLT), which are often the binding constraint for Service Level Objectives (SLOs).
3. Memory-Coupled Dynamics: Unlike classical queues, LLM inference is stateful. Requests accumulate large Key-Value (KV) caches during decoding. Naïve preemption to prioritize short jobs can lead to expensive cache eviction, recomputation, and "thrashing," potentially increasing tail latency despite reducing queueing delay.

The core question posed is whether schedulers need explicit job length predictions to optimize tail latency. The authors argue they do not, proposing instead a distribution-aware, prediction-free approach.

2. Methodology: UNIBOOST

The paper introduces UNIBOOST, a distribution-aware, prediction-free scheduling framework that replaces explicit length prediction with "soft" priority boosting driven by lightweight statistical signals. The design is a co-optimization of scheduling and cache-aware preemption, structured in four phases:

Phase 1: Strawman (DISTBOOST)

The initial approach treats prefill and decode phases as disjoint problems. It uses a $\gamma$-Boost priority function (inspired by queueing theory) for prefill requests but prioritizes the decode queue. While this improves tail metrics for decoding, it suffers from Head-of-Line (HoL) blocking where prefill requests are starved by long-running decode jobs.

Phase 2: Unified Prioritization (UNIBOOST-BASE)

To address HoL blocking, the authors unify prefill and decode queues into a single priority space.

• Priority Score: Requests are scored based on $\phi_i(t) = a_i - b_\gamma(\tilde{w}_i(t))$, where $a_i$ is arrival time, and $\tilde{w}_i(t)$ is the effective work (max of attained work and prefill length).
• Boost Function: $b_\gamma(w) = \frac{1}{\gamma} \log(\frac{1}{1 - e^{-\gamma w}})$. This function provides a "soft" priority boost to requests with less attained service, avoiding the harsh preemption of classical SRPT.
• Mechanism: The scheduler selects the request with the minimum score, allowing preemption across phases but controlled by a hysteresis parameter to prevent oscillation.

Phase 3: Stability via MEMGUARD (KV-Aware Hysteresis)

To mitigate the high cost of KV-cache eviction and recomputation, the authors introduce MEMGUARD.

• Quantized Priorities: Instead of updating priorities continuously, the system discretizes the attained work metric ($\hat{w}_i$) using geometric quantization (e.g., thresholds at $k, 2k, 4k...$).
• Minimum Run: Once a request is dispatched, it cannot be evicted until its attained work crosses the next quantization threshold. This amortizes KV movement costs and limits the number of preemption opportunities to a logarithmic bound relative to the job length.

Phase 4: Adaptive Parameter Estimation ($\gamma$-Ada)

The boost parameter $\gamma$ significantly impacts tail behavior. A static $\gamma$ is sub-optimal under varying loads.

• Online Estimation: The system estimates an effective tail slope ($\gamma_{eff}$) by fitting a log-linear slope to the upper tail of the observed response time distribution (between P95 and P99).
• Adaptation: The scheduler dynamically adjusts $\gamma$ to interpolate between FCFS (protecting the tail) and LAS (optimizing mean), adapting to workload shifts without explicit prediction.

3. Key Contributions

1. Prediction-Free Tail Optimization: Demonstrates that explicit job length prediction is not required to optimize tail latency. Instead, lightweight statistical signals and soft boosting suffice.
2. Co-Design of Scheduling and Eviction: Introduces a framework that jointly optimizes scheduling decisions with KV-cache management. By coupling boost-based scheduling with eviction-aware execution control (MEMGUARD), the system avoids the performance degradation caused by cache thrashing.
3. Robustness to Distribution Shifts: The proposed method adapts to varying workloads (heavy-tailed vs. light-tailed, reasoning vs. chat) without retraining or complex prediction models.
4. Theoretical Grounding: Adapts the $\gamma$-Boost policy from queueing theory to the specific constraints of LLM inference (statefulness, memory coupling).

4. Experimental Results

Evaluated on production and open-source traces (Azure, ShareGPT, S1K) using models like Llama-3-8B, CodeLlama-34B, and Qwen-72B on NVIDIA A100 GPUs:

• Tail Latency Reduction: UNIBOOST achieves a P99 TTLT up to 35–50% lower than SRPT with perfect length prediction (TRAIL+). It also reduces P99 TTFT by 34–47% across various workloads.
• Throughput: The method improves throughput by 1.01–1.12$\times$ under bursty loads compared to baselines.
• SLO Attainment: UNIBOOST allows systems to tolerate 2.9–8.7$\times$ more stringent SLOs for TTFT while maintaining 99% attainment compared to SJF-based approaches.
• Ablation Studies:
  • Removing the unified priority (Phase 2) leads to prefill starvation.
  • Removing MEMGUARD (Phase 3) causes significant tail latency spikes due to KV thrashing.
  • Removing adaptive $\gamma$ (Phase 4) reduces robustness under load shifts.
• Comparison: The method outperforms state-of-the-art baselines including vLLM's Sarathi (chunked prefill), LTR (learning-to-rank SJF), and TRAIL (prediction-based SRPT), particularly in reasoning-heavy workloads where prediction is most unreliable.

5. Significance and Claims

The paper claims that UNIBOOST provides a robust alternative to prediction-heavy scheduling policies for online LLM serving. Its significance lies in:

• Decoupling from Prediction: It removes the dependency on accurate length prediction, which is a major bottleneck in reasoning-heavy and variable-length workloads.
• Holistic Optimization: It addresses the "mean vs. tail" trade-off and the "scheduling vs. memory" trade-off simultaneously, offering a solution that is effective even when prediction quality degrades.
• Practicality: The design is simple to integrate into existing continuous-batching stacks (like vLLM and SGLang) and relies on lightweight runtime statistics rather than complex ML models.

The authors conclude that distribution-aware, eviction-conscious scheduling is essential for the next generation of LLM serving, especially as models become more capable of variable-length reasoning.