From Shortcut Learning to Discrete Neural Insertion Sort

Konstantinos Mylonas; Thrasyvoulos Spyropoulos

cs.LGSep 25, 2026

From Shortcut Learning to Discrete Neural Insertion Sort

Authors: Konstantinos Mylonas, Thrasyvoulos Spyropoulos

Abstract

Neural algorithmic reasoning aims to train neural networks to follow known algorithms and generalize beyond the input sizes seen during training. However, correct final outputs and intermediate supervision do not necessarily show that a model follows the intended execution. We study this problem using insertion sort. Our analysis of the CLRS30 baseline NAR shows that the hint objective is weakly optimized and that hint accuracy remains low. Moreover, many intermediate representations can already be decoded into sorted sequences before the reference insertion-sort execution terminates, suggesting that the model learns a shortcut to the final output. Motivated by these findings, we introduce Discrete Neural Insertion Sort. Our model represents the sequence as a chain, separates scalar exchanges from control-state transitions, and projects node representations back to discrete states after every processor step. When trained only on sequences of length 16, the model achieves $100\%$ sorted-sequence accuracy on sequences of length 64 and 128. However, an ablation shows that discretization and graph structure alone are insufficient: without additional supervision of the global inner-loop state, the model fails even at the training length. Our results show that discrete execution can support strong length generalization, while also highlighting the problem-specific inductive bias required to learn a faithful algorithmic execution.

Figures & tables

Figure 1: One inner-loop execution of insertion sort. The outer-loop index $j$ remains fixed at position 4 while $k$ tracks the value being inserted and $i$ identifies the element immediately to its left. Each successful comparison swaps the adjacent values and moves $i$ and $k$ one position to the left. The final comparison does not require a swap, so the inner loop terminates. The shaded node at position 5 has not yet been processed in panels (a)–(c). Panel (d) advances $j$ to this node and initializes $k=j$ and $i=j-1$ , leaving the executor ready to begin the next inner loop.

Figure 2: Output, hint, and total training losses for the CLRS insertion-sort baseline over 1,000 optimization steps. The output loss decreases substantially, whereas the hint loss remains high and strongly oscillatory. The hint component therefore does not exhibit the same sustained optimization as the final-output objective.

Figure 3: Average accuracy of a representative hint prediction at each of the 15 predicted transitions in a length-16 insertion-sort trajectory. The low accuracy provides further evidence that the model does not reliably follow the intermediate hint supervision.

Figure 4: Early-solution diagnostic on 64 sequences of length 16. Panel (a) reports, at each intermediate processor step, how many baseline representations decode to a fully sorted sequence when passed through the final-output decoder. Panel (b) reports the step at which the corresponding reference insertion-sort trajectories actually finish. Thirteen baseline decodes are already sorted at step 3 and 32 are sorted at step 4, although none of the reference trajectories finish before step 14. Reference completion is concentrated at the final two steps: 5 sequences finish at step 14 and 59 at step 15.

State	Code	Meaning
$i$	$1000$	The left element in the current inner-loop comparison.
$j$	$0100$	The current outer-loop element.
$\mathrm{next}\_j$	$0010$	The node that becomes $j$ after the current inner loop terminates.
$k$	$0001$	The right element in the current inner-loop comparison.
$j\land k$	$0101$	The outer-loop element at the first step of its inner loop, when the roles of $j$ and $k$ coincide.
nothing	$0000$	A node with no active control role at the current step.

Table 1: Discrete node states used by the insertion-sort executor.

Figure 5: Discretization step: At timestep $t$ , node $B$ is in state $i$ . After message passing his updated embedding $\tilde{h}_{B}^{t+1}$ is passed through 4 linear layers to produce the new discrete state.

Figure 6: One inner-loop execution of the proposed discrete neural insertion-sort model. Each row is one processor step. In the first phase, the directed edges of the chain act as nodes in a virtual graph. The v-node aggregates their representations and must identify the two task-relevant directed edges between the active

i

and

k

nodes. The edge comparison bits

c

help the v-node to decide if the inner loop is terminated and populate its embedding accordingly. In the second phase, the v-node broadcasts its embedding to every sequence node. Each node combines this graph-level context with local chain messages, and four binary state logits discretize the result. Steps 1 and 2 swap adjacent scalars and move

i

and

k

left. Step 3 produces no scalar change; the v-node communicates this global outcome, allowing the discrete transition to terminate the current inner loop and initialize the next one with

j=k=5

and

i=4

. Faint routes are available to the model, while red routes mark the task-relevant edge messages the v-node is intended to identify.

Sequence length	State	Scalar	Sorted
16	$100\%$	$100\%$	$100\%$
64	$100\%$	$100\%$	$100\%$
128	$100\%$	$100\%$	$100\%$

Table 2: Performance across different sequence lengths. The model is trained only on sequences of length 16 and evaluated autoregressively without additional training or fine-tuning.

Model	$n=16$	$n=64$	$n=128$
Without v-node supervision	$0\%$	$0\%$	$0\%$
With v-node supervision	$100\%$	$100\%$	$100\%$

Table 3: Effect of supervising the virtual node. Both variants use the same architecture and receive supervision on the discrete states and scalar updates. We report the sorted sequence accuracy.

Algorithmic Generalization

See all 18 papers

MINAR: Mechanistic Interpretability for Neural Algorithmic Reasoning
Feb 24, 2026Jesse He, Helen Jenne, Max Vargas +4Neural Algorithmic Reasoning Mechanistic Interpretability
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 +1
Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning
Nov 30, 2025Dongyue Li, Zhenshuo Zhang, Minxuan Duan +2Neural Algorithmic Reasoning Multi-Task Learning
†Northeastern University, Boston, Massachusetts · ‡University of Pennsylvania, Philadelphia, Pennsylvania
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

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

MINAR: Mechanistic Interpretability for Neural Algorithmic Reasoning

Jesse He, Helen Jenne, Max Vargas, Davis Brown+3

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+1

Neural Algorithmic Reasoning Mechanistic Interpretability GNN Explainability Graph Neural Networks Activation Patching

Open paper AskPDF arXiv

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.

Abstract

Algorithmic Generalization

Explore similar work

MINAR: Mechanistic Interpretability for Neural Algorithmic Reasoning

Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning

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