# A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving

> A deterministic O(1)-competitive algorithm for dynamic mixture-of-experts serving is proven, matching randomized performance and closing the deterministic gap.

- **Source:** [arXiv](https://arxiv.org/abs/2608.16947)
- **Published:** 2026-09-12
- **Permalink:** https://picx.dev/p/QUipUX
- **Whiteboard:** https://picx.dev/p/QUipUX/image

## Summary

# Summary of "A Deterministic Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving"

## Summary (Overview)

- **Main Result**: The paper proves a deterministic $O(1)$-competitive algorithm for Dynamic Mixture-of-Experts (MoE) serving, improving on the prior deterministic $O(k)$ baseline and matching the asymptotic performance of randomized approaches.
- **Key Theorem**: For every number of experts $m$ and replica budget $k \geq 1$, the algorithm satisfies $\mathrm{ALG}_{\det} \leq 10C_{\mathrm{PB}} \cdot \mathrm{OPT} + (5C_{\mathrm{PB}} + 8)k + 16$, where $C_{\mathrm{PB}}$ is an absolute constant from the Positive Body Chasing theorem.
- **Novel Contribution**: A deterministic pathwise rounding theorem that converts fractional allocations to integral ones with service distortion factor 3 and movement bounded by fractional movement plus $6k$.
- **Formal Verification**: The complete theorem is machine-checked in Lean 4, with the two-sparse positive-body chasing theorem as the sole scientific source premise.
- **Implication**: Randomization is not asymptotically necessary for constant-competitive MoE serving.

## Introduction and Theoretical Foundation

### Background
Dynamic Mixture-of-Experts inference requires deciding how many replica GPUs to assign to each expert as workloads change over time. The core trade-off involves:
- **Switching costs**: Moving replicas between experts incurs movement costs
- **Bottleneck latency**: Insufficient replication increases service latency

### Prior Work
- **Huang, Lou, and Xiao** formalized this as an online problem and proved an $O(\sqrt{\log k})$ randomized competitive ratio, with an $\Omega(\sqrt{\log k})$ lower bound for an offset-Fenchel-dual maximization problem.
- **Vergeres** proved a deterministic factor-16 bound for the equality-budget fractional relaxation and a randomized factor-48 integral bound via Lazy Threshold Rounding.
- The previous deterministic baseline was $\Omega(1)$ to $O(k)$ — achieved by keeping a fixed integral allocation, which is within factor $k+1$ of any fractional path since every fractional coordinate lies in $[0, k]$.

### Problem Model
Fix $m \geq 1$ experts and $k \geq 1$ replica GPUs. The integral state space is:

$$X_{m,k} = \left\{x \in \mathbb{Z}_{\geq 0}^m: \sum_{i=1}^m x_i = k\right\}$$

At round $t$, a nonnegative workload vector $r_t \in \mathbb{R}_{\geq 0}^m$ is revealed. The online algorithm chooses $x_t \in X_{m,k}$ and pays:

$$f_t(x_t) + \|x_t - x_{t-1}\|_1, \qquad f_t(x) = \max_{i \in [m]} \frac{r_{t,i}}{1 + x_i}$$

## Methodology

### 1. Finite Positive Approximation to Reciprocal Service

The epigraph of $r/(1+u)$ admits a finite positive-polyhedral inner approximation with constant distortion. For a workload coordinate $r$ and augmented allocation $u$, the tangent is defined as:

$$L_{r,p}(u) = \frac{r(2p - q)}{p^2} = \frac{r(2p - 1 - u)}{p^2}, \qquad q = 1+u$$

**Lemma 2 (Tangent Envelope)**: For all $r \geq 0$, $q > 0$, $p > 0$:

$$\frac{r}{q} - L_{r,p}(u) = \frac{r(q-p)^2}{qp^2} \geq 0$$

If $0 \leq u \leq 2k$, some $p \in \{1, \ldots, 2k+1\}$ satisfies $L_{r,p}(u) \geq \frac{3}{4}\frac{r}{1+u}$.

This yields the finite envelope $H_r(u) = \max_{1 \leq p \leq 2k+1} L_{r,p}(u)$ with:

$$\frac{3}{4}\frac{r}{1+u} \leq H_r(u) \leq \frac{r}{1+u} \quad (0 \leq u \leq 2k) \tag{1}$$

The inequality $s \geq L_{r,p}(u)$ is equivalent to the positive covering row (with support size at most 2):

$$\frac{p^2}{r(2p-1)}s + \frac{1}{2p-1}u \geq 1 \tag{2}$$

### 2. Event/Reset Reduction to Positive Body Chasing

Using augmented coordinates $(u_1, \ldots, u_m, s)$, the algorithm presents two types of bodies to the positive-body chaser:

**Event body** (when request $r_t$ arrives):
$$E_t = \left\{(u,s): \sum_i u_i \leq k, \quad s \geq L_{r_{t,i},p}(u_i) \text{ for all } i, p\right\} \tag{3}$$

**Reset body** (after the round-t action):
$$R_t = \left\{(u,s): \sum_i u_i \leq k, \quad s \leq \delta_t\right\}, \qquad \delta_t = 2^{-t} \quad (t \geq 1) \tag{4}$$

The geometrically shrinking positive resets charge service cost to vertical movement.

### 3. Balanced Projection (Removing Resource Augmentation)

The chaser operates with resource augmentation $\epsilon = 1$, giving $\sum_i u_i \leq 2k$. The balanced projection maps to exact-budget fractional allocations:

$$\rho(u) = \frac{k - \frac{1}{2}\sum_i u_i}{m}, \qquad x_i(u) = \frac{u_i}{2} + \rho(u) \tag{6}$$

**Lemma 4**: The map satisfies $x(u) \geq 0$, $\sum_i x_i(u) = k$, $x_i(u) \geq u_i/2$, and:

$$\|x(u) - x(v)\|_1 \leq \|u - v\|_1$$

### 4. Deterministic Pathwise Rounding (Key Novelty)

For a fractional state $z$ with $\sum_i z_i = k$, define the required integral level:

$$\ell_i(z) = \max\left\{0, \left\lceil \frac{z_i - 2}{3} \right\rceil\right\} \tag{12}$$

This is the smallest nonnegative integer satisfying $1 + z_i \leq 3(1 + \ell_i(z))$.

**Repair Rule**: Given previous integral state $y$ and current fractional state $z$:
1. Find least index $i$ with $y_i < \ell_i(z)$ and temporarily add one unit there
2. Among positive coordinates, choose $j$ maximizing $d_j(w,z) = 3w_j - 1 - z_j$
3. Remove one unit from $j$ (the "deep donor")
4. Repeat until all coordinates meet their required levels

**Top-unit potential**:
$$\Phi(y,z) = \sum_i (3y_i - 1 - z_i)_+ \tag{15}$$

**Lemma 5 (Deep Donor)**: Every nonnegative integral vector $y$ of mass $k+1$ contains a positive coordinate $j$ with $3y_j - 1 - z_j \geq 1$.

**Lemma 6 (Repair Charge)**: $\|R_z(y) - y\|_1 \leq 2(\Phi(y,z) - \Phi(R_z(y), z))$

**Lemma 7 (External Variation)**: For fixed $y$ and exact-budget fractional states $z, z'$:
$$2(\Phi(y,z') - \Phi(y,z)) \leq \|z' - z\|_1$$

**Theorem 8 (Deterministic Simplex Rounding)**: For every finite exact-budget fractional path $z_1, \ldots, z_T$ and supplied $y_0 \in X_{m,k}$, the repair rule produces a deterministic prefix-causal integral path satisfying:

$$1 + z_{t,i} \leq 3(1 + y_{t,i}) \quad \text{for every } t, i \tag{16}$$

$$\sum_{t=1}^T \|y_t - y_{t-1}\|_1 \leq 6k + \sum_{t=2}^T \|z_t - z_{t-1}\|_1 \tag{17}$$

$$\sum_t f_t(y_t) \leq 3\sum_t f_t(z_t) \tag{18}$$

## Empirical Validation / Results

### Main Theorem

**Theorem 1 (Deterministic $O(1)$-competitive upper bound)**: For every $m, k \geq 1$ and every integral initial state, there is a causal deterministic integral online algorithm such that every finite nonnegative workload sequence satisfies:

$$\mathrm{ALG}_{\det} \leq 10C_{\mathrm{PB}} \cdot \mathrm{OPT} + (5C_{\mathrm{PB}} + 8)k + 16$$

The multiplicative constant is independent of $m$, $k$, the initial state, the horizon, and the workloads.

This gives the boxed competitive ratio bound:

$$\mathrm{CR}_{\det}(k) \leq 10C_{\mathrm{PB}} \quad \text{for every } k \geq 1$$

Since $C_{\mathrm{PB}}$ is absolute, $\mathrm{CR}_{\det}(k) = \Theta(1)$ (the lower bound $\geq 1$ follows from the routine observation that every online path is feasible offline).

### Proof Composition

The composition of results yields:

$$\begin{aligned} \mathrm{ALG}_{\det} &\leq (M + 2k) + 6k + 3\left(\frac{4}{3}M + \frac{16}{3}\right) \\ &= 5M + 8k + 16 \\ &\leq 10C_{\mathrm{PB}} \cdot \mathrm{OPT} + (5C_{\mathrm{PB}} + 8)k + 16 \end{aligned}$$

where $M \leq C_{\mathrm{PB}}(k + 2\text{ OPT})$ is the chaser's movement bound.

### Formal Verification

The complete theorem is machine-checked in **Lean 4.32.2** with pinned Mathlib 4.32.2. Key declarations:
- `dynamicMoe_explicit_deterministic_upper` — the explicit deterministic upper bound
- `dynamicMoe_deterministic_theta_one` — the $\Theta(1)$ competitive ratio

The formalization uses the two-sparse positive-body consequence as its **sole scientific premise**. Lean reports only standard axioms (propext, Classical.choice, Quot.sound). The companion archive includes:
- 33 focused tests
- A 200-round oscillation control
- A deliberately false rounding rule without hysteresis (demonstrating why the dead band is necessary)

## Theoretical and Practical Implications

### Theoretical Significance
1. **Resolves the deterministic gap**: The prior deterministic bound was $O(k)$; this paper achieves $O(1)$, showing randomization is not asymptotically necessary for MoE serving.
2. **Novel rounding technique**: The deterministic pathwise rounding theorem (Theorem 8) provides a general tool for converting fractional online algorithms to integral ones with constant service distortion and bounded movement stretch.
3. **Positive body reduction**: The paper demonstrates how the MoE problem can be reduced to the Positive Body Chasing theorem, leveraging the $d=2$ sparsity of the covering constraints.

### Practical Implications
- The algorithm provides a **guaranteed competitive ratio** independent of problem dimensions (expert count, replica budget, horizon).
- The additive term $(5C_{\mathrm{PB}} + 8)k + 16$ grows linearly with the replica budget but is independent of the expert count.
- The model allocates replicas but does not model physical network topology, shared links, or routing.

### Comparison with Prior Work
| Method | Type | Competitive Ratio |
|--------|------|-------------------|
| Huang, Lou, Xiao | Randomized | $O(\sqrt{\log k})$ |
| Vergeres (fractional) | Deterministic | Factor 16 |
| Vergeres (integral) | Randomized | Factor 48 |
| Previous deterministic baseline | Deterministic | $O(k)$ |
| **This paper** | **Deterministic** | **$O(1)$ (factor $10C_{\mathrm{PB}}$)** |

## Conclusion

### Main Takeaways
- The paper proves a deterministic $O(1)$-competitive algorithm for Dynamic MoE serving, closing the gap between deterministic and randomized approaches.
- The key innovation is a **deterministic pathwise rounding theorem** with service distortion 3 and movement bounded by fractional movement plus $6k$, replacing the need for Lazy Threshold Rounding.
- The complete proof is **machine-checked in Lean 4**, providing formal verification relative to the Positive Body Chasing theorem.

### Open Directions
1. **Sharper constants**: The concrete bound $10C_{\mathrm{PB}}$ is not optimized; better numerical constants may be achievable.
2. **Efficiency**: The paper does not claim polynomial-time implementation of the complete algorithm; explicit bit-complexity analysis remains open.
3. **Grid optimization**: The concrete integer tangent grid uses $O(mk)$ covering rows per event; a geometric grid reduces this to $O(m\log(k+1))$.
4. **Broader applications**: The deterministic rounding theorem may apply to other online allocation problems with similar structure.

### Key Quote
> "The main conclusion is that $\mathrm{CR}_{\det}(k) \leq 10C_{\mathrm{PB}}$ for every replica budget $k \geq 1$. Because $C_{\mathrm{PB}}$ is absolute, this is an $O(1)$ upper bound. Thus the deterministic ratio has the same asymptotic order as the randomized ratio from the previous version, and randomization is not asymptotically necessary."

---

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