Scheduling LLM Inference with Uncertainty-Aware Output Length Predictions

Haoyu Zheng; Yongqiang Zhang; Fangcheng Fu; Xiaokai Zhou; Hao Luo; Hongchao Zhu; Yuanyuan Zhu; Hao Wang

cs.LGApr 1, 2026

Scheduling LLM Inference with Uncertainty-Aware Output Length Predictions

Authors: Haoyu Zheng, Yongqiang Zhang, Fangcheng Fu, Xiaokai Zhou, Hao Luo, Hongchao Zhu, Yuanyuan Zhu, Hao Wang,

Organizations: School of Computer Science, Wuhan University, Wuhan, China · Dameng Database Co., Ltd., Wuhan, China · School of Artificial Intelligence, Shanghai Jiao Tong University, Shanghai, China · Institute for Math and AI, Wuhan University, Wuhan, China ·

Abstract

To schedule LLM inference, the shortest 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 point estimate does not match the stochastic decoding process of LLM inference, where output length is uncertain 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\times$ for online inference and improves throughput by $1.42\times$ for offline data generation.

Figures & tables

Figure 1: Output length distribution for the first prompt in LMSYS-Chat-1M dataset ( Zheng et al., 2024 ) . Bars are the output lengths in 256 generations, while red curve is the fitted log-t distribution.

Distribution	# Parameters	KS Pass Rate
Log-t	3	93.1%
Log-t ( $\nu=3.5$ )	2	90.6%
Log-normal	2	60.3%
Gamma	2	32.0%
Weibull	2	19.0%
Exponential	1	10.7%

Table 1: Goodness of fit for common heavy-tailed distributions (1,000 prompts, 100 generations each). KS pass rate: the percentage of prompts where the fit passes the KS test (

p>0.05

Figure 2: Overview of the overall scoring pipeline. The prompt is prepended with a CLS token and encoded by DeBERTa. A multi-pooling strategy aggregates the CLS token, mean-pooled, and max-pooled representations. Two separate prediction heads (MLPs) predict $\hat{\mu}$ and $\hat{\sigma}$ , which together with a fixed $\nu=3.5$ are used to construct the log-t distribution. The final score is computed from $\mathbb{E}(\tilde{X})$ and CVaR.

Figure 3: Scheduling workflow for new requests. Solid arrows indicate the main workflow, while dashed arrows represent the asynchronous prediction workflow.

Panel of Figure 4 — Figure 4: Performance of schedulers for online chatbot serving on the real-world workload (LMSYS-Chat-1M) with the 8B model.

Testing Dataset	Testing Model Size	Average Per-token Latency (s/token) $\downarrow$				P90 Per-token Latency (s/token) $\downarrow$
Testing Dataset	Testing Model Size	FCFS	SSJF	LTR	TIE	FCFS	SSJF	LTR	TIE
LMSYS-Chat-1M	70B	9.08	5.50	4.34	2.41	16.13	8.24	7.03	4.05
ShareGPT	8B	1.66	0.95	0.86	0.57	3.27	1.84	1.56	0.90
ShareGPT	70B	4.36	2.43	2.22	1.41	8.78	4.90	3.78	2.22
Alpaca	8B	1.45	0.71	0.83	0.52	3.62	1.47	1.76	0.93
Alpaca	70B	4.52	2.06	2.36	1.54	11.36	4.32	5.14	2.81

Table 2: Generalization performance of scheduling strategies across different datasets and models under a request rate of 100 RPS. Training data for all methods are derived from LMSYS-Chat-1M using the 8B model.

Training Dataset	Testing Model Size	Time for 3k Samples (s) $\downarrow$				Throughput within 3 min $\uparrow$
Training Dataset	Testing Model Size	FCFS	SSJF	LTR	TIE (ours)	FCFS	SSJF	LTR	TIE (ours)
LMSYS-Chat-1M	8B	229.37	144.93	139.53	98.12	2292	3488	3672	4762
LMSYS-Chat-1M	70B	559.30	324.52	316.98	246.10	861	1557	1895	2524
Alpaca	8B	229.37	135.79	130.67	95.08	2292	3766	3663	4869
Alpaca	70B	559.30	311.06	314.36	240.19	861	1634	1708	2659

Table 3: Performance of schedulers on SDG tasks, across training datasets and testing model sizes. Evaluated on Alpaca dataset.

Panel of Figure 5 — Figure 5: Heatmaps of completion time versus output length under different strategies on the Alpaca dataset with the 8B model. TIE achieves higher concentration than SSJF and LTR, indicating its ability to accurately capture possible output lengths.

Distribution	Score $=$	Per-token Latency (s) $\downarrow$		TTFT (s) $\downarrow$		Time for 3k Samples (s) $\downarrow$	Throughput within 3 min $\uparrow$
Distribution	Score $=$	Average	P90	Average	P90	Time for 3k Samples (s) $\downarrow$	Throughput within 3 min $\uparrow$
log-t ( $\nu$ =3.5)	$\mathbb{E}[X]+\beta\cdot$ CVaR	0.67	0.96	48.23	131.13	98.12	4762
log-t (dynamic $\nu$ )	$\mathbb{E}[X]+\beta\cdot$ CVaR	0.69	1.02	47.76	132.40	97.70	4709
log-normal	$\mathbb{E}[X]+\beta\cdot$ CVaR	1.63	3.37	70.91	174.88	142.21	3584
log-t ( $\nu$ =3.5)	$\mathbb{E}[X]$ (i.e., SEPT scheduling)	0.75	1.21	52.26	145.03	108.51	4257
log-t ( $\nu$ =3.5)	$\mathbb{E}[X]+0.1\cdot$ CVaR	0.72	1.15	50.07	141.77	104.76	4391

Table 4: Ablation study on distribution family and score computation method. Online chatbot experiments use the LMSYS-Chat-1M dataset, and offline SDG experiments use the Alpaca dataset. All experiments are conducted on the Meta-Llama-3-8B-Instruct model. For score computation, CVaR is calculated at

\alpha=0.9

, and

\beta

denotes the adaptive risk-sensitivity coefficient. The gray row indicates the default configuration of TIE, orange rows indicate distribution family ablations, and green rows indicate score computation ablations.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 6 — Figure 6: Distributions of prompt lengths across datasets (tokenized using Meta-Llama-3-8B-Instruct) and output lengths across models.

Model	Dataset	Avg. PTLA (s/token) $\downarrow$				Avg. TTFT (s) $\downarrow$
Model	Dataset	FCFS	SSJF	LTR	TIE	FCFS	SSJF	LTR	TIE
GPT-oss-20B	LMSYS-Chat-1M	11.55	6.77	4.96	3.00	188.33	167.68	149.46	112.34
	ShareGPT	3.83	3.03	1.97	1.10	255.15	244.73	214.05	171.65
	Alpaca	3.91	2.19	2.06	1.26	117.35	98.59	97.66	71.79
Qwen3-30B-A3B-Instruct-2507	LMSYS-Chat-1M	8.07	3.40	2.95	1.59	150.18	109.49	96.26	73.62
	ShareGPT	3.76	1.75	1.50	0.86	224.70	172.47	150.54	116.26

Appendix

Table 5: Performance comparison of scheduling strategies across different models under the Chatbot workload.

Model	Time for 3k Samples (s) $\downarrow$				Throughput within 3 min $\uparrow$
Model	FCFS	SSJF	LTR	TIE	FCFS	SSJF	LTR	TIE
GPT-oss-20B	283.57	257.26	202.88	165.56	1828	1957	2654	3298
Qwen3-30B-A3B-Instruct-2507 (MoE)	176.27	152.69	106.53	68.80	3045	3511	4563	6419
Qwen3-Next-80B-A3B-Instruct (MoE)	271.22	233.51	156.85	123.91	1907	2193	3379	4316
DeepSeek-R1-Distill-Qwen-32B	2058.48	1584.06	1524.46	1134.33	245	352	394	533
Mistral-7B-Instruct-v0.3	238.95	175.88	196.77	123.07	2246	3077	2601	4173

Appendix

Table 6: Performance comparison of scheduling strategies on the SDG task across different models, tested on Alpaca dataset.

Figure 7: Effect of the number of repetitions on parameter estimation accuracy. The relative error is computed against the baseline obtained with 100 repetitions per prompt.

Figure 8: Effect of the degrees of freedom parameter

\nu

on fitting quality.

Type	Category	#Prompt	Skewness	CV	P90/P50	P99/P50	KS Pass
Structured	Translation & Reformulation	266	2.75	0.93	3.40	7.80	89.5%
	Factual QA & Knowledge	292	3.54	1.22	4.63	11.87	93.5%
	Code & Structured Output	158	2.79	0.87	2.99	6.86	94.4%
Open-ended	Creative & Open-ended Writing	165	3.42	1.12	5.60	13.00	95.7%
Open-ended	Conversation & Roleplay	82	2.68	1.35	7.50	16.50	95.2%
Others		37	3.00	1.45	9.50	17.50	94.0%

Appendix

Table 7: Diagnostic statistics by prompt family for the 1K

\times

100 prompt data (Section 3.1). Prompts classified using Qwen3-32B (thinking mode). Generation model: Llama-3-8B-Instruct. Dataset: LMSYS-Chat-1M. KS Pass: log-t test pass rate at

p>0.05

Training Data	TIE (ours)	SSJF	LTR
900K $\times$ 1	–	1.95	1.55
45K $\times$ 20	0.67	2.31	2.42
20K $\times$ 20	0.88	–	–
20K $\times$ 10	1.07	–	–
15K $\times$ 10	1.58	–	–
10K $\times$ 10	2.26	–	–

Appendix

Table 8: Average per-token latency (s/token) at 100 RPS with different training data scales (

K

prompts

\times

N

generations each). Model: Llama-3-8B-Instruct. Dataset: LMSYS-Chat-1M.

Temp.	TIE (ours)	SSJF	LTR
0.4	0.84	1.98	1.63
0.7 (as in training)	0.67	1.95	1.55
1.0	0.73	2.02	1.70
1.3	1.13	2.59	2.62
1.6	2.61	4.42	5.77

Appendix

Table 9: Average per-token latency (s/token) at 100 RPS. All schedulers trained at temperature

=

0.7, evaluated at varying temperatures. Model: Llama-3-8B-Instruct. Dataset: LMSYS-Chat-1M.

$\beta$	10 RPS	30 RPS	60 RPS	100 RPS	200 RPS
Adaptive	0.05	0.18	0.41	0.67	1.88
0.1	0.05	0.23	0.49	0.72	2.17
0.3	0.07	0.20	0.44	0.71	2.09
0.5	0.09	0.25	0.46	0.70	1.96
0.7	0.12	0.29	0.48	0.74	2.05

Appendix

Table 10: Average per-token latency (s/token) with adaptive vs. fixed

\beta

across request rates. Model: Llama-3-8B-Instruct. Dataset: LMSYS-Chat-1M. Bold : adaptive

\beta

; underlined : best fixed

\beta

per column.

RPS	10	30	40	60	80	100
TIE (ours)	0.05	0.18	0.25	0.41	0.54	0.67
TRAIL	0.06	0.15	0.23	0.57	0.87	1.41

Appendix

Table 11: Average per-token latency (s/token): TIE vs. TRAIL across RPS. Model: Llama-3-8B-Instruct. Dataset: LMSYS-Chat-1M.

RPS	TIE ( $\sigma_{\text{noise}}$ =0)	TIE (0.1)	TIE (0.3)	TIE (0.5)	TIE (0.7)	SSJF	LTR
60	0.41	0.43	0.49	0.55	0.60	0.91	0.76
100	0.67	0.77	1.05	1.34	1.66	1.95	1.55

Appendix

Table 12: Average per-token latency (s/token) under varying

\sigma

noise levels.

\sigma_{\text{noise}}

: range of multiplicative noise applied to predicted

\sigma

, i.e., the scheduler operates with

(1\pm\sigma_{\text{noise}})\times

predicted

\sigma

. Model: Llama-3-8B-Instruct. Dataset: LMSYS-Chat-1M.

Panel of Figure 9 — Figure 9: Full heatmaps of completion time versus output length under different strategies on the Alpaca dataset with the 8B model.

Panel of Figure 10 — Figure 10: Full heatmaps of completion time versus output length under different strategies on the Alpaca dataset with the 70B model.

LLM Inference Scheduling

Large language model inference scheduling allocates requests, batches, compute, and KV-cache memory to balance latency, throughput, and service-level objectives.

See all 160 papers

Beyond Prediction: Tail-Aware Scheduling for LLM Inference
Jun 16, 2026Yueying Li, Yuanfan Chen, Jiayang Chen +6LLM Serving Inference-Time Optimization
Cornell University, Computer Science Department, NY, USA · Microsoft Azure System Research, WA, USA · Cornell University, Electrical and Computer Engineering Department, NY, USA +2
OUTLETS: Output-Length Prediction from Speculative Decoding Backbones
Sep 1, 2026Weihuang Wen, Yingying Liu, Yichuan Liu +5LLM Serving LLM Inference Scheduling
The Chinese University of Hong Kong, Shenzhen · The University of Hong Kong · Huawei Technologies Co., Ltd.
Jumping the Line: Exploiting Length Predictions in LLM Scheduling
Oct 2, 2026Yuyang Dai, Rana Shahout, Mahmood SharifLLM Inference Scheduling LLM Serving
Florida State University · MIT · Tel Aviv University

Jun 16, 2026J/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+2

LLM Serving Inference-Time Optimization LLM Inference Scheduling LLM Request Scheduling

Open paper AskPDF arXiv

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.

Abstract

LLM Inference Scheduling

Explore similar work

Beyond Prediction: Tail-Aware Scheduling for LLM Inference

OUTLETS: Output-Length Prediction from Speculative Decoding Backbones

Jumping the Line: Exploiting Length Predictions in LLM Scheduling