# Discrete Neural Algorithmic Reasoning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 44 references that are in the map.
- First posted on arXiv 18 Feb 2024.

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Learning to Execute](https://mlsanity.com/paper/1410.4615/) (2014)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Tracr: Compiled Transformers as a Laboratory for Interpretability](https://mlsanity.com/paper/2301.05062/) (2023)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Pointer Graph Networks](https://mlsanity.com/paper/2006.06380/) (2020)
- [Relational inductive bias for physical construction in humans and machines](https://mlsanity.com/paper/1806.01203/) (2018)
- [Learning Transformer Programs](https://mlsanity.com/paper/2306.01128/) (2023)
- [Neural Execution Engines: Learning to Execute Subroutines](https://mlsanity.com/paper/2006.08084/) (2020)
- [Neural Algorithmic Reasoning with Causal Regularisation](https://mlsanity.com/paper/2302.10258/) (2023)
- [Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks](https://mlsanity.com/paper/2211.00692/) (2022)
- [Simulation of Graph Algorithms with Looped Transformers](https://mlsanity.com/paper/2402.01107/) (2024)
- [How to transfer algorithmic reasoning knowledge to learn new algorithms?](https://mlsanity.com/paper/2110.14056/) (2021)
- [Dual Algorithmic Reasoning](https://mlsanity.com/paper/2302.04496/) (2023)
- [Neural Algorithmic Reasoning Without Intermediate Supervision](https://mlsanity.com/paper/2306.13411/) (2023)
- [Algorithmic Concept-based Explainable Reasoning](https://mlsanity.com/paper/2107.07493/) (2021)
- [SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning](https://mlsanity.com/paper/2309.12253/) (2023)

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

- [Transformers Can Do Arithmetic with the Right Embeddings](https://mlsanity.com/paper/2405.17399/) (2024)
- [Recurrent Aggregators in Neural Algorithmic Reasoning](https://mlsanity.com/paper/2409.07154/) (2024)
- [NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithms](https://mlsanity.com/paper/2410.11031/) (2024)
- [KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems](https://mlsanity.com/paper/2509.15239/) (2025)
- [From Shortcut Learning to Discrete Neural Insertion Sort](https://mlsanity.com/paper/2609.31114/) (2026)
- [Algorithm-Informed Graph Neural Networks for Leakage Detection and Localization in Water Distribution Networks](https://mlsanity.com/paper/2408.02797/) (2024)
- [Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning](https://mlsanity.com/paper/2509.18930/) (2025)
- [THEIA: Learning Complete Kleene Three-Valued Logic in a Pure-Neural Modular Architecture](https://mlsanity.com/paper/2604.11284/) (2026)
- [Fitting Every Hint Is Not Enough: Premature Floods in Recurrent Algorithmic Reasoners](https://mlsanity.com/paper/2610.14982/) (2026)

## Abstract (arXiv)

Neural algorithmic reasoning aims to capture computations with neural networks by training models to imitate the execution of classical algorithms. While common architectures are expressive enough to contain the correct model in the weight space, current neural reasoners struggle to generalize well on out-of-distribution data. On the other hand, classical computations are not affected by distributional shifts as they can be described as transitions between discrete computational states. In this work, we propose to force neural reasoners to maintain the execution trajectory as a combination of finite predefined states. To achieve this, we separate discrete and continuous data flows and describe the interaction between them. Trained with supervision on the algorithm's state transitions, such models are able to perfectly align with the original algorithm. To show this, we evaluate our approach on multiple algorithmic problems and achieve perfect test scores both in single-task and multitask setups. Moreover, the proposed architectural choice allows us to prove the correctness of the learned algorithms for any test data.