# Mixture-of-Experts Serving

> This paper introduces the first formal model for Mixture-of-Experts serving, providing an optimal online algorithm with a tight competitive ratio and a 2-approximation for the static case.

- **Source:** [arXiv](https://arxiv.org/abs/2607.17880)
- **Published:** 2026-08-29
- **Permalink:** https://picx.dev/p/fAtAX5
- **Whiteboard:** https://picx.dev/p/fAtAX5/image

## Summary

# 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

| Result | Value |
|--------|-------|
| **Approximation ratio** | 2 (Theorem 6.1) |
| **Integrality gap** | $2 - \frac{1}{m}$ (Theorem 6.2) |
| **Hardness** | NP-hard; No FPTAS under ETH (Theorem 6.4) |

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.

---

_Markdown view of https://picx.dev/p/fAtAX5, served by PicX — AI-generated visual whiteboard summaries of research papers._