# From Sequence to Structure: Uncovering Substructure Reasoning in Transformers

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 15 of its 34 references that are in the map.
- First posted on arXiv 11 Jul 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 15 of 15)

- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Attending to Graph Transformers](https://mlsanity.com/paper/2302.04181/) (2023)
- [InstructGraph: Boosting Large Language Models via Graph-centric Instruction Tuning and Preference Alignment](https://mlsanity.com/paper/2402.08785/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMs](https://mlsanity.com/paper/2410.13857/) (2024)
- [Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation](https://mlsanity.com/paper/2502.18771/) (2025)
- [Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers](https://mlsanity.com/paper/2503.01805/) (2025)
- [Graph Transformers for Large Graphs](https://mlsanity.com/paper/2312.11109/) (2023)
- [Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path](https://mlsanity.com/paper/2408.09529/) (2024)
- [Rewarding Graph Reasoning Process makes LLMs more Generalized Reasoners](https://mlsanity.com/paper/2503.00845/) (2025)
- [Spectral Journey: How Transformers Predict the Shortest Path](https://mlsanity.com/paper/2502.08794/) (2025)
- [Towards Graph Foundation Models: A Transferability Perspective](https://mlsanity.com/paper/2503.09363/) (2025)
- [Parameter-Efficient Tuning Large Language Models for Graph Representation Learning](https://mlsanity.com/paper/2404.18271/) (2024)

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

- [Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective](https://mlsanity.com/paper/2509.22613/) (2025)
- [Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracing](https://mlsanity.com/paper/2509.20336/) (2025)
- [GraphGhost: Tracing Structures Behind Large Language Models](https://mlsanity.com/paper/2510.08613/) (2025)

## Abstract (arXiv)

Recent studies suggest that large language models (LLMs) possess the capability to solve graph reasoning tasks. Notably, even when graph structures are embedded within textual descriptions, LLMs can still effectively answer related questions. This raises a fundamental question: How can a decoder-only Transformer architecture understand underlying graph structures? To address this, we start with the substructure extraction task, interpreting the inner mechanisms inside the transformers and analyzing the impact of the input queries. Specifically, through both empirical results and theoretical analysis, we present Induced Substructure Filtration (ISF), a perspective that captures the substructure identification in the multi-layer transformers. We further validate the ISF process in LLMs, revealing consistent internal dynamics across layers. Building on these insights, we explore the broader capabilities of Transformers in handling diverse graph types. Specifically, we introduce the concept of thinking in substructures to efficiently extract complex composite patterns, and demonstrate that decoder-only Transformers can successfully extract substructures from attributed graphs, such as molecular graphs. Together, our findings offer a new insight on how sequence-based Transformers perform the substructure extraction task over graph data.