Linear-Readout Floors and Threshold Recovery in Computation in Superposition

arXiv:2605.01192v1 Announce Type: new Abstract: Two recent approaches to computation in superposition reach different recursive capacity regimes: Hanni et al. certify ilde{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 Omega(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 Omega(s/d) average per-coordinate squared error on Bernoulli sparse states. Matching the Welch floor against the published tolerance of the Hanni 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 Hanni template is left open.

Source: arXiv cs.LG | 2026-05-05