Asymptotic Optimality of cμ-Rule for LLM Inference Scheduling under Memory Constraint
Abstract
Large language model (LLM) inference, the process by which a pre-trained model receives an input prompt and generates output tokens sequentially, has become increasingly important with the widespread deployment of LLM-based applications. As inference workloads continue to scale, GPU memory has emerged as a critical bottleneck: the long input prompts and generation sequences common in agentic and reasoning workloads lead to substantial key-value (KV) cache usage. In this paper, we study the resulting online scheduling problem from a queueing perspective. Requests arrive stochastically with heterogeneous prompt and output lengths, undergo prefill and autoregressive decode, and compete for a finite KV-cache capacity. Unlike classical queueing models, the duration of a processing step depends on both prefill computation and KV-cache I/O, so service capacity is jointly determined by computation, memory access, and memory occupancy. We develop a fluid model that reduces the system to a multiclass single-server queue with effective service rates capturing computation, memory access, and memory capacity. This fluid analysis yields a cμ priority rule, where the effective service rate μ is jointly determined by computational speed, memory bandwidth, and memory capacity. We prove that this rule minimizes cumulative holding cost in the fluid model and, for a finite workload, also minimizes completion time and maximizes full-run output-token throughput. We then construct a feasible scheduling policy for the original finite system and prove that its scaled dynamics converge to the optimal fluid policy. Finally, experiments on a real LLM serving engine using an NVIDIA H800 show that practical implementations of the proposed priority rule substantially reduce average latency while maintaining high throughput relative to existing scheduling policies.
Related
- CP-WSP: A Declarative CP-SAT Framework for Configurable Multi-Constraint Workforce Scheduling
- On the Information Bottleneck for Ergodic Finite-State Markov Chains: Stationary Approximation and Asymptotic Optimality
- Translate, then decide: asymptotic optimality of latent-space control in bistable systems
- Kriging Beyond Gaussianity: Fixed-Domain Asymptotic Optimality
- Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
BibTeX
@misc{li2026asymptotic,
title = {{Asymptotic Optimality of $cμ$-Rule for LLM Inference Scheduling under Memory Constraint}},
author = {Zhenghao Li and Shengbo Wang and Nian Si},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04807},
eprint = {2611.04807},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04807},
}
RIS
TY - UNPB
TI - Asymptotic Optimality of cμ-Rule for LLM Inference Scheduling under Memory Constraint
AU - Zhenghao Li
AU - Shengbo Wang
AU - Nian Si
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04807
UR - https://arxiv.org/abs/2611.04807
AB - Large language model (LLM) inference, the process by which a pre-trained model receives an input prompt and generates output tokens sequentially, has become increasingly important with the widespread deployment of LLM-based applications. As inference workloads continue to scale, GPU memory has emerged as a critical bottleneck: the long input prompts and generation sequences common in agentic and reasoning workloads lead to substantial key-value (KV) cache usage. In this paper, we study the resulting online scheduling problem from a queueing perspective. Requests arrive stochastically with heterogeneous prompt and output lengths, undergo prefill and autoregressive decode, and compete for a finite KV-cache capacity. Unlike classical queueing models, the duration of a processing step depends on both prefill computation and KV-cache I/O, so service capacity is jointly determined by computation, memory access, and memory occupancy. We develop a fluid model that reduces the system to a multiclass single-server queue with effective service rates capturing computation, memory access, and memory capacity. This fluid analysis yields a cμ priority rule, where the effective service rate μ is jointly determined by computational speed, memory bandwidth, and memory capacity. We prove that this rule minimizes cumulative holding cost in the fluid model and, for a finite workload, also minimizes completion time and maximizes full-run output-token throughput. We then construct a feasible scheduling policy for the original finite system and prove that its scaled dynamics converge to the optimal fluid policy. Finally, experiments on a real LLM serving engine using an NVIDIA H800 show that practical implementations of the proposed priority rule substantially reduce average latency while maintaining high throughput relative to existing scheduling policies.
ER -