From Sequence to Structure: Uncovering Substructure Reasoning in Transformers

Overall response: Thank you for your suggestions. We would like to clarify your key concerns below.

• W: spelling error.

A: Thanks for your careful reading and feedback. We will address these points in the final version.

• W: legend items

A: The legend items represent the IDs of the extracted substructures. We conduct experiments in the directed graph setting to reduce randomness in token generation. As a result, when the model outputs a substructure, it follows a consistent central ordering of node IDs. For example, "0431" indicates that the model first identifies node 0 (with out-degree 2), followed by its neighbor 4 (out-degree 1), then node 3 (a neighbor of 4), and finally node 1 (a neighbor of both 3 and 0). Similarly, in the "2431" case, the node with out-degree 2 is node 2, serving as the structural starting point. We will address these points in the final version.

• W: EL Vs. AL

A: EL performs worse than AL when trained for the same number of epochs, but it eventually reaches comparable performance. In our results, we selected the epoch at which AL achieves its best performance. However, we will also provide additional information indicating when EL catches up with AL, as shown in the table below:

EL with longer input lengths requires more training epochs to achieve the same performance as AL. Although EL and AL are theoretically equivalent in their ability to represent graph structures, the longer input sequences in EL lead to less efficient learning. We will clarify this point in the revision.

• W: inconsistency of Assumption 3.4.

A: The unique case is used as a special setting in Section 3.1.2, referred to as the Single-Num-Single-Shape case. This assumption is not used in the subsequent sections. Assumption 3.4 applies specifically to the scenario in Section 3.1.2, where each graph contains only one target substructure, and the Transformer is trained to extract that particular substructure. We then extend our analysis to more complex settings involving multiple substructures. In the Multi-Num-Single-Shape case, the graph contains multiple instances of a specific substructure. In the Single-Num-Multi-Shape case, the graph includes diverse substructures, and a prompt is used to guide the Transformer to extract a specific one.

We will clearify the definations of these three tasks in the revision as:

Single-Num-Single-Shape Task:

The input is directed graphs G=(V,E) (|V|=n) and G'=(V',E') (|V'|=k), where there exists a unique copy of G' in G. The Transformer is required to find the unique copy of G' in G for the input G,G'.

Multi-Num-Single-Shape Task:

The input is directed graphs G=(V,E) (|V|=n) and G'=(V',E') (|V'|=k), where there might exist multiple copies of G' in G. The Transformer is required to find all copies of G' in G for the input G,G'.

Single-Task-Multi-Shape Task: The input is directed graphs G=(V,E) (|V|=n) and G'=(V',E') (|V'|$\leq$ k), where there exists a unique copy of G' in G. The Transformer is required to find the unique copy of G' in G for the input G,G'.

Overall response: Thank you for your suggestions. We would like to clarify your key concerns below

• W: decoder-only transformers Vs. GNNS and graph transformers

A: We respectively point out potential misunderstandings in your comments regarding the motivation and the goal of our paper. We want to clarify them below:

Recent studies have empirically shown that LLMs possess strong capabilities in graph reasoning tasks [1, 2, 3]. At the same time, it is important to understand the underlying mechanisms behind this graph reasoning ability with the textual data [4, 5]. We focus on the substructure extraction task, motivated by prior work [2, 3] showing that LLMs can identify and extract specific substructures from a given graph.

To bridge the gap, the goal of our paper is to provide insights into why LLMs can extract substructures from text descriptions of graphs. As clearly stated in the abstract How can a decoder-only Transformer architecture understand underlying graph structures?. We do not aim to argue using transformers to replace GNNs or graph transformers, nor do we propose new algorithms to solve graph tasks.

To this end, we train decoder-only transformers using a text-based input format, following the GPT-2 training pipeline, to explore the mechanisms underlying their graph reasoning abilities. Therefore, connecting and comparing with graph-specific encode models such as GNNs and graph transformers are completely beyond the scope of this work.

Although it is off topic of our paper, we'd like to introduce the differences between decoder-only transformer and encoder based GNN, and Graph Transformers which have been discussed in the existing papers [5, 6, 7]. GNNs and graph transformers in substructure extractions are models for graph encoding, and the output only limited in the substructure counting, instead of in indefinite length of textual description of substructure. Therefore, the mechanism is totally different as summarized in the Table:

• W: It is unclear how well the proposed methods (ISF and Tins) generalize to real-world graphs with larger size and noise.

A: As claried in the previous question, the focus of this work is "How can a decoder-only Transformer architecture understand underlying graph structures?" Therefore, our work does not propose new methods for solving graph tasks. Instead, we focus on providing both theoretical and empirical foundations for why decoder-only transformers can understand structural information from textual graph descriptions. We summarize the underlying mechanisms and refer to them as ISF and Tins.

We follow the data and settings used in prior work [4, 5], which showed that simplified datasets can capture key properties of decoder-only transformers, which are also reflected in the performance of LLMs. Based on this, we use simplified textual graph data to design experiments that explore how decoder-only transformers understand substructures. The findings from these foundational experiments also support and help explain the behaviors observed in LLMs, as discussed in Section 4.

Meanwhile, we use molecular graphs as a special case of attributed graphs to demonstrate the theoretical foundations in real-world applications, where LLMs are capable of reasoning over attributed graphs [2, 3, 7, 10].

• Q: sensitive to the format

A: Thank you for your great question. This is exactly one of the key goals of our paper. Prior work has shown that LLMs are sensitive to the formulation of input structure prompts, and different formats can lead to varying performance [3, 9]. In our paper, we explain this phenomenon by comparing the EL and AL formulations. While both formats are valid for graph tasks, they differ in input length, which is an important factor, as LLMs are sensitive to sequence length and effect performance.

[1] Wang H, Feng S, He T, et al. Can language models solve graph problems in natural language?[J]. Advances in Neural Information Processing Systems, 2023, 36: 30840-30861.

[2] Tang J, Zhang Q, Li Y, et al. GraphArena: Evaluating and Exploring Large Language Models on Graph Computation[C]//The Thirteenth International Conference on Learning Representations.

[3] Dai X, Qu H, Shen Y, et al. How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension[C]//The Thirteenth International Conference on Learning Representations.

[4] Saparov A, Pawar S A, Pimpalgaonkar S, et al. Transformers Struggle to Learn to Search[C]//The Thirteenth International Conference on Learning Representations.

[5] Wang S, Shen Y, Feng S, et al. Alpine: Unveiling the planning capability of autoregressive learning in language models[J]. Advances in neural information processing systems, 2024, 37: 119662-119688.

[6] Chen Z, Chen L, Villar S, et al. Can graph neural networks count substructures?[J]. Advances in neural information processing systems, 2020, 33: 10383-10395.

[7] Zhu W, Wen T, Song G, et al. On structural expressive power of graph transformers[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 3628-3637.

[8] Müller L, Kusuma D, Bonet B, et al. Towards principled graph transformers[J]. Advances in Neural Information Processing Systems, 2024, 37: 126767-126801.

[9] Fatemi B, Halcrow J, Perozzi B. Talk like a Graph: Encoding Graphs for Large Language Models[C]//The Twelfth International Conference on Learning Representations.

[10] Zhang Y, Wang H, Feng S, et al. Can LLM Graph Reasoning Generalize beyond Pattern Memorization?[C]//Findings of the Association for Computational Linguistics: EMNLP 2024. 2024: 2289-2305.

Overall: Thanks for your suggestions. We would like to clarify your key concerns below.

We respectively point out potential misunderstandings in your comments regarding the motivation and the goal of our paper. We want to clarify them below:

Recent studies have shown that LLMs possess strong capabilities in graph reasoning tasks [3, 4, 5]. At the same time, it is important to understand the underlying mechanisms behind this graph reasoning ability with the textual data [6, 7]. We focus on the substructure extraction task, motivated by prior work [4, 5] showing that LLMs can identify and extract specific substructures from a given graph.

To bridge the gap, the goal of our paper is to provide insights into why LLMs can extract substructures from text descriptions of graphs. As clearly stated in the abstract How can a decoder-only Transformer architecture understand underlying graph structures?. We do not aim to argue using transformers to replace GNNs or graph transformers, nor do we propose new algorithms to solve graph tasks.

To this end, we train decoder-only transformers using a text-based input format, following the GPT-2 training pipeline, to explore the mechanisms underlying their graph reasoning abilities. Therefore, connecting and comparing with graph-specific encode models such as GNNs and graph transformers are completely beyond the scope of this work.

• W: Transformers are considered special cases of GNNs, and the findings are not new.

A: As discussed in the “Overall Response,” our work focuses on understanding why decoder-only transformers can capture substructures when trained using next-token prediction. Therefore, a detailed comparison with encoder-based frameworks falls outside the scope of this paper.

Although it is off topic of our paper, we'd like to introduce the differences between decoder-only transformer and encoder based GNNs in the Table:

The concept of information aggregation in our work, referred to as m-filter, is fundamentally different from the conventional m-hop aggregation in GNNs. While GNNs aggregate information from m-hop neighbors based on the adjacency matrix toward a central node, decoder-only transformers instead learn to filter relevant information across m tokens in the input sequence, without relying on explicit graph structure.

• W: Comapring with the GNNs that used in reasoning tasks.

A: As mentioned in the "Overall Response," this paper focuses on the question: "How can a decoder-only transformer understand graph structure?" Accordingly, our analysis is centered specifically on decoder-only transformers, which align with the architecture of LLMs. To the best of our knowledge, this is the first work to analyze structure understanding in the context of next-token prediction.

[1] proposes graph neural network blocks to encode algorithmic reasoning tasks using edge and node representations in the form of vector lists, but our approach relies solely on textual sequences and trained by next token prediction. [2] presents a blueprint for neural algorithmic reasoning within an encoder-decoder framework, whereas our study targets decoder-only transformers. Therefore, both works are outside the scope of our discussion, which explains how decoder-only transformers trained on textual graph data can learn to understand structural information.

In Sections 5.1 and 5.2, we continue to follow our central focus on how LLMs can understand graph structures presented in textual descriptions. These sections include more complex graph types, such as composed and attributed graphs. Our motivation for analyzing these graphs stems from prior findings that LLMs are capable of decomposing graphs and understanding attributed graphs such as molecular structures [5]. Thus, exploring neural algorithmic reasoning in real-world applications is beyond the scope of our current discussion.

However, we would like to share our view that reasoning tasks often involve substructure understanding, making this an important direction for future research. Given that decoder-only transformers such as GPT-2 have demonstrated strong performance on reasoning tasks (e.g., mathematics and logic), it would be valuable to investigate whether graph reasoning can be framed as a specific instance of general reasoning in LLMs.

• W: minor typo

A: Thanks for your advice, we will change it into "Following prior work, we represent graph data using either Adjacency Lists (AL) or Edge Lists (EL), and encode them as textual sequences for input into Transformers" to make it clear.

• Q: transformer trained with a substructure counting-heavy approach.

A: We do not train the transformer to count substructures. Instead, we train a decoder-only transformer using a next-token prediction objective to extract substructure node lists from given graphs. While prior work using GNNs or graph transformers has primarily focused on substructure counting [8], our model is trained to generate complete substructure lists in text form. Previous studies have shown that the graph reasoning ability of decoder-only LLMs can be enhanced through cross-task fine-tuning on graph-related tasks [9, 10]. Building on this, our work provides theoretical foundations for why LLMs can understand structural information, offering a basis for extending their capabilities to a wide range of structure-based tasks.

[1] Battaglia, P.W., Hamrick, J.B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R. and Gulcehre, C., 2018. Relational inductive biases, deep learning, and graph networks.

[2] Veličković, P. and Blundell, C., 2021. Neural algorithmic reasoning.

[3] Wang H, Feng S, He T, et al. Can language models solve graph problems in natural language?[J]. Advances in Neural Information Processing Systems, 2023, 36: 30840-30861.

[4] Tang J, Zhang Q, Li Y, et al. GraphArena: Evaluating and Exploring Large Language Models on Graph Computation[C]//The Thirteenth International Conference on Learning Representations.

[5] Dai X, Qu H, Shen Y, et al. How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension[C]//The Thirteenth International Conference on Learning Representations.

[6] Saparov A, Pawar S A, Pimpalgaonkar S, et al. Transformers Struggle to Learn to Search[C]//The Thirteenth International Conference on Learning Representations.

[7] Wang S, Shen Y, Feng S, et al. Alpine: Unveiling the planning capability of autoregressive learning in language models[J]. Advances in neural information processing systems, 2024, 37: 119662-119688.

[8] Chen Z, Chen L, Villar S, et al. Can graph neural networks count substructures?[J]. Advances in neural information processing systems, 2020, 33: 10383-10395.

[9] Zhang Q, Chen N, Li Z, et al. Improving LLMs' Generalized Reasoning Abilities by Graph Problems[J]. arXiv preprint arXiv:2507.17168, 2025.

[10] Zhang Y, Wang H, Feng S, et al. Can LLM Graph Reasoning Generalize beyond Pattern Memorization?[C]//Findings of the Association for Computational Linguistics: EMNLP 2024. 2024: 2289-2305.

Dear reviewer, thank you for your feedback. We hope we've addressed all of your concerns. As we approach the end of the discussion period, we still welcome further discussions. Please feel free to let us know if you have any additional questions or concerns.

Thank you for your suggestions. We would like to clarify your key concerns below

• W: decoder-only transformers Vs. GNNS and graph transformers

A: We respectively point out potential misunderstandings in your comments regarding the motivation and the goal of our paper. We want to clarify them below:

Recent studies have empirically shown that LLMs possess strong capabilities in graph reasoning tasks [1, 2, 3]. At the same time, it is important to understand the underlying mechanisms behind this graph reasoning ability with the textual data [4, 5]. We focus on the substructure extraction task, motivated by prior work [2, 3] showing that LLMs can identify and extract specific substructures from a given graph.

To bridge the gap, the goal of our paper is to provide insights into why LLMs can extract substructures from text descriptions of graphs. As clearly stated in the abstract How can a decoder-only Transformer architecture understand underlying graph structures?. We do not aim to argue using transformers to replace GNNs or graph transformers, nor do we propose new algorithms to solve graph tasks.

To this end, we train decoder-only transformers using a text-based input format, following the GPT-2 training pipeline, to explore the mechanisms underlying their graph reasoning abilities. Therefore, connecting and comparing with graph-specific encode models such as GNNs and graph transformers are completely beyond the scope of this work.

Although it is off topic of our paper, we'd like to introduce the differences between decoder-only transformer and encoder based GNN, and Graph Transformers which have been discussed in the existing papers [5, 6, 7]. GNNs and graph transformers in substructure extractions are models for graph encoding, and the output only limited in the substructure counting, instead of in indefinite length of textual description of substructure. Therefore, the mechanism is totally different as summarized in the Table:

• W: toy examples and how textual data can enable model understanding.

A: We follow the experimental setups of prior studies [4, 5], which suggest that simplified datasets can capture key properties of decoder-only transformers that are also reflected in the performance of LLMs. In line with these studies, we use simplified textual graph data to construct both theoretical and empirical experiments aimed at exploring the mechanism of decoder-only transformers in substructure understanding tasks. The findings from these foundational experiments also support and help explain the behaviors observed in LLMs, as discussed in Section 4.

• W: The result in 3.2.2. It is not surprising and explanations for the diagonal case.

A: As discussed in the previous response, we use simplified settings to uncover the basic and foundational mechanisms of decoder-only transformers. Moreover, we do not assume that the hidden dimensions scale up to $n^k$. Instead, we argue that the number of layers is the most important factor enabling decoder-only transformers to understand substructures, which is the central focus of our main results. To support this, we present an additional experiment in which we increase the hidden dimension while training a transformer to detect triangles, using 300K training samples:

The results show that increasing hidden size alone does not improve accuracy. For instance, 2 layers with 384 hidden size perform similarly to smaller models. In contrast, 3 layers with 192 hidden size achieve 0.98 accuracy (1.33M parameters), while 1-layer (768) and 2-layer (384) models only reach 0.37 and 0.76. This suggests that substructure understanding relies more on model depth than size. We will add this in the revision.

• Q: differences between Theorems 3.3, 3.5, 3.7, and 3.8

A: We first establish the basic case, single-num-single-shape, in Section 3.1.2, where only one substructure is to be extracted. Theorem 3.3 provides the foundation for how substructure extraction unfolds across layers, while Theorem 3.5 shows that the Transformer identifies the correct substructure through internal computation of a subgraph isomorphism indicator, rather than relying solely on next-token prediction. In Section 3.1.3, we address a more complex setting involving multi-num-single-shape and single-num-multi-shape cases, as illustrated by Theorems 3.7 and 3.8. These results lead to a new insight: the ISF process can operate simultaneously across multiple substructures with various prompts. This understanding helps explain how LLMs are capable of extracting diverse substructures in varying quantities [3]. Furthermore, Theorems 3.7 and 3.8 provide the theoretical foundation for the Thinking-in-Substructure phenomenon discussed in Section 5. We will further clarify these points in the final version.

• Q: results in 3.2.2 setting

A: In the 3.2.2 setting, substructures are not explicitly specified, which is the extension of single-num-multi-shape setting. The dataset includes diverse substructures and question types, covering both terminology and topology, all trained within a single transformer. As a result, a single graph may contain both diagonal and square substructures, and only the question prompt guides the model to extract the correct one. If the transformer fails to distinguish the prompt accurately, it may extract the wrong substructure. For instance, in the Topo1 format, the topological descriptions of diagonals and squares are similar, which can lead to confusion in prompts understanding. We will clarify this in the revision.

[1] Wang H, Feng S, He T, et al. Can language models solve graph problems in natural language?[J]. Advances in Neural Information Processing Systems, 2023, 36: 30840-30861.

[2] Tang J, Zhang Q, Li Y, et al. GraphArena: Evaluating and Exploring Large Language Models on Graph Computation[C]//The Thirteenth International Conference on Learning Representations.

[3] Dai X, Qu H, Shen Y, et al. How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension[C]//The Thirteenth International Conference on Learning Representations.

[4] Saparov A, Pawar S A, Pimpalgaonkar S, et al. Transformers Struggle to Learn to Search[C]//The Thirteenth International Conference on Learning Representations.

[5] Wang S, Shen Y, Feng S, et al. Alpine: Unveiling the planning capability of autoregressive learning in language models[J]. Advances in neural information processing systems, 2024, 37: 119662-119688.

[6] Chen Z, Chen L, Villar S, et al. Can graph neural networks count substructures?[J]. Advances in neural information processing systems, 2020, 33: 10383-10395.

[7] Zhu W, Wen T, Song G, et al. On structural expressive power of graph transformers[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 3628-3637.

[8] Müller L, Kusuma D, Bonet B, et al. Towards principled graph transformers[J]. Advances in Neural Information Processing Systems, 2024, 37: 126767-126801.