The Complexity of Learning Sparse Superposed Features with Feedback

Akash KumarICML 2025 · OpenReview

Abstract

This paper investigates how efficiently we can extract the latent features learned by neural networks using simple relative feedback (e.g., "Is feature A more similar to B than to C?"). The authors prove that while general feature recovery requires quadratic complexity relative to the number of features, this can be significantly reduced if the features have a low-rank structure. This provides a theoretical foundation for distilling complex models into interpretable ones.

Introduction

Modern neural networks, especially Large Language Models (LLMs), represent information in a high-dimensional latent space. A major challenge in mechanistic interpretability is understanding these features. Often, models use "superposition," packing more features into a layer than there are physical dimensions (e.g., representing 1,000 concepts in a 512-dimensional vector).

While researchers use tools like Sparse Autoencoders (SAEs) to find these features, the complexity of retrieving them remains poorly understood. This paper asks: If we have a "teacher" (like a human or a more powerful AI) that can provide relative feedback on feature similarity, how many questions do we need to ask to perfectly reconstruct the model's internal feature dictionary?

Methodology

The authors frame feature learning as a problem of identifying a feature matrix (a covariance matrix or Mahalanobis distance) that defines how the model perceives similarity.

They analyze four primary feedback scenarios:

  1. Standard Constructive: The agent can invent any activation vector to ask the learner about.
  2. Sparse Constructive: The agent is restricted to using sparse activations (only a few features active at once).
  3. Standard Sampling: The agent must pick from a random pool of activations.
  4. Sparse Sampling: The agent picks from a pool of sparse activations.

The core approach involves triplet comparisons: the learner is told whether activation $\alpha$ is closer to $\beta$ than it is to $\zeta$. Mathematically, these inequalities reduce to linear constraints on the feature matrix. The authors also provide a practical optimization algorithm that uses gradient descent to solve for the feature matrix when dealing with massive, real-world dictionaries.

Datasets

The theory is validated across three distinct domains:

  • Synthetic Monomial Regression: Using Recursive Feature Machines (RFM) to recover a known "ground truth" feature matrix.
  • Board Game Models: Dictionaries extracted from ChessGPT and OthelloGPT (specifically MLP layers with dimensions like 4096 × 512).
  • Large Language Models: Features from Pythia-70M, focusing on attention output layers.

Key Insights

  • The Quadratic Barrier: To learn a dictionary of $p$ features, $O(p^2)$ queries are generally needed because a symmetric matrix has roughly $p^2/2$ degrees of freedom.
  • Low-Rank Efficiency: If the features live in a lower-dimensional subspace (rank $r$), the complexity drops to roughly $O(r^2 + p)$. This is a significant efficiency gain if task-relevant features are fewer than the total possible features.
  • Sparsity Trade-offs: While sparse activations are more interpretable and memory-efficient, they can make learning harder in the "sampling" regime. It becomes rarer to find the specific combinations of features needed to define the space's boundaries.
  • The "Oblivious Learner": The paper assumes an oblivious learner that simply picks any matrix fitting the feedback, providing a robust, worst-case bound.

Key Results

The authors established the first tight bounds for feedback complexity in these settings.

Comparison of feature matrix recovery across different feedback mechanisms.
  • Empirical Validation: In the RFM experiments, the learner reached the ground-truth Mean Squared Error (MSE) using exactly the number of feedbacks predicted by the theory (e.g., 55 feedbacks for a specific rank-8 task).
  • Scaling to ChessGPT: For a 4096-dimensional dictionary, they achieved a Pearson Correlation of 0.9773 (nearly perfect recovery) using approximately 8.4 million queries. This confirms that the quadratic scaling holds even at scale.
  • Sparsity Effects: As shown in the comparison above, increasing the sparsity of sampled activations requires significantly more samples to recover the ground truth. The "Sparse Sampling" method exhibits a much higher MSE under the same number of feedbacks, confirming the theoretical limitations.

Limitations and Future Work

  • Normal Transformation: The method recovers the dictionary up to a normal transformation (rotation and scaling). Exact original vectors require additional assumptions like strong incoherence (orthogonal rows).
  • Exact vs. Approximate: The current theory focuses on exact recovery. Future work exploring $\epsilon$-approximate recovery might require fewer queries for practical use.
  • Human-in-the-loop: While the paper uses AI teachers, the ultimate goal is to utilize human feedback to steer or audit model features, which remains an open experimental frontier.

Summary updated

Abstract

The success of deep networks is crucially attributed to their ability to capture latent features within a representation space. In this work, we investigate whether the underlying learned features of a model can be efficiently retrieved through feedback from an agent, such as a large language model (LLM), in the form of relative triplet comparisons. These features may represent various constructs, including dictionaries in LLMs or components of a covariance matrix of Mahalanobis distances. We analyze the feedback complexity associated with learning a feature matrix in sparse settings. Our results establish tight bounds when the agent is permitted to construct activations and demonstrate strong upper bounds in sparse scenarios when the agent's feedback is limited to distributional information. We validate our theoretical findings through experiments on two distinct applications: feature recovery from Recursive Feature Machine-trained models and dictionary extraction from sparse autoencoders trained on Large Language Models.
BibTeX
@inproceedings{kumar2025complexity,
  author = {Akash Kumar},
  title = {{The Complexity of Learning Sparse Superposed Features with Feedback}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=DvRuQ6mObK},
}
Figure