Source-linked AI summary
Towards a mathematical theory of superposition
Michael I. Ivanitskiy, John Jasper, Emily J. King, Dustin G. Mixon
TL;DR
The paper asks how neural networks can represent many features when neurons are fewer than features, rather than assigning each feature its own neuron. It models sparse feature encoding and recovery with an overcomplete dictionary and ReLU, proving support-recovery results for random and worst-case supports, including Gaussian matrices and ETFs.
Problem
When there are more features than neurons, neurons must represent superpositions of features rather than each responding to one feature.
Method
The paper analyzes support recovery by applying ReLU(W^T W x + b) to sparse binary features encoded through an overcomplete dictionary, using frame-theoretic and compressed-sensing arguments.
Results
Theorems establish high-probability recovery for random supports up to k ≪ d/log n and analyze worst-case recovery for Gaussian matrices and equiangular tight frames.
Takeaways & Limitations
For real ETFs with n > d + 1, recovery analysis is linked to a structural characterization showing relatively balanced Gram-matrix sign patterns.
Takeaways & Limitations
The random-support guarantee is stated for dictionaries that are nearly tight with low coherence.
Abstract
from arXiv · showhide
We develop a mathematical theory of superposition in neural networks using tools from frame theory and compressed sensing. In our model, a sparse binary vector \(x\) of active features is encoded through an overcomplete dictionary \(W\), and feature recovery is performed by applying \(\operatorname{ReLU}(W^\top W x+b)\) with an appropriate bias vector \(b\). We prove several recovery theorems for this model. In the random-support setting, we establish high-probability support recovery for nearly tight, low-coherence dictionaries, with guarantees when the expected sparsity is up to order \(d/\log n\). In the worst-case support setting, we give a sharp and computable criterion for which sparsity levels permit support recovery. We apply this criterion to Gaussian random matrices and equiangular tight frames. For real equiangular tight frames with \(n>d+1\), we determine the exact recovery threshold in terms of the coherence. The proof of this result for real equiangular tight frames relies on a novel characterization---which should be of independent interest to frame theorists---of the distribution of signs in the Gram matrix.
1 Introduction
The paper develops a mathematical account of neural-network superposition, where sparse feature combinations are represented in an overcomplete activation space and analyzed through frame theory and compressed sensing. It uses support recovery to obtain provable conditions for when feature activity can be recovered from neural activations.
- Superposition in neural networks: Superposition represents realizable activation vectors as nonnegative combinations of a small number of feature representations, often with more features than neurons.This overcomplete setting forces neurons to respond to multiple features rather than assigning one neuron to each feature.
- Superposition in neural networks: A two-dimensional color example shows that polysemantic feature vectors expand the representable palette, while a 2-sparsity constraint preserves unique recovery for only some colors.The three feature vectors are arranged as an equiangular triangle, illustrating why geometric separation supports sparse representation.
- Our approach: Support recovery: The paper replaces approximate sparse-vector recovery with support recovery: ReLU(W^⊤Wx+b) should have the same support as the sparse input x under suitable conditions on W, x, and b.The bias suppresses off-support coordinates after the Gram-matrix perturbation, while supported coordinates remain near their original values.
- Random support model: In the random-support model, high-probability recovery is established for nearly tight, low-coherence dictionaries when the expected sparsity satisfies k ≪ d/log n.Here k is the expected sparsity level when x has Bernoulli i.i.d. entries with parameter p=k/n.
- Worst-case support model: For worst-case supports, the paper develops recovery criteria and applies them to Gaussian matrices and equiangular tight frames, with ETFs recovering less-sparse vectors than Gaussian matrices.For real ETFs with n>d+1, the paper additionally characterizes balanced Gram-matrix sign patterns, with at most one predominantly positive or negative row.
2 Models of Superposition
The paper models superposition as support recovery for sparse binary feature vectors using an overcomplete matrix, bias, and ReLU. It analyzes random- and worst-case supports and connects the model to frame-theoretic structures and prior neural-network phenomena.
- Support recovery: The central question is when a d × n matrix W with d < n and bias b can represent sparse vectors x through support recovery.The target condition is that ReLU(W^⊤Wx+b) has the same support as x.
- Related work: Related work includes toy superposition models trained with mean-squared error, ETF-like learned dictionaries, and analyses using decoupled encoding and decoding matrices.The paper also distinguishes superposition from neural collapse despite qualitative similarities involving simplex ETFs.
- Support models: The random-support model uses i.i.d. Bernoulli(p) entries, whereas the worst-case model covers every binary vector with at most k nonzero entries.These models separate average-case guarantees from guarantees uniform over supports.
- Recovery guarantees: Under both models, an appropriate bias enables support recovery when W resembles an equiangular tight frame in a suitable sense.For random supports, the paper specifically treats nearly tight, low-coherence dictionaries and also bounds the reconstruction error.
- Mechanism: W^⊤W has nearly equal diagonal entries and small, nearly equal-magnitude off-diagonal entries, while b is approximately a small negative multiple of the all-ones vector.The bias offsets noise introduced because W^⊤W is not the identity.
- Mechanism: In the geometric picture, W^⊤Wx perturbs x, the negative bias suppresses off-support coordinates, and ReLU projects onto the nonnegative orthant.A subsequent scaling can move the surviving entries closer to the original binary values.
- Scope of the approach: The paper treats support recovery as a first step toward sparse recovery and general compressed sensing rather than directly optimizing mean-squared error.The model therefore targets a simpler, provable recovery property than approximate sparse-vector recovery.
3 Random Support Model
The random-support model recovers sparse feature supports, and under unit-norm tight, low-coherence conditions also controls reconstruction error with high probability.
- Random support setup: The model analyzes Bernoulli i.i.d. feature activations and evaluates both support recovery and ℓ∞ reconstruction mismatch.This differs from prior toy-model analyses based on expected squared ℓ2 error.
- Recovery guarantee: With probability at least 1−ε, ReLU(W^⊤Wx+b) recovers the support when p satisfies bounds determined by dictionary parameters.The theorem introduces dictionary-dependent conditions and a target failure probability ε.
- Recovery guarantee: With probability at least 1−ε, unit-norm dictionaries simultaneously recover support and achieve ∥x̂−x∥∞≤δ under the theorem’s condition.The error guarantee applies for δ∈(0,1).
- Sparsity regime: For p=k/n, support recovery holds with high probability when the expected sparsity satisfies k ≪ d/log n.This average-case regime is contrasted with the substantially sparser worst-case regime.
- Bias choice: For centered dictionaries, the bias reduces to a negative multiple of the all-ones vector.This matches behavior observed in earlier superposition literature.
4 Worst-Case Support Model
The worst-case support model characterizes recoverable sparsity through a computable criterion based on ReLU support preservation and diagonal dominance of Gram-matrix submatrices.
- Worst-case criterion: The model seeks a bias b making ReLU(W^⊤Wx+b) have the same support as every binary x with ∥x∥0≤k.This defines k(W), the largest universally recoverable sparsity level.
- Worst-case criterion: Support recovery is equivalent to an easily verified condition involving positive and negative Gram-matrix correlations and sums of the largest entries.The construction uses x+ = ReLU(x), x− = ReLU(−x), and Σ(k)v for the k greatest entries.
- Diagonal dominance: The parameter k′(W) is the largest k for which every principal k × k Gram submatrix is strictly diagonally dominant.This parameter is more intuitive than k(W), while the two remain within a factor of 2.
- Diagonal dominance: For dictionaries with unit-norm columns, k′(W) is linked to Tropp’s Babel function through the condition µ(k−1)<1.The criterion converts recoverability into a coherence-based condition.
- Applications: The upper and lower bounds are tight, with ETFs saturating the upper bound for n≤d+1 and the lower bound for n>d+1.The section applies the criterion to Gaussian matrices and equiangular tight frames.
5 Proof of Theorem 8
For Gaussian dictionaries, the proof combines probabilistic bounds on Gram-matrix correlations with union bounds to establish high-probability worst-case recovery guarantees.
- Gaussian bounds: The Gaussian analysis establishes lower and upper bounds on maximum worst-case sparsity levels yielding support recovery with high probability.These bounds are stated for matrices with i.i.d. Gaussian entries.
- Probabilistic ingredients: The argument uses rotation invariance to represent off-diagonal inner products through independent standard Gaussians and a chi-distributed norm.This reduction enables concentration estimates for the relevant Gram statistics.
- Probabilistic ingredients: A union bound combines concentration estimates for Gaussian order statistics and chi-square fluctuations.The proof invokes Chernoff, Hoeffding, and inverse-error-function bounds.
- Theorem 8: Theorem 8 follows by applying the union bound to Propositions 10 and 11.The theorem assumes n≥d≥100.
6 Proof of Theorem 9
The ETF analysis proves exact worst-case recovery thresholds by combining diagonal-dominance calculations with a structural characterization of Gram-matrix sign balance.
- ETF recovery: ETFs provide worst-case support recovery, and the paper states that they recover less sparse vectors than Gaussian dictionaries.The section also develops a structural result about real ETFs.
- Sign structure: For real ETFs with n>d+1, at most one Gram-matrix row can have predominantly positive or predominantly negative off-diagonal entries.Thus, most rows have relatively balanced positive and negative sign patterns.
- Sign structure: The proof derives sign balance by switching ETF rows and analyzing triple products of Gram-matrix signs.Rows with excessive imbalance lead to contradictions in two sign cases.