A Deterministic Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving
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_...
| Authors | Ian D'Ambrosio |
|---|---|
| Primary category | cs.DS |
| Published | 15 August 2026 |
| Last updated at source | 29 August 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.