Provably Extracting the Features from a General Superposition

2025/12/17 by Allen Liu, Liu, Allen
Computer Science · #Machine Learning and Algorithms #Advanced Graph Neural Networks #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2512.15987

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)=∑_i=1ⁿ σ_i(v_i^\top x), where each unit vector v_i encodes a feature direction and σ_i:\R→\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 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 ≠ 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.

Citations

• Provably Learning from Modern Language Models via Low Logit Rank
• Sequences of Logits Reveal the Low Rank Structure of Language Models
• Survey on Algorithms for multi-index models
• Model Stealing for Any Low-Rank Language Model
• Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics
• Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations
• Logits of API-Protected LLMs Leak Proprietary Information
• Stealing Part of a Production Language Model
• Computational-Statistical Gaps in Gaussian Single-Index Models
• Robustly Learning Single-Index Models via Alignment Sharpness
• The Linear Representation Hypothesis and the Geometry of Large Language Models
• On Learning Gaussian Multi-index Models with Gradient Flow
• A faster and simpler algorithm for learning shallow networks
• Agnostically Learning Single-Index Models using Omnipredictors
• Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models
• Learning Hidden Markov Models Using Conditional Samples
• Learning Single-Index Models with Shallow Neural Networks
• Governance Architecture for Neural Network Superposition: A Structural Solution to Hallucination via Routing and Interference Filtering
• Non-Gaussian Component Analysis via Lattice Basis Reduction
• Efficiently Learning Any One Hidden Layer ReLU Network From Queries
• Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations
• On the Cryptographic Hardness of Learning Single Periodic Neurons
• An Exact Poly-Time Membership-Queries Algorithm for Extraction a\n three-Layer ReLU Network
• Statistical-Query Lower Bounds via Functional Gradients
• Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
• Neural Additive Models: Interpretable Machine Learning with Neural Nets
• Reverse-Engineering Deep ReLU Networks
• Learning Two-layer Neural Networks with Symmetric Inputs
• Learning One-hidden-layer Neural Networks with Landscape Design
• Recovery Guarantees for One-hidden-layer Neural Networks
• Understanding intermediate layers using linear classifier probes
• Stealing Machine Learning Models via Prediction APIs
• When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity
• Nearly Optimal Sparse Fourier Transform
• Efficient Learning of Generalized Linear and Single Index Models with\n Isotonic Regression
• Most tensor problems are NP-hard
• Most Tensor Problems Are NP-Hard

Related

• Feature Cross Search via Submodular Optimization
• The Persian Rug: solving toy models of superposition using large-scale symmetries
• Agnostically Learning Multi-index Models with Queries
• Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations
• Mathematical Models of Computation in Superposition