MINAR: Mechanistic Interpretability for Neural Algorithmic Reasoning

Jesse He; Helen Jenne; Max Vargas; Davis Brown; Gal Mishne; Yusu Wang; Henry Kvinge

cs.LGFeb 24, 2026

MINAR: Mechanistic Interpretability for Neural Algorithmic Reasoning

Authors: Jesse He, Helen Jenne, Max Vargas, Davis Brown, Gal Mishne, Yusu Wang, Henry Kvinge

Organizations: Pacific Northwest National Laboratory, Richland, WA · Halıcı˘oğlu Data Science Institute, University of California, San Diego, San Diego, CA · Department of Computer and Information Science, University of Pennsylvania, Pennsylvaina, PA · Department of Mathematics, University of Washington, Seattle, WA

Abstract

The recent field of neural algorithmic reasoning (NAR) studies the ability of graph neural networks (GNNs) to emulate classical algorithms like Bellman-Ford, a phenomenon known as algorithmic alignment. At the same time, recent advances in large language models (LLMs) have spawned the study of mechanistic interpretability, which aims to identify granular model components like circuits that perform specific computations. In this work, we introduce Mechanistic Interpretability for Neural Algorithmic Reasoning (MINAR), an efficient circuit discovery toolbox that adapts attribution patching methods from mechanistic interpretability to the GNN setting. We show through two case studies that MINAR recovers faithful neuron-level circuits from GNNs trained on algorithmic tasks. Our study sheds new light on the process of circuit formation and pruning during training, as well as giving new insight into how GNNs trained to perform multiple tasks in parallel reuse circuit components for related tasks. Our code is available at https://github.com/pnnl/MINAR.

Figures & tables

Figure 1: MSE training loss, multiplicative test loss, and

L_{1}

regularization term for Bellman-Ford MinAggGNN.

Panel of Figure 2 — Figure 2: Identified circuit in the Bellman-Ford MinAggGNN (left) and parallel Bellman-Ford and BFS MinAggGNN (right). Nodes are individual MinAggGNN neurons. Input and output neurons are colored white, $f_{\Agg}$ neurons are colored blue, and $f_{\Up}$ neurons are colored orange. Circuit edges are colored by corresponding model weights.

Figure 3: Multiplicative test loss, MSE test loss, and

L_{1}

regularization terms for the Bellman-Ford network and circuit.

Figure 4: MSE training loss, multiplicative test loss, reachability accuracy, and

L_{1}

regularization term for parallel Bellman-Ford and BFS MinAggGNN.

Algorithm	BFS	DFS	Dijkstra	Prim’s MST	Bellman-Ford	Articulation Points	Bridges
Val Acc. (%)	99.90	70.73	93.37	81.15	93.75	94.63	78.68
Test Acc. (%)	98.25	36.42	81.50	48.18	82.55	97.42	88.22

Table 1: Validation and test accuracy of maximum-aggregated GINE on SALSA-CLRS.

Figure 5: Characterization score of circuits computed using Weight, WeightGrad , EAP, and EAP-IG (

m=20

) for SALSA-CLRS GNN for

K\in\{10,25,50,100,250,500,1000,1500,2000,2500,3000\}

Figure 6: Weighted Jaccard Similarity of task-specific circuits with WeightGrad , EAP, EAP-IG at $K=500$ .

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Circuit loss (left) and ablated circuit loss (right) for circuits found using Weight, WeightGrad , EAP, and EAP-IG (

m=20

) with

K=1,2,\dots,10

for the Bellman-Ford network.

Figure 8: Best Bellman-Ford circuit found by WeightGrad .

Figure 9: Bellman-Ford circuit at epoch 1000. The circuit contains 73 edges and achieves

\mathcal{L}_{\text{Mult}}=0.0578

. Elements which are part of the final circuit are bolded.

Figure 10: Bellman-Ford circuit at epoch 2000. The circuit 31 edges and achieves

\mathcal{L}_{\text{Mult}}=0.0565

. Elements which are part of the final circuit are bolded.

Figure 11: Train loss, test loss, and

L_{1}

regularization term for Bellman-Ford MinAggGNN trained without self-loops.

Figure 12: Bellman-Ford circuit from MinAggGNN trained without self-loops. Contains 17 of 18,240 edges. $\mathcal{L}_{\text{Mult}}=0.0599$ .

Figure 13: Multiplicative test loss, MSE test loss, and

L_{1}

regularization terms for the full Bellman-Ford network without self-loops and the Bellman-Ford circuit without self-loops. Inset shows a small inflection point in

L_{1}

norms.

Figure 14: Bellman-Ford circuit extracted from epoch 10000 of MinAggGNN training without self-loops. Contains 20 of 18,240 edges.

Panel of Figure 15 — Figure 15: Bellman-Ford circuits across four additional initializations.

Panel of Figure 16 — Figure 16: Bellman-Ford circuit generalization behavior across four additional initializations.

Panel of Figure 17 — Figure 17: Parallel Bellman-Ford and BFS circuits across four additional initializations.

Figure 18: Parameter summary for Bellman-Ford MinAggGNN ( Section 5.2 ).

Figure 19: Parameter summary for parallel Bellman-Ford and BFS MinAggGNN ( Section 5.2 ).

Figure 20: Parameter summary for Bellman Ford MinAggGNN without self-loops ( Section A.3 ).

Figure 21:

\text{Fid}^{-}

(top) and

\text{Fid}^{+}

(bottom) for SALSA-CLRS circuits using Weight, WeightGrad , EAP, and EAP-IG (

m=20

) at

K\in\{10,25,50,100,250,500,1000,1500,2000,2500\}

. For

\text{Fid}^{-}

, lower indicates a more sufficient circuit. For

\text{Fid}^{+}

, higher indicates a more necessary circuit.

Figure 22: Circuit accuracy (top) and ablated accuracy (bottom) for SALSA-CLRS circuits using Weight, WeightGrad , EAP, and EAP-IG (

m=20

) at

K\in\{10,25,50,100,250,500,1000,1500,2000,2500,3000\}

. For circuit accuracy, higher is better. For ablated accuracy, lower indicates a necessary circuit.

Figure 23: Weighted Jaccard index between CLRS circuits using WeightGrad , EAP, and EAP-IG ( $m=20$ ) at $K\in\{10,25,50,100,250,500\}$ .

Figure 24: Weighted Jaccard index between CLRS circuits using WeightGrad , EAP, and EAP-IG ( $m=20$ ) at $K\in\{1000,1500,2000,2500,3000\}$ .

Figure 25: Training graphs for the Bellman-Ford MinAggGNN from [ Nerem et al., 2025 ] .

Panel of Figure 26 — Figure 26: Example of clean and corrupted data for shortest path length prediction on a path graph.

Explore similar work

Certified Circuits: Stability Guarantees for Mechanistic Circuits
Feb 26, 2026Alaa Anani, Tobias Lorenz, Bernt Schiele +2Circuit Discovery Mechanistic Interpretability
Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany · CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning
Sep 23, 2025Alex Schutz, Victor-Alexandru Darvariu, Efimia Panagiotaki +2Graph Neural Networks Reinforcement Learning
Oxford Robotics Institute, University of Oxford · Stateful Robotics
Tracking Equivalent Mechanistic Interpretations Across Neural Networks
Mar 31, 2026Alan Sun, Mariya TonevaMechanistic Interpretability Transformer Interpretability
Carnegie Mellon University · Max Planck Institute for Software Systems

Feb 26, 2026J/K move · Enter open · S save

Certified Circuits: Stability Guarantees for Mechanistic Circuits

Alaa Anani, Tobias Lorenz, Bernt Schiele, Mario Fritz+1

Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany · CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Circuit Discovery Mechanistic Interpretability Circuits in Language Models

Open paper AskPDF arXiv

Understanding how neural networks arrive at their predictions is essential for debugging, auditing, and deployment. Mechanistic interpretability pursues this goal by identifying circuits--minimal subnetworks responsible for specific behaviors. However, existing circuit discovery methods are brittle: circuits depend strongly on the chosen concept dataset and often fail to transfer out-of-distribution, raising doubts whether they capture the concept or merely dataset-specific artifacts. We introduce Certified Circuits, which provide provable stability guarantees for circuit discovery. Our framework wraps any black-box discovery algorithm with randomized data subsampling to certify that inclusion decisions over circuit components--neurons or edges of the model graph, depending on the base algorithm--are invariant to bounded edit-distance perturbations of the concept dataset. Unstable components are abstained from, yielding circuits that are more compact and more accurate. We validate across three architectures (ResNet, ViT, GPT-2) on vision (ImageNet and four OOD datasets) and language (IOI, IOI-Hard, Greater-Than) tasks. Certified circuits achieve up to 56% higher accuracy and up to 80% fewer components, and remain reliable where baselines degrade. Certified Circuits puts circuit discovery on formal ground by producing mechanistic explanations that are provably stable and better aligned with the target concept. Code: https://github.com/AlaaAnani/certified-circuits.

Abstract

Explore similar work

Certified Circuits: Stability Guarantees for Mechanistic Circuits

Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning

Tracking Equivalent Mechanistic Interpretations Across Neural Networks