HFEPX · Eval paper review

On the Complexity of Neural Computation in Superposition

Micah Adler, Nir Shavit

Published

Sep 5, 2024

Citations

Trust level

Moderate

Usefulness score

55/100 (Medium)

Extraction confidence

65% (Moderate)

Derived from extracted protocol signals and abstract evidence.

Rater population

Not reported

Signals refreshed

Feb 26, 2026

Open arXiv Find implementation Shortlist (0) RSS feed

Should you rely on this paper?

This paper has useful evaluation signal, but protocol completeness is partial; pair it with related papers before deciding implementation strategy.

Use this for comparison and orientation, not as your only source.

Low-signal caution for protocol decisions

Use this page for context, then validate protocol choices against stronger HFEPX references before implementation decisions.

The abstract does not clearly name benchmarks or metrics.

Best use

Secondary protocol comparison source

Use if you need

A secondary eval reference to pair with stronger protocol papers.

What to verify

Read the full paper before copying any benchmark, metric, or protocol choices.

Main weakness

The abstract does not clearly name benchmarks or metrics.

Human feedback signal

Detected

From extracted signals

Evaluation signal

Detected

Eval setup described

Usefulness for eval research

55/100

Moderate-confidence candidate

Useful as a secondary reference; validate protocol details against neighboring papers.

If you are doing eval pipeline work, start here

Human Eval Papers LLM-as-Judge Papers Pairwise Preference Papers Tool-Use Evaluation Search

Abstract

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 $Ω(\sqrt{m' \log m'})$ neurons and $Ω(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(n^2 / \log n)$ features. Conversely, we provide a nearly tight constructive upper bound: logical operations like pairwise AND can be computed using $O(\sqrt{m'} \log m')$ neurons and $O(m' \log^2 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.

What we could verify

These are the protocol signals we could actually recover from the available paper metadata. Use them to decide whether this paper is worth deeper reading.