PaperlayerView exact revision on arXiv

Source-linked AI summary

High-probability guarantees for linear accessibility in feature superposition

Enrico Vompa

arXiv:2609.09556v1stat.MLcs.AIcs.IRcs.LGmath.PR

TL;DR

Feature superposition allows neural networks to encode many concepts in limited dimensions, but interference can restrict linear decoding of simultaneously active features. The paper formulates this as compressed sensing, derives fixed-support high-probability bounds under subgaussian noise, and finds sufficient dimension scaling of d = O(k log m), with Gaussian approximations supporting the theoretical decoding regime.

  • Problem

    Cross-feature interference limits the linear accessibility of simultaneously active features in representations that encode more concepts than dimensions.

  • Method

    The paper frames linear accessibility as compressed sensing and derives fixed-support decoding guarantees using the subgaussian Hoeffding inequality, then estimates failure rates with Gaussian approximations.

  • Results

    d = O(k log m) dimensions suffice for the paper’s high-probability linear decoding guarantee, improving prior worst-case quadratic limits.

  • Takeaways & Limitations

    The results characterize geometric limits on linear accessibility and provide a framework for evaluating sparse autoencoders, compositional generalization, and neural interpretability.

  • Takeaways & Limitations

    Applying the guarantees to LLM representations requires their assumptions to hold, and how extensively LLMs use the characterized regime remains unknown.

Abstract

from arXiv · show

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 then validate these bounds across system parameters through Gaussian-tail approximations. These results quantify the geometric constraints of the linear representation hypothesis, providing a framework for evaluating sparse autoencoders, compositional generalization, and neural interpretability.

1 Introduction

Feature superposition can encode many concepts in fewer dimensions, but simultaneous activity creates interference that limits linear accessibility. This paper frames the problem through compressed sensing and derives high-probability bounds with linear dimension scaling.

  • Compressed-sensing framing: Compressed sensing models m features in d dimensions when only a sparse support of size k is active.This provides the paper’s formal framework for analyzing simultaneous feature decoding.
  • Motivation: Feature superposition lets neural networks encode more concepts than dimensions, while cross-feature interference constrains simultaneous linear accessibility.Related features can exhibit constructive interference, but arbitrary combinations may remain difficult to decode.
  • Contributions: High-probability bounds for arbitrary supports show feature superposition scales linearly with active features, improving prior worst-case quadratic limits.The bounds are derived under a linear decoding scenario using the subgaussian Hoeffding inequality.
  • Validation: Gaussian-tail approximations estimate failure rates and provide a practical check on the theoretical bounds across system parameters.The paper uses these approximations to assess whether the derived guarantees apply in practice.
  • Contributions: The required dimension is d = Oε(k log m) for fixed error and failure tolerances when noise satisfies σ = Oε(1/√log m).The result gives a sufficient dimension scale for fixed-support decoding guarantees.

2 Theory: compressed sensing framework

The paper models linear accessibility as compressed sensing: sparse feature signals are encoded into lower-dimensional sketches and recovered with a fixed matched-filter decoder. Fixed-support concentration bounds control interference and noise, yielding linear dimension scaling rather than worst-case quadratic scaling, while retaining a limitation to non-uniform support guarantees.

  • Compressed sensing framework: A k-sparse signal over m features is mapped into a d-dimensional sketch by summing the embeddings of its active features with independent observation noise.The framework uses unit-norm dictionary columns and an active support S with |S| ≤ k.
  • Linear decoding: Linear decoding estimates each coefficient with a single matched-filter projection, so cross-feature interference can create false positives on inactive coordinates or distort active estimates.The decoder computes each estimate from the inner product between a dictionary feature and the compressed sketch.
  • Worst-case scenario: d = Oε(k^2 log m) is the upper bound for uniformly controlling the matched-filter error over every k-sparse input, with a nearly matching Ωε(k^2 log k log m) lower bound for arbitrary linear decoders.This quadratic scaling reflects suppression of interference across all combinatorially many supports.
  • Fixed-support guarantee: A fixed-support analysis partitions the error budget between interference and projected noise, then uses subgaussian tail bounds and a union bound across features.The support is fixed to avoid the uniform-support combinatorial penalty, while inactive and active coordinates receive separate interference bounds.
  • Fixed-support guarantee: dreq = Oε(k log m) for fixed α and δint independent of m, k, and ε, establishing linear scaling in the number of active features.The interference constraint bounds the maximum cross-feature interference with probability at least 1 − δint.
  • Recovery and limitations: σmax = Oε(1/√log m) for fixed α and δnoise, while thresholding the ℓ∞ error bound guarantees support recovery under a suitable minimum active coefficient.The theorem applies to any arbitrary fixed support with joint failure probability at most Δ; it is not uniform over all supports.

3 Numerical tests: evaluating theory

Numerical tests compare empirical decoding failures with Gaussian-tail estimates across dimensions, sparsities, dictionary sizes, and noise settings. They also evaluate recovery under normalization and dictionary learning with OMP, LASSO, and LISTA.

  • Gaussian approximation: The Gaussian approximation provides a more precise failure-rate estimate than the conservative Hoeffding bound while remaining below it.The approximation models interference terms independently and uses a tail-matching factor bounded below by 0.5.
  • Gaussian approximation: As recovery success approaches 100%, δemp converges to δgauss, supporting the Gaussian approximation for required high-probability decoding dimensions.Similar results are reported for Gaussian and Laplace distributions.
  • Gaussian approximation: 40,000 trials evaluate high-probability decoding across k ∈ [2, 24], m ∈ {512, 1024, 2048, 4096}, d ∈ {64, 128, 256, 512}, and ε ∈ {0.1, 0.2, ..., 0.9}.The evaluation includes Rademacher-distributed signals and reaches a minimum failure rate of 0.25%, corresponding to 99.75% success.
  • Representation learning: Figures 4 and 5 evaluate recovery through the existence of a valid separating threshold across dimensions, sparsities, vector-space normalization, and noisy environments.RMSNorm changes state magnitudes, but normalization scales target signal and geometric interference together, preserving relative signal-to-interference ratios.
  • Error budget: Interference and noise jointly consume the error tolerance, so greater interference leaves less budget available for noise, and conversely.The analysis partitions ε into αε for noise and (1 − α)ε for interference, while independent contributions add in variance.
  • Representation learning: Figure 6 compares OMP, LASSO, and LISTA using percentile summaries of matched cosine similarities to ground-truth directions.OMP, LASSO, and LISTA differ in how they recover sparse codes and update or emulate dictionary-learning procedures.

4 Discussion

The discussion connects linear accessibility to nonlinear decoding in language-model representations while emphasizing that this connection remains speculative. It identifies non-mean-zero representations and reliance on external evidence as important scope boundaries.

  • 4.1 Unknown nonlinear transform: SAEs use single-step linear projection and ReLU, whereas Transformers can implement LISTA-type iterative nonlinear decoding algorithms.The paper proposes that this difference may help explain why SAEs fail at compositional generalization while denser superpositions remain accessible to nonlinear decoding.
  • 4.1 Unknown nonlinear transform: World Models treat nonlinear observations as linear transforms of latent world structure, while structural features may require nonlinear recovery.The discussion hypothesizes that base features are represented linearly and higher-order properties are derived through iterative perception or reasoning.
  • 4.2 Limitations: The connection between linear accessibility and LLM mechanics remains speculative and relies on external empirical evidence.The theoretical argument uses asymptotic normality and normalization to motivate subgaussian interference, but does not establish that LLM representations satisfy those conditions.
  • 4.2 Limitations: Because LLM representations are not necessarily mean-zero, the concentration proofs apply to their geometries only when the stated assumptions hold.The extent to which LLMs actually use the characterized linear accessibility remains unknown.

5 Conclusion

The paper characterizes high-probability linear accessibility for sparse feature superposition using a noisy linear representation model. It concludes that decoding requires logarithmic dependence on dictionary size and linear dependence on sparsity under the stated assumptions.

  • 5 Conclusion: d = O(k log m) dimensions suffice for decoding, clarifying geometric limits of the linear representation hypothesis.The conclusion frames learned superposition as potentially supporting compositional reasoning within these geometric limits.
  • Model: The model represents semantic features as normalized latent directions and observations as y = Ax + z.Here, A is the feature dictionary, x is sparse, and z is additive observation noise.
  • Assumptions: The guarantees analyze a fixed deterministic support S with 1 ≤ |S| ≤ k, avoiding the uniform-support combinatorial penalty.Inactive coordinates are set to zero, and each target has at most k interfering active features.
  • Assumptions: The dictionary columns are independent mean-zero unit-sphere vectors, active coefficients are bounded and independent of the dictionary, and noise has independent mean-zero subgaussian coordinates.The coefficient bound is |x_j| ≤ 1, while the noise coordinates satisfy ||z_n||ψ2 ≤ σ.

A.1 Error decomposition

The error decomposition separates linear-decoder error into cross-feature interference and projected observation noise. Partitioning the tolerance enables separate probability bounds whose union controls the total decoding failure event.

  • Error decomposition: Subtracting the true coefficient from the linear decoder estimate isolates error into cross-feature interference and projected noise.The normalized dictionary vector makes the self-term vanish.
  • Error decomposition: Coordinates with at least one interfering active feature form I, while coordinates with no interference have I_i = 0.The number of interferers satisfies s_i ≤ |S| ≤ k.
  • Error decomposition: The tolerance ε is divided into αε for noise and (1 − α)ε for interference, so exceeding ε implies that at least one allocated budget is exceeded.The triangle inequality places the total failure event inside a union of component-wise failures.
  • Error decomposition: A union bound over the interfering coordinates converts the maximum-interference failure event into a sum of individual tail probabilities.This supplies the probability-control step for bounding cross-talk across all coordinates in I.

A.2 Interference concentration

The analysis bounds interference by conditioning on fixed signals and target vectors, controlling projection moments through spherical symmetry, and applying exponential-moment and union-bound arguments across active and inactive coordinates.

  • Conditional interference analysis: Interference is analyzed for each fixed target coordinate by conditioning on the signal and target-vector realizations.The resulting bound is deterministic and therefore remains valid after averaging over the joint dictionary-and-signal distribution.
  • Projection-moment bounds: Spherical symmetry and pairings of projection factors bound the even moments of U_j = ⟨a_i, a_j⟩.The sphere version of Wick’s theorem supplies the pairing count used in the exponential-moment bound.
  • Tail control: The exponential-moment method converts the projection-moment bound into a two-sided tail bound for interference.Symmetry gives equal upper and lower tails, while Markov’s inequality and conditional independence factor the expectation.
  • Tail optimization: Choosing λ = dt/s_i minimizes the quadratic exponent used in the interference tail bound.The derivation explicitly avoids an unspecified absolute constant and proves the relevant constant is 0.5.
  • Joint interference constraint: The union bound separates inactive-coordinate false positives from active-coordinate false negatives when controlling maximum cross-talk.The active contribution vanishes when |S| = 1.

A.3 Gaussian approximation of δint

The Gaussian approximation models interference as a normalized sum of spherical projections, then matches its tail to the Hoeffding envelope to estimate failure probabilities across system parameters.

  • Gaussian interference model: σ^2 = s_i/d is the worst-case interference variance when independent spherical projections contribute across s_i active interfering features.The projective central limit theorem motivates approximating standardized interference by N(0, 1).
  • Tail matching: The tail-matching factor c_tail aligns the Gaussian approximation with the Hoeffding-envelope form at threshold t = ε.The comparison allocates the entire error budget to the interference term.
  • Failure-probability estimate: The Gaussian estimate applies a union bound over inactive and active coordinate counts M ∈ {(m − |S|), |S|}.The factor c_tail is substituted back into the Hoeffding envelope to compute δ_int.
  • Approximation behavior: The 0.5 floor prevents the numerical estimate from exceeding the baseline Hoeffding bound while retaining sharper Gaussian decay in favorable regimes.Successful decoding is more probable when the feature count is small relative to dimension and less probable when dimension is relatively smaller.

A.4 Noise concentration

Noise concentration bounds projected subgaussian noise uniformly across dictionary coordinates, then transfers the conditional guarantee to the joint dictionary-and-noise distribution.

  • Projected-noise bound: Projected noise N_i = ⟨a_i, z⟩ is a sum of independent, mean-zero subgaussian variables conditional on the dictionary.The subgaussian Hoeffding inequality supplies the coordinate-level tail bound.
  • Noise assumptions: The coordinate noise scale satisfies ∥z_n∥_ψ2 ≤ σ, while each dictionary vector has unit Euclidean norm.These assumptions control the subgaussian norm after factoring out dictionary coordinates.
  • Uniform coordinate control: A union bound over all m coordinates yields the conditional noise constraint at allocated threshold t = αε.The bound is then inverted to obtain the allowable noise scale.
  • Joint guarantee: The conditional noise bound holds under the joint distribution of (A, z) with failure probability at most δ_noise.Uniformity over every realization of A enables this transfer without changing the failure guarantee.

B Extended methodology

The extended methodology evaluates dictionary learning across dimensions and sparsities using stochastic alternating minimization, sparse-code solvers, and regularized dictionary updates.

  • Experimental setup: Dictionary learning is evaluated for d ∈ {64, 128, 256}, k ∈ [1, 50), and dictionary size m = 1024.Each iteration uses N = 50,000 samples generated as Y = D_true X.
  • Sparse coding: Sparse codes are estimated with OMP constrained to k nonzeros and LASSO optimized using 50 FISTA iterations with Nesterov acceleration.The passage describes both sparse-recovery procedures used in the evaluation.
  • Dictionary update: The dictionary is updated with ridge-regularized Method of Optimal Directions using penalty 10^-4.Degenerate atoms with ∥d_i∥_2 < 10^-8 are reinitialized from random batch samples.
  • Recovery evaluation: Recovery is evaluated up to sign and permutation ambiguities using Hungarian matching on a cost matrix based on −|D_true^T D|.This matching accounts for equivalent dictionary representations during recovery assessment.

C Gaussian approximation on other distributions

Figure A.2 evaluates the tightness of the Gaussian approximation for high-probability decoding across sparsity, dictionary size, dimension, and error-threshold settings.

  • 40,000 trials were run for every combination of sparsity k ∈[2, 24], dictionary size m ∈{512, 1024, 2048, 4096}, and dimension d ∈{64, 128, 256, 512}.The evaluations used error thresholds ε ∈{0.1, 0.2, . . . , 0.9}.
Loading 2609.09556v1…