← All papers
First page of A Deterministic Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving

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

Ian D'Ambrosio

cs.DS Aug 15, 2026 · v2 cs.LG
The reduction to positive-body chasing, rounding, and the main competitive-ratio theorem are machine-checked in Lean 4 with Mathlib, taking the cited source results as premises.
Dynamic Mixture-of-Experts Serving allocates k replica GPUs among m experts as workloads change. At each round, the online algorithm sees the current workload, chooses integral replica counts, and pays bottleneck service cost plus replica movement. It does not know future workloads. Huang, Lou, and Xiao gave an O(sqrt(log k))-competitive randomized algorithm for this problem. We prove a deterministic O(1)-competitive algorithm. For every number of experts and every k>=1, the algorithm satisfies ALG_det <= 10 C_PB OPT + (5 C_PB + 8) k + 16, where C_PB is the absolute constant from Chasing Positive Bodies at resource augmentation one and covering sparsity two. Consequently, CR_det(k)<=10 C_PB for every k>=1, so CR_det(k)=Theta(1). The multiplicative factor does not depend on the number of experts, replica budget, horizon, or workload values. Thus randomization is not needed for the asymptotic guarantee. The proof has two layers. A finite tangent envelope, summable positive resets, and a nonexpansive balanced projection reduce reciprocal-max service costs to a deterministic exact-budget fractional path. A new deterministic rounding theorem converts every such path to integral allocations with service distortion three and movement bounded by the fractional movement plus 6k. The complete reduction, rounding theorem, causal composition, and quantified main theorem are machine-checked in Lean 4 relative to the positive-body result as the sole scientific source premise. The theorem concerns the allocation model above. It does not include network topology, shared-edge congestion, or routing decisions.

Dynamic Mixture-of-Experts serving allocates k replica GPUs among m experts online. The cost is bottleneck service cost plus replica movement. The best previously known guarantee was an O(sqrt(log k))-competitive randomized algorithm, so it was open whether a constant competitive ratio is achievable.

The reciprocal service-cost epigraph is approximated by a finite tangent envelope that yields positive covering rows of support two. Geometrically shrinking positive resets and a nonexpansive balanced projection reduce the problem to chasing positive bodies. This produces an exact-budget fractional path, which a rounding step then makes integral. The full reduction and main theorem are formalized in Lean 4 with Mathlib, treating the positive-body chasing and rounding results as explicit premises.

The abstract claims a deterministic algorithm with ALG <= 10 C_PB OPT + (5 C_PB + 8)k + 16, giving a constant competitive ratio independent of m, k, and horizon. The body states the bound for a randomized algorithm in expectation, with additive term (5 C_PB + 2)k + 16. The Lean development uses only standard axioms, and the 24 replay tests and artifact hashes were reproduced independently.