# Permutation-invariant hyperedge load balancing - ID: 1334 - Canonical URL: https://synthcore.org/idea/1334/permutation-invariant-hyperedge-load-balancing - API JSON: https://synthcore.org/api/idea/1334.json - API Markdown: https://synthcore.org/api/idea/1334.md - Verification status: unverified - Source: [arXiv:2607.23778](https://arxiv.org/abs/2607.23778) - Category: regularization - Solves: accuracy, stability, generalization - ML areas: moe-routing, regularization, training - Math tags: combinatorics, optimization, graph-theory - Ratings: usefulness 5/10; difficulty 4/10; novelty 6/10 ## Idea description Replace ordinary expert-load balancing with an all-pairs discrepancy penalty for each structured expert bundle. The penalty forces every class represented in a bundle to receive similar assignment mass, avoiding dependence on an arbitrary cyclic ordering and exposing imbalances between nonadjacent classes. ## Mathematical statement For a hyperedge e, let |e|=k be its number of vertices or classes, let (v_1,...,v_k) be any ordering of those vertices, and let q_{v,e} be the number of class-v items assigned to hyperedge e. The paper contrasts the cyclic penalty L_{1,e}(q)=\sum_{i=1}^{|e|}(q_{v_{i+1},e}-q_{v_i,e})^2, with v_{|e|+1}=v_1, against the permutation-invariant all-pairs penalty L_{2,e}(q)=\sum_{\{u,v\}\in e^2}(q_{u,e}-q_{v,e})^2, where e^2 denotes all unordered pairs of distinct vertices in e. The ML loss uses expected assignment counts q_{v,e}=\sum_{t=1}^{B}\mathbf{1}[c_t=v]p_{t,e}, where c_t is the class or routing stratum of token t and p_{t,e} is its router probability for hyperedge e. The total regularizer is R(q)=\sum_{e\in E}L_{2,e}(q), optionally normalized by the total mass in e. Since every unordered pair appears, L_{2,e}=0 exactly when all class loads in e are equal, and the result is invariant to relabeling or reordering the vertices. ## Key formulas - $$L_{1,e}(q)=\sum_{i=1}^{|e|}(q_{v_{i+1},e}-q_{v_i,e})^{2},\qquad v_{|e|+1}=v_1$$ - $$L_{2,e}(q)=\sum_{\{u,v\}\in e^{2}}(q_{u,e}-q_{v,e})^{2}$$ - $$q_{v,e}=\sum_{t=1}^{B}\mathbf{1}[c_t=v]p_{t,e},\qquad \mathcal{L}=\mathcal{L}_{\mathrm{task}}+\lambda\sum_{e\in E}\frac{L_{2,e}(q)}{\left(\sum_{v\in e}q_{v,e}+\varepsilon\right)^2}$$ ## Implementation notes Integrate this into the router-loss path of a structured MoE. Define a finite set E of admissible expert bundles; each bundle e contains the class strata that are allowed to share or jointly activate that bundle. For every minibatch, attach each token t to a stratum c_t, such as domain, language, modality, label bucket, or sequence-position group. The router produces logits z_{t,e} and probabilities p_{t,e}=softmax_e(z_t/ au). Compute expected counts q[v,e]=sum_t 1[c_t=v]p[t,e] for every v in e. Then compute the paper's all-pairs quantity L2[e] by looping over unordered pairs (u,v) in e and accumulating (q[u,e]-q[v,e])^2. Add lambda times the normalized sum over bundles to the task loss; use epsilon in the denominator to avoid instability for unused bundles. Pseudocode: logits=router(x); p=softmax(logits); q=zeros(|V|,|E|); for t,e: q[c[t],e]+=p[t,e]; balance=0; for e in E: for u