cmu-Rule Scheduling for LLM Inference: A Fluid-Optimal Priority Rule Under a Hard KV-Cache Budget, Effective Service Rates From Compute and Memory I/O, and Lower Latency at Full Throughput

INFERENCE SYSTEMS

Queueing theory finally meets the KV cache: when GPU memory is the bottleneck, the right priority rule prices each request by cost per unit of effective service - and that service rate is set jointly by compute speed, memory bandwidth, and capacity.

By Ossam Hashim

KEY FINDINGS

A new queueing-theoretic study (arXiv Nov 3; HKUST, USC) models LLM inference as it actually behaves: requests arrive stochastically with heterogeneous prompt and output lengths, run prefill then autoregressive decode, and compete for a finite KV-cache capacity while each step's duration depends on both prefill computation and KV-cache I/O.
Unlike classical queues, service capacity here is jointly determined by computation, memory access, and memory occupancy: how many requests can run concurrently, and how long each step takes, both shrink as KV caches fill GPU memory.
The authors build a fluid model (token processing rate and arrival rate scale together while memory capacity stays fixed) that reduces the system to a multiclass single-server queue with effective service rates capturing all three constraints - and derive a cmu priority rule on top of it.
They prove the 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; a constructed feasible policy for the real finite system provably converges to the fluid optimum.
The model is calibrated, not hand-waved: on an NVIDIA H800, measured batch step time varies approximately linearly with both KV-cache I/O volume and prompt tokens processed, with fitted per-token coefficients. On a real serving engine, the priority rule substantially reduces average latency while maintaining high throughput against existing scheduling policies (authors' reported result).
The stakes: Deloitte estimates inference will be roughly two-thirds of total AI compute in 2026, up from one-third in 2023 - scheduling efficiency is now a first-order cost lever, and this blog's llm-d analysis covered the control-plane side of the same problem.

When Memory Becomes the Queue

Classical queueing assumes a server whose capacity is fixed and whose job sizes are known. LLM serving breaks both assumptions. A request's work splits into a compute-heavy prefill and a decode loop whose every step reads the KV cache accumulated so far; the cache grows until the request completes. The number of requests that fit in memory at once is a hard constraint, and the time each step takes inflates with the I/O volume those resident caches impose. Priority decisions made as if service were memoryless - first-come-first-served, or shortest-job-first on prompt length - price jobs by the wrong clock.

The Fluid Reduction

The analysis picks a regime matched to the bottleneck: let token processing rate and arrival rate scale proportionally while total memory capacity stays fixed. In that limit the system collapses to a multiclass single-server queue whose effective service rates fold in computational speed, memory bandwidth, and the capacity constraint itself. That reduction is what makes the classical cmu rule - serve the class with the highest holding cost times effective service rate - available again, now with a mu that means something physical on a GPU. The proofs then run in two directions: the cmu rule is optimal for the fluid system (holding cost, plus completion time and full-run throughput for finite workloads), and a concrete scheduling policy built for the prelimit system converges to that fluid optimum as scale grows.

From Paper to Engine

The bridge to practice is calibration. By measuring mixed batches on an H800, the authors find batch step time approximately linear in both KV-cache I/O volume and prompt tokens processed, and fit the coefficients that turn the abstract effective rates into numbers a scheduler can compute online. Implemented on a real serving engine, the resulting priority rule substantially reduces average latency while holding throughput high relative to existing policies, in the authors' experiments. The contribution is not a new scheduler heuristic; it is a proof that the classic rule survives contact with memory-bound inference, once the service rate is defined honestly.

Assumptions and limitations

The worked example isolates the priority logic of the classical cmu rule; it has no memory capacity constraint, no two-phase workloads, and unit service - the paper's contribution is precisely the effective-rate construction this toy omits. Optimality results hold in the fluid limit and for the paper's model class; finite systems get convergence guarantees, not exact optimality. The H800 latency and throughput outcomes are the authors' reported experiments on one GPU type and one serving engine; the step-time linearity fit is empirical and hardware-specific. The Deloitte inference-share estimate is cited as the paper presents it. How the rule interacts with prefix caching, chunked prefill, or disaggregated serving is outside the paper's scope.

Worked Example: Priority by Price Per Unit Service

The cmu rule in miniature: six jobs arrive over five time units, each with a service length and a per-unit-time holding cost. A preemptive single server runs either first-come-first-served or cmu priority (highest cost divided by service length first). The meter sums the holding costs of all unfinished jobs at every unit of time. One fixed case first, then the average over two hundred random job sets - the rule's edge survives both.

import random
random.seed(7)
base = [(0, 8, 1), (0, 2, 5),
        (1, 6, 2), (2, 1, 9),
        (3, 5, 3), (4, 4, 4)]
def pick(av, sc, policy):
    if policy != "cmu":
        return av[0]
    bm = av[0]
    for i in av:
        if sc[i] > sc[bm]:
            bm = i
    return bm
def run(jobs, policy):
    sc = [c / s for _, s, c in jobs]
    rem = [s for _, s, _ in jobs]
    done = [False] * len(jobs)
    t = 0
    cost = 0
    while not all(done):
        av = []
        for i in range(len(jobs)):
            a = jobs[i][0]
            if a > t or done[i]:
                continue
            av.append(i)
        if av:
            i = pick(av, sc, policy)
            rem[i] -= 1
            if rem[i] == 0:
                done[i] = True
        for i in range(len(jobs)):
            if not done[i]:
                cost += jobs[i][2]
        t += 1
    return cost
of = run(base, "fcfs")
oc = run(base, "cmu")
print("one case fcfs:", of)
print("one case cmu:", oc)
tf = 0
tc = 0
for _ in range(200):
    jobs = []
    for k in range(6):
        jobs.append((k // 2,
            random.randint(1, 8),
            random.randint(1, 9)))
    tf += run(jobs, "fcfs")
    tc += run(jobs, "cmu")
af = tf / 200
ac = tc / 200
print("avg fcfs:", round(af, 1))
print("avg cmu:", round(ac, 1))

Sources & Provenance

Asymptotic Optimality of cmu-Rule for LLM Inference Scheduling under Memory Constraint (Li, Wang, Si, 3 Nov 2026) - arXiv abstract
Full paper (HTML), including the H800 step-time calibration and convergence proofs - arXiv full text
Prior GlobalTechDigest coverage of inference control planes - the llm-d v1.0 analysis

All theoretical and experimental claims are attributed to the preprint as published. Sources accessed 5 November 2026. This analysis is independent editorial content for GlobalTechDigest.

GlobalTechDigest

Search This Blog