# Matroid-Capacity Router

- ID: 2402
- Canonical URL: https://synthcore.org/idea/2402/matroid-capacity-router
- API JSON: https://synthcore.org/api/idea/2402.json
- API Markdown: https://synthcore.org/api/idea/2402.md
- Verification status: unverified
- Source: [arXiv:2608.16464](https://arxiv.org/abs/2608.16464)
- Category: architecture
- Solves: stability, scalability, accuracy
- ML areas: moe-routing, attention, graph-nn, regularization
- Math tags: combinatorics, graph-theory, optimization, measure-theory, submodularity
- Ratings: usefulness 5/10; difficulty 6/10; novelty 4/10

## Idea description

Replace independent top-k expert decisions by a global fractional routing problem that enforces token-side and expert-side capacities together with an additional diversity constraint represented by a partition or laminar matroid. Use the resulting Hall-type deficiency certificate to identify overloaded token subsets and penalize the actual structural cause of routing failure rather than relying only on an aggregate load-balancing loss.

## Mathematical statement

The paper uses submodularity, defined by $$f(X)+f(Y)\geq f(X\cap Y)+f(X\cup Y),$$ to define rank functions and derive matroid intersection min–max formulas. For the concrete bipartite capacity case, let $(T,\eta)$ be the token measure space, $(S,
u)$ the expert measure space, $E\subseteq T    imes S$ the allowed routing edges, $b(t)\geq0$ the demand of token $t$, $c(s)\geq0$ the capacity of expert $s$, and $d_E(A,s)=\eta(\{t\in A:(t,s)\in E\})$ the measure of neighbors of expert $s$ inside token subset $A\subseteq T$. Theorem 7.10 gives $$m_E(b,c)=\min_{A\subseteq T}\left\{\int_{T\setminus A}b(t)\,d\eta(t)+\int_S\min\{c(s),d_E(A,s)\}\,d\nu(s)\right\},$$ where $m_E(b,c)$ is the maximum feasible matching mass. The identity $$\int_{J'}\min\{u,v\}\,d\rho=\min_{C\in\Sigma'}\left\{\int_Cu\,d\rho+\int_{J'\setminus C}v\,d\rho\right\}$$ explains the subset certificate. In a finite minibatch, replace integrals by sums. Add a partition or laminar matroid with rank function $r(G)$, where every group $G$ of token-expert edges obeys $\sum_{(t,s)\in G}x_{ts}\leq r(G)$.

## Key formulas

- $$f(X)+f(Y)\geq f(X\cap Y)+f(X\cup Y)$$
- $$m_E(b,c)=\min_{A\subseteq T}\left\{\int_{T\setminus A}b(t)\,d\eta(t)+\int_S\min\{c(s),d_E(A,s)\}\,d\nu(s)\right\}$$
- $$\int_{J'}\min\{u,v\}\,d\rho=\min_{C\in\Sigma'}\left\{\int_Cu\,d\rho+\int_{J'\setminus C}v\,d\rho\right\}$$
- $$\max_{x\geq0}\ \sum_{(t,s)\in E}x_{ts}\quad\mathrm{s.t.}\quad \sum_sx_{ts}\leq b_t,\ \sum_tx_{ts}\leq c_s,\ \sum_{(t,s)\in G}x_{ts}\leq r(G)\ \forall G$$

## Implementation notes

Integrate the method into a mixture-of-experts router immediately after computing router logits $z_{ts}$ and before dispatching tokens to experts. For a minibatch of $n$ tokens and $m$ experts, compute $p_{ts}=\operatorname{softmax}_s(z_{ts}/\tau)$, retain the top-$q$ candidate experts per token, and call the retained edge set $E$. Set $b_t=1$ for every token and $c_s=\rho n/m$ for expert capacity. Define groups $G$ for expert families, devices, or hierarchical routing regions; assign each group a rank $r(G)$, with nested groups forming a laminar family. Use this MVP procedure: initialize $x_{ts}=p_{ts}$ on $E$; repeatedly project $x$ onto token constraints $\sum_sx_{ts}\leq1$, expert constraints $\sum_tx_{ts}\leq c_s$, and group constraints $\sum_{(t,s)\in G}x_{ts}\leq r(G)$ using Dykstra projections or alternating multiplicative rescaling; then dispatch each token to its largest $k$ projected entries. During training, use a straight-through estimator through the discrete dispatch and add a deficiency penalty. For finite batches, approximate the paper’s min–max certificate by running a small max-flow/min-cut or linear-program solver on the sparse bipartite graph, and compute $d_E(A,s)=|\{t\in A:(t,s)\in E\}|$. The exact mathematical components are the capacity constraints and subset deficiency objective; projection iterations, temperature, penalty coefficient, and certificate frequency are empirical choices. First test a 4-layer, 16-expert Switch-Transformer-style model with top-2 routing on WikiText-103 or a small C4 subset. Compare against top-2 routing with the standard auxiliary load-balancing loss at equal model FLOPs. Measure dropped-token rate, expert-load variance, group-capacity violations, routing overhead, and validation perplexity. The method succeeds if it substantially reduces overflow and load variance without worsening perplexity or making routing slower overall.

## Disclaimer

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