Research map / Large language models / Language, safety and interpretability

The Complexity of Learning Sparse Superposed Features with Feedback

ICML 2025 · Large language models › Language, safety and interpretability · approach: Mechanistic analysis of attention and representations

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies the feedback complexity of learning a PSD feature matrix (dictionary covariance / Mahalanobis metric) from relative triplet or pairwise similarity feedback from an agent such as an LLM, giving tight bounds for constructive feedback and bounds for sampled sparse activations, validated on RFM and SAE dictionaries.

Problem

How many relative similarity feedback queries are needed for an oblivious learner to recover a feature matrix (normal transformation DD^T) of a model's dictionary, in constructive and sampled, general and sparse activation settings.

Approach

Reduces triplet feedback to pairwise equality constraints on quadratic forms and shows that the feedback complexity is governed by the rank of the feature matrix (tight Θ(r(r+1)/2 + p − r − 1) for constructive general activations), with sparse-sampling bounds derived via Sard's theorem and Hoeffding's inequality.

Key results

• Eigendecomposition feedback reaches ground-truth MSE with about 38 feedbacks on the rank-8 RFM target in R^10 (theoretical bound 38, p(p+1)/2=55).
• On the ChessGPT SAE dictionary (4096x512), sparse constructive feedback reaches PCC 0.9773 with about 8.39M feedbacks, while sparse sampling needs roughly 4M samples to exceed PCC 0.96.
• Sparse sampling with 10M feedbacks on Pythia-70M dictionary reaches PCC 0.65, showing that sampled feedback needs very large budgets for large dictionaries.

Measured effects reported in the paper

Surprising findings

• Sparse dense-feature representation can require Omega(p^2) feedbacks even when the target is low rank, since sparse representations of dense rank-1 features need many terms.
• Sampled feedback from i.i.d. activations cannot exactly satisfy equality constraints almost surely, so exact recovery requires rescaling samples.

Limitations

• Recovery is only up to normal transformation; full dictionary recovery holds only under strong incoherence (orthogonal rows).
• Sampled sparse-setting bounds are loose relative to practical sample requirements, and dictionaries of large size need very many feedbacks.
• Experiments use an agent with access to the target feature matrix rather than a real LLM or human agent.

Experimental setup

Datasets: synthetic monomial regression data (Gaussian inputs in R^10) SAE dictionaries from ChessGPT SAE dictionaries from Pythia-70M

Benchmarks: synthetic monomial regression feature recovery ChessGPT SAE dictionary recovery Pythia-70M SAE dictionary recovery

Metrics: mean squared error Pearson correlation coefficient feedback count

Baselines: Eigendecomposition feedback Sparse Constructive feedback Random Gaussian sampling Sparse sampling

Builds on: Recursive Feature Machines sparse autoencoders Lemma from dictionary learning recovery (Gribonval and Schnass)

Closest papers by meaning

• Compute Optimal Inference and Provable Amortisation Gap in Sparse Autoencoders (ICML 2025 · similarity 0.86)
• Scaling and evaluating sparse autoencoders (ICLR 2025 · similarity 0.85)
• Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.85)
• Jacobian Sparse Autoencoders: Sparsify Computations, Not Just Activations (ICML 2025 · similarity 0.85)
• A is for Absorption: Studying Feature Splitting and Absorption in Sparse Autoencoders (NeurIPS 2025 · similarity 0.85)
• Sparsing Law: Towards Large Language Models with Greater Activation Sparsity (ICML 2025 · similarity 0.85)