mlsanityData to 14 Oct 2026

On the Complexity of Neural Computation in Superposition

arXiv 2409.15318 ↗First posted 5 Sep 2024cs.CC cs.AI cs.DScited by 21

On the map: Mechanistic interpretability → Sparse autoencoder training and evaluation

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.

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.

Builds on

17 of 44 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Mathematical Models of Computation in Superposition10 Aug
  2. 2022Toy Models of Superposition21 Sep

Other references · 15

  1. 2015Distilling the Knowledge in a Neural Networkcited by 10,324
  2. 2024Scaling and evaluating sparse autoencoderscited by 553
  3. 2021Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networkscited by 527
  4. 2024Jumping Ahead: Improving Reconstruction Fidelity with JumpReLU Sparse Autoencoderscited by 300
  5. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  6. 2024Transcoders Find Interpretable LLM Feature Circuitscited by 200
  7. 2016Linear Algebraic Structure of Word Senses, with Applications to Polysemycited by 165
  8. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  9. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 78
  10. 2022Polysemanticity and Capacity in Neural Networkscited by 77
  11. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  12. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
3 more
  1. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  2. 2020Neural Networks with Small Weights and Depth-Separation Barrierscited by 17
  3. 2018Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomialscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 8; 2026: 13.

21 papers.

Sort:

By area:

  1. 2025From Flat to Hierarchical: Extracting Sparse Representations with Matching Pursuitcited by 49
  2. 2025Superposition Yields Robust Neural Scalingcited by 31
  3. 2025Adversarial Examples Are Not Bugs, They Are Superpositioncited by 13
  4. 2025Towards Combinatorial Interpretability of Neural Computationcited by 9
  5. 2026Spectral Superposition: A Theory of Feature Geometrycited by 4
  6. 2025Expand Neurons, Not Parameterscited by 3
  7. 2026Compressed Computation is (probably) not Computation in Superpositioncited by 2
  8. 2025Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problemcited by 1
  9. 2026Evidence for feature-specific error correction in LLMscited by 1
  10. 2025Polysemy of Synthetic Neurons Towards a New Type of Explanatory Categorical Vector Spacescited by 0
  11. 2025Efficient Modular Learning through Naive LoRA Summation: Leveraging Orthogonality in High-Dimensional Modelscited by 0
  12. 2026Understanding Empirical Unlearning with Combinatorial Interpretabilitycited by 0
9 more
  1. 2026Similarity of Neural Network Representations in Superpositioncited by 0
  2. 2026Phase-Associative Memory: Sequence Modeling in Complex Hilbert Spacecited by 0
  3. 2026Toy Combinatorial Interpretability Models Reveal Lottery Tickets in Early Feature Spacecited by 0
  4. 2026Compressed Computation under L4 Loss is likely Computation in Superpositioncited by 0
  5. 2026Scaling Interpretable Transformers with Parity Bottleneck Layerscited by 0
  6. 2026Abstention and Noise Filtering: Two Missing Primitives of Softmax Attentioncited by 0
  7. 2026Interference Beyond Geometry in Concept Extractioncited by 0
  8. 2026The Ball and the Box: Two Geometries of Computation in Superpositioncited by 0
  9. 2026RouterInterp: Understanding Superposed Specialisation in Mixture of Experts Routingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Feature Superposition in Neural Networks: From Theory to Practice
  2. 2025Superposition as Lossy Compression: Measure with Sparse Autoencoders and Connect to Adversarial Vulnerability
  3. 2026Arbitrary-Accuracy Neural Approximation with Optimal Neuron Count and Near-Optimal Bit Complexity
  4. 2026Compositional Approximation Can Strictly Outperform Superpositional Approximation
  5. 2026Superposition unifies power-law training dynamics
  6. 2026High-probability guarantees for linear accessibility in feature superposition
  7. 2022A Measure of the Complexity of Neural Representations based on Partial Information Decomposition
  8. 2024The Computational Complexity of Circuit Discovery for Inner Interpretability