mlsanityData to 7 Oct 2026

Understanding Transformer Reasoning Capabilities via Graph Algorithms

arXiv 2405.18512 ↗First posted 28 May 2024cs.LG cs.AIcited by 64

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

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.

Key facts. Cited by 64 papers in the map (data through 7 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.

Builds on

66 of 87 references.

Closest ancestors · 5

Same direction, newest first

  1. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Models24 Apr
  2. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Models18 Aug
  3. 2022A Logic for Expressing Log-Precision Transformers6 Oct
  4. 2022Large Language Models are Zero-Shot Reasoners24 May
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 61

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  5. 2023GPT-4 Technical Reportcited by 18,132
  6. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  7. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  8. 2021Swin Transformer: Hierarchical Vision Transformer using Shifted Windowscited by 12,082
  9. 2020Scaling Laws for Neural Language Modelscited by 6,411
  10. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  11. 2018How Powerful are Graph Neural Networks?cited by 4,355
  12. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
38 more
  1. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,175
  2. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  3. 2022Training Compute-Optimal Large Language Modelscited by 2,927
  4. 2020GLU Variants Improve Transformercited by 1,724
  5. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  6. 2023PaLM 2 Technical Reportcited by 1,154
  7. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  8. 2020A Generalization of Transformer Networks to Graphscited by 653
  9. 2014Neural Turing Machinescited by 630
  10. 2017In-Datacenter Performance Analysis of a Tensor Processing Unitcited by 610
  11. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  12. 2022Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoningcited by 331
  13. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  14. 2023Think before you speak: Training Language Models With Pause Tokenscited by 254
  15. 2023Can Language Models Solve Graph Problems in Natural Language?cited by 249
  16. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  17. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  18. 2023Large Language Models on Graphs: A Comprehensive Surveycited by 190
  19. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  20. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 175
  21. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
  22. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  23. 2023Representational Strengths and Limitations of Transformerscited by 132
  24. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  25. 2023Teaching Arithmetic to Small Transformerscited by 121
  26. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  27. 2015Neural GPUs Learn Algorithmscited by 118
  28. 2024Let Your Graph Do the Talking: Encoding Structured Data for LLMscited by 112
  29. 2022Teaching Algorithmic Reasoning via In-context Learningcited by 111
  30. 2022Transformer for Graphs: An Overview from Architecture Perspectivecited by 107
  31. 2014Learning to Executecited by 105
  32. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
  33. 2023GraphLLM: Boosting Graph Reasoning Ability of Large Language Modelcited by 105
  34. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 103
  35. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  36. 2021Neural Algorithmic Reasoningcited by 92
  37. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  38. 2023GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problemscited by 88

50 most cited of 61 All 61 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 16; 2025: 34; 2026: 14.

64 papers.

Sort:

By area:

  1. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 223
  2. 2025Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systemscited by 125
  3. 2024Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoningcited by 83
  4. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thoughtcited by 73
  5. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
  6. 2024Text-space Graph Foundation Models: Comprehensive Benchmarks and New Insightscited by 44
  7. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
  8. 2025Understanding Transformer from the Perspective of Associative Memorycited by 31
  9. 2024The CLRS-Text Algorithmic Reasoning Language Benchmarkcited by 28
  10. 2025Roll the dice & look before you leap: Going beyond the creative limits of next-token predictioncited by 28
  11. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  12. 2024Mixture of Parrots: Experts improve memorization more than reasoningcited by 20
38 more
  1. 2024Transformers Struggle to Learn to Searchcited by 19
  2. 2025A Formal Comparison Between Chain of Thought and Latent Thoughtcited by 14
  3. 2024Revisiting Random Walks for Learning on Graphscited by 13
  4. 2024GraphTeam: Facilitating Large Language Model-based Graph Analysis via Multi-Agent Collaborationcited by 12
  5. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 12
  6. 2025Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformerscited by 11
  7. 2025The Serial Scaling Hypothesiscited by 11
  8. 2024Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Pathcited by 10
  9. 2025GraphThought: Graph Combinatorial Optimization with Thought Generationcited by 9
  10. 2025Lost in Transmission: When and Why LLMs Fail to Reason Globallycited by 9
  11. 2024Lost-in-Distance: Impact of Contextual Proximity on LLM Performance in Graph Taskscited by 8
  12. 2025Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descentcited by 8
  13. 2025Primal-Dual Neural Algorithmic Reasoningcited by 8
  14. 2026Sequential Group Composition: A Window into the Mechanics of Deep Learningcited by 7
  15. 2024CodeGraph: Enhancing Graph Reasoning of LLMs with Codecited by 6
  16. 2024Best of Both Worlds: Advantages of Hybrid Graph Sequence Modelscited by 6
  17. 2025Graph-Aware Isomorphic Attention for Adaptive Dynamics in Transformerscited by 6
  18. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
  19. 2025Position: We Need An Algorithmic Understanding of Generative AIcited by 5
  20. 2025The Transformer Cookbookcited by 5
  21. 2026Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Datacited by 5
  22. 2024Reasoning in Large Language Models: A Geometric Perspectivecited by 4
  23. 2025Subquadratic Algorithms and Hardness for Attention with Any Temperaturecited by 4
  24. 2025Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspectivecited by 4
  25. 2025Are Language Models Efficient Reasoners? A Perspective from Logic Programmingcited by 4
  26. 2026Discrete Diffusion Models Exploit Asymmetry to Solve Lookahead Planning Taskscited by 4
  27. 2024A Hierarchical Language Model For Interpretable Graph Reasoningcited by 3
  28. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  29. 2025Are Large Language Models Good Temporal Graph Learners?cited by 3
  30. 2025Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectoriescited by 3
  31. 2024Machines and Mathematical Mutations: Using GNNs to Characterize Quiver Mutation Classescited by 2
  32. 2024A Theory for Compressibility of Graph Transformers for Transductive Learningcited by 2
  33. 2025On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Studycited by 2
  34. 2025Fast attention mechanisms: a tale of parallelismcited by 2
  35. 2025Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracingcited by 2
  36. 2025Generalizable Insights for Graph Transformers in Theory and Practicecited by 2
  37. 2026Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformerscited by 2
  38. 2025Sample-Efficient Optimization over Generative Priors via Coarse Learnabilitycited by 1

50 most cited of 64 All 64 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
  2. 2024Transformers meet Neural Algorithmic Reasoners
  3. 2024Simulation of Graph Algorithms with Looped Transformers
  4. 2024KnowFormer: Revisiting Transformers for Knowledge Graph Reasoning
  5. 2026The Scaling Properties of Implicit Deductive Reasoning in Transformers
  6. 2025From Sequence to Structure: Uncovering Substructure Reasoning in Transformers
  7. 2025Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning
  8. 2026Grounding latent algorithm routing in transformer reasoning