mlsanityData to 7 Oct 2026

Online Scheduling for LLM Inference with KV Cache Constraints

arXiv 2502.07115 ↗First posted 10 Feb 2025cs.LG cs.AI math.OCcited by 17

On the map: Efficient LLM inference and serving → KV cache optimization

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.

Key facts. Cited by 17 papers in the map (data through 7 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.

Builds on

32 of 71 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM8 Mar
  2. 2023Efficient Memory Management for Large Language Model Serving with PagedAttention12 Sep
  3. 2023S3: Increasing GPU Utilization during Generative Inference for Higher Throughput9 Jun

Other references · 29

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2020Scaling Laws for Neural Language Modelscited by 6,411
  4. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  5. 2022Emergent Abilities of Large Language Modelscited by 2,483
  6. 2024DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Modelcited by 1,093
  7. 2024DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Servingcited by 595
  8. 2024KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantizationcited by 571
  9. 2023FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPUcited by 567
  10. 2023Splitwise: Efficient generative LLM inference using phase splittingcited by 536
  11. 2022Efficiently Scaling Transformer Inferencecited by 529
  12. 2024Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Servecited by 507
17 more
  1. 2023LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Datasetcited by 449
  2. 2023SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefillscited by 187
  3. 2023A Study of Generative Large Language Model for Medical Research and Healthcarecited by 160
  4. 2023Fast Distributed Inference Serving for Large Language Modelscited by 143
  5. 2024Inference without Interference: Disaggregate LLM Inference for Mixed Downstream Workloadscited by 120
  6. 2024Vidur: A Large-Scale Simulation Framework For LLM Inferencecited by 115
  7. 2023Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipelinecited by 86
  8. 2024Efficient LLM Scheduling by Learning to Rankcited by 83
  9. 2024Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Predictioncited by 64
  10. 2024Don't Stop Me Now: Embedding Based Scheduling for LLMscited by 34
  11. 2021Flow Time Scheduling with Uncertain Processing Timecited by 29
  12. 2023On Optimal Caching and Model Multiplexing for Large Model Inferencecited by 20
  13. 2024Enabling Efficient Batch Serving for LMaaS via Generation Length Predictioncited by 20
  14. 2025EcoServe: Designing Carbon-Aware AI Inference Systemscited by 18
  15. 2021Distortion-Oblivious Algorithms for Minimizing Flow Timecited by 15
  16. 2019Non-clairvoyant Precedence Constrained Schedulingcited by 3
  17. 2021Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job familiescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 13.

17 papers.

Sort:

By area:

  1. 2025Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraintscited by 16
  2. 2025Auto-Formulating Dynamic Programming Problems with Large Language Modelscited by 15
  3. 2025Adaptively Robust LLM Inference Optimization under Prediction Uncertaintycited by 8
  4. 2025LLM Serving Optimization with Variable Prefill and Decode Lengthscited by 7
  5. 2026Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answerscited by 7
  6. 2026MoE-SpAc: Efficient MoE Inference Based on Speculative Activation Utility in Heterogeneous Edge Scenarioscited by 5
  7. 2026SAGA: Workflow-Atomic Scheduling for AI Agent Inference on GPU Clusterscited by 5
  8. 2026Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspectivecited by 3
  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. 2026Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristicscited by 1
  12. 2026Cluster Workload Allocation: Semantic Soft Affinity Using Natural Language Processingcited by 0
5 more
  1. 2026Flow-Controlled Scheduling for LLM Inference with Provable Stability Guaranteescited by 0
  2. 2026Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scalecited by 0
  3. 2026Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practicecited by 0
  4. 2026Unified AI Gateway: A Framework for Joint Model Routing and KV Cache Managementcited by 0
  5. 2026Sample Count Is Not Enough: Candidate-Generation Strategy Shapes the Energy and Performance of LLM Test-Time Scalingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026KV Cache Optimization Strategies for Scalable and Efficient LLM Inference
  2. 2024A Survey on Large Language Model Acceleration based on KV Cache Management
  3. 2026Comparative Characterization of KV Cache Management Strategies for LLM Inference
  4. 2025KV Cache Compression for Inference Efficiency in LLMs: A Review
  5. 2024LLM Inference Unveiled: Survey and Roofline Model Insights
  6. 2024XKV: Personalized KV Cache Memory Reduction for Long-Context LLM Inference
  7. 2024Efficient LLM Inference with Kcache
  8. 2026The KV Cache Working Set: Online Capacity Planning for LLM Inference Systems