LLM Serving Optimization with Variable Prefill and Decode Lengths
read the original abstract
We study offline scheduling for large language model (LLM) serving under a fixed KV-cache memory budget, where requests have heterogeneous prompt (prefill) and response (decode) lengths. Prompt tokens determine initial KV-cache usage, while each generated token further increases memory consumption, creating dynamic memory constraints during autoregressive decoding. Given a backlog of n requests arriving together, the goal is to form mixed prefill and decode batches over time to minimize total end-to-end latency. We show that heterogeneous prompt lengths fundamentally change the scheduling problem: the problem is NP-hard, and standard policies such as first-come-first-served, shortest-output-first, and total-size-based prioritization can have unbounded approximation ratios. We propose Sorted-F, a scheduling algorithm that repeatedly forms feasible batches using an F-metric that balances batch size against downstream decode cost. We prove that Sorted-F achieves a constant-factor approximation guarantee in the offline/backlogged model. We also develop practical implementations, including an exact dynamic program for small instances and scalable local-search and greedy heuristics for larger instances, as well as LP-guided and receding-horizon variants. Experiments on public workloads that combine short conversations and long-document summarization show that F-metric-based scheduling consistently reduces latency relative to standard baselines and remains close to the LP relaxation lower bound for tractable instances.
This paper has not been read by Pith yet.
Forward citations
Cited by 7 Pith papers
-
Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice
SVF scheduling algorithm achieves a competitive ratio of 3 for LLM serving and integrates into vLLM to reduce average and tail latency.
-
Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scale
BalanceRoute reduces data-parallel imbalance in LLM inference via F-score routing and lookahead, yielding higher end-to-end throughput on 144-NPU clusters versus vLLM baselines.
-
Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scale
BalanceRoute uses a piecewise-linear F-score (with optional short lookahead) for sticky request routing in LLM serving, reducing DP imbalance and raising end-to-end throughput versus vLLM baselines on production and A...
-
A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints
A queueing model derives stability conditions for LLM inference services under combined compute and KV cache memory limits, with experimental validation showing typical deviations under 10%.
-
Flow-Controlled Scheduling for LLM Inference with Provable Stability Guarantees
A flow-control framework for LLM inference derives necessary and sufficient stability conditions and experimentally improves throughput, latency, and KV cache stability over common baselines.
-
Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints
The paper develops fluid-guided online scheduling algorithms (WAIT and Nested WAIT) for LLM inference that handle endogenous KV-cache memory growth and improve stability and latency over baselines in simulations.
-
Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics
LLM serving requires mathematical optimization and algorithms with provable guarantees rather than generic heuristics that fail unpredictably on LLM workloads.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.