When does shortest-job-first stop winning in an LLM scheduler?

Shortest-job-first is the folk wisdom of scheduling, and for LLM serving it's seductive: if you knew a request would emit 12 tokens versus 2,000, you'd obviously serve the short ones first. Real schedulers can't know that, output length is unknown until you generate it. So I built schedlab-rs, a deterministic discrete-event simulator of a vLLM-V1-style scheduler and paged-KV manager in Rust, to answer two questions honestly: how much does shortest-remaining-work help once you can only predict length badly, and is 'SRPT wins' even a real conclusion or just an artifact of the cost model you assumed for the GPU?

First finding: prediction error barely dents it. Across 1,620 configurations, a predicted-shortest-work policy that only ever sees a noisy length estimate recovers about 97% of a perfect oracle's SLO goodput, mean regret 0.012 versus 0.358 for FCFS, and it stays robust even as I crank prediction noise to lognormal sigma 1.0. The intuition: SRPT's value is mostly in not head-of-line-blocking a 2,000-token generation that starves everything behind it. You don't need an accurate estimate for that; you just need to not get the ordering catastrophically wrong, and even noisy predictions clear that bar.

Second finding, the one a single-equation simulator would hide: whether SRPT wins depends on the cost model you believed. I ship three structurally different cost families (context-free linear, a context-aware memory-bandwidth model, and a piecewise model with a utilization knee) and report every conclusion across all of them. Of 45 (workload, load) scenarios, the winning policy is the same under all three cost models in 29, a conclusion you can lean on, but it flips depending on the cost model in 16. If I'd shipped only the linear model, like most toy simulators, I'd have confidently reported the wrong answer in a third of the regimes.

The design decision that makes the experiment trustworthy is a hard boundary: a policy only ranks requests; the mechanism owns KV admission, chunked prefill, and recompute preemption. And the true output length is a private field, deployable policies receive a view that structurally cannot carry it, enforced by Rust's type system plus a property test. Only an oracle baseline sees the truth, as an upper bound. Without that, 'SRPT wins' is just the scheduler cheating by peeking at the future.

To check this isn't an artifact of synthetic workloads, I re-ran the whole study on a real Azure LLM inference trace, 19,366 production requests with ~1,150-token prompts, 4.5x heavier than my synthetic default. The headline held: predicted-SRPT regret 0.016 versus the oracle (FCFS 0.176), still ~98% of the oracle's goodput, and the cost-model dependence persisted in exactly the same signature, the conditional cells clustered where prediction error meets the load knee. Same story, real arrivals.

I'm deliberately not claiming this holds on a real GPU, because I haven't earned that claim yet, the cost models are plausible, not measured. So v1 makes the narrow, defensible claim (here's a faithful mechanism sim, and here's exactly where conclusions are robust to cost-model assumptions) and the calibration harness that closes the loop against real vLLM ships wired but hardware-gated, not faked. The conditional cells are the ones worth spending GPU hours on. That's the whole point: match the strength of the claim to the evidence, and label the rest.