# Tree-Structured Exact Expert Router

- ID: 76
- Canonical URL: https://synthcore.org/idea/76/tree-structured-exact-expert-router
- API JSON: https://synthcore.org/api/idea/76.json
- API Markdown: https://synthcore.org/api/idea/76.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.22815](https://arxiv.org/abs/2608.22815)
- Category: architecture
- Solves: scalability, accuracy, speedup
- ML areas: moe-routing, architecture, inference-speedup
- Math tags: graph-theory, combinatorics, quadratic-forms, optimization
- Ratings: usefulness 7/10; difficulty 7/10; novelty 8/10

## Idea description

Replace independent top-k expert selection with a decision-diagram router that optimizes a quadratic surrogate over binary expert activations and continuous assignment weights. When expert redundancy or communication costs form a tree, partial routing decisions are merged whenever they have the same separator state, turning exponentially many candidate masks into a dynamic program over a small number of graph cuts.

## Mathematical statement

The paper optimizes the gated quadratic set X_F,Z = {(x_0,x,z): z is in Z subset of {0,1}^n, ||F^T x||_2^2 <= x_0, and x_i(1-z_i)=0 for every i}, with objective d^T x + c^T z + x_0; after eliminating x_0 this is d^T x + c^T z + ||F^T x||_2^2. Here z_i indicates whether expert i is active, x_i is its continuous routing weight, F is a feature or cost factor, d is a linear routing preference, and c is an activation penalty. For Q = FF^T, Theorem 2 states that if supp(Q) is a connected tree, the state after a partial assignment v in {0,1}^{ell-1} depends only on the one-cut S = S_1^ell(v), with H^ell(v) = F_[ell:n] - Q_[ell:n],S (Q_S,S)^(-1) F_S. Thus different partial masks sharing the separator can be merged without changing the downstream quadratic problem. The adapted router uses this state-equivalence rule to compute the minimum-cost feasible mask and routing weights.

## Key formulas

- $$X_{\bm{F},Z}=\left\{(x_0,\bm{x},\bm{z})\in\mathbb{R}\times\mathbb{R}^{n}\times Z:\|\bm{F}^{\top}\bm{x}\|_{2}^{2}\leq x_0,\;\bm{x}\circ(\bm{1}-\bm{z})=\bm{0}\right\}.$$
- $$\min_{\substack{\bm{x}\in\mathbb{R}^{n},\bm{z}\in\{0,1\}^{n}\\ \bm{x}\circ(\bm{1}-\bm{z})=\bm{0}}}\;\bm{d}^{\top}\bm{x}+\bm{c}^{\top}\bm{z}+\left\|\bm{F}^{\top}\bm{x}\right\|_{2}^{2}.$$
- $$\bm{H^{\ell}}(\bm{v})=\bm{F_{[\ell:n]}}-\bm{Q_{[\ell:n],S}}\left(\bm{Q_{S,S}}\right)^{-1}\bm{F_{S}},\qquad S=S_{1}^{\ell}(\bm{v}),\quad \bm{Q}=\bm{F}\bm{F}^{\top}.$$
- $$\operatorname{DP}_{\ell+1}(s')=\min_{s\to s'\text{ by }z_{\ell}\in\{0,1\}}\left[\operatorname{DP}_{\ell}(s)+\Delta_{\ell}(s,z_{\ell})\right],\qquad s=\bigl(S_{1}^{\ell}(v),\bm{H}^{\ell}(v)\bigr).$$

## Implementation notes

Integrate this at the MoE router, before dispatching tokens to experts. Use one routing problem per token group or microbatch, with n experts and binary z_i indicating whether expert i may receive traffic. Build a symmetric interaction matrix Q from a calibration set: Q_ij can be an empirical covariance or cosine-similarity penalty between expert outputs, augmented with diagonal dispatch costs. Factor Q approximately as F F^T, or use a low-rank factor F directly. Let d_i be the negative router logit for expert i, c_i be the fixed activation or communication cost, and x_i be a nonnegative routing weight. Add sum_i x_i = 1, 0 <= x_i <= U_i z_i, and at most k active experts. Choose an expert ordering for which supp(Q) is a tree or has small separators. Enumerate partial binary assignments in this order. For every partial assignment v, compute its separator S_1^ell(v) and state H^ell(v) using H^ell(v) = F_[ell:n] - Q_[ell:n],S Q_S,S^(-1) F_S; hash states with identical separators and tolerance-rounded H matrices, and retain only the lowest-cost representative. For every retained state, solve the small local convex quadratic problem over newly activated experts, then propagate its cost. Backtrack the best terminal state to obtain z and x, and dispatch only to experts with z_i = 1. The separator rule and quadratic state update come from the paper; Q estimation, state tolerances, and ordering are empirical. First test on an 8-expert Switch-Transformer-style model using CIFAR-100 or WikiText-2, comparing against top-2 routing at equal active experts. Measure router wall time, expert FLOPs, load imbalance, validation loss, and unique state count. Success requires lower redundancy or communication and equal-or-better accuracy without router overhead dominating dispatch savings.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built an 8-expert path-tree quadratic router MVP, with exact support optimization versus standard top-2 routing. The separator-state formula and Schur-complement residual identity both passed numerical checks to machine precision; exact routing improved mean surrogate objective by 0.01938, but required about 31.5x the router time and slightly worsened load CV. Thus the quality signal is real on this synthetic setup, but the promised efficient routing win was not demonstrated because the MVP’s exact search is exhaustive and overhead dominates.

### Mechanism check

- Verdict: Built an 8-expert path-tree quadratic router MVP, with exact support optimization versus standard top-2 routing. The separator-state formula and Schur-complement residual identity both passed numerical checks to machine precision; exact routing improved mean surrogate objective by 0.01938, but required about 31.5x the router time and slightly worsened load CV. Thus the quality signal is real on this synthetic setup, but the promised efficient routing win was not demonstrated because the MVP’s exact search is exhaustive and overhead dominates.
- Confidence: 9/10
- Limitations: Synthetic quadratic objective only; no trained MoE, CIFAR/WikiText, expert-output calibration, communication measurement, non-path trees, or actual merged-state dynamic program was tested. The exact support solver uses scipy SLSQP and exhaustive masks, so its runtime is a correctness reference rather than a production router.

## Artifacts

- [report.md](https://synthcore.org/code/23/report.md)
- [results.json](https://synthcore.org/code/23/results.json)
- [tree_router_experiment.py](https://synthcore.org/code/23/tree_router_experiment.py)
- [Download all files as ZIP](https://synthcore.org/download/23)

## Disclaimer

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