TIE Scheduler: Optimizing LLM Inference Scheduling with Uncertainty-Aware Prediction

The TIE scheduler addresses the problem in LLM inference scheduling where traditional point estimation ignores the randomness of output length. Through analysis, it was found that output length follows a heavy-tailed distribution (fittable with a log-t distribution), and the Tail Inflated Expectation (TIE) metric was proposed to adjust the risk of long outputs. Experimental results show a 2.31x reduction in per-token latency for online inference and a 1.42x increase in throughput for offline batch processing.

LLM inference services face latency and throughput bottlenecks. Request processing is divided into two stages: prefill and decode. Scheduling needs to balance latency and throughput, but output lengths vary greatly between requests, so FIFO is prone to head-of-line blocking. The SJF strategy prioritizes short jobs, but existing methods use point estimation to predict output length, which cannot capture the randomness of the generation process.

Studies have found that output length exhibits a heavy-tailed distribution, which can be fitted with a t-distribution after log transformation. Based on this, the TIE metric is proposed: it combines the distribution expectation and tail probability to upwardly adjust the risk of long outputs. TIE is compatible with the SJF framework, computationally efficient, and can be used online in real time.

1. Online prediction: A lightweight model outputs log-t distribution parameters based on prompt features; 2. Dynamic adjustment: Update output length estimates during generation; 3. Batch processing optimization: Combine requests with similar TIE values to reduce load imbalance; 4. Strategy combination: Collaborate with priority scheduling and preemption mechanisms.

Online inference scenario: TPOT reduced by 2.31x, head-of-line blocking reduced; Offline batch processing: Throughput increased by 1.42x, batch composition optimized; Compared to baselines (FIFO, point-estimation SJF, quantile SJF), it performs best and has good generalization in tasks such as dialogue and code generation.

1. Reveals the random nature of output length in LLM inference; 2. Proves the importance of heavy-tailed distribution modeling for scheduling optimization; 3. Provides an efficient uncertainty quantification method, offering new ideas for system optimization.

Limitations: Relies on the log-t distribution assumption, prediction accuracy is affected by prompt complexity; Future directions: Explore more flexible distribution models, stronger predictors, multi-dimensional optimization (combining input length/priority), and hardware-aware scheduling.

Cloud service providers: Improve resource utilization and reduce costs; Enterprise users: Enhance interaction experience and support high concurrency; Researchers: Provide a reference for uncertainty scheduling problems. As LLM applications grow, uncertainty-aware optimization will become a key direction.