Adaptively Robust LLM Inference Optimization under Prediction Uncertainty

2025/08/20 by Zixi Chen, Yinyu Ye, Chen, Zixi +3 · 1 citation
Computer Science · Materials Science · #Artificial Intelligence (cs.AI) #Big Data and Digital Economy #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning in Materials Science #Natural Language Processing Techniques #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2508.14544

openalex publication_date 2025/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of optimizing Large Language Model (LLM) inference scheduling to minimize total latency. LLM inference is an online and multi-task service process and also heavily energy consuming by which a pre-trained LLM processes input requests and generates output tokens sequentially. Therefore, it is vital to improve its scheduling efficiency and reduce the power consumption while a great amount of prompt requests are arriving. A key challenge in LLM inference scheduling is that while the prompt length is known upon arrival, the output length, which critically impacts memory usage and processing time, is unknown. To address this uncertainty, we propose algorithms that leverage machine learning to predict output lengths, assuming the prediction provides an interval classification (min-max range) for each request. We first design a conservative algorithm, A_max, which schedules requests based on the upper bound of predicted output lengths to prevent memory overflow. However, this approach is overly conservative: as prediction accuracy decreases, performance degrades significantly due to potential overestimation. To overcome this limitation, we propose A_min, an adaptive algorithm that initially treats the predicted lower bound as the output length and dynamically refines this estimate during inferencing. We prove that A_min achieves a log-scale competitive ratio. Through numerical simulations, we demonstrate that A_min often performs nearly as well as the hindsight scheduler, highlighting both its efficiency and robustness in practical scenarios. Moreover, A_min relies solely on the lower bound of the prediction interval--an advantageous design choice since upper bounds on output length are typically more challenging to predict accurately.

Citations

• LLM Serving Optimization with Variable Prefill and Decode Lengths
• Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints
• Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents
• Online Scheduling for LLM Inference with KV Cache Constraints
• Don't Stop Me Now: Embedding Based Scheduling for LLMs
• Efficient LLM Scheduling by Learning to Rank
• ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling
• Vidur: A Large-Scale Simulation Framework For LLM Inference
• Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction
• Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
• DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving
• Splitwise: Efficient generative LLM inference using phase splitting
• LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset
• SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
• Online Resource Allocation with Convex-set Machine-Learned Advice
• Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline
• PaLM: Scaling Language Modeling with Pathways
• Secretary and Online Matching Problems with Machine Learned Advice
• Language Models are Few-Shot Learners
• Scaling Laws for Neural Language Models
• Competitive caching with machine learned advice
• The Price of Robustness

Cited by

• Specification and Detection of LLM Code Smells
• LLM Serving Optimization with Variable Prefill and Decode Lengths

Related

• Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline
• ELIS: Efficient LLM Iterative Scheduling System with Response Length Predictor
• Online Scheduling for LLM Inference with KV Cache Constraints
• Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents
• Statistical Modeling and Uncertainty Estimation of LLM Inference Systems