Fully online KV-cache scheduling has a linear deterministic competitive ratio

In fully online LLM inference with growing KV-cache memory, can every deterministic scheduler beat a linear worst-case gap from a hindsight optimum?

No. For the model introduced by Jaillet and coauthors, we prove that the best deterministic competitive ratio grows linearly with the number of requests.

The mechanism is simple. After the scheduler commits to a request that will fill memory, release many one-token requests whose prompts each occupy half the GPU. None can fit beside it. They wait; hindsight chooses the better order.

KV-cache scheduling in ninety seconds

Continuous batching lets several LLM requests generate a token in the same GPU round. Each carries its prompt and generated tokens, so its KV-cache footprint grows until completion.

Prompt and output lengths are revealed at arrival, but future requests remain unknown. Once started, a request advances every round and cannot pause or restart. The objective is total end-to-end latency. The benchmark knows the whole instance but obeys the same rules.

The open gap

Jaillet and coauthors proved a deterministic lower bound of Ω(√n). A conservative serial policy gives the elementary upper bound n. Before this result, no matching general bound was known under the same objective and action rules.

Ω(√n) ≤ R_det(n) ≤ n

What we found

Let R_det(n,M) be the best deterministic ratio for exactly n requests at memory M, and let R_det(n) take the worst case over memory. For every n ≥ 2, the paper proves

(n − 1) / 12 ≤ R_det(n) ≤ n R_det(n) = Θ(n)

The lower bound fixes the explicit memory M = 2(n − 1)n before quantifying over every deterministic causal scheduler, matching the definition of R_det(n).

Fig. 1: The long request and one new short request each need more than half the GPU memory, so they cannot run together. The online scheduler starts the long request before seeing the shorts. Hindsight knows they are coming and serves them first in the pictured case. If they arrive late, hindsight runs the long request first.

Why the commitment trap is linear

Write k = n − 1. Release one long request with prompt 1 and output M − 1. Observe its start round b. At b + M/2, release k short requests, each with prompt M/2 and one output token.

At that moment, the active long request uses at least M/2 + 2 memory. A new short would use M/2 + 1. Together they need more than M, so no short can overlap the long request. Every short waits until the long request finishes and incurs latency at least M/2. The online cost is therefore at least kM/2.

The hindsight schedule chooses one of two feasible orders. If the short requests arrive early enough, it runs them first and then starts the long request. If they arrive late, it runs the long request at time zero and serves the shorts afterward. Either comparator costs at most a constant times M. Their ratio is at least k/12.

For the upper bound, order requests by arrival and label, then place them serially. Each waits for at most the total output work, which every feasible schedule must perform. This gives ratio at most n for every memory.

Why the verification is strong

The model, memory rule, causality, comparator branches, and quantifier order are checked in Lean 4.32.2. A finite evaluator computes bounded offline optima. Its negative controls reject static memory accounting, distinguish total completion time from total end-to-end latency, and expose how kill-and-restart changes the witness.

A clean extraction fetched both pinned sources, built the Lean theorem, passed all 30 tests, regenerated the control file byte for byte, and recompiled the paper. An independent referee returned PASS across all release gates.

Beyond, the research system operated by Nth Research Collective, assisted with retrieval, computation, formalization, and adversarial review. Research systems are not authors; the author accepts full responsibility.

What this does and doesn't establish

The result settles the worst-over-memory order. It does not determine the tight function R_det(n,M) for every fixed memory. The hard family uses prompts of size M/2, so bounded-prompt and bounded-size-spread regimes may behave differently. The constants are not optimized.

The theorem is deterministic and does not settle the randomized ratio. It makes no claim about measured latency, throughput, cost, or energy in a production system.

No earlier Θ(n) theorem was found for this exact model in searches current to August 11, 2026. The preprint is not yet peer-reviewed.

Read it, run it

Archived record (manuscript and reproducibility package): doi.org/10.5281/zenodo.21896436

Reproduce the theorem: download the verified archive and run python3 verify_all.py from the extracted directory.

If you know of an earlier equivalent result, please send it to research@nthresearch.org.

Nth Research Collective

Vote on what Beyond attacks next →