Why do Mixture-of-Experts models route tokens the way they do? The gating mechanism at the heart of MoE architectures has long been treated as a learned heuristic, something that works well in practice but resists principled explanation. A new paper, "Is MoE Routing a Huffman Code? Discovering the Frequency-Diversity Law in Chain-of-Thought", proposes a surprisingly clean answer: optimised MoE routers spontaneously implement Huffman coding, allocating sparse expert resources to common tokens and invoking broader, more diverse expert committees for rare or complex reasoning steps. The claim is bold, but the empirical evidence presented is harder to dismiss than the framing might suggest.
The Core Claim: Routing as Source Coding
Huffman coding assigns shorter codewords to high-frequency symbols and longer ones to low-frequency symbols, minimising expected description length. The analogy to MoE routing is direct: if the number of distinct experts activated per reasoning step scales with the rarity of the semantic operation being performed, then the router is effectively implementing a variable-length code over the space of computational operations.
The authors formalise this as the Frequency-Diversity Law: the mean number of unique experts activated per layer for a given operation type o is proportional to the negative log-probability of that operation type, i.e. ū(o) ∝ −log p(o). They test this on Gemma-4-27B-A4B and Phi-3.5-MoE across four mathematical reasoning datasets (GSM8K, MATH, AQuA, CompMath-MCQ), classifying chain-of-thought steps by semantic operation type using a keyword classifier. The result is a Spearman correlation of ρ = 1.00 in both models, with p < 0.005. That is a striking result, though readers should note it is computed over only four operation-type categories, which limits the degrees of freedom available to the rank correlation.
Key Contributions
- The Frequency-Diversity Law: A falsifiable, quantitative prediction that expert diversity per step tracks operation rarity, grounded in Minimum Description Length (MDL) optimality rather than ad hoc intuition.
- Routing fingerprint consistency: Across all three architectures tested, steps performing the same arithmetic operation type (e.g. division) drawn from entirely different problems activate near-identical expert subsets (Jaccard similarity up to 0.947). Cross-operation pairs show substantially lower overlap. This holds with Mann-Whitney p ≤ 10⁻¹⁶³ across all 12 model-dataset combinations, suggesting the router encodes what computation is happening, not just which problem is being solved.
- Identification of the redundancy trap: Qwen3.5-35B-A3B, with an expert sparsity ratio of k/E = 3.1%, shows an anti-Huffman signature (Pearson r = −0.631 at baseline). The authors attribute this to functional redundancy induced by aggressive load-balancing: when the effective expert pool is large relative to the number of active experts per token, load-balancing loss forces the model to spread activations across near-duplicate experts rather than developing genuine specialisation.
- Subset Difference Pruning (SDP): A training-free method that identifies redundant expert pairs via cosine similarity of co-activation profiles, then masks the lower-frequency member by setting its router logit to −∞ at inference time. No weights are modified.
Methodology and Results
The experimental setup is straightforward. Chain-of-thought traces from correct model outputs are segmented by newline into reasoning steps, each classified into one of four operation types. Expert activation sets are recorded per layer per step, and the Frequency-Diversity Law is tested via scatter plots of mean unique experts against operation rarity.
For Qwen3.5-35B-A3B, SDP is applied at 10% and 20% pruning levels. The 10% pruned model retains 91.9% accuracy on GSM8K (baseline: 93.6%) while flipping the Huffman correlation from r = −0.631 to r = +0.567. The 20% pruned model achieves r = +0.533 but drops to 75.7% accuracy, suggesting the 10% level sits near the boundary of tolerable redundancy removal. Importantly, Figure 5 shows that the pruned experts account for a disproportionate share of activations relative to their count, confirming they are actively used functional duplicates rather than dormant parameters.
The routing regime taxonomy introduced in Table 1 is a useful conceptual contribution: Gemma (k/E = 6.25%) shows clean monotonic decline in expert diversity across the reasoning trace; Phi (k/E = 12.5%) shows stable low-entropy cluster pairs; Qwen (k/E = 3.1%) shows an inverted-U trajectory where diversity peaks mid-trace. The authors argue this inverted-U is the signature of functional redundancy rather than genuine semantic diversity, and the SDP results support that interpretation.
Limitations and Open Questions
Several aspects of the methodology warrant scrutiny. The keyword classifier for operation types is coarse: four categories with hard-coded trigger words will misclassify steps involving implicit arithmetic or multi-step operations within a single sentence. The Spearman ρ = 1.00 result, while striking, is computed over exactly four data points per model. A rank correlation over four points requires only monotonicity, not a tight linear relationship, so the statistical claim is weaker than the presentation implies. The authors acknowledge this indirectly by reporting Pearson r separately for the Qwen analysis, but the headline figure deserves more careful framing.
The Huffman analogy is also somewhat loose at the architectural level. Huffman codes are prefix-free and uniquely decodable; the expert activation patterns here are sets, not sequences, and the "code length" is operationalised as cardinality of the active expert set rather than bit-length of a routing decision. The information-theoretic mapping is suggestive rather than formally tight, and the paper would benefit from a more explicit treatment of where the analogy holds and where it breaks down.
SDP is training-free and simple, which is a genuine practical advantage. But the evaluation is limited to GSM8K, and the accuracy drop at 20% pruning is substantial enough to raise questions about whether the Huffman correlation improvement at that level is actually useful. Testing on harder reasoning benchmarks, or on tasks outside mathematics, would strengthen the universality claim considerably.
The proposed diagnostic, monitoring Huffman correlation r during training to detect load-balancing pathologies, is an appealing idea. If r turns persistently negative during training, it signals that functional duplicates are accumulating faster than genuine specialisation develops. This requires no downstream evaluation and could be computed cheaply from activation logs. Whether it is actionable in practice, for example by dynamically adjusting the load-balancing loss coefficient, is an open question the paper leaves for future work.
The broader implication, that MoE training should target MDL optimality rather than uniform load-balancing, is a meaningful reframing of an active design debate. Current practice treats load-balancing as a necessary regulariser to prevent expert collapse; this paper argues it can become a source of inefficiency when the sparsity ratio is too low. The effective sparsity range of 5-13% identified here as conducive to Huffman-efficient routing is a concrete, testable design recommendation, even if the supporting evidence is currently limited to three models and one task domain.
Full details, including the pruning algorithm, effective sparsity calculations, and per-operation-type statistics, are available in the appendices of the paper on arXiv.