MoE routing mirrors Huffman coding for efficient expert allocation

A new paper by Ching-Chieh Tsao, Zhuoyi Lin, and Wenya Wang reveals that Mixture-of-Experts (MoE) routing in large language models follows a fundamental information-theoretic principle: it behaves like Huffman coding. The authors introduce the Frequency-Diversity Law, which shows that state-of-the-art MoE models such as Phi-3.5-MoE and Gemma-4-27B-A4B spontaneously allocate sparse expert resources to high-frequency tokens while reserving diverse expert committees for rare, complex chain-of-thought trajectories. This discovery transforms routing from a black-box heuristic into a measurable compression mechanism, where short, efficient routing codes handle common information and longer, diverse codes handle rare, complex tasks.

The paper also identifies a critical inefficiency in Qwen3.5-35B-A3B: when effective sparsity (k/E_eff) is low, load-balancing inadvertently introduces functional redundancy among experts, masking the underlying Huffman efficiency signal. To address this, the researchers propose Subset Difference Pruning, a surgical strategy that removes functionally duplicate experts without degrading reasoning performance. This pruning forces the model to collapse into streamlined, high-density routing paths, dramatically improving Huffman efficiency. The findings advocate for a paradigm shift in MoE design—moving beyond forced load-balancing toward Minimum Description Length (MDL) optimality, where routing becomes a principled compression engine rather than a heuristic selection method.