Mixture-of-Experts Serving
2026-07-20 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to efficiently assign GPUs to different expert networks in Mixture-of-Experts (MoE) models, where only a few experts handle each token and their popularity changes over time. They create a formal model to understand this GPU assignment problem and develop an online algorithm that performs well compared to the best possible strategy. They also prove that their algorithm's performance is close to the theoretical limit. For the offline case, where all data is known in advance, they show it's a hard problem but provide an approximation solution. Their work balances the trade-off between fast responses and the cost of adjusting GPU assignments.
Mixture-of-ExpertsGPU assignmentonline algorithmsoffline algorithmsservice latencyapproximation algorithmsNP-hardnesscompetitive analysisETH (Exponential Time Hypothesis)resource allocation
Authors
Zhiyi Huang, Qinpei Lou, Tao Xiao
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 $Ω(\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.