# Scheduling LLM Inference with Uncertainty-Aware Output Length Predictions

arXiv: https://arxiv.org/abs/2604.00499 · HTML: https://mlsanity.com/paper/2604.00499/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 45 references that are in the map.
- First posted on arXiv 1 Apr 2026.

## Builds on (most cited first, 24 of 24)

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [DeBERTaV3: Improving DeBERTa using ELECTRA-Style Pre-Training with Gradient-Disentangled Embedding Sharing](https://mlsanity.com/paper/2111.09543/) (2021)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset](https://mlsanity.com/paper/2309.11998/) (2023)
- [A Long Way to Go: Investigating Length Correlations in RLHF](https://mlsanity.com/paper/2310.03716/) (2023)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Qwen2.5-1M Technical Report](https://mlsanity.com/paper/2501.15383/) (2025)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs](https://mlsanity.com/paper/2407.01082/) (2024)
- [Fast Distributed Inference Serving for Large Language Models](https://mlsanity.com/paper/2305.05920/) (2023)
- [Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline](https://mlsanity.com/paper/2305.13144/) (2023)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [S3: Increasing GPU Utilization during Generative Inference for Higher Throughput](https://mlsanity.com/paper/2306.06000/) (2023)
- [Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction](https://mlsanity.com/paper/2404.08509/) (2024)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Don't Stop Me Now: Embedding Based Scheduling for LLMs](https://mlsanity.com/paper/2410.01035/) (2024)
- [Towards Demystifying Serverless Machine Learning Training](https://mlsanity.com/paper/2105.07806/) (2021)
- [Balancing Cost and Effectiveness of Synthetic Data Generation Strategies for LLMs](https://mlsanity.com/paper/2409.19759/) (2024)
- [KV Prediction for Improved Time to First Token](https://mlsanity.com/paper/2410.08391/) (2024)
- [Adaptively Robust LLM Inference Optimization under Prediction Uncertainty](https://mlsanity.com/paper/2508.14544/) (2025)
- [ELIS: Efficient LLM Iterative Scheduling System with Response Length Predictor](https://mlsanity.com/paper/2505.09142/) (2025)
- [Internet Traffic Volumes Are Not Gaussian -- They Are Log-Normal: An 18-Year Longitudinal Study With Implications for Modelling and Prediction (Complete Version)](https://mlsanity.com/paper/2007.10150/) (2020)

## Built on by (most cited first, 8 of 8)

- [Robust Length Prediction: A Perspective from Heavy-Tailed Prompt-Conditioned Distributions](https://mlsanity.com/paper/2604.07931/) (2026)
- [TailSieve: Partial-Rollout-Guided Tail Routing for LLM Rollouts](https://mlsanity.com/paper/2608.22788/) (2026)
- [OUTLETS: Output-Length Prediction from Speculative Decoding Backbones](https://mlsanity.com/paper/2609.01068/) (2026)
- [MiCU: End-to-End Smart Home Command Understanding with Large Language Model](https://mlsanity.com/paper/2606.01099/) (2026)
- [BALANCE: Hybrid Autoregressive-Speculative LLM Inference at the Network Edge](https://mlsanity.com/paper/2608.05926/) (2026)
- [TokenCast: Forecasting Token Consumption During LLM Agent Execution](https://mlsanity.com/paper/2609.35760/) (2026)
- [Denoising Surface: Modeling and Predicting Inference Cost for Diffusion LLM Serving](https://mlsanity.com/paper/2610.00499/) (2026)
- [Jumping the Line: Exploiting Length Predictions in LLM Scheduling](https://mlsanity.com/paper/2610.03430/) (2026)

## Abstract (arXiv)

To schedule LLM inference, the textitshortest job first (SJF) principle is favorable by prioritizing requests with short output lengths to avoid head-of-line (HOL) blocking. Existing methods usually predict a single output length for each request to facilitate scheduling. We argue that such a textitpoint estimate does not match the textitstochastic decoding process of LLM inference, where output length is textituncertain by nature and determined by when the end-of-sequence (EOS) token is sampled. Hence, the output length of each request should be fitted with a distribution rather than a single value. With an in-depth analysis of empirical data and the stochastic decoding process, we observe that output length follows a heavy-tailed distribution and can be fitted with the log-t distribution. On this basis, we propose a simple metric called Tail Inflated Expectation (TIE) to replace the output length in SJF scheduling, which adjusts the expectation of a log-t distribution with its tail probabilities to account for the risk that a request generates long outputs. To evaluate our TIE scheduler, we compare it with three strong baselines, and the results show that TIE reduces the per-token latency by 2.31× for online inference and improves throughput by 1.42× for offline data generation.