A mixture-of-experts model (MoE) is a network in which a small learned "router" sends each token to only a few of many sub-networks, called experts. Training such a model has a well-known failure: a few experts win early, receive more tokens, improve faster, and starve the rest. This is called expert collapse. The most widely used fix today is a feedback controller. Each expert gets a bias added to its routing score, and after every step the bias is nudged down if that expert was overloaded and up if it was underloaded (Auxiliary-Loss-Free Load Balancing Strategy for Mixture-of-Experts). The controller works in practice, but nobody has checked whether it is a stable controller. Stable here means three things: whether it settles, how far it overshoots when the data mix shifts, and whether it chatters indefinitely at the size of its step.
This note proposes treating that bias update as what it is, a low-dimensional discrete-time feedback system. We would use the tools of automated Lyapunov synthesis to certify it and to design better versions. A Lyapunov function is an "energy" that provably decreases along the system's trajectories, so finding one proves the system converges. The state here is only the vector of $M$ expert biases, with $M$ typically 8 to 64. That is small enough for certificate-synthesis tools that cannot handle billions of weights. The practical payoff we test is a controller whose certified worst-case imbalance is known before training, including for experts of unequal size. Current balancing methods do not cover unequal expert sizes ($\phi$-Balancing for Mixture-of-Experts Training).
Core Claim
The key structural fact is simple. Hold the router's scoring function $s(x)\in\mathbb{R}^M$ fixed, and let $\ell(b)\in\mathbb{R}^M$ be the expected fraction of tokens each expert receives when biases $b$ are added before top-$k$ selection. Then $\ell$ is the gradient of a convex function:
$$ \ell(b) = \nabla F(b), \qquad F(b) = \mathbb{E}_x\big[\text{sum of the } k \text{ largest entries of } s(x)+b\big]. $$
The sum of the top $k$ entries is convex in $b$, and its gradient is the indicator of which experts are selected. Seen this way, bias balancing is descent on the dual of a balanced-assignment problem, $b_{t+1} = b_t - \eta\,u(\hat\ell_t - c)$. Here $\eta$ is the step size, $\hat\ell_t$ is the noisy load measured on the previous batch, $c$ is the target load vector (uniform, or proportional to expert capacity), and $u$ is the update law.
The rule from Auxiliary-Loss-Free Load Balancing uses $u=\mathrm{sign}$. In control terms that is a relay controller, and relay feedback on such a plant is expected to settle into a limit cycle of amplitude on the order of $\eta$ rather than converge.
Three things make the real system harder than this clean picture. First, the router weights keep learning, so $F$ drifts. Second, the load signal is stale by one step and noisy because it comes from a mini-batch. Third, $F$ is only weakly convex: it is flat along the all-ones direction and has kinks wherever score gaps vanish. We therefore pose the goal as an input-to-state stability certificate. Treating router drift and batch noise as a bounded disturbance $w_t$, we seek $V$ such that
$$ V(e_{t+1}) - V(e_t) \le -\alpha\big(\|e_t\|\big) + \sigma\big(\|w_t\|\big), $$
where $e_t$ is the bias error projected off the all-ones direction, and $\alpha,\sigma$ are increasing functions with $\alpha(0)=\sigma(0)=0$. This inequality yields a certified ultimate bound on load imbalance as a function of drift rate and batch size. It is a number that can be compared directly with the measured maximum imbalance.
The claim is threefold. First, such certificates can be synthesized for realistic $M$. Second, they predict which controller settings oscillate or overshoot under data shift. Third, synthesizing the controller together with its certificate gives smaller imbalance than sign updates at equal task loss, especially when capacity targets $c$ are unequal.
Relation to Prior Work
The closest work by name is Stable-MoE. It routes tokens across edge servers using drift-plus-penalty queue control with a hand-fixed quadratic potential on token and energy queues. It is a hardware-scheduling method: it neither synthesizes a Lyapunov function nor analyzes the bias dynamics that govern collapse inside training. We share the vocabulary but not the object of study.
The balancing methods motivate the problem. Loss-Free Balancing supplies the controller we analyze, and its result is our strongest baseline. $\phi$-Balancing already uses convex duality and mirror descent on moving-average loads. It is the main threat to novelty, because it also exploits convexity. However, it derives an update from an idealized static dual. It does not bound closed-loop behavior under router drift, staleness, or noise, and it explicitly leaves unequal expert capacities open. We address exactly those gaps.
Representation-level fixes are complementary and act on a different failure, homogenization of expert features rather than load. These include hyperspherical low-rank routing in On the Representation Collapse of Sparse Mixture of Experts and orthogonality and variance losses in Advancing Expert Specialization for Better MoE. We use them only as orthogonal controls. The first also constrains our design: its finding that routing is effectively a low-rank problem supports reducing the routing state to small dimension.
The method comes from three sources. Dissipativity Theory for Nesterov's Accelerated Method certifies optimization algorithms by abstracting a convex gradient map as a sector-bounded nonlinearity and solving tiny linear matrix inequalities (LMIs). That fits $\ell=\nabla F$ exactly. We extend it beyond static strongly convex objectives to flat directions, delay, and a disturbance input. For the non-convex parts that LMIs cannot capture, we use counterexample-guided synthesis. In that loop a neural Lyapunov candidate is trained, a solver searches for violations, and the violations are fed back, as in Automated Formal Synthesis of Lyapunov Neural Networks and Fossil 2.0. The non-convex parts are the moving-average filter, momentum, and the capacity-dependent target. Fossil 2.0 also supplies joint synthesis of controller and certificate. Its documented weaknesses, non-termination and poor scaling past about ten dimensions, set our limits. The symbolic search of Analytical Lyapunov Function Discovery is a fallback for finding closed-form certificates that verify in milliseconds.
Rethinking Convergence in MoE Training bounds gradient norms under routing switches. It treats the router as a source of noise, not as a controlled feedback system, so it neither predicts oscillation nor gives a design rule.
Research Program
The work has four parts.
The first is the model of the plant. We log $(b_t,\hat\ell_t,s(x))$ from small MoE training runs and estimate the local smoothness of $\nabla F$, which is governed by the density of near-ties in routing scores. We also estimate the drift rate of $F$ caused by router learning, and the batch noise level. These give the sector bounds and disturbance bound $w$ that the certificate needs. Making them measurable is the empirical core. If drift is large relative to the controller's bandwidth, no certificate will be tight, and we report that.
The second is certification of existing controllers. We certify the sign update, a smoothed sign update, and the $\phi$-balancing update. For linear-plus-sector abstractions we use LMIs, which scale to $M=64$ because the all-ones symmetry and permutation symmetry let us reduce to a few scalar blocks. For the full nonlinear reduced model at $M\le 8$ to $16$ we use dReal-verified neural certificates through Fossil. The output is a certified ultimate imbalance bound per controller and setting.
The third is synthesis. We jointly synthesize a controller from a small family together with its certificate. The family covers proportional-integral updates with a deadzone and gain scheduled on measured score-gap density. The controller is chosen to minimize the certified ultimate bound subject to a cap on bias magnitude, since large biases override the router's content-based preferences. Unequal capacity enters only through the target $c$, which the certificate handles directly. Because the bias is used only for selection and not for weighting expert outputs, the task gradient is untouched, as in Loss-Free Balancing.
The fourth is closing the loop. We train real models with each controller and compare certified bounds against measured imbalance and oscillation. Agreement validates the abstraction. Disagreement identifies which unmodeled effect matters.
Baselines
The naive reference point is top-$k$ routing with a Switch-style auxiliary balancing loss. On the 1B multilingual setting of Auxiliary-Loss-Free Load Balancing it reports validation perplexity 9.56 and maximum load violation 0.72. We also run no balancing at all, to show collapse occurs at our scale.
The strongest existing method is Loss-Free Balancing with sign updates. At 1B parameters and up to 200B tokens it reports perplexity 9.50 and maximum violation 0.04. We cannot reproduce 200B tokens. We therefore re-run it at our scale on identical data, model, and token budget, tuning its step size over the same number of trials as our controller's hyperparameters. Beating it means one of two things. Either we lower time-averaged and worst-case maximum violation by a margin larger than seed-to-seed spread at equal or better perplexity. Or, under a data-mix shift, we recover balance in fewer steps with smaller overshoot.
$\phi$-Balancing is the second strong baseline, run with the same tuning budget. Its reported fine-tuning results on Moonlight-16B-A3B are Math500 accuracy 66.2% versus 64.8% and HumanEval pass@1 75.9% versus 73.2%. These anchor a possible fine-tuning comparison if compute allows. We would only claim parity or better on load metrics, not on those downstream scores, unless we actually run that setting.
The key ablation keeps our synthesized controller's structure but sets its gains by grid search rather than certificate-driven synthesis. This isolates whether the certificate contributes anything beyond "use a proportional-integral controller." A second ablation swaps the certified controller into a model that also uses X-MoE routing. This checks that the load gains are orthogonal to representation fixes.
Why not just…?
Why not just tune Loss-Free Balancing's step size, or hand-design a PI controller? This is the most serious threat. A competent engineer might find good gains by grid search, and we may lose on raw imbalance numbers. The grid-search ablation settles it directly. If tuned gains match the synthesized ones, the remaining contribution is predictive: the certificate computes, from cheap measurements of drift and noise, which settings will oscillate or overshoot without training them. We would test that prediction on held-out configurations of batch size, number of experts, and shift severity. If the certificate fails to predict better than a heuristic based on step size relative to batch noise, the proposal has not earned its machinery, and we would say so.
Why not just rely on $\phi$-balancing's convex-duality derivation, which already explains convergence? Its derivation covers the idealized static dual. It does not cover the closed loop with stale, noisy loads and a drifting router, and its authors leave unequal capacities open. The heterogeneous-capacity and shift experiments below are where a static-dual argument and a closed-loop certificate should diverge. If $\phi$-balancing matches us there, our contribution reduces to supplying its missing proof.
Why not just use Expert Choice routing, which is balanced by construction? Expert Choice, studied in Routers in Vision Mixture of Experts, fixes per-expert capacity by letting experts pick tokens. That makes token coverage uneven and is awkward for autoregressive decoding, where future tokens are unavailable. We include it in the language-modeling comparison as a reference for perplexity. We do not see it as a substitute in the token-choice regime that most deployed models use.
Why not just hard-code a quadratic Lyapunov function, as Stable-MoE does for queues? We will try exactly that first. It is the LMI step with a fixed quadratic form. If a quadratic certificate already gives tight bounds, synthesis beyond it is unnecessary, and we report the quadratic result. We expect it to be loose once the moving-average filter, deadzones, and capacity-dependent targets enter. That expectation is checked by comparing quadratic and neural certified bounds against measured imbalance.
Proposed Experiments
We start with pipeline sanity. We run our synthesis path on the Fossil 2.0 suite of 13 continuous-time and 4 discrete-time models, where Fossil 2.0 reports 90 to 100% success, to confirm we reproduce its behavior before applying it to new plants.
Main training runs use top-2 MoE language models with 8, 16, and 64 experts on WikiText-103 and enwik8. We choose $k=2$ because Rethinking Convergence in MoE Training finds it near-optimal and reports a 3.125x reduction in iterations to target loss from $K=1$ to $K=2$ on WikiText-103. For enwik8, the 135M Brainformer reference of SimSMoE, 1.11 baseline and 1.08 bits per character, anchors the quality scale. A scaled run on the multilingual CCNet/Wikipedia setup of X-MoE follows if budget allows; there Switch reaches 19.02 and X-MoE 18.72 masked-language-model perplexity. Metrics are perplexity or bits per character, time-averaged and worst-case maximum violation, oscillation amplitude of biases late in training, and recovery time and overshoot after a scheduled abrupt change in data domain mix.
The heterogeneous-capacity experiment mixes experts of two widths with targets proportional to compute. No prior method in the file has a principled answer here.
The decisive check is calibration. Across roughly fifty configurations, does the certified ultimate bound rank-order and upper-bound the measured maximum violation? Does the certificate correctly flag which sign-update settings settle into limit cycles of size about $\eta$? If certified bounds are routinely violated, the reduced model is wrong and the program fails at its foundation. If they hold but are loose by more than an order of magnitude, the certificates are sound but useless for design. If they hold tightly and the synthesized controller beats tuned Loss-Free Balancing and $\phi$-balancing under shift and heterogeneous capacity, the claim is established.
References
- Auxiliary-Loss-Free Load Balancing Strategy for Mixture-of-Experts
- $\phi$-Balancing for Mixture-of-Experts Training
- Stable-MoE: Lyapunov-based Token Routing for Distributed Mixture-of-Experts Training over Edge Networks
- On the Representation Collapse of Sparse Mixture of Experts
- Advancing Expert Specialization for Better MoE
- Dissipativity Theory for Nesterov's Accelerated Method
- Formal Synthesis of Lyapunov Neural Networks
- Fossil 2.0: Design, usage and impact of a software tool for verification and control of dynamical models
- Analytical Lyapunov Function Discovery: An RL-based Generative Approach
- Rethinking Convergence in MoE Training: The Role of Routing Sparsity
- Routers in Vision Mixture of Experts: An Empirical Study
- SimSMoE: Toward Efficient Training Mixture of Experts via Solving Representational Collapse