LLM INFERENCE · QUEUEING · SCHEDULING

Asymptotic Optimality of cμ-Rule for LLM Inference Scheduling under Memory Constraint

Led by Zhenghao Li @ HKUST

We formulate a queueing model of LLM inference in which requests compete for finite KV-cache memory. Its fluid limit yields a cμ priority rule that minimizes cumulative holding cost, where the effective service rate μ is jointly determined by computational speed, memory bandwidth, and memory capacity; on a real serving engine, practical cμ policies substantially reduce average latency while keeping throughput high.

Read the paper Explore the traces
KV-cache constraintFluid limitcμ priority rulePrefill & decodeReal production traces

The idea

Price each request in memory-adjusted GPU time, then sort by cμ

μ · effective service rate

ΔStep time = apfnpfprefill compute +akvnkvKV-cache I/O +bfixed
1/μper request = apfsprefill compute +(akv + b/M) m̃memory held
s, o
Prompt and output tokens
m̃ = so + o(o−1)/2
KV-cache tokens held, summed over every step the request runs (without chunked prefill)
apf, akv, b, M
Prefill computational time per prompt token, KV-cache I/O time per token, fixed time per step, and memory size

Fitted on an H800: apf = 2.26×10−5 s/token, akv = 4.11×10−8 s/token, b = 7.79 ms.

Policies

Cumulative cQ

Loading experiment data…
s
Final cumulative cQ · cost·s

Prompt tokensOutput tokensCountStatus