From Flat to Hierarchical: Extracting Sparse Representations with Matching Pursuit

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Standard Sparse Autoencoders (SAEs) assume the Linear Representation Hypothesis (LRH)—that neural network features are linearly accessible and globally quasi-orthogonal—but this fails to capture hierarchical, nonlinear, or multimodal features observed empirically. The authors introduce MP-SAE, which unrolls the Matching Pursuit algorithm into a residual-guided sequential encoder that promotes conditional orthogonality. Applied to CLIP and other VLMs, MP-SAE uniquely recovers genuinely multimodal features that standard SAEs split into modality-specific dictionaries.

Problem

Standard SAEs operationalize LRH by learning overcomplete, approximately orthogonal dictionaries via linear encoders. However, recent work shows neural representations encode: (i) hierarchically structured concepts where orthogonality holds only across hierarchy levels (conditional orthogonality, not global), (ii) nonlinearly accessible features that cannot be recovered by a single linear projection, and (iii) multi-dimensional features for temporally structured concepts. Existing SAEs—including those with explicit hierarchical objectives (Matryoshka SAE)—cannot faithfully capture these structures. For VLMs specifically, standard SAEs collapse into bimodal "split dictionaries" with features selective to either vision or language, missing the cross-modal shared structure.

Method

MP-SAE embeds the classical Matching Pursuit (MP) algorithm as the encoder of a sparse autoencoder, with a shared learned dictionary for encoding and decoding. At inference, MP-SAE runs for T greedy steps: 1. Compute inner products between the current residual r⁽ᵗ⁾ and all dictionary columns D. 2. Select the best-matching feature j⁽ᵗ⁾ = argmaxⱼ (D⊤r⁽ᵗ⁾)ⱼ. 3. Project the residual onto that feature, add the contribution to the reconstruction, and subtract it from the residual: r⁽ᵗ⁺¹⁾ = r⁽ᵗ⁾ − z_{j⁽ᵗ⁾} D_{j⁽ᵗ⁾}.

By Proposition 3.1, D_{j⁽ᵗ⁻¹⁾}⊤ r⁽ᵗ⁾ = 0 (stepwise orthogonality), so each selected feature must explain variance orthogonal to all previously selected features. This promotes conditional orthogonality across features selected at different steps. Nonlinear access arises because each step's projection φ(r⁽ᵗ⁾) is linear in the residual but the residual itself is a nonlinear function of the input. The dictionary is learned end-to-end via backpropagation minimizing reconstruction loss. Expansion factor p = 25m is used throughout.

Key Contributions

• Conditional Orthogonality (Definition 2.3): Formalizes the structure of hierarchical representations—orthogonality required only across hierarchy levels, not within them—as a stress-test for SAEs beyond LRH's scope.
• MP-SAE architecture: A sparse autoencoder whose encoder unrolls the Matching Pursuit algorithm, enabling hierarchical and nonlinearly accessible feature recovery without modifying the decoder.
• Synthetic hierarchy benchmark: Demonstrates that Vanilla, BatchTopK, and Matryoshka SAEs each fail to jointly recover intra- and inter-level structure; MP-SAE is the only method that does so under low-to-moderate interference.
• Multimodal feature recovery in VLMs: Shows MP-SAE uniquely produces a flat (non-bimodal) modality score distribution on CLIP/COCO, recovering cross-modal features that standard SAEs cannot.
• Adaptive inference-time sparsity: MP-SAE is the only architecture that guarantees monotonically non-increasing reconstruction error as k increases at test time, without retraining.

Results

• Expressivity (R² vs. sparsity Pareto frontier): MP-SAE achieves consistently higher R² at identical sparsity levels across SigLIP, DINOv2, CLIP, and ViT (expansion factor 25×). No absolute numbers reported; results shown as Pareto curves.
• Effective rank: As sparsity k increases, MP-SAE's co-activation matrix effective rank grows steadily; standard SAEs saturate quickly.
• Babel coherence: MP-SAE dictionaries have higher global Babel scores than standard SAEs, but lower Babel scores among co-activated subsets at inference—demonstrating conditional orthogonality in practice.
• Adaptive sparsity: Only MP-SAE shows monotonically improving reconstruction error when k is varied at test time; TopK SAEs degrade under sparsity mismatch; ReLU SAEs plateau.
• Multimodal features (CLIP + COCO): Standard SAEs yield sharply bimodal modality score distributions; MP-SAE produces a substantially flatter distribution with significant mass in the 0.3–0.7 midrange, indicating shared vision–language units. Results replicate on AIMv2, SigLIP, SigLIP2.
• Synthetic benchmark: MP-SAE uniquely recovers both flat (intra-level) and hierarchical (inter-level) structure across low-to-moderate within-level correlation regimes; Matryoshka preserves hierarchy at the cost of flat structure; Vanilla/BatchTopK preserve flat structure at the cost of hierarchy.

Limitations

• MP-SAE assumes representations can be incrementally explained by conditionally orthogonal features; this inductive bias may be poorly matched to flat or categorically structured representations.
• Matching Pursuit is a greedy algorithm with no global optimality guarantee; it may be brittle under extreme noise.
• Under high within-level interference in the synthetic benchmark, MP-SAE sacrifices flatness to preserve hierarchy—revealing a regime where its inductive bias actively conflicts with flat structure.
• Analysis of VLMs focuses on final-layer frozen representations; behavior in intermediate layers or fine-tuned models is not studied.
• No absolute benchmark numbers are reported; comparisons are qualitative (Pareto curves, distribution shapes) rather than precise quantitative deltas.

Relevance to Vision-Language Models

MP-SAE directly addresses a known failure mode of SAEs applied to VLMs: the "split dictionary" problem, where standard SAEs decompose joint visual-language embedding spaces into modality-exclusive features rather than shared cross-modal concepts. By recovering genuinely multimodal dictionary atoms from CLIP (and confirmed on AIMv2, SigLIP, SigLIP2), MP-SAE provides a more faithful mechanistic interpretation of how VLMs represent shared semantic structure across vision and language. The insight that residual-based inference first explains modality-specific variance and then surfaces cross-modal residuals explains why the approach works for VLMs, and connects to broader questions about the geometry of aligned embedding spaces and what interpretability tools must assume to be useful for multimodal models.