Matroid-Capacity Router

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.