# Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use.
- Builds on 11 of its 69 references that are in the map.
- First posted on arXiv 10 Apr 2025.

## Placed in

- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)
- Efficient LLM inference and serving / [Serving systems and request scheduling](https://mlsanity.com/inference/serving-systems-and-request-scheduling/)

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

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://mlsanity.com/paper/2104.04473/) (2021)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving](https://mlsanity.com/paper/2501.01005/) (2025)
- [SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills](https://mlsanity.com/paper/2308.16369/) (2023)
- [Vidur: A Large-Scale Simulation Framework For LLM Inference](https://mlsanity.com/paper/2405.05465/) (2024)
- [Autellix: An Efficient Serving Engine for LLM Agents as General Programs](https://mlsanity.com/paper/2502.13965/) (2025)
- [POD-Attention: Unlocking Full Prefill-Decode Overlap for Faster LLM Inference](https://mlsanity.com/paper/2410.18038/) (2024)
- [Queue management for slo-oriented large language model serving](https://mlsanity.com/paper/2407.00047/) (2024)
- [Queueing, Predictions, and LLMs: Challenges and Open Problems](https://mlsanity.com/paper/2503.07545/) (2025)

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

- [Parallelizing Tool Execution and LLM Generation for Low-Latency Agent Serving](https://mlsanity.com/paper/2603.18897/) (2026)
- [Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints](https://mlsanity.com/paper/2504.11320/) (2025)
- [Taming the Titans: A Survey of Efficient LLM Inference Serving](https://mlsanity.com/paper/2504.19720/) (2025)
- [Auto-Formulating Dynamic Programming Problems with Large Language Models](https://mlsanity.com/paper/2507.11737/) (2025)
- [Adaptively Robust LLM Inference Optimization under Prediction Uncertainty](https://mlsanity.com/paper/2508.14544/) (2025)
- [LLM Serving Optimization with Variable Prefill and Decode Lengths](https://mlsanity.com/paper/2508.06133/) (2025)
- [Optimal Scheduling Algorithms for LLM Inference: Theory and Practice](https://mlsanity.com/paper/2508.01002/) (2025)
- [SAGA: Workflow-Atomic Scheduling for AI Agent Inference on GPU Clusters](https://mlsanity.com/paper/2605.00528/) (2026)
- [A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints](https://mlsanity.com/paper/2605.04595/) (2026)
- [Optimizing Service Operations via LLM-Powered Multi-Agent Simulation](https://mlsanity.com/paper/2604.04383/) (2026)
- [Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM pools](https://mlsanity.com/paper/2607.18253/) (2026)
- [AgentOpt v0.1 Technical Report: Client-Side Optimization for LLM-Based Agent](https://mlsanity.com/paper/2604.06296/) (2026)
- [Flow-Controlled Scheduling for LLM Inference with Provable Stability Guarantees](https://mlsanity.com/paper/2604.11001/) (2026)
- [Service-Induced Congestion in Memory-Constrained LLM Serving](https://mlsanity.com/paper/2606.15555/) (2026)
- [Beyond Prediction: Tail-Aware Scheduling for LLM Inference](https://mlsanity.com/paper/2606.18431/) (2026)
- [Efficient Clustering with Quality Guardrails for LLM-based Recommender Systems at Industry Scale](https://mlsanity.com/paper/2607.19704/) (2026)
- [LLM Inference Under Bursty Workload Distribution: Modifying the WAIT Algorithm](https://mlsanity.com/paper/2608.06135/) (2026)
- [DEALS: Decentralized Expertise-Aware Load Serving for Multi-Agent LLM Systems](https://mlsanity.com/paper/2609.33768/) (2026)

## Abstract (arXiv)

As demand for Large Language Models (LLMs) and AI agents grows rapidly, optimizing systems for efficient LLM inference becomes critical. While significant efforts have targeted system-level engineering, little has been explored from a mathematical modeling and queueing perspective. In this paper, we develop the queueing fundamentals for LLM inference. In particular, we study the throughput aspect of LLM inference systems. We prove that a large class of `work-conserving' scheduling algorithms achieve maximum throughput for both individual requests and AI-agent workloads with directed acyclic graph (DAG) and fork-join routing topologies, establishing `work-conserving' as a key design principle for practitioners. Technically, we develop a fluid-limit framework for multi-class batched processing networks under K-FCFS scheduling, which may be of independent interest. Evaluations of real-world systems confirm 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 analysis also reveals how constraints such as batch size limits and cyclic routing topologies complicate the throughput picture, pointing to rich open questions at the intersection of queueing theory and LLM system design.