Coset-aware MoE routing repair
Implementation & benchmark of arXiv:2607.27870 — On the number of factorable induced subgraphs
Source paper: On the number of factorable induced subgraphs arXiv:2607.27870 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Add an integer-lattice feasibility layer after ordinary top-1 or top-2 MoE routing. The router first produces its usual expert assignments, then minimally changes a small number of low-confidence assignments so the batch count vector lies in a prescribed lattice or desired coset, eliminating persistent modular load imbalance that ordinary auxiliary losses may not detect.
Formulas
Mathematical statement
For a partition \(\mathcal P=(P_1,\ldots,P_d)\), the paper represents an object by its index vector \(\mathbf i_{\mathcal P}(S)=(|S\cap P_1|,\ldots,|S\cap P_d|)\in\mathbb Z^d\). For an \(r\)-vertex packed object, the maximal admissible lattice is \(L_{\max}^d=\{\mathbf v\in\mathbb Z^d:r\mid |\mathbf v|\}\), where \(|\mathbf v|=\sum_{j=1}^d v_j\). Given a sublattice \(L\subseteq L_{\max}^d\), the residual obstruction is the finite coset group \(Q(\mathcal P,L)=L_{\max}^d/L\), whose order is \(q=|Q|\). We adapt this by taking \(d\) to be the number of experts, \(\mathbf c=(c_1,\ldots,c_d)\) to be the integer token-count vector in a microbatch, and \(L\) to encode desired divisibility or grouped-capacity constraints. The routing repair solves \(\min_{\Delta\in\mathbb Z^d}\|\Delta\|_1\) subject to \(\mathbf c+\Delta\in L+\mathbf a\), where \(\mathbf a\) is the target coset and \(\Delta\) is realizable by reassigning tokens. The finite quotient makes the constraint testable by residues rather than by an expensive global integer program.
Implementation notes
Integrate this immediately after the ordinary router chooses top-1 or top-2 experts and before dispatch. Use microbatches of B tokens and let c[j] be the number assigned to expert j. Start with a practical lattice: partition the E experts into groups G_1,...,G_g and require each group total to be divisible by r, or require each expert count to lie in a target residue class modulo m; encode these linear congruences as A c = b (mod m). This is the finite-coset version of c belonging to L+a. Compute residues from the current c. If the target coset is violated, select at most K low-confidence tokens whose second-best experts are available, and greedily apply swaps token t: expert i to expert j, updating c by e_j-e_i. Choose the swap with largest routing-margin loss per unit residue correction, where the margin is the difference between the chosen and alternative gate logits. Stop when A c=b mod m or K swaps are exhausted. In pseudocode: logits=g(x); choices=topk(logits); c=count(choices); while residue(Ac-b)!=0 and swaps<K: enumerate feasible alternatives; choose argmin(delta_margin / residue_progress); swap; update c. The paper supplies the index-vector, lattice, and quotient formulation; the engineer estimates the appropriate lattice empirically by measuring recurring count residues and selecting m or group constraints that correlate with overflow. The first experiment should use a 12-expert Switch-Transformer-style layer on CIFAR-100 or a small language-model corpus, comparing standard load-balancing loss against the same router plus repair at equal capacity factor. Measure overflow/drop rate, coefficient of variation of expert loads, auxiliary-loss contribution, training stability, and validation accuracy. A successful signal is substantially fewer dropped tokens and less batch-to-batch load variance with no meaningful increase in routing cost or degradation in perplexity.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.