Understanding Transformer Reasoning Capabilities via Graph Algorithms

Summary

This paper investigates the algorithmic reasoning capabilities of transformers on graph problems and introduces a novel hierarchy that categorizes tasks into solvable classes under different scaling regimes of transformers. In addition, the authors perform experiments on GraphQA to validate their theoretical analysis.

Strengths

1. **Theoretical Aspect**: It provides a novel hierarchy that categorizes graph problems based on the scale of transformers required to solve these problems, providing insights into their algorithmic reasoning capabilities. 2. **Empirical Validation**: This paper supports its theoretical analysis with some experiments on the GraphQA benchmark.

Weaknesses

1. **Limited Generalizability**: The theoretical results are based on specific assumptions, parameter scaling regimes, and tasks, which might not be directly related to all real-world scenarios or practical applications. 2. **Lack of Guidance for Practice**: Beyond the insight that deeper and wider transformers have greater capacity, what guidance can this paper provide to practitioners? 3. **Some Impractical Settings**: The settings of blank tokens appended to the input sequence are not related to the practical scenarios. 4. **Need for Further Empirical Evaluation**: The experimental results of this paper are only performed on the GraphQA benchmark. More experimental results are needed to validate the theoretical results on real-world tasks.

Questions

See the Weaknesses section.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Authors write about limitations fairly.

Summary

In this work, the authors propose a new representational hierarchy for standard transformers in terms of computing algorithms over graphs. To this end, the authors relate transformers to the massively parallel computing model (MPC), thus establishing the connection to several graph algorithms. The empirical study validates the theoretical results. In particular, the authors compare transformers to graph neural networks (GNNs), as well as training small transformers from scratch, fine-tuning large-scale pre-trained language models and LLM prompting.

Strengths

- The motivation for this work is strong and the study is timely. In particular, studying the representational capacity of transformers on graphs is important and useful both for studying the capabilities of transformers in general as well as for tasks explicitly modeling data as graphs. - The paper is written clearly and concise. In particular, I appreciated the “Theoretical interpretation” parts below each empirical result which helps navigating the empirical study in the context of the theoretical results. - The empirical study is tightly linked to the theory. For example, the presented theoretical results have implications on the tasks in GraphQA, the benchmark used in the empirical study and the empirical study backlinks to the corresponding theoretical result.

Weaknesses

- There is an ambiguity in the empirical results in 4.1 and 4.2. I searched the experimental details in the main paper as well as Appendix E.3 and believe that the authors use standard GNN baselines without added positional encodings (also see my question to confirm this). However, note that the authors use transformers with a tokenization following TokenGT (https://arxiv.org/abs/2207.02505), which leverages positional encodings (in particular, node identifiers). Now, the authors for example say in L290-291 that GNNs do not have the sufficient representational capacity to compute graph connectivity. At the same time, the authors attribute the positive results in 4.2. to the inductive bias of GNNs (e.g., L319). I think these two claims should be distinguished. GNNs with node identifiers are universal (see e.g., Abboud et al. 2020, https://arxiv.org/abs/2010.01179) but arguably still possess the inductive bias mentioned in L319, namely that they exclusively aggregate information via the 1-hop neighborhood. Further, it is known in the graph learning community that GNNs with added positional encodings perform much stronger on long-range tasks; see Tönshoff et al. 2023, https://arxiv.org/abs/2309.00367). I suggest to compare to both GNNs with node identifiers as well as without and to clearly distinguish claims about expressivity from those of inductive bias. - The authors state that standard deviation is not provided due to high runtime costs. However, I would appreciate if standard deviation could be provided at least for the smaller models, that is, the GNN baselines as well as the 60M transformer to obtain an understanding of the variance of the presented results.

Questions

- Do I understand correctly that the graph data is provided to the LM-based models as text, whereas the 60M transformer and the GNN baselines receive the graph information in terms of a custom tokenization (in the case of the transformer) or encoding (in the case of the GNN)? - Do I understand correctly that the GNNs are not trained with node identifiers but the 60M transformer is (following TokenGT)?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

The limitations were adequately addressed.

Summary

This paper studies the reasoning capabilities of transformers by characterizing their representational power to execute graph algorithms. Theoretically, the authors employ a general transformer model previously studied by Sanford et al. (2024), which assumes that the local MLPs can represent arbitrary functions and thus may have unbounded parameters. Using this transformer model, the authors investigate depth, width, and number of extra tokens required for algorithm execution. This leads to a representational hierarchy of graph reasoning tasks. In particular, by relating the transformer model to the MPC distributed computing model, the authors show that logarithmic depth is both sufficient and necessary to solve parallelizable graph tasks. Empirically, the authors carry out well-designed experiments to demonstrate their theoretical results.

Strengths

- Understanding the reasoning capabilities of transformers is a highly important problem, both in theory and in practice. The results in this paper add new insights from the prospective of algorithm execution. - The technical result on MPC simulation in this paper is a notable improvement from the previous result in Sanford et al. (2024). It is interesting to see that using extra tokens can significantly reduce the required embedding dimension. - The experiments are well designed. The paper is well written. Overall I think this is a good paper with clear contributions.

Weaknesses

- As the authors mentioned at the end of the paper, the assumption of unbounded-size MLPs provides strong results. At the same time, this is an apparent gap between theory and practice. I think that making such assumption is fine. Just raising this point as a limitation of the current theoretical framework. - The graphs used in the experiments are super small (5 to 20 nodes) compared to the size of transformers (60M and 11B). Since, theoretically, the required depth and width are sublinear with respect to the input size, this empirical setting creates a huge gap between theory and practice. It would be nice if the authors carry out additional experiments on larger graphs, or limit the number of parameters in the transformers to a few thousands.

Questions

- Have you tried experiments on much larger graphs? There is a huge gap in the parameter count of transformers and the size of graphs used in the current experiments. - A related work [1] studies execution of graph algorithms using a looped transformer architecture. There, the authors prove that a transformer layer with constant depth and width can simulate a single algorithmic step of a graph algorithm for any input graph size. Consequently, by looping the same layer repeatedly, the resulting transformer model (having constant parameter count) can execute several graph algorithms. The authors should discuss the difference between their theoretical framework and that considered in [1]. Because it seems that the looping mechanism might help the transformer model to gain more efficiency in terms of parameter count. [1] Simulation of Graph Algorithms with Looped Transformers. Artur Back de Luca, Kimon Fountoulakis. ICML 2024.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors should explicitly discuss about the limitations due to the assumption on local MLPs can represent arbitrary functions. For example, would this be a potential reason for the huge gap between the input sequence length (size of graph) and the transformer size (parameter count) in the experiments? The authors should comment on how likely will the assumption lead to a theory-practice gap, and possible future avenues to close this gap.