# Polymatroid Exchange Router

- ID: 2434
- Canonical URL: https://synthcore.org/idea/2434/polymatroid-exchange-router
- API JSON: https://synthcore.org/api/idea/2434.json
- API Markdown: https://synthcore.org/api/idea/2434.md
- Verification status: unverified
- Source: [arXiv:2608.17130](https://arxiv.org/abs/2608.17130)
- Category: architecture
- Solves: scalability, stability, accuracy
- ML areas: moe-routing, transformer
- Math tags: combinatorics, convex-analysis, optimization
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Replace overflow dropping in a mixture-of-experts layer with a discrete-convex load repair procedure. The router first chooses experts from neural logits, then applies capacity-aware exchange moves that preserve the total number of dispatched tokens and monotonically improve the routing objective whenever a feasible swap exists.

## Mathematical statement

The paper defines the integer simplex $\Delta_n^r=\{\alpha\in\mathbb{Z}_{\geq0}^n:\sum_{i=1}^n\alpha_i=r\}$ and an M-convex base set $J\subseteq\Delta_n^r$. Its symmetric exchange axiom states that for every $\alpha,\beta\in J$ and every index $i$ with $\alpha_i<\beta_i$, there exists $j$ with $\alpha_j>\beta_j$ such that $\alpha+e_i-e_j\in J$ and $\beta-e_i+e_j\in J$. Here $\alpha_i$ is the number of tokens assigned to expert $i$, $r$ is the number of routed tokens, and $e_i$ is the $i$th standard basis vector. A cage is a coordinatewise upper-bound vector $\kappa\in\mathbb{Z}_{\geq0}^n$; the caged feasible region is $J_\kappa=\{\alpha\in J:\alpha_i\leq\kappa_i\ \forall i\}$. The paper's caged retraction takes projected bases and retains maximal projected bases; an implementable discrete version is $R_\kappa(J)=\max_{\leq}\{\alpha\wedge\kappa:\alpha\in J\}$, where $(\alpha\wedge\kappa)_i=\min(\alpha_i,\kappa_i)$ and maximality is coordinatewise. The exchange axiom supplies local token moves: moving one token from expert $j$ to expert $i$ changes the load vector by $e_i-e_j$ while remaining in the polymatroidal feasible family.

## Key formulas

- $$\Delta_n^r=\left\{\alpha\in\mathbb{Z}_{\geq 0}^n\mid \alpha_1+\cdots+\alpha_n=r\right\}.$$
- $$\alpha_i<\beta_i\ \Longrightarrow\ \exists j\text{ with }\alpha_j>\beta_j\text{ such that }\alpha+e_i-e_j,\ \beta-e_i+e_j\in J.$$
- $$J_\kappa=\left\{\alpha\in J:\alpha_i\leq\kappa_i\ \text{for every }i\right\},\qquad R_\kappa(J)=\max_{\leq}\left\{\alpha\wedge\kappa:\alpha\in J\right\},\quad (\alpha\wedge\kappa)_i=\min(\alpha_i,\kappa_i).$$
- $$\alpha' = \alpha+e_i-e_j,\qquad \Delta S=S(\alpha')-S(\alpha)>0.$$

## Implementation notes

Integrate this into the dispatch stage of a top-1 or top-2 MoE layer, after router logits have been computed and before expert inputs are gathered. Let there be $n$ experts and $r$ tokens in a batch. Compute router scores $s_{t,i}$, form an initial assignment by top-1 selection or greedily assign top-2 slots, and let $\alpha_i$ be the resulting expert loads. Set the cage to $\kappa_i=\lceil c_i r\rceil$, where $c_i$ is the desired capacity fraction; reserve unavoidable slack if $\sum_i\kappa_i<r$. Construct candidate exchanges for every overloaded expert $j$ and under-capacity expert $i$. For each token $t$ currently assigned to $j$, calculate the score gain $g_{t,i}=s_{t,i}-s_{t,j}$ and retain the highest-gain candidates. The repair loop is: (1) find overloaded $j$; (2) choose an underloaded $i$ and token $t$ maximizing $g_{t,i}$; (3) propose $\alpha\leftarrow\alpha+e_i-e_j$; (4) accept only if $\alpha_i+1\leq\kappa_i$, the polymatroid feasibility oracle accepts the move, and $g_{t,i}>0$; (5) update the token assignment and repeat until capacities are met or no improving move remains. The MVP can use the uniform polymatroid, checking only nonnegativity and cage bounds; the stronger experiment should add partition or laminar constraints for expert groups. The mathematical inputs are the integer exchange rule and capacity cage; candidate search and score objective are engineering choices. Benchmark a small Switch-Transformer-style top-1 model against overflow dropping and standard capacity-factor routing. Record dropped-token fraction, all-to-all padding volume, auxiliary load-balance loss, router entropy, expert utilization variance, wall-clock dispatch time, and perplexity at equal training FLOPs. Success means near-zero dropped tokens, lower padding, and no perplexity degradation with less than 10% routing overhead.

## Disclaimer

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