# Understanding Transformer Reasoning Capabilities via Graph Algorithms

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

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 66 of its 87 references that are in the map.
- First posted on arXiv 28 May 2024.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 30 of 66)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [PaLM 2 Technical Report](https://mlsanity.com/paper/2305.10403/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [In-Datacenter Performance Analysis of a Tensor Processing Unit](https://mlsanity.com/paper/1704.04760/) (2017)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Think before you speak: Training Language Models With Pause Tokens](https://mlsanity.com/paper/2310.02226/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)

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

- [Reasoning with Latent Thoughts: On the Power of Looped Transformers](https://mlsanity.com/paper/2502.17416/) (2025)
- [Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systems](https://mlsanity.com/paper/2504.01990/) (2025)
- [Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoning](https://mlsanity.com/paper/2406.09170/) (2024)
- [Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought](https://mlsanity.com/paper/2505.12514/) (2025)
- [A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers](https://mlsanity.com/paper/2503.03961/) (2025)
- [Text-space Graph Foundation Models: Comprehensive Benchmarks and New Insights](https://mlsanity.com/paper/2406.10727/) (2024)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Understanding Transformer from the Perspective of Associative Memory](https://mlsanity.com/paper/2505.19488/) (2025)
- [Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction](https://mlsanity.com/paper/2504.15266/) (2025)
- [The CLRS-Text Algorithmic Reasoning Language Benchmark](https://mlsanity.com/paper/2406.04229/) (2024)
- [Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation](https://mlsanity.com/paper/2502.01694/) (2025)
- [Mixture of Parrots: Experts improve memorization more than reasoning](https://mlsanity.com/paper/2410.19034/) (2024)
- [Transformers Struggle to Learn to Search](https://mlsanity.com/paper/2412.04703/) (2024)
- [A Formal Comparison Between Chain of Thought and Latent Thought](https://mlsanity.com/paper/2509.25239/) (2025)
- [Revisiting Random Walks for Learning on Graphs](https://mlsanity.com/paper/2407.01214/) (2024)
- [Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones](https://mlsanity.com/paper/2505.21825/) (2025)
- [The Serial Scaling Hypothesis](https://mlsanity.com/paper/2507.12549/) (2025)
- [GraphTeam: Facilitating Large Language Model-based Graph Analysis via Multi-Agent Collaboration](https://mlsanity.com/paper/2410.18032/) (2024)
- [Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers](https://mlsanity.com/paper/2503.01805/) (2025)
- [Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path](https://mlsanity.com/paper/2408.09529/) (2024)
- [Sequential Group Composition: A Window into the Mechanics of Deep Learning](https://mlsanity.com/paper/2602.03655/) (2026)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [Lost in Transmission: When and Why LLMs Fail to Reason Globally](https://mlsanity.com/paper/2505.08140/) (2025)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Lost-in-Distance: Impact of Contextual Proximity on LLM Performance in Graph Tasks](https://mlsanity.com/paper/2410.01985/) (2024)
- [Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent](https://mlsanity.com/paper/2504.04702/) (2025)
- [Graph-Aware Isomorphic Attention for Adaptive Dynamics in Transformers](https://mlsanity.com/paper/2501.02393/) (2025)
- [CodeGraph: Enhancing Graph Reasoning of LLMs with Code](https://mlsanity.com/paper/2408.13863/) (2024)
- [Best of Both Worlds: Advantages of Hybrid Graph Sequence Models](https://mlsanity.com/paper/2411.15671/) (2024)
- [Compositional Reasoning with Transformers, RNNs, and Chain of Thought](https://mlsanity.com/paper/2503.01544/) (2025)

## Abstract (arXiv)

Which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems? While tremendous empirical advances have been attained by transformer-based neural networks, a theoretical understanding of their algorithmic reasoning capabilities in realistic parameter regimes is lacking. We investigate this question in terms of the network's depth, width, and number of extra tokens for algorithm execution. Our novel representational hierarchy separates 9 algorithmic reasoning problems into classes solvable by transformers in different realistic parameter scaling regimes. We prove that logarithmic depth is necessary and sufficient for tasks like graph connectivity, while single-layer transformers with small embedding dimensions can solve contextual retrieval tasks. We also support our theoretical analysis with ample empirical evidence using the GraphQA benchmark. These results show that transformers excel at many graph reasoning tasks, even outperforming specialized graph neural networks.