# On the Complexity of Neural Computation in Superposition arXiv: https://arxiv.org/abs/2409.15318 · HTML: https://mlsanity.com/paper/2409.15318/ ## Key facts - Cited by 21 papers in the map (data through 14 Oct 2026). - Placed in Sparse autoencoder training and evaluation, one of 13 directions in Mechanistic interpretability. - Builds on 17 of its 44 references that are in the map. - First posted on arXiv 5 Sep 2024. ## Placed in - Mechanistic interpretability / [Sparse autoencoder training and evaluation](https://mlsanity.com/mechinterp/sparse-autoencoder-training-and-evaluation/) ## Builds on (most cited first, 17 of 17) - [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015) - [Toy Models of Superposition](https://mlsanity.com/paper/2209.10652/) (2022) - [Scaling and evaluating sparse autoencoders](https://mlsanity.com/paper/2406.04093/) (2024) - [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021) - [Jumping Ahead: Improving Reconstruction Fidelity with JumpReLU Sparse Autoencoders](https://mlsanity.com/paper/2407.14435/) (2024) - [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016) - [Transcoders Find Interpretable LLM Feature Circuits](https://mlsanity.com/paper/2406.11944/) (2024) - [Linear Algebraic Structure of Word Senses, with Applications to Polysemy](https://mlsanity.com/paper/1601.03764/) (2016) - [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019) - [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018) - [Polysemanticity and Capacity in Neural Networks](https://mlsanity.com/paper/2210.01892/) (2022) - [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021) - [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021) - [Mathematical Models of Computation in Superposition](https://mlsanity.com/paper/2408.05451/) (2024) - [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020) - [Neural Networks with Small Weights and Depth-Separation Barriers](https://mlsanity.com/paper/2006.00625/) (2020) - [Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials](https://mlsanity.com/paper/1802.09121/) (2018) ## Built on by (most cited first, 21 of 21) - [From Flat to Hierarchical: Extracting Sparse Representations with Matching Pursuit](https://mlsanity.com/paper/2506.03093/) (2025) - [Superposition Yields Robust Neural Scaling](https://mlsanity.com/paper/2505.10465/) (2025) - [Adversarial Examples Are Not Bugs, They Are Superposition](https://mlsanity.com/paper/2508.17456/) (2025) - [Towards Combinatorial Interpretability of Neural Computation](https://mlsanity.com/paper/2504.08842/) (2025) - [Spectral Superposition: A Theory of Feature Geometry](https://mlsanity.com/paper/2602.02224/) (2026) - [Expand Neurons, Not Parameters](https://mlsanity.com/paper/2510.04500/) (2025) - [Compressed Computation is (probably) not Computation in Superposition](https://mlsanity.com/paper/2606.14673/) (2026) - [Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problem](https://mlsanity.com/paper/2507.09816/) (2025) - [Evidence for feature-specific error correction in LLMs](https://mlsanity.com/paper/2606.24964/) (2026) - [Polysemy of Synthetic Neurons Towards a New Type of Explanatory Categorical Vector Spaces](https://mlsanity.com/paper/2505.07831/) (2025) - [Efficient Modular Learning through Naive LoRA Summation: Leveraging Orthogonality in High-Dimensional Models](https://mlsanity.com/paper/2508.11985/) (2025) - [Understanding Empirical Unlearning with Combinatorial Interpretability](https://mlsanity.com/paper/2602.19215/) (2026) - [Similarity of Neural Network Representations in Superposition](https://mlsanity.com/paper/2604.00208/) (2026) - [Phase-Associative Memory: Sequence Modeling in Complex Hilbert Space](https://mlsanity.com/paper/2604.05030/) (2026) - [Toy Combinatorial Interpretability Models Reveal Lottery Tickets in Early Feature Space](https://mlsanity.com/paper/2605.17704/) (2026) - [Compressed Computation under L4 Loss is likely Computation in Superposition](https://mlsanity.com/paper/2607.04800/) (2026) - [Scaling Interpretable Transformers with Parity Bottleneck Layers](https://mlsanity.com/paper/2607.20652/) (2026) - [Abstention and Noise Filtering: Two Missing Primitives of Softmax Attention](https://mlsanity.com/paper/2609.22005/) (2026) - [Interference Beyond Geometry in Concept Extraction](https://mlsanity.com/paper/2609.35351/) (2026) - [The Ball and the Box: Two Geometries of Computation in Superposition](https://mlsanity.com/paper/2610.11744/) (2026) - [RouterInterp: Understanding Superposed Specialisation in Mixture of Experts Routing](https://mlsanity.com/paper/2610.11775/) (2026) ## Abstract (arXiv) Superposition, the ability of neural networks to represent more features than neurons, is increasingly seen as key to the efficiency of large models. This paper investigates the theoretical foundations of computing in superposition, establishing complexity bounds for explicit, provably correct algorithms. We present the first lower bounds for a neural network computing in superposition, showing that for a broad class of problems, including permutations and pairwise logical operations, computing m' features in superposition requires at least Omega(√m' log m') neurons and Omega(m' log m') parameters. This implies an explicit limit on how much one can sparsify or distill a model while preserving its expressibility, and complements empirical scaling laws by implying the first subexponential bound on capacity: a network with n neurons can compute at most O(n2 / log n) features. Conversely, we provide a nearly tight constructive upper bound: logical operations like pairwise AND can be computed using O(√m' log m') neurons and O(m' log2 m') parameters. There is thus an exponential gap between the complexity of computing in superposition (the subject of this work) versus merely representing features, which can require as little as O(log m') neurons based on the Johnson-Lindenstrauss Lemma. Our work analytically establishes that the number of parameters is a good estimator of the number of features a neural network computes.