Limits of Transformer Language Models on Learning to Compose Algorithms

Authors: jonathan  thomm
giacomo  camposampiero
michael  hersche
ibm  research -zurich
eth  zurich
mpi  tübingen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:50:19

Abstract: We analyze the capabilities of Transformer language models in learning compositional discrete tasks. To this end, we evaluate training LLaMA models and prompting GPT-4 and Gemini on four tasks demanding to learn a composition of several discrete sub-tasks. In particular, we measure how well these models can reuse primitives observable in the sub-tasks to learn the composition task. Our results indicate that compositional learning in state-of-the-art Transformer language models is highly sample inefficient: LLaMA requires more data samples than relearning all sub-tasks from scratch to learn the compositional task; in-context prompting with few samples is unreliable and fails at executing the sub-tasks or correcting the errors in multi-round code generation. Further, by leveraging complexity theory, we support these findings with a theoretical analysis focused on the sample inefficiency of gradient descent in memorizing feedforward models. We open source our code at https://github.com/IBM/limitations-lm-algorithmic-compositional-learning.

Main paper: 
 introduction: 
 While Large Language Models (LLMs) are known to perform well on natural language generation tasks [1, 2] , they exhibit failures on reasoning [3, 4, 5, 6, 7, 8, 9, 10] , mathematics [11, 12] , causal inference [13, 14, 15] , and algorithmic tasks [16, 17, 18] . Many interesting algorithmic tasks rely on function composition, which is an act of combining simple functions (e.g., primitive sub-tasks) to build more complicated ones. In this paper, we dive into the question of how sample-efficient Transformer-based [19] language models are when learning to compose as well as to decompose algorithmic procedures. We empirically approach the aforementioned question by analyzing the performance of Transformer language models on a set of compositional algorithmic tasks. Given that a Transformer language model has enough samples to learn all primitive sub-tasks, we define four hypotheses on how well it learns the composition task within the same training routine: H 1 . A Transformer language model learns the task composition with a constant number of samples (only used in the in-context learning setting). H 2 . A Transformer language model learns a compositional task with fewer samples than those required to learn its most difficult sub-task. 
preliminaries: 
 Computational graph Let A be a deterministic algorithm and let F A be a set of deterministic primitive operations that can be used by A during execution. Given an input x, we define the computational graph for the algorithm A as G A(x) = (V, E). G A(x) is a weakly connected, directed acyclic graph. The nodes v ∈ V represent all intermediate variables' values during A's execution, while the edges e ∈ E represent the function arguments involved in the computation of their target nodes. One source node s describes the input x, while the (single) sink node t represents the output A(x) = t. For every non-source node v, op(v) ∈ F A denotes the operation applied to compute v. Figure 1 shows an example with a toy input for one of the tasks (PEN) later introduced in Section 3.Sub-task definition While Dziri et al. [16] define one sub-task for each operation occurring in the nodes of G A(x) , we relax this constraint and also consider sub-tasks composed of multiple operations from F A . However, we require every operation in the set of primitives F A to be independently observable. Given the set S of all the defined sub-task graphs, we say that an operation f = op(v) is independently observable in a sub-task graph G ′ A(x) if either:• v is the only non-source node in G ′ A(x) (i.e., there is only one operation in the sub-graph). • v is not the only non-source node in G ′ A(x) and all other operations in the nodes of G ′are independently observable in the other sub-task graphs in S\{G ′ A(x) }.By using this constraint on the definition of the sub-tasks, we aim to achieve a middle-ground between completely synthetic settings (where each primitive is presented in isolation) and real-world settings (where the primitives are often grouped and correlated).  
probing compositionality with algorithmic tasks: 
 Pointer execution tasks are a family of algorithmic tasks initially proposed to benchmark the generalization capabilities of deep learning models [20] . They are designed to limit the number of confounders in the data and force the model to learn an algorithmic (general) solution, making solving the task with statistical shortcuts impossible. Furthermore, being algorithmic tasks, they are particularly suited for testing compositional learning, as they can be naturally decomposed into atomic operations. Hence, the introduction of this family of tasks would allow operating in a fully controlled environment, limiting the impact of exogenous factors on the empirical observations while having the possibility to stress-test compositionality.Motivated by these premises, we introduce two novel pointer execution tasks for testing compositional learning, Pointer Execution's neighbor (PEN) and Pointer Execution Reverse Multicount (PERM).To ensure the validity of our empirical evaluation, we then further extend our experiments to two well-established tasks for testing compositionality in Transformer-based language models, Highest Subsequence Sum (HSS) and Multiplication (MUL) [16] . We decompose each task in a set of sub-tasks S, such that every primitive operation of the task is independently observable in at least one sub-task. A more detailed exposition of the properties of S is included in Appendix B.1.We introduce the Pointer Execution's neighbor (PEN) task, where the goal is to jump between different words in the sequence according to a matching criterion while outputting the right neighbors of the matched words. This task is inspired by C-PVR, a task recently introduced by Abnar et al. [17] and itself based on the Pointer Value Retrieval task [20] . A sketch of the task is shown in Figure 2 (left). We identify three primitive operations to be left (get the green left neighbor), match (get the matching green word), and right (get the right yellow neighbor). We, therefore, split PEN into three sub-tasks that guarantee independent observability for each primitive: copy (Cpy), where the solver has to copy an input sequence of words (making the right primitive observable); reverse copy (RCpy), where the solver has to copy an input sequence of words in the reversed order (i.e. the last word first, making the left primitive observable); Pointer Execution (PE), where the solver has to match words in a sequence (making the match primitive observable). Additionally, we define the sub-task Pointer Execution Verbose (PEV) to facilitate the learning of the task. PEV requires solving the same problem as PEN with the addition of outputting both the matching words and their neighbors, making it less abstract (see Figure 2 ). More details on PEN can be found in Appendix B.2.To make the task more challenging, we add "attention traps" to the input sequences. These traps add spurious matches between neighboring (yellow) tokens (two spurious matches per yellow neighbor), such that the model could be tricked into matching the wrong sequence of tokens (yellow instead of green). An example of this kind of trapping mechanism is included in Figure 2 (left column), and in a more explicit visualization in Figure B.5. The traps are not added to the main (green) tokens, where the sequence of matches is always deterministic.We introduce the Pointer Execution Reverse Multicount (PERM) task. This task is conceptually similar to the PEN task. However, instead of matching forward and predicting the current word (or its neighbor), the solver has to output the reversed matched sequence. To increase the difficulty of the task, we enrich it with additional operations on the indices. In particular, for each element in the matched sequence, the solver needs to collect the number of matches and the number of left matches up to that point, multiply them, and output the result. A visualization of the task is presented in Figure 2 . We omit attention traps because there are no longer neighbor tokens in the input sequence.We identify the primitive operations of the PERM task to be match (common to PEN), reverse (reverse a sequence), and multicount (indexes operations, which includes counting the number of matches and left matches, as well as multiplying the two counts together). The primitives left and right are no longer needed, as we drop the concept of neighbors in this task. To make every primitive independently observable and learn PERM, we formulate three sub-tasks: Pointer Execution (PE), inherited from PEN; Pointer Execution Reverse (PER), where the solver has to match a sequence and reverse it, combining the primitives match and reverse (making the latter observable); Pointer Execution Multicount (PEM), where the model has to match the sequence and compute the index operations, combining the primitives match and multicount (making the latter observable).Task: Pointer chasing by matching value (last 2 letters) to address (first 2 letters) of words in the sequence with a given start value.Introduce neighbors shown in yellow blocks and delimiter between address and value.Output the pointer chasing result with the corresponding neighbors.Output only the neighbors of the words encountered during pointer chasing.Output the pointer chasing result in reverse order.Multiply the current pointer chain length with the number of left-pointers up to the current word.Explicitly provide the first word in the pointer chasing procedure. Our matching criterion is that the two end characters of the current word are equal to the first two characters of the matched word. By ensuring that there are no ambiguities in the input string, an attention mechanism can find the match by retrieving the last two characters of the word and matching it with the (unique) word that starts with them. Right: The Pointer Execution Reverse Multicount (PERM), together with the Pointer Execution (PE) and Pointer Execution Reverse (PER) sub-tasks. PERM first outputs the last word in the matching sequence and then goes backward. The number in the answer for each word is the count of matches times the count of left matches (i.e., arrow to the left in the forward matching sequence).Given a sequence of numbers, the Highest Subsequence Sum (HSS) task [16] consists in finding the highest sum of a number subsequence where no two numbers are neighbors. For this task, there exists a simple linear-time, constant-space dynamic programming (DP) solution which we use to generate sub-tasks. The dynamic programming recurrence isEQUATIONwhere number i+1 is the i + 1-th number in the input sequence. The final answer is dp(n) with n being the length of the input sequence. We identify one fundamental primitive used in this task inspired by this formulation of the problem, dp_step, presented in Equation 1. Hence, we define a single sub-task, the Subsequence Sum Execution (SSE) sub-task, to make the primitive dp_step observable. In this sub-task, the solver is required to execute the DP recurrence, explicitly computing dp(i) for the position i in the output (including if the new number was taken or not).The Multiplication (MUL) task [16] involves multiplying two multi-digit numbers in base 10. It is often used to assess the symbolic and compositional capabilities of LLMs [21, 22] . Dziri et al. [16] use this task to find that LLMs do not generalize well to out-of-domain computation graph depth and width. We identify two main primitive operations: digit_mul (digit multiplication between a number in base 10 and a digit) and add (addition between numbers). We then formulate two corresponding sub-tasks to guarantee that each one of these operations is observable: digitmultiplication (MUL), where the solver has to solve multiplications between a number in base 10 and a digit (making digit_mul observable) and addition (ADD), where the solver has to add numbers in base 10 (making add observable). We do not explicitly train on shifting the numbers with zeros before adding them up.4 Sample efficiency on compositional learning 
training llama models for testing compositionality: 
 In this section, we investigate compositional learning on the tasks presented in Section 3. For each one of them, we encode its multiple sub-tasks by adding unique identifiers at the beginning of the samples. We then train a LLaMA model from scratch on all sub-tasks concurrently (sampling from them uniformly at random). We use a character tokenizer and apply cross-entropy loss on all tokens, including both the input and the output sequences, as is usual in autoregressive language modeling. Computing the loss only on the answer part, as done in other works [23, 24] , led to worse results in our experiments. We consider an algorithmic task to be learned only when (almost) perfect in-distribution accuracy is achieved. Any solution resulting in lower accuracy is, on the other hand, considered wrong, as it fails to fully capture the operations of the algorithm underlying the task. We conducted additional ablations on the model architecture (e.g., a LLaMa architectural variation based on Universal Transformer [17] ), included in Appendix C.5. However, the unsatisfactory results deterred us from conducting further systematic analysis on it.Learning the PEN task. We train LLaMA with all four sub-tasks (Cpy, RCpy, PE, PEV) and PEN. As shown in Figure 3 (detailed numbers are in Table C .2), the model successfully learns all the sub-tasks containing the primitives needed for PEN. However, it fails to properly compose them for solving the task under hypotheses H 2 (no. of samples needed for the most difficult sub-task) and H 3 (no. of samples needed for relearning all sub-tasks). Increasing the sample size to 1000 K (roughly 10× more compared to the sum of the samples needed to learn each sub-task independently) allows the model to learn the PEN task. This makes hypothesis H 4 (a Transformer language model needs more data samples than the sum of samples needed for re-learning all sub-tasks separately) the most plausible.Furthermore, by training the model on PEN only (without the sub-tasks), we observe that LLaMA obtains no significant benefit from learning the sub-tasks (see w/o sub-tasks vs. w/ sub-tasks in Figure 3 ). Based on these results, we speculate that the sub-tasks are not properly reused, and the tasks are rather learned every time from scratch. We interpret this as evidence that the model is not learning the task compositionally.To set those results into context: our dataset of 1000 K samples overall has roughly 6× more tokens than the number of words a typical 13-year-old would have heard in their life [25] . Furthermore, we can train a discrete hill-climbing learning algorithm containing 121 discrete parameters to perfectly learn the PEN task from a single sample, given the sub-tasks as primitives (see Appendix C.2).We also propose an ablation with a smaller model (28 M instead of 150 M parameters, "aux. loss" in Figure 3 , and more detailed Table C .3). We add two additional prediction heads after a fraction of 1 /2 and 3 /4 of the layers, respectively, and train them using auxiliary losses. The first loss is used to train the first head to predict, at step i, the i-th (yellow) element of the answer. The second loss is used to train the second head to predict the (green) element to the left of the one predicted by the first head. The auxiliary losses model can learn PEN with 300 K samples, while the bigger LLaMA (150 M) obtains 0% accuracy with the same dataset size. However, this result also falls into the H 4 hypothesis.Learning the PERM task. We train LLaMA models on the PERM task together with its sub-tasks (PE, PER, and PEM). The training setting used to train the model on this task is identical to the one used for PEN. As reported in Figure 3 (and with more detail in Table C .4), LLaMA can learn with perfect accuracy all the individual sub-tasks but fails to learn their composition (PERM) within hypotheses H 2 , and H 3 . To achieve perfect accuracy, we need to scale up the dataset size by almost one order of magnitude compared to the H 3 setting (the required number of training samples is equal to the sum of the training samples of all the sub-task datasets). This provides evidence that hypothesis H 4 is the most plausible for PERM too. As for PEN, we study the impact of providing the sub-tasks together with the main task during training. Comparing the performance of LLaMA when given the sub-tasks and not (cf. Figure 3 top right), we observe that LLaMA seems to not benefit significantly from the sub-tasks. We speculate that also in this case this is a sign that the model is not re-using the primitives learned from the sub-tasks to solve the compositional task.Learning the HSS task and MUL tasks. We investigate HSS and MUL (related to [16] ). Figure 3 (bottom row) visualizes the results. As with our PEN and PERM tasks above, we observe that LLaMA does not exhibit strong compositional learning and learns under hypothesis H 4 . Also for While LLaMa achieves perfect accuracy on all the individual sub-tasks, it needs much larger amounts of training data to learn their composition. This observation makes hypothesis H2 (learning the composition requires less samples than the hardest sub-task, green) and H3 (learning the composition requires less samples than the sum of the sub-tasks, yellow) impossible to achieve on every task, where LLaMa seems to always fall into H4 (learning the composition requires more samples than the sum of the sub-tasks, red). Moreover, training together with the sub-tasks does not seem to perform sensibly better than training only on the main task (i.e., w/o sub-tasks).these tasks, it is possible to see that learning the sub-tasks along with the composition task did not significantly improve the performance.We additionally evaluate LLaMA's abilities on decompositionality, i.e., learning a sub-task like PEV after being trained only on the full compositional task (PEN). We observe that, when learning the decomposition task, the models benefit from being previously pre-trained on the composition task (see Table C .10). However, to get maximum accuracy on decomposing PEV from PEN, we need between 25 K and 50 K samples to fine-tune a PEN-pretrained model. This is a significant fraction of the data to learn the PEV task from scratch, making H 1 also implausible for decompositionality on the PEN task. Similar observations hold for decomposing PE from PERM (i.e., a PERM-pretrained model fine-tuned on the PE task; see Table C .11). We speculate that this might be an indication that the model does learn operations relevant for the sub-tasks when trained only on the composite task (since learning the decomposition gets easier), and the learned solution might be to some extent compositional, even if the learning process is not compositional (and very inefficient).In general, compositional learning can be split into two skills: (1) identifying and learning the primitives from the sub-tasks, and (2) assembling the learned primitives in the correct way to construct the solution to the composition task. In Appendix A we focus on (2) and enrich our empirical results with a theoretical perspective; a gist of it is included in the following paragraphs.Pre-training LLMs is sample inefficient in compositional learning. We prove that asymptotically, meaning from an unknown size onwards, feedforward models on gradient descent are data inefficient on combinatorial (including compositional) problems. We use a reduction over the required asymptotic compute time to prove the following result. Theorem 4.1 (Informal Theorem A.7). There exist (many) series of train-test datasets, such that feedforward models on gradient descent that memorize samples will need O(n k ) times more data than an optimal learner. Otherwise, they will not generalize to the test set. k is any positive number and n is the index in the series.Proof sketch. Many combinatorial problems are assumed to be hard to solve. N P hard problems provide an extreme case, where under the P ̸ = N P assumption the solution algorithm requires more than polynomial time. By constructing a train and test dataset where the problem instance of a combinatorial problem (e.g., SAT) is in the training set and the solution can easily be extracted from the labels of the test set, we can make the following reduction: if the learning algorithm finishes in polynomial time, then it cannot answer the test samples correctly, as this would build an algorithm which can solve the problem faster than possible. If our learning algorithm, however, tends to memorize the training set fast and, after memorization, training does not improve model test performance anymore, we can conclude that many samples will be needed to be able to generalize to the test set. At the same time, we can simulate a slow but data-efficient algorithm that extracts the problem instance from the training data, computes the answer, and naturally generalizes it to the test set. The same reduction applies to non-N P -hard problems, in which case the k in Theorem 4.1 becomes bounded. While the classical reduction requires an out-of-distribution test set, the reduction can be made in the in-distribution case as well using hardness assumptions from public key cryptography (shown in Theorem A.9). 
compositional learning via in-context prompting: 
 In this section, we investigate the performance of pre-trained LLMs, GPT-4 and Gemini-Pro, on the PEN and PERM tasks with various prompting methods. Concretely, we operate under the assumption that the models have learned to execute a sufficient set of operations during pre-training, and we test whether these latent abilities can be utilized to accurately solve the tasks given prompts of various complexitites. We experiment with a wide range of prompts, ranging from simple few-shot examples to state-of-the-art methods [26, 27, 28] . Besides the task test accuracy, we also report two partial correctness metrics, match accuracy and termination accuracy. Match accuracy measures how many steps in the output were a correct left-match-right step, regardless of the last word being correct.Termination accuracy checks if the last output word's left neighbor in the sequence matches the input sequence. We include ablations on possible confounding factors (such as tokenization), different task definitions, and number of in-context examples in Appendix D.Prompting to solve PEN. We first provide the models with simple few-shot prompts demonstrating eight input-output examples for the task. The exact format is shown in Figure D. 16 . We find that this is not sufficient to obtain non-zero task accuracy. We then prepend a natural language description of the task to the few-shot prompt as shown in Figure D.17, but we find that this does not change the scores in any significant way. We proceed further by introducing Chain-of-Thought (CoT) prompting [26] .The prompt now consists of a high-level description of the task, eight input-output examples, and a request for the model to perform the task step-by-step (Figure D.18) . With this prompting method, the models still exhibit zero task accuracy. We perform a similar experiment using a more recent and advanced CoT query, analogical CoT [28] , which prompts the model to generate its own analogical CoT [28] , and code interpreter as a multi-round prompting technique [27] ). Despite providing strong hints, few-shot CoT, task description, and without double traps (single only), both GPT-4 and Gemini fail on PEN (0% task accuracy). On PERM, the trend is similar and the main obstacle is multi-counting correctly (cf. the high match accuracy in the last two rows). GPT-4 reaches 42% task accuracy with a hand-crafted sub-task CoT. Gemini-Pro reaches to 9% in this setting.does not help GPT-4 or Gemini to obtain a correct answer (still 0% task accuracy), it more often chooses the correct word to match within its answer sequence, reaching 41% match accuracy. This showcases how susceptible GPT-4 is to adversarial or unfortunate task-irrelevant correlations, also within chain of thought.We also ablate on the newly available o1-preview model from OpenAI. While it cannot infer the task only from examples, it reaches 70% accuracy given a description of how to perform the task and CoT; see Appendix D.4 for more details.Prompting to solve PERM. The same progression of prompt refinements is also applied for PERM, and the results are consistent with the observations on the PEN task. The results are shown in Table 1 . When asked for CoT, GPT-4 does not find a good way to calculate the numbers for each word and tries to determine directly whether a match is to the left or not, something it seemingly has trouble doing. The best performing method is "Sub-task CoT" (Figure D.22) . In this method, we begin by explicitly enumerating all of the words. With this, a left match can be determined by comparing two numbers. We conclude the few-shot examples with an explicit computation of the multicount numbers. This format increases the GPT-4 task accuracy to 42%, which is significantly higher (by 29%) than all of the other results. However, this setting deviates from identifying and leveraging the compositional structure of the tasks, since it rather corresponds to executing a hand-crafted algorithm. Based on the presented results, we can conclude that on the investigated example compositions, in-context learning with few samples is unreliable and fails to compose knowledge from sub-tasks and solve the main compositional task.We experiment with asking GPT-4 to write code, which is a suitable prompting method for our algorithmic tasks. We use the official multi-round code interpreter of GPT-4's assistant API. While it enables GPT-4 to sometimes output a correct solution, it is not systematic and often fails at finding its errors. An example prompt for PEN is shown in Figure D.23.To get a deeper understanding of how the code generation of GPT-4 fails, we investigate 20 random answers from our results of the multi-round code interpreter in Table 1 . We find that the model always outputs executable code and copies the task sequence correctly. While 10% of the answers were correct, 65% of the answers were a wrong answer sequence, and in the remaining 24%, the model tried 10 attempts of code programs and messages in between before being killed. In 35% of the cases, the model initially produced code which results in an infinite loop when executed on the sample. In those cases, the model can fix this problem once (13%), three times (38%) it tries to correct itself until shutdown, and three times (38%) it catches the problem but still outputs a wrong answer. Once it catches the error and gives a correct answer (13%). Further, it is interesting that the model never leverages the example question+answer given (it could verify its solution code with that before submitting an answer). 
related work: 
 Dziri et al. [16] and others [9, 29, 30] investigate limitations of Transformer language models on compositionality with prompting and finetuning. Differently from them, we train state-of-the-art language models from scratch and analyze how well the models can reuse and reorder sub-tasks learned. This gives new insights into compositional learning and provides a view into some limitations of current language model pre-training. Similarly, Razeghi et al. [31] find a correlation between performance and the frequency of how often task instances occur in the training data.Apart from the tasks we use in this work, there exist many benchmarks on compositional learning for language models [3, 5, 8, 11, 21, 32, 33, 34, 35] . However, compared to them, our training setup and synthetic tasks specifically target compositional learning abilities subject to sample efficiency.Many works tackled the problem of improving models' compositionality already [9, 36, 37, 38, 39] . However, their focus is mostly on the improvement of the model's behavior in specific benchmarks, while model-inherent systematic compositional learning remains extremely sample inefficient.Feng et al. [40] point out that constant-size logarithmic precision Transformers can implement mathematical and dynamic programming problems. In order to learn a concept with CoT, the data has to lay out the respective step-by-step solution. Connecting to our bound, the concept needs to be made "obvious" to learn. Various works [17, 41, 42, 43] present approaches to instead allow Transformers to change their depth. This could make the model computationally more powerful as it allows the model to take arbitrary computation time for difficult samples. Our theoretical result instead focuses on fixed-depth Transformers, as they currently are most present in LLMs, and focuses on tasks where the given depth of the Transformers is already sufficient to solve the task.There has been extensive research on the expressive power of language models [40, 44, 41] . Judd [45] already showed that finding weights for feedforward neural networks such that the neural network correctly predicts at least 2 /3 of the training examples is NP-hard in general [46] . Our theoretical bounds work focuses on overparameterized models that memorize. Other follow-ups construct concrete example network architectures being hard to train [46, 47, 48] . Kearns [49] presents results on the complexity of learning, with a focus on learning from distributions, compared to us investigating data and model efficiency. Abbe and Sandon [50] show that decision problems learnable in polynomial time are learnable by gradient descent in polynomial time. Different from us, they give their learning algorithm arbitrarily many samples and distinguish poly-time vs. non-poly-time.7 Conclusions, limitations, and future work Limitations. We do not propose practical ideas to tackle the issues identified with the investigated algorithmic tasks. Hence, it remains for future research to find effective means to incentivize compositional learning in Transformer-based language models, possibly by incorporating more inductive biases towards compositionality in the model architecture or the training procedure. Additionally, while the investigated algorithmic tasks allow to work in a fully controlled environment with limited confounding factors, they still represent a rather limited collection of benchmarks. Its expansion with more natural tasks, as well as the ablation of different sub-task definitions, could strengthen the observations and conclusions proposed in this work.Conclusions and future work. In this work, we analyzed the capabilities of Transformer language models in learning compositional algorithmic tasks. To do so, we formulated a set of hypotheses to characterize the efficiency of a model when learning compositional tasks, from efficient (H 1 ) to inefficient (H 4 ) regimes. We introduced a new set of algorithmic tasks based on pointer execution to benchmark compositional learning in large language models in a more controlled setting. On these novel tasks, as well as other well-known benchmarks from previous works, we observe that Transformer-based language models struggle at compositional learning on tasks demanding to learn the composition of several discrete sub-tasks, making our hypothesis H 4 most plausible (learning the compositional task requires more samples than the sum of those required to learn the individual sub-tasks). Further, we show (also theoretically) that learning certain (compositional) concepts with feedforward models on gradient descent is very data inefficient, adding further support to reject H 1 -H 3 . Finally, we empirically rule out also the possibility that these tasks can be learned in a few-shot fashion by state-of-the-art LLMs such as GPT-4 and Gemini-Pro. This evaluation of current state-of-the-art Transformer language models may provide some directions to improvements in compositional capabilities which would help models to be more reliable and improve on complex algorithmic structures like reasoning or mathematics. Addressing the current limitations of this work might also be an interesting avenue for future research.A Feedforward models on gradient descent can only learn the obvious 2As in our empirical results, we focus on model size and dataset size, not compute, which e.g. is the focus of [51, 52, 50] . This has the rationale, that concepts or tasks which do not have unlimited amounts of data and are hard to learn, can in theory still be learned while gradient descent on feedforward models will be limited. In particular, in this part we show classes of tasks that are learnable from a single sample each (i.e., learnable within hypothesis H 1 ), but on which feedforward models trained with gradient descent will learn within hypothesis H 4 , needing up to exponentially many samples. See also From complexity theory, we know that finding the proof of membership of a string in a language is in general less efficient than verifying its membership given a proof. We use this structure: Definition A.1 (K). Let L be any recursive decision problem with solution in space O(n) and being verifiable in time O(n). Let us look at all algorithms solving L and let k(n) be a (high) lower bound of them. We denote K to be the set of choosing one upper bound k(n) per such decision problem. Some examples: Assuming the exponential time hypothesis, SAT solution algorithms need exponential time (i.e. k(n) can be an arbitrarily high polynomial), and verification is in O(n). Under the same assumption, the edit distance algorithm needs Ω(n 2-ϵ ) for any ϵ > 0 while being verifiable in O(n) [53] . Usually, no lower bounds are proven for such problems, but the fact that we can not find faster algorithms makes assumptions reasonable. Definition A.2 (Concept, Concept Class). A concept C = (U C , f C , n C ) consists of an algorithm f defined on a set of inputs U and a natural number n C . We call n C the "difficulty" of C. A concept class C is an infinite set of concepts where each n ∈ N occurs only finitely many times.The intuition: A concept class is a set of concepts that are connected by some common basis, e.g. they all pose certain challenges (e.g. finding a formula assignment) to an overarching problem to learn (e.g. the SAT problem). We need a class of such problems because complexity theory makes asymptotic statements.Similar definitions are used by Kearns [49] , here we use a slightly different definition of concepts as functions instead of subsets of an object set to better suit today's applications. Definition A.3 (Application of a Concept). Given a concept C = (U, f, n), an application of C is a pair (T, E) of nonempty sets of samples (i.e. input-output pairs) of f . We call T the training set and E the test set or examination set.Here we deviate from classical learning theory in that we do not define a distribution. Instead, we define the more general case of having a training regime and testing regime since we focus on systematic generalization. One can additionally require E and T to be statistically dependent to recover classical train-test distributions, as we, for example, show in Appendix A.5. Definition A.4 (Learning Algorithm). Let S denote the set of all finite datasets (i.e., sets of inputoutput pairs) and Θ the set of all input-bounded and runtime-bounded algorithms. A learning algorithm is an algorithmL : S → Θ. We say a L learns a concept C = (U C , f C , n C ) on a dataset T C , if M(x) = f (x) ∀x ∈ U with M := L(T C ).Let TIME(A, x) denote the runtime of an algorithm A on an input x. For a concept class C and a learning algorithm L, we denote:EQUATIONI.e. the maximum inference runtime on a test sample for concepts of difficulty n 0 . Theorem A.5. For each k ∈ K there is a (different) concept class C, with applications (T C , E C ) (i.e., train and test datasets) for each C ∈ C, with the following properties:1. There is a learning algorithm L * that can learn each concept from a single sample in O(k(n C )) time and withz L * C (n C ) = O(n C ) 2.For any learning algorithm L, L one of the following will hold:• "L does not learn": L is not able to learn infinitely many concepts in C.• "L learns during inference":With M = L(T C ), (x,y)∈E C TIME(M, x) = Ω(k(n C )) • "L does learn": TIME(L, T C ) = Ω(k(n C ))The intuitive claim of this theorem is, that there are concepts, which require a Ω(k(n C )) time (i.e. a lot) to learn while being fast at inference.A special case for SAT is carried out in Appendix A.3 and the general case in Appendix A.4. The proof focuses on training on a minimal dataset (one sample) and testing on an out-of-distribution "exam" set. For completeness, in Appendix A.5 we provide a proof for similar claims in an in-distribution training-testing setting.We now introduce a memorization assumption which assumes that our learning algorithm memorizes fast.Definition A. T ′ C = G(T C ) with G running in time o(k(n C )): If z L C (n C ) = o( k(n C ) n C ), then L needs Ω( k(n C ) z L C (n C ) ) many samples to learn each concept C = (U C , f C , n C ) ∈ C. 2.There exists a learning algorithm L * learning each concept from a single sample withz L * C (n C ) = O(n C ).We use the notion of G (which is an algorithm free to choose) to make sure that bigger datasets do not make things "obvious", that is, leak too much information about the exam E C .If we think about the PEN task, it is a combination of sub-tasks, i.e., P EN (x) = Cpy(P E(RCpy(x))). There are combinations for three of the sub-tasks chained together. Already in such a restricted setting, learning the task from scratch is extremely inefficient, requiring a multiplicative factor of one million samples more than the discrete optimization algorithm described in Appendix B.2, which in this case corresponds to the optimal learner mentioned in Corollary 5.7. This confirms the outcome that our theoretical framework would predict, i.e. LLaMA fails at learning from few examples, although the existence of the optimal learner shows that it would be possible.The theory allows us to extend this result beyond the limit of the empirically verifiable. When more primitives are available (e.g. in general-purpose datasets like The Pile [54] , finding the right functional composition of the sub-tasks quickly becomes a computationally hard combinatorial task. With such problems, the theory says that plain gradient descent will tend to just memorize the few samples of the compositional task, instead of (combinatorially) finding the right composition.Nasr et al. [55] show that one can extract more memorized data from larger models. Tirumala et al. [56] have shown that larger language models memorize faster than smaller models. Based on this, we can conservatively assume a constant number of steps for memorizing the fixed-size answer to a sample. This fits definition A.6 for a learning algorithm L F learning with (growing) constant-depth feedforward models, depending on the input size in the training data, as one gradient step has the time complexity of a forward pass. Therefore, Corollary A.7 can be interpreted as follows: There are classes of concepts, such that to learn them reliably, either the feedforward deep learning model needs to be unfavorably larger than needed for inference (z L F C (n) >> n), or the data inefficiency is very high (by a factor k(n)z L F C (n)). Note that in practice, memorization does not necessarily mean, we stop optimizing, here we implicitly assume that after memorization, nothing useful happens anymore, e.g., the gradient signal magnitude is 0 and the model does not change further.Much research has been done on the complexity of various problems. Here we want to point out a few further concept classes that need significant computation to learn and therefore underlie the above statements:A fundamental capability for safe, explainable, and intelligent systems, is to be able to infer causal relationships. It has been shown, however, that learning such structural causal models is NP-hard in the number of graph nodes [57, 58] . Therefore: Let our complexity class contain the functions applying all structural causal models and generate observations for each concept. Now let us test those functions by an exam after training (i.e. by just asking for the structural causal model). Then, for this specific concept class, Theorem A.5 and Corollary A.7 hold for k(n) being a super-polynomial function.Further, it has been shown [59] that given a structural causal model, it is NP-hard to infer whether one particular event always leads to another. Such inference might be important for a few selected cases. Again, by constructing a concept class containing functions such that the structural model is given or inferable and the always-cause is asked or needed for predictions in the inference phase, it follows by Theorem A.5 and Corollary A.7 that learning such concepts requires a lot of computationand many samples for feedforward neural networks although theoretically unnecessary.For brevity "algorithm" refers to always terminating algorithms. Let us fix a standard random access memory computational model. We also fix a universal encoding and decoding function ENC, DEC that can encode/decode any algorithm or object we define below (imagine, for example, a digital processor model where everything can be encoded in 0s and 1s). From now on we omit all encodings and decodings and instead use defined objects and their encodings interchangeably for the sake of simple notation. . Gradient Descent on Feedforward Networks under the assumption of constant-stepmemorization however, will only be able to learn problems as hard to learn as they are during inference. Therefore, the model size needs to be much larger than necessary, or the training samples need to be much larger than necessary, or gradient descent will have trouble learning.For a better reader's experience, let us restate the theorem:Theorem. For each k ∈ K there is a (different) concept class C, with applications (T C , E C ) (i.e., train and test datasets) for each C ∈ C, with the following properties:1. There is a learning algorithm L * that can learn each concept from a single sample in O(k(n C )) time and with z L * C (n C ) = O(n C ) 2. For any learning algorithm L, L one of the following will hold:• "L does not learn": L is not able to learn infinitely many concepts in C.• "L learns during inference":With M = L(T C ), (x,y)∈E C TIME(M, x) = Ω(k(n C )) • "L does learn": TIME(L, T C ) = Ω(k(n C ))For simplicity, we first prove a special case where k is the minimal runtime of a SAT (3-satisfiability) problem (i.e. given P ̸ = N P exponential in n).Proof. Valiant and Vazirani [60] have shown, that given a formula which is either uniquely satisfiable or not satisfiable, deciding this is NP-hard. From this follows, that given a uniquely satisfiable formula, it is (assuming P ̸ = N P ) not possible in polynomial time, to find a proof for it, i.e. the unique satisfying variable assignment (this holds, because checking such a proof is fast).We choose C to be a set constructed from the set of unambiguously satisfiable SAT formulas: Given a uniquely satisfiable formula A and the unique solution y A , let U A = {A, 1, . . . , |y A |} be the set containing the formula and the variable names. Let f A (A) = 1 and f A (i) = y A i . Our concept is now C A = (U A , f A , |A|). We choose the training dataset of the concepts to be {(A, 1)} and the examination dataset to be {(i, y A i )|i ∈ 1, . . . , |y A |}. This means we train on a uniquely satisfiable formula, and the test set tests whether the model learned the unique solution to it.We now construct the learning algorithm L * learning C ∈ C from one sample. Let us fix an arbitrary(U C , f C , n C ) ∈ C.Given the training dataset T C = {(A C , 1)} corresponding to C, L * builds an algorithm M of the form:• M(A) = CHECK(A, x) for a formula A of length n C where x, |x| ≤ n C is a stored (i.e. hardcoded) constant. CHECK returns 1 iff x is a satisfying variable assignment for the variables of A. Note that n C can be inferred by L * as it is the length of the single sample in T C .• M(i) = x i , i.e. the i-th variable assignment.• On all other inputs, M can implement any algorithm (e.g. some pre-trained knowledge).Note that M has a linear running time in n C on all samples in T C and E C . Now, L * finds the satisfying variable assignment x (using the minimal-runtime algorithm) for A C and stores it in x.Note that this procedure runs in k SAT (n C ) for k SAT (n C ) being the minimal runtime for finding a solution to uniquely satisfiable formulas (which is assumed to be exponential under the exponential time hypothesis). Now to the second step: Assume there is a learning algorithm L and assume that it can learn all concepts except finitely many and do so in o(k SAT (n C )) (i.e. strictly less) time and with M = L(T C ) needing o(k SAT (n C )/n C ) time on each sample in E C . Then one can simulate the learning setting to find a solution to a formula A, n := |A| (except finitely many times): First, simulate L on {(A, 1)} to obtain M = L({(A, 1)}). Then, simulate M on all variable indices i as inputs to obtain the satisfying assignment y A . This algorithm findsy A in o(k SAT (n)) + o(n * k SAT (n) n ) = o(k SAT (n)) time, contradiction.This proof is analogous to the special SAT case. We recommend the reader to read the special case first.Proof. Let k ∈ K. Let P be the problem k corresponds to (e.g. SAT). Let A s denote the solving algorithm for P running in time k(n), i.e. an algorithm that computes a solution to each instance of a class of problem cases, where the solution is in O(n) space. Let A c be the checking algorithm that can verify if such a solution is correct, running in O(n). We choose the concept class C to be a set constructed from the set of positive instances in P (e.g. in the SAT special case this would be a uniquely satisfiable CNF formula): Given such a positive input instance X, let U X = {X, 1, . . . , |A s (X)|}. Let f X (X) = 1 and f X (i) = A s (X) i . Our concept is now C X = (U X , f X , |X|). We choose the training dataset of the concepts to be {(X, 1)} and the examination dataset to be {(i, y X i |i ∈ 1, . . . , |y X |}. We now construct the learning algorithm L * learning C ∈ C from one sample. Let us fix an arbitrary(U C , f C , n C ) ∈ C.Given the training dataset T C = {(X, 1)} corresponding to C, L * builds an algorithm M of the form:• M(X) = CHECK(X, s) for a problem instance X of the problem P with |X| ≤ n C . |s| = O(n C) is a stored (i.e. hardcoded) constant. CHECK returns 1 iff s is a proof for the problem instance X (which exists by Definition A.1). Values for s will be candidate solutions for X, and L * will search for the solution.• M(i) = s i , i.e. the i-th value (e.g. bit) of s.• On all other inputs, M can implement any algorithm (e.g. some pre-trained knowledge).Note that M has a linear runtime in n C on all samples in T C and E C . Now, L * computes s * = A s (X) (i.e. the solution to P) and stores it in s, i.e. s = s * . Note that this procedure runs in TIME(A s , X) time (which can be k(nC ) if k(n C ) is tight).Now to the second step: Assume there is a learning algorithm L and assume that it can learn all concepts except finitely many and do so in o(k(n C )) (i.e. strictly less) time and with M = L(T C ) needing o(k(n C )/n C ) time on each sample in E C . Then one can simulate the learning setting to find a solution to a problem case X ∈ P, n := |X| (except finitely many times): First, simulate L on {(X, 1)} to obtain M = L({(X, 1)}). Then, simulate M on all solution indices as inputs to get the proof y X for X. This algorithm finds yX in o(k(n)) + o(n * k(n) n ) = o(k(n)) time, contradiction.A.6 Proof of the corollary A.7Corollary. Let k ∈ K. Then there exists a concept class C with applications T C , E C such that:• Any constantly memorizing learning algorithm L learning on an (arbitrary) augmented dataset T ′ C generated by a generatorT ′ C = G(T C ) with G running in time o(k(n C )): If z L C (n C ) = o( k(n C ) n C ), then L needs Ω( k(n C ) z L C (n C ) ) many samples to learn each concept C = (U C , f C , n C ) ∈ C.• There exists a learning algorithm L * learning each concept from a single sample withz L * C (n C ) = O(n C ).Proof. Let us fix k ∈ K and define our concept class C with applications E C , T C as given by Theorem A.5.The second part follows immediately by Theorem A.5.The first part: Let L be a constantly memorizing learning algorithm L with a generator G. Assume thatz L C (n C ) = o( k(n C ) n C ) and, L learns with |T ′ C | = o( k(n C ) z L C (n C ) ).Then by Definition A.6, there exists a constant B such that for every C ∈ C, L runs in time:B * |T ′ C | * Z C ≤ B * |T ′ C | * z L C (n C ) = o( k(n C ) z L C (n C ) * z L C (n C )) = o(k(n C )). Therefore, we can summarize that G runs in o(k(n C )), L runs in o(k(n C )), and M = L(T ′ C ) runs in z L C (n C ) = o( k(n C ) n C). This can't be, as Theorem A.5 states that we need more computation time.In this Appendix section, we expose more details about our definition of the set of sub-tasks S and the properties that it shows. In particular, we characterize it through different angles, namely:• atomicity: each sub-task is an atomic unit roughly corresponding to a basic block of operations in the equivalent procedural programming language.• minimality: among all the possible definitions of sub-tasks, we define S to be the minimal set of sub-tasks, where every primitive operation is made observable in exactly one sub-task.• usefulness: the defined set of primitives is useful to learn the compositional task. We validate this in our experiments on task de-composition (Section 4.2), which shows that the model learns and compose the given set of primitives when it is trained on the full compositional task.• uniqueness: by imposing independent observability on the different primitives, we can relax the constraint on the bijection between primitives and sub-tasks, allowing for sub-tasks that contain more than a single primitive. As a result, the definition of S is not unique. However, this does not undermine the validity of the investigation, since we are measuring a relative phenomenon. The inefficiency of Transformer-based language models that we observe is always relative to the considered set of chosen sub-tasks. However, considering all the properties above, we speculate that similar results could be also measured for alternative definitions of the sub-tasks set S.In addition to the task description in Section 3, there are some additional constraints, visualized in Figure B .5:1. The (yellow) neighbors of the green chain build a chain themselves, starting at the second word in the sequence (i.e. the first yellow word).2. The full sequence is at least double the length of the green matching sequence. With all other 'free' green words, we build another matching sequence starting at a random "free" green position (we call it the "free" matching sequence, see the blue arrows in Figure B.5). This is important because then the model cannot easily tell apart the green positions of the correct matching sequence with the green positions of the "free" matching sequence without either matching all green tokens from the start or looking at the answer words and starting matching from their left neighbors.3. Each yellow word next to a true green matching word (except the terminating word in the yellow matching sequence) has a doppelganger (which we also call attention trap) next to a "free" green word. We add this to "confuse" the model: since the model learns to match words to words, it could be tempted to match yellow words, which would give it the wrong order of neighbors. To make them distinguishable in the answer, we define the doppelganger to match equally to the previous and next word but have a different "data" number in the middle. The (yellow) neighbors of matched green words build a matching sequence themselves (in their own order) and have exactly one matching outside the neighbors each (except the last yellow word in the order of the yellow sequence, which has no matching). Therefore, each yellow neighbor except the last matches to two words in the sequence. The blue arrows are over the remaining green positions (which are not part of any answer), which also build a matching sequence. Those additional constraints remove shortcut solutions. Figure B.6: How a language model with next-token-prediction can solve the PEN task. Take the most recent word in the answer, find its left neighbor ("left"), find the match ("match"), and retrieve its right neighbor ("right"). This corresponds to the sub-tasks RCpy (e.g., in this task, the model has to find left neighbors), PE, and Cpy. The data efficiency in de-compositionality (see Tables C.10, C.11) provide some evidence that this is the natural way a model solves the task when being close to 100% performance and without being trained on the sub-tasks.We use a batch size of 384 samples, which corresponds to ca. 250 K tokens per batch for the PEN task and 50 K for the PERM task. Our 150 M parameter model contains of 12 layers and a hidden size of 1024. The learning rate is 10 -4 , as in the original paper [2] .Our discrete learning algorithm which can learn the PEN task from a single example is a 2-gram model over 11 words resulting in 121 parameters with 8 values each. This results in a search space of size 1.9 * 10 109 . Each value is an action function that manipulates the current word in the forward pass of the model (at the beginning of the forward pass it is set to "error") and gives back one of the 11 action outcomes. The last two action outcomes (initially (BOS,BOS)) result in the next 2-tuple determining the next discrete parameter. As this execution could loop or run over many parameters, we limit the depth to 12. The actions and their outcomes are:• EOS: retrieves the eos constant (outcome: EOS)• LAST-OUTPUT: retrieves the last output word (or the start word if it is the beginning of the answer) (outcome: LAST-OUTPUT) • MATCH: matches, if there is no next match, this will return error (outcome: MATCH) • LEFT: get the left neighbor of the current word (outcome: LEFT) • RIGHT: get the right neighbor of the current word (outcome: RIGHT) • IS-START: is it the beginning of the answer (outcomes: IS-START-TRUE, IS-START-FALSE) • IS-ERROR: is the current state error (outcomes: IS-ERROR-TRUE,IS-ERROR-FALSE) • OUTPUT: output the current word (outcome: OUTPUT)• For an entry point we define an additional action outcome: BOS The search algorithm uses a simple hill-climbing heuristic with restarts towards getting as many answer words in the sample right as possible. To search more effectively, we add a penalty to changing the same parameter over and over. The most challenging part of our novel pointer execution tasks is to learn the left-match-right structure, which is easily found by this algorithm.The numbers are visualized in Section 4. Each row in the tables C. C .10, decompositionality significantly improves data efficiency compared to training a model on the finetuning task from scratch. For learning the task to full performance, however, it still seems to need more than a low constant number of demonstrations (5-20 K), making the H 1 -equivalent "A Transformer language model learns a decomposition with a constant number of samples" rather implausible for decompositionality.We ablate a variation of our model architecture based on the Universal Transformer (UT) Csordás et al. [61] and the more recent Hyper-UT [17] , for both of which there is evidence of better compositional generalization than the original Transformer. For instance, a UT-style transformer displayed good performance on compositional tasks like SCAN Csordás et al. [61] . The model based on UT reached a similar performance as the original LLaMA model, i.e. a behavior that could be classified in H 4 .We then also experimented with a Hyper-UT-style LLaMA, based on the aforementioned Hyper-UT work [17] , in which each layer selects its weights from a common weight embedding pool to realize a parameter-efficient model. This model consistently achieved a lower accuracy compared to LLaMA on a large set of small algorithmic tasks. Thus, we chose not to systematically explore its performance in a more challenging compositional algorithmic setting. Unlike open-source models, such as the LLaMa, closed-source LLMs do not allow to customize the tokenization process. Hence, tokenization could potentially represent a major confounder for our prompting experiments. If fact, an erroneous mapping between words and tokens would inevitably undermine the ability of the model to correctly perform matching operations in the input sequence, making it impossible to successfully reconstruct the correct path in pointer execution tasks. In this Appendix section, we provide more details on a set of control experiments that were designed to ensure that this phenomenon did not play a role in our empirical evaluation.As a preliminary step, we ablated in our experiments different strategies to structure our input components. However, we found that alternative designs for the tasks structure (e.g. LL-N-LL, where L represents a lower-case Latin letter and N a one-digit number) were always detrimental for the task accuracy compared to the current sequence design (i.e. LLNLL). To ensure that the input sequences of our pointer execution tasks were effectively tokenized as expected, we run some quantitative experiments with GPT-4's open-source tokenizer (tiktoken). Unfortunately, we could not find an open-source tokenizer for Gemini-Pro; the available token counter only provides limited information about the actual tokenization.Analyzing the GPT-4 tokenizer results, we found that the digit delimiter ensures safe splitting within a word in 100% of the samples, i.e. LLNLL always yields [LL, N, LL]. Additionally, we observed that 13.2% of the 2-grams were split into two different tokens (e.g., bq is tokenized to b and q), which may affect the attention mechanism. As an additional experiment, we removed these 2-grams from the dataset. However, removing the "splittable" 2-grams did not result in an improvement of the performance (the accuracy decreased from 0.19 to 0.05 on PEN) when using the best-performing prompting technique with GPT-4 (Code Interpreter).We additionally designed a natural variation of the PEN task, dubbed Natural-PEN, where we replaced the synthetic 2-gram sequences used for the matching in the original tasks with 3-gram, in-distribution, natural English words. Natural-PEN inherits a similar structure of the components from the original PEN task, WNW, where W in this case are 3-characters English words. In practice, we filtered all valid 3-gram words from Scrabble3 that were translated to a single token when using GPT-4's tokenizer. This gave us a set of 707 words (out of the original 1338 words). Similar to the experiment in the previous paragraph, we find that the GPT-4's performance using the best prompting techniques does not improve on this in-distribution, natural English words, yielding even a lower accuracy on Natural-PEN (Table D only, it achieves much higher accuracy when given a description of how to perform the task. Our hand-crafted step-by-step solutions achieve higher accuracy than the solutions that o1 finds when asked for Chain of Thought (CoT) only.In this section, we include some exemplary prompts that were used in the PEN and PERM experiments with pre-trained LLMs. We start with the vanilla few-shot (8) prompt, shown in Table D . 16 .EXAMPLE: xv ke vu7bh sb0fz xy5ih eo7sf ay7of xd3nj zs7bt eo1sf jn6yc xd5nj od3nk br2ny yc2pr ls5sg nv1zs sb5fz uy7vu sf1zv bh6ia sg5dg ux6oc zv4xd ya1yk br5ny wc4xy ke5fm jw1dx ny7sb wq2mm fz6eo nk2nv sf5zv pr3ya fz4eo yk0dk fm4br oc4wc nj0ls ih1uy di7fw mm2pq zv7xd of7wq nj4ls xv7gn ls6sg dx0ux vz7uc ah7od sg4dg sn2jw ae5ce ia7jn zw4ed bt5ay fm6br pq6kw ny3sb gn4ah ke0fm ANSWER: ke ls6sg ke0fm sg4dg br2ny sf5zv sb5fz eo1sf fm6br xd3nj nj4ls fz6eo zv7xd ny3sb EXAMPLE: wk qp ld2ki lt1ui te3ob et4mm ss1hi lt0ui ki3ay ad2dh zk1cc cl6lt zz3zs cl1lt hi3ct ap4ys sf1sz bc4yh ct4gf gn5ap mt5zd mm5gn sr1ne yh3et up0vl lu2cl no1ps ys3lu vm6us et6mm us4ha qp1ad zd6sf dh7bc ps3ld bc6yh sv5ch ad4dh qe4hd mm6gn ha0qe dh3bc vl3mt ys4lu ob2zk qp0ad wk7zz lu0cl ch7up ac2hh ne1te qo4qz cc2rp gx2yq xv3vm gn4ap rp2ss sd5gc zs6no yh4et tl7sv xs5jm sz0sr ww1rb ay6xv ap2ys ANSWER: qp lu0cl cl1lt yh4et ys3lu bc6yh lt1ui ad2dh ap2ys gn4ap et6mm qp1ad dh3bc mm6gn EXAMPLE: fy kn fz2jy st6zr wk4hz zo3st gz0nt ri2ru dt0rh ri4ru kq0lt st0zr pp3da ru2io lw0vk zo1st sx5xe ej2sj er1fz kn2ej fd2pp ej6sj mc7gs io0zo si4lp ns1jr xe6nb zn5ns vk4fd sj0im lt7lw kn4ej nb0lg sj2im lg0qi ru6io gs7yf zr3zn jy1wk im1ri fy5er ns7jr qi5dt io1zo yf7gz zn4ns nt6do im6ri lp6mc mk2ym do2kq zh3vh ox5si fk0sk hz3sx zr2zn ANSWER: kn ns7jr kn2ej st6zr im1ri zo3st zr2zn ej2sj zn5ns sj2im ru6io io1zo ri4ru EXAMPLE: xr ql hq6za co0gt yv6md sk5zi xr3kq zi0co zl4om mc7ha gy3ej xj0qp ud2hq ha0km yu7xa gt6nb rb4mi xj4qp li3ib km1cf lj2ek qp6sk ib4dv ha5km fc5gy gx1xd om7hb tx1mc al0lw gt4nb lw5fc xd6nj ek1tr nb5tx rz3yv ql1xj xu4it km0cf mi5vo gx5xd xa1in xd7nj vo6xz tx6mc dv4al co6gt kq2li sk6zi tr1zl cf7gx md0je mc4ha hh7rz cf2gx gp7yu zi2co je0gp nb0tx in2rb qp0sk it7hh lq4cl ej6lj ql0xj xz0ud sa2sc ANSWER: ql zi0co sk6zi km1cf ha5km co6gt gt4nb xd6nj gx1xd xj0qp ql0xj qp6sk nb5tx cf7gx mc7ha tx1mc EXAMPLE: bn xy fv6wc tn0jp sk2qb vy7mw od1hf ju6vs xf1kc xy6zn ue0dr zn7vy ya5fv ls4tn qb2km tn6jp yw6yn zn6vy pc5yw jp4vc af6rc mw7ls hf4om mw5ls kc4wt vv7ju hk3hn vy4mw hn3af vc3vv wt6pc vc6vv yn1sm ls2tn pe4pq jk3gb km7ep zv5gv om4vk mb7mz dr7hk jp0vc ep2pe is5ie sm2sk th7ba vz3ya ju1vs wc2ue xy2zn at5xd wq2wv bn5vz vv4ju vk3at gr0xr xd2xf up2vq ANSWER: xy vv4ju ju1vs ls4tn tn0jp xy2zn zn7vy jp0vc vy4mw vc3vv mw7ls EXAMPLE: kt nn fz2kv rv6wb kh6vu js4wk et7lx zk0sb ie3zb wb6mx vu5et nn7zx zb6zn pp3js kv4hk gt6rv bf4vr mx3zk sv5ok zk6sb gk1rx pp1js vg5kh wk5gt vr3fz zx2pp zu4ac nn3zx qe6rl gt4rv ac2tp rv5wb kt6zu sb4ic hk2xe sb1ic rx1xm mx6zk zn6vg az3vp xm4qe zx0pp dm1lt hl4li ok0ja wk3gt bc6bf tl2eb jn7dm ve3jl lt1bc tg5gp tp6sv wb4mx xe6ie ot2pj ja6gk js7wk ANSWER: nn sb4ic nn3zx rv5wb wb4mx zk6sb wk3gt js7wk pp1js mx6zk zx0pp gt4rv EXAMPLE: pq gg vs1dy cr4yf xt5kz gg1gn tg0fn gn4cr pq4jj tc1ts qh0ek yf2tc sk2al tc4ts jl3xi cr3yf ub1zh ts7lh tp2vb ex4px kz2kn gn3cr ez7up gg4gn dn2ez jm4ex ek1sz lh0eu kn5cg jm6ex jj5fp yf3tc il5wn eu3jm bd5fc ex7px wn5yw ir0xf fc3vs lh1eu fp0bd eu2jm fn6jl pa4zf zh4ku ep6jf dy4xt ts6lh vc5sk dv5nw sz2ub di7yp vb2dn tk0as ku0km mw7mx km0tp hi3pl bg4il nl1hv xi0bg kk2ao al1tg dx2ca up4vc ru0dc ANSWER: gg tc1ts yf3tc eu2jm ex7px lh1eu cr4yf ts6lh gg1gn gn3cr jm6ex EXAMPLE: if xe gw0is zl5jz if2mv wa5xs vs1st nz2wc ox0qs ko5xq xj4ue ko3xq hx7ym ca6zl is0bf xq6ed gs7ga xs0yg mv5ox ca5zl bg0bk xq1ed ry2gw rt7ca bf7lx xe1wa ym3vs xs7yg qs1ee wc6cb pe6ag ed3nz xn4dt zl7jz on6oc xe7wa ps0xj yg7ko st5ps cb2rt ag3xn wc2cb bk7hx rt2ca ee1ry cb4rt ra4on wa2xs lx7az ed0nz dt1ra be3hb rc4gs nz5wc az7rc yg0ko ue2pe or4fg ANSWER: xe wa5xs ca5zl ko5xq wc6cb cb4rt rt7ca zl5jz xq6ed xe1wa ed0nz yg0ko nz5wc xs0yg YOUR QUESTION: vq sk zg5gr ne7vc co7os hc6cv pq3ss dp4je vq3sx pu0dp wn2co vc6hc dw5vy ne6vc vy0oe gp6zm ka1rw vc1hc tz5mx je3hy ab2pq pu7dp oe3ka on5is lf1ju hy6gp gr5jp gp5zm os2dq sk6ne dq7cn on0is ju0qq cv2on mx1mb is0pu sx1wn cv1on rw4sz je6hy jp1tz dp0je io1lf is4pu ss5dw sk2ne sz4ij hc1cv qq6ab uk0af cn4zg hy2gpClearly mark your answer by writing 'Answer: <your answer>' as last line.Table D .16: GPT4 and Gemini prompt for Pointer Execution's Neighbor (PEN) task with only few-shot examples of the task. The tasks are encoded so that every word start and word end of a word in the input are encoded as separate tokens, so a model can pattern-match the respective token to do the matching operation. Table D .22: GPT4 and Gemini prompt for Pointer Execution Reverse Multicount with description and sub-task few-shot chain of thought (Sub-task CoT). This chain-of-thought makes sure that the language model can easily execute all operations. In our experiments, for GPT4 to reliably determine whether in which order two words occur in a sequence needed enumeration.In Table D .23, we include the prompt that was used for the code interepreter.I give you a sequence of words. Each word has four characters plus a middle, words are separated by spaces. Start with the leftmost word. Output its neighbor. Then, match the last two characters of the current word (i.e. not the neighbor) to the word starting with those two characters. Again, output the neighbor. Do this until your current word (not the neighbor) has no match anymore. EXAMPLE: bn oi fe6zt vj4ks yk3us fi6mk lo0ox yd5pt dc2rk mk3vj wj2fe wk0bm yo6kt ks5wk ox1yk wk6bm gc7kj oi1fi ah7gc ks0wk vq6ah gv7yd as4vq bm3gv vs3ho vj0ks kj0au yd6pt bn7dd mk2vj qg5lx pt4xv ho7lo oi5fi au7qg fi0mk zt3as nd4zd kt1vs gv0yd lx2dc fa0ut dd5ry pt3xv ry7yo bm0gv ANSWER: oi mk2vj pt3xv bm0gv ks5wk gv0yd vj0ks oi5fi yd5pt wk6bm fi6mk YOUR QUESTION: bc ek vq7ze pe7mu vu5pf nu1sb zg2uf vd5vn ep3qt ek2oj ng6ep ig7is bc4sx is2nu sx3lq pe2mu lq4oo sb1vd wh0lw oj7ax qb2vq mu4xm hq6eu nu0sb pf3qb ax2pe yh7bm sb0vd gz5vu vd1vn fa5sj oj0ax eu0zg ek4oj ze3gx xm3ig oo5hq mu7xm bp7gz is7nu lw3ng vf7ko sj3jq xm4ig xp0fa ax6pe gx3wh qc6tc uf5xp ig3is qt5yh rs5lk Reason step by step. Then, use the code interpreter to solve the task. Clearly mark your answer by writing 'Answer: <your answer>' as last line.Table D.23: GPT4 prompt for the Pointer Execution's neighbor task with code interpreter. Table D .24: GPT4 and Gemini prompt for Pointer Execution Reverse Multicount with description and fewshot-chain-of-thought we found to be similar to the chain of thought the model chooses naturally. The 0s in the input words are inserted to make sure, GPT-4 encodes each word start and word end as one token and therefore can match more easily.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification:We open source our code at https://github.com/IBM/ limitations-lm-algorithmic-compositional-learning. Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Details on the training procedure of our models are included in Appendix C.1.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: To make our statements, a certain trend is shown (high data inefficiency). Multiple runs could enhance the precision of our data points, but it seems irrelevant to our main statements, showing trends of data inefficiency and is also handled this way in other papers training LLMs from scratch.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: This information is inferable by looking at our hyperparameter settings, e.g. in C.1 and depends on the precise framework used (e.g. Pytorch Lightning), which we refer to other resources.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, agree with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: To the best of our knowledge, our work has no societal impact besides advancing knowledge on compositionality in LLMs.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: To the best of our knowledge, our work has no societal impact besides advancing knowledge on compositionality in LLMs.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: The data generation hyperparameters are given, and the code is simple to use.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: We do not use crowdsourcing or human experiments.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: We do not use crowdsourcing or human experiments.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Obvious here means: either present in many samples, or simple to extracthttps://scrabble.collinsdictionary.com/word-lists/three-letter-words-in-scrabblehttps://openai.com/index/introducing-openai-o1-preview 
 
 Appendix:  


Decision: This paper presents empirical and theoretical evidence that Transformer language models are inefficient learners of compositions of tasks, in the sense that they require more training samples than the sum of the samples required to learn each task individually. The reviewers identified several strengths, including
1. Well-designed problems that are carefully constructed to shed light on an important question
2. Through empirical experiments using both open-weight and API-access models
3. Clear writing and a very thorough literature review that places the results in context

Two of the reviewers raised two significant concerns. First, qmuR and Fa35 felt that the contrived tasks were not realistic. As the authors replied in their rebuttal, real world data introduces many confounders and controlled experiments are valuable for understanding the limitations of a model. Further, the authors emphasized that the "algorithmic" nature, i.e., having a precise, formal specification improves on previous work studying composition, and extends prior work using the pointer-based tasks that did not explore composition. The AC agrees with the authors on these points.

The second major concern was about experimental details, including concerns about tokenization as a confounder. The authors addressed these concerns in their rebuttal and they are encouraged to include the additional investigations in the final version of the paper.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: 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?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: The authors discuss some limitations, but do not directly address the generalizability of their findings to natural tasks subtasks composition.
paper_summary: 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.
strength_weakness: strength_weakness: 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: questions: Q1. Is the PEN dataset only corresponding to one underlying program?  
Q2. What are the insights of PEN and PERM these two datasets?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: See weaknesses.
limitations: limitations: Limitations of not solving the issues raised are addressed in the paper.

Comments: comment: Thanks for your additional comments on our rebuttal, we are glad to hear that many of your questions were clarified and that you are even more confident about your positive judgment on our submission.

Regarding the synthetic nature of the experiments, we understand your concerns and we agree that the scope of the additional experiments on Natural-PEN might be limited if the goal is to evaluate to what extent the pre-training can improve the compositionality of these large models. This ablation was mostly proposed to check whether the use of "rare" tokens in the tasks had an impact or not on the performance.
We also agree that the design and evaluation of a similar testbed that simulates an in-distribution task will be valuable future work, but at the same time we still strongly argue for the importance of an evaluation on a synthetic setting which allows full controllability (see also the discussion on this with reviewers teuc and Fa35).

Once again, thanks for your positive and constructive feedback and for your involvement in the review process, which we deeply appreciate.
Thank you for the detailed responses. 
Many of questions were responded to and clarified and I'm more confident in my evaluation. 
I would like to note that my main concern which is the synthetic nature of the experiments remains unanswered. I appreciate the authors attempt to provide additional experimental results in the short rebuttal time. However, using English-words as tokens does not make it "in-distribution" as these n-grams are completely out-of-distribution compared to the training data of the model. If anything, using common full-word tokens as inputs induce a strong prior as encoded in their embeddings and is thus expected to deteriorate the performance. It is not trivial to design a similar testbed that does simulate an in-distribution task, but is a pursuit that if achieved will be most beneficial. Nevertheless, even this intermediate step of investigating the compositional abilities of model in a synthetic controlled setting is interesting and enriches our knowledge about the properties of transformer based language models.
I thus wish to thank the authors for the answers, and choose to keep my score as is.
Once again, thank you for your valuable inputs and service as a reviewer. We are at your disposal for any further clarification or discussion regarding our rebuttal.
Once again, thank you for your valuable inputs and service as a reviewer. We are at your disposal for any further clarification or discussion regarding our rebuttal.
Thank you very much for raising your score, we are glad that our response clarified your concerns.
We will indeed incorporate all this material in the revised version of the manuscript.
Once again, thanks for highlighting these issues and contributing to the improvement of our work.
**(4)** We agree with you that the synthetic tasks considered might be missing the diversity of natural data that may have more examples of how to do composition in a general sense. This is intentional. We chose to provide the model only with a minimal set of sub-tasks and avoid this kind of redundancy. 

Firstly, because in these settings the risk of learning spurious correlations and other possible confounding phenomena (such as the unobserved local structures anomalies pointed out by DGs4) would increase, possibly compromising our results. 

Secondly, because increasing the set of observed combinations of primitives beyond the minimal set is itself an inefficiency. We could also have provided many more combinations of sub-tasks to artificially "simulate" this regime, but that would have added an additional dimension to our investigation that is, however, inefficient by design.

Finally, we cannot see any reason why a model that does not perform well on simple, well-defined synthetic tasks would perform better in a more natural and complex setting. Instead, the only solution that we see to the learning inefficiency consists in adding more inductive bias into the model, as was the case for example in our experiments with the additional prediction heads (experiments with the _auxiliary loss_ in Section 4.1).

**(5)** We are happy to hear that our additional results on tokenization were satisfying. Thanks again for suggesting to investigate more closely into this aspect of our experiments.

Finally, we understand your concern regarding the excessive changes to our initial submission. However, most of the proposed changes would be added in the form of Appendix material to address possible objections and secondary aspects of our study (e.g., tokenization, other models, etc.). The changes in the main document would concern mostly the presentation of the tasks, on which many reviewers (rightfully) had some concerns, while the main message of the paper and the main empirical results would remain consistent with the original submission.
Thank you for raising your score, for the additional comments on our work, and for your involvement in the review process, we really appreciate it.

**(1)** We agree that the definition right now lacks formality and that this should be addressed. We propose a simple variation of our initial hypothesis, which does not affect either our observations or our experimental setup, yet fixes the weak definition of H1.
- H1. A Transformer language model learns a compositional task with fewer samples than those required to learn its most difficult sub-task.
- H2. A Transformer language model learns a compositional task with fewer samples than the sum of the samples needed to learn every sub-task.
- H3. A Transformer language model learns a compositional task with approximately (the same order of magnitude) as many samples as the sum of the samples needed to learn every sub-task.
- H4. A Transformer language model needs more data samples than in H3.

**(2)** It is indeed hard, given the limited explainability of the internal mechanisms of Transformer models, to establish whether or not the model is effectively learning certain operations. However, the experiments on the task decomposition represent in our view a solid clue that LLaMa learns internal operations related to the set of primitives that we define (since pre-training on the compositional task results in a faster learning of the individual sub-tasks). Additionally, we argue that this experiment also proves the validity of our choice of primitives: when trained only on the compositional task, the model autonomously converges to operations that are related to them and can effectively compose them to solve the task. Hence, we believe that assuming that the model should be able to leverage the primitives in the given sub-tasks to learn the compositional task does not seem too far-fetched.

This, in some sense, links back to some of your remarks in the initial review which we might now have completely addressed in the previous response.
> 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)
In practice, the experiments on de-compositionality show exactly these two points.

To sum up the rather long discussion on the topic, these were the main important clarifications and arguments.
- _atomicity_: the sub-tasks are effectively atomic units roughly corresponding to a basic block of operations in the equivalent procedural programming language;
- _uniqueness_: the sub-tasks are not unique because we could consider an arbitrary set of sub-tasks composed of primitives or combinations of primitives that make each one of them observable. However, we choose the minimal set of sub-tasks that makes every operation observable.
- _validity of the primitive set_: experiments on task de-composition corroborates the hypothesis that the considered primitives can be learned and be effectively composed when training only on the full compositional task. This represents a validation of our choice of primitives and our experimental setup in general. 
- _relativity_: the measured inefficiency is relative to our specific definition of sub-tasks and primitives, as correctly pointed out. However, considering all the points above, we speculate that similar results could be measured also for alternative definitions.

**(3)** We included an extensive rebuttal on the nature of the introduced tasks and why they are a meaningful contribution to the community in general in the response to reviewer teuc. We include a summary of our main arguments in the following list.
- First, a main driver for the design of our new tasks was the absence in the landscape of research on compositional learning of algorithmic tasks based on the pointer execution (PE), a synthetic evaluation task first introduced by Bengio et al. [20] to test the generalization capabilities of deep learning models. 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. 
- Second, PEN and PERM are particularly suitable for benchmarking compositionality due to their algorithmic nature. 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.
- 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.
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.
Thanks for the response and clarifications.

1. Using ideas like "a few demonstrations" is just not formal. And dressing this up as a formal hypothesis just seems to be misdirection when the experiments just choose some arbitrary number out of thin air. This is honestly a small part of the paper, and does not majorly impact my opinion, but it is bad practice.

2. Thanks for the discussion here. I agree that it is a tricky issue for sure, but I am still not totally convinced that these must be the ways to decompose the tasks or that it is conclusive that the model is actually learning them in the way presented.

3. Thanks for the figure. It is still not clear to me why the new task definitions are necessary.

4. Thanks again for the clarification. Indeed adding the hints that get closer to showing how to do composition is maybe helpful. I guess my point was that maybe these synthetic tasks are missing the diversity of natural data that may have more examples of *how* to do composition in a general sense. And just training on narrow subtasks and expecting composition to arise seems unrealistic (and also not being suggested by people in the literature as being something that would occur, to my knowledge)

5. Thanks for these extra experiments and investigation. This does seem to be better evidence that the tokenization is not a major issue. 

I will increase my score to a 4 to reflect the partial resolution of some of the issues I raised, but I think the remaining issues still leave the paper below the bar for acceptance in my mind, especially with several substantial changes to the paper being suggested.