# Transformers meet Neural Algorithmic Reasoners

arXiv: https://arxiv.org/abs/2406.09308 · HTML: https://mlsanity.com/paper/2406.09308/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 13 Jun 2024.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 16 of 16)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Gemini: A Family of Highly Capable Multimodal Models](https://mlsanity.com/paper/2312.11805/) (2023)
- [Perceiver IO: A General Architecture for Structured Inputs & Outputs](https://mlsanity.com/paper/2107.14795/) (2021)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Teaching Algorithmic Reasoning via In-context Learning](https://mlsanity.com/paper/2211.09066/) (2022)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [Positional Description Matters for Transformers Arithmetic](https://mlsanity.com/paper/2311.14737/) (2023)
- [Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems](https://mlsanity.com/paper/2310.10603/) (2023)
- [Dual Algorithmic Reasoning](https://mlsanity.com/paper/2302.04496/) (2023)
- [Neural Algorithmic Reasoning for Combinatorial Optimisation](https://mlsanity.com/paper/2306.06064/) (2023)

## Built on by (most cited first, 13 of 13)

- [Hierarchical Reasoning Model](https://mlsanity.com/paper/2506.21734/) (2025)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Artificial Kuramoto Oscillatory Neurons](https://mlsanity.com/paper/2410.13821/) (2024)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Recurrent Aggregators in Neural Algorithmic Reasoning](https://mlsanity.com/paper/2409.07154/) (2024)
- [Can LLMs Reason Structurally? Benchmarking via the Lens of Data Structures](https://mlsanity.com/paper/2505.24069/) (2025)
- [Open-Book Neural Algorithmic Reasoning](https://mlsanity.com/paper/2501.00072/) (2024)
- [Algorithmic Language Models with Neurally Compiled Libraries](https://mlsanity.com/paper/2407.04899/) (2024)
- [NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithms](https://mlsanity.com/paper/2410.11031/) (2024)
- [Neural Algorithmic Reasoners informed Large Language Model for Multi-Agent Path Finding](https://mlsanity.com/paper/2508.17971/) (2025)
- [Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning](https://mlsanity.com/paper/2512.01113/) (2025)
- [Inductive Generalization for Robotic Manipulation](https://mlsanity.com/paper/2606.20999/) (2026)
- [A Symbolic Neural CPU for Quantization-Simulated Writeback and Interpretable Program Execution](https://mlsanity.com/paper/2607.10021/) (2026)

## Abstract (arXiv)

Transformers have revolutionized machine learning with their simple yet effective architecture. Pre-training Transformers on massive text datasets from the Internet has led to unmatched generalization for natural language understanding (NLU) tasks. However, such language models remain fragile when tasked with algorithmic forms of reasoning, where computations must be precise and robust. To address this limitation, we propose a novel approach that combines the Transformer's language understanding with the robustness of graph neural network (GNN)-based neural algorithmic reasoners (NARs). Such NARs proved effective as generic solvers for algorithmic tasks, when specified in graph form. To make their embeddings accessible to a Transformer, we propose a hybrid architecture with a two-phase training procedure, allowing the tokens in the language model to cross-attend to the node embeddings from the NAR. We evaluate our resulting TransNAR model on CLRS-Text, the text-based version of the CLRS-30 benchmark, and demonstrate significant gains over Transformer-only models for algorithmic reasoning, both in and out of distribution.