# On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 29 references that are in the map.
- First posted on arXiv 7 Mar 2024.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [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)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [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)
- [Relational Attention: Generalizing Transformers for Graph-Structured Tasks](https://mlsanity.com/paper/2210.05062/) (2022)
- [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)
- [How to transfer algorithmic reasoning knowledge to learn new algorithms?](https://mlsanity.com/paper/2110.14056/) (2021)
- [Neural Algorithmic Reasoners are Implicit Planners](https://mlsanity.com/paper/2110.05442/) (2021)
- [Dual Algorithmic Reasoning](https://mlsanity.com/paper/2302.04496/) (2023)
- [Neural Bipartite Matching](https://mlsanity.com/paper/2005.11304/) (2020)
- [Reasoning-Modulated Representations](https://mlsanity.com/paper/2107.08881/) (2021)
- [Learning to Configure Computer Networks with Neural Algorithmic Reasoning](https://mlsanity.com/paper/2211.01980/) (2022)

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

- [The CLRS-Text Algorithmic Reasoning Language Benchmark](https://mlsanity.com/paper/2406.04229/) (2024)
- [Benchmarking ChatGPT on Algorithmic Reasoning](https://mlsanity.com/paper/2404.03441/) (2024)
- [Recurrent Aggregators in Neural Algorithmic Reasoning](https://mlsanity.com/paper/2409.07154/) (2024)
- [Neural Algorithmic Reasoning with Multiple Correct Solutions](https://mlsanity.com/paper/2409.06953/) (2024)
- [NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithms](https://mlsanity.com/paper/2410.11031/) (2024)
- [Beyond Interpolation: Extrapolative Reasoning with Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2502.04402/) (2025)
- [FloydNet: A Learning Paradigm for Global Relational Reasoning](https://mlsanity.com/paper/2601.19094/) (2026)
- [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)
- [Fitting Every Hint Is Not Enough: Premature Floods in Recurrent Algorithmic Reasoners](https://mlsanity.com/paper/2610.14982/) (2026)

## Abstract (arXiv)

Neural algorithmic reasoning is an emerging research direction that endows neural networks with the ability to mimic algorithmic executions step-by-step. A common paradigm in existing designs involves the use of historical embeddings in predicting the results of future execution steps. Our observation in this work is that such historical dependence intrinsically contradicts the Markov nature of algorithmic reasoning tasks. Based on this motivation, we present our ForgetNet, which does not use historical embeddings and thus is consistent with the Markov nature of the tasks. To address challenges in training ForgetNet at early stages, we further introduce G-ForgetNet, which uses a gating mechanism to allow for the selective integration of historical embeddings. Such an enhanced capability provides valuable computational pathways during the model's early training phase. Our extensive experiments, based on the CLRS-30 algorithmic reasoning benchmark, demonstrate that both ForgetNet and G-ForgetNet achieve better generalization capability than existing methods. Furthermore, we investigate the behavior of the gating mechanism, highlighting its degree of alignment with our intuitions and its effectiveness for robust performance.