Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents

• URL: http://arxiv.org/abs/2504.07347v2
• Date: Thu, 24 Apr 2025 14:10:22 GMT
• Title: Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents
• Authors: Yueying Li, Jim Dai, Tianyi Peng,
• Abstract summary: We develop the queuing fundamentals for large language model (LLM) inference.<n>We prove that a large class of 'work-conserving' scheduling algorithms can achieve maximum throughput.
• Score: 6.318292471845427
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As demand for Large Language Models (LLMs) and AI agents rapidly grows, optimizing systems for efficient LLM inference becomes critical. While significant efforts have focused on system-level engineering, little is explored from a mathematical modeling and queuing perspective. In this paper, we aim to develop the queuing fundamentals for large language model (LLM) inference, bridging the gap between the queueing theory and LLM system communities. In particular, we study the throughput aspect in LLM inference systems. We prove that a large class of 'work-conserving' scheduling algorithms can achieve maximum throughput for individual inference LLM engine, highlighting 'work-conserving' as a key design principle in practice. In a network of LLM agents, work-conserving scheduling alone is insufficient, particularly when facing specific workload structures and multi-class workflows that require more sophisticated scheduling strategies. Evaluations of real-world systems show that Orca and Sarathi-serve are throughput-optimal, reassuring practitioners, while FasterTransformer and vanilla vLLM are not maximally stable and should be used with caution. Our results highlight the substantial benefits that the queueing community can offer in improving LLM inference systems and call for more interdisciplinary development.

Related papers

• An Autonomous Network Orchestration Framework Integrating Large Language Models with Continual Reinforcement Learning [13.3347292702828]
  This paper proposes a framework called Autonomous Reinforcement Coordination (ARC) for a SemCom-enabled SAGIN.<n>ARC decomposes orchestration into two tiers, utilizing LLMs for high-level planning and RL agents for low-level decision-making.
  arXiv  Detail & Related papers  (2025-02-22T11:53:34Z)
• A Little Help Goes a Long Way: Efficient LLM Training by Leveraging Small LMs [74.35290684163718]
  A primary challenge in large language model (LLM) development is their onerous pre-training cost. This paper explores a promising paradigm to improve LLM pre-training efficiency and quality by leveraging a small language model (SLM)
  arXiv  Detail & Related papers  (2024-10-24T14:31:52Z)
• EVOLvE: Evaluating and Optimizing LLMs For Exploration [76.66831821738927]
  Large language models (LLMs) remain under-studied in scenarios requiring optimal decision-making under uncertainty. We measure LLMs' (in)ability to make optimal decisions in bandits, a state-less reinforcement learning setting relevant to many applications. Motivated by the existence of optimal exploration algorithms, we propose efficient ways to integrate this algorithmic knowledge into LLMs.
  arXiv  Detail & Related papers  (2024-10-08T17:54:03Z)
• Large Language Models for Knowledge-Free Network Management: Feasibility Study and Opportunities [36.70339455624253]
  This article presents a novel knowledge-free network management paradigm with the power of foundation models called large language models (LLMs) LLMs can understand important contexts from input prompts containing minimal system information, thereby offering remarkable inference performance even for entirely new tasks. Numerical results validate that knowledge-free LLMs are able to achieve comparable performance to existing knowledge-based optimization algorithms.
  arXiv  Detail & Related papers  (2024-10-06T07:42:23Z)
• LLMs can Schedule [3.435169201271934]
  Job shop scheduling problem (JSSP) remains a significant hurdle in optimizing production processes. This paper explores the potential of Large Language Models (LLMs) for JSSP. Surprisingly, our findings demonstrate that LLM-based scheduling can achieve performance comparable to other neural approaches.
  arXiv  Detail & Related papers  (2024-08-13T15:53:58Z)
• Large Language Model as a Catalyst: A Paradigm Shift in Base Station Siting Optimization [62.16747639440893]
  Large language models (LLMs) and their associated technologies advance, particularly in the realms of prompt engineering and agent engineering.<n>Our proposed framework incorporates retrieval-augmented generation (RAG) to enhance the system's ability to acquire domain-specific knowledge and generate solutions.
  arXiv  Detail & Related papers  (2024-08-07T08:43:32Z)
• CoMMIT: Coordinated Instruction Tuning for Multimodal Large Language Models [68.64605538559312]
  In this paper, we analyze the MLLM instruction tuning from both theoretical and empirical perspectives. Inspired by our findings, we propose a measurement to quantitatively evaluate the learning balance. In addition, we introduce an auxiliary loss regularization method to promote updating of the generation distribution of MLLMs.
  arXiv  Detail & Related papers  (2024-07-29T23:18:55Z)
• Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning [53.6472920229013]
  Large Language Models (LLMs) have demonstrated impressive capability in many natural language tasks. LLMs are prone to produce errors, hallucinations and inconsistent statements when performing multi-step reasoning. We introduce Q*, a framework for guiding LLMs decoding process with deliberative planning.
  arXiv  Detail & Related papers  (2024-06-20T13:08:09Z)
• New Solutions on LLM Acceleration, Optimization, and Application [14.995654657013741]
  Large Language Models (LLMs) have become extremely potent instruments with exceptional capacities for comprehending and producing human-like text in a range of applications. However, the increasing size and complexity of LLMs present significant challenges in both training and deployment. We provide a review of recent advancements and research directions aimed at addressing these challenges.
  arXiv  Detail & Related papers  (2024-06-16T11:56:50Z)
• Efficient Prompting for LLM-based Generative Internet of Things [88.84327500311464]
  Large language models (LLMs) have demonstrated remarkable capacities on various tasks, and integrating the capacities of LLMs into the Internet of Things (IoT) applications has drawn much research attention recently. Due to security concerns, many institutions avoid accessing state-of-the-art commercial LLM services, requiring the deployment and utilization of open-source LLMs in a local network setting. We propose a LLM-based Generative IoT (GIoT) system deployed in the local network setting in this study.
  arXiv  Detail & Related papers  (2024-06-14T19:24:00Z)
• Extracting Heuristics from Large Language Models for Reward Shaping in Reinforcement Learning [28.077228879886402]
  Reinforcement Learning (RL) suffers from sample inefficiency in reward domains, and the problem is further pronounced in case of transitions. To improve the sample efficiency, reward shaping is a well-studied approach to introduce intrinsic rewards that can help the RL agent converge to an optimal policy faster.
  arXiv  Detail & Related papers  (2024-05-24T03:53:57Z)
• Towards Efficient LLM Grounding for Embodied Multi-Agent Collaboration [70.09561665520043]
  We propose a novel framework for multi-agent collaboration that introduces Reinforced Advantage feedback (ReAd) for efficient self-refinement of plans. We provide theoretical analysis by extending advantage-weighted regression in reinforcement learning to multi-agent systems. Experiments on Over-AI and a difficult variant of RoCoBench show that ReAd surpasses baselines in success rate, and also significantly decreases the interaction steps of agents.
  arXiv  Detail & Related papers  (2024-05-23T08:33:19Z)
• Extending Token Computation for LLM Reasoning [5.801044612920816]
  Large Language Models (LLMs) are pivotal in advancing natural language processing. LLMs often struggle with complex reasoning tasks due to inefficient attention distributions. We introduce a novel method for extending computed tokens in the Chain-of-Thought process, utilizing attention mechanism optimization.
  arXiv  Detail & Related papers  (2024-03-22T03:23:58Z)
• LLM Inference Unveiled: Survey and Roofline Model Insights [62.92811060490876]
  Large Language Model (LLM) inference is rapidly evolving, presenting a unique blend of opportunities and challenges. Our survey stands out from traditional literature reviews by not only summarizing the current state of research but also by introducing a framework based on roofline model. This framework identifies the bottlenecks when deploying LLMs on hardware devices and provides a clear understanding of practical problems.
  arXiv  Detail & Related papers  (2024-02-26T07:33:05Z)
• Towards Efficient Generative Large Language Model Serving: A Survey from Algorithms to Systems [14.355768064425598]
  generative large language models (LLMs) stand at the forefront, revolutionizing how we interact with our data. However, the computational intensity and memory consumption of deploying these models present substantial challenges in terms of serving efficiency. This survey addresses the imperative need for efficient LLM serving methodologies from a machine learning system (MLSys) research perspective.
  arXiv  Detail & Related papers  (2023-12-23T11:57:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.