mlsanityData to 14 Oct 2026

Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice

arXiv 2606.22327 ↗First posted 21 Jun 2026cs.AIcited by 0

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

Abstract (arXiv)

The rapid growth of interactive Large Language Model serving has made efficient management of dynamic Key-Value cache footprints increasingly important for inference performance. Modern inference systems overwhelmingly rely on time-centric scheduling heuristics, such as Shortest Job First. However, their classical guarantees are rooted in traditional scheduling modeling, failing to capture the highly dynamic, 2D spatio-temporal geometric growth specific to LLM inference mechanisms. To resolve this, we propose the geometry-aware online scheduling by introducing the Smallest Volume First (SVF) algorithm and its highly efficient variant, 1-bit SVF. Via a novel volume-certificate proof, we establish a worst-case approximation ratio for SVF that approaches 3 in the high-concurrency regime of LLM serving, substantially improving upon the prior best constant of 48. Building upon this core breakthrough, we complete a comprehensive theoretical taxonomy analyzing our algorithms across different traffic scenarios and information availability. Practically, we seamlessly integrate our approach as a plug-and-play layer in vLLM. Extensive evaluations on Llama-3.1 models demonstrate comprehensive performance gains: SVF delivers strong reductions in both average and tail latency, while 1-bit SVF, with merely a single bit of information, achieves competitive throughput and latency. This work establishes a theoretically sound and empirically proven approach for resolving memory-constrained scheduling in modern LLM deployments. To facilitate future research, our code is available at https://github.com/Li-Beverly-Kong/Geometry-Aware-Online-Scheduling.git.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Serving systems and request scheduling, one of 12 directions in Efficient LLM inference and serving. Builds on 28 of its 38 references that are in the map. First posted on arXiv 21 Jun 2026.

Builds on

28 of 38 references.

Closest ancestors · 9

Same direction, newest first

  1. 2026Predicting LLM Output Length via Entropy-Guided Representations12 Feb
  2. 2025LLM Serving Optimization with Variable Prefill and Decode Lengths8 Aug
  3. 2025ServeGen: Workload Characterization and Generation of Large Language Model Serving in Production15 May
  4. 2025Taming the Titans: A Survey of Efficient LLM Inference Serving28 Apr
  5. 2024Efficient LLM Scheduling by Learning to Rank28 Aug
  6. 2024Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction12 Apr
  7. 2024BurstGPT: A Real-world Workload Dataset to Optimize LLM Serving Systems31 Jan
  8. 2023Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline22 May
  9. 2023Fast Distributed Inference Serving for Large Language Models10 May

Other references · 19

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2024The Llama 3 Herd of Modelscited by 14,715
  4. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
  5. 2019Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelismcited by 1,868
  6. 2023LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Datasetcited by 461
  7. 2024Inference without Interference: Disaggregate LLM Inference for Mixed Downstream Workloadscited by 121
  8. 2019Well-Read Students Learn Better: On the Importance of Pre-training Compact Modelscited by 120
  9. 2024DynamoLLM: Designing LLM Inference Clusters for Performance and Energy Efficiencycited by 112
  10. 2023S3: Increasing GPU Utilization during Generative Inference for Higher Throughputcited by 81
  11. 2024When Search Engine Services meet Large Language Models: Visions and Challengescited by 59
  12. 2024LLM Inference Serving: Survey of Recent Advances and Opportunitiescited by 46
7 more
  1. 2024Don't Stop Me Now: Embedding Based Scheduling for LLMscited by 35
  2. 2023AI-assisted Code Authoring at Scale: Fine-tuning, deploying, and mixed methods evaluationcited by 21
  3. 2024Enabling Efficient Batch Serving for LMaaS via Generation Length Predictioncited by 20
  4. 2025Online Scheduling for LLM Inference with KV Cache Constraintscited by 19
  5. 2025Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraintscited by 19
  6. 2025Adaptively Robust LLM Inference Optimization under Prediction Uncertaintycited by 10
  7. 2025Optimizing LLM Inference Throughput via Memory-aware and SLA-constrained Dynamic Batchingcited by 8

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Beyond Prediction: Tail-Aware Scheduling for LLM Inference
  2. 2026Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics
  3. 2025Apt-Serve: Adaptive Request Scheduling on Hybrid Cache for Scalable LLM Inference Serving
  4. 2026SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity
  5. 2025Optimal Scheduling Algorithms for LLM Inference: Theory and Practice
  6. 2026Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference serving
  7. 2026PRISM: Fast Online LLM Serving via Scheduling-Memory Co-design
  8. 2026Comparative Characterization of KV Cache Management Strategies for LLM Inference