A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving
Ian D'Ambrosio
cs.DS
Aug 15, 2026 · v1
cs.LG
TL;DR
The reduction, rounding composition, and quantified main competitive-ratio theorem are machine-checked in Lean 4 with Mathlib, treating cited theorems as formal interfaces.
Abstract
Huang, Lou, and Xiao introduced Dynamic Mixture-of-Experts Serving and gave an O(sqrt(log k))-competitive randomized algorithm for its integral primal problem, where k is the number of replica GPUs beyond the mandatory copy of each expert. Their matching lower barrier applies to an auxiliary dual and leaves the primal order open. We prove that the randomized primal competitive ratio is in fact Theta(1) for arbitrary numbers of experts. The upper bound reduces reciprocal-max service costs to chasing positive bodies with covering row sparsity two. A finite tangent envelope approximates each reciprocal epigraph within a constant factor, summable positive resets convert accumulated service into movement, and a nonexpansive balanced projection removes the positive-body algorithm's resource augmentation. Combining the resulting fractional path with Lazy Threshold Rounding gives E[ALG] <= 10 C_PB OPT + (5 C_PB + 2) k + 16, where C_PB is the absolute constant from Chasing Positive Bodies at resource augmentation one and covering sparsity two. The full reduction, rounding composition, and quantified main theorem are machine-checked in Lean 4 relative to exact formal interfaces for the two cited source theorems. Deterministic rational controls and a fresh independent replay accompany the formal proof.
Problem
Dynamic Mixture-of-Experts serving decides replica GPU allocation online, trading switching cost against bottleneck latency. Prior work gave an O(sqrt(log k))-competitive randomized algorithm for the integral primal problem, leaving the asymptotic primal ratio open.
Approach
The reciprocal service cost r/(1+u) is inner-approximated by a finite positive-polyhedral tangent envelope with constant distortion, giving covering rows of support two. An event/reset construction with geometrically shrinking positive resets reduces the problem to positive-body chasing, and a nonexpansive balanced projection removes resource augmentation. Lazy Threshold Rounding converts the fractional path to an integral allocation. The full reduction, rounding composition, and final constant assembly are formalized in Lean 4.32.2 with Mathlib 4.32.2, treating the two cited source theorems as primitive premises.
Results
The randomized primal competitive ratio is proven to be Theta(1) for arbitrary numbers of experts, with E[ALG] <= 10 C_PB OPT + (5 C_PB + 2) k + 16. The main upper-bound declaration is machine-checked using only the standard axioms, and a fresh independent replay reproduced 24 tests and both artifact hashes.