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

• URL: http://arxiv.org/abs/2606.22327v2
• Date: Wed, 24 Jun 2026 14:02:53 GMT
• Title: Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice
• Abstract summary: We introduce geometry-aware online scheduling by introducing Smallest Volume First (SVF) algorithm and its highly efficient variant, 1-bit SVF.<n>SVF delivers strong reductions in both average and tail latency, while 1-bit SVF, with merely a single bit information, achieves competitive throughput and latency.<n>This work establishes a theoretically sound and empirically proven approach for resolving memory-constrained scheduling in modern Large Language Model deployments.
• Score: 12.809268527016599
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The explosive demand for interactive Large Language Model serving has highlighted the management of the Key-Value cache's dynamic memory footprint as a critical area for performance optimization in inference engines. Modern inference systems overwhelmingly rely on time-centric scheduling heuristics, such as Shortest Job First. However, their theoretical optimality is rooted in traditional schedule 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. Theoretically, we provide a rigorous mathematical foundation for our approach. Via a novel volume-certificate proof, we sharpen SVF's worst-case competitive ratio from the prior best of 48 towards \textbf{3} in the high-concurrency regime of LLM serving. 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 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/Aurora-Kl/Geometry-Aware-Online-Scheduling.git.

Related papers

• Empirical Recipes for Efficient and Compact Vision-Language Models [54.92440500651415]
  Vision-language models (VLMs) in resource-constrained settings demand low latency and high throughput.<n>We conduct an empirical end-to-end efficiency analysis and systematically profile inference to identify the dominant bottlenecks.<n>We develop optimization recipes tailored to compact VLMs that substantially reduce latency while preserving accuracy.
  arXiv  Detail & Related papers  (2026-03-17T17:17:40Z)
• Beyond Test-Time Training: Learning to Reason via Hardware-Efficient Optimal Control [86.63490309209378]
  We formulate reasoning as optimal control and introduce the Test-Time Control layer, which performs finite-horizon LQR planning over latent states at inference time.<n>We demonstrate that embedding optimal control as an architectural layer provides an effective and scalable mechanism for reasoning beyond test-time training.
  arXiv  Detail & Related papers  (2026-03-10T05:42:13Z)
• $\ abla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasoner is an iterative generation framework that integrates differentiable optimization over token logits into the decoding loop.<n>$nabla$-Reasoner achieves over 20% accuracy improvement on a challenging mathematical reasoning benchmark.
  arXiv  Detail & Related papers  (2026-03-05T08:42:54Z)
• Prism: Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models [96.0074341403456]
  Inference-time compute has re-emerged as a practical way to improve LLM reasoning.<n>Most test-time scaling (TTS) algorithms rely on autoregressive decoding.<n>We propose Prism, an efficient TTS framework for dLLMs.
  arXiv  Detail & Related papers  (2026-02-02T09:14:51Z)
• TimeLens: Rethinking Video Temporal Grounding with Multimodal LLMs [81.78017865436816]
  We present TimeLens, a systematic investigation into building MLLMs with strong video temporal grounding ability.<n>We first expose critical quality issues in existing VTG benchmarks and introduce TimeLens-Bench, comprising meticulously re-annotated versions of three popular benchmarks.<n>We also address noisy training data through an automated re-annotation pipeline, yielding TimeLens-100K, a large-scale, high-quality training dataset.
  arXiv  Detail & Related papers  (2025-12-16T18:59:58Z)
• Scaling up Multi-Turn Off-Policy RL and Multi-Agent Tree Search for LLM Step-Provers [16.135928990655422]
  This paper introduces textttBFS-Prover-V2, a system designed to address the dual scaling problem.<n>The first is a novel multi-turn off-policy RL framework for continually improving the performance of LLM step-prover at training time.<n>The second innovation is a planner-enhanced multi-agent search architecture that scales reasoning capabilities at inference time.
  arXiv  Detail & Related papers  (2025-09-08T09:54:18Z)
• Optimal Scheduling Algorithms for LLM Inference: Theory and Practice [6.043830060363904]
  This paper develops a theoretical framework that models routing and scheduling in Large Language Model inference systems.<n>We identify two key design principles-optimal tiling and dynamic resource allocation-that are essential for achieving high throughput.<n>We show that the Resource-Aware Dynamic (RAD) scheduler achieves throughput optimality under mild conditions.
  arXiv  Detail & Related papers  (2025-08-01T18:12:21Z)
• Pangu Embedded: An Efficient Dual-system LLM Reasoner with Metacognition [95.54406667705999]
  Pangu Embedded is an efficient Large Language Model (LLM) reasoner developed on Ascend Neural Processing Units (NPUs)<n>It addresses the significant computational costs and inference latency challenges prevalent in existing reasoning-optimized LLMs.<n>It delivers rapid responses and state-of-the-art reasoning quality within a single, unified model architecture.
  arXiv  Detail & Related papers  (2025-05-28T14:03:02Z)
• Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints [14.341123057506827]
  Large Language Models (LLMs) are indispensable in today's applications, but their inference procedure demands significant computational resources.<n>This paper formulates LLM inference optimization as a multi-stage online scheduling problem.<n>We develop a fluid dynamics approximation to provide a tractable benchmark that guides algorithm design.
  arXiv  Detail & Related papers  (2025-04-15T16:00:21Z)
• Online Scheduling for LLM Inference with KV Cache Constraints [22.133592174540052]
  Large Language Model (LLM) inference is an intensive process requiring efficient scheduling to optimize latency and resource utilization.<n>We propose a novel and theoretically scheduling algorithm that minimizes inference latency while effectively managing the KV cache's memory.
  arXiv  Detail & Related papers  (2025-02-10T23:11:44Z)
• ALISE: Accelerating Large Language Model Serving with Speculative Scheduling [7.367068885621016]
  Large Language Models (LLMs) represent a revolutionary advancement in the contemporary landscape of artificial general intelligence (AGI) In this paper, we propose a new efficient LLM inference serving framework, named ALISE. We show that ALISE improves the throughput of inference serving by up to 1.8x and 2.1x under the same latency constraint on the Alpaca and ShareGPT datasets, respectively.
  arXiv  Detail & Related papers  (2024-10-31T00:58:11Z)
• EE-LLM: Large-Scale Training and Inference of Early-Exit Large Language Models with 3D Parallelism [70.07661254213181]
  We present EE-LLM, a framework for large-scale training and inference of early-exit large language models (LLMs) Built upon Megatron-LM, EE-LLM implements a variety of algorithmic innovations and performance optimizations tailored to early exiting. Our analytical and empirical study shows that EE-LLM achieves great training efficiency with negligible computational overhead.
  arXiv  Detail & Related papers  (2023-12-08T09:31:50Z)
• Scalable Optimal Margin Distribution Machine [50.281535710689795]
  Optimal margin Distribution Machine (ODM) is a newly proposed statistical learning framework rooting in the novel margin theory. This paper proposes a scalable ODM, which can achieve nearly ten times speedup compared to the original ODM training method.
  arXiv  Detail & Related papers  (2023-05-08T16:34:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.