mlsanityData to 14 Oct 2026

Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracing

arXiv 2509.20336 ↗First posted 24 Sep 2025cs.LG cs.AIcited by 3

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

Abstract (arXiv)

Transformer-based LLMs demonstrate strong performance on graph reasoning tasks, yet their internal mechanisms remain underexplored. To uncover these reasoning process mechanisms in a fundamental and unified view, we set the basic decoder-only transformers and explain them using the circuit-tracer framework. Through this lens, we visualize reasoning traces and identify two core mechanisms in graph reasoning: token merging and structural memorization, which underlie both path reasoning and substructure extraction tasks. We further quantify these behaviors and analyze how they are influenced by graph density and model size. Our study provides a unified interpretability framework for understanding structural reasoning in decoder-only Transformers.

Key facts. Cited by 3 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 13 of its 16 references that are in the map. First posted on arXiv 24 Sep 2025.

Builds on

13 of 16 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithms28 May

Other references · 12

  1. 2019BERT Rediscovers the Classical NLP Pipelinecited by 1,059
  2. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 1,003
  3. 2020A Primer in BERTology: What we know about how BERT workscited by 815
  4. 2023Explainability for Large Language Models: A Surveycited by 333
  5. 2023Can Language Models Solve Graph Problems in Natural Language?cited by 252
  6. 2019Analyzing the Structure of Attention in a Transformer Language Modelcited by 243
  7. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 176
  8. 2024The pitfalls of next-token predictioncited by 160
  9. 2024How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehensioncited by 30
  10. 2024Transformers Struggle to Learn to Searchcited by 19
  11. 2024ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Modelscited by 18
  12. 2025From Sequence to Structure: Uncovering Substructure Reasoning in Transformerscited by 3

Built on by

Cited by year (2026 to 14 Oct)

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

3 papers.

  1. 2025Understanding the Staged Dynamics of Transformers in Learning Latent Structurecited by 1
  2. 2026Inside-Out: Measuring Generalization in Vision Transformers Through Inner Workingscited by 0
  3. 2026Why Retrieval-Augmented Generation Fails: A Graph Perspectivecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2023The Expressive Power of Transformers with Chain of Thought
  2. 2026Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism
  3. 2026CircuitProbe: Predicting Reasoning Circuits in Transformers via Stability Zone Detection
  4. 2025Mechanistic Unveiling of Transformer Circuits: Self-Influence as a Key to Model Reasoning
  5. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
  6. 2025To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers
  7. 2026What Structural Inductive Bias Helps Transformers Reason Over Knowledge Graphs? A Study with Tabula RASA
  8. 2024A Hierarchical Language Model For Interpretable Graph Reasoning