- Rating
- 1
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper proposes a formal definition of "feature" in mechanistic interpretability (MI). Based on this definition, the authors formulate finding features as a combinatorial optimization problem (KMF) and prove that it is NP-complete and hard to approximate. They propose two heuristics to solve it: one solves a relaxed MINLP, and the other combines local search with beam search.
Critical strengths
- The paper addresses a real gap: "feature", the most basic concept in MI, still lacks a formal definition.
- Formulating feature discovery as a combinatorial optimization problem, with an MINLP formulation, is a new perspective.
- The experiments cover both vision and language models.
Critical weaknesses
- The feature direction is decoupled from the block's neurons. In Definition 1, is the mean over all neurons on the samples , so it depends only on and not on . As a result, C1 constrains the neurons, while C3 effectively constrains only how samples are grouped. The only justification given (§3.1) is that restricting to the block's neurons would prevent comparison in . This does not hold: zero-padding outside also gives a vector in . The choice has a direct consequence. Concepts that frequently co-occur (e.g., eyes/nose, ship/water) will cover the same or heavily overlapping in a limited probing set. Their directions will then be nearly identical, so C3 rules them out and they can never be features at the same time. The example in Appendix A.1 shows the same problem: two nested blocks are judged nearly orthogonal, and what decides this is a neuron that belongs to neither block.
- The theoretical results add little. The NP-hardness proof only uses instances with , where C2 and C3 hold trivially, so the problem reduces to the known Max-Edge Biclique problem [1]. The inapproximability result is inherited from it in the same way. The theory therefore says nothing about what the MI-specific constraints contribute.
- Features depend on the probing dataset, not only on the model. In MI, a feature should be a property of the model itself. Under Definition 1, however, a block is a subset of the samples in , and is a mean over those samples. The normalization of the activation matrix and the threshold are also computed from (App. A.8). In the experiments, consists of only 50 randomly drawn samples per class, with a single fixed seed, and the paper does not analyze whether the results are stable.
- Incorrect citations. Several citations credit the wrong work. For example, SAEs in MI are attributed to Han et al. (2018)[2], on measuring pressure in clothing, and Shi et al. (2020)[3], on diagnosing faults in rolling bearings. BDAS is attributed to Grant et al. (2026)[4], but it was introduced by Wu et al. (2023)[5].
Taken together, these issues make it hard to accept Definition 1 as a faithful formalization of the MI notion of feature.
References
[1] R. Peeters. The maximum edge biclique problem is NP-complete. Discrete Applied Mathematics, 131(3):651–654, 2003.
[2] Tao Han, Kuangrong Hao, Yongsheng Ding, and Xuesong Tang. A sparse autoencoder compressed sensing method for acquiring the pressure array information of clothing. Neurocomputing, 275:1500–1510, 2018.
[3] Peiming Shi, Xiaoci Guo, Dongying Han, and Rongrong Fu. A sparse auto-encoder method based on compressed sensing and wavelet packet energy entropy for rolling bearing intelligent fault diagnosis. Journal of Mechanical Science and Technology, 34(4):1445–1458, 2020.
[4] Satchel Grant, Simon Jerome Han, Alexa Tartaglini, and Christopher Potts. Addressing divergent representations from causal interventions on neural networks. In Proc. of Int. Conf. on Learning Representations (ICLR), pp. 11330–11356, 2026.
[5] Wu, Zhengxuan, et al. "Interpretability at scale: Identifying causal mechanisms in alpaca." Advances in neural information processing systems 36 (2023): 78205-78226.
Questions for authors
- The objective in Problem 1, $ f(\mathcal{F}^{L,D}) = \sum_k |V^k_{N,S}| = |N_L^k|\cdot|S_D^k| $, is written incorrectly: the right-hand side drops the sum over . Also, since blocks may overlap, this objective counts overlapping cells more than once, so it does not measure the "coverage" the authors describe.
- Could the authors compare against a direction defined on and zero-padded elsewhere?
- Are the discovered features stable when the probing set is resampled with different seeds? For example, after matching features across seeds, what are the overlap of and the cosine similarity of ?
- Please carefully check all citations in the paper.
2 comments
I thank the authors for their response and ablation experiments on the stability.
However, I share Reviewer 4umd's view, there is no foundation for claims about the complexity of understanding, it's just the complexity of solving the authors' own proposed problem. As stated in the proof of Theorem 1, with K = 1 the maximality and ε-orthogonality conditions hold trivially, so the hardness comes entirely from maximizing |N|·|S| (i.e., Max-Edge Biclique), which is a modeling choice rather than a property of understanding or of features themselves.
In other words, first the proposed feature definition is still questionable and not convincing to me (in particular, the decoupling of from N_k raised in my review), second the complicated NP problem building on top of this definition further weakens the foundation of the paper.
So I will maintain my current rating. But as I indicated by my confidence score, I am not an expert in complexity theory, and the AC may weigh my evaluation accordingly.
Authors Rebuttal Reviewer 3 Submission 20777
We thank the reviewers for the time spent on our work and for the comments and insights they provided, which we have done our best to address. The paper has been updated accordingly, and each answer below points to the lines of the revised manuscript where the corresponding change was made. Full citations of the works we mention can be found in the bibliography of the paper.
Feature definition concerns and zero-padding N_k [R3W1], [R3Q2]. The direction does depend on Nk, albeit indirectly, via the samples on which the block’s neurons satisfy C1 (§3.1, added lines 196-200). Zero-padding outside Nk, e.g. ablating the other neurons, would yield a different ϕ, altering the cosine similarity between features and the direction itself, since all neurons of the layer take part in the linear combination a feature is. On co-occurring concepts, features are concepts as the network encodes them, not as a human names them, as discussed in our answer to [R1W1, R1Q1]. Two concepts distinct for the model must differ on some samples; if they always share samples and fire the same neurons, they collapse into one feature. Maximality is irreducibility w.r.t. what the network represents, not human-level concepts. What remains a limitation is that a probing set too small to expose a distinction the network does make would collapse the corresponding blocks, a matter of how D is sampled, not of the definition. Appendix A.1 rules out exactly this case. A direction defined on Nk and zero-padded elsewhere [R3Q2] is not the direction MI posits, so comparing against it would compare against a variant that does not adhere to the assumptions.
NP-hardness proof [R3W2]. We use K=1 because reducing to a subfamily of instances is standard practice for such results, which is what grounds the reduction. NP membership holds for arbitrary K (Appendix A.3), so KMF is NP-complete. As the reviewer points out, we make no claim on how the MI constraints affect complexity for K>1, which remains an open question. Empirically, however, solving the exact formulation with growing K increases execution time exponentially, which is why those runs are not reported in the paper, consistent with the (2(l+d))K search space of §3.2. The contribution is the link between MI feature discovery and a hardness result, stated for the first time thanks to a formal notion of feature. The consequence is practical, per the Ethics Statement: the features any method returns are approximations, and interpretations built on them should be treated accordingly.
Stability experiments [R3W3], [R3Q3]. We agree, and have updated the evaluation accordingly. All experiments were re-run over 10 seeds for drawing D, and every table now reports mean and standard deviation across runs, identically for our methods and all baselines. Stable scores do not by themselves imply the same features are recovered across seeds, so we also matched features across runs and measured the overlap of their neuron sets Nk and the cosine similarity of their directions ϕ(Fk) (Appendix A.10, Tables 11-12). L&B-search is among the most reproducible methods on the second-last layer, while SAE and BDAS are the least, often returning features with no counterpart in another run. Stability also increases with K on 4 of 5 models, consistent with K being below the number of distinct structures the layer carries. We added a dedicated paragraph in §6 (lines 482-523) Features are indeed defined w.r.t. a probing set, as the activation matrix is the only empirical access to the model assumed, with normalization and t derived from it (Appendix A.8). Whether the retrieved features were an artifact of a particular draw of D is what these results address.
Incorrect citations [R3W4], [R3Q4]. Han et al. (2018) and Shi et al. (2020) are cited for SAEs as a technique originating in compressed sensing, not for their use in MI. We agree a reference for the latter should also be given, and added Elhage et al. (2022). On BDAS, the method is indeed introduced by Wu et al. (2023), now cited as its source. We also went through all the remaining citations and corrected them where needed, for instance attributing Spectral Co-clustering to Dhillon (2001) instead of Von Luxburg (2007).
Objective function [R3Q1]. The reviewer is right about the notation, now corrected to ∑k∣NkL∣⋅∣SkL∣. On the second point, the coverage we aim at is per feature, not over the set of features taken together: a sample can express several features, and a neuron can carry several of them, so a cell can rightfully belong to more than one block (added lines 224-226, §3.2). Maximizing distinct covered cells would favour blocks that partition the matrix, each covering only part of the samples where its feature is expressed. We want each feature to span as many of its own samples and neurons as possible, which is what the cumulative size expresses.