Modern neural networks are growing at an unprecedented rate. While scaling up models—making them wider and deeper—typically yields better performance, it also makes them prohibitively expensive for inference. To mitigate this, researchers increasingly rely on Sparsity. Instead of executing the entire network for every input, a "routing function" activates only a small subgraph or "expert."
While "Mixture of Experts" (MoE) models like Switch Transformers are incredibly efficient in practice, their routing functions are often designed heuristically or learned through trial and error. Until now, we have lacked a formal mathematical proof explaining why these sparse subgraphs can represent complex functions just as well as their dense counterparts.
This NeurIPS 2022 paper from Google Research bridges the gap between the empirical success of sparsely activated networks and underlying approximation theory. It proves that sparse networks can match the approximation power of dense networks while offering an exponential speedup in inference time, provided they use "locality-aware" routing.
Formalizing Sparse Routing
To study this problem mathematically, the authors introduce two key components:
- Data-Dependent Sparse Model (DSM): A formal framework where the network's active units and weights change dynamically based on the input $x$. This captures the core mechanism of MoE and Scaling Transformers.
- Locality Sensitive Hashing (LSH) for Routing: To make the mathematics tractable, the authors utilize LSH as the routing mechanism. LSH is an algorithm that hashes similar input vectors into the same "bucket" with high probability. By using LSH, each "expert" in the network acts as a specialist for a specific neighborhood of the input space.
Combining these concepts allows the authors to analyze how well a sparse network can approximate Lipschitz functions—functions that are "smooth" and do not change abruptly.
Key Insights: The Power of Locality
The core theoretical breakthrough is realizing that for smooth functions, the entire network doesn't need to process every point globally. If you route similar inputs to the same expert using LSH, that expert only needs to learn a local approximation of the function.
Furthermore, the theory leverages the Manifold Advantage. While real-world data might be highly dimensional (e.g., a $224 \times 224$ image), it typically resides on a much lower-dimensional "manifold" ($k \ll d$). Sparse networks are particularly efficient at exploiting this low-dimensional structure. The authors also demonstrate that pseudo-random hashing—often used in empirical works to distribute tokens—can be "non-smooth" and perform poorly compared to LSH, which preserves the geometric relationships between data points.
Empirical Validation and Key Results
The authors validated their theory using both synthetic benchmarks (random polynomials, hypercube functions) and real-world datasets like CIFAR-10, testing both CNN and Vision Transformer (ViT) architectures.
- Exponential Efficiency Gap: The authors mathematically prove a massive gap in inference complexity. To reach an error level of $\epsilon$, a dense model requires time that scales exponentially with the manifold dimension $k$. In contrast, an LSH-based sparse model only requires $O(dk \log(1/\epsilon))$ time—an exponential improvement.
- Better Trade-offs: In experiments, sparse models (DSMs) consistently outperformed dense models of the same active size. For example, a DSM with 90% sparsity (only 10% of units active) achieved higher accuracy than a narrow dense model with the equivalent number of active parameters.
- FLOPs vs. Accuracy: On synthetic data, a sparse model achieved a lower Mean Squared Error (MSE) using only 18k FLOPs compared to a dense model requiring 73k FLOPs.
Limitations and Future Work
While this paper provides a robust theoretical foundation, it opens several avenues for future research:
- Single Layer Focus: The theoretical proofs primarily focus on a single sparsely activated final layer. A full theoretical treatment of deep, multi-layer sparse routing remains an open challenge.
- LSH vs. Learned Routing: The paper uses LSH because it is mathematically clean and geometrically sound. However, most state-of-the-art models use learned routers (like Top-K routing). Proving similar bounds for learned routers is a logical next step.
- Scale of Experiments: The empirical validation was conducted on relatively small scales (e.g., CIFAR-10). Testing these specific LSH-based routers on massive Large Language Models (LLMs) is necessary to confirm if the theoretical gains hold at the trillion-parameter scale.
Summary updated