The Ball and the Box: Two Geometries of Computation in Superposition

Xiaoyu Li; Lequan Lin; Dai Shi; Jiaojiao Jiang; Junbin Gao; Andi Han

cs.LGOct 8, 2026

The Ball and the Box: Two Geometries of Computation in Superposition

Authors: Xiaoyu Li, Lequan Lin, Dai Shi, Jiaojiao Jiang, Junbin Gao, Andi Han

Organizations: University of New South Wales · University of Sydney · University of Cambridge

Abstract

Neural representations can encode more features than they have dimensions, a phenomenon known as superposition. We study the dimension needed to compute Boolean gates from such representations. For a single threshold layer with a Gaussian random dictionary and uniformly random sparse Boolean inputs, we derive sharp dimension thresholds under two error criteria. A vanishing expected error count can require more dimensions than correctness of every output with high probability. Shared reads explain the gap: rare realizations can produce many errors at once. The expected-count threshold has ball geometry, while joint reliability has box geometry when a gate is evaluated on every feature tuple. Optimizing shared readout weights and biases gives explicit thresholds for conjunction, disjunction, and majority. For pairwise conjunction, the analysis also describes the transition near the threshold, in agreement with exact simulations.

Figures & tables

	Midpoint bias	Optimized bias
Count errors, $\mathbb{E}X\to 0$ (ball)	$8k(\lambda_{1}^{2}+\lambda_{0}^{2})$	$2k\bigl(\sqrt{2}\,\lambda_{1}+(\lambda_{1}^{2}+\lambda_{0}^{2})^{1/2}\bigr)^{2}$
	$\sim 16\,k\log m$	$\sim 4\,k\log m$
Forbid errors, $\mathbb{P}(X=0)\to 1$ (box)	$4k(\lambda_{1}+\lambda_{0})^{2}$	$k(3\lambda_{1}+\lambda_{0})^{2}$
	$\sim 8\,k\log m$	$\sim 2\,k\log m$

Table 1: Sharp first-order thresholds for pairwise conjunction, with

\lambda_{1}=\sqrt{2\log k}

and

\lambda_{0}=\sqrt{2\log(m-k)}

. Second lines give the limit when

\log k=o(\log m)

. All entries are

32k\log k

to first order when

\log m\sim\log k

Panel of Figure 1 — Figure 1: Two geometries for the one-active class of pairwise conjunction. Left: independent vectors have the extreme projections of a disc of radius $\sqrt{2\log N}$ , where $N=k(m-k)$ . Right: shared active and inactive reads form a grid in $[-\lambda_{1},\lambda_{1}]\times[-\lambda_{0},\lambda_{0}]$ . A gate fails beyond the line normal to $a=(1,1)$ at distance $s_{z}/(\sigma_{d}\lVert a\rVert)$ . The expected count must clear the disc; reliability must clear the rectangle. Here $\lambda_{0}=3\lambda_{1}$ ; points are illustrative.

Figure 2: Bias, gate type and the separation of reliability from expected errors, all at $k=1024$ . (a) Three pairwise biases and feature recovery on shared draws at $m=k^{4}$ . (b) Four gates with the half-slack bias at $m=k^{4}$ . Here $d_{\rm box}=k((2t-1)\hat{\lambda}_{1}+(2r-2t+1)\hat{\lambda}_{0})^{2}$ , with $(r,t)=(2,2)$ in (a) and each gate’s own $(r,t)$ in (b). (c,d) The midpoint pairwise rule at $m=k^{4},k^{16},k^{64}$ , normalized by $d_{0}$ of ( 14 ). Points and bands in (a–c): 4096 exact draws per cell and pointwise $95\%$ Wilson intervals. Dashed curves in (c): $\Psi_{\hat{\beta}}$ from Theorem 7.1 (i). Panel (d): quadrature of proposition 3.2 ; dotted lines mark the first-order ball centers.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure A.1: Dependency map. An arrow points from a result to one that builds on it. Blue: expected errors (the ball); orange: reliability (the supremum and the box); grey: the exact law and its reduction. Small italic text names the classical tool each proof adds.

Symbol	Meaning
$E=[e_{1}\|\cdots\|e_{m}]$	dictionary, independent columns $e_{i}\sim N(0,I_{d}/d)$
$S$ , $x=\mathbf{1}_{S}$ , $k$ , $n=m-k$	active set (uniform $k$ -subset), input, sparsity, number of inactive features
$u=Ex$ , $R=E^{\top}u$	stored vector and feature reads; $A_{i}=R_{i}$ ( $i\in S$ ), $B_{j}$ (inactive reads)
$H$ , $Z$ , $W$ , $\sigma$	$H\sim\chi^{2}_{d}/d$ , independent Gaussian samples of sizes $k$ and $n$ , $\sigma=\sqrt{kH/d}$ ( Theorem 3.1 )
$\sigma_{d}=\sqrt{k/d}$	deterministic interference scale
$\xi$ , $\xi_{I}$	$\xi_{i}=Z_{i}-\bar{Z}$ on $S$ and $W_{j}$ off $S$ ; interference vector of a tuple $I$

Appendix

Table A.1: Notation.

Panel of Figure 6 — Figure J.1: The four first-order thresholds of pairwise conjunction and the threshold of feature recovery, in units of $k\log m$ , as functions of $\log m/\log k$ . All four conjunction thresholds equal $32k\log k$ when $\log m\sim\log k$ ; they separate toward $16$ , $8$ , $4$ and $2$ (dotted). The vertical lines mark the regimes of the simulations in Section 9 .

Figure J.2: Pairwise conjunction, 4096 exact draws per point, pointwise

95\%

Wilson bands. (a) Three deterministic biases and feature recovery evaluated on the same draws; the count-optimal and half-slack curves nearly coincide, and recovery switches on near ratio

0.39

, left of the plotted range. (b) The half-slack bias of Theorem 6.1 (a) as

k

grows; dashed curves are the profiles

\Psi_{\hat{\beta}}(x/2)F_{+}(x/2)

of Theorem 7.1 (ii) at the slack

x=\hat{\lambda}_{1}(\sqrt{d/k}-3\hat{\lambda}_{1}-\hat{\lambda}_{0})

Figure J.3: Reliability of four threshold gates at

m=k^{4}

with the half-slack bias of Theorem 6.1 (a) for

k=64,256,1024

, and with the midpoint bias and the sample-adaptive oracle bias for

k=1024

. The horizontal axis is the dimension in units of the quantile box center of each gate. Dashed line: that center; dotted line: the midpoint box threshold of Theorem 6.1 (b) in the same units.

Figure L.1: All four cases of campaign E1. Each point uses 4096 independent draws; bands are pointwise

95\%

Wilson intervals. The three bias rules and feature recovery share each cell’s draws.

Ratio	$d$	$\mathbb{P}(X=0)$ [95% interval]	MC mean	MC s.e.	Quadrature
0.60	164032	0.0000 [0.0000, 0.0009]	2.462e+06	4.199e+05	2.485e+06
1.00	273387	0.1548 [0.1440, 0.1662]	312.3	127.7	427.3
1.20	328064	0.8252 [0.8133, 0.8365]	10.46	8.232	6.742
1.35	369072	0.9727 [0.9672, 0.9772]	0.06288	0.01097	0.3274
1.50	410081	0.9976 [0.9955, 0.9987]	0.002693	0.0008277	0.0178
1.75	478427	0.9995 [0.9982, 0.9999]	0.0004904	0.0003452	0.0002069

Appendix

Table L.1: The half-slack bias at

k=1024

m=1024^{4}

(campaign E1). Mean error is the Rao–Blackwellized sample mean over the inactive reads with its Monte Carlo standard error; the last column is the quadrature of proposition 3.2 . Rare draws carry the mean, so the sample mean and its standard error can both be misleading, as at ratio

1.35

Ratio	0.8	0.9	1	1.1	1.2	1.35	1.5
$\mathrm{AND}_{2}$ , half-slack	0	21	668	2262	3387	3980	4081
$\mathrm{AND}_{2}$ , oracle	1	141	1573	3305	3952	4092	4096
$\mathrm{AND}_{3}$ , half-slack	1	154	1258	2919	3758	4065	4093
$\mathrm{AND}_{3}$ , oracle	11	571	2456	3788	4077	4095	4096
$\mathrm{OR}_{2}$ , half-slack	0	0	640	3298	4009	4092	4096
$\mathrm{OR}_{2}$ , oracle	0	0	1308	3944	4094	4096	4096

Appendix

Table L.2: Campaign E2 at

k=1024

m=k^{4}

: success frequency of the half-slack rule (out of 4096) and of the oracle at selected dimension ratios to the quantile box center.

Ratio	succ.	$\mathbb{E}X$	succ.	$\mathbb{E}X$	succ.	$\mathbb{E}X$
	$m=k^{4}$		$m=k^{16}$		$m=k^{64}$
0.9	33	$5.81\times 10^{3}$	0	$9.03\times 10^{18}$	0	$2.01\times 10^{89}$
1	1208	$422$	1327	$3.29\times 10^{15}$	1392	$4.51\times 10^{77}$
1.1	3191	$30.9$	3896	$1.21\times 10^{12}$	4091	$1.02\times 10^{66}$
1.2	3922	$2.26$	4089	$4.43\times 10^{8}$	4096	$2.32\times 10^{54}$
1.35	4084	$0.0453$	4096	$3.15\times 10^{3}$	4096	$7.98\times 10^{36}$

Appendix

Table L.3: Campaign E3, the midpoint pairwise network at

k=1024

: success frequency (out of 4096) and exact expected number of wrong outputs at selected dimension ratios to

d_{0}=4k(\hat{\lambda}_{1}+\hat{\lambda}_{0})^{2}

Campaign, rule	$m$	$k$	$\hat{\beta}$	Limit	Simulation [95% interval]
E1, half-slack	$k^{4}$	64	2.458	0.155	0.143 [0.133, 0.154]
E1, half-slack	$k^{4}$	256	2.342	0.154	0.139 [0.129, 0.150]
E1, half-slack	$k^{4}$	1024	2.275	0.154	0.155 [0.144, 0.166]
E1, half-slack	$k^{2}$	1024	1.538	0.147	0.149 [0.139, 0.160]
E2, half-slack	$k^{4}$	64	2.458	0.155	0.149 [0.138, 0.160]
E2, half-slack	$k^{4}$	256	2.342	0.154	0.141 [0.131, 0.152]

Appendix

Table L.4: Success frequency at the quantile center (dimension ratio

1

, 4096 draws) against the limit of Theorem 7.1 .

Criterion	Protects	Midpoint bias	Optimized bias	Source
$\mathbb{E}X/\lvert\mathcal{F}\rvert\to 0$	a typical gate	$d/k\to\infty$ (any fixed bias)		Corollary M.1
$\mathbb{P}(X=0)\to 1$	a typical input	$8k\log m$	$2k\log m$	Theorem 6.1 (a,b)
$\mathbb{E}X\to 0$	the total additive loss	$16k\log m$	$4k\log m$	Theorem 6.1 (c,d)
correct on every support	every input, chosen after $E$	$\Theta(k^{2}\log m)$	—	Proposition 8.1

Appendix

Table M.1: Four error criteria for the universal family of pairwise conjunctions when

\log k=o(\log m)

, in order of the width they require. The first row is a condition on

d/k

, the middle rows are sharp first-order thresholds, and the last row is sharp up to constants. With optimized biases, the reliability threshold holds against every common representation and the expected-count threshold against every gate-local rule.

	Reliability		Expected count
Gate	(a) half-slack	(b) midpoint	(c) midpoint	(d) optimized
$\mathrm{AND}_{2}$	$1$	$4$	$8$	$2$
$\mathrm{AND}_{3}$	$1$	$4$	$12$	$3$
$\mathrm{OR}_{2}$	$9$	$16$	$16$	$6+4\sqrt{2}\approx 11.66$
$\mathrm{MAJ}_{3}$	$9$	$16$	$24$	$9+6\sqrt{2}\approx 17.49$
Recovery, $\mathrm{THR}^{1}_{1}$	$1$	$4$	$4$	$1$

Appendix

Table M.2: Capacity constants of corollary M.2 . At width

d

and activity

k

, the criterion tolerates dictionaries with

\log m

up to

d/(2c_{\bullet}k)

to first order, so a smaller constant means exponentially more features. Columns follow the parts of Theorem 6.1 .

Target $\mathbb{P}(X=0)$	$0.5$	$0.9$	$0.99$	$0.999$
Midpoint bias	$1.61$	$1.81$	$2.08$	$2.35$
Half-slack bias	$1.10$	$1.29$	$1.54$	$1.80$
Best deterministic common bias	$1.09$	$1.29$	$1.54$	$1.79$

Appendix

Table M.3: Width for a target success probability at

k=1024

and

m=k^{4}

, from ( M.1 ) with the profiles evaluated at

\hat{\beta}=\hat{\lambda}_{0}/\hat{\lambda}_{1}=2.28

, in units of the optimized quantile centre

k(3\hat{\lambda}_{1}+\hat{\lambda}_{0})^{2}

. The midpoint centre is

1.54

in these units. The closed-form half-slack bias stays within

0.6\%

of the best deterministic common bias.

Explore similar work

May 2, 2026cs.LG

Linear-Readout Floors and Threshold Recovery in Computation in Superposition

Two recent approaches to computation in superposition reach different recursive capacity regimes: Hänni et al. certify

\tilde{O}(d^{3/2})

computable features in width

d

via an approximate-linear recursive template, while Adler and Shavit reach near-quadratic capacity (up to logarithmic factors) using thresholded Boolean recovery. The main contribution of this paper is conceptual: we argue these results are not contradictory because they maintain different interface invariants, and we formalize the distinction. As a tool, we record a rank-trace Welch-type lower bound for biorthogonal linear readouts: for

F \gg d

, the worst-case off-diagonal cross-talk of any unit-diagonal linear readout is

Ω(d^{-1/2})

, and the bound is tight on average for unit-norm tight frames. At quadratic feature load

F=d^2

, random-support threshold recovery succeeds for sparsities

s=O(d/\log d)

, while linear readouts still incur

Ω(s/d)

average per-coordinate squared error on Bernoulli sparse states. Matching the Welch floor against the published tolerance of the Hänni correction layer explains the

d^{3/2}

scale as a compatibility threshold for that template, not a universal upper bound. Robust nonlinear reset beyond the Hänni template is left open.

Hector Borobia, Elies Seguí-Mas, Guillermina Tormo-Carbó

VRAIN – Valencian Research Institute for Artificial Intelligence, Universitat Politècnica de València, Valencia, Spain · Department of Economics and Social Sciences, Universitat Politècnica de València, Valencia, Spain · Department of Business Organisation, Universitat Politècnica de València, Valencia, Spain

Feature Superposition

Ask PDF

Jul 6, 2026cs.LG

Compressed Computation under $L^4$ Loss is likely Computation in Superposition

Neural networks are thought to represent concepts as directions in their activation space, and superposition lets them encode more concepts than they have dimensions. It is natural to ask whether they can also compute more functions than they have neurons, i.e., perform computation in superposition. In this regime many functions of sparse inputs are evaluated by a layer with fewer neurons than there are functions to compute. Representation in superposition is by now fairly well understood, but computation in superposition is not, and there are few toy models of it arising through training rather than being hand designed. As a toy model of computation in superposition we study the compressed-computation setup: a single-hidden-layer ReLU network with 50 neurons that must compute the ReLU of each of 100 sparse input features. We show that training it under an

L^4

loss (the mean fourth power of the error), rather than the usual

L^2

, elicits a solution that appears to compute all features in superposition. We then reverse-engineer this solution. We find that the network assigns each feature a sparse binary codeword over neurons and decodes it with a pseudoinverse of the encoder. Given these codewords, a description with only three scalars recovers most of the network's performance, and we validate it by building equivalent networks from hand-designed codes.

Francisco Ferreira da Silva, Stefan Heimersheim

ReLU Neural Networks Feedforward Neural Networks Neural Network Expressivity

Ask PDF

Sep 9, 2026stat.ML

High-probability guarantees for linear accessibility in feature superposition

Neural networks can leverage feature superposition to encode more concepts than dimensions, but cross-feature interference constrains the linear accessibility of simultaneously active features. By framing linear accessibility as a compressed sensing problem, we derive high-probability bounds for fixed supports under subgaussian noise, proving the sufficient dimension scales linearly (

d=O_{\varepsilon}(k \log m)

) rather than prior worst-case quadratic limits. We characterize the asymmetry between active and inactive interference and the trade-off between interference and observation-noise budgets. We then validate these bounds across system parameters through Gaussian-tail approximations. We also introduce IHT-SAE, which uses learned iterative refinement to improve feature recovery beyond the limits of linear availability. These results quantify the geometric constraints of the linear representation hypothesis, providing a framework for evaluating sparse autoencoders, compositional generalization, and neural interpretability.

Enrico Vompa

Applied Artificial Intelligence Group Tallinn University of Technology, Estonia

Feature Superposition Neural Representation Geometry Representation Disentanglement

Ask PDF

Abstract

Explore similar work

Linear-Readout Floors and Threshold Recovery in Computation in Superposition

Compressed Computation under L4L^4L4 Loss is likely Computation in Superposition

High-probability guarantees for linear accessibility in feature superposition

Compressed Computation under $L^4$ Loss is likely Computation in Superposition