🤖 AI

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

This paper proposes a geometry-aware online scheduling framework featuring the Smallest Volume First (SVF) and 1-bit SVF algorithms, which theoretically improve competitive ratios and practically enhance LLM serving performance by addressing the dynamic 2D memory footprint of Key-Value caches more effectively than traditional time-centric heuristics.

Original authors: Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

Published 2026-06-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a busy coffee shop. This isn't just any coffee shop; it's a high-tech one where every drink you make requires a specific amount of counter space (memory) that grows the longer you spend making it.

In the world of Large Language Models (LLMs), this "counter space" is called the KV Cache. Every time the AI generates a word (token), it needs a little more memory to remember what it just said so it can keep the conversation flowing. If you run out of counter space, the whole shop has to stop.

The Problem: The "Shortest Job First" Mistake

For a long time, computer systems managed these requests using a rule called Shortest Job First (SJF). The logic is simple: "If a customer orders a quick espresso, let them go first because it's fast. If someone orders a complicated 20-minute latte, make them wait."

The paper argues that in the world of AI, this rule is actually broken. Here is why:

The Trap: In a normal shop, a short order takes up space for a short time. But in an AI shop, even a "short" request might need a huge amount of counter space if the customer asks for a long story.
The 2D Reality: The paper says we need to look at two dimensions: Time (how long it takes) and Space (how much memory it eats up as it grows). The old rule only looked at time.
The Result: By prioritizing only "fast" jobs, the system often gets clogged with requests that are fast to start but eat up all the memory, blocking everyone else. It's like letting a customer order a tiny espresso, but they decide to sit at the counter for an hour, blocking the barista from making anything else.

The Solution: "Smallest Volume First" (SVF)

The authors propose a new rule called Smallest Volume First (SVF). Instead of asking, "How fast is this?" they ask, "How much total counter space will this request occupy over its entire life?"

Think of it like packing a moving truck:

Old Way (SJF): You load the smallest boxes first, hoping they fit.
New Way (SVF): You calculate the total "volume" of every item (height × width × depth) and load the items that take up the least total space first.

By doing this, the system clears out requests that are "small" in total memory footprint quickly. This frees up space for bigger requests to start sooner, preventing the whole system from getting stuck.

The "One-Bit" Trick (1-bit SVF)

Predicting exactly how long a conversation will take is hard. It's like trying to guess exactly how many words a customer will say before they stop talking. The paper introduces a clever shortcut called 1-bit SVF.

Instead of trying to predict the exact number of words, the system just asks a simple question: "Is this a short request or a long request?" (Yes/No).

It uses a tiny bit of information (just one "bit") to categorize the request.
Surprisingly, the paper shows that this simple guess is almost as good as the complex prediction. It's like a barista just asking, "Is this a quick coffee or a long drink?" and making decisions based on that simple answer. It saves a lot of brainpower (computing power) while still keeping the line moving smoothly.

What the Paper Proved

The authors didn't just guess this would work; they did the math to prove it:

The Math: They showed that in the worst-case scenarios (like a sudden rush of customers), their new method is guaranteed to be much better than the old "Shortest Job First" method. They tightened the mathematical guarantee from being potentially 48 times worse than perfect to only 5 times worse.
The Test: They tested this on real AI models (Llama-3.1) using a popular system called vLLM.
- Result: The new method made the AI faster for everyone, especially for the slowest requests (reducing "tail latency").
- Efficiency: The "1-bit" version was incredibly lightweight, adding almost zero delay to the system while still performing very well.

Summary

In simple terms, this paper says: Stop judging AI requests just by how fast they finish. Judge them by how much "memory space" they occupy while they are running. By switching to a "Smallest Volume First" strategy, and even using a super-simple "short vs. long" guess, we can make AI chatbots faster, smoother, and less likely to crash under heavy loads.

Technical Summary: Geometry-Aware Online Scheduling for LLM Serving

Problem Statement

The deployment of Large Language Models (LLMs) in interactive scenarios faces a critical bottleneck: the management of the dynamic memory footprint of the Key-Value (KV) cache. Unlike traditional scheduling problems where job size is static, LLM inference exhibits a unique 2D spatio-temporal geometric growth.

Memory-Time Coupling: In autoregressive decoding, execution time is linearly coupled with memory expansion; each generated token increases the KV cache footprint.
Continuous Batching Dynamics: Modern engines (e.g., vLLM) use continuous batching, where the concurrent batch size fluctuates dynamically after every decoding step as requests complete and new ones enter.

Existing scheduling heuristics, primarily Shortest Job First (SJF), are rooted in classical time-centric modeling. They fail to capture the geometric reality of LLM serving. Recent theoretical work [10] has demonstrated that under these specific geometric constraints, SJF yields an unbounded worst-case competitive ratio, creating a fundamental gap between classical scheduling theory and the physical realities of modern LLM inference.

Methodology

The authors propose a Geometry-Aware Online Scheduling framework that shifts the prioritization metric from 1D execution time to 2D memory volume.

Core Algorithm: Smallest Volume First (SVF)

Instead of isolating execution time, SVF evaluates the integral of memory consumption over a request's entire lifecycle. For a request $r_i$ with prompt length $s_i$ and output length $o_i$ , the Volume $v_i$ is defined as:
$v_i = s_i \cdot o_i + \frac{o_i^2 + o_i}{2}$
This formula quantifies the total "memory-time" area occupied by the request. SVF acts as a strictly greedy policy, sorting requests in ascending order of $v_i$ . The implementation is decoupled into two processes: a background predictor that batches requests to query output lengths, and a scheduler that admits the highest-priority (smallest volume) requests into the running batch until KV cache capacity is reached.

Lightweight Variant: 1-bit SVF

To minimize computational overhead, the authors introduce 1-bit SVF. This variant replaces exact length prediction with a binary classifier that categorizes requests as "short" ( $m=0$ ) or "long" ( $m=1$ ).

It assigns a global proxy length $O_m$ to each class.
The proxy volume is calculated as $\hat{v}_i = s_i \cdot O_m + \frac{O_m^2 + O_m}{2}$ .
This design extracts only a single bit of information while preserving the core spatio-temporal scheduling guarantees.

Theoretical Contributions

The paper provides a rigorous mathematical foundation, moving beyond empirical trial-and-error to formal guarantees:

Tightened Worst-Case Bounds (Burst Arrivals):
- For SVF with known output lengths under burst arrival models, the authors prove a worst-case competitive ratio (CR) of CR $\le$ 5. This significantly tightens the previous bound of CR $\le$ 48 found in prior literature [10].
- The proof utilizes a novel "macroscopic certificate" methodology, showing that every blocked step implies an active memory mass $> M/2$ , directly aligning the algorithm's waiting time with the lower bound of the optimal offline schedule.
- For 1-bit SVF, the competitive ratio is bounded by $O(T)$ , where $T$ is the maximum model length, proving that even with minimal information, the system remains stable under extreme loads.
Stochastic Bounds (Poisson Arrivals):
- Under Poisson arrival processes, the paper derives expected competitive ratios.
- SVF achieves $E[CR] \le 1 + \frac{4}{(1-\mu)(1-\rho)}$ , where $\mu$ relates to the geometric distribution of lengths and $\rho$ is system utilization.
- 1-bit SVF's performance degradation is shown to be governed by a "volumetric distortion penalty" $\epsilon$ , which decays exponentially with the classification threshold, ensuring long-term stability.

Experimental Results

The approach was implemented as a plug-and-play layer within vLLM and evaluated on Llama-3.1-8B and Llama-3.1-70B models using LMSYS-Chat and LongBench workloads.

Latency Reduction: SVF consistently achieved the lowest average and tail (P95) latencies across all benchmarks, outperforming FCFS, SJF, and even Oracle-SJF (which has perfect future knowledge of lengths) in memory-intensive scenarios (LongBench).
Throughput: SVF maintained higher throughput than SJF. 1-bit SVF achieved competitive throughput and latency, often surpassing SJF in tail latency metrics.
Overhead: The prediction overhead was negligible. The full-length predictor consumed at most 0.06% of end-to-end latency, while the 1-bit classifier consumed $\le$ 0.01%.
Fairness: Contrary to classical greedy heuristics that starve long jobs, the geometry-aware greediness of SVF rapidly releases bounded KV cache memory, breaking global head-of-line blocking and improving fairness for larger requests.

Significance and Claims

The paper claims to establish a theoretically sound and empirically proven approach for resolving memory-constrained scheduling in modern LLM deployments. Its primary significance lies in:

Paradigm Shift: It moves the field from legacy 1D time-centric heuristics to 2D geometry-aware prioritization, addressing the fundamental mismatch between classical scheduling theory and LLM inference mechanics.
Theoretical Advancement: By tightening the competitive ratio from 48 to 5 and introducing a novel proof methodology, it provides universal structural guarantees that hold across arbitrary and adversarial workload distributions.
Practical Viability: The "plug-and-play" nature of the scheduler, combined with the extreme efficiency of the 1-bit variant, demonstrates that rigorous mathematical optimization can be seamlessly integrated into high-performance inference engines without prohibitive overhead.

The authors conclude that this geometry-aware approach not only optimizes system efficiency but also offers implications for sustainable AI deployment by reducing the computational resources and carbon footprint required for large-scale inference.