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

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

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

## 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, 28 of 28)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset](https://mlsanity.com/paper/2309.11998/) (2023)
- [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)
- [Well-Read Students Learn Better: On the Importance of Pre-training Compact Models](https://mlsanity.com/paper/1908.08962/) (2019)
- [DynamoLLM: Designing LLM Inference Clusters for Performance and Energy Efficiency](https://mlsanity.com/paper/2408.00741/) (2024)
- [BurstGPT: A Real-world Workload Dataset to Optimize LLM Serving Systems](https://mlsanity.com/paper/2401.17644/) (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)
- [When Search Engine Services meet Large Language Models: Visions and Challenges](https://mlsanity.com/paper/2407.00128/) (2024)
- [LLM Inference Serving: Survey of Recent Advances and Opportunities](https://mlsanity.com/paper/2407.12391/) (2024)
- [Don't Stop Me Now: Embedding Based Scheduling for LLMs](https://mlsanity.com/paper/2410.01035/) (2024)
- [ServeGen: Workload Characterization and Generation of Large Language Model Serving in Production](https://mlsanity.com/paper/2505.09999/) (2025)
- [AI-assisted Code Authoring at Scale: Fine-tuning, deploying, and mixed methods evaluation](https://mlsanity.com/paper/2305.12050/) (2023)
- [Enabling Efficient Batch Serving for LMaaS via Generation Length Prediction](https://mlsanity.com/paper/2406.04785/) (2024)
- [Online Scheduling for LLM Inference with KV Cache Constraints](https://mlsanity.com/paper/2502.07115/) (2025)
- [Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints](https://mlsanity.com/paper/2504.11320/) (2025)
- [Taming the Titans: A Survey of Efficient LLM Inference Serving](https://mlsanity.com/paper/2504.19720/) (2025)
- [Adaptively Robust LLM Inference Optimization under Prediction Uncertainty](https://mlsanity.com/paper/2508.14544/) (2025)
- [Predicting LLM Output Length via Entropy-Guided Representations](https://mlsanity.com/paper/2602.11812/) (2026)
- [Optimizing LLM Inference Throughput via Memory-aware and SLA-constrained Dynamic Batching](https://mlsanity.com/paper/2503.05248/) (2025)
- [LLM Serving Optimization with Variable Prefill and Decode Lengths](https://mlsanity.com/paper/2508.06133/) (2025)

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