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

The paper investigates how neural representations that use superposition can encode more features than their dimensionality allows, focusing on the dimensionality required to compute Boolean gates. For a single threshold layer with a Gaussian random dictionary and uniformly random sparse Boolean inputs, the authors derive precise dimension thresholds under two error criteria: one based on vanishing expected error count and another on high‑probability correctness of every output. The study reveals a geometric distinction—ball geometry for expected‑count thresholds and box geometry for joint reliability—explains the gap via shared reads, and provides explicit thresholds for conjunction, disjunction, and majority gates, including a detailed analysis of pairwise conjunction near the threshold.