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

The article presents a new geometry-aware online scheduling method for Large Language Model (LLM) serving, introducing the Smallest Volume First (SVF) algorithm and its efficient variant, 1-bit SVF. This approach significantly improves the management of dynamic memory footprints in inference engines, achieving a competitive ratio reduction from 48 to 5 for known output lengths while demonstrating reduced average and tail latency in extensive evaluations on Llama-3.1 models. This work is crucial for practitioners as it provides a theoretically grounded and empirically validated solution for optimizing memory-constrained scheduling in LLM deployments, with the implementation available as a plug-and-play layer in vLLM.