# Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracing

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

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

## 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, 13 of 13)

- [BERT Rediscovers the Classical NLP Pipeline](https://mlsanity.com/paper/1905.05950/) (2019)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [A Primer in BERTology: What we know about how BERT works](https://mlsanity.com/paper/2002.12327/) (2020)
- [Explainability for Large Language Models: A Survey](https://mlsanity.com/paper/2309.01029/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Analyzing the Structure of Attention in a Transformer Language Model](https://mlsanity.com/paper/1906.04284/) (2019)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension](https://mlsanity.com/paper/2410.05298/) (2024)
- [Transformers Struggle to Learn to Search](https://mlsanity.com/paper/2412.04703/) (2024)
- [ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Models](https://mlsanity.com/paper/2405.09220/) (2024)
- [From Sequence to Structure: Uncovering Substructure Reasoning in Transformers](https://mlsanity.com/paper/2507.10435/) (2025)

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

- [Understanding the Staged Dynamics of Transformers in Learning Latent Structure](https://mlsanity.com/paper/2511.19328/) (2025)
- [Inside-Out: Measuring Generalization in Vision Transformers Through Inner Workings](https://mlsanity.com/paper/2604.08192/) (2026)
- [Why Retrieval-Augmented Generation Fails: A Graph Perspective](https://mlsanity.com/paper/2605.14192/) (2026)

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