Faith and Fate: Limits of Transformers on Compositionality

Summary

This paper studies the compositional reasoning capability of Transformer models on three kinds of tasks, namely multi-digit multiplication, logic grid puzzles, and a dynamic programming problem. The compositional complexity of a given task, or the number of reasoning steps, can be easily controlled by varying lengths of inputs. This paper formulates the reasoning steps as a computation graph and uses characteristics like lengths and widths of the computation graph to qualify the level of complexity. For experimental evaluation, this work evaluates several Transformer models (i.e., GPT3, ChatGPT, GPT-4) using zero-shot, few-shot, and finetuning techniques. This paper shows that in zero-shot and few-shot settings, all three Transformer models deteriorate sharply from nearly perfect to nearly zero when increasing compositional complexity. Furthermore, finetuning GPT-3 with or without scratchpads does not help GPT-3 generalize to unseen and more complicated task instances. To gain a deeper understanding of these failures, this work finds that 1) Transformer models are likely to give partially correct predictions on outputs that can be determined by a small set of input features, and 2) Transformer models are likely to rely on computation patterns seen in training data and generalize poorly when they are not sufficient for OOD tests. Finally, with reasonable assumptions, this work gives a theoretical justification for why any models fail to generalize longer compositional reasoning tasks. Informally, as long as every single step is not perfect, the error will happen for a sufficiently long reasoning chain.

Strengths

- This work carefully selects three representative compositional tasks and introduces computation graphs to systematically quantify the level of complexity. - State-of-the-art transformer models like GPT-3, ChatGPT, and GPT-4 are used in the experimental evaluations. The observed limits are likely to be universal for existing transformer models. - Some new insights in analyzing the successes and failures of Transformer models are presented. Specifically, relative information gain seems a likely reason that Transformer models tend to predict partially correct answers; and linearized subgraph matching suggests Transformer models tend to capture spurious patterns in the training. - Four interesting categories of errors are proposed and can effectively characterize the mistaken behaviors of Transformer models when the compositional complexity increases. The restoration error is particularly interesting, as it captures an often ignored problem -- the model could give correct answers but because of wrong reasons. - Some simple but formal analyses are proposed to illustrate the theoretical limits of Transformer models.

Weaknesses

- It is well-known that large language models like GPT-3, ChatGPT, and GPT-4 behave poorly on complicated reasoning and planning tasks. So, most results of this work are somewhat expected. - Only three tasks are evaluated, and only one specific algorithm is chosen for each task. Although the chosen algorithm seems straightforward, it is possible that the particular algorithm may not be appropriate for Transformer models to learn. It does not rule out that the Transformer models may be good at learning other less intuitive algorithms for the evaluated tasks. - Finetuning is only performed on GPT-3. It is understandable that finetuning larger models like ChatGPT or GPT4 is computationally prohibitive for a small research group. But, from a scientific point of view, the observations on GPT-3 may not generalize to ChatGPT or GPT4, and the emergent capabilities of larger language models may overcome the limits observed on GPT-3. - The claim of subsection 3.2.2 is a bit subjective. Linearized subgraph matching is a means proposed in this work to better understand Transformer models. It does shine some light on why Transformer models fail for the chosen tasks, however, whether that's indeed Transformers' internal dynamics is not quite clear. - The theoretical justification seems oversimplified. It has nothing to do with the Transformer models.

Questions

Even assuming the computation graph is unique for a specific problem instance, exponentially many different sequential steps could express the same computation. How many sequences are extracted for a problem instance? The definition (line 213) of whether a full computation is seen during training is not quite clear, particularly what's the precise meaning of the sign $\equiv$ here? Figure 5b shows that predictions with large graph depth (e.g., > 16) tend to be all correct and have zero frequencies. It seems the Transformer models do generalize to more complicated tasks without reusing seen computation patterns in the training. Is it a plotting issue? Or is this interpretation wrong for some reason?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors discussed potential limitations, and there is no (obvious) negative societal impact of this work.

Summary

This work studies the ability of LLMs for compositional tasks. They propose a formalization called computation graphs. With this formalization, they further propose three different tasks: multi-digit multiplication, Einstein’s puzzle, and a dynamic programming problem. They test multiple LLMs on these three tasks with different training and inference settings. By varying the depth and width of the graph, they show that LLMs do not do well when the scale of the problem is large. In their further analysis, they point out two problems of LLM models: relying on single-step shortcuts and relying on similar training subgraphs. They also conduct an error classification and notice many hints for memorization (e.g., restoration error). Finally, this work presents a theoretical analysis showing the effect of error propagation.

Strengths

1. This work presents a relatively comprehensive and detailed evaluation of the compositional abilities for LLMs. The empirical results contain multiple training settings, and results w/wo scratchpads. 2. The three tasks designed in this work can be valuable for future work on compositional tasks. 3. The error analyses in this work are detailed and insightful. I really like the error classification analysis, which shows a more detailed description about LLM behaviors, and provide concrete and quantitative evidence for memorization, restoration error and error propagation.

Weaknesses

1. While the theoretical derivation is interesting, I find the takeaways and the perspective to be slightly underwhelming. The main takeaway seems to be error propagation lead to bad results when the problem scale is sufficiently large. This is true, but this is also true for everything, and for both machines and humans. To me, the more interesting problem lies in that why even n is not very large, compositional problems still seem to be relatively hard. Additionally, I think the theoretical derivation applies to sampling but not to greedy decoding. 2. The idea of using a computation graph to control and analyze the difficulty of composition is not novel, see related works in [1][2][3]. While I do feel that the approach and objective of this paper are different enough compared to previous works, there should still be a discussion about these works. 3. Minor presentation issue: Some experimental setup details are hard to find. For example, I cannot find how large the finetuning datasets are. And some of the other important details (e.g., how you split the train/test for finetuning experiments) are in the appendix. I understand the space is tight in the main paper, but I would encourage the authors to add some details to the main paper so that the results can be interpreted more easily. [1] Josef Valvoda, Naomi Saphra, Jonathan Rawski, Adina Williams, and Ryan Cotterell. Benchmarking Compositionality with Formal Languages. In COLING 2022. [2] Keysers, Daniel, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev et al. Measuring Compositional Generalization: A Comprehensive Method on Realistic Data. In ICLR 2020. [3] Ben Bogin, Shivanshu Gupta, and Jonathan Berant. Unobserved Local Structures Make Compositional Generalization Hard. In EMNLP 2022.

Questions

1. The prompt in the scratchpad seems to be carefully designed. How many different prompts have you tried? How do different prompts influence the findings? 2. How do you compute the entropies used in the information gains? 3. Just to confirm, when doing the question-answer training, is there no scratchpads?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

This work provided a limitation section in Sec. 8 in the main paper and a societal impact statement in Appendix E.

Summary

This paper contributes to the literature on analyzing the limitations of Transformer models in compositional tasks by presenting an analysis based on computation graphs. Based on these computation graphs, some interesting new observations are made, which I believe are worth publishing. I found the paper a great read and very interesting. I have many comments/criticisms/questions below, but I would like to clarify that these are not attempts to attack the content, and more aiming for constructive criticisms for trying to make the paper more clear and situated in the literature, as I think the work is very solid. Some typos/comments: - Part of this work has already been studied in the past, and I think the authors should do a better job in differentiating the new insights from previously known parts. For example, I think it'd be great to discuss the new findings given: "Making transformers solve compositional tasks" (2021), "The devil is in the detail: Simple tricks improve systematic generalization of transformers" (2021), and "Grokking: Generalization beyond Overfitting on Small Algorithmic Datasets" (2022) - Page 2: "This substantial gap suggests that systematic problem-solving capabilities do not emerge from maximum likelihood training" -> See the Grokking paper I mentioned above, as they show that maybe systematic problem-solving abilities can improve when training beyond the overfitting threshold. - Section 3: As discussed in "Making transformers solve..." mentioned above, even if "vanilla" Transformers really struggle to solve compositional tasks, slight modifications to the architecture show significant gains. So, when only evaluating variants of the GPT architecture, it seems like conclusions are limited to GPT-like models, and not to "Transformers" in general, as small architectural decisions can have big impact in these types of tasks. For example GPT models being decoder-only models, they employ causal attention, where as encoder-decoder models would be able to deploy bidirectional attention to the input problem, which can give very different inductive biases. Carefully clarifying the extent of the conclusions would be better. - Section 3.1: "suggesting that systematic problem-solving capabilities do not emerge via exhaustive training on task-specific data." -> Again, I'd like to bring up the Grokking paper results, and I wonder if the authors could comment on the implications for their results here. - Section 3.1: Although results are very interesting, I think the authors over-generalize the conclusions from experiments with one particular model pretrained in one particular way. I think it might be good to constrain conclusions of results to decoder-only-GPT-style-pretrained-Transformer models. - Propositon 4.1: this has very little to do with Transformers, but with any method that approximates steps. And btw, this proposition applies to humans as well, as the probability that a human makes a long calculation correct decreases with the length of the calculation due to the growing probability that at least one of the steps is wrong. So, again, I think that clarifying the extent of the conclusions in the paper needs some work, whereas above I was pointing out that experiments show failure cases for GPT-style models and you are overgeneralizing to Transformers, here you are showing a limitation of sequential prediction models, and too narrowly just blaming Transformers. Moreover, I see this proposition very related to the classic error compounding in the literature of imitation learning (e.g., see "Efficient Reductions for Imitation Learning", 2010), and usual solutions, e.g. Dagger, rely on training models to recover from mistakes, mitigating the problem. It'd be great to comment on the relation if the authors see it appropriate.

Strengths

Even if the weaknesses of Transformers in compositional tasks have been studied many times in the recent past, this paper brings an interesting new perspective based on computation graphs that allows for a more finegrained analysis than previous work.

Weaknesses

Perhaps the two main weaknesses (fixable) are that (1) conclusions seem to be overgeneralizing to the whole class of Transformer models, when only one instance of them was used for evaluation, and (2) it seems that some of the most relevant pieces of work in the literature were not discussed, making it harder to see what are the new pieces of knowledge that this paper is bringing compared to what was already known. Both of them fixable with small modifications to the manuscript though.

Questions

- In Section 3.2.3: How were these errors analyzed? Was the text output of the models parsed to find the intermediate steps? Assuming many of these are in natural language, how accurately were you able to recover these intermediate steps? - Concerning memorization/shortcuts: We humans use memorization and shortcuts all the time for performing some of these operations (e.g., we know that X times 0 is 0, no matter how many digits does X have, and hence we will skip all the computation graph, etc.). The key it seems to me is to know when these shortcuts are applicable, and when they are dangerous. Did you see any case of the former (correct application of shortcuts)? (apologies if this is explained somewhere in the paper or appendix, but I was unable to find it). - As a curiosity, where does the "faith and fate" from the title come from, it might be a lack of familiarity with some English idioms, but I am struggling to make the connection with the paper.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

As acknowledged by the authors in their own section, the main limitation is that experiments were conducted with just GPT models, and it's unclear if we can generalize from those, given these are all the same Transformer architecture, and pretrained in a particular way.

Summary

This paper develops empirical and theoretical studies on the limitations of Transformers for solving compositional tasks. It defines computation graphs and quantifies compositional complexity with the graph metrics and uses relative information gain to predict surface patterns learned by Transformer. It conducts extensive experiments on three representative compositional tasks and finds that Transformers rely on pattern matching and exhibits poor generalization in compositionality.

Strengths

This paper conducts extensive experiments and profound analysis. The idea of quantifying compositional complexity with computational graphs is inspiring.

Weaknesses

The empirical findings and the driven conclusions are quite trivial.

Questions

1. Based on the findings, what could be a possible solution for improving Transformers in multi-step compositional problems? 2. Can the computational graph definition and graph metrics be generalized to other compositional tasks, for example geometry problems?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The paper lacks methodologies or instructions for improving the model based on the obtained empirical findings and driven conclusions.

Thank you for the detailed replies

The replies helped to clarify my confusion, which I guess other readers may also share, so I wish the authors will incorporate them into future revisions.