Limits of Transformer Language Models on Learning to Compose Algorithms

Thank you for your insightful comments and observations.

(W1) As shown in our results, H1 can be fixed to a very large range, and 100 was chosen for illustrational purposes; what is crucial is that we assume it is empirically much lower than H2. This means that H1 is defined to make the hypothesis more accessible and actionable, and it should only depict an upper bound of "a few demonstrations" i.e., we got inspired by what one would usually give in a few-shot and took an upper bound. We also refer to the PAC learning theorem, where the logarithmic factor shows that with very few samples, a large hypothesis space can be reduced, making a constant assumption on limited-complexity tasks reasonable in practice.

(W2) Thanks for the critique, it is indeed an important aspect that was not sufficiently clarified in the manuscript. In the introduced tasks, every primitive roughly corresponds to a basic block of operations in the equivalent procedural programming language and can be considered an atomic unit. To visualize the atomicity of the primitives within the tasks, we included pseudocode that shows how the introduced tasks (PEN and PERM) can be decomposed and solved with these primitives by a language model trained on next-token prediction in the additional 1-page PDF note.

The definition of these sub-tasks is, per se, not unique. However, our definition of sub-tasks is minimal, as every primitive is independently observed in only one task (as described in Section 2.2), and the primitives are atomic. In addition, we argue that our observations are independent of the optimality and uniqueness of primitives and sub-tasks. The inefficiency observed is relative to the given set of primitives and not defined in absolute terms. Finally, we cannot completely exclude the existence of an "optimal" set of primitives that could be easily re-combined by the model to learn compositional tasks efficiently. However, this possibility is deemed unrealistic by some of our experimental results. For instance, in our de-compositionality experiments (Section 4.2 and Tables B8, B9) we see that the model learns the sub-tasks much faster when pre-trained on the composition task. We speculate that this provides evidence that the model learns mechanisms similar to our primitives and that the learning inefficiency is, hence, mostly imputable to the difficulty of the model to recombine the primitives (which would not be solved by a better set of primitives).

(W3) Thank you very much for your question. We tried to improve the exposition of the tasks and their motivation in our rebuttal to the reviewer teuc. In addition, we also improved Figure 1, please refer to the additional 1-page PDF note.

(W4) This is a valid concern. Firstly, we argue that experimenting with small, un-trained models can still be interesting to test whether the compositionality can emerge naturally or not (as this result could be then potentially translated to real-world practical application) and provide insights on the intrinsic limitations of Transformer-based models on these tasks. Then, we highlight that in our experiments we also incorporated a certain amount of inductive bias toward compositional solution. For example:

• In-context learning. We prompted GPT-4 and Gemini-Pro extensively and demonstrated that they did not learn to compose their primitives successfully enough to even perform the tasks when given a clear description and a large number of examples. Please find the new results with many-shot prompting in the general response.
• Training the model from scratch. Note that we provided hints to the model such that learning how to compose learned primitive sub-tasks is made easier. We do this by introducing the PEV (Pointer-Execution Verbose) to the list of sub-tasks, which implicitly shows to the model the order in which the other subtasks need to be applied to solve PEN. For results with different architectures, please see "ablations with different architectures" in our general response.
• Fine-tuning of larger pre-trained models. Inspired by your comment, we have designed a new set of experiments to fine-tune larger pre-trained models on our algorithmic tasks, to validate whether the bigger size and/or the pre-train knowledge would affect our observations. Unfortunately, this kind of training takes a considerable amount of time, but we hope to be able to provide practical results before the end of the discussion period.

(W5) Thank you for raising potential concerns regarding tokenizations. We already searched through different task designs to improve the performance of GPT-4 and Gemini-Pro. The reviews motivated us to conduct further investigations and quantification primarily on the openly available GPT-4 tokenizer. Our findings can be summarized as follows (see the general response for a detailed discussion):

• We ablated different task designs in the initial submission; however, we found that the current sequence design (e.g., "ab1cd") performs best among other alternatives (such as "ab-1-cd").
• As an additional analysis, we tested the tokenization of GPT-4's open-source tokenizer (tiktoken). We found that the digit delimiter is always tokenized separately (e.g., "ab1cd" yields "ab", "1", and "cd"); hence, it does not have a detrimental effect on the attention mechanism. We found that some of the 2-grams were split into 2 tokens; however, removing them from the dataset did not improve the overall task accuracy with the best-performing prompting technique.
• We designed a new natural variation of PEN, dubbed Natural-PEN, where we replaced the synthetic 2-gram sequences with 3-gram, in-distribution, natural English words. Overall, we found that the GPT-4's performance does not improve on this in-distribution, natural English words, yielding even a lower accuracy on Natural-PEN.

Thank you for your positive feedback, insightful comments, and observations.

PEN and PERM: clarification and motivation To better understand the PEN and PERM tasks, we start the exposition by explaining the original Pointer Execution (PE) task using our encoding scheme.

The PE task is similar to linked list traversal or pointer chasing. The inputs are words delimited by whitespaces, where each word consists of an address, a delimiter, and a value. In our setup, addresses and values are each encoded using two letters from the English alphabet, and the delimiter is a single digit between 0 and 9. For example, uk7bh has "uk" as the address, 7 as the delimiter, and "bh" as the value. The first word in the input sequence is a single address, which points to a unique word in the sequence, starting the linked list traversal process. The sequence is traversed by reading out the value of the current word and matching it to the unique word whose address equals the current value. The traversal ends once there is no word whose address equals the value of the current word.

For example, given the input sequence "aa bc1yu aa5bc op9mn", the correct word traversal order is "aa aa5bc bc1yu".

This type of task is especially suitable for our study, as it limits the number of confounders in the data and, therefore, reduces (if not annihilates) the number of shortcut solutions that the model can find. In other words, PE tasks force the model to learn an algorithmic (general) solution by design and not rely on any possible statistical shortcut that might compromise the validity of the observations.

However, algorithmic tasks based on pointer chasing have so far been absent from the landscape of research on compositional learning. This is in large part due to the difficulty in expressing the PVR task using any primitive procedure except match, which extracts the value of the word currently processed and finds the word whose address matches the value. Hence, our PEN and PERM tasks emerged from the need for a set of tasks that keep the beneficial properties of pointer-chasing tasks and can simultaneously be expressed as a composition of a set of simple primitives.

The algorithmic primitives we introduce in the PEN task are left and right, which require the model to find the word to the left resp. to the right of the word that is currently being processed.

The input sequence is also modified and now consists of two sequences with interleaved elements. The first sequence is a valid PE sequence, whereas the second sequence is reminiscent of a PE sequence, but the values and addresses are not restricted to be unique. The two sequences have no common addresses or values. As an example, take the two sequences "ab ab8cd cd6ef" and "gh gh9kl gh6ij". The first one is a valid PE sequence, and the second one has the repeated address "gh". The corresponding PEN sequence is "ab gh ab8cd gh9kl cd6ef gh6ij". The task consists of traversing the pointers of the first of the two interleaved sequences while, at each traversal step, outputting the word to the right of the word currently traversed (the neighbor).

The fact that the model needs to output the neighbor combined with the neighbor's value, possibly having several matching addresses in the sequence, makes PEN a challenging compositional task, which can still be solved using only a few algorithmic primitives.

The PERM task is also based on the PE task, with a slightly different encoding of the sequence elements. The elements now consist of four letters from the English alphabet, to be interpreted as pairs of addresses and values, each encoded using two characters. The first element in the pointer traversal is explicitly provided.

PERM builds on top of the PE task by requesting that the sequence of words in the pointer chasing problem be output in reverse order, and it additionally involves keeping track of the length of the chain of pointers as well as the pointer orientation, i.e., does it point to the left or to the right of the current word.

Let us start with the following example sequence: "aabb eeff ccdd bbcc ddee", with the initial word being "aabb". Following the sequence of pointers starting from "aabb" results in the following sequence: "aabb bbcc ccdd ddee eeff". Each element in the resulting sequence has two numerical values associated with it, these being the length of the preceding pointer chain ('count') as well as the number of 'left'-pointers in the chain preceding the current element ('count left'). In our example here, the relevant sequences and numerical values are represented below:

Input sequence: "aabb eeff ccdd bbcc ddee"

Pointer chasing result: "aabb bbcc ccdd ddee eeff"

Count: 0 1 2 3 4

Count left: 0 0 1 1 2

Each step in the pointer-chasing procedure increases the "count" by one.

"bbcc" -> "ccdd" is the first pointer oriented to the left, and so it increases "count left" from 0 to 1. "ddee" -> "eeff" is the second pointer oriented to the left, and it increases "count left" from 1 to 2.

The final result is obtained by outputting the pointer chasing result in reverse order and associating with each word in the output sequence a number equal to "count" multiplied by "count left" for that word. This results in the following output:

Input sequence: 'aabb eeff ccdd bbcc ddee'

PERM result: 'aabb.0 bbcc.0 ccdd.2 ddee.3 eeff.8'

(Q1) We cannot guarantee that our decomposition of the PEN task into the primitives "match", "left" and "right" is unique. A different set of primitives will lead to a different decomposition. However, given our set of very simple primitives, it is highly unlikely that there exists a decomposition different from what we provide in the PDF.

(Q2) We refer to our answer Q1 of reviewer qmuR.

Your response has clarified my concerns. I have raised my score from 4 to 6. I really hope these clarifications can go into the revised version of the paper to improve the clarity and presentation.

Thank you for your insightful comments and observations.

(W1) We thank the reviewer for raising potential concerns regarding tokenizations. We already searched through different task designs to improve the performance of GPT-4 and Gemini-Pro. The reviews motivated us to conduct further investigations and quantification primarily on the openly available GPT-4 tokenizer. Our findings can be summarized as follows (see the general response for a detailed discussion):

• We ablated different task designs in the initial submission; however, we found that the current sequence design (e.g., "ab1cd") performs best among other alternatives (such as "ab-1-cd").
• As an additional analysis, we tested the tokenization of GPT-4's open-source tokenizer (tiktoken). We found that the digit delimiter is always tokenized separately (e.g., "ab1cd" yields "ab", "1", and "cd"); hence, it does not have a detrimental effect on the attention mechanism. We found that some of the 2-grams were split into 2 tokens; however, removing them from the dataset did not improve the overall task accuracy with the best-performing prompting technique.
• We designed a new natural variation of PEN, dubbed Natural-PEN, where we replaced the synthetic 2-gram sequences with 3-gram, in-distribution, natural English words. Overall, we found that GPT-4's performance does not improve on this in-distribution, natural English words, yielding even a lower accuracy on Natural-PEN.

(W2) Thanks for the comment and the relevant pointers! Following your suggestion, we provided the models with a more consistent number of shots on both PEN and PERM to verify whether increasing the number of examples beyond 8 would highlight an increase in the models' accuracy. We provided up to 32 examples (64 did not fit into the 8k context window of the GPT-4 version we are using). However, we did not observe any performance improvement, as reported in the table below.

We believe that the helpfulness of the additional examples might depend on the considered task and that, in some cases, there could be no improvements or even considerable sensitivity to the number of prompts. If you consider these results relevant, an Appendix on them could be added upon acceptance.

(W3) This is a limitation of our current results. However, we did experiment with different sizes of LLaMA up to 600M. Because we could train a 33M model to perform the PEN task well, it is reasonable to assume a 150M model should be sufficiently large, and hence present our results with this model. Regarding other architectures, we also ablated a Universal-Transformer-style model in Appendix B.5 thanks to their good performance on compositional tasks like SCAN [61]. This model (UT-style LLaMA) has only one layer with the same configuration (embedding size 1024, 16 heads), and this layer is repeated. We achieved very similar results with UT-style LLaMA (Table B.10) compared to our main model. Please see our general response for more variants of architectures that we tried.

(Q1) This is an interesting question, thanks for pointing to the prior work for discussion in our paper and suggesting a more general research direction. In our investigation, the tasks considered do not present unobserved local structures since the composition of primitives only admits a specific combination of operations (e.g., RIGHT[MATCH[LEFT[MATCH]]] in PEN), and the trained models should always have (at least in principle) the possibility to observe and learn this specific sub-graph in the computational graph.

This is a desired property as the goal of our investigation was not to stress-test how well Transformer language models can learn arbitrary difficult compositional tasks but rather to measure how sample efficient they are in learning the composition of simple primitives in algorithmic tasks. Considering more tasks characterized by more complex phenomena (such as unobserved compositions of the primitives, spurious correlations in the data, semantical ambiguities, etc.) would have hence partially defeated this purpose, contaminating the effects of the intrinsic limitation of the Transformer model with other factors.

However, after observing and validating our hypotheses on the simple synthetic datasets, we still believe that it would be compelling to extend the analysis to more natural compositional tasks such as the ones investigated by Bogin et al. It would allow us to verify how well the observed behavior scales in a real-world scenario, possibly providing new angles to it.

(Q2) Please refer to the results presented in (W1) and to the note on tokenization included in the general response.

(Q3) We report here the exact specifications of the models that we trained in our experiments. We use the Adam optimizer, a hidden size of 1024 and 12 layers. The model is a standard LLaMA 2 implementation, decoder only with Rope positional encoding and a Swiglu feedforward net. We did not use Grouped Query Attention, as LLaMA models do not use them in their smaller sizes. For what concerns the possible ablations on width/depth and larger models, we performed some minor ablations on them, but we observed no changes in the results, discouraging us from proceeding further in this direction (see our response in (W3) as well). However, as pointed out in your question, it would be interesting to observe whether the size and depth of the model can play a role in the learning efficiency, and if this interplay can be characterized through similar scaling laws such as Kaplan's.

(Q4) We would like to extend our sincere gratitude for the suggestions on the presentation and writing in general. We will incorporate them upon acceptance.

Thank you for your insightful comments and questions.

(W1) We acknowledge that the investigated collection of tasks does not cover the full range of real-world applications. Nonetheless, this is a common choice across different works in this domain [paper references 16, 29, 30]. It allows us to operate in a fully controlled environment, limiting the impact of exogenous factors on the empirical observations while having the possibility to stress-test compositionality. Furthermore, we believe that working with synthetic datasets does not limit the generalizability of our findings. When a model fails to learn efficiently in a synthetic, fully controlled environment, it will even more do so in more complex, real-world scenarios, which present several additional challenges for the model (e.g., semantic and syntactic ambiguities, spurious correlations, distribution shifts, etc.). This is also supported by a deep foundation of literature showing limited compositionality in practice [paper references 5, 8, 9, 11, 13 16].

Moreover, the synthetic nature of the considered tasks does not preclude the possibility of making observations that could be translated to more complex, real-world scenarios as well. One example is the multiplication task (MUL), a fundamental task in mathematics on which LLMs struggle without a significant amount of additional training [paper references 11, 16]. We speculate that both our empirical and theoretical results can shed light on this behavior, justifying it as an intrinsic inefficiency of LLMs in composing the simple sub-operations necessary to solve the task and quantifying their sample inefficiency in certain complexity classes.

(W2) While strictly speaking, our statements are limited to our tasks, in our investigation, we include a diverse range of algorithmic tasks and observe consistent behavior across all of them. Therefore, we expect that the same conclusions would hold on any similar tasks involving the composition of simple, known primitive operations (which occurs in many algorithmic, mathematical, and reasoning tasks).

(W3) We tried to clarify the tasks with an updated Figure 1, shown in the 1-page PDF note.

(Q1) Concerning the extent to which our observations could potentially extend to practical, real-world applications beyond the synthetic tasks used in the experiments, please refer to our observations in (W1). In addition, also refer to the general response (tokenization) with the additional results on the new Natural-PEN.

On the other hand, the reasons behind the introduction of the novel tasks are manyfold:

• First, we argue for the introduction of algorithmic tasks based on the pointer execution, introduced by Bengio et al. [20] and so far absent in the landscape of research on compositional learning. This task limits the number of confounders in the data and, therefore, reduces (if not annihilates) the number of shortcut solutions that the model can find. In other words, pointer execution tasks force the model to learn an algorithmic (general) solution by design and not rely on any possible statistical shortcut that might compromise the validity of the observations.
• As algorithmic tasks, PEN and PERM are particularly suitable for benchmarking compositionality. We can decompose them into single atomic operations (referred to as primitives in the text), which can make learning the task easier if the model can identify and leverage their compositional nature. We clarify their decompositional nature in the response of W2 of reviewer Fa35.
• Finally, our tasks represent a unique example in the sense that the failure of GPT-4 and Gemini-Pro is very apparent despite extreme help, e.g., providing multi-shot examples and showcasing limited compositionality of current SOTA models better than any task we are aware of.

(Q2) These LLMs would always perform decently if there is enough data. Our findings, however, are that the required data becomes excessive with more complex tasks. Our forecast is, therefore, that the more complex and the more domain-specific the tasks become, the harder it becomes for LLMs to perform them correctly (e.g., different to our education systems, where a student does not necessarily get more data for more complicated concepts). Concretely, in our experiments, this materializes in a model starting to hallucinate wrong solutions and failing at seemingly obvious executions (see GPT-4 experiments and Figure 2).

(Q3) There exists evidence [17, 61] that Transformers with weight-sharing between different layers and recurrence tend to perform better on compositional tasks than standard Transformer variants. It is for this reason that we also experimented with several such models during our work. We discuss details thereof in the general response.

Additionally, we independently investigated several novel architectural modifications aimed at increasing compositionality within the Transformer. One such idea has been penalizing superposition in favor of improving compositionality inspired by [Elhage et al., 2022, Olah, 2023], by including a single parameter modifying the read-outs from the latent representations for attention and feedforward blocks that penalize superposition and with that possibly encourages compositionality in the latent representations. We also built a Transformer that appends new computations from attention and feedforward passes (instead of adding) to a list of "latent tokens" with an additional attention mechanism to access those fields in the hope that compositionality can be encouraged. While some of those approaches did increase compositional capabilities on small datasets, we have not found a fundamental improvement in the domain of our experiments so far.

[Elhage et al., 2022] https://arxiv.org/abs/2209.10652 [Olah, 2023] https://transformer-circuits.pub/2023/superposition-composition/index.html