# Effective-resistance natural-gradient routing

- ID: 889
- Canonical URL: https://synthcore.org/idea/889/effective-resistance-natural-gradient-routing
- API JSON: https://synthcore.org/api/idea/889.json
- API Markdown: https://synthcore.org/api/idea/889.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.13990](https://arxiv.org/abs/2607.13990)
- Category: optimization
- Solves: stability, accuracy, sample-efficiency
- ML areas: moe-routing, optimizer, training-dynamics
- Math tags: probability, statistics, linear-algebra, spectral-theory
- Ratings: usefulness 7/10; difficulty 6/10; novelty 7/10

## Idea description

Replace independent expert activation or ordinary softmax routing with an exact fixed-m external-field subset router. Parameterize expert weights by logits, use the subset covariance as the Fisher matrix, and precondition router gradients with its Moore-Penrose pseudoinverse on the sum-zero subspace. The paper's resistance bound supplies a data-dependent ceiling for pairwise logit updates, preventing unstable motion when some experts have low inclusion variance.

## Mathematical statement

For d experts and a fixed routing budget m, the external-field distribution is p_theta(S)=exp(sum_{i in S} theta_i)/e_m(exp(theta)) over subsets S of [d] with |S|=m, where theta_i are expert logits, w_i=exp(theta_i)>0, and e_m(w)=sum_{|T|=m} product_{l in T}w_l. Let X=I_S in {0,1}^d, mu=E[X], and Sigma=Cov(X). Because 1_d^T X=m always, Sigma 1_d=0 and only logit differences are identifiable. The main theorem states that for i not equal to j, (e_i-e_j)^T Sigma^dagger(e_i-e_j) <= 1/v_i+1/v_j, where Sigma^dagger is the Moore-Penrose pseudoinverse, e_i is the i-th standard basis vector, and v_i=Sigma_ii=mu_i(1-mu_i). Its corollary is Sigma >= 1/2(D-vv^T/V), with D=diag(v), v=(v_1,...,v_d)^T, and V=sum_i v_i. For router loss J(theta), g=nabla_theta J, use the constrained natural-gradient direction u=Sigma^dagger P g, where P=I-1_d 1_d^T/d projects out the unidentifiable all-ones direction. Scale the update so every pairwise logit displacement obeys |Delta theta_i-Delta theta_j| <= rho sqrt(1/v_i+1/v_j).

## Key formulas

- $$\mathbb{P}(\mathsf{S}=S)=\frac{\prod_{i\in S}w_i}{e_m(w)},\qquad e_m(w)=\sum_{\substack{T\subseteq[d]\\|T|=m}}\prod_{\ell\in T}w_\ell,$$
- $$(\mathbf{e}_i-\mathbf{e}_j)^{\top}\Sigma^{\dagger}(\mathbf{e}_i-\mathbf{e}_j)\leq\frac{1}{v_i}+\frac{1}{v_j},$$
- $$\Sigma\succeq\frac{1}{2}\left(D-\frac{vv^{\top}}{V}\right),\qquad D=\operatorname{diag}(v),\quad V=\sum_{i=1}^{d}v_i,$$
- $$\theta_{t+1}=\theta_t-\eta\,\Sigma_t^{\dagger}P g_t,\qquad P=I-\frac{\mathbf{1}_d\mathbf{1}_d^{\top}}{d},\qquad \Delta\theta\leftarrow\Delta\theta\cdot\min\left(1,\frac{\rho}{\max_{i<j}|\Delta\theta_i-\Delta\theta_j|/\sqrt{1/v_i+1/v_j}}\right).$$

## Implementation notes

Integrate this into the router-logit update, not into the transformer hidden-state path. For each token or token group, let the router produce logits theta in R^d, choose a fixed budget m, and sample S from the external-field law. A practical exact sampler uses dynamic programming for elementary symmetric polynomials: compute E[k][r] for the first k experts with E[0][0]=1 and E[k][r]=E[k-1][r]+exp(theta_k)E[k-1][r-1], then sample the subset backward conditional on the remaining cardinality. For small d, enumerate all m-subsets; for larger d, use the DP conditional probabilities. At each optimizer step, compute inclusion means mu_i=exp(theta_i)e_{m-1}(w_{-i})/e_m(w), variances v_i=mu_i(1-mu_i), and pairwise probabilities P_ij=exp(theta_i+theta_j)e_{m-2}(w_{-i,-j})/e_m(w), giving Sigma_ij=P_ij-mu_i mu_j for i not equal to j. Project the router gradient g with P, solve Sigma u=P g using conjugate gradient restricted to the sum-zero subspace, and use u as the natural-gradient direction. Add the resistance-based trust-region rescaling in the final formula; rho is a tunable maximum pairwise logit movement. Estimate Sigma from exact DP marginals when d is modest, or from a moving-average minibatch covariance for large or hierarchical routers. First test on a 12-expert, top-2 or top-4 CIFAR-100 or WikiText MoE, comparing ordinary softmax/top-m routing with Adam at equal router FLOPs. Measure validation loss, expert-load coefficient of variation, dead-expert fraction, gradient-norm spikes, and loss variance. The expected signal is fewer routing-collapse events and faster loss reduction at equal communication budget, especially when logits become highly imbalanced.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: harms
- Verdict: Built an exact fixed-m external-field router with DP subset sampling, exact covariance/Fisher computation, pseudoinverse natural-gradient routing, and resistance-based pairwise trust scaling. The mechanism manifested: across 65 imbalanced configurations, the maximum normalized resistance ratio was 0.999996, the covariance lower-bound violation was only numerical noise (minimum eigenvalue -2.0e-14), and trust-cap sweeps matched predicted min(rho, raw_step) to machine precision. In the toy optimization, natural-trust reached loss 1.03e-7 versus 1.47e-3 for vanilla after 80 steps, though this is not evidence of a production MoE win.

### Mechanism check

- Verdict: Built an exact fixed-m external-field router with DP subset sampling, exact covariance/Fisher computation, pseudoinverse natural-gradient routing, and resistance-based pairwise trust scaling. The mechanism manifested: across 65 imbalanced configurations, the maximum normalized resistance ratio was 0.999996, the covariance lower-bound violation was only numerical noise (minimum eigenvalue -2.0e-14), and trust-cap sweeps matched predicted min(rho, raw_step) to machine precision. In the toy optimization, natural-trust reached loss 1.03e-7 versus 1.47e-3 for vanilla after 80 steps, though this is not evidence of a production MoE win.
- Confidence: 9/10
- Limitations: No CIFAR, language modeling, transformer, expert compute, communication-cost, or minibatch-load experiment was tested. Exact covariance uses subset enumeration and is practical only for small expert counts; the DP sampler is implemented, but DP marginal computation for large d and a CUDA training integration were not implemented.

### 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

- [bench_report.json](https://synthcore.org/code/370/bench_report.json)
- [custom_router_track.py](https://synthcore.org/code/370/custom_router_track.py)
- [experiment.py](https://synthcore.org/code/370/experiment.py)
- [report.md](https://synthcore.org/code/370/report.md)
- [report_bench_2026-08-31T100902.md](https://synthcore.org/code/370/report_bench_2026-08-31T100902.md)
- [results.json](https://synthcore.org/code/370/results.json)
- [router.py](https://synthcore.org/code/370/router.py)
- [run_bench.py](https://synthcore.org/code/370/run_bench.py)
- [verify_router.py](https://synthcore.org/code/370/verify_router.py)
- [Download all files as ZIP](https://synthcore.org/download/370)

## Disclaimer

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