# Optimal Scheduling Algorithms for LLM Inference: Theory and Practice

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

## Key facts

- Cited by 6 papers in the map (data through 14 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.

## Placed in

- Efficient LLM inference and serving / [Serving systems and request scheduling](https://mlsanity.com/inference/serving-systems-and-request-scheduling/)

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Fast Transformer Decoding: One Write-Head is All You Need](https://mlsanity.com/paper/1911.02150/) (2019)
- [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://mlsanity.com/paper/2104.04473/) (2021)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving](https://mlsanity.com/paper/2501.01005/) (2025)
- [OpenChat: Advancing Open-source Language Models with Mixed-Quality Data](https://mlsanity.com/paper/2309.11235/) (2023)
- [CacheGen: KV Cache Compression and Streaming for Fast Large Language Model Serving](https://mlsanity.com/paper/2310.07240/) (2023)
- [Llumnix: Dynamic Scheduling for Large Language Model Serving](https://mlsanity.com/paper/2406.03243/) (2024)
- [DeepSpeed-FastGen: High-throughput Text Generation for LLMs via MII and DeepSpeed-Inference](https://mlsanity.com/paper/2401.08671/) (2024)
- [Hydragen: High-Throughput LLM Inference with Shared Prefixes](https://mlsanity.com/paper/2402.05099/) (2024)
- [FlashDecoding++: Faster Large Language Model Inference on GPUs](https://mlsanity.com/paper/2311.01282/) (2023)
- [POD-Attention: Unlocking Full Prefill-Decode Overlap for Faster LLM Inference](https://mlsanity.com/paper/2410.18038/) (2024)
- [BlendServe: Optimizing Offline Inference for Auto-regressive Large Models with Resource-aware Batching](https://mlsanity.com/paper/2411.16102/) (2024)
- [Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents](https://mlsanity.com/paper/2504.07347/) (2025)
- [Intelligent Router for LLM Workloads: Improving Performance Through Workload-Aware Load Balancing](https://mlsanity.com/paper/2408.13510/) (2024)

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

- [Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret](https://mlsanity.com/paper/2606.09668/) (2026)
- [WISP: Waste- and Interference-Suppressed Distributed Speculative LLM Serving at the Edge via Dynamic Drafting and SLO-Aware Batching](https://mlsanity.com/paper/2601.11652/) (2026)
- [Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM pools](https://mlsanity.com/paper/2607.18253/) (2026)
- [StreamServe: Adaptive Speculative Flows for Low-Latency Disaggregated LLM Serving](https://mlsanity.com/paper/2604.09562/) (2026)
- [FluidPD: In-Place Elasticity for SLO-Aware Prefill-Decode Disaggregated LLM Serving](https://mlsanity.com/paper/2610.06917/) (2026)
- [Stable Token-level Scheduling for Serverless LLM Inference](https://mlsanity.com/paper/2610.17689/) (2026)

## 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.