The Computational Complexity of Circuit Discovery for Inner Interpretability

Federico Adolfi, Martina G. Vilas, Todd Wareham

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:

Table 1: Circuit affordances for description, explanation, prediction, and control.

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:

Figure 1: Relationships between circuit types. Sufficient Circuits (SCs) are faithful to the model. The entire network is a trivial SC. Necessary Circuits (NCs) are units shared by all minimal SCs. Quasi-minimal SCs contain a known breaking point (here, NC) and unknown superfluous units.

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

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.
BibTeX
@inproceedings{adolfi2025computational,
  author = {Federico Adolfi and Martina G. Vilas and Todd Wareham},
  title = {{The Computational Complexity of Circuit Discovery for Inner Interpretability}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=QogcGNXJVw},
}
Figure