Asymptotic Optimality of $c\mu$-Rule for LLM Inference Scheduling under Memory Constraint

| Source: arXiv AI

Tags: LLM inference, KV cache, c-mu rule, queueing theory, NVIDIA H800, scheduling

A queueing-theory paper shows a c-mu priority rule, with service rate set by compute, memory bandwidth and KV-cache capacity, is asymptotically optimal for LLM inference scheduling and cuts latency on an H800 serving engine.

Details

Long prompts and outputs in agentic and reasoning workloads make KV-cache memory the bottleneck in LLM serving. The authors model scheduling as a queue where requests with different prompt and output lengths compete for finite KV-cache capacity, and step time depends on prefill compute and KV-cache I/O. A fluid model reduces this to a multiclass single-server queue with effective service rates. That yields a c-mu priority rule they prove minimizes holding cost in the fluid model and, for finite workloads, completion time, while maximizing output-token throughput. A feasible policy converges to the fluid optimum, and on a real serving engine with an NVIDIA H800 it substantially reduces average latency while keeping high throughput.