Certified dual-price MoE routing MVP

Implementation

dual_moe_experiment.py implements top-1 routing with one nonnegative expert price per expert:

lambda <- max(0, lambda + rho * (realized_load - capacity))

It computes the relaxed objective

L = sum_e lambda[e] * C[e] + sum_i max_e(u[i,e] - lambda[e])

and the accepted feasible utility after enforcing expert capacity. results.json contains the fixed-seed output.

Stage-1 mathematical checks and predictions

Seed: 1037.

1. Weak-duality prediction: for every nonnegative price vector, P <= L, so the measured violation should be zero. Across 1,000 random instances, maximum violation was 0.0; the minimum observed gap was 5.943 and mean gap 43.103.

2. Local price-dynamics prediction: in the symmetric two-expert toy with 200 tokens and uniform utility differences, linearization gives price-difference multiplier approximately 1 - rho*n. Thus the predicted multipliers for rho [.001,.005,.01,.02,.04] are [.8,0,-1,-3,-7]. Observed mean absolute load imbalances were [11.27,16.25,200,200,200]. Small rho remains bounded, while rho >= .01 (the predicted marginal/unstable region) collapses into full oscillation. This confirms the qualitative stability boundary, though the rho=.005 case is noisy because the discrete assignment map is nonsmooth.

3. Overload-direction prediction: an expert with positive excess load receives a positive price increment. In the 70/30 two-expert case with capacities 50/50, initial greedy counts were [70,30] and the final prices after 30 updates were [0.8,0.6], so the overloaded expert's price increased as predicted. However, the final counts stayed [70,30]: with discrete top-1 routing, the price difference had not crossed the utility margin. This is an important failure mode of the un-smoothed update, not a hidden success.

Mini comparison

With four experts, 128 tokens, capacity 32 each, 500 batches, and identical generated utilities:

| method | accepted utility | overflow tokens | load variance | mean dual gap | |---|---:|---:|---:|---:| | greedy baseline | 60.42 | 63.70 | 1434.55 | n/a | | dual rho=.001 | 74.85 | 10.40 | 56.47 | 2.35 | | dual rho=.01 | 72.64 | 12.84 | 66.31 | 4.58 | | dual rho=.1 | 21.85 | 95.75 | 3058.69 | 618.52 |

The small-step dual router gives a clear toy improvement in accepted utility, overflow, and load variance. The large step is unstable, consistent with the stability sweep.

Conclusion

The mechanism manifested: the certified bound was never violated, overload raised its corresponding price, and a stable small step improved routing balance and accepted utility. This is not evidence of a language-model perplexity win: no Transformer, language-model validation, top-2 routing, EMA smoothing, wall-clock latency, or GPU benchmark was tested. The discrete overload example also shows that the raw update may require smoothing, smaller steps, or explicit overflow handling to reliably change assignments.

Run with:

/home/maxwelhelp/main/bin/python3 dual_moe_experiment.py