Mixture-of-Experts Serving
For system designers deploying MoE models, this work provides the first principled analysis of dynamic GPU allocation to experts, balancing latency and reconfiguration cost.
The paper introduces a formal model for serving Mixture-of-Experts models and provides a polynomial-time online algorithm with O(√log k) competitive ratio, along with a matching lower bound, and offline results including NP-hardness and a constant-factor approximation.
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 $Ω(\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.