Standard LLM scheduling policies fail on a basic math problem — and a new paper proves it.
Researchers studying offline scheduling for large language model inference found that common approaches — first-come-first-served, shortest-output-first, and total-size-based prioritization — can perform arbitrarily badly when request lengths vary. The culprit is KV-cache memory: prompt tokens claim a chunk upfront, and every generated token claims more, creating memory pressure that shifts dynamically as a batch runs. The paper shows the general scheduling problem is NP-hard, which means the intuitive heuristics operators rely on today have no worst-case guarantee. The team's answer is Sorted-F, an algorithm that builds batches by balancing how large a batch can be against how expensive its decoding tail will be — and they prove it hits a constant-factor approximation bound.
That proof matters because most LLM infrastructure teams have been tuning serving stacks with benchmarks that flatten request diversity — short conversations and long-document jobs lumped into tidy averages. Real production traffic mixes both, which is exactly where Sorted-F's gains show up in experiments on public workloads. Latency reductions relative to standard baselines are consistent, and results stay close to the LP relaxation lower bound on tractable instances.
The practical implementations range from an exact dynamic program for small batches to greedy and local-search heuristics for scale, plus LP-guided and receding-horizon variants — which suggests the authors are aware this will need to run in real inference servers, not just academic test harnesses. Whether cloud inference providers quietly fold this into their schedulers, or startups use it as a wedge, will be worth watching.