mlsanityData to 14 Oct 2026

Simulation of Graph Algorithms with Looped Transformers

arXiv 2402.01107 ↗First posted 2 Feb 2024cs.LG cs.AI cs.DScited by 30

Not on the map. Why?

Abstract (arXiv)

The execution of graph algorithms using neural networks has recently attracted significant interest due to promising empirical progress. This motivates further understanding of how neural networks can replicate reasoning steps with relational data. In this work, we study the ability of transformer networks to simulate algorithms on graphs from a theoretical perspective. The architecture we use is a looped transformer with extra attention heads that interact with the graph. We prove by construction that this architecture can simulate individual algorithms such as Dijkstra's shortest path, Breadth- and Depth-First Search, and Kosaraju's strongly connected components, as well as multiple algorithms simultaneously. The number of parameters in the networks does not increase with the input graph size, which implies that the networks can simulate the above algorithms for any graph. Despite this property, we show a limit to simulation in our solution due to finite precision. Finally, we show a Turing Completeness result with constant width when the extra attention heads are utilized.

Key facts. Cited by 30 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 2 Feb 2024.

Builds on

34 of 44 references.

References · 34

  1. 2017Attention Is All You Needcited by 60,361
  2. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  4. 2017Graph Attention Networkscited by 8,923
  5. 2022Emergent Abilities of Large Language Modelscited by 2,512
  6. 2021Transformers in Vision: A Surveycited by 1,013
  7. 2023Scaling Vision Transformers to 22 Billion Parameterscited by 694
  8. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
  9. 2014Neural Turing Machinescited by 644
  10. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  11. 2022Transformers Learn Shortcuts to Automatacited by 268
  12. 2020Sparse Sinkhorn Attentioncited by 251
22 more
  1. 2021Incorporating Convolution Designs into Visual Transformerscited by 248
  2. 2023Looped Transformers as Programmable Computerscited by 237
  3. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  4. 2019What Can Neural Networks Reason About?cited by 159
  5. 2023Teaching Arithmetic to Small Transformerscited by 123
  6. 2015Neural GPUs Learn Algorithmscited by 121
  7. 2019Neural Execution of Graph Algorithmscited by 121
  8. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 106
  9. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 104
  10. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  11. 2015Neural Programmer-Interpreterscited by 101
  12. 2021Neural Algorithmic Reasoningcited by 94
  13. 2022A Generalist Neural Algorithmic Learnercited by 59
  14. 2022Graph Neural Networks are Dynamic Programmerscited by 55
  15. 2022Relational Attention: Generalizing Transformers for Graph-Structured Taskscited by 41
  16. 2023Learning Transformer Programscited by 41
  17. 2020Neural Execution Engines: Learning to Execute Subroutinescited by 36
  18. 2023Neural Algorithmic Reasoning with Causal Regularisationcited by 31
  19. 2023Dual Algorithmic Reasoningcited by 21
  20. 2023Neural Algorithmic Reasoning for Combinatorial Optimisationcited by 19
  21. 2023Neural Algorithmic Reasoning Without Intermediate Supervisioncited by 17
  22. 2023Parallel Algorithms Align with Neural Executioncited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 9; 2025: 10; 2026: 11.

30 papers.

Sort:

By area:

  1. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 240
  2. 2025A Survey on Latent Reasoningcited by 81
  3. 2024Transformers Can Do Arithmetic with the Right Embeddingscited by 78
  4. 2026LoopFormer: Elastic-Depth Looped Transformers for Latent Reasoning via Shortcut Modulationcited by 61
  5. 2024On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encodingcited by 36
  6. 2024How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehensioncited by 30
  7. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 22
  8. 2025A Formal Comparison Between Chain of Thought and Latent Thoughtcited by 15
  9. 2026Training-Free Looped Transformerscited by 15
  10. 2024Revisiting Random Walks for Learning on Graphscited by 13
  11. 2024Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Pathcited by 10
  12. 2024Discrete Neural Algorithmic Reasoningcited by 9
18 more
  1. 2025Primal-Dual Neural Algorithmic Reasoningcited by 9
  2. 2024Benchmarking ChatGPT on Algorithmic Reasoningcited by 8
  3. 2026Loop the Loopies!cited by 8
  4. 2025Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteriacited by 5
  5. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 4
  6. 2025Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networkscited by 4
  7. 2025Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspectivecited by 4
  8. 2026Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separationcited by 2
  9. 2025Efficiently Learning Branching Networks for Multitask Algorithmic Reasoningcited by 1
  10. 2026Beyond Test-Time Memory: State-Space Optimal Control for LLM Reasoningcited by 1
  11. 2024Algorithm-Informed Graph Neural Networks for Leakage Detection and Localization in Water Distribution Networkscited by 0
  12. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0
  13. 2026Beyond What Seems Necessary: Hidden Gains from Scaling Training-Time Reasoning Length under Outcome Supervisioncited by 0
  14. 2026Learning to Approximate Uniform Facility Location via Graph Neural Networkscited by 0
  15. 2026UltRAG: a Universal Simple Scalable Recipe for Knowledge Graph RAGcited by 0
  16. 2026Loom: A Scalable Analytical Neural Computer Architecturecited by 0
  17. 2026Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Managementcited by 0
  18. 2026Learning to Extrapolate in Depth with Looped Transformerscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithms
  2. 2026Which Algorithms Can Graph Neural Networks Learn?
  3. 2026Stability and Generalization in Looped Transformers
  4. 2024Transformers Struggle to Learn to Search
  5. 2024Reasoning Algorithmically in Graph Neural Networks
  6. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization
  7. 2026Shared Weights, Selected Computations: How Looped Transformers Route What Each Loop Does
  8. 2024Are Large-Language Models Graph Algorithmic Reasoners?