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
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 L1 regularization term for Bellman-Ford MinAggGNN.
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 L1 regularization terms for the Bellman-Ford network and circuit.
Figure 4: MSE training loss, multiplicative test loss, reachability accuracy, and L1 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∈{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,…,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 LMult=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 LMult=0.0565 . Elements which are part of the final circuit are bolded.
Figure 11: Train loss, test loss, and L1 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. LMult=0.0599 .
Figure 13: Multiplicative test loss, MSE test loss, and L1 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 L1 norms.
Figure 14: Bellman-Ford circuit extracted from epoch 10000 of MinAggGNN training without self-loops. Contains 20 of 18,240 edges.
Figure 15: Bellman-Ford circuits across four additional initializations.
Figure 16: Bellman-Ford circuit generalization behavior across four additional initializations.
Figure 17: Parallel Bellman-Ford and BFS circuits across four additional initializations.
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: Fid− (top) and Fid+ (bottom) for SALSA-CLRS circuits using Weight, WeightGrad , EAP, and EAP-IG ( m=20 ) at K∈{10,25,50,100,250,500,1000,1500,2000,2500} . For Fid− , lower indicates a more sufficient circuit. For 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∈{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∈{10,25,50,100,250,500} .
Figure 24: Weighted Jaccard index between CLRS circuits using WeightGrad , EAP, and EAP-IG ( m=20 ) at K∈{1000,1500,2000,2500,3000} .
Figure 25: Training graphs for the Bellman-Ford MinAggGNN from [ Nerem et al., 2025 ] .
Figure 26: Example of clean and corrupted data for shortest path length prediction on a path graph.
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.
Alaa Anani, Tobias Lorenz, Bernt Schiele +2
Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany · CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Neural algorithmic reasoning (NAR) is a paradigm that trains neural networks to execute classic algorithms by supervised learning. Despite its successes, important limitations remain: inability to construct valid solutions without post-processing and to reason about multiple correct ones, poor performance on combinatorial NP-hard problems, and inapplicability to problems for which strong algorithms are not yet known. To address these limitations, we reframe the problem of learning algorithm trajectories as a Markov decision process, which imposes structure on the solution construction procedure and unlocks the powerful tools of imitation and reinforcement learning (RL). We propose the GNARL framework, encompassing the methodology to translate problem formulations from NAR to RL and a learning architecture suitable for a wide range of graph-based problems. We achieve high rates of reaching correct states on several CLRS-30 problems and performance matching or exceeding much narrower NAR approaches for NP-hard problems. Remarkably, GNARL remains applicable when no expert algorithm is available, though reward-driven learning can exhibit greater variability than direct supervision.
Alex Schutz, Victor-Alexandru Darvariu, Efimia Panagiotaki +2
Oxford Robotics Institute, University of Oxford · Stateful Robotics
Mechanistic interpretability (MI) is an emerging framework for interpreting neural networks. Given a task and model, MI aims to discover a succinct algorithmic process, an interpretation, that explains the model's decision process on that task. However, MI is difficult to scale and generalize. This stems in part from two key challenges: there is no precise notion of a valid interpretation; and, generating interpretations is often an ad hoc process. In this paper, we address these challenges by defining and studying the problem of interpretive equivalence: determining whether two different models share a common interpretation, without requiring an explicit description of what that interpretation is. At the core of our approach, we propose and formalize the principle that two interpretations of a model are equivalent if all of their possible implementations are also equivalent. We develop an algorithm to estimate interpretive equivalence and case study its use on Transformer-based models. To analyze our algorithm, we introduce necessary and sufficient conditions for interpretive equivalence based on models' representation similarity. We provide guarantees that simultaneously relate a model's algorithmic interpretations, circuits, and representations. Our framework lays a foundation for the development of more rigorous evaluation methods of MI and automated, generalizable interpretation discovery methods.
Alan Sun, Mariya Toneva
Carnegie Mellon University · Max Planck Institute for Software Systems