Cμ priority rule optimizes large language model memory use and speed
Asymptotic Optimality of $cμ$-Rule for LLM Inference Scheduling under Memory Constraint
Artificial Intelligence
Summary
Large language models produce text by processing inputs and generating outputs step-by-step, but this process can be slowed by limited GPU memory used to store intermediate data. The authors look at managing multiple requests competing for this limited memory as a queuing problem and develop a new model that considers both computation and memory limits. They propose a scheduling rule, called the cμ-rule, that decides which requests to prioritize to minimize waiting time and improve throughput. Their approach is proven mathematically optimal in a fluid model and shown experimentally to reduce latency on real hardware.
What this means in practice
- •For cloud ai service operators: Implement scheduling policies that optimize memory use and throughput for serving large language model requests on GPU clusters under tight memory constraints.
- •For high-performance computing teams: Manage competing jobs that require sharing large GPU memory caches to reduce overall completion time and increase token generation rates for sequential workloads.
Authors
Zhenghao Li, Shengbo Wang, Nian Si
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.