mlsanityData to 14 Oct 2026

Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents

arXiv 2504.07347 ↗First posted 10 Apr 2025stat.ML cs.LG math.PRcited by 18

On the map: LLM agents and tool use → Software engineering coding agents

also in 1 more
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.

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.

Builds on

11 of 69 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025Autellix: An Efficient Serving Engine for LLM Agents as General Programs19 Feb

Other references · 10

  1. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
  2. 2021Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LMcited by 632
  3. 2024DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Servingcited by 617
  4. 2023Splitwise: Efficient generative LLM inference using phase splittingcited by 558
  5. 2025FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Servingcited by 258
  6. 2023SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefillscited by 193
  7. 2024Vidur: A Large-Scale Simulation Framework For LLM Inferencecited by 117
  8. 2024POD-Attention: Unlocking Full Prefill-Decode Overlap for Faster LLM Inferencecited by 47
  9. 2024Queue management for slo-oriented large language model servingcited by 36
  10. 2025Queueing, Predictions, and LLMs: Challenges and Open Problemscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 6; 2026: 12.

18 papers.

Sort:

By area:

  1. 2026Parallelizing Tool Execution and LLM Generation for Low-Latency Agent Servingcited by 20
  2. 2025Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraintscited by 19
  3. 2025Taming the Titans: A Survey of Efficient LLM Inference Servingcited by 16
  4. 2025Auto-Formulating Dynamic Programming Problems with Large Language Modelscited by 16
  5. 2025Adaptively Robust LLM Inference Optimization under Prediction Uncertaintycited by 10
  6. 2025LLM Serving Optimization with Variable Prefill and Decode Lengthscited by 7
  7. 2025Optimal Scheduling Algorithms for LLM Inference: Theory and Practicecited by 6
  8. 2026SAGA: Workflow-Atomic Scheduling for AI Agent Inference on GPU Clusterscited by 6
  9. 2026A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraintscited by 2
  10. 2026Optimizing Service Operations via LLM-Powered Multi-Agent Simulationcited by 1
  11. 2026Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM poolscited by 1
  12. 2026AgentOpt v0.1 Technical Report: Client-Side Optimization for LLM-Based Agentcited by 0
6 more
  1. 2026Flow-Controlled Scheduling for LLM Inference with Provable Stability Guaranteescited by 0
  2. 2026Service-Induced Congestion in Memory-Constrained LLM Servingcited by 0
  3. 2026Beyond Prediction: Tail-Aware Scheduling for LLM Inferencecited by 0
  4. 2026Efficient Clustering with Quality Guardrails for LLM-based Recommender Systems at Industry Scalecited by 0
  5. 2026LLM Inference Under Bursty Workload Distribution: Modifying the WAIT Algorithmcited by 0
  6. 2026DEALS: Decentralized Expertise-Aware Load Serving for Multi-Agent LLM Systemscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Efficient LLM Scheduling by Learning to Rank
  2. 2026End-to-End Latency-Minimizing and Load-Balanced Request Scheduling for Edge LLM Inference in Agentic AI Services
  3. 2024Multi-Bin Batching for Increasing LLM Inference Throughput
  4. 2023Fast Distributed Inference Serving for Large Language Models
  5. 2025Astraea: A State-Aware Scheduling Engine for LLM-Powered Agents
  6. 2023Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline
  7. 2026AgentPerfBench: A Benchmarking and Evaluation Suite for Inference Performance of Agentic LLMs
  8. 2024Demystifying AI Platform Design for Distributed Inference of Next-Generation LLM models