The superposition-recovery floor is computational, not information-theoretic¶

Question (posed cold). A VSA memory superposes M key-value pairs into one vector s = Σ bind(k_i, v_i). Naive unbind + cleanup recovers reliably only up to M/D ≈ 0.1–0.3 before crosstalk dominates. Is that floor an information wall, or can some decoder push blind recovery toward M/D ≈ 1 while keeping soft/graceful readout (i.e. not by switching to an exact coded store with a hard cliff)?

Answer (two parts). With the standard random code, no blind decoder crosses M/D ≈ 0.27 — thirteen methods across eight families floor there (see below), because it is a statistical-to-computational hard phase of the random ensemble (the solution exists and is verifiable to ≥1.5·D, but no poly method finds it blindly). But the floor is a property of the random code, not a wall: co-designing the encoder as a spatially-coupled (SC-SPARC) code — the standard capacity-achieving construction — crosses it with a polynomial decoder at matched storage and preserves soft readout. Verified independently here: at M/D = 0.29, the random code recovers 0.43 while the coupled code recovers 0.92, with the decoding wave propagating through fully- interfering middle blocks (not sharding). And with the coupling width tuned (w≈8) it is noise-robust — it strictly dominates the bundle across the practical corruption range (at 10% dropout, 0.82 vs 0.41; at 10% AWGN, 1.00 vs 0.58), degrading gracefully and converging to parity only under heavy corruption. So: capacity beyond the floor comes from code design — a real ~+33–50% capacity gain that keeps graceful degradation across the useful noise range, established coding theory (threshold saturation) transplanted to the VSA floor. The floor is not fundamental, and the capacity/robustness tension is not exclusive.

This corrects a loose earlier reading. §25/§26 of PREREGISTRATION-binding-readout.md reached M ≈ D — but only with exact coded key-value stores (pinv / Reed-Solomon / XOR), which have a hard cliff and lose soft similarity. That is not "beating the superposition floor with graceful readout"; it is choosing the coded-store corner of the tradeoff. For soft superposition recovery the floor stands.

The two verified facts¶

Both reproduced independently (not just taken from the exploration agents), on a genuine capacity test: unitary keys (exact-inverse HRR — the strong Plate/Frady baseline), a shared L=64 value codebook reused across the M facts (real crosstalk, not one-symbol-per-fact). Script: scripts/superposition_floor.py (numpy, seeds 0..4).

(1) The floor. Blind recovery — naive HRR unbind, and Approximate Message Passing (AMP, the Bayes-optimal iterative decoder) — saturates near M/D ≈ 0.25–0.27, dimension-invariant (the transition sharpens with D, confirming it is a real phase transition, not a small-D artifact):

(2) The gap is computational. Initialise a hard Gauss-Seidel solver at the true support (a "genie") and it stays there — and no random restart ever finds a competing exact fit — all the way to M/D = 1.5 (the largest load tested):

So the true solution is a stable, exactly-fitting, verifiable fixed point to ≥1.5·D, while every blind method is trapped in spurious minima (residual ~3 vs truth's 0). In noiseless exact arithmetic the information is plainly there — 256 real numbers carry the ~2300 bits of M·log₂L easily — so the barrier is entirely computational: verifiable ≠ findable. This refutes a strict "info-theoretically impossible past ~0.5·D" reading and matches the known SPARC/CDMA hard-phase picture (a low algorithmic threshold ≈0.27 far below the information threshold). The practical capacity limit is instead set by quantization/noise — which is exactly why deterministic HMS shards.

Soft/graceful readout is preserved throughout: the AMP posterior on the true entry degrades continuously across the transition (no cliff) — the property an exact code would destroy.

What was explored, and why each floored¶

Seven mechanisms, run cold with an explicit mandate to test any bound invoked rather than assume it. Per-mechanism curves are from the exploration agents; the floor and the computational-gap crux (rows 1–2's numbers) were independently reproduced.

The convergence is the result: eight decoders (including the naive baseline), one floor, each failing for a different, tested reason, all consistent with a single computational hard phase.

Attacking the assumptions: does any stronger solver break 0.27?¶

The "0.27 is fundamental" claim rests on two assumptions, not proven theorems: that AMP is optimal, and that the statistical-to-computational hard phase is real. The shared codebook actually violates AMP's iid state-evolution premise, so AMP need not be optimal here. Six solvers, each validated at M/D=0.10 (all 1.000), pushed past the floor (scripts/superposition_floor_probes.py, D=256, 5 seeds):

Two findings, both honest:

• Assumption #1 was partially false — and it didn't matter. VAMP/OAMP (built for correlated designs) is strictly better than AMP: it holds 100% at M/D=0.25 where AMP has already frayed to 0.875, confirming the shared-codebook correlation was hurting AMP. But it only nudges the reliable knee ~0.25→0.27; at M/D=0.30 it collapses with everything else. The best available solver confirms the floor rather than breaking it.
• Local search hurts past the floor (AMP+refine, multistart both fall below plain AMP at M/D≥0.30). Refining a blind estimate drives it into a spurious minimum — a direct, positive signature of the trap-dominated landscape the hard-phase predicts.

So the assumption-attack strengthens the conclusion: the floor survived VAMP, annealing, local-search refinement, and 32-restart search, and the one place AMP was genuinely suboptimal (the correlation) buys only ~0.02 in M/D.

The OGP-evader (lattice reduction) also fails¶

The Overlap Gap Property obstructs stable/local algorithms, but lattice reduction (LLL/BKZ) is a global algebraic method and the textbook OGP evader — the one poly candidate with a theoretical reason to cross. It was tested with a correct CVP embedding (the true assignment is the unique closest vector; validated at 100% recovery at low load). Verdict, head-to-head at matched (D, L): LLL is strictly worse than AMP. At D=48, L=8, M/D=0.50, AMP=0.94 vs LLL=0.13; at L=16, M/D=0.30, AMP=1.00 vs LLL=0.09. LLL collapses at or below the AMP threshold, and worsens as N=M·L grows — because its approximation factor is exponential in the lattice dimension (D+M+N), so Babai rounding on the reduced basis fails long before the information limit. (An earlier raw sweep showed LLL at 100% past M/D=0.5 for L=4 — a confound: small L is easy for every method, AMP included. Matched comparison removes it.) So the last poly-time algorithm candidate is closed too; the crossing below comes from the encoder, not the decoder.

The bigger lever: the floor is the value prior, not superposition¶

The whole floor sweep fixed the value model to "one of L codebook vectors" (block-one-hot). That choice is what makes recovery combinatorial — N = M·L unknowns — and sets the ~0.27·D AMP threshold. Change the value model to a continuous amplitude (one of L PAM levels on a per-key vector) and recovery becomes the linear solve s = K a (N = M unknowns), whose only limit is identifiability at M/D = 1.0. Verified (scripts/superposition_floor_priors.py): 100% recovery to M/D=0.95, collapsing at 1.0 — a poly decoder (least-squares) with graceful soft readout, ~3.7× the one-hot floor, at the same log₂L bits/fact. Small-alphabet PAM-AMP pushes past 1.0.

This corrects an earlier claim in this doc that reaching M≈D requires a "hard cliff, no soft recall": the continuous high-capacity route is graceful; the cliff was an artifact of exact coded (Reed–Solomon/XOR) stores, not of high capacity.

The honest catch: continuous amplitudes are SNR-hungry (L levels packed into amplitude → small minimum distance), so under even 5% noise the one-hot code is more robust at low load. Total information per dimension is roughly conserved (~1.6–1.9 bits/dim across schemes). So the deep structure is not a wall but a capacity/robustness tradeoff on the value-encoding axis: the 0.27·D "floor" is simply where the robust (one-hot) encoding sits; spend the budget on fragile amplitudes → M/D→1.0 clean, or on a coupled code → ~0.5 noise-robust. There is no capacity wall, only a budget and where you spend it.

Crossing it: co-design the encoder (spatially-coupled code)¶

The decoder sweeps all fix the encoder to a random bundle. But the hard phase is a property of the random ensemble — and coding theory's central result is that designed codes (LDPC, polar, spatial coupling) reach capacity with polynomial belief-propagation decoders by engineering the hard phase away (threshold saturation). Applied here (scripts/superposition_floor_coded.py, verified independently):

Same storage (both store s ∈ R^D, same M facts, same D), same polynomial decoder (block section-AMP, which reduces to the harness AMP and reproduces the floor on the random code — the correctness guard). The coupled code's reliable knee rises from ~0.27 to ~0.34 (C=16) → ~0.40 (C=32), climbing toward the MAP/identifiability threshold as the chain lengthens. Per-block accuracy confirms it is real threshold saturation, not sharding: the decoding wave nucleates at the lightly-loaded seed block and propagates through fully-interfering middle blocks (local density = the aggregate rate), decoding them to ~1.0. Soft readout is preserved (continuous degradation, no cliff).

What this is and isn't. It is a genuine crossing of the floor with a poly decoder at matched storage — the floor is not fundamental. It is established coding theory (SC-SPARC threshold saturation; Donoho–Javanmard–Montanari 2013, Rush–Venkataramanan) transplanted onto the VSA-memory floor — validation, not a new algorithm.

Noise robustness (corrected — it is robust). An earlier pass called the crossing "clean-signal only." Direct frontier measurement (scripts/superposition_floor_robust.py, 6 seeds) refutes that. The fragility was an artifact of the narrowest coupling (w=3), which concentrates each fact into ~9% of dims. A coupling-width sweep finds w≈8 optimal — each fact spreads over ~24% of dims (dropout-robust) while the wave still nucleates. At that width, past the floor (M/D=0.284), coupled strictly dominates the bundle across the practical corruption range:

Often ~2× the bundle at 10% dropout, and degrading gracefully (continuous, no cliff). The honest bound: the advantage narrows to parity under heavy corruption (~30% dropout), and at extreme AWGN (σ≈0.4) the wide-w code dips slightly below the bundle — so it is a practical-regime win, not a universal one. But the capacity/robustness tension is not exclusive: a co-designed code beats the random bundle on both axes at matched storage across the operating range HMS cares about.

What it means for HMS¶

• Capacity beyond the floor comes from code design, and it survives moderate noise. No blind decoder beats the random floor (a measured statistical-to-computational gap), but a spatially-coupled encoder buys a real ~+33–50% facts/dim with a poly decoder and soft readout — and that advantage persists through ~20% AWGN and ~10–20% dropout, degrading gracefully. So it is a usable lever for HMS, not a clean-room-only curiosity; only under heavy corruption does it converge to the bundle (never worse). Sharding remains the route to capacity in the high-corruption limit.
• The two escapes each cost something concrete. Exact coded store → M ≈ D but hard cliff, no soft recall (§26). Side information → past the floor but at the bit-cost of the side information (sharding). Soft superposition recovery → floored at ~0.27·D. There is no free lunch, and now we know why (computational hardness), not just that.
• The holographic layer's value is not superposition capacity. It is the preserved soft/graceful readout (continuous degradation, noise robustness) and — the HMS novelty — verifiability/plasticity, not a higher fact-per-dimension count.

Honest scope¶

• Single clean bundle, one substrate class (unitary-key circular-convolution HRR / FHRR, shared Gaussian codebook), D up to 512–1024. The hard-phase is empirical here and consistent with SPARC/CDMA theory; it is not proven for this exact ensemble.
• "Computational hardness" means no polynomial method tested crossed it; it is not a proof that none exists. A genuinely novel superposition code remains open (and would be publishable) — but coupling, coherence design, learning, peeling, nonlinear lift, and Hopfield are now measured negatives, not untried ideas.
• The independently reproduced crux is scripts/superposition_floor.py.

Reproduce: the floor + computational gap — uv run python scripts/superposition_floor.py; the stronger-solver attack — uv run python scripts/superposition_floor_probes.py; the spatially-coupled crossing — uv run python scripts/superposition_floor_coded.py.