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:
- 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.
- 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