The Computational Complexity of Circuit Discovery for Inner Interpretability
Authors: Federico Adolfi
Martina G. Vilas
Todd Wareham
Venue: ICLR 2025 Spotlight (2025)
Keywords: inner interpretability
mechanistic interpretability
circuit discovery
computational complexity
parameterized complexity
Primary area: interpretability and explainable AI
TL;DR: Parameterized complexity of circuit queries explains interpretability outcomes and viable algorithmic options for circuit discovery.

Abstract: Many proposed applications of neural networks in machine learning, cognitive/brain science, and society hinge on the feasibility of inner interpretability via circuit discovery. This calls for empirical and theoretical explorations of viable algorithmic options. Despite advances in the design and testing of heuristics, there are concerns about their scalability and faithfulness at a time when we lack understanding of the complexity properties of the problems they are deployed to solve. To address this, we study circuit discovery with classical and parameterized computational complexity theory: (1) we describe a conceptual scaffolding to reason about circuit finding queries in terms of affordances for description, explanation, prediction and control; (2) we formalize a comprehensive set of queries for mechanistic explanation, and propose a formal framework for their analysis; (3) we use it to settle the complexity of many query variants and relaxations of practical interest on multi-layer perceptrons. Our findings reveal a challenging complexity landscape. Many queries are intractable, remain fixed-parameter intractable relative to model/circuit features, and inapproximable under additive, multiplicative, and probabilistic approximation schemes. To navigate this landscape, we prove there exist transformations to tackle some of these hard problems with better-understood heuristics, and prove the tractability or fixed-parameter tractability of more modest queries which retain useful affordances. This framework allows us to understand the scope and limits of interpretability queries, explore viable options, and compare their resource demands on existing and future architectures.

Published as a conference paper at ICLR 2025
THE COMPUTATIONAL COMPLEXITY OF CIRCUIT DISCOVERY FOR INNER LNTERPRETABILITY
Federico Adolfi
Martina G. Vilas
ESI Neuroscience, Max-Planck Society
Department of Computer Science
& University of Bristol fede. ado.f @bristol.aaaee
Goethe University Frankfurt mart ingiiiaiiiii asê -tw.eeemmmaannnaaaeeeema frankfurt.de
Todd Wareham
Department of Computer Science Memorial University of Newfoundland ha mooldmuun... ca
ABSTRACT
Many proposed applications of neural networks in machine learning, cogni- tive/brain science, and society hinge on the feasibility of inner interpretability via circuit discovery. This calls for empirical and theoretical explorations of viable al- gorithmic options. Despite advances the design and testing of heuristics, there are concerns about their scalability and faithfulness at time when we lack under- standing of the complexity properties of the problems they are deployed to solve. To address this, study circuit discovery with classical and parameterized com- putational complexity theory: (1) we describe a conceptual scaffolding to reason about circuit finding queries in terms of affordances for description, explanation, prediction and control; (2) we formalize a comprehensive set of queries for mech- anistic explanation, and propose formal framework for their analysis; (3) we use it to settle the complexity of many query variants and relaxations of practical in- terest on multi-layer perceptrons. Our findings reveal challenging complexity landscape. Many queries are intractable, remain fixed fixed-paranee parameter intractable rela- tive to model/circuit features, and inapproximable under additive, multiplicative. and probabilistic approximation schemes. To navigate this landscape, we prove there exist transformations to tackle some of these hard problems with better- understood heuristics, and prove the tractability or fixed-parameter tractability of more modest queries which retain useful affordances. This framework allows us to understand the scope and limits of interpretability queries, explore viable options, and compare their resource demands on existing and future architectures.
INTRODUCTION
As artificial neural networks (ANNs) grow in size and capabilities, Inner Interpretabiliit emerging field tasked with explaining their inner workings (Räuker et al., 2023; Vilas et al., 2024a) attempts devise scalable, automated procedures to understand systems mechanistically. Many proposed applications of neural networks in machine learning, cognitive and brain sciences, and society, hinge on the feasibility of inner interpretability. For instance, we might have rely on interpretability methods to improve system safety (Bereska & Gavves, 2024), detect and control vulnerabilities Ctarefa-Carrased use task subnetworks (Zhang et al., 2024), explain internal concepts underlying decisions (Lee et al., 2023), experiment with neuro-cognitive models of language, vision, etc. (Lindsay, 2024; Lindsay & Bau, 2023; Pavlick, 2023), describe determinants of ANN-brain alignment (Feghhi et al., 2024; Oota et al., 2023), improve architectures, and extract domain insights (Räuker et al., 2023). We will have to solve different instances of these interpretabilitty problems, ideally automatically, for increasingly large models. We therefore need efficient interpretability procedures, and this requires empirical and theoretical explorations of viable algorithmic options.
al., 2024), prune for efficiency (Hooker et al., 2021), find and

---

Published as a conference paper at ICLR 2025
Circuit discovery and its challenges. Since top-down approaches to inner interpretability (see Vilas et al., 2024a) work their way down from high-level concepts or algorithmic hypotheses (Lieberum et al., 2023), there is interest in complementary bottom-up methodology: circuit discovery (see Shi et al., 2024; Tigges et al., 2024). It starts from neuron- and circuit-level isolation or description (e.g., Hoang-Xuse -uan et al., 2024; Lepori et al., 2023) and attempts to build up higher-Ievel abstrac- tions. The motivation is the circuit hypothesis: models might implement their capabilitiies via small subnetworks (Shi et al., 2024). Advances in the design and testing of interpretability heuristics (see Shi et al., 2024; Tigges et al., 2024) come alongside interest in the automation of circuit discovery (e.g., Conmy et al., 2023; Ferrando & Voita, 2024; Syed et al., 2023) and concerns about its feasibil- ity (Voss et al., 2021: Räuker et al., 2023). One challenge is scaling up methods to larger networks, more naturalistic datasets, and more complex tasks (e.g., Lieberum et al., 2023; Marks et al., 2024), given their manual-intensive search over large spaces (Voss et al., 2021). A related issue is that current heuristics, though sometimes promising (c.g., Merullo et al., 2024), often yield discrepant results (see e.g., Shi et al., 2024; Niu et al., 2023; Zhang & Nanda, 2023). They often find circuits that are not functionally faithful (Yu et al., 2024a) or lack the expected affordances (e.g., effects on behavior; Shi et al., 2024). This questions whether certain localization methods yield results that inform editing (Hase et al., 2023), and vice versa (Wang & Veitch, 2024). More broadly, we run into 'interpretability illusions' (Friedman al., 2024) when our simplifications (e.g., circuits) mimic the local input-output behavior of the system but lack fairhfulees (Jacovi & Goldberg, 2020).
Exploring viable algorithmic options. These challenges come at a time when, despite emerging theoretical frameworks (c.g.. Vilas et al., 2024a; Geiger et al., 2024), there are notable gaps in the formalization and analysis of the computational problems that interpretability heuristics attempt to solve (see Wang & Veitch, 2024, $8). Issues around scalability of circuit discovery and faithfulness have a natural formulation in the language of Computational Complexity Theory (Arora & Barak, 2009; Downey & Fellows, 2013). A fundamental source of breakdown of scalability which lack of faithfulness is one manifestation of- is the intrinsic resource demands of interpretability prob- lems. In order to design efficient and effective solutions, we need to understand the complexity properties of circuit discovery queries and the constraints that might be leveraged to yield the de- sired results. Although experimental efforts have made promising inroads, the complexity-theoreee properties that naturally impact scalability and faithfulness remain open questions (see e.g., Suber- caseaux, 2020, $6C). We settle them here by complementing these efforts with systematic study of the computational complexity of circuit discovery for inner interpretability. We present a frame- work that allows us to (a) understand the scope and limits of interpretability queries for descrip- tion/explanation and predictiom/control, (b) explore viable options, and (c) compare their resource demands among existing and future architectures.
1.1 CONTRIBUTIONS
We present a conceptual scaffolding to reason about circuit finding queries in terms of affordances for description, explanation, prediction and control.
We formalize a comprehensive set of queries that capture mechanistic explanation, and propose a formal framework for their analysis.
We use this framework to settle the complexity of many query variants, parameterizations, approximation schemes and relaxations of practical interest on multi-layer perceptrons, relevant to various architectures such as transformers.
We demonstrate how our proof techniques can also be useful to draw links between inter- pretability and explainability by using them to improve existing results on the latter.
1.2
OVERVIEW OF RESULTS
We uncover a challenging complexity landscape (see Table 4) where many queries are intractable (NP-hard, E.5-hard), remain fixed-parameter intractable (W[1]-hard) when con- straining model/cireuit features (c.g., depth), and are inapproximable under additive, mul- tiplicative, and probabilistic approximation schemes.
We prove there exist transformations to potentially tackle some hard problems (NP- vs. 21-- complete) with untter-undd heuristics, and prove the tractability (PTIME) or fixed- parameter tractability (FPT) of other queries of interest, and we identify open problems. We describe a quasi-minimality property of ANN circuits and exploit it to generate tractable queries which retain useful affordances as well as efficient algorithms to compute them. We establish a separation between local and global query complexity. Together with quasi- minimality, this explains interpretability illusions of faithfulness observed in experiments.
2

---

Published as a conference paper at ICLR 2025
1.3 RELATED WORK
This paper gives the first systematic exploration of the computational complexity of inner inter- pretability problems.' An adjacent area is the complexity analysis of explainability problems (Bas- san & Katz, 2023; Ordyniak et al., 2023). It differs from our work in its focus on input queries -sspetts of the input that explain model decisions networks via circuit queries. Barceló et al. (2020) study the
look at the inner workings of neural explainabiii explainability of multi-layer percep- trons compared to simpler models through a set of input queries. Bassan al. (2024) extend this idea with a comparison between local and global explainability. None of these works formalize or analyze circuit queries (although Subercaseaux, 2020, identifies it as an open problem); we adapt the local versus global distinction in our framework and show how our proof techniques can tighten some results on explainability queries. Ramaswamy (2019) and Adolf & van Rooij (2023) explore a small set of circuit queries and only on abstract biological networks modeled as general graphs, which cannot inform eircuit discovery in ANNs. Efforts in characterizing the complexity of learning neural networks (e.g.. Song et al., 2017; Chen et al., 2020; Livni et al., 2014) might eventually con- nect to our work, although a number of differences between the formalizations makes results in one area difficult to predict from those in the other. Likewise, efforts to settle the complexity of finding small circuits consistent with a truth table (Hitchcock & Pavan, 2015) are currently too general to be applicable to interpretability problems. More generally, we join efforts build a solid theoretical foundation for interpretability (Bassan & Katz, 2023; Geiger et al., 2024; Vilas et al., 2024a).
2 MECHANISTIC UNDERSTANDING OF NEURAL NETWORKS
Mechanistic understanding is a contentious topic (Ross & Bassett, 2024), but for our purposes it will suffice to adopt pragmatic perspective. In many cases of practical interest, we want our inter- pretability methods to output objects that allow us to, in some limited sense, (I) describe or explain succinctly, and (2) control or predict precisely. Such objects (e.g.. circuits) should be 'efficiently queriable"; they are often referred to as "a way of making an explanation tractable" (Cao & Yamins, 2023). Roughly, this means that we would like short descriptions (e.g., small circuits) with use- ful affordances (e.g., to readily answer questions and perform interventions of interest). Circuits have the potential fulfill these criteria (Olah et al., 2020). Here we preview some special circuits with useful properties which we formalize and analyze later on. Table I maps the main circuits we study to their corresponding affordances for description, explanation, prediction and control. Formal definitions of circuit queries given alongside results in Section 4 (see also Appendix).
Table 1: Circuit affordances for description, explanation, prediction, and control.
Affordance
Circuit
Description / Explanation
Prediction / Control
Sufficient Circuit
Which neurons suffice in isolation to cause
Inference in isolation. Minimal: ablating any neuron breaks bchavior of the circuit.
a behavior? Minimum: shortest description.
Quasi-minimal
Which neurons suffice in isolation to cause behavior and which is breaking point?
Ablating the breaking point breaks behavior of the circuit.
Sufficient Circuit
Necessary Circuit
Which neurons are part of all circuits for a behavior? Key subcomputations?
Ablating the neurons breaks behavior of any sufficient circuit in the network.
Circuit Ablation &
Which neurons are necessary in the current configuration of the network?
Ablating/Clamping the neurons breaks
Clamping
behavior of the network.
Circuit Robustness
How much redundancy supports a behavior? Resilience to perturbations. Which neurons drive a hehavior in given input context, i.e., are control nodes?
Ablating any set of neurons of size below
threshold does not break behavior.
Patched Circuit
Patching neurons changes network behavior for inputs of interest. Steering: Editing.
Quasi-minimal Patched Circuit
Which neurons can drive behavior in given input context and which neuron is
Patching neurons causes target behavior for
inputs of interest; Unpatching breaking
breaking point?
point breaks target hehavior.
Gnostic Neurons
Which neurons respond preferentially to certain concept?
Concept editing; guided synthesis.
TThis work expands on FA's PhD dissertation University of Bristol (Adolfi, 2023; Adolfi et al., 2024).
3

---

Published as a conference paper at ICLR 2025
3 INNER INTERPRETABILITY QUERIES AS COMPUTATIONAL PROBLEMS
We model post-hoc interpretability queries neural networks computational problems in order to analyze their intrinsic complexity properties. These circuit queries also formalize criteria for desired circuits, including those appearing in the literature, such as 'faithfulness', 'completeness', and 'minimality' (Wang et al., 2022; Yu et al., 2024a).
Query variants: coverage, size and minimality. The coverage of circuit is the domain over which it behaves in a certain way (e.g., faithful to the model's prediction). Local circuits do so over all possible inputs. The size of circuit is
finite set of known inputs and global circuits do the number of neurons. Some circuit queries require circuits of bounded size whereas others leave the size unbounded. A circuit with certain property (e.g., local sufficiency) minimal if there is no subset of its neurons that also has that property (cf. minimum size among all such circuits present in the network; see Figure 1).
Trivial SC O O U O Non-minimal SC + U
Minimal SC
Minimum/man /mal SC
NC
Quasi-minimal
U
Figure 1: Relationships between circuit types. Sufficient Circuits (SCs) are faithful to the model. The entire network is trivial SC. Necessary Circuits (NCs) units shared by all minimal SCs. Quasi-minimal SCs contain known breaking point (here, NC) and unknown superfluous units.
To fit our comprehensive suite of problems, we explain how to generate problem variants and later on only present one representative definition of each.
Problem 0. PRObLEMNAme (PN)
Input: A multi-layer perceptron M, Coverage N, SizeIN.
Output: A Property circuit C of M, SizOUT, CoverageOUT C(x)= Suffix.
Problem O and Table 2 illustrate how to generate problem variants using a template, and ProblemName SUFFICIENT CIRCUIT as an example (c.g., the Coverage [ [IN/OUT] variables specify parts of the input/output description that vary according to whether the requested circuit must have global or local faithfulness). Problem definitions will be given for search (return spec- ified circuits) or decision (answer yes/no circuit queries) versions. Others, including optimization (return maximum/mininum- sented later on are obtained similarly. We also explore various parameterizations, approximation schemes, and relaxations that we explain in the following sections as needed.
circuits), can be generated by assigning variables. Problems pre-
Table 2: Generating query variants from problem templates.
Query variants
Description variables
Local
Global
Bounded
Unbounded
Optimal
Bounded
Unbounded
Optimal
IoverageIN
input
input
input x
CoverageOUT
Vx
Vx
Vx
SizeIN
int. u S M
int. u < M
SizeOUT
size |C| S
min. size
size |C| S u
min, size
Property
minimal /" ""_
minimal
minimal ""
minimal
Suffix
if it exists, otherwise
if exists,
otherwise
4

---

Published as a conference paper at ICLR 2025
3.1 COMPLEXITY ANALYSES
Classical and parameterized complexity. We prove theorems about interpretability queries build- ing on techniques from classical (Garey & Johnson, 1979) and parameterized complexity (Downey & Fellows, 2013). Given our limited knowledge of the problem space of interpretability, worst-case analysis is appropriate to explore which problems might be solvable without requiring any addi- tional assumptions (e.g., Bassan et al., 2024; Barceló et al., 2020), and experimental results suggest it captures lower bound on real-world complexity (e.g.. Friedman et al., 2024; Shi et al., 2024; Yu et al., 2024a). Here we give a brief, informal overview of the main concepts underlying our analyses (see Appendix for extensive formal definitions). We will explore beyond classical polynomial-time tractability (PTIME) by studying fixed-pann perammeeee tractability (FPT), a more novel and finer- sneerggained look at the sources of complexity of problems to test aspects that possibly make interpretability feasible in practice. NP-hard queries are considered intractable because they cannot be computed by polynomial-tina algorithms. A relaxation is to allow unreasonable (e-g., exponential) resource demands to be confined to problem parameters that can be kept small in practice. Parameterizing given ANN and requested circuit leads to parameterized problems (see Table 3 for problem pa- rameters we study later). Parameterized queries in the class FPT admit fixed-parameter tractable algorithms. W-hard queries (by analogy: to FPT as NP-hard to PTIME), however, do not. We study counting problems via analogous classes #P and #W[1]. We also investigate completeness for NP and classes higher up the polynomial hierarchy such as Σg and TH to identify aspects of hard problems that make them even harder, and to explore the possibility to tackle hard interpretability problems with better-understood methods for well-known NP-complete problems (de Haan & Szei- der, 2017). Most proof's involve reductions between computational problems which establish the complexity status of interpretability queries based on the known complexity of canonical problems in other areas.
Table 3: Model and circuit parameterizations.
Parameter
Model (given)
Circuit (requested)
Number of layers (depth)
L
i
Maximum layer width
L
tw
Total number of units?
Ú = [M| S i.
Pew
|C|
Number of input units
U₁
/,
Number of output units
Üo
ûo
Maximum weight
W
Maximum bias
B
b
Approximation. Although sometimes computing optimal solutions is intractable, it is conceivable we could devise tractable interpretability procedures to obtain approximate solutions that are useful in practice. We consider 5 notions of approximation: additive, multiplicative, and three probabilis- tie schemes (AA = {c, PTAS, 3PA}; see Appendix for formal definitions). Additive approximation algorithms return solutions most fixed distance away from optimal (c.g., from the minimum- sized circuit), ensuring that errors cannot get impractically large (c-approiimabilit)) Multiplicatiie approximation returns solutions at most factor of optimal away. Some hard problems allow for polynomial-time multiplicative approximation schemes (PTAS) where we can get arbitrarily close to optimal solutions as long we expend increasing compute time (Ausiello et al., 1999). Finally, we consider three types of probabilistic polynomial-time approximability (henceforth 3PA) that may be acceptable in situations where always getting the correct output for an input is not required: al- gorithms that (1) always run in polynomial time and produce the correct output for a given input in all but small number of cases (Hemaspaandra & Williams, 2012); (2) always run polynomial time and produce the correct output for a given input with high probability (Motwani & Raghavan, 1995); and (3) run in polynomial time with high probability but are always correct (Gill, 1977).
Model architecture. The Multi-Layer Perceptron (MLP) is a natural first step in our exploration because (a) it is proving useful as a stepping stone in current experimental (e.g., Lampinen et al., 2024) and theoretical work (e.g., Rossem & Saxe, 2024; McInerney & Burke, 2023); (b) it exists as a leading standalone architecture (Yu et al., 2024b), as the central element of all-MLP architectures (Tolstikhin et al., 2021), and as key component of state-of-the-art models such transformers (Vaswani et al., 2017); (c) it is of active interest to the interpretability community (c.g., Geva et al., 2022; 2021; Dai et al., 2022; Meng et al., 2024; 2022; Niu et al., 2023; Vilas et al., 2024b; Hanna
5

---

Published as a conference paper at ICLR 2025
et al., 2023); and (d) relate our findings in inner interpretabiliiyy to those in explainability, which also begins with MLPs (c.g.. Barceló et al., 2020; Bassan et al., 2024). Although MLP blocks can be taken units to simplify search, it is recommended to investigate MLPs by treating each neuron as a unit (e.g., Gurnee et al., 2023; Cammarata et al., 2020; Olah et al., 2017), as it better reflects the semantics of computations in ANNs (Lieberum al., 2023, sec. 2.3.1). We adopt this perspective in our analyses. We write M for an MLP model and M(x) for its output on input vector x. Its size | the number of neurons. A circuit C is a subset of |C| neurons which induce a (possibly end-to-end) subgraph of M (see Appendix for formal definitions).
4 RESULTS & DISCUSSION: THE COMPLEXITY OF CIRCUIT QUERIES
In this section we present each circuit query with its computational problem and a discussion of the complexity profile we obtain across variants, relaxations, and parameterizations. For an overview of the results for all queries, see Table 4. Proofs of the theorems can be found in the Appendix.
4.1 SUFFICIETT CIRCUIT
Sufficient circuits (SCs) are sets of neurons connected end-to-end that suffice, in isolation, to produce some model behavior over an input domain (see faithfulness; Wang et al., 2022; Yu et al., 2024a). They are conceptually related to the desired outcome of zero-ablating components that do not contribute to the behavior of interest (small, parameter-efficient subnetworks). Zero-ablation as method (e.g., to find sufficient circuits) has been criticized on the grounds that the patched value (zero) is somewhat arbitrary and therefore can mischaracterize the functioning of the neuron/cireuit when operating in the context of the rest of the network during inference. This gives rise alterna- tive methods such as activation patching with activation means or specific input activations, which we study later. SCs remain relevant as, despite valid eriticisms of zero-ablation (e.g., Conmy et al., 2023), circuit discovery through pruning might be justified at least in some cases (Yu et al., 2024a).
Problem 1. BOUNDED LOCAL SUFFICIENT CIRCUIT (BLSC)
Input: A multi-layer perceptron M, an input vector x, and an integer u S [M]
Output: A circuit C in M of size [C] < u, such that ((x) = M(x), if it exists, otherwise P.
We find that many variants of SC are NP-hard (see Table 4). Counterintuitively. this intractability does not depend straightforwardly on parameters such as network depth (W[]]-hard relative to P). Therefore, hardness is not mitigated by keeping models shallow. Given this barrier, we explore the possibility of obtaining approximate solutions but find that hard SC variants are inapproximable relative to all schemes in Section 3.1. An alternative is to consider the membership of these problems in well-studied class whose solvers are better understood than interpretability heuristics (de Haan & Szeider, 2017). We prove that local versions of SC are NP-complete. This implies there exist efficient transformations from instances of SC to those of the satisfiability problem (SAT; Biere et al., 2021), opening up the possibility to borrow techniques that work reasonably well in practice for SAT that might be suitable for some versions of neural network problems. Interestingly, this is not possible for the global version, which we prove is complete for a class higher up the complexity hierarchy (E. complete). This result establishes formal separation between local and global query complexity that partly explains 'interpretability illusions' (Friedman et al., 2024; Yu et al., 2024a), which we conjecture holds for other queries we investigate later. These illusions come about when an interpretability abstraction (e.g., circuit) seems empirically faithful to its target (c.g., model behavior) by some criterion (c.g., 'local' tests on a dataset), but actually lacks faithfulness the way it generalizes to other criteria (e.g., tests of its 'global' behavior outside the original distribution).
Next we explore whether we could diagnose if SCs with some desired property (e.g., minimality) are abundant, which would be informative of the ability of heuristic search to stumble upon one of them. We analyze various queries where the output is a count of SCs (i.e., counting problems). We find that both local and global, bounded and unbounded variants are #P-complete and remain intractable [W[[]-hard] when parameterized by many network features including depth (Table 3).
The hardness profile of SC over all these variants calls for exploring more substantial relaxations. We introduce the notion of quasi-minimality for this purpose (similar to Ramaswamy, 2019) and later demonstrate its usefuiness beyond this particular problem. Any neuron in a minimal/minimum SC is a breaking point in the sense that removing it will break the target behavior. In are merely guaranteed to know at least one neuron that causes this breakdown. By introducing this relaxation, which gives up some affordances but retains others of interest, we get a feasible interpretability query.
SCs

---

Published as a conference paper at ICLR 2025
Problem 2. UNBOUNDED QUASI-MINIMAL LOCAL SUFFICIENT CIRCUIT (UQLSC)
Input: A multi-layer perceptron M, and an input vector x.
Output: A circuit C in M and neuron E C s.t. C(x) (x) and (C) {e}](x) + M(x).
UQLSC is in PTIME. We describe an efficient algorithm to compute which can be heuristically biased towards finding smaller circuits and combined with techniques that exploit weights and gra- dients (see Appendix).
4.2 GNOSTIC NEURON
Gnostic neurons, sometimes called 'grandmother neurons' in neuroscience (Gale et al., 2020) and "concept neurons' or "object detectors' in AI (e.g., Bau et al., 2020), are one of the oldest and still current interpretability queries of interest (see also 'knowledge neurons'; Niu et al., 2023).
Problem 3. BOUNDED GNOSTIC NEURONS (BGN)
Input: A mulli-layyer perceptron M and two sets of input vectors X' and V an integer k and an activation threshold t.
Output: A set of neurons V in M of size [V] 2 such that Veey it is the case that VxEx' M(x) produces activations A% 2 t and Vyey Ai < t, if it exists, else 1. BGN in PTIME. Alternatives might require GNs to have some behavioral effect when intervened; such variants would remain tractable.
4.3 CIRCUIT ABLATION AND CLAMPING
The idea that some neurons perform key suhcomputations for certain tasks naturally leads to the hypothesis that ablating them should have downstream effects on the corresponding model behav- iors. Searching for neuron sets with this property has been strategy (i.c., zero-ablation) to get at important circuits (Wang& & Veitch, 2024). The circuit ablation (CA) problem formalizes this idea.
Problem 4. BOUNDED LOCAL CIRCUIT ABLATION (BLCA)
Imput: A multi-layer perceptron M, an input vector x, and an integer u & [M].
Output: A neuron set C in M of size |C] S u, s.t. [M \ C](x) # M(x), if exists, else 1.
A difference between CAs and minimal SCs is that the former can be interpreted as possibly non- minimal breaking set in the context of the whole network whereas the latter is by default a minimal breaking set when the SC is taken in isolation. In this sense, CA can be seen as less stringent criterion for circuit affordances. A related idea circuit clamping (CC): fixing the activations of certain neurons to a level that produces a change in the behavior of interest.
Problem 5. BOUNDED LOCAL CIRCUIT CLAMPING (BLCC)
Input: A multi-layer perceptron M, vector x, value r, and an integer u s.t. < u S I.]. Output: A subset of neurons C in M of size |C] < u, such that for the M induced by clamping all E C to value r, .M (x) # M(x), if it exists, otherwise 1.
Despite these more modest criteria, we find that both the local and global variants of CA and CC NP-hard, fixed-parameter intractable W[1]-hard relative to various parameters, and inapprox- imable in all 5 senses studied. However, we prove these problems are NP-complete, which opens up practical options not available for other problems we study (see remarks in Section 4.1).
4.4 CIRCUIT PATCHING
A critique of zero-ablation is the arbitrariness of the value, leading to alternatives such as mean- ablation (e.g., Wang et al., 2022). This contrasts studying circuits in isolation versus embedded in surrounding subnetworks. Activation patching (Ghandeharioun et al., 2024; Zhang & Nanda, 2023; Hanna et al., 2024) and path patching (Goldowsky-Dii) al., 2023) try pinpoint which activations play an in-context role in model behavior, which inspires the circuit patching (CP) problem.
Problem 6. BOUNDED LOCAL CIRCUIT PATCHING (BLCP)
Input: A multi-layer perceptron M, an integer k, an input vector y, and a vector set X. Output: subset C in M of size |C] S k, such that for the M induced by patching with activations from M(y) and M \ C with activations from M(x). M M(y) for all E X. if exists, otherwise 1.
We find that local/global variants are intractable (NP-hard) in way that does not depend pa- rameters such as network depth or size of the patched circuit (W[1] and are inapproximable (fc, PTAS, 3PA --na-inaprroxx). Although we also prove the local variant of CP is NP-complete and
7

---

Published as a conference paper at ICLR 2025
therefore approachable in practice with solvers for hard problems not available for the global vari- ants (see remarks in Section 4.1), these complexity barriers motivate exploring further relaxations.
With some modifications the idea of quasi-minimality can be repurposed to do useful work here.
Problem 7. UNBOUNDED QUASI-MINIMAL LOCAL CIRCUIT PATCHING (UQLCP)
Input: A multi-layer perceptron M, an input vector and a set X' of input vectors.
Output: A subset C in M and neuron C, such that for the MM" induced by patching C with activations from M(y) and M \ with activations from MM),, VXEx -MM(x) = M(y), and for M' induced by patching identically except for E Exex MM'xx) o _M(y).
In this way obtain a tractable query (PTIME) for quasi-minimal patching, sidestepping barriers while retaining some useful affordances (see Table 1). We present an algorithm to compute UQLCP efficiently that can be combined with strategies exploiting weights and gradients (see Appendix).
Table 4: Classical and parameterized complexity results by problem variant.
Classical & parameterized queries'
Problem variants
P PM U Pc PM {I. U1, Uo, W, B} Pc (i,b,, ú, ür, to, úz b}
Local
Global
Decision/Search
Optimization
Deciston/Search
Optimization
SUFFICIENT CIRCUIT (SC)
NP-complete
A-inapprox.
Edp 22p-compecte
A-inapprox.
P-SC
W[1]-hard
A-inapprox.
W[1]-hard
A A-inapprox.
Minimal SC
NP-complete
?
Mg NP-hard
P-Minimal SC
W[1]-hard
?
W[1]-hard
Unbounded Minimal SC
?
N
N
P-Unbounded Minimal SC
?
A
A
Unbounded Quasi-Minimal SC
PTIME
?
Count SC
#P-complete
#P-hard
P-Count SC
#Wald-
#W[l]-hard
N
Count Minimal SC
#P-complete
#P-hard
A
A
P-Count Minimal SC
--had
#W[1]-hard
Count Unbounded Minimal SC
#P-complete
#P-hard
GNOSTIC NEURON (GN)
PTIME
N/A
?
N/A
CIRCUIT ABLATION (CA)
NP-complete
A-inapprox.
E Σn NP-hard
A- A-inapprox.
[t. Ü, Uo, W, B, úJ-CA
W[1]-hard
A-inapprox.
W[1]-hard
A-inapprox.
CIRCUIT CLAMPING (CC)
NP-complete
A-inapprox.
Σ NP-hard
A-inapprox.
(i, W, B, ac-cc
Wil]-hard
inapproxx
W[I]-hard
A A-inapprox.
CIRCUIT PATCHING (CP)
NP-complete
A i-inapprox.
E 23 NP-hard
A A-inapprox.
{L. U., W. B, aj-CP
W[2]-hard
A-inapprox.
W[2]-hard
A-inapprox.
Unbounded Miniiml CP
PTIME
N/A
?
N/A
NECESSARY CIRCUIT (NC) [I. Uo W, aJ-NC
2> NNP-hard
A 4-inapprox. A-inapprox.
E 23 NP-hard
A i-aappoox.
W[1]-hard
W[1]-hard
A-inapprox.
CIRCUIT ROBUSTNESS (CR)
coNP-complete coal
?
11 coNP-hard
(L.Ū,,0o W, W.B, &.&
? FPT
coW[1]-hard
[|RR))-
FPT
?
(H) -Z)
FPT
FPT
FPT
FPT
SUFFICIENT REASONS (SR) (L, Uo W. B. aj-SR -R
ΣΤ NP-hard 3PA-inapprox.
N
Whl]-hard
3PA-inapprox.
CCicuuts are bounded- sonnded-size unless otherwise stated. Each cell contains the complexity of the problem variant in terms of classical and FP (in)tractabilit, membership in complexity classes, and (in)approximabiltty (A {c, PTAS, 3PA)). '?' marks potentially fruitful open prohlems. 'N/A' stands for applicable.
8

---

Published as a conference paper at ICLR 2025
4.5 NECESSARY CIRCUIT
The criterion of necessity is stringent one, and consequently necessary circuits (NCs) carry power- ful affordances (see Table 1). Since neurons in NCs collectively interact with all possible sufficient eircuits for a target behavior, they are candidates describe key task subcomputations and interven- ing on them is guaranteed to have effects even in the presence of high redundance. This relates to the notion of circuit overlap and therefore to efforts in identifying circuits shared by various tasks (e.g., Merullo et al., 2024), and the link between overlap and faithfulness (c.g., Hanna et al., 2024).
Problem 8. BOUNDED GLOBAL NECESSARY CIRCUIT (BGNC)
Input: A multi-layer perceptron M, and an integer k.
Output: A subset S of neurons M of size |S| I k, such that SnC of 0 for every circuit C in M that is sufficient relative all possible input vectors, if it exists, otherwise I..
Unfortunately both local and global versions of NC are NP-hard (in E3 Table 4), remain intractable even when keeping parameters such network depth, number of input and output neurons, and others small (Table 3), and does not admit any of the available approximation schemes (Section 3.1). Tractable versions of NC are unlikely unless substantial restrictions or relaxations are introduced.
4.6 CIRCUIT ROBUSTNESS
A behavior of interest might be over-determined or resilient in the sense that many circuits in the model implement it and one take when the other breaks down. This is related to the notion of redundancy used in neuroscience (e.g.. Nanda et al., 2023). Intuitively, when a model implements task in this way, the behavior should be more robust number of perturbations. The possibility of verifying this property experimentally motivates the circuit robustness (CR) problem, and a related interpretability effort diagnosing nodes that are excluded by circuit discovery procedures but still have an impact on behavior (false negatives; Kramár et al., 2024).
Problem 9. BOUNDED LOCAL CIRCUIT ROBUSTNESS (BLCR)
Input: A multi-layer perceptron M, a subset H of M, an input vector x, and an integer k with 1 < le < [
Output: <YES> if for each H' C H. with |I < k. M(x) [M H')(),, else <NO>.
We find that Local CR is coNP-complete while Global CR is in Hy and coNP-hard. It remains fixed-paramen parameter intractable (coW([]-hard) relative model parameters (Table 3). Pushing further, we explore parameterizing CR by [[ and prove fixed-panc seed-parameter tractability of { )-CR which holds both for the local and global versions. There exist algorithms for CR that scale well as long as | is reasonable; a scenario that might be useful to probe robustness in practice. This wraps up our results for circuit queries. We briefly digress into explainability before discussing some implications.
4.7 SUFFICIETT REASONS
Understanding the sufficient reasons (SR) for model decision in terms of input features consists of knowledge of values of the input components that are enough to determine the output. Given model decision on an input, the most interesting reasons are those with the least components.
Problem 10. BOUNDED LOCAL SUFFICIENT REASONS (BLSR)
Input: A multi-layer perceptron M, input vector of length |x|
ûr and an integer At
with < k < 0j.
Output: A subset x" of x of size xx| = k. such that for every possible completion x" of x" M(x*) = Mx). if exists, otherwise 1.
To demonstrate the usefulness of our framework beyond inner interpretability, we show how it links to explainability. Using our techniques for circuit queries, we significantly tighten existing results for SR (Barceló et al., 2020; Wäldchen et al., 2021) by proving that hardness (NP-hard, W[1]-hard, 3PA-inapprox.) holds even when the model has only one hidden layer.
IMPLICATIONS, LIMITATIONS, AND FUTURE DIRECTIONS
We presented framework based parameterized complexity to accompany experiments inner interpretability with theoretical explorations of viable algorithms. With this grasp of circuit query complexity, we can understand the challenges of scalability and the mixed outcomes of experiments with heuristics for circuit discovery. There is ample complexity theorreic evidence that there is a limit (often underestimated) to how good the performance of heuristics on intractable problems can

---

Published as a conference paper at ICLR 2025
be (Hemaspaandra & Williams, 2012). We can explain 'interpretability illusions' (Friedman et al., 2024) due to lack of faithfulness, minimality (e.g., Shi et al., 2024; Yu et al., 2024a) and other affor- dances (Wang& & Veitch, 2024; Hase et al., 2023), in terms of the kinds of circuits that our current heuristics are well-equipped to discover. For instance, consider the algorithm for automated circuit discovery proposed by Conmy al. (2023), which eliminates one network component time if the consequence on behavior is reasonably small. Since this algorithm runs in polynomial time, it is not likely to solve the problems proven hard here, such as MINIMAL SUFFICIENT CIRCUIT. How- ever, one reason we observe interesting results in some cases is because it is well-equipped to solve QUASI-MINIMAL CIRCUIT problems. As our conceptual and formal analyses show, quasi- minimll circuits can mimic various desirable aspects of sufficient circuits (Table 1), and the former can be found tractably (results for Problem 2 and Problem 7). At the same time, understanding these prop- erties of circuit discovery heuristics helps us explain observed discrepancies: why we often see (1) lack of faithfulness (i.c., global coverage is out of reach for QMC algorithms), (2) non-minimality (i.e.. QM circuits can have many non-breaking points), and (3) large variability in performance across tasks and analysis parameters (e.g., Shi et al., 2024; Conmy et al., 2023).
Although we find that many queries of interest intractable in the general case (and empirical results are in line with this characterization), this should not paralyze efforts to interpret neural net- work models. As our exploration of the current complexity landscape shows, reasonable relaxations, restrictions and problem variants can yield tractable queries for circuits with useful properties. Con- sider a few out of many possible avenues to continue these explorations.
(i) Study query parameters. Faced with an intractable query, we can investigate which parameters of the problem (e.g., network circuit aspects) might be responsible for its core hardness. If these problematic parameters can be kept small in real-world applications, this yields a fixed-parameter tractable query. We have explored some, but more are possible as any aspect of the problem can be parameterized. A close dialogue between theorists and experimentalists is important for this, as empirical regularities suggest which parameters might be fruitful to explore theoretically, and experiments test whether theoretically conjectured parameters can be kept small in practice.
(ii) Generate novel queries. Our formalization of quasi-minimal circuit problems illustrates the search for viable algorithmic options with examples of tractable problems for inner interpretabil- ity. When the use case is well defined, efficient queries that return circuits with useful affordances for applications can be designed. Alternative circuits might also mimic the affordances for predic- tion/control of ideal circuits while avoiding intractability.
(iii) Explore network output axis of approximation. Some of our constructions use binary in- put/output (following previous work; e.g.. Bassan et al., 2024; Barceló et al., 2020). Although con- (see Appendix for (counterJexamplee
tinuous output does not necessarily matter complexity this is an interesting direction for future work, as it opens the door to studying the network output as an axis of approximation, which in turn might be a useful relaxation.
(iv) Design more abstract queries. A different path is to design queries that partially rely on mid- level abstractions (Vilas al., 2024a) to bridge the gap between circuits and human-intelligible algorithms (c.g., key-value mechanisms; Geva et al., 2022; Vilas et al., 2024b).
(v) Characterize actual network structure. is in principle possible that some real-world, trained neural networks possess internal structure that is benevolent to general (ideal) circuit queries (c.g.. redundancy; see Appendix). In such optimistic scenarios,
purpose heuristics might work well. The empirical evidence available to date, however, speaks against this. In any case, it will always be important to characterize any such structure to use it explicitly to design algorithms with useful guarantees.
(vi) Compare resource demands of intepprtaaiiityyepllaanbittttt across architectures. Our results for inner interpretability complement those of explainability (e.g., Barceló et al., 2020; Bas- san et al., 2024; Wäldchen et al., 2021). These aspects can be studied together for different ar- chitectures to assess their intrinsic interpretability. To some extent our results already transfer to some cases of interest. Since the transformer architecture contains MLPs, the complexity status of our circuit queries bears neuron-level circuit discovery efforts in transformers (c.g., Large I Language/Vision// Audio models).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank Ronald de Haan for comments on proving membership using alternating quantifier formu- las.
REFERENCES
Federico Adolfi. Computational Meta-Theory in Cognitive Science: A Theoretical Computer Sci- ence Framework. PhD thesis, University of Bristol, Bristol, UK, 2023.
Federico Adolfi and Iris van Rooij. Resource demands of implementationist approach to cogni- tion. In Proceedings of the 21 International Conference on Cogmitive Modeling, 2023.
Federico Adolfi, Martina G. Vilas, and Todd Warcham. Cumplexity-Theoree Limits the Promises of Artificial Neural Network Reverse-Engineenee Proceedings of the Annual Meet- ing of the Cognitive Science Society, 46(0), 2024.
Sanjeev Arora and Boaz Barak. Computational Complexity: Modern Approach. Cambridge University Press, Cambridge: New York, 2009. ISBN 778-0-521-42426-1
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verifica- tion and the hardness of approximation problems. Journal of the ACM (JACM), 45(3)5501-555, 1998.
Giorgio Ausiello, Alberto Sharchetti-paaccamet Pierluigi Crescenzi, Giorgio Gambosi, Marco Pro- tasi, and Viggo Kann. Complexity and Approxúmation. Springer Berlin Heidelberg, Berlin, Hei- delberg, 1999. ISBN 978-3-642-63581-
Pablo Barceló, Mikaël Monet, Jorge Pérez, and Bernardo Subercaseaux. Model Interpretability through the lens of Computational Complexity. In Advances Neural Information Processing Systems, volume 33, pp. 15487-15498. Curran Associates, Inc., 2020.
Shahaf Bassan and Guy Katz. Towards Formal XAI Formally Approximate Minimal Explanations of Neural Networks. In Tools and Algorithms for the Construction and Analysis of Systems: 29th International Conference, TACAS 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22-27, 2023, Proceedings, Part I, pp. 187-207, Berlin, Heidelberg. 2023. Springer- Verlag. ISBN 97833-031-30822-2.
Shahaf Bassan, Guy Amir, and Guy Katz. Local vs. Global Interpretabilityy A Computational Com- plexity Perspective. In Proceedings of the 41st International Conference on Machine Learning, pp. 3133-3167. PMLR, 2024.
David Bau, Jun Zhu, Hendrik Strobelt, Agata Lapedriza, Bolei Zhou, and Antonio Torralba. Understanding the role individual units deep neural network. Proceedings of the National Academy of Sciences, 117(49):3071-33007 2020.
Leonard Bereska and Stratis Gavves. Mechanistic interpretability for AI safety review. Trans- actions on Machine Learning Research, 2024. ISSN 2835-8856. Survey Certification, Expert Certification.
Armin Biere, Marijo J. H. Heule, Hans van Maaren, and Toby Walsh (eds.). Handbook of Satisfia bility. Number Volume 3 in Frontiers in Artificial Intelligence and Applications. IOS Press, Amsterdam Berlin Washington, DC, second edition edition, 2021. ISBN 978-1-64368-166-3.
Nick Cammarata, Shan Carter, Gabriel Goh, Chris Olah, Michael Petrov, Ludwig Schubert, Chelsea Voss, Ben Egan, and Swee Kiat Lim. Thread: Circuits. Distill, 5(3)=22,, 2020.
Rosa Cao and Daniel Yamins. Explanatory models in neuroscience, Part 2: Functional intelligibility and the contravariance principle. Cognitive Systems Research, pp. 101200, 2023.
Sitan Chen, Adam R. Klivans, and Raghu Meka. Learning Deep ReLU Networks Is Tixed-Parameter Tractable. (arXiv:2009.13511 2020.
11

---

Published as a conference paper at ICLR 2025
Yijia Chen and Bingkai Lin. The Constant Inapproximabilit of the Parameterized Dominating Set Problem. SIAM Journal on Computing. 48(2):513-5333 5,,,,,3,,111 2019.
Arthur Conmy, Augustine Mavor-Parker, Aengus Lynch, Stefan Heimersheim, and Adrià Garriga- Alonso. Towards Automated Circuit Discovery for Mechanistic Interpretability. Advances in Neural Information Processing Systems, 36: 13118-663,,, 2023.
Damai Dai, Li Dong, Yaru Hao, Zhifang Sui, Baobao Chang, and Furu Wei. Knowledge Neu- rons in Pretrained Transformers. Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 8493-8502, Dublin, Ireland, 2022. Association for Computational Linguisties.
Ronald de Haan and Stefan Szeider. Parameterized complexity classes beyond para-NP. Journal of Computer and System Sciences, 87:16-57, 2017.
R. G. Downey and M. R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer New York, New York, NY, 1999. ISBN 978-1-4612-67999 978-1-4612-0515-99
Rod G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London [u.a.], 2013. ISBN 978-1-4471-55500
Ebrahim Feghhi, Nima Hadidi, Bryan Song, Idan A. Blank, and Jonathan C. Kao. What Are Large Language Models Mapping to in the Brain? A Case Against Over-Reliance on Brain Scores. (arXiv:2406.01533) 2024.
Javier Ferrando and Elena Voita. Information Flow Routes: Automatically Interpreting Language Models at Scale. (arXiv:2403.00824) 2024.
Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts Theoretical Computer Science. Springer, Berlin Heidelberg New York, 2006. ISBN 978-3-540-29953-00
Lance Fortnow. The status of the P versus NP problem. Communications of the ACM, 52(9):78-86, 2009.
Dan Friedman, Andrew Lampinen, Lucas Dixon, Danqi Chen, and Asma Ghandeharioun. Inter- pretability Illusions in the Generalization of Simplified Models. (arXiv:2312.036666,, 2024.
Ella M. Gale, Nicholas Martin, Ryan Blything, Anh Nguyen, and Jeffrey S. Bowers. Are there any 'object detectors' in the hidden layers of CNNs trained to identify objects or scenes? Vision Research, 176:60-71, 2020.
Jorge García-Carraseo Alejandro Maté, and Juan Trujillo. Detecting and Understanding Vulnera- bilities Language Models via Mechanistic Interpretability. In Proceedings of the Thirty-Thin International Joint Conference Artificial Intelligence, pp. 385-393, 2024.
Michael R Garey and David S Johnson. Computers and intractability. W.H. Freeman, 1979.
William I. Gasarch, Mark Krentel, and Kevin Rappoport. OptP as the normal behavior of NP-complete problems. Mathematical Systems Theory, 28(6):487-514, 1995.
Atticus Geiger, Duligur lbeling, Amir Zur, Maheep Chaudhary, Sonakshi Chauhan, Jing Huang, Aryaman Arora, Zhengxuan Wu, Noah Goodman, Christopher Potts, and Thomas Ieard. Causal Abstraction: A Theoretical Foundation for Mechanistic Interpretability. (arXiv:2301.04709, 2024.
Mor Geva, Roei Schuster, Jonathan Berant, and Omer Levy. Transformer Feed-Forward Layers Are Key- Value Memories. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen- tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 5484-5495, Online and Punta Cana, Dominican Republic, 2021. Association for Computational Linguistics.
12

---

Published as a conference paper at ICLR 2025
Mor Geva, Avi Caciularu, Kevin Wang. and Yoav Goldberg. Transformer feedd-oowwad Layers Build Predictions by Promoting Concepts in the Vocabulary Space. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, pp. 30-45, Abu Dhabi, United Arab Emirates, 2022. Association for Computational Linguistics.
Asma Ghandeharioun, Avi Caciularu, Adam Pearce, Lucas Dixon, and Mor Geva. Patchscopes: Unifying Framework for Inspecting Hidden Representations of Language Models. In Proceedings of the st International Conference on Machine Learning, pp. 15466-15490. PMLR, 2024.
John Gill. Computational Complexity of Probabilistic Turing Machines. SIAM Journal on Comput- ing, 6(4):675-695, 1977.
Nicholas Goldowsky-Dill, Chris MacLeod, Lucas Sato, and Aryaman Arora. Localizing Model Behavior with Path Patching. (arXIv:300.00596), 2023.
Wes Gurnee, Neel Nanda, Matthew Pauly, Katherine Harvey, Dmitri Troitskii, and Dimitris Bertsi- mas. Finding Neurons in Haystack: Case Studies with Sparse Probing. Transactions on Machine Learning Research, 2023.
Michael Hanna, Ollie Liu, and Alexandre Variengien. How does GPT-2 compute greater-than?: Interpreting mathematical abilities pre-trained language model. In Thirty-Seventh Conference on Neural Information Processing Systems, 2023.
Michael Hanna, Sandro Pezzelle, and Yonatan Belinkov. Have Faith in Faithfulness: Going Beyond Circuit Overlap When Finding Model Mechanisms. (arXiv:200311786)) 2024.
Peter Hase, Mohit Bansal, Been Kim, and Asma Ghandeharioun. Does Localization Inform Edit- ing? Surprising Differences in Causality-Based Localization vs. Knowledge Editing in Language Models. Advances in Neural Information Processing Systems, 36:17643-17668, 2023.
Lane A. Hemaspaandra and Ryan Williams. SIGACT News Complexity Theory Column 76: An atypical survey of typical-case heuristic algorithms. ACM SIGACT News, 43(4):70-88 89, 2012.
John M. Hitchcock and A. Pavan. On the UP-Completeness of the Minimum Circuit Size Problem. LIPlcs, Volume 45, FSTTCS 2015, 45:236-2455 2015.
Nhat Hoang-Xuan, Minh Vu, and My T. Thai. LLM-assisted Concept Discovery: Automatically Identifying and Explaining Neuron Functions. (rxXiv:2406.08522) 2024.
Sara Hooker, Aaron Courville, Gregory Clark, Yann Dauphin, and Andrea Frome. What Do Com- pressed Deep Neural Networks Forget? (arXiv:1911.0524) 2021.
Alon Jacovi and Yoav Goldberg. Towards Faithfully Interpretable NLP Systems: How Should We Define and Evaluate Faithfulness? In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 4198-4205, Online, 2020. Association for Computational Linguistics.
N. Karmarkar. A new polynomial-tin algorithm for linear programming. Combinatorica, 4(4): 373-395, 1984.
János Kramár, Tom Lieberum, Rohin Shah, and Neel Nanda. AIp*; An efficient and scalable method for localizing LLM behaviour components. (arXiv:2403.00745) 2024.
MW Krentel. The complexity of optimization functions. Journal of Computer and System Sciences, 36(3):490-509, 1988.
Andrew Kyle Lampinen, Stephanie C. Y. Chan, and Katherine Hermann. Learned feature represen- tations are biased by complexity, learning order, position, and more. Transactions on Machine Learning Research, 2024.
Jae Hee Lee, Sergio Lanza, and Stefan Wermter. From Neural Activations to Concepts: A Survey on Explaining Concepts in Neural Networks, (arXiv:2310.11 1184), 2023.
13

---

Published as a conference paper at ICLR 2025
Michael A. Lepori, Thomas Serre, and Ellie Pavlick. Uncovering Causal Variables in Transformers using Circuit Probing. (arXiv:2311.04354) 2023.
Tom Lieberum, Matthew Rahtz, János Kramár, Neel Nanda, Geoffrey Irving, Rohin Shah, and Vladimir Mikulik. Does Circuit Analysis Interpretability Scale? Evidence from Multiple Choice Capabilities in Chinchilla. surXiv:2307.09488) 2023.
Grace W Lindsay. Grounding neuroscience in behavioral changes using artificial neural networks. Current Opinion in Neurobiology, 2024.
Grace W. Lindsay and David Bau. Testing methods of neural systems understanding. Cognitive
Systems Research, 82:101 156, 2023.
Roi Livni, Shai Shalev-Shwartz. and Ohad Shamir. On the Computational Efficiency of Training Neural Networks. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Samuel Marks, Can Rager, Bric J. Michaud, Yonatan Belinkov, David Bau, and Aaron Mueller. Sparse Feature Circuits: Discovering and Editing Interpretable Causal Graphs in Language Mod- cls. (arXiv:2403.196) 2024.
Andrew Mclnerney and Kevin Burke. Feedforward neural networks as statistical models: Improving interpretability through uncertainty quantification. (arXiv:2311.081333 2023.
Kevin Meng, Arnab Sen Sharma, Alex J. Andonian, Yonatan Belinkov, and David Bau. Mass- Editing Memory in Transformer. In The Eleventh International Conference on Learning Repre- sentations, 2022.
Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov. Locating and editing factual associations in GPT. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, pp. 17359-17372, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 978-1-71387-1088
Jack Merullo, Carsten Eickhoff, and Ellie Pavlick. Circuit Component Reuse Across Tasks in Trans- former Language Models. In The Twelfth International Conference on Learning Representationss 2024.
Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge: New York, 1995. ISBN 978-0-521-47465-8
Vedant Nanda, Till Speicher, John Dickerson, Krishna Gummadi, Soheil Feizi, and Adrian Weller. Diffused redundancy in pre-trained representations. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, Curran Associates, Inc., 2023.
volume 36, pp. 4055-4073
Jingcheng Niu, Andrew Liu, Zining Zhu, and Gerald Penn. What does the Knowledge Neuron Thesis Have to with Knowledge? In The Twelfth International Conference on Learning Rep- resentations, 2023.
Chris Olah, Alexander Mordvintsev, and Ludwig Schubert. Feature Visualization. Distill, 2(11))e7, 2017.
Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter. Zoom In: An Introduction Circuits. Distill, 5(3):c00024.001, 2020.
Subba Reddy Oota, Emin Çelik, Fatma Deniz, and Mariya Toneva. Speech language models lack important brain-relevant semantics. (arXiv:2311.04666) 2023.
Sebastian Ordyniak, Giacomo Paesani, and Stefan Szeider. The Parameterized Complexity of Find- ing Concise Local Explanations. In Proceedings of the Thiroy- International Joint Con- ference on Artificial Intelligence, pp. 3312-3320, Macau, SAR China, 2023. International Joint Conferences on Artificial Intelligence Organization. ISBN 978- 978-1-956792--3-4
14

---

Published as a conference paper at ICLR 2025
C.H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Jour- nal of Computer and System Sciences, 43:425 440, 1991.
Ellie Pavlick. Symbols and grounding in large language models. Philosophical Transactions of the Royal Society Mathematical, Physical and Engineering Sciences, 38 (81221)):00200041 2023.
J. Scott Provan and Michael O. Ball. The Complexity of Counting Cuts and of Computing the Probability that a Graph Connected. SIAM Journal on Computing, 12(4):777-788, 1983.
Venkatakrishnan Ramaswamy. An Algorithmic Barrier to Neural Circuit Understanding. bioRxiv, 2019. doi: 10.1101/639724.
Tilman Räuker, Anson Ho, Stephen Casper, and Dylan Hadfield-Menell Toward Transparent AI: A Survey on Interpreting the Inner Structures of Deep Neural Networks. In 2023 JEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 464-483, IEEE Computer Society, 2023. ISBN 978 978-1-66546-299-D0
Lauren N. Ross and Dani Bassett. Causation neuroscience: Keeping mechanism meaningful. Nature Reviews Neuroscience, 25(2):81 2024.
Loek Van Rossem and Andrew M. Saxe. When Representations Align: Universality in Repre- sentation Learning Dynamics. In Proceedings of the 41 International Conference on Machine Learning, pp. 49098-49121. PMLR, 2024.
Marcus Schaefer and Christopher Umans. Completeness the polynomial-time hierarchy: A com- pendium. SIGACT News, 33(3):32-49, 2002.
Claudia Shi, Nicolas Beltran- Achille Nazaret, Carolina Zheng, Adrià Garriga-Alonso, An- drew Jesson, Maggie Makar, and David Blei. Hypothesis Testing the Circuit Hypothesis in LLMs. In ICML 2024 Workshop on Mechanistic Interpretability. 2024.
Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the Complexity of Learning Neural Networks. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Bernardo Anibal Subercascaux. Model Interpretability through the Lens of Computational Com- plexity. PhD thesis, Universidad de Chile, 2020.
Aaquib Syed, Can Rager, and Arthur Conmy. Attribution Patching Outperforms Automated Circuit Discovery. In NeurlPS Workshop on Attributing Model Behavior Scale, 2023.
Curt Tigges, Michael Hanna, Qinan Yu, and Stella Biderman. LLM Circuit Analyses Are Consistent Across Training and Scale. (arXiv:2407.10827 2024.
Seinosuke Toda. PP is as Hard as the Polynomial Time Hierarchy. SIAM Journal on Computing, 20 39:866-877, 1991.
Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai Thomas Un- terthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, and Alexey Dosovitskiy. MLP-Mixer: An all-MLP Architecture for Vision. 35th Conference on Neural Information Processing Systems (NeurIPS 2021), volume 34, pp. 24261-24272. Curran Associates, Inc., 2021.
Leslie G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing, 430):400-4 1979.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E. ukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural In- formation Processing Systems, volume 30. Curran Associates, Inc., 2017.
Martina G. Vilas, Federico Adolfi, David Poeppel, and Gemma Roig. Position: An Inner Inter- pretability Framework for Al Inspired by Lessons from Cognitive Neuroscience. In Proceedings of the 41st International Conference Machine Learning, pp. 49506-49522. PMLR, 2024a.
15

---

Published as a conference paper at ICLR 2025
Martina G. Vilas, Timothy Schaumlöffel, and Gemma Roig. Analyzing vision transformers for im- age classification in class embedding space. Proceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23, pp. 40030-40044 Red Hook, NY, USA, 2024b. Curran Associates Inc.
Chelsea Voss, Nick Cammarata, Gabriel Goh, Michael Petrov, Ludwig Schubert, Ben Egan, Swee Kiat Lim, and Chris Olah. Visualizing Weights. Distill, 6(2):e0024.0007, 2021.
Stephan Wäldchen, Jan Macdonald, Sascha Hauch, and Gitta Kutyniok. The computational com- plexity of understanding binary classifier decisions. Journal of Artificial Intelligence Research, 70:351-387, 2021.
Kevin Ro Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt, In- terpretability in the Wild: A Circuit for Indirect Object Identification in GPT-2 Small. In The Eleventh International Conference on Learning Representations, 2022.
Zihao Wang and Victor Veitch. Does Editing Provide Evidence for Localization? In ICML 2024
Workshop on Mechanistic Interpretability, 2024.
Harold Wareham. Systematic Parameterized Complexity Analysis in Computational Phonology-
PhD thesis, University of Victoria, Canada, 1999.
Todd Wareham. Creating teams of simple agents for specified tasks: A computational complexity perspective. (arXiv:2205.02061) 2022.
Lei Yu, Jingeheng Niu, Zining Zhu, and Gerald Penn. Functional Faithfulness in the Wild: Circuit Discovery with Differentiable Computation Graph Pruning. (acXiv:2407.03779,, 2024a.
Runpeng Yu, Weihao Yu, and Xinchao Wang. (4rXiv:2407.16674), 2024b.
KAN or MLP: A Fairer Comparison.
Enyan Zhang, Michael A. Lepori, and Ellie Pavlick. Instilling Inductive Biases with Subnetworks. (arXiv:2310.10899) 2024.
Fred Zhang and Neel Nanda. Towards Best Practices of Activation Patching in Language Models: Metries and Methods. In The Twelfth International Conference on Learning Representattons, 2023.
16


Reviews:
[{"review_id": "P0vNeAXjTH", "reviewer": "Reviewer_19hk", "summary": "The paper studies the computational challenges surrounding the fields of circuit discovery and mechanistic interpretability. Achieving circuit discovery or accurate and precise interpretability at scale is a major empirical challenge for deep learning today. This paper sheds light on why that goal might be computationally out of reach by showing that many of the tools we use today end up having to solve computationally hard problems. Some of the specific problems the paper studies computational complexity of are:\n\n1. Sufficient circuit – finding a small sub-circuit which reproduces the behavior of the network on a specific input or all inputs.\n2. Gnostic neurons – a set of neurons with maximally distant activations of certain subsets of inputs we are trying to classify between.\n3. Circuit Ablation and Clamping\n4. Circuit patching\n5. Circuit robustness\n6. Sufficient reasons\n\nFor all these different problems, the paper studies the computational hardness of the general problem, fixed-parameter tractability, hardness of approximation (additive, multiplicative and probabilistic).\nThey show that while some of these problems are solvable in poly time (like gnostic neurons) most remain hard even to approximate. However, some are NP-complete and have reductions from 3SAT which leaves the promise of SAT-solver heuristic being applicable for these problems.\nIn addition, for some problems the results show a separation between local notion of interpretability (which captures a certain property only on a small set of inputs) and a global notion (which captures the property over the entire input range). Such separations are proposed as a reason for why local explanations of faithfulness in the past have been shown to be at times fickle.", "questions": "-\tWhat is the valid criticism of zero-ablation? (line 285)\n-\tCan you add a brief discussion on how your results relate to some computational hardness results known for PAC-learning variants of neural networks. In particular, I’m curious to understand if any of your results follow more directly from some of the hardness reductions considered in these works. Some example works (a non-exhaustive list) are cited below ([1-3]).\n-\tWhat happens if we relax the assumption of having a step function at the output layer? Would most of the problems studied continue to remain intractable. (note that now we can also allow for an approximation in the quality of the output. i.e. the sub-circuit doesn’t have to exactly match the behavior of the original circuit, it can be approximately close)\n\n\n1. On the computational efficient of training neural nets. Livni et. al.\n2. On the complexity of learning neural networks. Song et. al.\n3. Learning deep neural networks is fixed-parameter tractable. Chen et. al.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "-\tThe paper tackles an important conceptual question facing empirical deep learning today. Although its results are theoretical and computational complexity has faced criticism in the past of being overly pessimistic, it is nevertheless a stellar guiding light as to what problems are tractable and might be solvable without requiring any additional assumptions.\n-\tThe paper provides some transformations/additional assumptions with which some of the problems to be solved start becoming tractable.\n-\tThe paper is quite comprehensive in its coverage of different notions and tools used in mechanistic interpretability literature.\n- Even if computational hardness for many of the problems being studied is to be expected by theorists, it is important to compile the results and clearly state the message as it might help guide practitioners search for tractable notions of interpretability.", "weaknesses": "-\tComputational complexity of PAC learning MLPs is a well-studied problem by the learning theory community and has connections to many of the results you study here. A comparison to some of the hardness results already known there is in order.\n-\tThe assumption of applying a step function on the output is quite stringent. It is known that being able to see a real-valued output rather than a Boolean output can make some learning problems on neural nets tractable [1]. The results of the paper would be stronger and more significant if they hold without the step function being applied at the end.\n-\tFor most of the interpretability tasks, the notion of approximation considered to measure the quality of the sub-circuit found allows for some amount of flexibility in capturing the output behavior. This axis of approximation doesn’t seem to be addressed in your work (apologize if I missed it). Could the landscape change for any of the problems when considering such an approximation. \n\n\n[1] Reliably Learning the ReLU in Polynomial Time. Goel et. al.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rStRcavV28", "reviewer": "Reviewer_ZH6m", "summary": "The authors frame a large number of circuit discovery problems in mechanistic interpretability as a set of formally defined queries about computational graphs.\nThey identify and prove the complexity classes for each of these queries. They also find the fixed-parameter complexity classes and the complexity of several types of approximations to the optimal algorithms.", "questions": "Some proofs rely on step functions being applied to neuron activations. To what extent do these proofs apply to neural networks with only ReLU activation functions? I believe that ReLU MLPs can approximate step functions, but not implement them exactly. Alternatively, could you extend your proofs such they don't rely on step functions?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This is the first formal characterization of the complexity of circuit discovery that I am aware of. It is very useful for the field to formalize problems such that they can be reasoned about with clarity. The formal characterization is also useful to clearly enumerate all the types of circuit queries that mechanistic interpretability researchers might want to perform to understand networks.\n\nThe paper is extremely thorough in covering a wide range of queries. The proofs that I read in detail (Appendix B on Minimum Locally Sufficient Circuits) appeared to be correct.", "weaknesses": "It is unclear to what extent these results should be major considerations for applied circuit discovery in real models. Heuristics such as gradient magnitude may be powerful enough to achieve close to optimal solutions with simple algorithms. The authors should include discussions of this to clarify.\n\nThe paper is primarily of use to researchers in mechanistic interpretability. Yet many researchers in the field will struggle to quickly understand much of the paper due to terse explanations of basic concepts in complexity theory. To some extent this is unavoidable as it would be arduous to include extensive tutorials on basic concepts from complexity, but a few well-chosen explanations could go a long way to bridge the gap for researchers who have some background in computer science. For example, more intuitive definitions of fixed parameter complexity, W[1]-hard and $\\Sigma^{p}_{2}$-hard could be fairly concise and save many readers from needing to search for external resources.\n\nFurther, it would be useful to spell out more explicitly for less familiar readers how each proof connects to real world applications of circuit discovery. For example, since transformers contain MLPs, the proofs of complexities of queries on MLPs also apply to neuron level circuit discovery in transformers. Similarly, since binary vectors are a subset of the possible inputs to a real model, some proofs apply to models which are not constrained to binary inputs.\n\nSince real models do not have binary activations, it is almost impossible for a circuit to achieve perfect faithfulness. In practice, we want our circuits to produce outputs that are sufficiently close to the full model output. But the problems considered by the authors ask for circuits that are perfectly faithful. So the authors should discuss whether their results apply in practice to realistic circuit discovery requirements.\n\nSome smaller nitpicks:\n- In Table 2: The notation “ “ is unclear because it looks like it could mean the same value as the previous row. It would be clearer to use a faded font or simply leave the box empty.\n - In Table 2: There is no explanation of \"Coverage In\" vs \"Coverage Out\".\n - I don’t understand why the coverage out of local circuits is empty.\n - In Appendix A.3 there is no explanation of function g(k).\n - In Appendix A.4.1 the variable I (instances) should be explained in the first paragraph.\n - In Appendix B, in the definition of MLSC, it’s unclear what the purpose of the constant c is.\n - In Appendix B, in Table 5, the third column is not labeled.\n - In Appendix B.2 make it clear which parts of proofs are being repeated from earlier parts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A2rrtxBFPe", "reviewer": "Reviewer_8wLc", "summary": "This paper presents a framework for examining the computational complexity of generating various types of \"interpretability queries\" within the field of mechanistic interpretability. Unlike previous work that explored the complexity of post-hoc explanations for different ML models, primarily focusing on explanations in the input domain, this paper extends these findings by providing similar forms of explanations (specifically for neural networks) at the neural level rather than the input level. The paper also introduces complexity results for different mechanistic interpretability queries, demonstrating the intractability of some queries while proving that others are tractable, especially under certain relaxations.", "questions": "1. Over what type of input domain are the results defined (binary, discrete, or continuous)? \n\n2. What non-trivial proofs are presented in the paper?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper's primary strength lies in bridging two distinct areas of interest: (1) the formal analysis of the computational complexity involved in generating various forms of explanations (as explored in [1] and [2]), which often fall under the sub-domain known as \"formal explainable AI,\" and (2) the more contemporary field of mechanistic interpretability. While prior work has proposed using the computational complexity of post-hoc explanations to shed light on interpretability (e.g., [1], [2]), this paper extends that concept by linking it to mechanistic interpretability queries. I believe this approach has the potential to inspire further research in both domains, facilitating a more rigorous analysis of mechanistic interpretability, an area that is currently somewhat underexplored. Additionally, this work offers a thorough categorization of different mechanistic interpretability queries, providing a solid foundation for future studies.\n\n[1] Model Interpretability through the Lens of Computational Complexity (Barcelo et. al, Neurips 2020)\n\n[2] Local vs. Global Interpretability: A Computational Complexity Perspective (Bassan et. al, ICML 2024)", "weaknesses": "1. The paper does not clearly discuss its limitations. I would be interested in hearing from the authors what they consider to be the main limitations of their work. While the paper focuses on neuron-level explanations, one evident (potential) limitation is the lack of clarity around the definition of the input space domain. From my understanding, it appears to be binary, but is that correct? Or is the input space discrete or continuous? Given that this research centers on neural networks, rather than simpler models where binary or discrete domains are more common, it would be reasonable to also consider more complex domains, such as continuous ones. Additionally, transitioning to continuous input settings could have significant implications for the complexity of the problem. This should (at the very least) be discussed by the authors.\n\n2. Many of the proofs presented in the paper appear to be relatively straightforward, and I’m not fully convinced of the *technical* significance of this work. It would be beneficial to clearly indicate when a proof is trivial versus when it is non-trivial. Additionally, specifying when a result confirms well-known folklore assumptions, and when it is genuinely surprising would enhance clarity. This distinction was not always evident in the paper.\n\n\n3. Some of the \"folklore\" concepts that this paper seeks to rigorously prove are somewhat unclear. For instance, the explanation of this idea could be improved:\n\nThis result establishes a formal separation\n between local and global query complexity that partly explains ‘interpretability illusions’ (Friedman\n etal.,2024;Yuetal.,2024a) arising in practice due to local but not global faithfulness.\n\nthe meaning of \"interpretability illusions\" is not clearly defined.\n\n4. I'm not entirely convinced by the rigid distinction between \"interpretability\" as being neuron-level and \"explainability\" as being input-level. Naturally, the efficiency of providing explanations at the input level is also closely tied to the model's interpretability, not just its neuron-level explanations. Perhaps a more appropriate way to differentiate between the outcomes here and those in previous studies is to describe them as explanations or interpretations at the \"input level\" versus the \"neuron level,\" both of which contribute to the model’s overall interpretability.\n\n5. The main table is excellent and offers a clear summary of the results. However, a more concise version of this table might be preferable for the main text, with the larger, detailed version included in the appendix.\n\n6. The paper suggests that problems “contained” within NP can be efficiently addressed using SAT solvers. However, this is not always the case—when it comes to neural networks, especially for continuous domains, neural network verification models often serve as more appropriate optimization tools. These are usually not based on SAT solvers, but rather on SMT-based solvers, or branch-and-bound methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HYFDZjEvqL", "reviewer": "Reviewer_YPDD", "summary": "The paper formalizes several problems along the lines of finding the minimal subcircuit in a deep network that matches its computation; this is motivated by finding a small interpretable subcircuit. They show that this and several variants of this problem are intractable (either NP-hard or \\Sigma_2^2. For several variants they all show that there is no PTAS.", "questions": "The paper is well written and gives nice clean formalization of several problems motivated by interpretability.\n\nIn several of the problem formalizations you are trying to find the minimal sub-circuit for a given input x. If the problem is a boolean classification problem then in many circuits there might be some trivial tiny sub-circuits that give the correct output for that given x -- in your reduction you have avoided that by choosing a carefully crafted worst case circuit. Wouldn’t it make more sense to look at a distribution of inputs? I would have expected that one would get a much stronger inapproximability hardness result if you took a set of inputs and insisted that the sub-circuit should output correctly for all inputs which you are doing problem 8.\n\nWhat is the takeaway here for interpretability in practice? Do you think interpretability is essentially intractable? Please expand on potential practical approaches to interpretability in light of these hardness results with scenarios and reasons as to why interpretability might still be feasible despite the worst-case intractability.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Interpreting formalization and complexity study of several problems motivated by interpretability of deep networks.", "weaknesses": "The hardness results are not surprising. The area of finding small circuits is in general very hard (see for example: https://www.cs.uwyo.edu/~jhitchco/papers/npcmcsp.pdf even though it is a related but very different problem). The reduction from CLIQUE is simple.\n\nThe worst case hardness may not capture the average case complexity for real world distributions. I do understand proving hardness results for probabilistic settings is more difficult. But the impossibility results may not imply hardness of interpretability in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)