A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving

Abstract

Huang, Lou, and Xiao introduced Dynamic Mixture-of-Experts Serving and gave an O(sqrt(log k))-competitive randomized algorithm for the integral primal, leaving the primal order open. This preprint proves that the randomized primal competitive ratio is Theta(1) for arbitrary numbers of experts and replica budgets under the fixed-sequence (oblivious-adversary) convention. The proof reduces reciprocal-max service costs to chasing positive bodies with covering row sparsity two, removes resource augmentation by balanced projection, and applies Lazy Threshold Rounding. The resulting bound is E[ALG] <= 10 C_PB OPT + (5 C_PB + 2)k + 16. The new reductions and theorem composition are machine-checked in Lean 4 relative to exact interfaces for the two cited source theorems. The accompanying reproducibility archive contains the paper source, pinned-source bootstrap, Lean files, deterministic controls, tests, and manifests. A clean extraction reproduced 24 tests, both canonical evidence hashes, and the seven-page paper. Version v2 incorporates external technical feedback by removing the dedicated factor-one lower-bound section and explicitly stating the capacity-scaling and sparsity properties used by the reduction. The theorem, proof, constants, and formal evidence are unchanged. Scope: fixed workload sequences. The deterministic integral ratio and adaptive-adversary case remain open.