# Simulation of Graph Algorithms with Looped Transformers

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

## 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 (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Transformers in Vision: A Survey](https://mlsanity.com/paper/2101.01169/) (2021)
- [Scaling Vision Transformers to 22 Billion Parameters](https://mlsanity.com/paper/2302.05442/) (2023)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [Incorporating Convolution Designs into Visual Transformers](https://mlsanity.com/paper/2103.11816/) (2021)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [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)
- [Tracr: Compiled Transformers as a Laboratory for Interpretability](https://mlsanity.com/paper/2301.05062/) (2023)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [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)
- [Relational Attention: Generalizing Transformers for Graph-Structured Tasks](https://mlsanity.com/paper/2210.05062/) (2022)
- [Learning Transformer Programs](https://mlsanity.com/paper/2306.01128/) (2023)
- [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)

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

- [Reasoning with Latent Thoughts: On the Power of Looped Transformers](https://mlsanity.com/paper/2502.17416/) (2025)
- [A Survey on Latent Reasoning](https://mlsanity.com/paper/2507.06203/) (2025)
- [Transformers Can Do Arithmetic with the Right Embeddings](https://mlsanity.com/paper/2405.17399/) (2024)
- [LoopFormer: Elastic-Depth Looped Transformers for Latent Reasoning via Shortcut Modulation](https://mlsanity.com/paper/2602.11451/) (2026)
- [On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encoding](https://mlsanity.com/paper/2410.01405/) (2024)
- [How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension](https://mlsanity.com/paper/2410.05298/) (2024)
- [Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent](https://mlsanity.com/paper/2410.11268/) (2024)
- [A Formal Comparison Between Chain of Thought and Latent Thought](https://mlsanity.com/paper/2509.25239/) (2025)
- [Training-Free Looped Transformers](https://mlsanity.com/paper/2605.23872/) (2026)
- [Revisiting Random Walks for Learning on Graphs](https://mlsanity.com/paper/2407.01214/) (2024)
- [Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path](https://mlsanity.com/paper/2408.09529/) (2024)
- [Discrete Neural Algorithmic Reasoning](https://mlsanity.com/paper/2402.11628/) (2024)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Benchmarking ChatGPT on Algorithmic Reasoning](https://mlsanity.com/paper/2404.03441/) (2024)
- [Loop the Loopies!](https://mlsanity.com/paper/2607.16051/) (2026)
- [Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria](https://mlsanity.com/paper/2508.07102/) (2025)
- [Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers](https://mlsanity.com/paper/2501.10688/) (2025)
- [Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks](https://mlsanity.com/paper/2502.16763/) (2025)
- [Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective](https://mlsanity.com/paper/2509.22613/) (2025)
- [Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separation](https://mlsanity.com/paper/2605.30757/) (2026)
- [Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning](https://mlsanity.com/paper/2512.01113/) (2025)
- [Beyond Test-Time Memory: State-Space Optimal Control for LLM Reasoning](https://mlsanity.com/paper/2603.09221/) (2026)
- [Algorithm-Informed Graph Neural Networks for Leakage Detection and Localization in Water Distribution Networks](https://mlsanity.com/paper/2408.02797/) (2024)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)
- [Beyond What Seems Necessary: Hidden Gains from Scaling Training-Time Reasoning Length under Outcome Supervision](https://mlsanity.com/paper/2602.00927/) (2026)
- [Learning to Approximate Uniform Facility Location via Graph Neural Networks](https://mlsanity.com/paper/2602.13155/) (2026)
- [UltRAG: a Universal Simple Scalable Recipe for Knowledge Graph RAG](https://mlsanity.com/paper/2603.28773/) (2026)
- [Loom: A Scalable Analytical Neural Computer Architecture](https://mlsanity.com/paper/2604.08816/) (2026)
- [Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management](https://mlsanity.com/paper/2605.19514/) (2026)
- [Learning to Extrapolate in Depth with Looped Transformers](https://mlsanity.com/paper/2610.14456/) (2026)

## 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.