On the Complexity of Neural Computation in Superposition

Researchers establish theoretical foundations for neural network superposition, proving lower bounds that require at least Ω(√m' log m') neurons and Ω(m' log m') parameters to compute m' features. The work demonstrates exponential complexity gaps between computing versus merely representing features and provides first subexponential bounds on network capacity.

• →Neural networks computing in superposition require at least Ω(√m' log m') neurons and Ω(m' log m') parameters for m' features across broad problem classes.
• →A network with n neurons can compute at most O(n²/log n) features, establishing explicit limits on model compression.
• →There exists an exponential complexity gap between computing features in superposition versus simply representing them.
• →The research provides nearly tight upper bounds showing logical operations can be computed using O(√m' log m') neurons.
• →Parameter count serves as a good analytical estimator for the number of features a neural network can compute.