# Online Scheduling for LLM Inference with KV Cache Constraints

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 32 of its 71 references that are in the map.
- First posted on arXiv 10 Feb 2025.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [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)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model](https://mlsanity.com/paper/2405.04434/) (2024)
- [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)
- [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)
- [SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills](https://mlsanity.com/paper/2308.16369/) (2023)
- [A Study of Generative Large Language Model for Medical Research and Healthcare](https://mlsanity.com/paper/2305.13523/) (2023)
- [GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM](https://mlsanity.com/paper/2403.05527/) (2024)
- [Fast Distributed Inference Serving for Large Language Models](https://mlsanity.com/paper/2305.05920/) (2023)
- [Inference without Interference: Disaggregate LLM Inference for Mixed Downstream Workloads](https://mlsanity.com/paper/2401.11181/) (2024)
- [Vidur: A Large-Scale Simulation Framework For LLM Inference](https://mlsanity.com/paper/2405.05465/) (2024)
- [Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline](https://mlsanity.com/paper/2305.13144/) (2023)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [S3: Increasing GPU Utilization during Generative Inference for Higher Throughput](https://mlsanity.com/paper/2306.06000/) (2023)
- [Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction](https://mlsanity.com/paper/2404.08509/) (2024)
- [Don't Stop Me Now: Embedding Based Scheduling for LLMs](https://mlsanity.com/paper/2410.01035/) (2024)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [On Optimal Caching and Model Multiplexing for Large Model Inference](https://mlsanity.com/paper/2306.02003/) (2023)
- [Enabling Efficient Batch Serving for LMaaS via Generation Length Prediction](https://mlsanity.com/paper/2406.04785/) (2024)
- [EcoServe: Designing Carbon-Aware AI Inference Systems](https://mlsanity.com/paper/2502.05043/) (2025)
- [Distortion-Oblivious Algorithms for Minimizing Flow Time](https://mlsanity.com/paper/2109.08424/) (2021)

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

- [Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints](https://mlsanity.com/paper/2504.11320/) (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)
- [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)
- [SAGA: Workflow-Atomic Scheduling for AI Agent Inference on GPU Clusters](https://mlsanity.com/paper/2605.00528/) (2026)
- [MoE-SpAc: Efficient MoE Inference Based on Speculative Activation Utility in Heterogeneous Edge Scenarios](https://mlsanity.com/paper/2603.09983/) (2026)
- [Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective](https://mlsanity.com/paper/2601.18999/) (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)
- [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)
- [Cluster Workload Allocation: Semantic Soft Affinity Using Natural Language Processing](https://mlsanity.com/paper/2601.09282/) (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)
- [Unified AI Gateway: A Framework for Joint Model Routing and KV Cache Management](https://mlsanity.com/paper/2609.06940/) (2026)
- [Sample Count Is Not Enough: Candidate-Generation Strategy Shapes the Energy and Performance of LLM Test-Time Scaling](https://mlsanity.com/paper/2609.19499/) (2026)

## Abstract (arXiv)

Large Language Model (LLM) inference, where a trained model generates text one word at a time in response to user prompts, is a computationally intensive process requiring efficient scheduling to optimize latency and resource utilization. A key challenge in LLM inference is the management of the Key-Value (KV) cache, which reduces redundant computations but introduces memory constraints. In this work, we model LLM inference with KV cache constraints theoretically and propose a novel batching and scheduling algorithm that minimizes inference latency while effectively managing the KV cache's memory. More specifically, we make the following contributions. First, to evaluate the performance of online algorithms for scheduling in LLM inference, we introduce a hindsight optimal benchmark, formulated as an integer program that computes the minimum total inference latency under full future information. Second, we prove that no deterministic online algorithm can achieve a constant competitive ratio when the arrival process is arbitrary. Third, motivated by the computational intractability of solving the integer program at scale, we propose a polynomial-time online scheduling algorithm and show that under certain conditions it can achieve a constant competitive ratio. We also demonstrate our algorithm's strong empirical performance by comparing it to the hindsight optimal in a synthetic dataset. Finally, we conduct empirical evaluations on a real-world public LLM inference dataset, simulating the Llama2-70B model on A100 GPUs, and show that our algorithm significantly outperforms the benchmark algorithms. Overall, our results offer a path toward more sustainable and cost-effective LLM deployment.