# Neural Algorithmic Reasoning with Multiple Correct Solutions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 12 references that are in the map.
- First posted on arXiv 11 Sep 2024.

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

- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [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)
- [Neural Algorithmic Reasoning with Causal Regularisation](https://mlsanity.com/paper/2302.10258/) (2023)
- [Neural Algorithmic Reasoning for Combinatorial Optimisation](https://mlsanity.com/paper/2306.06064/) (2023)
- [Neural Algorithmic Reasoning Without Intermediate Supervision](https://mlsanity.com/paper/2306.13411/) (2023)
- [SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning](https://mlsanity.com/paper/2309.12253/) (2023)
- [On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods](https://mlsanity.com/paper/2403.04929/) (2024)

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

- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithms](https://mlsanity.com/paper/2410.11031/) (2024)
- [Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning](https://mlsanity.com/paper/2509.18930/) (2025)
- [FlowBalance: Verifier-Grounded Self-Improvement from On-Policy Reasoning Experience](https://mlsanity.com/paper/2609.03241/) (2026)

## Abstract (arXiv)

Neural Algorithmic Reasoning (NAR) extends classical algorithms to higher dimensional data. However, canonical implementations of NAR train neural networks to return only a single solution, even when there are multiple correct solutions to a problem, such as single-source shortest paths. For some applications, it is desirable to recover more than one correct solution. To that end, we give the first method for NAR with multiple solutions. We demonstrate our method on two classical algorithms: Bellman-Ford (BF) and Depth-First Search (DFS), favouring deeper insight into two algorithms over a broader survey of algorithms. This method involves generating appropriate training data as well as sampling and validating solutions from model output. Each step of our method, which can serve as a framework for neural algorithmic reasoning beyond the tasks presented in this paper, might be of independent interest to the field and our results represent the first attempt at this task in the NAR literature.