Limits of Transformer Language Models on Learning to Compose Algorithms

Summary

This paper studies whether transformers can efficiently learn compositional discrete tasks. In particular, the paper introduces two new tasks: pointer execution neighbor and pointer execution reverse multicount as well as using multiplication and highest subsequence sum from prior work. First, small models are trained from scratch, showing substantially slower learning on the composition than on the subtasks. Next, API models are prompted to solve the same tasks and perform somewhat poorly. Some theory is also provided showing how models that memorize can struggle to learn compositions efficiently.

Strengths

1. The paper proposes an interesting question as to whether we can determine whether a language model has some higher level concept of task composition that allows it to learn compositions of previously learned tasks efficiently. 2. The paper includes a nice theoretical result via a complexity theory reduction that shows how composition is hard if we assume stylized models that memorize the training data.

Weaknesses

1. H1 as written cannot be disproven empirically since the "constant" could just be larger than those tested. It seems in the experiments "constant" means 100. If that is what is meant, then just say so in the hypothesis. 2. It is not clear if the notion of "sub-task" is somehow atomic and unique. This makes hypothesis H2 and H3 somewhat ill-defined too. It is possible that there are different sub-tasks (and perhaps many more of them) that better track how the model actually learns. Just because we can posit one way to compositionally solve the task does not mean that the model will learn that way (or even that it can necessarily represent that composition). 3. It is not clear why the new tasks are necessary or what specifically they add over prior, simpler tasks. There needs to be more justification of the somewhat complicated tasks to explain why they are necessary. Generally the presentation of these tasks and the results was unclear and could use improvement to make it more visually clear how matches and transitions are meant to happen in the tasks and more precisely what all the baselines are doing in the experiments. 4. It is not clear why one would expect an untrained small (150m) language model to somehow be able to compose subtasks without being trained to perform composition. As such, the results that the composition does not just arise and indeed takes longer to learn is not surprising. 5. I am somewhat worried that the way the strings representing the nodes are designed is interacting badly with the tokenizers in the API experiments. These are clearly "out of distribution" types of words and they may be tokenized in ways that make it very difficult to solve the task. Did you do any analysis of how these strings get tokenized? The tokenizers are publicly available. Also, it is difficult to fit this section into the story of the paper since there is no comparison to the learning of the subtasks.

Questions

See weaknesses.

Rating

4

Confidence

3

Soundness

2

Presentation

1

Contribution

2

Limitations

Limitations of not solving the issues raised are addressed in the paper.

Summary

This paper focuses on analyzing the transformer language models' learning and transferability on compositional discrete tasks. Specifically, it has four hypothesis, and the author studies for a variety of language models, whether does these hypothesis hold. H1. An LLM can learn to perform a compositional task with constant number of datapoints. H2. An LLM can learn to perform a compositional task, given as many sample as the most difficult sub-task required. H3. An LLM can learn to perform a compositional task, given the data samples of relearning all sub-tasks for learning the composition. H4. An LLM can learn to perform a compositional task, given more data samples in H3. The authors introduces a new benchmark for creating systematic sub-tasks and testing compositionally. With LLaMA model, H4 holds; with both GPT-4 and Gemini, using H1 (prompting) fails to perform the tasks, or multi-round code generation with COT technique.

Strengths

Originality: 3.5 / 5 This paper examines how the number of datapoint samples affects the learning of compositional tasks in existing transformer-based large language models (LLMs). The authors created a new, challenging compositional dataset based on computation graphs and demonstrated that learning compositional tasks with LLMs is highly data-inefficient. While the BIG-bench paper indicates the insufficiency of reasoning and compositional abilities in LLMs, this paper innovatively provides a concrete, quantitative, and extensive study on the extent of this insufficiency. Quality: 3.5/5 The empirical study is pretty extensive with both LLaMA, GPT-4 and Gemini. There are multiple prompting techniques adopted with GPT-4 and Gemini, all of them fails to generate a reliable result. There are also very interesting theotrical proofs in the appendix to bolster the authors' claims. Clarity: 3/5 Figure 1 is hard to understand just by staring at the graph. For each task, it only provides one example which is non-trivial at all. One can hardly figure out its ground truth program for each example, and whether in a task of PE, is the underlying program the same across all the datapoints. I believe a descriptive caption by the side of each task is necessary. For example, PE refers to a program that takes a sequence of words and returns a list of words all colored green, where the first output word matches the first input word, and any subsequent output word starts with the last two characters of the previous word. However, the figures and tables in the experimental section are pretty clear and helpful to understand. Significance: 2.5/5 Understanding the problem of the data inefficiency in transformer based LLMs is important to the community which focuses on data efficiency and reasoning, such as neuro-symbolic community.

Weaknesses

As stated in the strengths above. One of the main issue is the clarity issue of the tasks. Besides "what is the task", I also want to understand "why these two tasks are needed". What do PEN and PERM these two datasets bring?

Questions

Q1. Is the PEN dataset only corresponding to one underlying program? Q2. What are the insights of PEN and PERM these two datasets?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

I believe the stated limitation regarding addressing weaknesses in the LLM is not appropriate for this specific paper. Instead, the limitation should focus on the choice of the compositional dataset.

Summary

This paper evaluates the compositional learning abilities of Transformer-based models with LLaMA-like architecture on tasks requiring the composition of several discrete sub-tasks. To this end, the paper reuses two existing compositional algorithmic tasks and introduces two new ones, focusing on how many samples are needed for models to learn to compose the sub-tasks compared to the sample efficiency of learning the sub-tasks themselves. The study measures the efficiency of models when trained from scratch and the effectiveness of prompting the pretrained language models GPT-4 and Gemini. The experiments suggest that hypotheses that compositional learning requires no more samples than the sum of samples needed for each subtasks should be rejected. The paper also performs few-shot prompting with GPT-4 and Gemini with different prompting techniques to investigate their ability to learn to compose or decompose algorithms in-context and find that they are unreliable for executing sub-tasks or correcting errors in multi-round code generation. Finally, the paper uses complexity theory to support these findings, suggesting that when training feedforward models to memorize information with gradient descent, the sample inefficiency is inevitable.

Strengths

1. Aside from achieving state-of-the-art performance on many academic benchmarks, transformer-based language models are the undisputed workhorse for numerous real-world applications. However, their training does not necessitate compositional learning explicitly, while many of the tasks they are tasked at solving do require such capability. As such, understanding the limits and requirements for these models to learn to compose independent skills is key to drive our understanding of these foundational models and to improve them. 2. The analyzed tasks in the paper are very well defined to verify that a model that learns a task must know how to perform the subtasks, and that given capability to solve the subtasks, a model must only learn to compose these abilities to solve the task itself. Creating such settings is not trivial, and goes a long way to enhance our understanding of the compositional learning abilities of transformer models. 3. The paper provides a very thorough literature review and contextualizes the work around prior work very well. 4. The presentation of the paper is generally very nice, making a technical read easier and fluent.

Weaknesses

1. The authors correctly identify tokenization as a possible negative confounder in the defined testbed, and thus use character-based tokenization for the training experiments. However, the same care is not taken when investigating the abilities of GPT4 and gemini to perform in-context-learning. Namely, given the highly synthetic nature of the inputs, it is highly possible that both the out-of-domain distribution of these inputs (deviating from natural texts) as well as differences in how inputs are tokenized (for example, one key can be tokenized with a single token, another by three tokens, and a third be tokenized along with parts of the corresponding value) confounds and skew the results, hindering their usefulness. 2. Moreover, while the authors study many prompting techniques to evaluate GPT4 and Gemini, they use a constant 8-shot prompting. It is known that these models can benefit greatly from increased number of demonstrations, and has been shown that for out-of-domain tasks, one has to prompt the model with significantly more than 8 prompts to perform well (e.g. Levy et al., 2022, Bertsch et al. 2024, Agarwal et al. 2024) 3. The proposed testbed is very well defined, but a single transformer based model is being studied. Understanding the contextualization of the results given difference in the model and tasks properties (for example width-depth ratio, scaling behavior with respect to parameter count or effect length of the inputs) would be very beneficial.ֿ

Questions

1. Can you imagine similar experiments with more natural compositional tasks that can be learnt, and then used to benchmark SOTA LLMs in the settings they were designed and trained for? For example, do you think it is possible to use something similar to the unobserved local structures as proposed by Bogin et al. (2022) to create such settings? 2. Can you try repeating the experiments with clear instruction for GPT4/Gemini but using as keys only tokens in their respective vocabularies separated by e.g ‘-‘ so that the tokenization and highly synthetic nature of the task would have less detrimental effect on the results? 3. What are the exact specifications of the trained model? You mentioned it is 150M parameters, does that mean it is a 12-layer decoder only model? What was the training procedure in terms of hyperparameters? Do you see any scaling behaviors a-la Kaplan et al., 2020? For example, does using a larger model decrease the amount of samples needed? Also, does the depth of the model affect the ability to learn to compose subtasks? 4. Presentation suggestion - in a few places in the text, it would be very helpful for the reader to be able to read the descriptions if they were coupled with examples. 1. In section 2.2 you define sub-tasks in the computation graphs. I think including a small demonstration of such a computational graph, along with toy examples of sub-tasks and tasks would go a long way to make this section clearer and improve the smoothness of the reading. 2. In Section 3 you define and explain the different tasks and subtasks of your testbed. While Figure 1 is very nice and contributes a lot, it does not explicitly show the different sub-tasks or the procedures involved in deriving the output from each input, and in some cases (for example the counts in PERM) it may take time for the reader to understand what are the exact tasks. I think a more explicit demonstration of the procedure would be very helpful. It can either be a step-by-step demonstration of the procedure for each task (added in the appendix for brevity), or even a textual derivation of the procedure applied to clarify the operations being performed at every step. 3. In section 4, it will be very useful to add a table with an example input and output used for each task and their statistics (e.g. length, histogram on number of neighbor steps needed etc). If the inputs and outputs in Figure 1 are representative, you can also say that directly and point there.

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

The authors discuss some limitations, but do not directly address the generalizability of their findings to natural tasks subtasks composition.

Summary

The paper investigates the capabilities of Transformer-based language models in learning compositional discrete tasks. The authors evaluate both training LLaMA models and prompting GPT-4 and Gemini-Pro on tasks that require the learning of compositions of several discrete sub-tasks. The results indicate that these models exhibit significant sample inefficiency: LLaMA models require more data to learn compositional tasks than to relearn all sub-tasks from scratch, and in-context prompting with GPT-4 and Gemini is unreliable and often fails in multi-round code generation. The findings are supported by a theoretical analysis showing the sample inefficiency of gradient descent in memorizing feedforward models.

Strengths

- The paper evaluates both training from scratch and in-context prompting methods, providing a thorough analysis of the models' capabilities. - The authors introduce new algorithmic tasks designed to test compositional learning and providing a theoretical framework to support the empirical findings. - The study offers a deep dive into the limitations of current LLMs, supported by both empirical data and theoretical arguments, which can guide future research in learning compositional tasks.

Weaknesses

- The tasks and settings used in the experiments may not cover the full range of real-world applications, limiting the generalizability of the findings. - The performance and conclusions drawn are heavily dependent on the specific tasks designed by the authors, which might not fully represent other compositional learning scenarios. - Personally, it took me a while to understand how the given algorithmic tasks are designed and how they relate to the broader context of compositional learning. For instance, the `PERM' problem was not immediately intuitive to me.

Questions

- How well do the findings translate to practical, real-world applications beyond the synthetic tasks used in the experiments? Any specific reason to introduce new algorithmic tasks for evaluation? - Would the models perform differently on a broader variety of compositional tasks, particularly those that are more complex or domain-specific? - What specific modifications to model architecture or training strategies could be employed to enhance the sample efficiency of Transformer models in compositional learning?

Rating

4

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

- The study focuses on a limited set of compositional tasks, which may not fully capture the diversity of problems faced in real-world applications.