Beyond Prediction: Tail-Aware Scheduling for LLM Inference

LLM serving exhibits extreme length variability, making size-based scheduling difficult in practice. Recent LLM schedulers approximate SJF/SRPT using predicted decode lengths or rank and primarily report mean-centric metrics (e.g., TTFT/TBT). We show these prediction-driven policies can be fragile under distribution shifts, bursty arrivals, and GPU memory pressure, and still offer limited control over 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, $\gamma$-parameterized priority boosting driven by lightweight statistical signals. Our design co-optimizes scheduling with cache-aware preemption to account for memory-coupled decode dynamics that vary across workload mixes. Evaluated on Azure production traces, our method achieves a P99 TTLT up to 35--50\% lower than SRPT with perfect length prediction and a TTFT 34--47\% lower across various workloads, including reasoning-heavy and chat-heavy tasks, demonstrating a robust alternative for tail-latency optimization in online LLM serving.

Problem. When you chat with an AI assistant or use AI agent, your request shares a server with many others, and the system constantly decides whose request to work on next. Some requests finish in a flash; others — especially when the model "reasons" through a hard problem — run far longer, and there is no reliable way to tell which is which in advance. Most systems try to guess each request's length and serve the shortest first, which lowers the average wait but leaves some unlucky users stuck waiting far too long, and those worst-case latencies are exactly what people notice. Solution. We built a scheduler that makes no predictions at all. Instead, it watches simple live signals to gently nudge each request's priority, while carefully managing the limited memory on AI chips so it rarely wastes effort by restarting interrupted work. A single adjustable knob lets operators balance protecting long requests against speeding up short ones. Impact. On real-world traffic, this cuts the worst-case waits by a third to a half, beating even methods handed perfect knowledge of request lengths, and is easy to add to existing systems.