Mixture-of-Experts Serving

2026/07/20 by Zhiyi Huang, Qinpei Lou, Tao Xiao
#cs.DS

paper · pdf

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(√(log k))-competitive online algorithm, where k is the number of GPUs beyond one per expert. We complement it with a matching Ω(√(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.

Related

• MoE++: Accelerating Mixture-of-Experts Methods with Zero-Computation Experts
• Mixture of Experts with Mixture of Precisions for Tuning Quality of Service
• From Score Distributions to Balance: Plug-and-Play Mixture-of-Experts Routing
• Optimizing Mixture-of-Experts Inference Time Combining Model Deployment and Communication Scheduling
• Mixture of Diverse Size Experts