# Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 66 references that are in the map.
- First posted on arXiv 15 Apr 2025.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Energy and Policy Considerations for Deep Learning in NLP](https://mlsanity.com/paper/1906.02243/) (2019)
- [DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model](https://mlsanity.com/paper/2405.04434/) (2024)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU](https://mlsanity.com/paper/2303.06865/) (2023)
- [Carbon Emissions and Large Neural Network Training](https://mlsanity.com/paper/2104.10350/) (2021)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset](https://mlsanity.com/paper/2309.11998/) (2023)
- [DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale](https://mlsanity.com/paper/2207.00032/) (2022)
- [Sustainable AI: Environmental Implications, Challenges and Opportunities](https://mlsanity.com/paper/2111.00364/) (2021)
- [SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills](https://mlsanity.com/paper/2308.16369/) (2023)
- [GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM](https://mlsanity.com/paper/2403.05527/) (2024)
- [Vidur: A Large-Scale Simulation Framework For LLM Inference](https://mlsanity.com/paper/2405.05465/) (2024)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [Compute and Energy Consumption Trends in Deep Learning Inference](https://mlsanity.com/paper/2109.05472/) (2021)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Online Scheduling for LLM Inference with KV Cache Constraints](https://mlsanity.com/paper/2502.07115/) (2025)
- [Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents](https://mlsanity.com/paper/2504.07347/) (2025)

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

- [Auto-Formulating Dynamic Programming Problems with Large Language Models](https://mlsanity.com/paper/2507.11737/) (2025)
- [The Markovian Thinker: Architecture-Agnostic Linear Scaling of Reasoning](https://mlsanity.com/paper/2510.06557/) (2025)
- [Adaptively Robust LLM Inference Optimization under Prediction Uncertainty](https://mlsanity.com/paper/2508.14544/) (2025)
- [Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answers](https://mlsanity.com/paper/2602.05395/) (2026)
- [LLM Serving Optimization with Variable Prefill and Decode Lengths](https://mlsanity.com/paper/2508.06133/) (2025)
- [Assured autonomy: How operations research powers and orchestrates generative AI systems](https://mlsanity.com/paper/2512.23978/) (2025)
- [OptiRepair: Closed-Loop Diagnosis and Repair of Supply Chain Optimization Models with LLM Agents](https://mlsanity.com/paper/2602.19439/) (2026)
- [SuperInfer: SLO-Aware Rotary Scheduling and Memory Management for LLM Inference on Superchips](https://mlsanity.com/paper/2601.20309/) (2026)
- [A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints](https://mlsanity.com/paper/2605.04595/) (2026)
- [You Only Need Your Transformer 25% of the Time: Meaning-First Execution for Eliminating Unnecessary Inference](https://mlsanity.com/paper/2601.00847/) (2025)
- [Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics](https://mlsanity.com/paper/2605.01280/) (2026)
- [Online Pandora's Box for Contextual LLM Cascading](https://mlsanity.com/paper/2606.07392/) (2026)
- [The Value of Information in Resource-Constrained Pricing](https://mlsanity.com/paper/2603.24974/) (2026)
- [Flow-Controlled Scheduling for LLM Inference with Provable Stability Guarantees](https://mlsanity.com/paper/2604.11001/) (2026)
- [Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scale](https://mlsanity.com/paper/2605.06113/) (2026)
- [Service-Induced Congestion in Memory-Constrained LLM Serving](https://mlsanity.com/paper/2606.15555/) (2026)
- [Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice](https://mlsanity.com/paper/2606.22327/) (2026)
- [LLM Inference Under Bursty Workload Distribution: Modifying the WAIT Algorithm](https://mlsanity.com/paper/2608.06135/) (2026)
- [Analytical Power-Aware Provisioning for Prefill-Decode Disaggregated AI Inference](https://mlsanity.com/paper/2609.24639/) (2026)

## Abstract (arXiv)

Large language models now serve millions of users daily, with providers incurring costs exceeding 700,000 per day. Each request requires token-by-token inference, making GPU scheduling central to latency, capacity, and cost. The difficulty is endogenous memory growth: generated tokens expand the Key-Value (KV) cache, and overflow can evict in-progress requests and waste prior computation. We formulate inference as a multi-stage online scheduling problem with endogenous memory growth, linear iteration times, and GPU-resident KV-cache constraints. We introduce a fluid model that characterizes equilibrium batch composition, memory requirement, and stability region. Guided by the fluid model, we design WAIT (Waiting for Accumulated Inference Threshold), a threshold-based admission rule for known output lengths, and Nested WAIT, which extends the rule to unknown output lengths by regulating how requests advance across decode-stage segments. Both algorithms approximate the fluid benchmark asymptotically under the stated memory conditions. Nested WAIT uses an additional safety buffer of moderate scale to hedge against memory-overflow-induced evictions under unknown output lengths. In Vidur simulations configured for Llama-2-7B on an A100 GPU, with supplemental real-GPU validation reported in the appendix, the policies enlarge the empirically observed stable operating range relative to widely used baseline algorithms and reduce latency especially in near-overloaded and overloaded regimes.