acceptodds
Under review as a conference paper at ICLR 2027

The complexity of understanding: Formalizing Concept Discovery in Mechanistic Interpretability

Abstract

Mechanistic Interpretability (MI) is an emerging subfield of eXplainable Artificial Intelligence (XAI), which aims to reverse-engineer the internal representations of black-box machine-learning models (like neural networks) into human-understandable concepts. Despite increasing attention and promising results, the literature still lacks a formalization of the most basic and fundamental MI concept of "feature", leading to limited rigor and inconsistencies in the general adoption of MI, as well as a continued reliance on human judgment for its evaluation. In this work, we fill this gap by devising, for the first time, a formal definition of the notion of mechanistic feature, grounded in the core principles of the MI literature. We formulate a novel optimization problem to soundly identify mechanistic features according to our definition, and theoretically characterize it in terms of NP-completeness, inapproximability, and mixed-integer nonlinear programming (MINLP) formulation. To face the inherent computational complexity of the problem, we design two well-founded heuristics: one consisting in solving a relaxed yet easier- and faster-to-solve MINLP formulation of our problem, and the other relying on a combined local- and beam-search strategy. We extensively evaluate our methods on numerous datasets and testing scenarios. The obtained results demonstrate their high effectiveness and superiority over a variety of baselines.

Primary area:
interpretability and explainable AI
Keywords:
eXplainable AI, Mechanistic Interpretability, Concept Discovery

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_4mRiOpenReview ↗
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
  1. The feature direction is decoupled from the block's neurons. In Definition 1, ϕ(Fk)\phi(F_k) is the mean over all ll neurons on the samples SkS_k, so it depends only on SkS_k and not on NkN_k. 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 Rl\mathbb{R}^l. This does not hold: zero-padding outside NkN_k also gives a vector in Rl\mathbb{R}^l. The choice has a direct consequence. Concepts that frequently co-occur (e.g., eyes/nose, ship/water) will cover the same or heavily overlapping SDS_D 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.
  2. The theoretical results add little. The NP-hardness proof only uses instances with K=1K=1, 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.
  3. 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 DD, and ϕ\phi is a mean over those samples. The normalization of the activation matrix and the threshold tt are also computed from DD (App. A.8). In the experiments, DD 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.
  4. 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 kk. 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 NkN_k 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 NkN_k and the cosine similarity of ϕ\phi?
  • Please carefully check all citations in the paper.
2 comments
AuthorsOpenReview ↗

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 NkN_k, albeit indirectly, via the samples on which the block’s neurons satisfy C1 (§3.1, added lines 196-200). Zero-padding outside NkN_k, e.g. ablating the other neurons, would yield a different ϕ\phi, 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 NkN_k 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=1K = 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 KK (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>1K > 1, which remains an open question. Empirically, however, solving the exact formulation with growing KK increases execution time exponentially, which is why those runs are not reported in the paper, consistent with the (2(l+d))K(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 DD, 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 NkN_k and the cosine similarity of their directions ϕ(Fk)\phi(F_k) (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 KK on 4 of 5 models, consistent with KK 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 tt derived from it (Appendix A.8). Whether the retrieved features were an artifact of a particular draw of DD 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∣\sum_{k}|N_{k}^{L}|\cdot|S_{k}^{L}|. 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.

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 ϕ\phi 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.

Reviewer_4umdOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes a formal definition of a "mechanistic feature" as a block, meaning a set of neurons x a set of samples from a dataset, where every activation has magnitude at least a threshold t, under constraints of maximality and orthogonality.


It defines finding this as the K-Mechanistic Features problem (KMF) and proves it is NP-complete.


It gives two heuristics for the problem, a relaxed MINLP and L&B-search (local plus beam search), and evaluates them on VGG16 and ViT (CIFAR-10/100) and on an MLP head fine-tuned on top of Llama 3.2 1B (SST5).

Critical strengths

It's true that we really could use a formal definition of a "feature" in mech interp. I would be glad to see more work on this.


The formal problem is stated clearly.


They tested on both vision and language tasks, though on the language side the analysed layers belong to an MLP head added on top of Llama, not to Llama itself (why?).

Critical weaknesses

The paper stipulates a definition of a mechanistic feature, and presents this definition as though it faithfully captures what the field means by "feature"/what a "feature" is. I disagree with this for a few reasons:


  1. The paper itself calls the ideas from the literature "assumptions", and then suddenly changes them to "core MI principles". But they're not – linear representation, superposition etc are working hypotheses, which the paper's own motivation concedes are "hard to validate or refute". So at best we can say that they stipulate a definition that contains some hypotheses from the literature about what a feature is.


  2. I'm also confused why these particular ideas were chosen to include, because the literature cited to support them is pretty thin. Irreducibility rests on one review paper and is translated as maximality (no block contained in another), which I don't think is what irreducibility usually means in the MI literature. The linear representation assumption is attributed to a paper on the optimality of the Johnson-Lindenstrauss lemma, which only shows that many near-orthogonal vectors can exist. I don't think the neuron relevance threshold appears in any of the cited feature vis work, which uses activation strength to identify units to look at, not really as part of a definition of a feature.


  3. While I don't object to stipulated definitions in general, I struggle with the way it is presented here. All of the key contributions in the paper rely on this definition being the definition of a feature. And I just don't think it is. It seems to me like the NP-hardness of the task comes from the modelling choices and the sorta arbitrary definition of a feature, so I don't think there's any foundation for claims about "the complexity of understanding", it's just the complexity of the chosen problem.


The paper could be reframed as simply proposing a new interpretability technique, which would address the concerns above. But it doesn't seem like it works particularly well as an interp technique either, or at least the evaluation doesn't demonstrate that it does:


The internal metrics are just measuring the definition, they show that L&B-search approximates KMF but not whether the blocks are interpretable features. Naturally, baselines perform worse on an objective that they don't optimise for. That performance is then read as their "limits in finding actual MFs", where "actual MFs" just means whatever Definition 1 says.


On the metrics that aren't the methods own objective, L&B-search mostly doesn't beat the baselines. On the causal metrics it is often worst or near worst, and on the last layer PCA and SAE achieve higher purity. I don't think this supports a "superiority over a variety of baselines".


On the last layer, the entries are softmax probabilities and t is set so that roughly one entry per sample reaches the threshold, so recovering one block per class is essentially recovering the predicted class.


There's no null baseline (comparison against random blocks of matched size and threshold), there's no held-out evaluation, there's no real causal evaluation (zeroing a block's neurons and measuring the drop in the logit of the class those neurons contribute to most strongly through the output weights is not sufficient, the block was selected for high activation, so the drop is basically guaranteed).

The qualitative evidence only shows the sample most cosine-aligned with each feature, which is best case by construction – I would want to see randomly selected samples from each feature as well.

Questions for authors

The paper says that "the linear representation assumption (§3.1) implies that a feature is exhibited by multiple neurons and samples", so "it is desirable to identify the largest possible set of neurons and samples of any feature". This doesn't seem to follow. Why maximise |N|·|S|? Doesn't it just reward broad, generic blocks?


The paper cites superposition and linear representation but seems to define membership neuron by neuron – isn't this a contradiction? A feature spread weakly across many neurons, i.e. the textbook superposition case, seems unlikely to reach the threshold on any single neuron, doesn't this mean it can never form a block?
Does this method assume superposition or not?

Why was the method applied to an added MLP head rather than to Llama's own layers? Does it scale to, and work on, the model's internal activations?

1 comment
AuthorsOpenReview ↗

Authors Rebuttal Reviewer 2 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.

Experiments on Language model [R2S3], [R2Q3]. We probe an MLP head on Llama to keep the analyzed layer type consistent across models (§5, lines 357-359); the residual stream is future work. The method operates on any activation matrix and scales comparably, staying in the order of minutes up to 256x5000 across K (Table 2).

Concerns on Definition [R2W1]. We answer the first two points, since the third would repeat them.

  • The definition is grounded in the MI assumptions, taken to hold rather than established (line 183). This is standard mathematical practice, as with results proved under the assumption P ≠ NP. We formalize hypotheses recognized within the community (Bereska & Gavves, 2024; Elhage et al., 2022; Räuker et al., 2023; Somvanshi et al., 2026). We used “principle” for readability, but agree this may mislead, and have replaced it with “hypothesis” or “assumption”.
  • Irreducibility follows from features as fundamental units of representation (Olah et al., 2020; Elhage et al., 2022): SAE rests on exactly this, disentangling features into concepts that cannot be disentangled further (Huben et al., 2024). We translate it into Maximality (no block contained in another block). Quasi-orthogonality combines superposition and linear representation (lines 188-193); Larsen & Nelson (2017) is cited only for the Johnson-Lindenstrauss lemma (lines 84, 192); the assumption is attributed to Bereska & Gavves (2024) and Elhage et al. (2022) at line 81, now joined by Olah et al. (2020) and Bricken et al. (2023) at line 123. Neuron relevance is not taken from a single definition, but follows from the assumptions and feature visualization practice (Olah et al., 2017; 2020; Cammarata et al., 2020; Zeiler & Fergus, 2014), stated by us as a condition on the feature itself.

Evaluation scores and last layer experiments [R2W2], [R2W3], [R2W4]. The last layer is a sanity check (lines 361-363): features correspond to classes by construction, so any method should recover them, and baselines reaching similar results despite not optimizing our objective supports our claim. On second-last layer, L&B-search does not always achieve the best causal scores, but ranks 1st or 2nd most often (8 of 15 cases), in at least one causal score per scenario in 4 of 5 cases before the stability update in [R3W3, R3Q3], and in all 5 after it, supporting our method as the better performing one (updated lines 417-419). Finally, our definition captures the MI assumptions, so its objective is defined on them, and retrieved features are meaningful, as visualization analysis shows.

Null baseline, held-out evaluation and causal evaluation [R2W5]. A null baseline is intractable: drawing a random block matching size and Thresholding is an NP-complete MBP instance, and relaxing Thresholding makes the blocks inadmissible under Definition 1. On held-out evaluation, we are unsure what is meant: features come from a random probing set, and their absence elsewhere would not invalidate them. We have now added a stability analysis, as raised in [R3W3, R3Q3]. On causal evaluation, this is why we restrict it to the second-last layer: on the last layer neurons correspond to classes, guaranteeing the effect described, while on the second-last they do not, and the target class is derived following logic in literature (Geiger et al. (2022)), adapted in Appendix A.11. We also report the Gaussian score and Loss Recovered, so evaluation does not rest on ablation alone.

Random samples in feature visualization [R2W6]. Appendix A.14 now also reports, per feature, a sample drawn at random from SkS_k with the Grad-CAM of the block’s score on it.

Objective function [R2Q1]. Maximizing the size does not reward generic blocks, as it is not maximized in isolation. C1 stops growth over NkN_k and SkS_k where the feature is absent, C2 forbids containing another feature, and C3 requires pairwise ϵ\epsilon-orthogonal directions (§3.2, lines 225-228); a generic block would violate C1 or be ruled out by C2-C3. What is maximized is each block’s size, not the matrix coverage ([R3Q1]).

Superposition and thresholding [R2Q2]. No membership is defined: the direction is computed over all of R^l, with every neuron contributing to it, and the selected neurons are those relevant enough to the feature on its samples ([R3W1, R3Q2]). The definition holds regardless of t, a parameter whose poor choice can degrade results without making it inconsistent with superposition, which is assumed: nothing in Definition 1 bounds K by l, so more features than neurons can coexist in RlR^l.

Reviewer_SkdLOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies feature discovery in mechanistic interpretability by representing candidate features as blocks of a neural network's activation matrix and defining their directions through mean activations. It formalizes thresholding, non-containment, and approximate orthogonality requirements, then seeks K features maximizing cumulative block size. The authors give an NP-completeness argument for the decision problem, a conditional inapproximability result, a mixed-integer nonlinear formulation, and two heuristics. Experiments on five model-dataset combinations compare the methods with PCA, SAE, spectral co-clustering, and BDAS using structural, class-alignment, intervention, and reconstruction metrics, supplemented by visualizations. Results support competitive performance in these settings, rather than uniform superiority across metrics or a guarantee of human-understandable concepts.

Critical strengths

I find the text pleasant to read. The introduction makes the motivation and proposed framework accessible to me (Lines 033–051, 073–095).

Critical weaknesses
  • Beyond the mathematical properties, it remains unclear to me whether mechanistic features should align with human-understandable concepts, and how that requirement enters the framework. I also wonder how feature granularity relates to K: could different granularities yield maximal coverage at K = 1 or at a larger K? These questions matter to what the discovered features represent (Lines 076–090).
Questions for authors
  • Clarification: Should satisfying the formal definition imply alignment with a human-understandable concept, or is this a separate empirical property? How should the qualitative visualizations be interpreted in relation to that distinction (Lines 076–087, 1371–1374)?
  • Clarification: How does K relate to the intended granularity of features? Appendix A.4 acknowledges that selecting K remains unresolved; does the framework distinguish equally good coverage at different granularities, even when K is supplied (Lines 088–090, 200–207)?
  • Clarification: Regarding the claimed first formal definition, why have earlier approaches not provided such a definition? Is there a conceptual obstacle that this framework resolves (Lines 096–101, 129–133)?
1 comment
AuthorsOpenReview ↗

Authors Rebuttal Reviewer 1 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.

Alignment with human-understandable concepts [R1W1, R1Q1]. Alignment is a separate, empirical property, not implied by Definition 1: C1-C3 are necessary conditions derived from the MI assumptions (R1-R3), not sufficient for human-understandability. Building nameability into the definition would reintroduce the reliance on human judgment that motivates our work (lines 70-72). We have stated this explicitly in §3.1, lines 202-206. The qualitative visualizations should be read accordingly: a sanity check that the blocks are coherent, and an illustration of how the framework can be used to interpret them, not a validation of Definition 1. The syntheses are produced from the block’s mean neuron activations alone, without looking at its samples, so their agreement with the in-block exemplars is an independent check, and Grad-CAM then localizes the regions driving the block, which helps in the harder cases. Stated in §6, lines 477-481.

K and feature granularity [R1W1, R1Q2]. As added in §3.2 (lines 228-230), granularity is a property of the model (architecture, training procedure, layer) and of the data it is trained on, not of KK, which only determines how many features are retrieved. If KK matches the actual number of learned features, they are captured at their own granularity; if smaller, coverage is partial; if larger, the extra blocks can only be fragments or near-duplicates of existing ones. At a fixed KK, f alone does not separate two solutions of equal cumulative size at different granularities, since the coverage f expresses is per feature rather than over the set of features taken together (detailed in our answer to [R3Q1]); what breaks the tie is ϵ\epsilon-orthogonality, as fragments of the same feature have highly similar directions and are penalized. That the recovered granularity is the model’s own is visible in Fig. 2, where VGG16 and ViT, compared on the same dataset at KK = 10, converge on whole class objects and on finer boundary structure respectively. Determining the right KK remains an open problem, shared with the existing literature, which we leave to future work.

Absence of formal definition [R1Q3]. Mechanistic Interpretability is a recent field, built on assumptions that the literature states informally. Existing definitions are either colloquial rather than formal (Bereska & Gavves, 2024; Somvanshi et al., 2026) or too general to constrain what a feature is, as Causal Abstraction’s own dependence on the method it is instantiated on illustrates (we updated §2 accordingly, lines 132-134). In our opinion, this is due both to the youth of the field, where research lines have only recently been systematized, and to the intrinsic difficulty of stating R1-R3 together, which are requirements of different kinds: R1 constrains activation values, R2 is a containment relation, R3 a geometric condition on directions in RlR^l. A direction alone gives R1 and R2 nothing to act on; a set of neurons and samples gives R3 no direction. The definition resolves this, carrying the footprint for C1-C2 and inducing ϕ\phi(F) for C3. A further contribution is showing this faithfulness has a cost: proving KMF NP-complete and hard to approximate (Theorem 1, Corollary 1) places the difficulty in the notion itself, which any method adhering to R1-R3 inherits. We also added lines 84-87 in §1.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.