# Memorization Capacity of Neural Networks with Conditional Computation

arXiv: https://arxiv.org/abs/2303.11247 · HTML: https://mlsanity.com/paper/2303.11247/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 41 references that are in the map.
- First posted on arXiv 20 Mar 2023.

## Builds on (most cited first, 24 of 24)

- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [BranchyNet: Fast Inference via Early Exiting from Deep Neural Networks](https://mlsanity.com/paper/1709.01686/) (2017)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Dynamic Neural Networks: A Survey](https://mlsanity.com/paper/2102.04906/) (2021)
- [Learning Factored Representations in a Deep Mixture of Experts](https://mlsanity.com/paper/1312.4314/) (2013)
- [Conditional Computation in Neural Networks for faster models](https://mlsanity.com/paper/1511.06297/) (2015)
- [Dynamic Channel Pruning: Feature Boosting and Suppression](https://mlsanity.com/paper/1810.05331/) (2018)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Deep Neural Decision Trees](https://mlsanity.com/paper/1806.06988/) (2018)
- [Adaptive Neural Trees](https://mlsanity.com/paper/1807.06699/) (2018)
- [Low-Rank Approximations for Conditional Feedforward Computation in Deep Neural Networks](https://mlsanity.com/paper/1312.4461/) (2013)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Convolutional Rectifier Networks as Generalized Tensor Decompositions](https://mlsanity.com/paper/1603.00162/) (2016)
- [Exponentially Increasing the Capacity-to-Computation Ratio for Conditional Computation in Deep Learning](https://mlsanity.com/paper/1406.7362/) (2014)
- [Decision Forests, Convolutional Networks and the Models in-Between](https://mlsanity.com/paper/1603.01250/) (2016)
- [An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks](https://mlsanity.com/paper/2106.07724/) (2021)
- [Class Based Thresholding in Early Exit Semantic Segmentation Networks](https://mlsanity.com/paper/2210.15621/) (2022)

## Built on by (most cited first, 3 of 3)

- [Memory of recurrent networks: Do we compute it right?](https://mlsanity.com/paper/2305.01457/) (2023)
- [Cluster-based classification with neural ODEs via control](https://mlsanity.com/paper/2312.13807/) (2023)
- [Theoretical Guarantees for One-Shot Magnitude Pruning and Compute-Adaptive Early Exit](https://mlsanity.com/paper/2609.12337/) (2026)

## Abstract (arXiv)

Many empirical studies have demonstrated the performance benefits of conditional computation in neural networks, including reduced inference time and power consumption. We study the fundamental limits of neural conditional computation from the perspective of memorization capacity. For Rectified Linear Unit (ReLU) networks without conditional computation, it is known that memorizing a collection of n input-output relationships can be accomplished via a neural network with O(√n) neurons. Calculating the output of this neural network can be accomplished using O(√n) elementary arithmetic operations of additions, multiplications and comparisons for each input. Using a conditional ReLU network, we show that the same task can be accomplished using only O(log n) operations per input. This represents an almost exponential improvement as compared to networks without conditional computation. We also show that the Theta(log n) rate is the best possible. Our achievability result utilizes a general methodology to synthesize a conditional network out of an unconditional network in a computationally-efficient manner, bridging the gap between unconditional and conditional architectures.