Reproduce “Queueing, Predictions, and LLMs: Challenges and Open Problems” on OpenResearch

About this paper

Michael Mitzenmacher, Rana Shahout

This paper surveys advancements in leveraging predictions to optimize queueing systems and applies this framework to the complex scheduling challenges inherent in Large Language Model (LLM) inference. It identifies numerous open problems at the intersection of classical queueing theory, learning-augmented algorithms, and LLM systems, aiming to guide future research toward achieving lower latency and higher throughput.

Key insights

• Integrating machine learning predictions into queueing policies can significantly improve average response times, often approaching the performance of policies with perfect information, even with imperfect predictions.
• LLM inference introduces distinct scheduling challenges, such as the dynamic KV cache and high preemption costs, which necessitate new queueing models and prediction-aware algorithms beyond traditional approaches.
• The precise definition and management of the "cost of predictions" are crucial for developing practical and optimal scheduling policies that selectively use predictive information.

Summary by alphaXiv.