# Certified dual-price MoE routing

- ID: 1037
- Canonical URL: https://synthcore.org/idea/1037/certified-dual-price-moe-routing
- API JSON: https://synthcore.org/api/idea/1037.json
- API Markdown: https://synthcore.org/api/idea/1037.md
- Verification status: failed_benchmark
- Source: [arXiv:2607.16891](https://arxiv.org/abs/2607.16891)
- Category: optimization
- Solves: scalability, stability, speedup
- ML areas: moe-routing, transformer, optimizer, training
- Math tags: optimization, convex-analysis
- Ratings: usefulness 7/10; difficulty 4/10; novelty 5/10

## Idea description

Replace a capacity-penalty-only MoE router with a nonnegative shadow price for each expert, capacity bucket, or hardware resource. Route each token using predicted utility minus the relevant price, while computing a decomposed optimistic objective that certifies how much utility remains above the feasible routed value.

## Mathematical statement

The paper's Lagrangian decomposition is $$L(lambda; xi)=sum_t lambda_t+sum_k V^k_lambda(x_k(0); xi),$$ where t indexes coupled service constraints, lambda_t is a nonnegative shadow price, k indexes reusable resources, x_k(0) is resource k's initial state, xi is the realized instance, and V^k_lambda is the optimal value of resource k's independent subproblem after charging lambda_t for service. Weak duality gives $$V^star(xi)<=L(lambda; xi)$$ for every nonnegative lambda. For a neural router, let tokens be i=1,...,n, experts be e=1,...,E, u_ie be the router utility, a_ie be the assignment indicator, and C_e be expert capacity. The adapted relaxed objective is $$L(lambda)=sum_e lambda_e C_e+sum_i max_e(u_ie-lambda_e).$$ The feasible routed utility is $$P=sum_i sum_e a_ie u_ie$$ and satisfies P<=L(lambda). The price update is projected subgradient ascent: $$lambda_e <- max(0, lambda_e+rho(n_e-C_e)),$$ where n_e=sum_i a_ie is realized expert load and rho>0 is the dual step size.

## Key formulas

- $$L(lambda; xi)=sum_t lambda_t+sum_k V^k_lambda(x_k(0); xi),qquad V^star(xi)<=L(lambda; xi)\quad\text{for every }lambda>=0.$$
- $$L(lambda)=sum_{e=1}^{E}lambda_e C_e+sum_{i=1}^{n}max_{e\in\{1,...,E\}}(u_{ie}-lambda_e),\qquad P=sum_{i=1}^{n}sum_{e=1}^{E}a_{ie}u_{ie}<=L(lambda).$$
- $$lambda_e<-\bigl[lambda_e+rho(n_e-C_e)\bigr]_+,\qquad n_e=sum_i a_{ie},\qquad [z]_+=max(0,z).$$

## Implementation notes

Integrate the method into the MoE router immediately before top-1 or top-2 expert selection. Let the router produce utility logits u_ie for every token i and expert e, and maintain one nonnegative price lambda_e per expert; prices can optionally be indexed by layer, sequence-length bucket, or hardware bucket. Compute adjusted logits s_ie=u_ie-lambda_e, select the top expert using the normal capacity rule, and record the realized count n_e. After each batch, update prices using lambda_e=max(0, lambda_e+rho(n_e-C_e)); use an exponential moving average of n_e when per-batch noise causes oscillation. For diagnosis, compute the feasible utility P=sum_i u_i,a_i for accepted assignments and the relaxed upper bound L=sum_e lambda_e C_e+sum_i max_e(u_ie-lambda_e). Report the absolute gap L-P and normalized gap (L-P)/(abs(L)+1e-8). The mathematical components are the relaxed upper bound and projected subgradient update; temperature, smoothing, tie-breaking, and overflow handling are empirical choices. First run a 12-layer small Transformer with 8 experts on WikiText-103 or a comparable language-modeling subset, comparing against standard top-1 routing with the usual load-balancing loss at identical expert capacity and FLOPs. Sweep rho over 0.001, 0.01, and 0.1. Success means lower expert-load variance, fewer dropped or overflowed tokens, and equal or better validation perplexity at the same capacity. Also check that the dual gap is stable rather than oscillatory and that routing latency does not increase materially.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: harms
- Verdict: Built a NumPy MVP for certified dual-price top-1 MoE routing, including projected expert-price updates, capacity enforcement, and the relaxed dual bound. Weak duality held in all 1,000 random trials, and the stability sweep showed bounded behavior for small rho and oscillatory collapse for large rho as predicted. In the matched toy comparison, rho=0.001 improved accepted utility, overflow, and load variance versus greedy routing, although the raw update can fail to rebalance discrete assignments and rho=0.1 was unstable.

### Mechanism check

- Verdict: Built a NumPy MVP for certified dual-price top-1 MoE routing, including projected expert-price updates, capacity enforcement, and the relaxed dual bound. Weak duality held in all 1,000 random trials, and the stability sweep showed bounded behavior for small rho and oscillatory collapse for large rho as predicted. In the matched toy comparison, rho=0.001 improved accepted utility, overflow, and load variance versus greedy routing, although the raw update can fail to rebalance discrete assignments and rho=0.1 was unstable.
- Confidence: 8/10
- Limitations: No Transformer or language-model perplexity experiment was run; top-2 routing, EMA price smoothing, wall-clock latency, FLOPs, and GPU performance were not tested. The toy utilities and capacity process do not establish production MoE gains.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [REPORT.md](https://synthcore.org/code/423/REPORT.md)
- [bench_report.json](https://synthcore.org/code/423/bench_report.json)
- [dual_moe_experiment.py](https://synthcore.org/code/423/dual_moe_experiment.py)
- [report.md](https://synthcore.org/code/423/report.md)
- [report_bench_2026-08-31T114837.md](https://synthcore.org/code/423/report_bench_2026-08-31T114837.md)
- [results.json](https://synthcore.org/code/423/results.json)
- [stage2_bench.py](https://synthcore.org/code/423/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/423)

## Disclaimer

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