A Theoretical View on Sparsely Activated Networks

Cenk Baykal, Nishanth Dikkala, Rina Panigrahy, Cyrus Rashtchian, Xin Wang

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:

  1. 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.
  2. 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.

1D example of local approximation and sparse vs. dense scaling behavior.

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.
Comparison of Mean Squared Error between dense networks, Data-Dependent Sparse Models (DSM), and LSH-routed models.

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

Abstract

Deep and wide neural networks successfully fit very complex functions today, but dense models are starting to be prohibitively expensive for inference. To mitigate this, one promising research direction is networks that activate a sparse subgraph of the network. The subgraph is chosen by a data-dependent routing function, enforcing a fixed mapping of inputs to subnetworks (e.g., the Mixture of Experts (MoE) paradigm in Switch Transformers). However, there is no theoretical grounding for these sparsely activated models. As our first contribution, we present a formal model of data-dependent sparse networks that captures salient aspects of popular architectures. Then, we show how to construct sparse networks that provably match the approximation power and total size of dense networks on Lipschitz functions. The sparse networks use much fewer inference operations than dense networks, leading to a faster forward pass. The key idea is to use locality sensitive hashing on the input vectors and then interpolate the function in subregions of the input space. This offers a theoretical insight into why sparse networks work well in practice. Finally, we present empirical findings that support our theory; compared to dense networks, sparse networks give a favorable trade-off between number of active units and approximation quality.
BibTeX
@inproceedings{baykal2022theoretical,
  author = {Cenk Baykal and Nishanth Dikkala and Rina Panigrahy and Cyrus Rashtchian and Xin Wang},
  title = {{A Theoretical View on Sparsely Activated Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=AODVskSug8},
}
Figure