mlsanityData to 7 Oct 2026

Optimal Scheduling Algorithms for LLM Inference: Theory and Practice

arXiv 2508.01002 ↗First posted 1 Aug 2025cs.LG cs.DCcited by 5

On the map: Efficient LLM inference and serving → Serving systems and request scheduling

Abstract (arXiv)

With the growing use of Large Language Model (LLM)-based tools like ChatGPT, Perplexity, and Gemini across industries, there is a rising need for efficient LLM inference systems. These systems handle requests with a unique two-phase computation structure: a prefill-phase that processes the full input prompt and a decode-phase that autoregressively generates tokens one at a time. This structure calls for new strategies for routing and scheduling requests. In this paper, we take a comprehensive approach to this challenge by developing a theoretical framework that models routing and scheduling in LLM inference systems. We identify two key design principles-optimal tiling and dynamic resource allocation-that are essential for achieving high throughput. Guided by these principles, we propose the Resource-Aware Dynamic (RAD) scheduler and prove that it achieves throughput optimality under mild conditions. To address practical Service Level Objectives (SLOs) such as serving requests with different Time Between Token (TBT) constraints, we design the SLO-Aware LLM Inference (SLAI) scheduler. SLAI uses real-time measurements to prioritize decode requests that are close to missing their TBT deadlines and reorders prefill requests based on known prompt lengths to further reduce the Time To First Token (TTFT) delays. We evaluate SLAI on the Openchat ShareGPT4 dataset using the Mistral-7B model on an NVIDIA RTX ADA 6000 GPU. Compared to Sarathi-Serve, SLAI reduces the median TTFT by 53% and increases the maximum serving capacity by 26% such that median TTFT is below 0.5 seconds, while meeting tail TBT latency constraints.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Placed in Serving systems and request scheduling, one of 12 directions in Efficient LLM inference and serving. Builds on 20 of its 49 references that are in the map. First posted on arXiv 1 Aug 2025.

Builds on

20 of 49 references.

Closest ancestors · 4

Same direction, newest first

  1. 2025Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents10 Apr
  2. 2024Llumnix: Dynamic Scheduling for Large Language Model Serving5 Jun
  3. 2024Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve4 Mar
  4. 2023FlashDecoding++: Faster Large Language Model Inference on GPUs2 Nov

Other references · 16

  1. 2017Attention Is All You Needcited by 59,932
  2. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,767
  3. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  4. 2022Fast Inference from Transformers via Speculative Decodingcited by 1,615
  5. 2023GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpointscited by 1,311
  6. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,107
  7. 2019Fast Transformer Decoding: One Write-Head is All You Needcited by 700
  8. 2021Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LMcited by 621
  9. 2023OpenChat: Advancing Open-source Language Models with Mixed-Quality Datacited by 250
  10. 2025FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Servingcited by 248
  11. 2023CacheGen: KV Cache Compression and Streaming for Fast Large Language Model Servingcited by 199
  12. 2024DeepSpeed-FastGen: High-throughput Text Generation for LLMs via MII and DeepSpeed-Inferencecited by 106
4 more
  1. 2024Hydragen: High-Throughput LLM Inference with Shared Prefixescited by 71
  2. 2024POD-Attention: Unlocking Full Prefill-Decode Overlap for Faster LLM Inferencecited by 46
  3. 2024BlendServe: Optimizing Offline Inference for Auto-regressive Large Models with Resource-aware Batchingcited by 19
  4. 2024Intelligent Router for LLM Workloads: Improving Performance Through Workload-Aware Load Balancingcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026WISP: Waste- and Interference-Suppressed Distributed Speculative LLM Serving at the Edge via Dynamic Drafting and SLO-Aware Batchingcited by 1
  2. 2026StreamServe: Adaptive Speculative Flows for Low-Latency Disaggregated LLM Servingcited by 0
  3. 2026Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regretcited by 0
  4. 2026Beyond Accuracy and Cost: Latency-Aware LLM Query Routing for Dynamic Workloadscited by 0
  5. 2026FluidPD: In-Place Elasticity for SLO-Aware Prefill-Decode Disaggregated LLM Servingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Flow-Controlled Scheduling for LLM Inference with Provable Stability Guarantees
  2. 2024Efficient LLM Scheduling by Learning to Rank
  3. 2026Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference serving
  4. 2026Taming Request Imbalance: SLO-Aware Scheduling for Disaggregated LLM Inference ↗
  5. 2026SLO-Aware Compute Resource Allocation for Prefill-Decode Disaggregated LLM Inference
  6. 2025Apt-Serve: Adaptive Request Scheduling on Hybrid Cache for Scalable LLM Inference Serving
  7. 2025DOPD: A Dynamic PD-Disaggregation Architecture for Maximizing Goodput in LLM Inference Serving
  8. 2026TokenRouter: Efficient Serving System for Token-Level LLM Routing