mlsanityData to 14 Oct 2026

Recurrent Aggregators in Neural Algorithmic Reasoning

arXiv 2409.07154 ↗First posted 11 Sep 2024cs.LG cs.AIcited by 6

Not on the map. Why?

Abstract (arXiv)

Neural algorithmic reasoning (NAR) is an emerging field that seeks to design neural networks that mimic classical algorithmic computations. Today, graph neural networks (GNNs) are widely used in neural algorithmic reasoners due to their message passing framework and permutation equivariance. In this extended abstract, we challenge this design choice, and replace the equivariant aggregation function with a recurrent neural network. While seemingly counter-intuitive, this approach has appropriate grounding when nodes have a natural ordering -- and this is the case frequently in established reasoning benchmarks like CLRS-30. Indeed, our recurrent NAR (RNAR) model performs very strongly on such tasks, while handling many others gracefully. A notable achievement of RNAR is its decisive state-of-the-art result on the Heapsort and Quickselect tasks, both deemed as a significant challenge for contemporary neural algorithmic reasoners -- especially the latter, where RNAR achieves a mean micro-F1 score of 87%.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 36 of its 43 references that are in the map. First posted on arXiv 11 Sep 2024.

Builds on

36 of 43 references.

References · 36

  1. 2017Inductive Representation Learning on Large Graphscited by 6,320
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,057
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2017Deep Setscited by 1,421
  6. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  7. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 222
  8. 2019What Can Neural Networks Reason About?cited by 159
  9. 2022Transformer Language Models without Positional Encodings Still Learn Positional Informationcited by 150
  10. 2019Neural Execution of Graph Algorithmscited by 121
  11. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 106
  12. 2018Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputscited by 98
24 more
  1. 2021Neural Algorithmic Reasoningcited by 94
  2. 2023Everything is Connected: Graph Neural Networkscited by 85
  3. 2021Universal Approximation of Functions on Setscited by 62
  4. 2021The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalizationcited by 62
  5. 2022A Generalist Neural Algorithmic Learnercited by 59
  6. 2023Swallowing the Bitter Pill: Simplified Scalable Conformer Generationcited by 56
  7. 2022Graph Neural Networks are Dynamic Programmerscited by 55
  8. 2020Pointer Graph Networkscited by 53
  9. 2022Relational Attention: Generalizing Transformers for Graph-Structured Taskscited by 41
  10. 2023Neural Algorithmic Reasoning with Causal Regularisationcited by 31
  11. 2022Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Taskscited by 30
  12. 2024The CLRS-Text Algorithmic Reasoning Language Benchmarkcited by 28
  13. 2021Neural Algorithmic Reasoners are Implicit Plannerscited by 21
  14. 2023Dual Algorithmic Reasoningcited by 21
  15. 2023Neural Algorithmic Reasoning for Combinatorial Optimisationcited by 19
  16. 2021Reasoning-Modulated Representationscited by 13
  17. 2022Learnable Commutative Monoids for Graph Neural Networkscited by 13
  18. 2023Asynchronous Algorithmic Alignment with Cocyclescited by 13
  19. 2024Transformers meet Neural Algorithmic Reasonerscited by 13
  20. 2024On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methodscited by 11
  21. 2024Discrete Neural Algorithmic Reasoningcited by 9
  22. 2020Adversarial Permutation Guided Node Representations for Link Predictioncited by 7
  23. 2023Parallel Algorithms Align with Neural Executioncited by 6
  24. 2022Continuous Neural Algorithmic Plannerscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 2.

6 papers.

  1. 2025Graph neural networks extrapolate out-of-distribution for shortest pathscited by 11
  2. 2025Primal-Dual Neural Algorithmic Reasoningcited by 9
  3. 2024Best of Both Worlds: Advantages of Hybrid Graph Sequence Modelscited by 6
  4. 2025KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problemscited by 1
  5. 2026FloydNet: A Learning Paradigm for Global Relational Reasoningcited by 1
  6. 2026Richer Representations for Neural Algorithmic Reasoning via Auxiliary Reconstructioncited by 0