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

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."