# Refinement-consistent bipartite routing

- ID: 2547
- Canonical URL: https://synthcore.org/idea/2547/refinement-consistent-bipartite-routing
- API JSON: https://synthcore.org/api/idea/2547.json
- API Markdown: https://synthcore.org/api/idea/2547.md
- Verification status: unverified
- Source: [arXiv:2608.18870](https://arxiv.org/abs/2608.18870)
- Category: architecture
- Solves: stability, scalability, memory
- ML areas: moe-routing, attention, graph-nn
- Math tags: combinatorics, graph-theory, measure-theory, optimization
- Ratings: usefulness 6/10; difficulty 6/10; novelty 6/10

## Idea description

Represent hierarchical routing decisions by one weighted bipartite graph between parent experts or regions and fine cells or token groups. Select a regularized edge set once, then derive both coarse parent activation and fine-grained routing from it, preventing later refinement from invalidating earlier load balancing.

## Mathematical statement

The paper defines a labelled family of carriers \(\mathcal F\), a shading \(Y(F)\subset F\) for every label, total shaded mass \(M(Y)=\sum_{F\in\mathcal F}|Y(F)|\), total carrier mass \(D(\mathcal F)=\sum_{F\in\mathcal F}|F|\), physical union \(U(\mathcal F,Y)=\bigcup_{F\in\mathcal F}Y(F)\), density \(\lambda(\mathcal F,Y)=M(Y)/D(\mathcal F)\), and multiplicity \(\mu(\mathcal F,Y)=M(Y)/|U(\mathcal F,Y)|\). The cellular construction places positive child mass on weighted edges \((p,c)\) between labelled parents \(p\) and atomic cells \(c\); a single regularized edge set defines both child and parent shadings and supports later whole-incidence selections. The neural adaptation uses edge weights \(w_{pc}\ge 0\), parent mass \(a_p=\sum_c w_{pc}\), cell mass \(b_c=\sum_p w_{pc}\), and a selected edge set \(E'\). Coarse routing is \(r_p=\mathbf 1\{\exists c:(p,c)\in E'\}\), while fine routing is \(s_{pc}=\mathbf 1\{(p,c)\in E'\}\); deriving both from \(E'\) enforces exact compatibility. A practical regularizer constrains selected degrees \(d_p=\sum_c s_{pc}\) and \(d_c=\sum_p s_{pc}\), while retaining a prescribed fraction of total weight \(\sum_{(p,c)\in E'}w_{pc}\).

## Key formulas

- $$U(\mathcal{F},Y)=\bigcup_{F\in\mathcal{F}}Y(F),\qquad M(Y)=\sum_{F\in\mathcal{F}}|Y(F)|,\qquad D(\mathcal{F})=\sum_{F\in\mathcal{F}}|F|,$$
- $$\lambda(\mathcal{F},Y)=\frac{M(Y)}{D(\mathcal{F})},\qquad \mu(\mathcal{F},Y)=\frac{M(Y)}{|U(\mathcal{F},Y)|},$$
- $$a_p=\sum_{c}w_{pc},\qquad b_c=\sum_{p}w_{pc},\qquad W(E')=\sum_{(p,c)\in E'}w_{pc},$$
- $$\max_{E'\subseteq E}W(E')\quad\text{s.t.}\quad d_p=\sum_c\mathbf 1[(p,c)\in E']\le D_p,\quad d_c=\sum_p\mathbf 1[(p,c)\in E']\le D_c,$$

## Implementation notes

Integrate this into a hierarchical sparse MoE or region-attention router. At each layer, partition tokens into fine cells \(c\), such as contiguous blocks of 16 tokens or learned clusters, and compute parent logits for experts or coarse regions \(p\). Set \(w_{pc}=\exp(z_{pc}/\tau)\) for candidate incidences, retaining only the top \(K\) edges per cell. Build a weighted bipartite graph with parents on the left and cells on the right. Select one edge set \(E'\) using greedy capacity-aware filtering: sort edges by descending \(w_{pc}/(1+\alpha d_p+\beta d_c)\); accept an edge only if the parent degree is below \(D_p\), the cell degree is below \(D_c\), and the retained mass can still reach \(\rho\sum_{p,c}w_{pc}\). If differentiability is needed, use the hard set for dispatch and a straight-through estimator, or use sigmoid gates in the backward pass. Define parent activation from the same selected edges, \(r_p=\mathbf 1[d_p>0]\), and fine routing weights by \(q_{pc}=s_{pc}w_{pc}/\sum_{p'}s_{p'c}w_{p'c}\). Never independently top-k parents after selecting cells, because that breaks compatibility. Compute \(a_p\), \(b_c\), retained mass, degree variance, and dropped mass exactly. Also split every cell a second time and measure the fraction of parent assignments that become invalid; the intended benefit is refinement stability. Start with a 12-layer, 125M-parameter Transformer on Wikitext-103 using 8 experts. Compare standard top-2 MoE routing against this method at equal active FLOPs. Success means lower expert-load variance and fewer overflow drops without worse perplexity, or equal perplexity with at least 10% fewer active expert evaluations.

## Disclaimer

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