A polynomial-time $O(\sqrt{\log k})$-competitive online algorithm, where $k$ is the number of GPUs beyond one per expert, and a matching $\Omega(\sqrt{\log k})$ barrier for the online dual problem underlying the analysis.
Abstract
Mixture-of-Experts (MoE) models route each token to only a few expert networks, distributing the serving load across experts whose popularity shifts over time. A serving system must therefore dynamically decide how many GPUs to assign to each expert, trading off service latency against the cost of reconfiguring the assignment. We introduce a formal model of MoE Serving and initiate a principled study of online and offline algorithms for it. Our main result is a polynomial-time $O(\sqrt{\log k})$-competitive online algorithm, where $k$ is the number of GPUs beyond one per expert. We complement it with a matching $\Omega(\sqrt{\log k})$ barrier for the online dual problem underlying our analysis. In the offline setting, we give a constant-factor approximation, show that MoE Serving is NP-hard, and rule out an FPTAS assuming ETH.
A deterministic O(1)-competitive algorithm that allocates k replica GPUs among m experts as workloads change and is machine-checked in Lean 4 relative to the positive-body result as the sole scientific source premise.
Serving a Mixture-of-Experts (MoE) model pays for expert precision twice: the resident footprint pays for every expert the router can reach, while each batch-one decode step pays only for the experts it selects. These are two different rate functionals over the same per-expert widths, yet published per-expert MoE alloc...
Meng-Qi Guo, Zhe Wei, Yuan Yuan et al.· 0 citations
This work introduces FWP (Fragility-Weighted Perplexity), computed from prompt tokens on a reference-instance prefill and calibrated to candidate-instance degradation, and yields a signed reduced-reward score that is KKT-consistent with the LP optimum under optimal prices and primal-feasible tie allocation.
Mixture-of-experts (MoE) routers typically apply softmax to the router scores and keep the top-K experts, making every token use exactly K experts. Sparsity-inducing probability maps such as sparsemax, alpha-entmax and normmax can adaptively assign exact zeros to selected experts, and therefore appear to offer token-de...
Tomás Brogueira, Marcos V. Treviso, Miguel Couceiro· 0 citations
This work proves that rank logarithmic in $M$ suffices for routing expressivity when the number of active experts is fixed, and is necessary up to precision factors, and introduces MoRE (Mixture of Rank-reduced-routed Experts), which factorizes the router weight matrix at rank r and reduces the routing cost to $O((h +...
The results indicate that over-dispersed routing is a qualitatively distinct pruning regime in which standard assumptions fail, and that recognizing it is a prerequisite for principled expert pruning of load-balanced MoE models.
Berkcan Kapusuzoglu, Connor Pryor, Sangwoo Cho et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
