MINAR: Mechanistic Interpretability for Neural Algorithmic Reasoning

Jesse He, Helen Jenne, Max Vargas, Davis Brown, Gal Mishne, Yusu Wang, Henry Kvinge · 2026

Read MINAR: Mechanistic Interpretability for Neural Algorithmic Reasoning by Jesse He, Helen Jenne, Max Vargas, Davis Brown, Gal Mishne, Yusu Wang, Henry Kvinge (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-21442.txt.

Introduction

Jesse He and six co-authors introduce MINAR, a toolbox for mechanistic interpretability in neural algorithmic reasoning. That young field studies how graph neural networks emulate classical algorithms like Bellman-Ford, a match called algorithmic alignment. Meanwhile, mechanistic interpretability seeks the small circuits inside models that perform specific computations.

MINAR adapts attribution patching methods from language-model interpretability to the graph-network setting for efficient circuit discovery. Two case studies show it recovers faithful neuron-level circuits from networks trained on algorithmic tasks. The study also shows how circuits form and prune during training, and how networks trained on several tasks at once reuse circuit parts for related tasks. Code is public.

Catalog record

CREATORJesse He, Helen Jenne, Max Vargas, Davis Brown, Gal Mishne, Yusu Wang, Henry Kvinge
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-21442

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

MINAR: Mechanistic Interpretability for Neural Algorithmic Reasoning Jesse He, Helen Jenne, Max Vargas, Davis Brown, Gal Mishne, Yusu Wang, Henry Kvinge 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 M echanistic I nterpretability for N eural A lgorithmic R easoning (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 . 1 Introduction The recent surge in the capabilities of large language models (LLMs) has created a commensurate demand for novel interpretability methods suited to rigorous analysis of these models. At the same time, the discovery of phenomena like grokking ( 38 ) has shown that rich algorithmic structure can arise via standard training methods. This confluence of interests has led to the emergence of mechanistic interpretability ( 33 ) , which attempts to explain model behavior using specific subsets of a model’s internal computation. In several striking cases ( 45 ; 24 ) this has allowed researchers to reduce seemingly complex behaviors to an interpretable sequence of mathematical operations. At the same time, researchers have noticed that graph neural networks (GNNs) are capable of implementing classical algorithms as a result of the similarity between their message-passing structure and dynamic programming. This notion of “algorithmic alignment” ( 47 ) or “neural algorithmic reasoning” ( 44 ) , promises robust out-of-distribution generalization and substantial improvements in sample complexity. With an interest in discovering how models perform algorithmic tasks on the one hand, and a class of models (GNNs) that are known to naturally implement traditional algorithms on the other, neural algorithmic reasoning creates a natural testbed for fine-grained mechanistic interpretability research. In this work, we introduce M echanistic I nterpretability for N eural A lgorithmic R easoning (MINAR). To our knowledge, MINAR is the first attempt to apply automated circuit discovery to the GNN setting. Through two case studies, we demonstrate how MINAR enables a detailed study of neural algorithmic reasoning models. Our contributions are as follows: 1. Building on prior work in mechanistic interpretability, we develop an efficient approach for identifying end-to-end neuron-level circuits in GNNs ( Section 4 ). 2. Applied to a GNN trained to predict single-source shortest path distances, we show that MINAR extracts a minimal circuit that captures the model’s implementation of the Bellman-Ford algorithm ( Section 5.2 ). (a) MINAR also reveals a delayed pruning effect, where the optimal circuit appears to be pruned from a larger circuit long after a generalizable model has been obtained. ( Section 5.3 ). (b) MINAR exposes shortcut learning in a network trained to perform Bellman-Ford and breadth-first search (BFS) in parallel ( Section 5.4 ). 3. We study a GNN trained to perform seven tasks from the CLRS-30 benchmark ( 43 ) in parallel. Here, MINAR showcases how the model leverages the same circuit components to perform related tasks ( Section 6 ). 2 Related Work Circuit Discovery and Mechanistic Interpretability Early mechanistic interpretability work, e.g., ( 33 ; 52 ) , combines manual examination of parameters with expert hypotheses to reverse-engineer the inner workings of a narrow trained model. However, the rise in language model capabilities has created an interest in applying such methods to much larger models, focusing on methods to partially or fully automate much of the mechanistic interpretability process. In particular, researchers have identified “circuits” that perform specific subtasks ( 35 ) , and the process of identifying circuits is known as circuit discovery . A number of approaches for circuit discovery have been proposed, such as attribution patching ( 42 ; 18 ; 51 ) or pruning ( 6 ; 8 ; 50 ) . These methods formulate the model as a computation graph and attempt to find small subgraphs responsible for a particular behavior. To date, much of the circuit discovery literature has been focused on sub-tasks for language models such as indirect object identification ( 45 ) , and has identified coarse-grained circuits whose nodes are entire attention heads or MLP modules. Algorithmic Alignment in Graph Neural Networks While mechanistic interpretability has revealed surprising structure in large generalist models, a different class of narrow models has also been shown to possess algorithmic “reasoning” capabilities: graph neural networks (GNNs). Broadly, GNNs operate via an iterative message-passing scheme: each node in the graph maintains an embedding, and iteratively aggregates the embeddings of its neighbors to update its own embedding. 47 and 13 point out that this aggregate-and-update flow resembles dynamic programming, hypothesizing that this algorithmic alignment of GNNs affords them an advantage in learning algorithmic tasks where more ad hoc approaches might fail. For example, learning reachability via BFS and shortest paths via Bellman-Ford in parallel can help GNNs generalize on both tasks ( 44 ) . 43 later introduced the CLRS-30 benchmark to demonstrate this parallel reasoning ability across 30 algorithmic tasks inspired by the classic textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein ( 9 ) . However, it was only recently that 34 showed that GNNs are not only capable of learning specific algorithms, but that a properly designed GNN will provably learn a specific algorithm (in their case Bellman-Ford) when trained with sparsity regularization. 3 Preliminaries Let \Phi be a GNN operating on an attributed graph G=(V,E,X,A) , where V is the node set, E is the edge set, X:V\to\mathbb{R}^{p} are the node features and A:E\to\mathbb{R}^{q} are edge attributes. We briefly recall the message-passing scheme that underlies most popular GNNs. A GNN \Phi of depth L maintains an embedding \Phi^{(\ell)}_{v} for each node v\in V and \ell=0,\dots,L , with layer 0 being the input node features \Phi^{(0)}_{v}=X_{v} . In each layer, \Phi^{(\ell)}_{v} is updated according to the features of its 1-hop neighborhood \mathcal{N}(v) : \Phi^{(\ell+1)}_{v}=f^{(\ell)}_{\Up}\left(\Phi^{(\ell)}_{v},\bigoplus_{u\in\mathcal{N}(v)}f^{(\ell)}_{\Agg}(\Phi^{(\ell)}_{u},A_{(u,v)})\right) (1) where f^{(\ell)}_{\Agg} and f^{(\ell)}_{\Up} are any functions and \bigoplus denotes any permutation-invariant operation such as sum, mean, minimum, or maximum. We may denote the output of \Phi at node v by \Phi_{v} or \Phi_{v}(G) , if the input graph is ambiguous. Fundamental to circuit discovery is the computation graph , which represents the connections between individual model components ( 35 ; 42 ; 51 ) 1 1 1 In GNN literature, some authors ( 48 ; 49 ; 19 ) use “computation graph” to refer to a GNN’s layered message-passing, but in this paper “computation graph” will always refer to the model computation graph. . These components are typically defined at an architectural level, representing modules like attention heads or MLPs. Here, we will denote by \Psi an arbitrary (perhaps non-graph) neural network.

Read the complete text