Unverified 2026

Crystal Parenthesis Expert Balancer

Implementation & benchmark of arXiv:2607.12232 — Contractions and applications of crystal skeletons: Young quasisymmetric and Stanley symmetric functions

Usefulness6/10
Difficulty5/10
Novelty7/10

Source paper: Contractions and applications of crystal skeletons: Young quasisymmetric and Stanley symmetric functions arXiv:2607.12232 ⓘ · analyzed Aug 30, 2026

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

Idea description

Use the paper's crystal parenthesis matching as a deterministic local search over a sequence of MoE expert assignments. For adjacent experts i and i+1, pair assignments according to the crystal rule and move one unpaired i to i+1 only when this reduces expert-load imbalance. This provides a structured alternative to relying exclusively on an auxiliary load-balancing loss.

Formulas

$$f_i(i^r(i+1)^s)=\begin{cases}i^{r-1}(i+1)^{s+1}&\text{if }r>0,\\0&\text{otherwise,}\end{cases}$$
$$s_i(i^r(i+1)^s)=i^s(i+1)^r,$$
$$\Delta_i=(L_i-L_{i+1})^2-((L_i-1)-(L_{i+1}+1))^2,$$
$$w'=f_i(w)\quad\text{only if }r>0\text{ and }\Delta_i<0.$$

Mathematical statement

For a word w of expert labels, select adjacent labels i and i+1. In the subword containing only these labels, interpret i+1 as a left parenthesis and i as a right parenthesis, then greedily pair matching parentheses. The unpaired subword is i^r(i+1)^s for integers r,s greater than or equal to zero. The paper's lowering operator is f_i(i^r(i+1)^s)=i^{r-1}(i+1)^{s+1} when r>0 and 0 otherwise, so it moves exactly one unmatched assignment from expert i to expert i+1. The paper also defines the adjacent symmetric-group action s_i(i^r(i+1)^s)=i^s(i+1)^r, which swaps the unmatched blocks while preserving their total size. Here w is the ordered expert-assignment sequence, r and s are unmatched counts, and L_j is the current load of expert j. The ML adaptation applies f_i only when L_i is sufficiently larger than L_{i+1}.

Implementation notes

Integrate this after top-1 or top-2 router selection and before dispatching tokens to experts. Let router logits be g in R^(B times T times E), set w_(b,t)=argmax_j g_(b,t,j), and compute L_j as the number of tokens assigned to expert j. For every adjacent pair (i,i+1), extract positions whose labels are i or i+1 and scan them in sequence order. Maintain a stack: push an i+1; when an i arrives and the stack is nonempty, cancel one pair; otherwise record the i as unmatched. The remaining unmatched labels have the required form i^r(i+1)^s. If L_i exceeds L_(i+1) by at least two, change one unmatched i to i+1, subject to expert capacity. Process pairs in descending load difference and stop after K changes, where K is a small fraction of the batch size. The matching and legal move come directly from the paper; capacity, pair ordering, and the threshold are empirical choices. For differentiability, use the modified assignment for dispatch and retain the original router logits for backpropagation, optionally adding a straight-through gate correction. First test a 125M-parameter Transformer with top-1 Switch-style routing on a small language-model corpus. Compare against standard auxiliary load loss at equal capacity. Measure expert-load coefficient of variation, overflow and dropped-token rates, throughput, and validation perplexity. Success means at least 30 percent fewer dropped tokens and lower load variance without slower training or worse 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.