Must the competitive ratio for randomized Dynamic MoE Serving grow with the extra-replica budget, or can it remain constant?
Dynamic Mixture-of-Experts serving has two costs to manage. A busy expert with too few replicas becomes a bottleneck; moving replicas to meet the next workload also costs something. The policy sees the current workload but not the future. How much worse must it be than an offline planner that knows the whole sequence?
Under the fixed-sequence convention, the answer is a constant factor for every number of experts and every extra-replica budget.
The extra-replica budget
There are m experts, each with one mandatory GPU copy, plus k additional replica GPUs to place. At each round, a workload is revealed and the policy distributes those k replicas using only what it has seen so far. It pays the worst workload-per-copy ratio, counting one mandatory copy plus assigned extras, and a reconfiguration cost equal to the total coordinate-wise change in replica counts. k counts only the extra replicas, not the total GPU fleet.
The bound that grew with every GPU
In 2026, Huang, Lou, and Xiao introduced this problem and gave a randomized competitive upper bound of O(√(log k)). Their matching-looking lower barrier applies to an auxiliary dual maximization problem, not the original question; weak duality does not transfer it back. Whether the original primal ratio grows with k or remains constant stayed open.
What we found
The paper proves an explicit upper bound and its asymptotic consequence:
CPB is an absolute constant from the Chasing Positive Bodies theorem of Bhattacharya, Buchbinder, Levin, and Saranurak. The factor 10·CPB does not depend on m, k, or the horizon. The result settles the asymptotic order but does not determine the best numerical constant or claim that the algorithm is 1-competitive.
How the constant emerges
Two properties of the service cost make the reduction possible. First, halving an allocation coordinate increases its reciprocal cost by at most two:
Second, service is the maximum of one univariate function per expert. Each epigraph constraint therefore involves only one allocation coordinate and the shared height, giving covering-row sparsity d=2.
The reciprocal service cost has infinitely many tangent constraints. The proof replaces them with a finite integer grid that preserves at least three-quarters of the value. Summable positive resets convert service into movement without leaving the source theorem's scope. The positive-body chaser may temporarily use twice the replica budget; a nonexpansive balanced projection restores the exact budget, with the inequality above limiting the service increase to a factor two. Lazy Threshold Rounding then makes the fractional path integral online using one shared random seed.
An earlier reduction failed adversarial review because it needed infinitely many tangents and an invalid zero reset. The released proof repairs both. Source-fidelity audits then found that one imported interface allowed a constraint outside its theorem and the other hid a per-step guarantee inside a summed consequence. Both interfaces were repaired before the final replay.
How the result was checked
Every new Dynamic MoE bridge and the explicit constant upper theorem are checked in Lean 4 against exact interfaces for the two cited source theorems. An independent referee reran the public package from a clean extraction: all packaged files matched their manifest, cited sources matched pinned hashes, 24 theorem and exact-control tests passed, both evidence files regenerated byte for byte, and the paper recompiled cleanly.
A separate control packet includes 7,056 movement checks, 2,184 service checks, and a deliberately wrong movement normalization that the suite rejects. A later independent referee checked the two exposition changes above and confirmed that the theorem, proof, constants, and all thirteen numbered equations remained unchanged.
Beyond, the research system operated by Nth Research Collective, assisted with literature retrieval, hypothesis generation, formalization, exact controls, and adversarial review. Research systems are not authors; the author made the final scientific judgments and accepts full responsibility.
What this does and doesn't establish
The result settles asymptotic order, not the best numerical constant or a 1-competitive guarantee. The deterministic integral ratio remains open. The theorem covers an oblivious adversary fixing the workload sequence in advance, not one reacting to the algorithm's random choices. The Lean development proves the new reduction relative to exact source-level interfaces; it does not reformalize either cited paper.
We make no claim about measured latency, throughput, GPU cost, or energy in a production deployment. Huang, Lou, and Xiao's dual lower barrier remains valid; it does not determine the primal order. No earlier constant randomized integral primal bound for arbitrary experts and replica budgets was found in searches current to August 11, 2026. This is a public preprint, not yet peer-reviewed.
Read it, run it
Archived record (manuscript and certificates): doi.org/10.5281/zenodo.21918990
Reproduce the theorem: download the v2 reproducibility package 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.