GEOMETRY-AWARE ONLINE SCHEDULING FOR LLM SERVING: FROM THEORETICAL BOUND TO SYSTEM PRACTICE

Modern LLM inference engines often rely on time-centric scheduling heuristics like Shortest Job First (SJF). However, these heuristics fail to account for the unique 2D spatio-temporal growth of the Key-Value (KV) cache during autoregressive decoding. The authors investigate whether a geometry-aware approach, which explicitly models the integral of memory consumption over time, can provide more robust and efficient scheduling for high-concurrency LLM serving.

The authors propose the Smallest Volume First (SVF) algorithm and a lightweight 1-bit variant. Unlike time-only heuristics, SVF prioritizes requests by their total predicted KV cache volume—the area under the memory-time curve. They provide a rigorous mathematical foundation for this approach, utilizing a novel volume-certificate proof to derive competitive ratio bounds. To validate these findings, they integrated the SVF scheduler as a plug-and-play layer within the vLLM inference engine and evaluated its performance using Llama-3.1 models.

The study demonstrates that SVF significantly outperforms traditional scheduling heuristics. Theoretically, the authors sharpen the worst-case competitive ratio from 48 down to 3 in high-concurrency regimes. Empirically, SVF provides substantial reductions in both average and tail latency. Furthermore, the 1-bit SVF variant, which requires only a binary classification of request length, achieves competitive throughput and latency with minimal computational overhead, proving that even coarse-grained geometric information is sufficient for effective scheduling.

This work bridges the gap between classical scheduling theory and the physical realities of modern LLM deployment. By shifting the focus from simple time-based heuristics to geometry-aware metrics, the authors provide a principled, theoretically sound framework that is both robust to adversarial traffic bursts and easy to implement in existing production systems like vLLM.