Mixture-of-Experts Serving: A Comprehensive Summary

Summary (Overview)

• New formal model: Introduces the Dynamic and Static MoE Serving problems, where a serving system must dynamically allocate GPUs to experts in a Mixture-of-Experts language model, balancing latency cost against reconfiguration overhead.
• Online algorithm: Presents a polynomial-time $O(\sqrt{\log k})$-competitive online algorithm for Dynamic MoE Serving, where $k = n - m$ is the number of extra GPUs beyond one per expert.
• Matching lower bound: Proves an $\Omega(\sqrt{\log k})$ barrier for the online dual problem, showing the competitive ratio is tight for the primal-dual analysis framework.
• Offline results: Gives a polynomial-time constant-factor approximation for Dynamic MoE Serving, a 2-approximation for the Static variant with an integrality gap of $2 - 1/m$, and proves NP-hardness with no FPTAS under ETH.
• Technical contributions: Combines online primal-dual methods with Fenchel duality and KL-divergence regularization, exploiting smoothness of the latency function to improve the competitive ratio from $\log k$ to $\sqrt{\log k}$.

---

Introduction and Theoretical Foundation

Background

Dense language models scale by increasing parameters per token, tying computation to capacity. Mixture-of-Experts (MoE) models break this tie by maintaining multiple expert networks but routing each token to only a few experts. This architecture underlies prominent models including DeepSeek-V3, Mixtral, and Gemini 3 Pro. For instance, DeepSeek-V3 activates only 37 billion of its 671 billion parameters per token.

The MoE Serving Problem

Consider $m$ experts deployed on $n > m$ GPUs. At each step $t$, the system observes the workload $r_t = (r_{t,i})_{i \in [m]}$ routed to each expert and decides how many GPUs to assign to each. The objective minimizes the sum of two costs:

1. Latency cost: The time for all experts to finish their workloads:

$$f_t(x_t) = \max_{i \in [m]} \frac{r_{t,i}}{1 + x_{t,i}}$$

where $x_{t,i} = c_{t,i} - 1$ is the number of extra GPUs assigned to expert $i$ (beyond the mandatory one), subject to $\sum_{i \in [m]} x_{t,i} = k = n - m$.

2. Reconfiguration cost: The $L_1$ distance between consecutive configurations:

$$\sum_{i \in [m]} |x_{t-1,i} - x_{t,i}|$$

The total objective over horizon $[T]$ is:

$$\sum_{t \in [T]} \left(\max_{i \in [m]} \frac{r_{t,i}}{1 + x_{t,i}} + \sum_{i \in [m]} |x_{t-1,i} - x_{t,i}|\right)$$

Key Theoretical Properties

The latency function $f_t$ satisfies three crucial properties (Lemma 3.3):

1. Conjugate Pair: For any $\gamma_t \in -\partial f_t(x_t)$: $f_t(x_t) = \langle \gamma_t, x_t + \mathbf{1}\rangle$

2. Smoothness: For any $\theta \geq 1$, if $x_{t,i} + 1 \leq \theta(x'_{t,i} + 1)$ for all $i$, then:

$$f_t(x'_t) \leq \theta f_t(x_t)$$

(Doubling GPUs at best halves the cost.)

3. Sublinearity of conjugate: For any $\theta \in (0,1]$:

$$\hat{f}_t(\theta\gamma_t) \geq \sqrt{\theta}\,\hat{f}_t(\gamma_t)$$

where $\hat{f}_t(\gamma_t) = \inf_{x_t \geq 0}(f_t(x_t) + \langle x_t, \gamma_t\rangle)$ is the offset Fenchel conjugate.

---

Methodology

Convex Program Relaxation

The dynamic problem is relaxed to a convex program (PRIMAL):

$$\text{minimize} \quad \sum_{t \in [T]} f_t(x_t) + \sum_{t \in [T]} \sum_{i \in [m]} y_{t,i}$$ $$\text{subject to} \quad \sum_{i \in [m]} x_{t,i} \leq k, \quad y_{t,i} \geq x_{t,i} - x_{t-1,i}, \quad x_{t,i}, y_{t,i} \geq 0$$

With the offset Fenchel dual (DUAL):

$$\text{maximize} \quad \sum_{t} \hat{f}_t(\gamma_t) - \sum_{t} k\alpha_t$$ $$\text{subject to} \quad \gamma_{t,i} + \beta_{t+1,i} - \beta_{t,i} \leq \alpha_t, \quad 0 \leq \beta_{t,i} \leq 1, \quad \gamma_{t,i} \geq 0, \quad \alpha_t \geq 0$$

Weak duality gives $\text{DUAL}^\star \leq \text{PRIMAL}^\star + k$.

Regularized Greedy Algorithm (Online)

At each step $t$, select:

$$x_t = \underset{x \in \mathbb{R}_{\geq 0}^m: \sum_i x_i = k}{\arg\min} \left(f_t(x) + D_{KL}(x + \mathbf{1} \| x_{t-1} + \mathbf{1})\right)$$

where the KL divergence is:

$$D_{KL}(u\|v) = \sum_{i \in [m]} \left(u_i \ln \frac{u_i}{v_i} - u_i + v_i\right)$$

The regularization parameter is $\eta = \max\{1, \ln(k+1)\}$, chosen to optimize the competitive ratio. The dual variables are scaled by $1/\eta$ to restore dual feasibility:

$$\alpha_t = \frac{1}{\eta}\alpha'_t, \quad \beta_{t,i} = -\frac{1}{\eta}\ln\frac{x_{t-1,i} + 1}{k+1}, \quad \gamma_t = \frac{1}{\eta}\gamma'_t$$

Lazy Threshold Rounding

To convert fractional solutions to integral ones, the paper uses a polynomial-time rounding scheme:

1. Sample thresholds $\theta_i \in [0,1)$ independently and uniformly for each expert $i$.
2. Compute lower bounds $\ell_{t,i} = \max\{0, \lfloor x_{t,i} - \theta_i\rfloor\}$.
3. Choose $\bar{x}_t$ satisfying $\ell_{t,i} \leq \bar{x}_{t,i} \leq \max\{\ell_{t,i}, \bar{x}_{t-1,i}\}$ with $\sum_i \bar{x}_{t,i} = k$.

Static Model Rounding

For the static problem, the algorithm solves the convex relaxation, rounds down ($\bar{x}_i = \lfloor x^\star_i\rfloor$), and allocates the remaining GPUs arbitrarily.

---

Empirical Validation / Results

Online Results (Theorem 4.1)

The main results for Dynamic MoE Serving:

1. Polynomial-time $O(\sqrt{\log k})$-competitive online algorithm
2. Polynomial-time O(1)-approximation algorithm (offline)

The competitive ratio derivation proceeds as follows:

• Regularized Greedy ensures reconfiguration cost is bounded by latency cost: $\sum_i y_{t,i} \leq f_t(x_t)$ (Lemma 4.3).
• The dual objective satisfies: $\text{DUAL} \geq \frac{1}{2\sqrt{\eta}}\text{PRIMAL} - m$.
• Combining with weak duality: $\text{PRIMAL} \leq 2\sqrt{\eta} \cdot (\text{OPT} + m + k)$.
• With $\eta = \max\{1, \ln(k+1)\}$, the competitive ratio is $O(\sqrt{\log k})$.

The rounding preserves both costs up to constant factors (Lemma 4.4):

1. $f_t(\bar{x}_t) \leq 3 f_t(x_t)$ (latency cost)
2. $\mathbb{E}[\|\bar{x}_t - \bar{x}_{t-1}\|_1] \leq \|x_t - x_{t-1}\|_1$ (reconfiguration cost)

Online Dual Hardness (Theorem 5.1)

No online algorithm for the dual problem achieves competitive ratio better than $\frac{1}{32}\sqrt{\ln k}$.

The proof constructs a single-phase instance where only one expert receives workload $r_{t,q} = 1$ for $\tau$ steps. The key gadget functions simplify to:

$$\hat{f}_t(\gamma_t) = \begin{cases} 2\sqrt{\gamma_{t,q}} - \gamma_{t,q}, & \gamma_{t,q} \in [0,1] \\ 1, & \gamma_{t,q} \geq 1 \end{cases}$$

The stopping time $\tau$ is the first step where $D_\tau \leq 16\sqrt{\tau/\ln k}$, which is guaranteed to exist (Lemma 5.2). The offline strategy spreads the β-budget evenly: $\gamma_{t,q} = 1/\tau$, achieving dual value at least $\sqrt{\tau}$. Repeating over $R$ phases with cyclic expert requests yields the $\sqrt{\ln k}/32$ lower bound.

Static Model Results

The integrality gap instance uses $m$ experts, $n = 2m - 1$ GPUs, $T = 1$ step with uniform workload $r_{1,i} = 1$. The fractional optimum is $m/(2m-1)$ while integral optimum is 1.

Hardness reduction: From Densest k-Subgraph (DkS), constructing experts as vertices, $n = m + k$ GPUs, and one time step per edge with workload $r_{e,i} = 2$ for endpoints and 1 otherwise. The objective becomes $\text{ALG}(S) = 2|E| - |E(S)|$, exactly equivalent to maximizing induced edges.

---

Theoretical and Practical Implications

Theoretical Contributions

1. New problem formulation: Provides the first formal theoretical model for MoE serving, capturing the fundamental trade-off between latency and reconfiguration costs.

2. Improved competitive ratio: The $O(\sqrt{\log k})$ ratio improves on the standard $\log k$ achieved by naive regularized greedy approaches, exploiting the specific structure (smoothness) of the latency cost function.

3. Tight dual barrier: The matching $\Omega(\sqrt{\log k})$ lower bound for the dual problem shows the analysis framework is tight, though the primal gap remains open.

4. Offline complexity: Establishes that the static problem is NP-hard with no FPTAS under ETH, while providing near-optimal approximation algorithms.

Practical Implications

• DeepSeek-V3 deployment context: The paper directly addresses the practical challenge of periodically recomputing expert placement (currently done every ~10 minutes with simple heuristics), providing principled alternatives with provable guarantees.
• Dynamic reallocation: Demonstrates that dynamic reconfiguration can be beneficial when done carefully, with the online algorithm automatically balancing latency versus overhead.
• Static deployment: For systems where reconfiguration is prohibitively expensive, the 2-approximation provides a simple, near-optimal static placement strategy.

Key Technical Insights

1. Smoothness exploitation: The observation that $f_t(x'_t) \leq \theta f_t(x_t)$ when $x_{t,i} + 1 \leq \theta(x'_{t,i} + 1)$ enables both the improved competitive ratio and the efficient rounding scheme.

2. Sublinearity of the conjugate: The property $\hat{f}_t(\theta\gamma_t) \geq \sqrt{\theta}\hat{f}_t(\gamma_t)$ is crucial for the dual analysis, allowing the scaled dual variables to maintain value.

3. Hardy's inequality: Used to prove the online dual lower bound, showing that early overcommitment forces a $\sqrt{\ln k}$-factor loss.

---

Conclusion

This paper initiates the principled study of Mixture-of-Experts serving through a formal optimization lens. The main contributions are:

1. A formal model capturing the latency-reconfiguration trade-off in MoE serving.
2. An $O(\sqrt{\log k})$-competitive online algorithm using regularized greedy with KL divergence, improved from the standard $\log k$ by exploiting function smoothness.
3. A matching $\Omega(\sqrt{\log k})$ barrier for the online dual problem, showing the analysis is tight.
4. Offline algorithms: constant-factor approximation for dynamic, 2-approximation for static, with matching integrality gap.
5. Hardness results: NP-hardness and no FPTAS under ETH for the static problem.

Future Directions

• Closing the primal gap: Whether the $O(\sqrt{\log k})$ competitive ratio for the primal problem can be improved or matched by a lower bound remains open.
• Practical validation: Empirical evaluation of the algorithms on real MoE serving workloads.
• Extensions: Incorporating additional constraints such as memory limits, heterogeneous GPU types, or communication costs between GPUs.
• Tighter offline bounds: Improving the constant factor in the offline approximation or closing the gap between the 2-approximation and the $2 - 1/m$ integrality gap for the static problem.