LLM Inference Under Bursty Workload Distribution: Modifying the WAIT Algorithm

Anjali Gangadhar Katageria; Shobha Rani; Raghu Nandan Sengupta

cs.LGAug 6, 2026

LLM Inference Under Bursty Workload Distribution: Modifying the WAIT Algorithm

Authors: Anjali Gangadhar Katageria, Shobha Rani, Raghu Nandan Sengupta

Organizations: Department of Mathematics, Indian Institute of Technology Dharwad, Dharwad, Karnataka, India · Department of Management Sciences, Indian Institute of Technology Kanpur, Kanpur, Uttar Pradesh, India

Abstract

Large Language Models (LLMs) such as ChatGPT and Claude are widely used for information retrieval and problem-solving. Recent work has focused on improving scheduling algorithms to boost throughput while maintaining low latency. However, these approaches often assume Poisson request arrivals with constant rates - an assumption that fails to reflect the inherently bursty and dynamic nature of real-world traffic. We propose a lightweight extension to the state-of-the-art WAIT algorithm [1], which adapts to time-varying arrival rates without prior traffic knowledge. The proposed algorithm performs online estimation of request intensity based on observed interarrival times. Using Markov Modulated Poisson Process (MMPP)-based synthetic workloads with diverse request types, we conduct a simulation-based evaluation demonstrating that the proposed method achieves higher throughput than Sarathi-Serve [2], ORCA [3], and vLLM [4] in the evaluated low arrival-rate shift scenarios while maintaining comparable latency.

Explore similar work

Beyond Prediction: Tail-Aware Scheduling for LLM Inference
Jun 16, 2026Yueying Li, Yuanfan Chen, Jiayang Chen +6Large Language Model Serving Optimal Scheduling
Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice
Jun 21, 2026Li Kong, Qi Qi, Yinyu Ye +1Large Language Model Serving Optimal Scheduling
MAPS: Memory-Aware Predictive Scheduling Framework for Large Language Model Serving
Sep 14, 2026Tiancheng Zhang, Yulin Chen, Yunfeng Zhao +3Large Language Model Serving Optimal Scheduling

Jun 16, 2026 · cs.LGJ/K move · Enter open · S save

Beyond Prediction: Tail-Aware Scheduling for LLM Inference

Yueying Li, Yuanfan Chen, Jiayang Chen, Esha Choukse+5

Cornell University, Computer Science Department, NY, USA · Microsoft Azure System Research, WA, USA · Cornell University, Electrical and Computer Engineering Department, NY, USA · NVIDIA Corporation, CA, USA · Cornell University, Operations Research and Information Engineering Department, NY, USA

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.

Large Language Model Serving Optimal Scheduling Scheduling Low-Latency Systems

Open paper Ask about it PDF

Abstract

Explore similar work

Beyond Prediction: Tail-Aware Scheduling for LLM Inference

Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice

MAPS: Memory-Aware Predictive Scheduling Framework for Large Language Model Serving