Research map / Large language models / Reasoning and chain of thought

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

NeurIPS 2026 · Large language models › Reasoning and chain of thought · approach: Efficient LLM serving · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Smallest Volume First (SVF) and 1-bit SVF, geometry-aware online schedulers for LLM KV-cache memory-constrained serving, with a volume-based worst-case bound approaching 3 and vLLM evaluation on Llama-3.1 models.

Problem

Shortest-Job-First-style time-centric scheduling ignores the 2D spatio-temporal KV-cache growth of LLM requests, and prior theory gives weak or unbounded approximation ratios for it under memory constraints.

Approach

Prioritize requests by their total KV-cache volume (prompt length times output length plus the quadratic growth term) instead of time, prove a volume-certificate worst-case bound of 1+2/(1-alpha) (approaching 3), and show a 1-bit length classifier with proxy lengths retains the guarantee up to an O(T) factor.

Key results

• SVF attains the lowest average per-token latency across burst and Poisson settings; e.g., on Llama-3.1-8B LongBench burst, SVF average latency 70.02 s/tok vs SJF 106.16 and FCFS 125.89.
• Theoretical worst-case ratio for SVF under burst arrivals is 1+2/(1-alpha), which tends to 3 as alpha goes to 0, improving the prior constant of 48.
• Scheduling-policy overhead stays below 0.04% of end-to-end time in all tested settings.

Surprising findings

• Oracle-SJF yields worse average latency than non-omniscient SVF on LongBench, suggesting time-centric metrics are misaligned with LLM memory dynamics.
• 1-bit SVF with a single classification bit achieves the best non-oracle P95 and throughput on the real-world BurstGPT trace.

Limitations

• Theory assumes output lengths are known in the idealized analysis and uses non-preemptive execution with unified token/memory units.
• Experiments are limited to a single worker node; multi-GPU cluster scheduling is left to future work.
• Stochastic bounds rely on a geometric output-length approximation of a bounded length distribution.

Experimental setup

Datasets: LMSYS-Chat LongBench BurstGPT

Benchmarks: LMSYS-Chat LongBench BurstGPT

Metrics: average per-token latency P95 per-token latency token throughput scheduling overhead

Baselines: FCFS SJF Oracle SJF Oracle SVF

Builds on: vLLM Shortest Job First memory-constrained LLM scheduling model

Closest papers by meaning

• Beyond Prediction: Tail-Aware Scheduling for LLM Inference (ICML 2026 · similarity 0.92)
• Efficient LLM Scheduling by Learning to Rank (NeurIPS 2024 · similarity 0.89)
• Fast Inference for Augmented Large Language Models (NeurIPS 2025 · similarity 0.89)
• A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints (ICML 2026 · similarity 0.88)
• MAPS: Memory-Aware Predictive Scheduling Framework for Large Language Model Serving (ICML 2026 · similarity 0.88)
• OServe: Accelerating LLM Serving via Spatial-Temporal Workload Orchestration (ICML 2026 · similarity 0.88)