From Sequence to Structure: Uncovering Substructure Reasoning in Transformers
On the map: LLM reasoning → Knowledge- and tool-augmented reasoning
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.
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.
Builds on
15 of 34 references.
Closest ancestors · 3
Same direction, newest first
- 2025Rewarding Graph Reasoning Process makes LLMs more Generalized Reasoners2 Mar
- 2024Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path18 Aug
- 2024InstructGraph: Boosting Large Language Models via Graph-centric Instruction Tuning and Preference Alignment13 Feb
Other references · 12
- 2020A Generalization of Transformer Networks to Graphscited by 661
- 2023Attending to Graph Transformerscited by 83
- 2024GraphArena: Evaluating and Exploring Large Language Models on Graph Computationcited by 49
- 2024Theoretical limitations of multi-layer Transformercited by 45
- 2024Graph Transformers: A Surveycited by 32
- 2024How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMscited by 24
- 2025Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigationcited by 12
- 2025Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformerscited by 11
- 2023Graph Transformers for Large Graphscited by 10
- 2025Spectral Journey: How Transformers Predict the Shortest Pathcited by 8
- 2025Towards Graph Foundation Models: A Transferability Perspectivecited by 7
- 2024Parameter-Efficient Tuning Large Language Models for Graph Representation Learningcited by 3
Built on by
Citing papers per year: 2025: 3.
3 papers.
Similar, not cited
Close in wording, no citation either way
- 2024GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability
- 2026Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism
- 2025TinyGraphEstimator: Adapting Lightweight Language Models for Graph Structure Inference
- 2026Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning
- 2026Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compression
- 2025When Structure Doesn't Help: LLMs Do Not Read Text-Attributed Graphs as Effectively as We Expected
- 2024A Hierarchical Language Model For Interpretable Graph Reasoning
- 2024GUNDAM: Aligning Large Language Models with Graph Understanding