TL;DR
This paper presents the first systematic complexity-theoretic analysis of circuit discovery for inner interpretability, revealing a challenging landscape where most standard queries are highly intractable (NP-hard or $\Sigma_2^p$-hard). However, the authors show that by relaxing strict minimality to a novel property called "quasi-minimality," we can unlock tractable, polynomial-time algorithms for mechanistic explanation.
What Problem Does This Paper Address?
As artificial neural networks grow in size and capability, understanding how they make decisions becomes crucial. "Inner interpretability" attempts to look under the hood by identifying "circuits"—small, functional subnetworks responsible for specific behaviors.
While researchers have developed various heuristic methods (like activation patching or pruning) to find these circuits, we lack a fundamental understanding of whether these problems are actually scalable or faithful. This paper addresses this gap by formalizing a comprehensive set of circuit discovery queries and evaluating their fundamental computational limits using classical and parameterized complexity theory.
Methods
The authors use computational complexity theory to map out the resource demands of circuit discovery on Multi-Layer Perceptrons (MLPs). They formalize queries based on their practical "affordances"—what they allow a researcher to describe, explain, predict, or control—as summarized in Table 1:
To evaluate these queries, the authors construct mathematical reductions from canonical hard problems (such as CLIQUE, VERTEX COVER, and DOMINATING SET). They also analyze whether these problems can be salvaged using additive, multiplicative, or probabilistic approximation schemes.
Datasets
No empirical datasets were used in this work, as it is a purely theoretical paper focusing on computational complexity proofs.
Key Insights and Ideas
- Shallow Networks Aren't Easier: Counterintuitively, the intractability of finding sufficient circuits doesn't disappear in shallow networks; the problems remain fixed-parameter intractable (W[1]-hard) relative to network depth. Keeping models shallow does not mitigate the core hardness.
- The "Interpretability Illusion" Explained: The paper mathematically separates local complexity (evaluating a single input) from global complexity (all possible inputs). Local queries are typically NP-complete, while global ones shoot up to $\Sigma_2^p$-complete. This explains why a discovered circuit might seem perfectly faithful during local testing on a dataset but completely fail to generalize globally.
- Quasi-Minimality to the Rescue: While finding a strictly minimal circuit is intractable, the authors introduce quasi-minimality. A quasi-minimal circuit guarantees that we know at least one "breaking point" neuron (removing it breaks the behavior), even if some superfluous units remain. This subtle relaxation drops the problem's complexity down to polynomial time (PTIME), making it efficiently solvable.
As illustrated in Figure 1, this relationship helps us navigate the boundary between trivial, minimal, and quasi-minimal circuits:
Key Results
- Intractable Queries: Standard formulations of Sufficient Circuit (SC), Circuit Ablation (CA), Circuit Clamping (CC), and Circuit Patching (CP) are NP-hard or $\Sigma_2^p$-hard and are fundamentally inapproximable under additive, multiplicative, or probabilistic schemes.
- Tractable Queries: Unbounded Quasi-Minimal Local Sufficient Circuit (UQLSC) and Unbounded Quasi-Minimal Circuit Patching (QMCP) are proven to be in PTIME, meaning they can be computed efficiently.
- Gnostic Neurons: Finding "gnostic neurons" (units that respond preferentially to a specific concept) is also tractable and sits comfortably in PTIME.
Limitations and Future Work
- Architecture Focus: The proofs focus primarily on Multi-Layer Perceptrons (MLPs). While MLPs are core sub-components of Transformers, directly extending this framework to full Transformer architectures remains an open avenue.
- Discrete vs. Continuous: Many of the proof constructions rely on binary inputs and outputs. Investigating continuous network outputs as an axis of approximation is highlighted as a promising direction for future relaxation.
- Worst-Case vs. Average-Case: This study conducts a worst-case analysis. Real-world trained networks might possess benevolent internal structures (like high redundancy) that make average-case performance better than these theoretical bounds suggest.
Summary updated