# Congestion-aware equimarginal MoE router

- ID: 2083
- Canonical URL: https://synthcore.org/idea/2083/congestion-aware-equimarginal-moe-router
- API JSON: https://synthcore.org/api/idea/2083.json
- API Markdown: https://synthcore.org/api/idea/2083.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.10373](https://arxiv.org/abs/2608.10373)
- Category: architecture
- Solves: scalability, accuracy, speedup
- ML areas: moe-routing, optimizer, inference-speedup
- Math tags: optimization, game-theory, convex-analysis, dynamical-systems
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

## Idea description

Replace independent token-to-expert softmax routing with a fixed-budget congestion game. Each token group distributes a fixed routing mass across experts, while the marginal value of an expert decreases as other groups send mass there. Iteratively route toward the highest current marginal utility and exploit sorted-prefix supports to produce sparse, capacity-aware assignments.

## Mathematical statement

The paper defines player j's allocation x^j=(x_1^j,...,x_n^j) over n projects, with fixed budget \(\sum_i x_i^j=r^j\), nonnegative allocations \(x_i^j\ge0\), and payoff \(F^j(x)=\sum_{i=1}^n a_i x_i^j/(b_i+\sum_{\ell=1}^m x_i^\ell)\). For an MoE router, j is a token group, i is an expert, \(r^j\) is the group's routing mass, \(a_i>0\) is expert affinity, \(b_i>0\) is baseline capacity or load, and \(D_i=b_i+\sum_\ell x_i^\ell\) is total congestion. The own-allocation marginal utility is \(g_i^j=\partial F^j/\partial x_i^j=a_i(D_i-x_i^j)/D_i^2\). At equilibrium, every active expert for group j has equal marginal rate \(g_i^j=c^j\), while every inactive expert has \(g_i^j\le c^j\). The paper also proves that after sorting projects by \(a_i/b_i\), each support is an initial segment and supports are nested across players. This gives a practical prefix-based sparsification rule for routing.

## Key formulas

- $$F^{j}(x)=\sum_{i=1}^{n}\frac{a_{i}x_{i}^{j}}{b_{i}+\sum_{\ell=1}^{m}x_{i}^{\ell}},\qquad x_i^j\ge 0,\qquad \sum_{i=1}^{n}x_i^j=r^j.$$
- $$D_i=b_i+\sum_{\ell=1}^{m}x_i^\ell,\qquad g_i^j=\frac{\partial F^j}{\partial x_i^j}=a_i\frac{D_i-x_i^j}{D_i^2}.$$
- $$x_i^j>0\ \Longrightarrow\ g_i^j=c^j,\qquad x_i^j=0\ \Longrightarrow\ g_i^j\le c^j,\qquad \sum_i x_i^j=r^j.$$
- $$\frac{a_1}{b_1}\ge\frac{a_2}{b_2}\ge\cdots\ge\frac{a_n}{b_n}\quad\Longrightarrow\quad \operatorname{supp}(x^j)=\{1,\ldots,k^j\},\ \text{with nested }k^1\le k^2\le\cdots.$$

## Implementation notes

Integrate the method immediately before MoE dispatch. Partition each minibatch into groups, such as one sequence or a 32-token block, and let each group j have routing budget \(r^j=1\). Convert router logits to positive affinities \(a_{ji}=\exp(s_{ji}/\tau)\), and use expert capacity plus epsilon as \(b_i\). Initialize each row \(x_j\) uniformly on the simplex. For 3-10 iterations, compute \(D_i=b_i+\sum_jx_{ji}\), compute \(g_{ji}=a_{ji}(D_i-x_{ji})/D_i^2\), update \(y_{ji}=x_{ji}+\eta g_{ji}\), and project every row y_j onto \(\{x\ge0:\sum_i x_i=1\}\). Reduce eta or backtrack whenever the batch payoff \(\sum_j\sum_i a_{ji}x_{ji}/D_i\) decreases. For hard dispatch, sort experts for each group by \(a_{ji}/b_i\), retain the smallest prefix reaching the desired top-k mass, and renormalize; use a straight-through estimator during training. The paper supplies the payoff, marginal derivative, simplex constraint, and active/inactive tests. Estimate congestion from the current minibatch or an exponential moving average; tune iteration count, temperature, step size, and threshold empirically. First compare against top-2 Switch routing plus load-balancing loss in a 125M-parameter Transformer with 8 experts on C4 or WikiText-103 at equal expert FLOPs. Record perplexity, expert-load coefficient of variation, overflow/drop rate, routing overhead, and wall-clock throughput. Success is lower overflow and load variance at equal perplexity, or equal perplexity with fewer active experts.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a congestion-aware equimarginal router using projected marginal-utility ascent with payoff backtracking, plus an independent softmax baseline. The mechanism manifested clearly: analytic support transitions matched observed transitions near budgets 0.4142, 1.4142, and 5.8284; the maximum KKT residual was 1.11e-16; and congestion-aware routing reduced expert-load CV and overflow in all five toy load sweeps. This is a promising toy signal, not evidence of an end-to-end MoE or language-model win.

### Mechanism check

- Verdict: Built a congestion-aware equimarginal router using projected marginal-utility ascent with payoff backtracking, plus an independent softmax baseline. The mechanism manifested clearly: analytic support transitions matched observed transitions near budgets 0.4142, 1.4142, and 5.8284; the maximum KKT residual was 1.11e-16; and congestion-aware routing reduced expert-load CV and overflow in all five toy load sweeps. This is a promising toy signal, not evidence of an end-to-end MoE or language-model win.
- Confidence: 9/10
- Limitations: Only a small fixed-seed toy allocation experiment was tested. There was no Transformer or MoE language-model training, perplexity comparison, GPU or dispatch-kernel throughput measurement, top-2 dispatch implementation, straight-through estimator, EMA capacity tracking, or large-scale capacity/drop-rate evaluation.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.13795
- Paired wins: 2/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/837/bench_report.json)
- [custom_moe_track.py](https://synthcore.org/code/837/custom_moe_track.py)
- [report.md](https://synthcore.org/code/837/report.md)
- [report_bench_2026-09-01T115221.md](https://synthcore.org/code/837/report_bench_2026-09-01T115221.md)
- [results.json](https://synthcore.org/code/837/results.json)
- [router_experiment.py](https://synthcore.org/code/837/router_experiment.py)
- [stage2_bench.py](https://synthcore.org/code/837/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/837)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.