Provably Extracting the Features from a General Superposition

Allen LiuarXiv 2025 · DOI · arXiv

TL;DR

Modern machine learning models often pack more features into a representation than there are dimensions—a phenomenon known as superposition. This paper presents the first efficient algorithm to provably recover these hidden feature directions and their response functions from black-box query access, even when the features are highly correlated and the response functions are nearly arbitrary.

What Problem Does This Paper Address?

A cornerstone of modern AI interpretability is the Linear Representation Hypothesis: the idea that models represent concepts as directions in a high-dimensional vector space. However, models often exhibit superposition, where the number of features ($n$) exceeds the number of dimensions ($d$). In this "overcomplete" regime, recovering individual features is notoriously difficult.

Previous research has largely hit a wall:

  1. Passive Learning is Hard: Trying to learn these features from random samples (like a standard dataset) faces significant computational "lower bounds," meaning it's likely impossible to do efficiently for general functions.
  2. Specific Activations: Existing "query-based" methods (where you can ask the model for its output on any input) are often brittle, relying on specific properties of functions like the "kink" in a ReLU activation.

This paper asks: Can we provably and efficiently extract features in superposition for any general, nonlinear response function using only black-box queries?

Methods

The author treats the model as a sum of "ridge functions": $f(x) = \sum a_i \sigma_i(v_i^\top x)$, where $v_i$ are the feature directions and $\sigma_i$ are the response functions. The core innovation is a Fourier-space search algorithm.

Key steps include:

  • Gaussian Reweighting: To make the math tractable, the author multiplies the function by a Gaussian. In the Fourier domain, this transforms the "lines" of the feature directions into "tubes" of concentrated mass.
  • Iterative Fourier Search: Inspired by the Goldreich-Levin algorithm (used in boolean logic), the algorithm searches for "heavy" mass in Fourier space. It uses random orthonormal bases and "hyperplane-like slices" to narrow down the coordinates of the feature directions $v_i$ one by one.
  • Two-Scale Smoothing: The algorithm uses two different smoothing scales ($\ell_1, \ell_2$). One scale helps locate the directions $v_i$, while a much finer scale is used to reconstruct the specific shape of the nonlinear response functions $\sigma_i$ via interpolation.

Datasets

This is a purely theoretical paper. It does not use empirical datasets or benchmarks. Instead, it provides rigorous mathematical proofs for the algorithm's complexity and correctness.

Key Insights and Ideas

  • Nonlinearity is a Feature, Not a Bug: A major insight is that superposition only causes "non-identifiability" (the inability to distinguish features) if the response functions are linear. If the responses are nonlinear, the features become mathematically "visible" and separable, even when they are overcomplete ($n > d$).
  • Fourier Sparsity: The author observes that while the function $f(x)$ might be complex in the spatial domain, its Fourier transform is "sparse"—it is only supported on lines passing through the origin in the directions of the features.
  • Query Power vs. Passive Samples: The paper demonstrates that while "passive" learning (looking at a fixed dataset) is computationally hard, "active" query access (probing the model like an API) provides enough information to bypass these hardness barriers.

Key Results

  • Polynomial Efficiency: The algorithm is "efficient," meaning its runtime and the number of queries required grow only polynomially with respect to the dimension ($d$), the number of features ($n$), the Lipschitz constant of the functions ($L$), and the desired accuracy ($1/\epsilon$).
  • General Recovery: The algorithm successfully:
  • Identifies all nonlinear feature directions $v_i$ (up to sign and error).
  • Reconstructs the univariate response functions $\sigma_i$ over a bounded domain.
  • Robustness: Unlike prior work, this method does not require the feature directions to be nearly orthogonal or linearly independent; they only need to be "not nearly identical."

Limitations and Future Work

  • Query Access Requirement: The method requires "black-box query access," which is a stronger assumption than having a static dataset. In the real world, many models are behind APIs that limit queries or add noise.
  • Single-Layer Architecture: The current proof focuses on a "sum of ridge functions," which is equivalent to a neural network with one hidden layer. Extending this to deep, multi-layer architectures where features interact in more complex ways remains an open challenge.
  • Non-degeneracy: The algorithm cannot recover "linear" parts of the features (if a response function is purely linear, its direction isn't uniquely identifiable in a sum). The author acknowledges this but notes that the nonlinear parts—which are often the most interesting for interpretability—are fully recoverable.

Summary updated

Abstract

It is widely believed that complex machine learning models generally encode features through linear representations. This is the foundational hypothesis behind a vast body of work on interpretability. A key challenge toward extracting interpretable features, however, is that they exist in superposition. In this work, we study the question of extracting features in superposition from a learning theoretic perspective. We start with the following fundamental setting: we are given query access to a function \[ f(x)=\sum_{i=1}^n σ_i(v_i^\top x), \] where each unit vector $v_i$ encodes a feature direction and $σ_i:\R\to\R$ is an arbitrary response function and our goal is to recover the $v_i$ and the function $f$. In learning-theoretic terms, superposition refers to the \emph{overcomplete regime}, when the number of features is larger than the underlying dimension (i.e. $n > d$), which has proven especially challenging for typical algorithmic approaches. Our main result is an efficient query algorithm that, from noisy oracle access to $f$, identifies all feature directions whose responses are non-degenerate and reconstructs the function $f$. Crucially, our algorithm works in a significantly more general setting than all related prior results. We allow for essentially arbitrary superpositions, only requiring that $v_i, v_j$ are not nearly identical for $i \neq j$, and allowing for general response functions $σ_i$. At a high level, our algorithm introduces an approach for searching in Fourier space by iteratively refining the search space to locate the hidden directions $v_i$.
BibTeX
@misc{liu2025provably,
  author = {Allen Liu},
  title = {{Provably Extracting the Features from a General Superposition}},
  year = {2025},
  eprint = {2512.15987},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.15987},
}
Figure