What exactly is Neural Algorithmic Reasoning (NAR)? We propose a working definition and position NAR among neighboring fields such as differentiable programming and neural combinatorial optimization. We discuss where NAR should and should not be applied, and propose a neuralization test to help make this distinction. Furthermore, we lay out a research agenda with theoretical goals and benchmarking standards, and invite the NAR community to help shape where the field goes next.
@inproceedings{he2026neural,title={Neural Algorithmic Reasoning Must Explain When Neuralization Adds Value},author={He, Yu and Nerem, Robert R and Stoll, Timo and Cant{\"u}rk, Semih and Georgiev, Dobrik and Wittig, Solveig and Qian, Chendi and Geerts, Floris and Jegelka, Stefanie and Vitercik, Ellen and Wang, Yusu and Karalias, Nikolaos and Morris, Christopher},booktitle={3rd AI for Math Workshop: Toward Self-Evolving Scientific Agents},year={2026},url={https://openreview.net/forum?id=A4FI5tZRT4},}
LLM
Can LLMs Reason Structurally? Benchmarking via the lens of Data Structures
Yu He*, Yingxi Li*, Colin White, Ellen Vitercik
International Conference on Machine Learning (ICML) 2026
Structural reasoning—the ability to understand and manipulate relationships—underpins many problem-solving processes. For example, when planning a trip, an LLM needs to reason about connectivity between places, rank priorities, and work out temporal relationships. We propose DSR-Bench, a benchmark for evaluating such abilities through synthetic data structure tasks, providing deterministic verification, automated evaluation, and fine-grained insights into which types of relationships LLMs struggle with.
@inproceedings{he2026can,title={Can {LLM}s Reason Structurally? Benchmarking via the lens of Data Structures},author={He, Yu and Li, Yingxi and White, Colin and Vitercik, Ellen},booktitle={Forty-third International Conference on Machine Learning},year={2026},url={https://openreview.net/forum?id=kChzpoYFef},}
2025
NAR
Primal-Dual Neural Algorithmic Reasoning
Yu He and Ellen Vitercik
International Conference on Machine Learning (ICML) 2025
Neural Algorithmic Reasoning (NAR) teaches neural networks to simulate classical algorithms, applying algorithmic thinking to real-world data. However, prior work has mostly focused on algorithms for polynomial-time-solvable problems, while many real-world problems are NP-hard. We propose PDNAR, a general NAR framework for NP-hard problems based on primal-dual approximation algorithms, demonstrating strong size and OOD generalization.
@inproceedings{he2025primaldual,title={Primal-Dual Neural Algorithmic Reasoning},author={He, Yu and Vitercik, Ellen},booktitle={Forty-second International Conference on Machine Learning},year={2025},url={https://openreview.net/forum?id=iBpkzB5LEr},}
GNN
Overcoming Information Bottlenecks in Directed Graph Neural Networks through Rewiring
Message passing in GNNs is known to be limited by long-range dependencies and oversquashing. We propose two rewiring strategies based on shortcut sets and edge connectivity to tackle these challenges, respectively.
@inproceedings{he2025overcoming,title={Overcoming Information Bottlenecks in Directed Graph Neural Networks through Rewiring},author={He, Yu and Karmarkar, Ishani and Vitercik, Ellen},booktitle={The Fourth Learning on Graphs Conference},year={2025},url={https://openreview.net/forum?id=cuI1BeP8QP},}
2024
NAR
Deep Equilibrium Models For Algorithmic Reasoning
Sophie Xhonneux, Yu He, Andreea Deac, Jian Tang, Gauthier Gidel
Most neural algorithmic reasoning models use a fixed number of steps or a termination network to predict when to stop. Ideally, the model should learn to stop upon reaching a fixed-point equilibrium. We explore this idea using deep equilibrium models and discuss several challenges that arise along the way.
@inproceedings{xhonneux2024deep,title={Deep Equilibrium Models For Algorithmic Reasoning},author={Xhonneux, Sophie and He, Yu and Deac, Andreea and Tang, Jian and Gidel, Gauthier},booktitle={The Third Blogpost Track at International Conference on Learning Representations (ICLR)},year={2024},url={https://openreview.net/forum?id=diagbK14G5},}
2023
GNN
Higher-Order Expander Graph Propagation
Thomas Christie* and Yu He*
NeurIPS 2023: New Frontiers in Graph Learning Workshop
Expander graphs are highly connected sparse graphs with low diameters, making them an ideal template for message passing in GNNs. To tackle oversquashing in higher-order interactions, we introduce higher-order expander graph propagation, a rewiring strategy based on bipartite expanders.
@inproceedings{christie2023higherorder,title={Higher-Order Expander Graph Propagation},author={Christie, Thomas and He, Yu},booktitle={NeurIPS 2023 Workshop: New Frontiers in Graph Learning},year={2023},url={https://openreview.net/forum?id=0lZjoxTZFb},}
GNN
Sheaf-based Positional Encodings for Graph Neural Networks
Yu He, Cristian Bodnar, and Pietro Liò
NeurIPS 2023: Symmetry and Geometry in Neural Representations Workshop
Positional encodings are essential for graph transformers and for disambiguating local neighborhoods in GNNs. We propose a novel set of positional encodings based on sheaf theory. The sheaf Laplacian can be learned from node features, allowing it to encode both structural and semantic information.
@inproceedings{he2023sheafbased,title={Sheaf-based Positional Encodings for Graph Neural Networks},author={He, Yu and Bodnar, Cristian and Liò, Pietro},booktitle={NeurIPS 2023 Workshop on Symmetry and Geometry in Neural Representations},year={2023},url={https://openreview.net/forum?id=ZtAabWUPu3},}
We extend XLVIN, which leverages a graph neural network to simulate the value iteration algorithm in deep reinforcement learning, from control tasks with discrete action spaces to continuous action spaces. We introduce several selective expansion policies to efficiently handle the resulting large planning graphs.
@inproceedings{he2020cnap,title={Continuous Neural Algorithmic Planners},author={He, Yu and Veličković, Petar and Liò, Pietro and Deac, Andreea},booktitle={Proceedings of the First Learning on Graphs Conference},pages={54:1--54:13},year={2022},editor={Rieck, Bastian and Pascanu, Razvan},volume={198},series={Proceedings of Machine Learning Research},month={09--12 Dec},publisher={PMLR},url={https://proceedings.mlr.press/v198/he22a.html},}
2018
Earlier
Algorithm Selection for Classification Problems via Cluster-based Meta-features
Daren Ler, Hongyu Teng, Yu He, Rahul Gidijala
In 2018 IEEE International Conference on Big Data (Big Data), 2018
@inproceedings{8621982,author={Ler, Daren and Teng, Hongyu and He, Yu and Gidijala, Rahul},booktitle={2018 IEEE International Conference on Big Data (Big Data)},title={Algorithm Selection for Classification Problems via Cluster-based Meta-features},year={2018},pages={4952-4960},doi={10.1109/BigData.2018.8621982},}
Algorithm Selection for Classification Problems via Cluster-based Meta-featuresIn 2018 IEEE International Conference on Big Data (Big Data), 2018