Research map / Learning theory and algorithms / Combinatorial and search optimization
The Computational Complexity of Circuit Discovery for Inner Interpretability
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses classical and parameterized complexity theory to map the complexity landscape of circuit-discovery queries (sufficient, necessary, patched, ablation, clamping, robustness circuits) on multi-layer perceptrons, identifying intractable, FPT, and tractable variants and their approximability.
Problem
Circuit discovery for inner interpretability of neural networks is used in many applications, but the computational complexity of its queries (finding faithful, minimal, or necessary circuits) is largely unknown, which bears on scalability and faithfulness of heuristics.
Approach
Formalizes circuit-finding queries on MLPs as computational problems (local vs. global coverage, bounded/unbounded size, minimality) and settles their classical, parameterized, counting, and approximation complexity; introduces quasi-minimality as a relaxation that yields PTIME queries retaining useful affordances.
Key results
- Local sufficient circuit is NP-complete while global sufficient circuit is Σ^p_2-complete, establishing a formal local-vs-global complexity separation.
- Unbounded quasi-minimal local sufficient circuit is computable in PTIME, giving a tractable relaxation.
- Circuit robustness parameterized by |H| is fixed-parameter tractable, while local circuit robustness is coNP-complete.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the general sufficient-circuit query with unbounded quasi-minimality | Sufficient Circuit on MLPs · Local sufficient-circuit search | complexity: NP-complete -> PTIME | Helped |
| replace general circuit patching with unbounded quasi-minimality | Circuit Patching on MLPs · Local circuit patching | complexity: NP-complete -> PTIME | Helped |
| require global rather than local sufficiency | Sufficient Circuit on MLPs · Bounded sufficient-circuit search | complexity: NP-complete -> $\Sigma^p_2$-complete | Hurt |
| parameterize circuit robustness by |H| | Circuit Robustness on MLPs · Local and global circuit robustness | complexity: coW[1]-hard -> FPT | Helped |
| constrain the MLP to one hidden layer | Sufficient Reasons on MLPs · Local sufficient reasons | complexity | No clear effect |
| keep network depth small | Sufficient Circuit on MLPs · Bounded sufficient-circuit search | complexity | No clear effect |
Surprising findings
- Hardness of sufficient circuits does not depend straightforwardly on network depth: it is W[1]-hard relative to depth-related parameters, so keeping models shallow does not mitigate hardness.
- Many hard circuit queries are inapproximable under additive, multiplicative, and probabilistic approximation schemes.
Limitations
- Results concern worst-case complexity on MLPs with binary inputs/outputs; transfer to trained real-world networks is not established.
- Many query variants remain open (marked '?'), including unbounded minimal and global gnostic neuron problems.
Experimental setup
Builds on: Sufficient reasons explainability complexity Parameterized complexity theory Activation patching Automated circuit discovery
Closest papers by meaning
- Efficient Automated Circuit Discovery in Transformers using Contextual Decomposition (ICLR 2025 · similarity 0.89)
- Transcoders find interpretable LLM feature circuits (NeurIPS 2024 · similarity 0.89)
- Everything, Everywhere, All at Once: Is Mechanistic Interpretability Identifiable? (ICLR 2025 · similarity 0.88)
- Sparse Feature Circuits: Discovering and Editing Interpretable Causal Graphs in Language Models (ICLR 2025 · similarity 0.87)
- Many Circuits, One Mechanism: Input Variation and Evaluation Granularity in Circuit Discovery (NeurIPS 2026 · similarity 0.87)
- Local vs. Global Interpretability: A Computational Complexity Perspective (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.