Limits of Transformer Language Models on Learning to Compose Algorithms
Authors: Jonathan Thomm
Giacomo Camposampiero
Aleksandar Terzic
Michael Hersche
Bernhard Schölkopf
Abbas Rahimi
Venue: NeurIPS 2024 poster (2024)
Keywords: Few-shot Compositional Learning
Compositionality
Sample Efficiency
Algorithmic Learning
Large Language Models
Transformers
Primary area: natural_language_processing
TL;DR: We analyze the capabilities of Transformer language models in learning compositional discrete tasks and observe that compositional learning is very sample inefficient.

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.

Limits of Transformer Language Models on Learning to Compose Algorithms
Jonathan Thomm 1,2+
Giacomo Camposampiero 1.2
Aleksandar Terzic
thomm@ethz. ch
giacomo.. hww.:/aappprrreiimmmm... com
aleksandar baakaandar.terrcccllbbb.occo terzic1@ibb.coom
Michael Hersche mi michael. ceerscheiin com
Bernhard Schölkopf bs@tuebingen. mpg. de
Abbas Rahimi" abrêzurich, ibm. com
IBM Research Zurich, 2ETH Zurich, MPI Tübingen
Abstract
We analyze the capabilities of Transformer language models in learning com- positional discrete tasks. To this end, 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 mod- els can reuse primitives observable in the sub-tasks to learn the composition task. Our results indicate that compositional learning in state-of-the-art Trans- former 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, support these findings with theoretical analysis focused on the sample inefficiency of gradient descent memorizing feedforward models. We open source code at https://ggthiiii com/IBM/ limitations 1m- t -eannin
1 Introduction
While Large Language Models (LLMs) are known to perform well on natural language generation tasks [ 2, they exhibit failures on reasoning 3
8 10], mathematics [2], causal inference [13 [14 15). and algorithmic tasks [16 17 18) Many interesting algorithmic tasks rely on function composition, which is an 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 when learning compose well 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 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:
4
5
6 7
decompose
Hi. A Transformer language model learns the task composition with constant number of samples (only used in the in-context learning setting).
H2. A Transformer language model learns compositional task with fewer samples than those required learn its most difficult sub-task.
Research conducted at IBM Research - Zurich.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

M3. A Transformer language model learns a compositional task with fewer samples than the sum of the samples needed to learn every sub-task.
H4. A Transformer language model needs more data samples than in M3.
This paper makes the following main contributions:
In Section 3 introduce family of two new algorithmic tasks with a compositional structure that is well-suited for creating systematic sub-tasks and testing compositionaliyy. We specifically design these synthetic tasks with independently observable sub-tasks such that the composition is easily inferable from the sub-tasks but harder to learn from scratch.
Section we train LLaMA models [2 on this family of the tasks as well as two tasks investigated by Dziri et al. 16]. We ensure that all necessary sub-tasks are learned and test how efficiently the models can learn their compositional re-combinations. We show that training LLaMA models from scratch fails to compose all learned sub-tasks under hypotheses H2 and H3. making H4 the most plausible hypothesis for all four tasks. Furthermore, we propose a formal bound, showing that current supervised gradient descent training fails in compositional learning in the limit.
In Section 5 we investigate GPT-4 and Gemini on all tasks and observe their failures to perform the tasks, or multi-round code generation, with task description and various chain-of-the oftthugghtthh examples. This shows that in-context learning with few samples is unreliable and fails to compose knowledge from sub-tasks and that Hi does not hold for the investigated tasks.
Preliminaries
Computational graph Let A be deterministic algorithm and let FA be set of deterministic primitive operations that can be used by during execution. Given an input x, we define the computational graph for the algorithm A as Ga(z) (V, E). Ga(a) is a weakly connected, directed acyclic graph. The nodes u E represent all intermediate variables' values during A's execution, while the edges nodes. One source node s describes the input æ, while the (single) sink node t represents the output A(x) 1. For every non-source node v, op(v) E FA denotes the operation applied to compute w. Figure shows an example with toy input for one of the tasks (PEN) later introduced in Section 3
E represent the function arguments involved in the computation of their target
Sub-task definition While Dziri et al. [16] define one sub-task for each operation occurring in the nodes of G GA(z), we relax this constraint and also consider sub-tasks composed of multiple operations from FA. However, we require every operation in the set of primitives FA 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 sub-task graph G' ((xx) if either:
v the only non-source node in G¹ G'A(=) (i.e., there is only one operation in the sub-graph).
v is not the only non-source node in G" (m)) and all other operations in the nodes of G' A(x) are independently observable in the other sub-task graphs in S S(((G'(()))
By using this constraint on the definition of the sub-tasks, we aim to achieve a middle- 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).
source node
def PEN(s))):
A(x)
ab ab41q wv7q1
res seq seq[1]
while !s- EOS):
last fat__match_> lcft(res[-1), seq) new_match- = match(last_matee seq)
G ((x)
ab
ab4fq
wv791
opta)
left
op(n)
natch
op(c)
right
right_match right(new (new_match, seq) res.append(right_mm
sink node
xy wv7q1
Figure 1: Translation of a compositional algorithmic task A, PEN (see Section for details), into its cor- responding compositional graph Giz)). for the input = "ab xy ab4fq wv7ql". The operations (edges) are volor-matched with the respective operations in the pscudo-code of the algorithmic task A(x).

---

3 Probing compositionality with algorithmic tasks
Pointer execution tasks are a family of algorithmic tasks initially proposed to benchmark the gen- eralization capabilities of deep learning models [2]]. 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-basse 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 independently observable in least one sub-task. A more detailed exposition of the properties of S is included in Appendix B.
3.1 Pointer execution's neighbor (PEN)
We introduce the Pointer Execution's '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 al. [I7 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 1eft 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" 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 (anreee(let (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.
3.2 Pointer execution reverse multicount (PERM)
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 We omit attention traps because there are no longer neighbor tokens in the input sequence.
Figure 2
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
3

---

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).
Pointer Exccution (PE)
chasing by masching letters) (fast Jeners)
wonds in the sequence with a given start value.
Squee
ablq
Input:
lquae
Introduce neighbors stowa yellow boocks and delimiter between idéress and value.
Ourgut:
abliq fquer
Explicitly provide the first word chasing procedur.
Pointer Execution (PE)
Pointer Execution (PE)
xy-2wy
Pcy Swer
werSigg
eteb
peeg
BOS -----
ab
nislne
Leghtee
abilg
acart
Outpect cley gywk
Inpist: my pisluc sydwe fiflex
wrvTel wesgg)
Outpat: ab ab4iq fqilox
Ouput the poimerr chasing rosult with the correponding neighboss
Ourper pointer chasing neverse under
Pointer Exccution Verbose (PEV)
Pointer Execution Reverse (PER)
syDww
SySw
wxFgi
wwrrgl
Eyne
abet
olgg
gynok
nislac
ab4fq
actrt
Start: abet
Output: gywk clugy etch abet
Impet: ab zy abdar zorbwrr Ealtes xyfiwv abtig wyTal ardet wrre) Outgut: abdfi we7kgl faoeer
Multiply current poimer length the number left-oointes up the curtert wood.
Oulput the neighhurs of the wonds
Pointer Execution Reverse Mulsicount (PERM)
Pointar Execution Neighhour (PEN)
xx
XB/2ww
werec
Fyne
rorwc
zees
B08
nibllan
absifq
Count Left
Multiplied
Ingut: my nieaae sydev sydvey wbdliy weleel
Start:
Output: wy'ee syröwr
Output: gyw2.3 ehgy 2 eselu abet.0
Figure 2: Introduced compositional algorithmic tasks. Left: The Pointer Execution (PE)'s neighbor (PEN). together the Pointer Execution (PE) and Pointer Execution Verbose (PEV) sub-tasks. Starting left, output obtained by matching words and predicting the current word (in PE) or its neighhor 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 ambiguities in the input string, an attention mechanism can find the match by retrieving the last characters of the word and matching 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.c., arrow to the left in the forward matching sequence).
PEV and PEN).

---

3.3 Highest subsequence sum (HSS)
Given a sequence of numbers, the Highest Subsequence Sum (HSS) task [16] consists in finding the highest sum of number subsequence where no two numbers are neighbors. For this task, there exists a simple linear-time ponstant-space dynamic programming (DP) solution which we use generate sub-tasks. The dynamic programming recurrence is
dp(i + 1) = max(dp(i - 1) + number,41)dp(())
where number,-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[] I 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 in the output (including if the new number was taken or not).
3.4 Multiplication (MUL)
The Multiplication (MUL) task [6] involves multiplying two multi-digit numbers in base 10. It is often used 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_m _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: digit- multiplication (MUL), where the solver has to solve multiplications between number in base 10 and a digit (making digit_m mul observable) and addition (ADD), where the solver has 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
4.1 Training LLaMA models for testing compositionality
In this section, we investigate compositional learning on the tasks presented in Section 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 usual 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 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 based on Universal Transformer (17), included in Appendix C.5 However, the unsatisfactory results deterred us from conducting further systematic analysis it.
the model architecture (e.g.. LLaMa architectural variation
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 Hz (no. of samples needed for the most difficult sub-task) and Hy (no. of samples needed for relearning all sub-tasks). Increasing the sample size to 1000 K (roughly 10x 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 H4 (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.
5

---

To set those results into context: our dataset of 1000 K samples overall has roughly 6x more tokens than the number of words a typical 13-year-old would have heard in their life [5]. 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 150M 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 obtains 0% accuracy with the same dataset size. However, this result also falls into the H4 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 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 H2. and H3. To achieve perfect accuracy, we need to scale up the dataset size by almost one order of magnitude compared to the M3 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 H4 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 LI LAMA when given the sub-tasks and not (cf. Figure top 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.
top right), we observe that L.LaMA seems to not benefit significantly
Learning the HSS task and MUL tasks. We investigate HSS and MUL (related to (6)). Figure 3 (bottom row) visualizes the results. As with our PEN and PERM tasks above, we observe that LLMMA does not exhibit strong compositional learning and learns under hypothesis H4. Also for
(a) PEN task
(b) PERM tack
1.00
XM
Sub-taska
1.00
Sub-tasks
CPY
PE
RCPY
0.75
PEM
Arcuracy
PE PEV
Averrayy
PER
0.50
0.50
Task
Task
wy
0.25
sub-tasks
0.25
wylo subs kanks
wio sub-taoks
0.00
aux loss
0.00
10"
10F
10
discrete solvee
104
TPP
11P
tnxining samplss
Iniinin samples
(c) HSS task
(d) MUL task
1.00
Sub-tzeks
1,00
Sub-tasks
SSE Task
DMUL
0.75
0.75
ADD
Ancuracy
wy Laads wyl substasles
Accuney
Tusk
0.50
0.50
wy sailttolks
Regimes
-eddee w//o sub-ttoks
Ho
0.25
Regines
H2
H2
0.00
74
0.00
76:
107
10
10
10
10
12P
Enoiniing stmple
Ensiningg somples
Figure 3: Accuracy of LLLMA models on PEN, PERM, HSS, and MUL, and their respective sub-tasks. While LLaMa achieves perfect accuracy all the individual sub-task: 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 Hg (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 H. (learning the composition requires more samples than the sum of the sub-tasks, red). Moreover, training together with the sub tabks does not seem to perform sensibly better than training only the main task (i.c., 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.
4.2 Testing decomposition by learning sub-tasks from pre-trained LLaMA model
We additionally evaluate LLaMA's abilities on deconpositionaltyy. 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.TOP. However, to get maximum accuracy on decomposing PEV from PEN, need between 25 K and 50 K samples to fine-tune a PEN-pretrained model. This is significant fraction of the data learn the PEV task from scratch, making Mi also implausible for decompositionality on the PEN task. Similar observations hold for decomposing PE from PERM (i.e., a PERM-pretraingg model fine-tuned on the PE task; see Table C.II). 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 to some extent compositional, even if the learning process is not compositional (and very inefficient).
4.3 Asymptotic limitations on compositional learning
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 ineffi- cient on combinatorial (including compositional) problems. We 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²) times more data than an optimal learner. Otherwise, they will not generalize to the test set. any positive number and n is the index in the series.
Proof sketch. Many combinatorial problems are assumed to be hard to solve. NP hard problems provide an extreme case, where under the P * NP assumption the solution algorithm requires more than polynomial time. By constructing a train and test dataset where the problem instance of combinatorial problem (c.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, 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 N problems, in which case the k in Theorem 4.1 becomes bounded. While the classical reduction requires an -iitt--diitiiittionn 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).
5 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- 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-ae methods 226 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 correct left wwtmmmathhhighh step, regardless of the last word being correct.
7

---

Termination accuracy checks if the last output word's left neighbor in the sequence matches the imput sequence. We include ablations on possible confounding factors (such as tokenization), different task definitions, and number of in-context examples in Appendix D
5.1 GPT-4 and Gemini prompting on PEN and PERM
Prompting solve PEN. We first provide the models with simple few-shot prompts demonstrating eight inpul- examples for the task. The exact format is shown in Figure D.16 We find that this is 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 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 more recent and advanced CoT query, analogical CoT [28], which prompts the model to generate its own few-shot examples by asking it to recall several examples of similar algorithmic problems it has been exposed to during training (Figure D.19) This still does not help us achieve non-zere task accuracy.
We then provide more explicit guidance in the few-shot examples using two different approaches. In the first approach (Few-shot COT, Figure D.20). the few-shot examples demonstrate each step the pointer matching procedure alongside with the corresponding outputs (right neighbors) at each step. In the second approach (Sub-task CoT, FigureD.2II, the few-shot examples consist of two phases: first, we match the entire sequence given an initial input, and then we output the right neighbors of the elements of the previously matched sequence. While none of the two approaches achieve non-zero task accuracy, sub-task CoT prompts induce higher match accuracy in the Gemini-Pro model, reaching 33%.
We experiment with one further ablation, in which we remove the additional attention traps in the yellow tokens (see Appendix B.2. such that every yellow token only matches once. Although this
Traps Removed
Code Interpreter Analogical CoT
Termination Acc.
Termination Acc.
Few-shot CoT
Sub-task CoT
Few-shot
Deseription CoT
Match Auc.
Task Acc.
Match Auc.
Task Acc.
Task
Prompt Setting
GPT-4
Gemini-Pro
0.12
0.04
0.00
0.05
0.03
0.00
0.11
0.04
0.00
0.09
0.03
0.00
0.08
0.14
0.00
0.05
0.01
0.00
PEN
n.a.
0.16
0.23
0.00
0.19
0.12
0.00
n.a.
V
0.20
0.14
0.00
0.14
0.33
0.00
n.a.
0.30
0.39
0.00
0.20
0.08
0.00
n.a.
n.a.
0.31
0.41
0.19
n.a.
n.a.
n.a.
n.a.
0.06
0.16
0.00
0.10
0.00
0.00
0.12
0.37
0.06
0.08
0.04
0.04
n.a.
0.14
0.45
0.00
0.10
0.10
0.02
n.a.
0.38
0.74
0.08
0.28
0.12
0.02
PERM
n.a.
n.a.
0.80
0.96
0.14
0.06
0.82
0.00
n.a.
V
n.a.
0.62
0.95
0.42
0.19
0.77
0.09
n.a.
n.a.
n.a.
V
0.67
0.42
0.13
n.a. n.a.
n.a.
n.a.
n.a
n.a.
0.16
0.41
0.02
0.16
0.06
0.00
Table 1: Results of GPT-4 and Pro with various prompt settings (including chain-of-thought (CoT), analogical CoT 288) and code interpreter as multi-round prompting technique (7)). 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- Pem reaches to 9% in this setting.
8

---

does not help GPT-4 or Gemini to obtain 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 -lreeviiw 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 [ When asked for CoT, GPT-4 does not find 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, 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.
begin by
5.2 GPTT code interpreter on PEN and PERM
We experiment with asking GPT-4 to write code, which is suitable prompting method for our algorithmic tasks. We use the official multi-round code interpreter of GPT-4's assistant API. While 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 [ 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 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 (1 (13%), three times (38%) it tries to correct itself until shutdown, and three times (38%) it catches the problem but still outputs 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 answer).
6 Related work
investigate limitations of Transformer language models on compositionality with prompting and finetuning. Differently from them, we train state-of state-of-the-art --tth-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. [1 find correlation between performance and the frequency of how often task instances occur in the training data.
Dziri et al. [16] and others 9
29 30
Apart from the tasks we use in this work, there exist many benchmarks on compositional learning for synthetic tasks specifically target compositional learning abilities subject to sample efficiency.
language models B 3
21 32 33 34] 35]. However, compared to them, our training setup and
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. 440 point out that constant-size logarithmic precision Transformers can implement mathematical and dynamic programming problems. In order to learn 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 [77 Transformers to change their depth. This could make the model computationally more powerful as 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.
41
42 43 present approaches instead allow
There has been extensive research on the expressive power of language models 40 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 incentivize compo- sitional learning in Transformer- based language models, possibly by incorporating more inductive biases towards compositionality in the model architecture the training procedure. Additionally, while the investigated algorithmic tasks allow to work in a fully controlled environment with limited confounding factors, they still represent 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. this work, we analyzed the capabilities of Transformer language models in learning compositional algorithmic tasks. To do so, formulated a of hypotheses to characterize the efficiency of a model when learning compositional tasks, from efficient (H1) to inefficient (H4)) regimes. We introduced to benchmark compositional learning in large language models in more controlled setting. On these novel tasks, as well 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 Hi 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 Hi-Hs. Finally, we empirically rule out also the possibility that these tasks can be learned in few-shot fashion by state-of-the-ar LLMs such as GPT-4 and Gemini-Pro. This evaluation of current state-of-ft the- 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.
set of algorithmic tasks based pointer execution
10

---

References
[1] Kyle Mahowald, Anna A Ivanova, Idan Blank, Nancy Kanwisher, Joshua Tenenbaum, and Evelina Fedorenko. Dissociating language and thought in large language models. Trends in Cognitive Sciences, 2024.
[2] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023.
[3] Arsenii Kirillovich Moskvichev, Victor Vikram Odouard, and Melanie Mitchell. The Con- ceptARC benchmark: Evaluating understanding and generalization in the ARC domain. Trans- actions on Machine Learning Research, 2023.
[4] Wenting Zhao, Justin Chiu, Claire Cardie, and Alexander Rush. Abductive commonsense reasoning exploiting mutually exclusive explanations. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Toronto, Canada, July 2023. Association for Computational Linguistics.
[5] Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashu- bin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Mare van Zee, and Olivier Bousquet. Measuring compositional generalization: A comprehensive method on realistic data. International Conference on Learning Representa- tions (ICLR), 2020.
[6] Ning Bian, Xianpei Han, Le Sun, Hongyu Lin, Yaojie Lu, and Ben He. ChatGPT is knowl- edgeable but inexperienced solver: An investigation of commonsense problem in large language models. arXiv preprint arXiv:2303.1642 2023.
[7] Michael Hersche, Francesco di Stefano, Thomas Hofmann, Abu Sehastian, and Abbas Rahimi. Probabilistic abduction for visual abstract reasoning via learning rules in vector-symbolic architectures. In Proceedings of the NeurIPS Workshop on Mathematical Reasoning and AI, 2023.
[8] Najoung Kim and Tal Linzen. COGS: compositional generalization challenge based on semantic interpretation. In Proceedingy of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, November 2020.
[9] Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah Smith, and Mike Lewis. Measuring and narrowing the compositionality gap in language models. In Findings of the Association for Computational Linguistics: EMNLP 2023, Singapore, December 2023, Association for Computational Linguistics.
[10] Giacomo Camposampiero, Loie Houmard, Benjamin Estermann, Joël Mathys, and Roger Wattenhofer. Abstract visual reasoning enabled by language. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, 2023.
[11] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[12] Yiran Wu, Feiran Jia, Shaokun Zhang, Hangyu Li, Erkang Zhu, Yue Wang, Yin Tat Lee, Richard Peng, Qingyun Wu, and Chi Wang. An empirical study on challenging math problem solving with GPT-4. In International Conference on Learning Representations (ICLR), 2024.
[13) Zhijing Jin, Jiarui Liu, Zhiheng LYU, Spencer Poff, Mrinmaya Sachan, Rada Mihalcea, Mona T. Diab, and Bernhard Schölkopf. Can large language models infer causation from correlation? In International Conference Learning Representations (ICLR), 2024.
[14] Cheng Zhang, Stefan Bauer, Paul Bennett, Jiangfeng Gao, Wenbo Gong, Agrin Hilmkil, Joel Jennings, Chao Ma, Tom Minka, Nick Pawlowski, et al. Understanding causality with large language models: Feasibility and opportunities. arXiv preprint SiXX::3344005544. 2023.
11

---

[15] Z. Jin, Y. Chen, F. Leeb, L. Gresele, O. Kamal, Z. Lyu. K. Blin, F. Gonzalez, M. Kleiman-Weiner, M. Sachan, and B. Schölkopf. CLadder: A benchmark to assess causal reasoning capabilities of language models. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
[16] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang (Lorraine) Li, Liwei Jiang. Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras. Jena Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of transformers on compositionality. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
[17] Samira Abnar, Omid Saremi, Laurent Dinh, Shantel Wilson, Miguel Angel Bautista, Chen Huang, Vimal Thilak, Etai Littwin, Jiatao Gu, Josh Susskind, and Samy Bengio. Adaptivity and modularity for efficient generalization over task complexity. arXiv preprint arXiv:2310.0886 2023.
[18] Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans- formers learn shorteuts to automata. In International Conference on Learning Representations (ICLR), 2023.
[19] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and IIlia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017.
[20] Chiyuan Zhang, Maithra Raghu, Jon Kleinberg, and Samy Bengio. Pointer value retrieval: A new benchmark for understanding the limits of neural network generalization. arXiv preprint arXiv:2107. 12580, 2021.
[21] David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. ArXiv, Abss/194.00557, 2019.
[22] Jacob Russin, Roland Fernandez, Hamid Palangi, Eric Rosen, Nebojsa Jojic, Paul Smolensky. and Jianfeng Gao. Compositional processing emerges in neural networks solving math problems. 43rd Annual Meeting of the Cognitive Science Society, 2021.
[23] Gregoire Deletang, Anian Ruoss, Jordi Gray-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A Ortega. Neural networks and the Chomsky hierarchy. In International Conference Learning Representations (ICLR), 2023.
[24] Daniel Y Fu, Tri Dao, Khaled Kamal Saab, Armin W Thomas, Atri Rudra, and Christopher Re, Hungry hungry hippos: Towards language modeling with state space models. In International Conference on Learning Representations (ICLR), 2023.
[25] Alex Warstadt, Leshem Choshen, Aaron Mueller, Adina Williams, Ethan Wilcox, and Chengxu Zhuang. Call for papers-The BabyLM Challenge: Sample-efficient pretraining on a develop- mentally plausible corpus. arXiv preprint arXiv:2301..1796, 2023.
(26) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoe V Le, and Denny Zhou, Chain of thought prompting clicits reasoning in large language models. Advances in Neural Information Processing Systems (NeurIPS), 36. 2022.
[27] Aojun Zhou, Ke Wang, Zimu Lu, Weikang Shi, Sichun Luo, Zipeng Qin, Shaoqing Lu, Anya Jia, Linqi Song, Mingjie Zhan, and Hongsheng Li. Solving challenging math word problems using GPT-4 code interpreter with code-based selffverification In International Conference on Learning Representations (ICLR), 2024.
[28] Michihiro Yasunaga, Xinyun Chen, Yujia Li, Panupong Pasupat, Jure Leskovec, Percy Liang, Ed H. Chi, and Denny Zhou. Large language models as analogical reasoners. In International Conference on Learning Representations (ICLR). 2024.
[29] Linlu Qiu, Liwei Jiang, Ximing Lu, Melanie Sclar, Valentina Pyatkin, Chandra Bhagavatula, Bailin Wang, Yoon Kim, Yejin Choi, Nouha Dziri, and Xiang Ren. Phenomenal yet puzzling: Testing inductive reasoning capabilities of language models with hypothesis refinement. In International Conference on Learning Representations (ICLR), 2024.
12

---

[30] Zhuoyan Xu, Zhenmei Shi, and Yingyu Liang. Do large language models have composi- tional ability? an investigation into limitations and scalability. In ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2024.
[31] Yasaman Razeghi, IV RobertL.Logan, Matt Gardner, and Sameer Singh. Impact of pretraining term frequencies on few-shot numerical reasoning. In Conference on Empirical Methods in Natural Language Processing, 2022.
[32] Tristan Thrush, Ryan Jiang, Max Bartolo, Amanpreet Singh, Adina Williams, Douwe Kiela, and Candace Ross. Winoground: Probing vision and language models for visio-linguistic compositionality. 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
[33] Lorenzo Bertolini, Julie Weeds, and David Weir. Testing large language models on com- positionality and inference with phrase-level adjective-noun entailment. In Proceedings of the 29th International Conference on Computational Linguistics. International Committee on Computational Linguistics, 2022.
[34] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jenry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint 10.1:8,10..1168, 2021.
[35] Brenden M. Lake and Marco Baroni. Generalization without systematicity: On the compo- sitional skills sequence-to-sequenee recurrent networks. In International Conference on Machine Learning (ICML), 2017.
[36] Meriem Beloucif, Mihir Bansal, and Chris Biemann. Using Wikidata for enhancing composi- tionality in pretrained language models. In Proceedings of the 14th International Conference on Recent Advances in Natural Language Processing, 2023.
[37] Jiaao Chen, Xiaoman Pan, Dian Yu, Kaiqiang Song, Xiaoyang Wang, Dong Yu, and Jianshu Chen. Skills-in-context prompting: Unlocking compositionality in large language models. arXiv preprint arXiv:2308.003:3 2023.
[38] Andrew Drozdov, Nathanael Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. Compositional semantic parsing with large language models. In International Conference on Learning Representations (ICLR), 2023.
[39] Chenhao Zheng, Jieyu Zhang, Aniruddha Kembhavi, and Ranjay Krishna. Iterated learning improves compositionality in large vision-language models. arxiv preprint 2024.
[40] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
[41] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. In International Conference Learning Representations (ICLR), 2019.
[42] Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
[43] Andrea Banino, Jan Balaguer, and Charles Blundell. Pondernet: Learning to ponder. In 8th ICML Workshop on Automated Machine Learning (AutoMI), 2021.
[44] Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In The Second Blogpost Track at ICLR 2023, 2021.
[45] Stephen Judd. On the complexity of loading shallow neural networks. Journal of Complexity, 4 19),177-192, 1988.
[46] Avrim Blum and Ronald I.. Rivest. Training a 3-node neural network NP-complete. Neural Networks. 5(1):117-127, 1992.
13

---

[47] Digvijay Boob, Santanu S Dey, and Guanghui Lan. Complexity of training ReLU neural network. Discrete Optimization, 44:100620, 2022.
[48] Bhaskar DasGupta, Hava Siegelmann, and Eduardo Sontag, On the Intractability of Loading Neural Networks, pages 357-389. Springer US, Boston, MA, 1994.
[49]
Michael Kearns. The computational complexity of machine learning. MIT press, 1990.
[50]
Emmanuel Abbe and Colin Sandon. Polynomial-time universality and limitations of deep learning. Communications on Pure and Applied Mathematics, 76(1 1):3493-3544 2023.
[51] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas. Lisa Anne Hendricks, Johannes Welbi, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. Training compute-optimal large language models. arXiv preprint arXiv:2203. 15556, 2022.
[52] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arxáv preprint arxiv:2001.0836 2020.
[53] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless seth is false). SIAM Journal Compuling, 47(3):1087-1097, 2018.
[54] Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang. Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. The Pile: An 800GB dataset of diverse text for language modeling. arXiv preprint arXiv:2101.0000 2020.
[55] Milad Nasr, Nicholas Carlini, Jonathan Hayase, Matthew Jagielski, A Feder Cooper, Daphne Ip- polito, Christopher A Choquette-Choo Eric Wallace, Florian Tramèr, and Katherine Lee. Scalable extraction of training data from (production) language models. arXiv preprint arXiv:2311.17035, 2023.
[56] Kushal Tirumala, Aram Markosyan, Luke Zettlemoyer, and Armen Aghajanyan. Memorization without overfitting: Analyzing the training dynamics of large language models. Advances in Neural Information Processing Systems (NeurIPS), 35, 2022.
[57] David Maxwell Chickering. Learning bayesian networks is np-complete. Learning from data: Artificial intelligence and statistics pages 121-130, 1996.
[58] Yury Kaminsky and Irina Deeva. BigBraveBN: algorithm of structural learning for bayesian networks with large number of nodes. Procedia Computer Science, 212:191-200, 2022.
[59] Thomas Eiter and Thomas Lukasiewicz. Complexity results for structure- based causality. Artificial Intelligence, 142(1):53 89, 2002.
[60] L.G. Valiant and V.V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85-93, 1986.
[61] Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber. The devil is in the detail: Simple tricks improve systematic generalization of transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, 2021.
14

---

Appendix
Table of Contents
A
Feedforward models on gradient descent can only learn the obvious
16
A.1
Details on the theory...
18
A.2
Intuition: Learning- inference gap
18
Special case: SAT proof on algorithmic learning
A.4
General proof algorithmic learning
20
A.5
Algorithmic learning the in-distribution setting
21
A.6
Proof of the corollary|A. A.7
22
B
Specifications of PEN, PERM, HSS, and MUL
23
B.1
Properties of the sub-task definition
23
Details PEN task
23
C
Training experiments details
24
C.I
LLaMA training hyperparameters)
................................
24
C.2
Details on the discrete solver of the PEN Task
24
C.3
Accuracy tables
25
C.4
Performance of LLaMA on decompositionality
28
C,5
Model ablation: Performance of UT--style LLaMA on PERM
29
D
Prompting experiments details
30
D.I
Input sequences tokenization
30
D.2
Natural PEN
30
D.3
Many-shoe shot prompting
30
D.4
Prompting OpenAl al -preview
31
D.5
Prompt examples
32
15

---

A Feedforward models on gradient descent can only learn the obvious
As in our empirical results, we focus on model size and dataset size, not compute, which e.g. is the focus of [51 122 [5]] This has the rationale, that concepts or tasks which do not have unlimited amounts of data and are hard learn, can 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 single sample each (i.e., learnable within hypothesis Hi), but on which feedforward models trained with gradient descent will learn within hypothesis H4. needing up to exponentially many samples. See also Figure A.4 for an intuition.
From complexity theory, we know that finding the proof of membership of a string in language is in general less efficient than verifying its membership given proof. We use this structure:
Definition A.1 (K)) Let L be any recursive decision problem with solution in space ((n) and being verifiable in time (n). Let us look at all algorithms solving L and let (()) 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 exponen- tial time (i.e. k(n) can be an arbitrarily high polynomial), and verification is in ((n). Under the same assumption, the edit distance algorithm needs 22(22=) for any e >> O 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 = (Uc, nt) consists of an algorithm f defined set of inputs U and a natural number ne. We call ne the "difficulty" of C. A concept class is an infinite set of concepts where each n E N occurs only finitely many times.
The intuition: they all pose certain challenges (e.g. finding a formula assignment) to an overarching problem to learn (e.g. the SAT problem). We need class of such problems because complexity theory makes asymptotic statements.
A concept class is set of concepts that connected by some common basis, e.g.
Similar definitions are used by Kearns 449 functions instead of subsets of an object set to better suit today's applications.
here use slightly different definition of concepts as
Definition A.3 (Application of a Concept). Given a concept (U, f. n)). an application of C is pair (T, E") of nonempty sets of samples (i.e. input-output pairs) of f. We call I' 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 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 input- output pairs) and θ the set of all input-bounded and algorithm is an algorithm L: S θ We say a L learns concept C = (Uc, fc, ne) on dataset Te, if M(z)= = f(x) Vz U with M = L(Te).
algorithms. A learning
Let TIME(A, æ) denote the runtime of an algorithm A on an input x. For a concept class C and learning algorithm L, we denote:
(no)
max (IME(C((TU....))). (UJmm)) E
Lee. the maximum inference runtime on test sample for concepts of difficulty no- Theorem A.5. For each k E K. there is a (different) concept class C, with applications (Te, Ec) (Le.,
train and test datasets) for each C E C, with the following properties:
1. There is a learning algorithm L that can learn each concept from a single sample in Okk(n)))
time and with 25 (nc) = ((ne)
2 OOvious here means: either present many samples, simple to extract
16

---

2. For any learning algorithm L. L one of the following will hold:
"C does not learn": L is not able to learn infinitely many concepts in C.
"C learns during inference": With M = [(Tc), Ess.)eE TIME(M, (2(k(nc))
"L does learn": TIME(C, Tc) ((k(nc))
The intuitive claim of this theorem is, that there are concepts, which require a [((k(c)) time (i.e. lot) to learn while being fast at inference.
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-distribun "exam" set. For completeness, in Appendix A.5 we provide proof for similar claims in in-distribution training-testing setting.
We now introduce a memorization assumption which assumes that our learning algorithm memorizes fast.
Definition A.6 (Constant Memorization). Given a concept class with applications Te, Ee for each C E C and a learning algorithm L. We say L memorizes constantly under C, if there is constant B, such that for any Te, Ec, runs in time B (Tel * Z with being the longest runtime of .M :- L(Tc)
sample in E.
With this, we obtain:
Corollary A.7. Let K. Then there exists a concept class C with applications Tc, Ee such that:
1. Any constantly memorizing learning algorithu C learning on an (arbitrary) augmented dataset To generated by a generator To = G(Tc) with G running in time o(k(nc))): If =5 (nc) o( (k(n)) ne
then L needs 91
(m())))
k(ne), many samples to learn each concept C = (Uc, fe, ne) E
There exists a learning algorithm L learning each concept from a single sample with =E (nc) = O(nc).
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 Ec.
If we think about the PEN task, it is a combination of sub-tasks, i.e., PFN(( (P(PE(CPpy(T))) There are combinations for three of the sub-tasks chained together. Al- ready 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 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 would be possible.
The theory allows us to extend this result beyond the limit of the empirically verifiable. When more primitives are available (c.g. 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 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, can conservatively assume constant number of steps for memorizing the fixed-size answer to sample. This fits definition A.6 for learning algorithm L learning with (growing) constant feedforward models, depending on the input size in the training data, one gradient step has the time complexity of forward pass.
Therefore, Corollary A.7 can be interpreted 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 (=f" (n) >> 11), or the data inefficiency is very high (by factor = (m)
k(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 O and the model does not change further.
17

---

Much research has been done on the complexity of various problems. Here we want to point out few further concept classes that need significant computation to learn and therefore underlie the above statements:
fundamental capability for safe, explainable, and intelligent systems, is to be able 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-poli poperrpolynooiill function.
Further, has been shown 159 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 few selected cases. Again, by constructing a concept class containing functions such that the structural model is given inferable and the always-cause asked or needed for predictions in the inference phase, follows by Theorem AA5 Corollary A.7 that learning such concepts requires a lot of computation and many samples for feedforward neural networks although theoretically unnecessary.
A.1 Details on the theory
For brevity "algorithm" refers to always terminating algorithms. Let fix standard random access memory computational model. We also a universal encoding and decoding function ENC, DEC that can encode/decode any algorithm or object we define below (imagine, for example, digital processor model where everything can be encoded in Os 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.
A.2 Intuition: Learning-inference gap
See Figure A.4
problem difficuly sample
difficully learaale gracient descent sample
learning
Inference
offort
effort
Figure A.4: Intuition for our statement: Based on widely accepted assumptions, there are problems requiring much more learning computation time than usage computation time (here: per sample available). Gradient Descent on Feedforward Networks under the assumption of constant-step- memorization 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.
18

---

A.3 Special case: SAT proof on algorithmic learning
For a better reader's s experience, let us restate the theorem:
Theorem. For each k E K. there is a (different) concept class C, with applications (Te, Ee) (i.e.
train and lest datasets) for each C E C, with the following properties:
1. There is a learning algorithm L" that can learn each concept from a single sample in O(k(nc)) time and with z (nc) = O(nc)
2. For any learning algorithm L, L one of the following will hold:
"L does not learn": : f. is not able to learn infinitely many concepts in C.
"L learns during inference". With M = L(Tc), E(a,yieR TIME(M, (2(k(ne))
"C does learn": TIME(C,Tc) (2k(me))
For simplicity. we first prove special case where k is the minimal runtime of SAT (3- (3-satisfiability problem (i.e. given P NP exponential in n).
Proof. Valiant and Vazirani [60] have shown, that given 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 * P) not possible in polynomial time, to find a proof for it, i.c. the unique satisfying variable assignment (this holds, because checking such proof is fast).
We choose C to be a set constructed from the set of unambiguously satisfiable SAT formulas: Given uniquely satisfiable formula A and the unique solution y² let Ú {A, 1, ........ [b be the set containing the formula and the variable names. Let (A) = and f (+) = y Our concept is now C (U f^, [A).. We choose the training dataset of the concepts to be {(4, 1)} and the examination dataset to be {ii, vt") ]i 1...., |1. This means we train formula, and the test set tests whether the model learned the unique solution to it.
uniquely satisfiable
We now construct the learning algorithm L learning C E C from one sample. Let fix an arbitrary (Ue, fc, ne) E C.
Given the training dataset Te {(Ac, 1)} corresponding to C, L builds an algorithm M of the form:
((A) (A,CK(A, for formula A of length ne where x; |ar| S ne is stored (i.e. hardcoded) constant. CHECK returns 1 iff x is a satisfying variable assignment for the variables of A. Note that ne can be inferred by L is the length of the single sample in Tc.
MMi) z4, i.c. the i-th variable assignment.
On all other inputs, M can implement any algorithm (e.g. some pre-trained knowledge).
Note that M has linear running time in ne on all samples in Te and Ec. Now, L finds the satisfying variable assignment x (using the minimal-runtime algorithm) for Ac and stores it in Note that this procedure runs in ksAr(ne) for ksAr(ne) being the minimal runtime for finding 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 (TkxAT(())) (i.e. strictly less) time and with M L(Te) needing of (ks (ri)/nnc) time on each sample in Fc. Then one can simulate the learning setting to find a solution to a formula A, = |A] (except finitely many times): First, simulate L on ((A, 1)} to obtain M = (A( 1)}). Then, simulate M on all variable indices as inputs to obtain the satisfying assignment A This algorithm finds a in o(ksAT (n)) + o(n kSar(n) ) okks (n)) n
time, contradiction.
19

---

A.4 General proof on algorithmic learning
This proof is analogous to the special SAT case. We recommend the reader to read the special case first.
Proof. Let E K. Let P be the problem & corresponds to (e.g. SAT). Let A, denote the solv- ing algorithm for P running in time k(n), i.e. an algorithm that computes a solution to each instance of class of problem cases, where the solution algorithm that can verify if such solution is correct, running in O(n). We choose the concept class C to a set constructed from the set positive instances in (e.g. in the SAT special case this would be uniquely satisfiable CNF formula): Given such positive input instance X, let U = (X. I.... (X))). Let (X) = and f (*( = (X)): Our concept is now Cx (U* .fx ( We choose the training dataset of the concepts to be {(X,1) and the examination dataset to be {(i, yf E 1,,...,1y11)
O(n) space. Let A, be the checking
We now construct the learning algorithm L learning C E C from one sample. Let us fix an arbitrary (Ue, fc, ne) E
Given the training dataset Tc {(X, } corresponding to C, C builds an algorithm M of the form:
MM(X CHECK(X, s) for problem instance X of the problem P with |X] S nc- |s| = ((n) is a stored (i.e. hardcoded) constant. CHECK returns iff & is a proof for the problem instance X (which exists by Definition A.T). Values for 8 will be candidate solutions for X, and L will search for the solution.
-Mi)) = 8,, i.e. the i-th value (e.g. bit) of
On all other inputs, M can implement any algorithm (e.g. some pre-trained knowledge).
Note that M has a linear runtime in ne on all samples in Te and Eg. Now, L computes s" = -X) (i.e. the solution to P) and stores it in i... s". Note that this procedure runs in TIME (A, X) time (which can be k(nc) if k(ni)) is tight).
Now to the second step: Assume there is learning algorithm & and assume that it can learn all concepts except finitely many and do so in o(k(nc)) (i.e. strictly less) time and with M ((Tc) needing ((k(n)) ((cc)/cc)) /nc) time each sample in Ec. Then one simulate the learning setting find a solution to problem case X E P, n == [X] (except finitely many times): First, simulate C on {(X, })} to obtain M L(((X, 1))). Then, simulate M on all solution indices as inputs to get the proof x for X. This algorithm finds yx o(k(n)) + o(n * k(n] = o(k(n)) time, contradiction.
20

---

A.5 Algorithmic learning in the in-distribution setting
The underlying idea of this proof is to use one-way functions that are assumed to be hard even when sees many examples. Such functions are known from cryptography. By using public-key cryptography we enable an attacker to simulate our learning setting which then allows us to show that this learning setting cannot be successful easily while we make sure, the setting is principally learnable 49 For more elaborate motivations, we refer to this work.
Assumption A.8 is standard assumption about cryptography being safe.
Assumption A.8 (Randomized RSA is CPA Secure). Let pk, pk denote an RSA encryption scheme with padding the plaintext with zeros and random bits before encryption. Assume that this encryption algorithm is CPA secure.
Theorem A.9. Let k(n) be any polynomial function. Assuming Assumption A.8 there exists randomized concept class C containing exactly one concept Cn per n N with applications (Te, Ec) (i.e. train and test datasets) where Te and Ec are drawn from the same distribution, with the following properties:
There is a learning algorithm that can learn each concept from a single sample.
For any learning algorithm L and any n, L will either have negligible (in n) probability of learning concept Cn. Otherwise, M = C(Tc,, needs D2( kim) computation time on sample in Ec,,, or L needs ((k(n)) computation time learn.
Proof. Let us denote by ple, pk our randomized RSA encryption scheme. For each n E N, we now build one concept:
First let s {0, 13"h be the randomly chosen secret for pk, pk We define:
U+ (zz,p(()), pk)] E (0,1)")
(3)
U_ (k.p)) pk) E (0, (0.1)")
(4)
where denotes the ciphertext size of pk. Note that the encryption is randomized and U4 contains all combinations pk(x) for the random bits. We define fa( = 1 if E U4 and (e) = U_ The concept is now (U+ U U_, fn,fn; n). Let us fix some constant size for Tn, F,, each (one is sufficient). Each sample in Tn and E,, is drawn with probability from U+ u.a.r. and with probability from U_ u.a.r.
With C being defined, let construct the learning algorithm L learning from sample. Let be fixed and sample Tn, E,, L chooses an arbitrary sample (Ir, pp(()))pp))))))))))))))))) and brute-forces the secret key d of the RSA encryption scheme. Note that this key is unique given the public key information pk. L now builds an algorithm M for the form:
M(x e, pk) 1 iff the decoding of c is and 0 otherwise
On all other inputs, M can implement any algorithm (e.g. some pre-trained knowledge).
Note that those operations are efficiently doable, much faster than breaking the RSA secret key.
Now to the second part: Let k be any polynomial function and fix some n. Assume there is learning algorithm L and assume that it learns the concept Cn with non-negligible probability in n.
Further assume that L needs o(k(n)) time and M L(Tc.) spends of k(m)) for each sample E Ec- Then, we can break RSA encryption in polynomial time: Let our serryption-braakin algorithm be given public key configuration (including π). It samples training dataset ''' with the public key. Then simulates L on it and obtains M = -[T). For the IND-CPA game, chooses words mo o mı randomly and gets the (randomized) encryption c of one of them back. & sets {(mo, pk)} as the test set. E now computes the answer by simulating the trained model and choosing my M( c, pk)) 1. This will give non-negligible success probability for the IND-CPA game in polynomial time, contradiction.
21

---

A.6 Proof of the corollary A.7
Corollary, Let k K. Then there exists a concept class C with applications Te, Ee such that: Any constantly memorizing learning algorithm L learning on an (arbitrary) augmented dataset T'c generated by a generator T G(Tc) with G running in time o(k(nc))) If z (nc) = of (inn))) ), then needs Q1( k(nel) many samples to learn each concept (n()
C (U, EC
There exists learning algorithm L learning each concept from single sample with =f (nc) O(ne).
Proof. Let us fix E IC and define our concept class with applications Ec, Te 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 that =f (me) = o( me and, L learns with [T&l = of k(nel, Then by Definition A.6 there exists ((c))
constant such that for every C E C, L runs time:
B (Tc) * Ze - B I =nc) = ol k(ne)
(ne) * =[(nc) = o(k(ne)).
Therefore, summarize that G runs in o(k(nc)), L runs in o(k(n))) and M L(T)) runs in =f(nc) = o( k(ac), This can't be, as Theorem A.5 states that we need more computation time. 0 ne
22

---

B Specifications of PEN, PERM, HSS, and MUL
B.1 Properties of the sub-task definition
In this Appendix section, we expose more details about our definition of the set of sub-tasks 8 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, 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 (.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 single primitive. As result, the definition of S is not unique. However, this does not undermine the validity 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.
B.2
Details on the PEN task
In addition to the task description in Section there are some additional constraints, visualized in Figure B.5)
1. The (yellow) neighbors of the green chain build chain themselves, starting at the second word in the sequence (i.e. the first yellow word).
2. The full sequence at least double the length of the green matching sequence. With all other 'free' green words, we build another matching sequence starting at 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 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.
Stit
xy
fylie
aboiq
Ryp
Figure B.5: Matchings of the yellow words: The (yellow) neighbors of matched green words build 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 two words in the sequence. The blue arrows are over the remaining green positions (which are not part of any answer), which also build matching sequence. Those additional constraints remove shorteut solutions.
23

---

abolc
acic:
wangg
VE'enoghlee (PS2))
Answar:
Figure B.6: How language model with next-token-predde preddicionn can solve the PEN task. Take the most recent word in the answer, find left neighbor ("left"), find the match ("match"), and retrieve its right neighbor ("right"). This corresponds the sub-tasks RCpy (c.g., in this task, the model has to find left neighbors), PE, and Cpy. The data efficiency in de-compositionalty (see Tables (.100 C.I1 provide some evidence that this is the natural way model solves the task when being close to 100% performance and without being trained on the sub-tasks.
C Training experiments details
C.1 LLaMA training hyperparameters
We batch size of 384 samples, which corresponds 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 is 10-4, in the original paper (2).
C.2 Details the discrete solver of the PEN Task
Our discrete learning algorithm which can learn the PEN task from a single example a 2- 2-gram model over 11 words resulting in 121 parameters with 8 values each. This results in search space of size 1.9 * 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 (BOSBBOS) result 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-TRUF, IS-START-FALSEE
IS-ERROR: is the current state error (outcomes: IS--RROR-TRUEE.S-ERRR----
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 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 learn the left-matee -right structure, which is easily found by this algorithm.
24

---

C.3 Accuracy tables
The numbers are visualized in Section 4 Each row in the tables C.2 corresponds to one run with the respective data mix.
and C.8
Cpy
RCpy
PE
PEV
PEN
Cpy
RCpy
PE
PEV
PEN
Model
Number of samples (in thousand)
Aceuracy at convergence
20
20
60
100
100
1.00
1.00
0.99
0.91
0.00
LLaMA
20
20
60
100
500
1.00
1.00
1.00
0.99
0.93
150M
20
20
60
100
750
1.00
1.00
1.00
0.98
0.95
20
20
60
100
1000
1.00
1.00
0.99
0.99
0.97
Table C.2: Performance of LLaMA on in-distribution test samples of the Pointer Execution's 's neighbor (PEN) task and its sub-tasks. Training until convergence. We used the standard language modeling loss on every next token in the input, which performed best. The best validation performance is taken for each task separately. As shown, while models learn all sub-tasks Cpy. RCpy, and PE very well, on the PEN task (which is a composition of the sub-tasks Cpy, RCpy, and PE) they need much larger amounts data than on any of the sub-tasks. This observation makes hypothesis H4 most plausible for PEN.
PEN
PEN
samples (in thousand)
Accuracy convergence
Model
300
0.00
LLaMA
500
0.74
150M
750
0.98
1000
0.98
LLaMA 28 M
300
0.98
auxiliary loss
Table C.3: Results of LLaMA models trained only on the Pointer Execution's 's neighbor (PEN) task. Compared to Table C.2, we observe that the model does not seem to systematically profit from the compositionality given there.
PERM
PERM
PE
PEM
PER
PE
PEM
PER
Model
Number of samples (in thousand)
Accuracy at convergence
40
40
150
150
1.00
1.00
0.99
0.25
40
40
150
230
1.00
1.00
0.99
0.30
LLaMA 150M
40
40
150
1000
1.00
1.00
1.00
0.74
40
40
150
1500
1.00
1.00
1.00
0.91
40
40
150
2000
1.00
1.00
1.00
0.91
Table C.4: Performance of LLaMA models in-distribution test samples of the Pointer Execution Reverse Multicount (PERM) task and its sub-tasks. Similar to Table we observe that although all sub-tasks are learned perfectly by the models, their composition does not learn fully until including an almost 10-fold increase of the data needed for all sub-tasks together, making hypothesis H4 most plausible for this task too.
25

---

PERM
PERM
samples
Accuracy at convergence
Model
(in thousand)
500
0.21
LLaMA
1000
0.68
150M
1500
0. 0.65
2000
0.98
Table C.5: Results of LLaMA models trained only the PERM task. Compared Table C.4 observe that the model does not seem to systematically profit from the compositionality given there, similar to PEN.
SSE
HSS
SSE
HSS
Model
samples (in thousand)
Accuracy convergence
25
25
1.00
0.68
LLaMA 150M
25
50
0.99
0.85
25
100
0.99
0.95
25
200
0.99
0.99
Table C.6: Performance of LLaMA models on Highest Subsequence Sum and Highest Subsequence Execution. Hypothesis H4 is the most plausible.
HSS
HSS
# samples
Accuracy convergence
Model
(in thousand)
25
0.67
LLaMA
50
0.84
M
100
0.95
200
0.99
Table C.7: Performance of LLaMA models only on the Highest Subsequence Sum task.
26

---

DMUL
ADD
MUL
DMUL
ADD
MUL
Model
samples (in thousand)
Accuracy at convergence
10
190
200
1.00
0.99
0.65
LLaMA M
10
190
400
1.00
0.99
0.68
10
190
800
1.00
0.99
0.74
10
190
1600
1.00
0.99
0.77
Table C,8: Performance LLaMA models on Digit Multiplication (DMUL), addition (ADD), and multiplication (MUL). Hypothesis H4 is the most plausible.
MUL
MUL
# samples
Accuracy at convergence
Model
(in thousand)
200
0.56
LLaMA 1
400
0.63
800
0.78
1600
0.77
Table C.9: Performance of LLaMA models only on multiplication (MUL).
27

---

C.4
Performance of LLaMA on decompositionality
In Tables C.10 and C.11 with LLaMa.
we include more details results about experiments on decompositionality
PEN
PEV
Pretraining samples (in thousand)
Finetuning samples (in thousand)
Pretraining Accuracy
Finetuning Accuracy
Model
1000
0.98
2
0.48
1000
0.98
8
0.92
LLaMA
1000
0.98
12
0.93
1
1000
0.98
25
0.97
1000
0.98
50
0.99
Table C.10: Performance LLaMA models pre-trained on Pointer Execution's neighbor (PEN), and after finetuning on Pointer Exccution Verbose (PEV) until convergence (i.c., PEN->PEV), We observe that decompositionality significantly improves data efficiency compared to training a model on the finetuning task from scratch. At the same time, however, for learning the task to full performance, still seems to need more than low constant number of demonstrations (2 50 K), making the H1 Hu-equivalent (i.e. "A Transformer language model learns decomposition with constant number of samples") rather implausible for decompositionality as well.
PERM
PE
Pretraining samples (in thousand)
Finetuning samples (in thousand)
Pretraining Accuracy
Finetuning Accuracy
Model
2000
0.98
1
0.80
2000
0.98
3
0.96
LLaMA 150 M
2000
0.98
5
0.97
2000
0.98
10
0.98
2000
0.98
20
0.99
Table C.11: Performance LLaMA models pre-trained on Pointer Execution Reverse Multicount (PERM), and after finetuning Pointer Execution (PE) until convergence (i.e., PERM-PP), As shown similarly in Table C.100 decompositionality significantly improves data efficiency compared to training model on the finetuning task from scratch. For learning the task to full performance, however, still seems to need more than low constant number of demonstrations (5-20 K), making the Hi -iieeuvvallntt "A Transformer language model learns decomposition with constant number of samples" rather implausible for decompositionalliyy
28

---

C.5 Model ablation: Performance of UT-sstyle LLaMA on PERM
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 UT [17]. for both of which there is evidence of better compositional generalization than the original Transformer. For instance, UT-style transformer displayed good performance on compositional tasks like SCAN Csordás et al. [6]] The model based on UT reached similar performance as the original L. LLMM model, i.e. behavior that could be classified in H4. We then also experimented with a Hyper-U'T-style UTy-style LLaMA, based on the aforementioned Hyper-UTT work [7]. in which each layer selects its weights from a common weight embedding pool to realize parameter-efficien model. This model consistently achieved lower accuracy compared to LLaMA on a large set of small algorithmic tasks. Thus, we chose not to systematically explore its performance in more challenging compositional algorithmic setting. The results are shown in table C.12 The hyperparameters used to train the model are the same as the ones used for the standard models (see Appendix C.I).
PE Multi
PE Multi
PERM
PERM
PER
PER
PE
PE
Model
Number of samples (in thousand)
Accuracy at convergence
40
40
150
150
1.00
0.99
0.93
0.26
40
150
230
1.00
0.99
0.98
0.29
LLaMA 150M
40
40
150
1500
1.00
1.00
1.00
0.98
40
150
2000
1.00
1.00
1.00
0.99
Table C.12: Performance of LLaMA with weight sharing across all transformer layers on the PERM
task and its sub-tasks. We see similar results compared to Table C.4 i.e., hypothesis H4 is most plausible for the PERM task on this model.
29

---

D Prompting experiments details
D.1 Input sequences tokenization
Unlike open-source models, such 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, 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 a one-digit number) were always detrimental for the task accuracy compared to the current sequence design (i.c. 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, LLJ. 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 additional experiment, we removed these 2-grams from the datasct. However, removing the "splittable" 2-grams did not result in an improvement of the performance (the accuracy decreased from 0.19 to 0.05 PEN) when using the best rest-performing prompting technique with GPT-4 (Code Interpreter).
D.2 Natural-PEN
We additionally designed 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 in this case are 3-characters English words. In practice, we filtered all valid 3-gram words from Scrabble that were translated to 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.13
Setup
Termination acc.
Match acc.
Task acc.
Few-shot CoT Few-shot CoT, no traps
0.50
0.27
0.00
0.20
0.29
0.00
Code Interpreter
0.05
0.10
0.05
Table D.13: Result of GPT-4 on the Natural-PEN task.
D.3 Many-shot prompting
We additionally ablated the number of shot provided to the LLMs to perform in-context learning. We increased the number of shots from examples up to 32 examples (64 did not fit into the 8k context window of the old GPT-4 version we are benchmarking). However, we did not observe any performance improvement, as reported in T.11
30

---

Termination acc.
Termination acc,
Match acc.
Match acc.
Task ucc.
Task acc.
Model
PEN
PERM
GPT-48 0,12
0,04
0.00
0.12
0.37
0.06
GPT-432 shots
0.16
0.06
0.00
0.36
0.59
0,00
Geminig shots
0.05
0.03
0.00
0.08
0.04
0.04
Geminiga shots
0.15
0.20
0.00
0.32
0.05
0.00
Table D.14: Ablation the number of shots used to do in-context learning in PEN and PERM, for both GPT-4 and Gemini. In particular, the number of shots is increase from 8 examples to 32 examples. Despite increasing the partial metrics, providing more shots does improve the overall task accuracy in both PEN (same, 0%) and PERM (the accuracy goes to 0% for both models).
D.4 Prompting OpenAl ol -preview
In this section, include further results with the newly-released model from OpenAI, ol-preview" specifically trained to tackle complex tasks in science, coding, and math. The results are reported in Ta11e
Avg. solution time (s) Termination aec.
Sub-task CoT
Few-shot
Description
Match acc.
Task Acc.
CoT
Task
Prompt Setting
ol ol-preview
83
0.14
0.05
0.00
PEN
77
0.86
0.86
0.70
41
0.98
1.00
0.85
86
0.24
0.22
0.10
PERM
64
0.82
0.94
0.71
47
0.94
0.90
0.90
Table D.15: Results al with various prompt settings. While ol o1-preview cannot infer task from examples 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 ol finds when asked for Chain of Thought (CoT) only.
31

---

D.5 Prompt examples
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: tv ke whhh shilf sySih ou my 7ol sai sh ootsd jneye sufnij odlek bebny yedge lossg ne las 4hStr uy Thu sfley bióia sy5dlg unfor aodkd lyk brfoy unksy keffin
7sb wa22m feieo ok2ey pr foden ylodk frostr occwee nytts ihiluy di7fw mmmgg pe7sd af7wg nj4is xy7ge lotig dollxx vatuue sh7od spiig snājw acfor in zwled bay fmootr pysko ny gaish keOlm ANSWER: le lofgg kellfi sgidg bryny st5ev sh5l2 colst fmobr sdānj njáls fxtico av7sd ny3sh
EXAMPLE: wi qp id int to etémm ssiti 20u ki adIch zictee cloit aziss ellit hišct apdys stisz bedyh cságt gnzup mitted mmága se tne yhóet uptst luZel nolgs ys3l vinfuns ettmm us-iha qplad adoet chehhe po3l bolihh svsch wilkth go4tu mirliga luckge dhibe visen yoatu ob2ak aptiid with luttel ch7upp acthi ne tellee gokgge colp gx2yq xv3vm gudap ipass sdtge
tizs xs5jua
trb aylove apdys
ANSWER:
up luocl cllb yhilet ysalu bedyh Itlui ad2dh aplys golop etómm lad dhdlec mmsgg
EXaMple: ty in txzjy wietzz zolst paint drcch diéru kugll stter ppáda milio lutvk zoist scdue ej2y erliz kn2ej kdlpp ejúsj me7es io0zo s4lp usj xedab antns vidlid sj0mm li kadee nbillg s/m lgbgs rutio yyl arlan jy tik imini tySer ns giódt to yflge zndns miñdo imfir 1póme mk2ym do2kg zh3vh oxdsa Bosk hrlax ar2mn
ANSWER: lns noyj kndejj stoar intri zotet wrnn oj rases sitim musio
riden
EXAMPLE:
sr el hyfir colggt yodedd Ski srakq ziooo zioe meTh gy 3ej sjOup wilhg hullkm yu7sa gifeb rh4mi situp li3tb kmilef apeak ibAdy ha5kmm fe5gy gal om7hh ix alltw gidnh lu56; sdinj ektir sixdr rx3yv gllxj vudit kertef midio gaovd salin vd7aj valuz txfine dudal coégr lupti skozi trillergge millje molhu hh7 el2ps spyyu ri2oo jelgp sbits in2rb upösk i77hh kylel ej6i el0x oxOud salisc
ol riflco sk6oi imitef huSion coler granh sdkej gxtsd sfop glllaj qufsk nbfix eryyx meTha telmme
EXaMple: be sy frówe tnfppp sk2gh vy 7ew odthf jubvs aflkk symem uelker m7yy yasrv la4tn ohikkm tnlj ywyyn zeówy pefyy joáve aftice mw The hidom mw51s loder ve hit the vyseow hataf velvy uripe velw ynlsm 1s7m pelpa jk korTep zudgy om4vk nid7m drink jetive qp isfie am2sk th7ha vxdya vu welte xytzo artedd wqzwe bodvz vuiuu vicket grlorr ad2xt up2vg
WER: ay viiju juivs iskta calp symm zalvy jolive vylme velvv mw/ss
knévu jabwk ertix akiish teb wedmx vuder autex zodas ppäjs lo-tbkk getev bóeve micak sttck skfsb gkirs paljs vgekh widge ex2pp zufac mikes gefdl golty ucd re5wb kiteuu shiic bk2kse shiic rxlsm modikk znorg acdep xmiqe zxUpp dmilt hldli oklja wkagt betidl 122eb ja7dm ve ltlbe 1g5gg golse wiskar xefie ot2p) ja6gk jrnkk:
EXAMPLE: an bazky
ANSWER:
ma sbiic makx rvSwb wblms zkóob wkigt jst wk iplis modick zxlpp galre
EXAMPLE: IN is onlyf staks la igllfs gnler pojii tells ghOck yfzh akaal tolts jixi ondyf uh 187th in exips kyzkn gnder ex7up gefgn de2ee jmdex dklsg knšog jinex ji5tp yiu eušjm bd5ic exipx wasyw irtiu fodvs lu fplibd cužjm Exdii paraal ab/lku epájf dytet cutth ve5sk dxdaw szlub dipyp vblin (kOas kollkm 7mx knrtpp hilpl byrill nl ailly klo ltg dx upise rullde
go its yie enzjm ex7p hhlen cstyf 1ott polge goöer jmncex
EXAMPLE: if se gwili dlj ifyy wasts vs nzwwe oxlegs kosug sjaue kodng hym caéel isthif saped p-ign eslyg myfox casel byltsk led 1yw dTaa biTls selwa you seryg lee wofch palag edee 1o4dt Sirje onfice seTwa patlsj ygoko stsps chhr hen watch hkc ofter onlry chsint ridon walss 7ar edline dilm belhb rolgs neswe artre yylkko uclpe orlfg
A ANSWER: se wasss catxl lofing wesch di4r ilaa zijje xppeed sel wa eiline yellio nw5w sslyg
YouR QuiNTION: vi at 2g2gr tee colos hefev paass dpdje vgitx puckp wnice vothe dwdvy nodve vylle eptzm kalw 125mx ješty abipp puidp oetka on5is irju hylup Sip zpoom os2dg stree dipenn onllis jutlog ev mit wih ielgu su we evion rade jebly joltz dpoye inllf isdpu widu skine sxdi he lev ggfish ukOuf codag hylbe
Clearly mark your answer by writing 'Aswer eyour answer>' as lust line.
Table 1.1 GPT4 and Gemini prompt for Pointer Execution's '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 model can pattern pattern-match match the respective token to do the matching operation.
32

---

Then, we introduce a natural language description of the task, prepended before the examples of the task, as shown in Table D.17
1 give you a sequence of words. Fach word has four characters plus a middle, words are separated by spaces, Start with the leftmost word. Output its neighbor. Then, match the last characters the current word (ic. the neighbor) 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: xv ke vu7bh shOfk sy eo7sf ay xd3nj zs7ht colsf jnéyc xd5nj od3ak hr2ny yc2gr Issag ny las shōfz uv7vu sfliv bbóia sg5dg. ux6oc zo4xd yalyk briny wokxy ke5fm jw ny7sb wq2mm fzteo nk2nv sf5zv praya fa4co ykOdk fm44rr oo4we njols ih by di7fw mm2pg 2v7xd of7wq njAls xv7ga lstig dxoux vzzue ah?od sgådg sa2jw acSee in7jn zw-eed bišay fmnóbr pobkow ny3sb gn-fal koOfmn Answer: ke is6sg keOlin spidg br2ny si5zv sb512 colst Imbbre xdjaj ajels (2óeo 2v7xd nsb
<7 MORE EXAMPLES>
YOUR QUESTION: va sk 4g5gr nee co7os hencv pçlss dp vg3sx pulblp wnlco vebhi dw5vy neóve vyūoe spózm kalrw velhc 125ıx ješhy pb2pq pu7dp oaa onsis Ifiju hyógp gršpp go5zm os2dq skóne de7en ontis ju0gg ev2on mxlmb is0pa sxlwn ev tw4sz jeóhy jpltz dpDje iolif isApu ssddw skine sziij helev qubab ukiluf caraa by2gp
Clearly mark your answer by writing 'Answer: syour answer>' as last line.
Table D.17: GPT4 and Gemini prompt for Pointer Execution's 's Neighbor (PEN) task with few-shot examples of the task and a task description.
On top of this, we also add a request to reason step-by-step (CoT), as shown in Table D.I8
1 give you a sequence of words. Each word has four characters plus a middle, words are separated by spaces. Start with the leftmost word. the neighbor) word starting with two characters.
Ouiput neighbor. Then, match last two characters the current word Again, ourput the neighbor. Do this until your current word (not the neighbor) has no match anymore.
EXAMPLE: xv ke vubba sbülz SyS coïst sy7of sdjaj 257bt colsf jasye xd5aj od3nk brlny yclpt la5sg av nzszs sh5f2 uvu sf1ev bbóia sg5dg uxbac zedad yalyk brSny weday ke5lm jwlds ny7sb wq2mm lxfeeo nk2ny stSev praya Iodeo ykokk finsbr oolwe njOls unluy di7/w mm22p wvsd of7wq njals xy7gn lafing dxOux vrlue ahded sp4dg snljw aefcc in7jn 4ededd hiSay finshr pobkew ny 3sh gn4ah ke0fm Answer: ke lefigg keOfin sg4dg br2ny sf5zv shöfz sol fmobr xd3nj nj4ls fzóco zv7xd ny3sb
<7 MORE EXAMPLES>
YOUR QUESTION: vy sk ag5gr ne nve co7os hubey pulss dpdje vy3sx pulkip wnzeo veblic dw5vy nelve vyQue spfumn kulrw vellhe 1z5max Jeh ab2pg pa7dp oeška Iflju hyögp gr5p gp5zm os2dq skóne dupen andis ju0ky ev2on mx isliu sx lon rwdaz, jeóhy jpliz dpOje iolIf is4po ssddw sk2ne sz4ij he lev go6ab uk0af en42g hy2ep
Reason step by step. Clearly mark your answer wriling" "Answer: <your answers' last line.
Table D.18: GPT4 and Gemini prompt for Pointer Execution's neighbor task with a task description. few-shot examples of the task, and request to reason step-by by-step.
We ablate the latter with a variation from Yasunaga et al.
28
Your fask tackle algorithmic problems. When presented with algorithmic problem, recall relevant prohlems examples. Afterward, proceed to solve the initial problem.
# PR: I give
sequence of words. Each word has four characters plus middle, words are separated by spaces. Start with the leftmost word. Output its neighbor. Then, match the last two characters of the curreat word (i.c not the neighbor) to the word starting with those two characters. Again, output the neighbor. Do this until your current word the neighbor) has mutch anymore.
Sequen CE: oj ce mmãeo in7ds uyOaz du4ki 5w celiss 5heve s1in yloom cesqu wvdgy dsški nj7ww slDin gylki 4k2sl lulni in3ds atllye ki7ee oi7mm kidee sirry hr3fw mjfje ce qu wo0mj quóei You ei2rk ve4mp quzei jefluy ehihs eafow gysev oulyl le omôna 19221 ro opžjm mnōhk pp mm2tn zwOld xqllu zkósl azfiqq bs7 caOsj xys ow5zy yy2qb oj ci4zk
# INSTRUCTIONS:
Relevant Problems:
Recall ihree examples of algorithmic problems that are relevant to the initial problem. Your problems should be distinct from each other and initial prohlem (e.g. involving different numhers and names and instructions). For each problem:
After "Q:" ", describe the problem
After 'A:" explain the solution and enclose the ultimate answer in \boxed(:
#e Solve the Initial Problem:
Q: Copy and paste the initial problem here.
A: Explain the solution and enclose the ultimate answer in Vboxed{) here.
Table D.19; GPT4 and Gemini prompt for PEN with the prompting technique introduced by Yasunaga al. 28
33

---

We further improved the level of help in the prompt by providing few-shot cf -hotthttt examples and sub-task few-shot chain-of of-thhtght examples in Table D.20 and D.2T respectively.
I give you as sequence words Fuch word four characters plus middle, words are sepamted by spaces. Start with loftrrstt wond. Output its neighoor Then, musch the last two characters of the current word (i.c. not the neightor) to the word starting with those two characters, Again, output the neighboe Do this until your curmen word (not the neighbor has no mutch anymone
EXAMPLE: E: ki gu wvlkk sdi rašan (efied aglou colwn wber (llg ae la hh by 3kj rklfy zusel untob fedfw fbew's gu30l ug5ib walks hnSw 2p nh7di kusah dh 7ym obl móii hikib ly Ir 1c2sh ounbow nk3pr tizay lnlnk ktlug is hi optre inflye sktop gev bwiich priju
The leftmrst word Now, we need find word that starts with "ki". The wond "ktlug" Its right neighhori "glhi"", so the next output wonl "iglhi".
hts right seightce
first outut word "gu".
Now, we need to find word that stans with 'ugg. The word is "ugStt" Its right neigthor is "wnDle"" so the next outpur word is "watk>r.
Now, we need find word that statss with 'tb". The word is "Istwb" Its right neighber is "gu50", the nest oulpui word is "gu30"
we
"wh", The
"whTer"" Its right neightor "Bitg". the outpui word is "IHdgg
Now; we need
weed stans with
word 'weal" right neightor is "hidah", so next outur word "hi4ca""
Now, we need to find word that stans with t6", The wordis is "iiza" Its right neighburis is "kxink", so the next output wond is "kellnk'
Now, we need find word that statts with 'wo" The word is "agdos" lirright neighbor is "coéen",
the next output word is "codwwn". "oa". word is "aatbur. Its right glohor "wkktpr" the
output word "skcppr"
Now, we need find word that starts with "bw". The werd "buskzh". Its right neighbor is "priju", su the next output word is "présu"
Now, we need to find word that stats with "sh". The word is "sh7qm". Iis right neighter is "oh so the next output word is "ablea". There is no word thet staris with "gm". we are done with the matching.
Therefore answer "gu ig hi wnika guóf (ldg hisub kelnk colwn npe prlju ablee"'
<? MORE EXAMPLES> YOUR QUESTION: jm og noler thisr duSij kaaam aeOad cyfth méllk am/rw iu0kg bj 7mu upaja rk ed selvv iwlli sistf dafddu mukef willer onlyr vacal ohtir qpfdt sitff atikk swiji doSgo sh lbk kniu muámmi jj2nd colpa adfidd rwDmm godbpp oxfoe alZeg bel toddd lalsb dmffww detio jm17kr mi5hj willw laz1 197au paski ikfodd datgp Resson step by step. Clearly mark your snswer by writing 'Anvwer syour anewers' as last line.
Table D.20: GPT4 and Gemini prompt for the Pointer Execution's 's neighbor task with few-shot chain of thought (Few-shot CoTT examples and a description.
give you sequence woods, word four charneters plus middle, words separnted spaces, Start with leftrestt word. Output neightor match the last two characters of the current word (ie. not the neighbor) to the word starting with those two churacters, Again, oulput the neighbor. Do this until your aurrent word (not the neighbor) his no mucch anymon.
EXAMPLE: sa rilkk kyavi ky modyl saSts yleet endry woldu valot tu7il kgOvt eiTex yillet pqmm modyl wofdd fo2aa citiy pañee etIly qinggi darkk xwihi vI5M heTei pa7tu v77hl milil ag modled bigg vitfcl hotten ntéve chéri ex2hy ry 7dd sylge witH filmm ddlis gndka
snilag 1y7gn ewhhy du3kg ciāvx
First find the motchiing soquence words, then find the neighhors.
Now we nead to find a word that starts with "sa". The word is "suS6"".
Now we nead to find word that starts with Tk"". The word ls "foZai".
Now need find word that starts
The word "ailee""
Now we nend to find wand that starts with The wond "cntry".
Now we sead to find ward that starts with "ty" The word is 741""
Now need find word that starts with "dd". The word 'ddl "wittr".
Now neal find
that starts
Now we nead find word that starts with The word "M7hh""
Now we need to find word that starts with 'bl'. The word is "bl3gk"
Now we nead find word that starts with "gk". The word is "gk2am"" Now we need find word that starts
"ym"
word gi".
There is no wand that staris with 'si", so we are done with the matching. Now we nead to find the neightoess of the matched words.
The right neighbor of "sa" is "eo".
right neighber "saSfs" "ylfie".
The right neighher "Mkaal" is "eibry"
The right neighbor of "aillen" is "kgdve".
The right neighbor of "cnOry" "wo7du"
right neighber of "ry/idd "fyfiaa".
The right neighber of "dillii" is gadlo..
The right neighber of "witat"s is "il"m"".
The right neighber of "asffel's "uuiil..
right neighber "bl3gk" "viold".
The right neighber of "gk2em" is "mx4y?""
The right neighbor of "qm/gi" is "duikk"
Therefore the answer isc "wo yléei ettly lgtht woldu Eyfgn gn3tu fdlms tulil višid modyl duckg"
<J MORE EXAMPLES>
YOUR QUESTION: 1m2 fime Iglat pb4ex la3v gdwa sclii my2sh whllg my isb uglms djlيp di2mm sx xylny kilkly ny ro4my osSun gle tkSkp dep yašda sh2nj nalse reōmy gáin sbúuj lygg gdliwa talma datup ma3gp zplph dulx zoqd faily tokce vpásy rylle vedgs phlls dolti ow5y abuu yklwe yplta ggSeb 65vp evödh mefio bafut 5bc jip agoos st0y iuddu kibda xutia zpāyb bolor yhówn oelys li5fz
Reason step by step. Clearyy mork your answer by writing 'Answer syour answers' as last line.
Table D.21: GPT4 and Gemini prompt for the Pointer Execution's 's neighbor task with sub-task chain of thought (Sub-task CoT) examples and description.
34

---

In Table D.22, we include the advanced sub-task few-shot CoT for the PERM task.
I giive you sequence words, The last word (after the "I") is the word start with, Now match match the last two charncters of the current word to the word starting with those two characters. If this match was going to the left, i.. the matched word is left of the current word in the sequence, increase variable counting the number left matchings. Do this until your current Finally, oulput this sequence of words, in reverse order in the formal word.a where x is the number of left mutchings uniil the ouiput word times the number matchings until curput word. Example answer: abod.4
has match anymore.
ghef.0
EXAMPLE: kpoms gethy pkotq godey mf0kp msOjd hiogo vuovu vl0gg baOvl arOpk io0bn jdOhl byOjm eydoy oy0mf gyodo I lrOpp
First, let's enumeerte the words:
1kp0mms
2:gg0hy
3 3:pk0kq
4:golley
Somiikp
6xms00d
7-hilggo
RevaOvu
9rv10gg
10:ba0v
1ppkkp
12:g00n
jd0hl
14:hy0jm
15ayy0oy
16:0y0mnf
17:gy(lo
Starting with "arOpk", let's match and calculate:
"arOpk" matches with "pk0ku". The word "arlpk" is 11th and "pkllq"" is 3th, so left matches so far. "pkórq"" matches with "IgObn'. The word "pkctq" is 3th and "tyOhn" is 12th left matches far, "tqOOn" matches with "baOvl". The werd "tq0lnn is 12th and "ba0el" is 10th, so 2 left matches so far. "batkv"" matches with "vIlgg". "vl0gg" mutches with "gg0ky". The word "villgg" is 9th and "getthy" is 2th, so left matches so fur. word "ggthh"
word "bativl"
"v10ge" 9th,
matches
"zg0hy" matches with "hy0jm".
"hy0jm" 14th,
matches
There no further matches for 'hyOjm" so we end the sequence here.
Finally, calculate the number of left matches times the number matches for each word get:
arOpk: 000=0 0-0=0
pkDu: 1=1=1
400e: 1=2=2
baovl: 2"3w6
villg:: 3*4=12
geOhy: 4-5=20
hy0jm: 4*6=24
Thus, answer "hy0jm.24 gg0hy.20 v10gg.12 hn0vi.6 tylhn.2 pkOiq.1 arOpk.0".
EXAMPLES>
question: sollpp Isfif vsfchh ekōin zgüek wtQsl spOsv umols rhile hyOkt slOvs in0hyy dfDum svDnh ktDzg rhOks Reason step by step. Clearly mark your answer wriling' 'Answer: eyour answer>' last line.
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 thain-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 a sequence needed enumeration.
In Table D.23 we include the prompt that was used for the code interepreter.
T give you sequence of words. Fach word has four characters plus middle, words are separated by spaces. Start with the leftmost word. Output its neighbor. Then, match last two characters the current word (.c. not the neighbor) to word starting with those two characters. Again, output the neighbor. Do this until your current word (not the neighbor) has match anymere.
EXAMPLE: hn feónt vj4ks yks f66mk lofox yd5pp de2rk mk3yj wj2fe wkf0m yoōkt ks5wk ox lyk wkóhm 7cj oi ah7 ksOwk vefihh gyTyd ns4vq hm3gv vsšho vjöks kjoau yd6pt baidd mk2vi gg5lx pt-ky ho?lo oišn an7qg fi0mk ztáas nd4zd ktivs gvoyd 1x2de faOut dd5ry plaxv ry7yo bm0gg ANSWER: mk2vj prix bm0gy ks5wk gvoyd vjöks oi5fi yd5pt wk6bm fi6mk YOUR QUESTION: be va po7mu
vušpf nulsb ag2uf vd5va epšqt ok2oj ngáep gis bo4sx is2nu sx3lq po2mu 1ç400 sblvd whOlw ojzax qb2vg mu4xm bąfcu nuDsb pfag ax2pc yh7bm sbrvd gı5vu vdl fasaj ojuax eutkgg ekdoj 2e3gx am3ig oo5hy mu7xm bp7gz Iw3ng vi7ko sjzjy xmdig spofa ax6pe gx3wh getic uf5xp igāis q15hh m5lk
Reason step by step. Then, the cade interpreter to solve the task. Clearly mark your answer by writing 'Anwwer: eyour answers' last line.
Table D.23: GPT4 prompt for the Pointer Execution's 's neighbor task with code interpreter.
35

---

I give you sequence words. The last word (afler the "I") is the word to start with, Now malch match the last two characters of the current word to the word starting with those characters, If this match going the left, i.c. the matched word left of the current word in the soquence, increase a variable counting the number of left matchings. Do this until your current word has no match anymore. Finally, ociput this sequence words, reverse order the format werd.x where
number of left matchings until the ourput word times the number matchings until the ouiput word. Example answer: abed.4 efab. ghef.0
EXAMPLE: ud0kg wplme yyOno xgoyy srOmw pgOyg oqlzz me0lg uoube eptepp rstav brooi oiOud mrOpp octhrp avtic tz0th yęOtz thors vk00x stOmm
Starting with "stUmw". let's match and calculates
"srOmw" matches with "mw0lq". No left match, left matches so far.
"mw0oq" matches with "oq0zt" This left match, left matches far.
There are no further matches for "oq02t", so we end the sequence here. Reversing sequence formatting as per the instructions, we gel:
og0zt.2
ua00oq.0
sr0mw.0
This, the answer is 2oq02t:2 marlon 0 srOmnw.0".
EXAMPLE: vallep xvōtx melht xxOds dsfre reOrm txOrg shōvs xillow pflss ghösh eplime bwüxv rn0gh st0pf kh0of xx0ds Starting with "xxtlds" let's match and calculate:
"xxOde" matches with "dailre.. No left match, 0 left matches sa far. matches "se0mm" matches with "ma0gh. No left match, left matches far. "mmllgh" matches with "ghllsht. This is a left match. left matches so far. "ghOsh" matches with "shDess.. This left match, 2 left matches "shOvs" matches with "vs0ep", This is a left match, left matches so far. "vstlep" matches with "eplime". No match,
"dsOre" matches "re0mm". No match,
matches
"epfine" matches with "melixe. This a left match, 4 left matches so far. matches far,
"metxt" matches with "xtObw", No match, "xttbw" matches with "bwOxv". No left match, left matches so far. "bwtkv" mutches with "xv00x". This is a left match, left matches so far. "xvOrx" matches with "rx0rg". No left match, 5 left matches far.
There are no further matches for "txOtg", so we end the sequence here.
Reversing the sequenee and formatting it per the instructions, we
tx0rg.60
55
bwDxv.40
xt0bw.36 36
me0xt.12
ep0me.21
v80epp188
10
gh0sh.4
m0gh.0
re0rm.0
dsUre.0
x
Thus, the unswer is: "Ix0tt.60) xv0lx..5 bwDxx.40 x60bw.36 me0xt.32 ep0mee:21 vsflep. 18 shilvs. ghish.4 miilghh re0mm.0 dsOre.0 xxOds.0"
<7 MORE EXAMPLES>
YOUR QUESTION: hwows gsogs equeq yzopt waOlw um0qd cafea tf0um df0df uoOlf fiouo proyz polie I fiOwo Reason by step, Clearly mark your unswer by writing 'Answer: syour answer>' as last line.
Table D.24: GPT4 and Gemini prompt for Pointer Execution Reverse Multicount with description and
wwwshot-hhin--oftthee
found to be similar the chain of thought the model chooses naturally.
The Os 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.
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract describes testing LLMs on compositional tasks and describes the most important results. It also mentions theoretical contributions. By describing the key points of the paper, the scope reflected.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer:[Yer
Justification: The paper explicitly discusses the limitations in section and tries to lay out all information for critical reading.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
37

---

Answer: [Yes]
Justification:
The paper provides the proofs and assumptions in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide extensive information to allow the replication of our experiments in Appendix B Appendix C and Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
38

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
open source our code at Limitations- 1m- algoritthae tarrithmii-oo compositionn learningg
We
IBM/
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, 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.T
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. 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 statements, certain trend 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 also handled this way 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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
39

---

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 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 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 figures symmetric error bars that would yield results that are out 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.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [No]
Justification: This information is inferable by looking at our hyperparameter settings, e.g. in C.1 and depends the precise framework used (e.g. Pytorch Lightning), which 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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, agree with the NeurIPS Code of Ethics https: sattps://nnet htpp::///nuripp http:///bccccccc.ccceeeeeellllle
Answer: [Yes]
Justification: To the best of our knowledge, our work has no societal impact besides advancing knowledge compositionality in LLMSs.
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. 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 compositionality in LLMs.
40

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: We work with randomly generated synthetic textual data which does not contain any information which would make it susceptible to misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite every work that contributed to our work.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
41

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of 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 s creators.
13. 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/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. 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 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 contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. 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 use crowdsourcing or human experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
42

---

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.
43

---

44


Reviews:
[{"review_id": "iOUHVqAS2M", "reviewer": "Reviewer_qmuR", "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.", "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?\n- Would the models perform differently on a broader variety of compositional tasks, particularly those that are more complex or domain-specific?\n- What specific modifications to model architecture or training strategies could be employed to enhance the sample efficiency of Transformer models in compositional learning?", "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.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper evaluates both training from scratch and in-context prompting methods, providing a thorough analysis of the models' capabilities.\n- The authors introduce new algorithmic tasks designed to test compositional learning and providing a theoretical framework to support the empirical findings.\n- The study offers a deep dive into the limitations of current LLMs, supported by both empirical data and theoretical arguments, which can guide future research in learning compositional tasks.", "weaknesses": "- The tasks and settings used in the experiments may not cover the full range of real-world applications, limiting the generalizability of the findings. \n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and questions.\n\n---\n\n**(W1)** We acknowledge that the investigated collection of tasks does not cover the full range of real-world applications. Nonetheless, this is a common choice across different works in this domain [paper references 16, 29, 30]. It allows us to operate in a **fully controlled** environment, limiting the impact of exogenous factors on the empirical observations while having the possibility to stress-test compositionality. Furthermore, we believe that working with synthetic datasets does not limit the generalizability of our findings. When a model fails to learn efficiently in a synthetic, fully controlled environment, it will even more do so in more complex, real-world scenarios, which present several additional challenges for the model (e.g., semantic and syntactic ambiguities, spurious correlations, distribution shifts, etc.).\nThis is also supported by a deep foundation of literature showing limited compositionality in practice [paper references 5, 8, 9, 11, 13 16]. \n\nMoreover, the synthetic nature of the considered tasks does not preclude the possibility of making observations that could be translated to more complex, real-world scenarios as well. One example is the multiplication task (MUL), a fundamental task in mathematics on which LLMs struggle without a significant amount of additional training [paper references 11, 16]. We speculate that both our empirical and theoretical results can shed light on this behavior, justifying it as an intrinsic inefficiency of LLMs in composing the simple sub-operations necessary to solve the task and quantifying their sample inefficiency in certain complexity classes.\n\n---\n\n**(W2)** While strictly speaking, our statements are limited to our tasks, in our investigation, we include a diverse range of algorithmic tasks and observe consistent behavior across all of them. Therefore, we expect that the same conclusions would hold on any similar tasks involving the composition of simple, known primitive operations (which occurs in many algorithmic, mathematical, and reasoning tasks). \n\n---\n\n**(W3)** We tried to clarify the tasks with an updated Figure 1, shown in the 1-page PDF note. \n\n---\n\n**(Q1)** Concerning the extent to which our observations could potentially extend to practical, real-world applications beyond the synthetic tasks used in the experiments, please refer to our observations in (W1). In addition, also refer to the general response (tokenization) with the additional results on the new Natural-PEN. \n\nOn the other hand, the reasons behind the introduction of the novel tasks are manyfold: \n- First, we argue for the introduction of algorithmic tasks based on the pointer execution, introduced by Bengio et al. [20] and so far absent in the landscape of research on compositional learning. This task limits the number of confounders in the data and, therefore, reduces (if not annihilates) the number of shortcut solutions that the model can find. In other words, pointer execution tasks force the model to learn an algorithmic (general) solution by design and not rely on any possible statistical shortcut that might compromise the validity of the observations.\n- As algorithmic tasks, PEN and PERM are particularly suitable for benchmarking compositionality. We can decompose them into single atomic operations (referred to as _primitives_ in the text), which can make learning the task easier if the model can identify and leverage their compositional nature. We clarify their decompositional nature in the response of W2 of reviewer Fa35.\n- 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.\n\n---\n\n**(Q2)** These LLMs would always perform decently if there is enough data. Our findings, however, are that the required data becomes excessive with more complex tasks. Our forecast is, therefore, that the more complex and the more domain-specific the tasks become, the harder it becomes for LLMs to perform them correctly (e.g., different to our education systems, where a student does not necessarily get more data for more complicated concepts). Concretely, in our experiments, this materializes in a model starting to hallucinate wrong solutions and failing at seemingly obvious executions (see GPT-4 experiments and Figure 2).\n\n---\n\n**(Q3)** There exists evidence [17, 61] that Transformers with weight-sharing between different layers and recurrence tend to perform better on compositional tasks than standard Transformer variants. It is for this reason that we also experimented with several such models during our work. We discuss details thereof in the general response.\n\nAdditionally, we independently investigated several novel architectural modifications aimed at increasing compositionality within the Transformer. One such idea has been penalizing superposition in favor of improving compositionality inspired by [Elhage et al., 2022, Olah, 2023], by including a single parameter modifying the read-outs from the latent representations for attention and feedforward blocks that penalize superposition and with that possibly encourages compositionality in the latent representations. We also built a Transformer that appends new computations from attention and feedforward passes (instead of adding) to a list of \"latent tokens\" with an additional attention mechanism to access those fields in the hope that compositionality can be encouraged. While some of those approaches did increase compositional capabilities on small datasets, we have not found a fundamental improvement in the domain of our experiments so far.\n\n[Elhage et al., 2022] https://arxiv.org/abs/2209.10652\n[Olah, 2023] https://transformer-circuits.pub/2023/superposition-composition/index.html", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q2YOdZspie", "reviewer": "Reviewer_DGs4", "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.", "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?\n2. 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?\n3. 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?\n4. 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.\n    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.\n    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.\n    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": "The authors discuss some limitations, but do not directly address the generalizability of their findings to natural tasks subtasks composition.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Aside from achieving state-of-the-art performance on many academic benchmarks, transformer-based language models are the undisputed workhorse for numerous real-world applications. However, their training does not necessitate compositional learning explicitly, while many of the tasks they are tasked at solving do require such capability. As such, understanding the limits and requirements for these models to learn to compose independent skills is key to drive our understanding of these foundational models and to improve them.   \n2. The analyzed tasks in the paper are very well defined to verify that a model that learns a task must know how to perform the subtasks, and that given capability to solve the subtasks, a model must only learn to compose these abilities to solve the task itself. Creating such settings is not trivial, and goes a long way to enhance our understanding of the compositional learning abilities of transformer models.\n3. The paper provides a very thorough literature review and contextualizes the work around prior work very well.\n4. The presentation of the paper is generally very nice, making a technical read easier and fluent.", "weaknesses": "1. The authors correctly identify tokenization as a possible negative confounder in the defined testbed, and thus use character-based tokenization for the training experiments. However, the same care is not taken when investigating the abilities of GPT4 and gemini to perform in-context-learning. Namely, given the highly synthetic nature of the inputs, it is highly possible that both the out-of-domain distribution of these inputs (deviating from natural texts) as well as differences in how inputs are tokenized (for example, one key can be tokenized with a single token, another by three tokens, and a third be tokenized along with parts of the corresponding value) confounds and skew the results, hindering their usefulness.\n2. 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)\n3. 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.ֿ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and observations.\n\n---\n\n**(W1)** We thank the reviewer for raising potential concerns regarding tokenizations. We already searched through different task designs to improve the performance of GPT-4 and Gemini-Pro. The reviews motivated us to conduct further investigations and quantification primarily on the openly available GPT-4 tokenizer. Our findings can be summarized as follows (see the general response for a detailed discussion): \n\n- We ablated different task designs in the initial submission; however, we found that the current sequence design (e.g., \"ab1cd\") performs best among other alternatives (such as \"ab-1-cd\").\n- As an additional analysis, we tested the tokenization of GPT-4's open-source tokenizer (tiktoken). We found that the digit delimiter is always tokenized separately (e.g., \"ab1cd\" yields \"ab\", \"1\", and \"cd\"); hence, it does not have a detrimental effect on the attention mechanism. We found that some of the 2-grams were split into 2 tokens; however, removing them from the dataset did not improve the overall task accuracy with the best-performing prompting technique.\n- We designed a new natural variation of PEN, dubbed Natural-PEN, where we replaced the synthetic 2-gram sequences with 3-gram, in-distribution, natural English words. Overall, we found that GPT-4's performance does not improve on this in-distribution, natural English words, yielding even a lower accuracy on Natural-PEN.\n---\n**(W2)** Thanks for the comment and the relevant pointers! Following your suggestion, we provided the models with a more consistent number of shots on both PEN and PERM to verify whether increasing the number of examples beyond 8 would highlight an increase in the models' accuracy. We provided up to 32 examples (64 did not fit into the 8k context window of the GPT-4 version we are using). However, we did not observe any performance improvement, as reported in the table below. \n\n|Model|Task |Termination Acc.|Match Acc.|Task Acc.|\n|-----|---|----|----|----|\n|GTP-4|PEN|0.16|0.06|0.0|   \n|Gemini-Pro|PEN|0.15|0.2|0.0|   \n|GPT-4|PERM|0.36|0.59|0.0|   \n|Gemini-Pro|PERM |0.32|0.05|0.0| \n\nWe believe that the helpfulness of the additional examples might depend on the considered task and that, in some cases, there could be no improvements or even considerable sensitivity to the number of prompts. If you consider these results relevant, an Appendix on them could be added upon acceptance.\n\n---\n\n**(W3)** This is a limitation of our current results. However, we did experiment with different sizes of LLaMA up to 600M. Because we could train a 33M model to perform the PEN task well, it is reasonable to assume a 150M model should be sufficiently large, and hence present our results with this model. Regarding other architectures, we also ablated a Universal-Transformer-style model in Appendix B.5 thanks to their good performance on compositional tasks like SCAN [61]. This model (UT-style LLaMA) has only one layer with the same configuration (embedding size 1024, 16 heads), and this layer is repeated. We achieved very similar results with UT-style LLaMA (Table B.10) compared to our main model. Please see our general response for more variants of architectures that we tried.\n\n---\n\n**(Q1)** This is an interesting question, thanks for pointing to the prior work for discussion in our paper and suggesting a more general research direction. In our investigation, the tasks considered do not present unobserved local structures since the composition of primitives only admits a specific combination of operations (e.g., RIGHT[MATCH[LEFT[MATCH]]] in PEN), and the trained models should always have (at least in principle) the possibility to observe and learn this specific sub-graph in the computational graph.\n\nThis is a desired property as the goal of our investigation was not to stress-test how well Transformer language models can learn arbitrary difficult compositional tasks but rather to measure how **sample efficient** they are in learning the composition of simple primitives in algorithmic tasks. Considering more tasks characterized by more complex phenomena (such as unobserved compositions of the primitives, spurious correlations in the data, semantical ambiguities, etc.) would have hence partially defeated this purpose, contaminating the effects of the intrinsic limitation of the Transformer model with other factors.\n\nHowever, after observing and validating our hypotheses on the simple synthetic datasets, we still believe that it would be compelling to extend the analysis to more natural compositional tasks such as the ones investigated by Bogin et al. It would allow us to verify how well the observed behavior scales in a real-world scenario, possibly providing new angles to it.\n\n---\n\n**(Q2)** Please refer to the results presented in (W1) and to the note on tokenization included in the general response.\n\n---\n\n**(Q3)** We report here the exact specifications of the models that we trained in our experiments. We use the Adam optimizer, a hidden size of 1024 and 12 layers. The model is a standard LLaMA 2 implementation, decoder only with Rope positional encoding and a Swiglu feedforward net. We did not use Grouped Query Attention, as LLaMA models do not use them in their smaller sizes.\nFor what concerns the possible ablations on width/depth and larger models, we performed some minor ablations on them, but we observed no changes in the results, discouraging us from proceeding further in this direction (see our response in (W3) as well). However, as pointed out in your question, it would be interesting to observe whether the size and depth of the model can play a role in the learning efficiency, and if this interplay can be characterized through similar scaling laws such as Kaplan's. \n\n---\n\n**(Q4)** We would like to extend our sincere gratitude for the suggestions on the presentation and writing in general. We will incorporate them upon acceptance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9DIRWfvxxd", "reviewer": "Reviewer_teuc", "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. \nH1. An LLM can learn to perform a compositional task with constant number of datapoints. \nH2. An LLM can learn to perform a compositional task, given as many sample as the most difficult sub-task required.\nH3. An LLM can learn to perform a compositional task, given the data samples of relearning all sub-tasks for learning the composition.\nH4. An LLM can learn to perform a compositional task, given more data samples in H3.\nThe authors introduces a new benchmark for creating systematic sub-tasks and testing compositionally.\nWith 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.", "questions": "Q1. Is the PEN dataset only corresponding to one underlying program?  \nQ2. What are the insights of PEN and PERM these two datasets?", "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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality: 3.5 / 5\n\nThis paper examines how the number of datapoint samples affects the learning of compositional tasks in existing transformer-based large language models (LLMs). The authors created a new, challenging compositional dataset based on computation graphs and demonstrated that learning compositional tasks with LLMs is highly data-inefficient. While the BIG-bench paper indicates the insufficiency of reasoning and compositional abilities in LLMs, this paper innovatively provides a concrete, quantitative, and extensive study on the extent of this insufficiency.\n\nQuality: 3.5/5\n\nThe empirical study is pretty extensive with both LLaMA, GPT-4 and Gemini. There are multiple prompting techniques adopted with GPT-4 and Gemini, all of them fails to generate a reliable result. There are also very interesting theotrical proofs in the appendix to bolster the authors' claims. \n\nClarity: 3/5\n\nFigure 1 is hard to understand just by staring at the graph. For each task, it only provides one example which is non-trivial at all. One can hardly figure out its ground truth program for each example, and whether in a task of PE, is the underlying program the same across all the datapoints. I believe a descriptive caption by the side of each task is necessary. For example, PE refers to a program that takes a sequence of words and returns a list of words all colored green, where the first output word matches the first input word, and any subsequent output word starts with the last two characters of the previous word. However, the figures and tables in the experimental section are pretty clear and helpful to understand. \n\nSignificance: 2.5/5\n\nUnderstanding the problem of the data inefficiency in transformer based LLMs is important to the community which focuses on data efficiency and reasoning, such as neuro-symbolic community.", "weaknesses": "As stated in the strengths above. One of the main issue is the clarity issue of the tasks. Besides \"what is the task\", I also want to understand \"why these two tasks are needed\". What do PEN and PERM these two datasets bring?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback, insightful comments, and observations. \n\n**PEN and PERM: clarification and motivation**\nTo better understand the PEN and PERM tasks, we start the exposition by explaining the original Pointer Execution (PE) task using our encoding scheme.\n\nThe PE task is similar to linked list traversal or pointer chasing. The inputs are words delimited by whitespaces, where each word consists of an address, a delimiter, and a value. In our setup, addresses and values are each encoded using two letters from the English alphabet, and the delimiter is a single digit between 0 and 9. For example, uk7bh has \"uk\" as the address, 7 as the delimiter, and \"bh\" as the value. The first word in the input sequence is a single address, which points to a unique word in the sequence, starting the linked list traversal process. The sequence is traversed by reading out the value of the current word and matching it to the unique word whose address equals the current value. The traversal ends once there is no word whose address equals the value of the current word.\n\nFor example, given the input sequence \"aa bc1yu aa5bc op9mn\", the correct word traversal order is \"aa aa5bc bc1yu\". \n\nThis type of task is especially suitable for our study, as it limits the number of confounders in the data and, therefore, reduces (if not annihilates) the number of shortcut solutions that the model can find. In other words, PE tasks force the model to learn an algorithmic (general) solution by design and not rely on any possible statistical shortcut that might compromise the validity of the observations.\n\nHowever, algorithmic tasks based on pointer chasing have so far been absent from the landscape of research on compositional learning. This is in large part due to the difficulty in expressing the PVR task using any primitive procedure except ``match``, which extracts the value of the word currently processed and finds the word whose address matches the value. Hence, our PEN and PERM tasks emerged from the need for a set of tasks that keep the beneficial properties of pointer-chasing tasks and can simultaneously be expressed as a composition of a set of simple primitives.\n\nThe algorithmic primitives we introduce in the PEN task are ``left`` and ``right``, which require the model to find the word to the left resp. to the right of the word that is currently being processed.\n\nThe input sequence is also modified and now consists of two sequences with interleaved elements. The first sequence is a valid PE sequence, whereas the second sequence is reminiscent of a PE sequence, but the values and addresses are not restricted to be unique. The two sequences have no common addresses or values. As an example, take the two sequences \"ab ab8cd cd6ef\" and \"gh gh9kl gh6ij\". The first one is a valid PE sequence, and the second one has the repeated address \"gh\". The corresponding PEN sequence is \"ab gh ab8cd gh9kl cd6ef gh6ij\". The task consists of traversing the pointers of the first of the two interleaved sequences while, at each traversal step, outputting the word to the right of the word currently traversed (the neighbor).\n\nThe fact that the model needs to output the neighbor combined with the neighbor's value, possibly having several matching addresses in the sequence, makes PEN a challenging compositional task, which can still be solved using only a few algorithmic primitives.\n\nThe PERM task is also based on the PE task, with a slightly different encoding of the sequence elements. The elements now consist of four letters from the English alphabet, to be interpreted as pairs of addresses and values, each encoded using two characters. The first element in the pointer traversal is explicitly provided.\n\nPERM builds on top of the PE task by requesting that the sequence of words in the pointer chasing problem be output in reverse order, and it additionally involves keeping track of the length of the chain of pointers as well as the pointer orientation, i.e., does it point to the left or to the right of the current word.\n\nLet us start with the following example sequence: \"aabb eeff ccdd bbcc ddee\", with the initial word being \"aabb\". Following the sequence of pointers starting from \"aabb\" results in the following sequence: \"aabb bbcc ccdd ddee eeff\". Each element in the resulting sequence has two numerical values associated with it, these being the length of the preceding pointer chain ('count') as well as the number of 'left'-pointers in the chain preceding the current element ('count left'). In our example here, the relevant sequences and numerical values are represented below:\n\nInput sequence:             \"aabb eeff ccdd bbcc ddee\"\n\nPointer chasing result:     \"aabb bbcc ccdd ddee eeff\"\n\nCount:                        0    1    2    3    4\n\nCount left:                   0    0    1    1    2\n\nEach step in the pointer-chasing procedure increases the \"count\" by one.\n\n\"bbcc\" -> \"ccdd\" is the first pointer oriented to the left, and so it increases \"count left\" from 0 to 1. \"ddee\" -> \"eeff\" is the second pointer oriented to the left, and it increases \"count left\" from 1 to 2.\n\nThe final result is obtained by outputting the pointer chasing result in reverse order and associating with each word in the output sequence a number equal to \"count\" multiplied by \"count left\" for that word. This results in the following output:\n\nInput sequence:  'aabb   eeff    ccdd    bbcc    ddee'\n\nPERM result:     'aabb.0 bbcc.0  ccdd.2  ddee.3  eeff.8'\n\n---\n\n**(Q1)** We cannot guarantee that our decomposition of the PEN task into the primitives \"match\", \"left\" and \"right\" is unique. A different set of primitives will lead to a different decomposition. However, given our set of very simple primitives, it is highly unlikely that there exists a decomposition different from what we provide in the PDF. \n\n---\n\n**(Q2)** We refer to our answer Q1 of reviewer qmuR.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0txzQgon0j", "reviewer": "Reviewer_Fa35", "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.", "questions": "See weaknesses.", "limitations": "Limitations of not solving the issues raised are addressed in the paper.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The paper proposes an interesting question as to whether we can determine whether a language model has some higher level concept of task composition that allows it to learn compositions of previously learned tasks efficiently. \n\n2. The paper includes a nice theoretical result via a complexity theory reduction that shows how composition is hard if we assume stylized models that memorize the training data.", "weaknesses": "1. H1 as written cannot be disproven empirically since the \"constant\" could just be larger than those tested. It seems in the experiments \"constant\" means 100. If that is what is meant, then just say so in the hypothesis. \n\n2. 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). \n\n3. 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.  \n\n4. 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. \n\n5. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and observations.\n\n---\n\n**(W1)** As shown in our results, H1 can be fixed to a very large range, and 100 was chosen for illustrational purposes; what is crucial is that we assume it is empirically much lower than H2. This means that H1 is defined to make the hypothesis more accessible and actionable, and it should only depict an upper bound of \"a few demonstrations\" i.e., we got inspired by what one would usually give in a few-shot and took an upper bound. We also refer to the PAC learning theorem, where the logarithmic factor shows that with very few samples, a large hypothesis space can be reduced, making a constant assumption on limited-complexity tasks reasonable in practice.\n\n---\n\n**(W2)** Thanks for the critique, it is indeed an important aspect that was not sufficiently clarified in the manuscript. In the introduced tasks, every primitive roughly corresponds to a basic block of operations in the equivalent procedural programming language and can be considered an atomic unit. To visualize the atomicity of the primitives within the tasks, we included pseudocode that shows how the introduced tasks (PEN and PERM) can be decomposed and solved with these primitives by a language model trained on next-token prediction in the additional 1-page PDF note.\n\nThe definition of these sub-tasks is, per se, not unique. However, our definition of sub-tasks is _minimal_, as every primitive is independently observed in only one task (as described in Section 2.2), and the primitives are atomic. In addition, we argue that our observations are independent of the optimality and uniqueness of primitives and sub-tasks. The inefficiency observed is _relative_ to the given set of primitives and not defined in absolute terms. Finally, we cannot completely exclude the existence of an \"optimal\" set of primitives that could be easily re-combined by the model to learn compositional tasks efficiently. However, this possibility is deemed unrealistic by some of our experimental results. For instance, in our de-compositionality experiments (Section 4.2 and Tables B8, B9) we see that the model learns the sub-tasks much faster when pre-trained on the composition task. We speculate that this provides evidence that the model learns mechanisms similar to our primitives and that the learning inefficiency is, hence, mostly imputable to the difficulty of the model to recombine the primitives (which would not be solved by a better set of primitives).\n\n---\n\n**(W3)** Thank you very much for your question. We tried to improve the exposition of the tasks and their motivation in our rebuttal to the reviewer teuc. In addition, we also improved Figure 1, please refer to the additional 1-page PDF note. \n\n---\n\n**(W4)** This is a valid concern. Firstly, we argue that experimenting with small, un-trained models can still be interesting to test whether the compositionality can emerge naturally or not (as this result could be then potentially translated to real-world practical application) and provide insights on the intrinsic limitations of Transformer-based models on these tasks. Then, we highlight that in our experiments we also incorporated a certain amount of inductive bias toward compositional solution. For example:\n- _In-context learning_. We prompted GPT-4 and Gemini-Pro extensively and demonstrated that they did not learn to compose their primitives successfully enough to even perform the tasks when given a clear description and a large number of examples. Please find the new results with many-shot prompting in the general response.\n- _Training the model from scratch_. Note that we provided hints to the model such that learning how to compose learned primitive sub-tasks is made easier. We do this by introducing the PEV (Pointer-Execution Verbose) to the list of sub-tasks, which implicitly shows to the model the order in which the other subtasks need to be applied to solve PEN. For results with different architectures, please see \"ablations with different architectures\" in our general response.\n- _Fine-tuning of larger pre-trained models_. Inspired by your comment, we have designed a new set of experiments to fine-tune larger pre-trained models on our algorithmic tasks, to validate whether the bigger size and/or the pre-train knowledge would affect our observations. Unfortunately, this kind of training takes a considerable amount of time, but we hope to be able to provide practical results before the end of the discussion period.\n\n---\n\n**(W5)** Thank you for raising potential concerns regarding tokenizations. We already searched through different task designs to improve the performance of GPT-4 and Gemini-Pro. The reviews motivated us to conduct further investigations and quantification primarily on the openly available GPT-4 tokenizer. Our findings can be summarized as follows (see the general response for a detailed discussion): \n- We ablated different task designs in the initial submission; however, we found that the current sequence design (e.g., \"ab1cd\") performs best among other alternatives (such as \"ab-1-cd\").\n- As an additional analysis, we tested the tokenization of GPT-4's open-source tokenizer (tiktoken). We found that the digit delimiter is always tokenized separately (e.g., \"ab1cd\" yields \"ab\", \"1\", and \"cd\"); hence, it does not have a detrimental effect on the attention mechanism. We found that some of the 2-grams were split into 2 tokens; however, removing them from the dataset did not improve the overall task accuracy with the best-performing prompting technique.\n- We designed a new natural variation of PEN, dubbed Natural-PEN, where we replaced the synthetic 2-gram sequences with 3-gram, in-distribution, natural English words. Overall, we found that the GPT-4's performance does not improve on this in-distribution, natural English words, yielding even a lower accuracy on Natural-PEN.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We want to thank all the reviewers for their helpful and supporting comments. We are encouraged that they acknowledge the importance of addressing current Transformer models'  limitation in learning compositional tasks (DGs4, teuc), and that w.r.t. other benchmarks such as BIG-bench, our work provides a concrete, quantitative, and extensive study on the extent of this insufficiency (teuc) by introducing two novel evaluation benchmarks (i.e., PEN and PERM). Moreover, we are glad that they appreciate the thoroughness of our analysis (teuc, qmuR) with both from scratch and in-context learning, as well as theoretical proofs (teuc, Fa35, qmuR).

In this general response, we summarize our response to the reviewer's major concerns. A point-by-point response to each reviewer can be found in the individual responses. 

## Tokenization
We thank the reviewers for raising potential concerns regarding tokenizations. Indeed, we already searched through different task designs to improve the performance of GPT-4 and Gemini-Pro. The reviews motivated us to conduct further investigations and quantifications primarily on the openly available GPT-4 tokenizer. Our findings can be summarized as follows:

**Different task designs**
While preparing the initial submission, we already ablated the structure of the PEN and PERM examples fed into the LLMs to validate whether differences in the representation of the task could affect the tokenization and, indirectly, the performance of the model. One example of an ablated structure involved adding dashes to the sequences (e.g., "ab-1-cd"). However, these variations in the structure did not achieve any improvement over our base formulation of the tasks.

**Tokenizer analysis with GPT-4**
To shed more light on tokenization, we additionally tested the validity of the prompting technique reported in the manuscript for GPT-4 using its 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 GPT-4's tokenization on our tasks showed that our induced sequence structure with digits as delimiters ensures safe splitting within a word, e.g., "ab1cd" would be mapped to three tokens "ab", "2", and "cd". However, we saw that 13.2% of the 2-grams are split into two 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, this setup could not improve the performance (0.05 vs. 0.19 on PEN) when using the best-performing prompting technique with GPT-4 (Code Interpreter). Hence, tailoring the task to the tokenizer does not lead to an improved performance. 

**New Natural-PEN with in-distribution, natural English words**
Inspired by the comments of reviewer Fa35, we additionally designed a natural variation of the PEN, 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. To do so, we filtered all valid 3-gram words from Scrabble (https://scrabble.collinsdictionary.com/word-lists/three-letter-words-in-scrabble/) that resulted in 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:

|Setup |Termination Acc.|Match Acc.|Task Acc.|
|-----|----|----|----|
|Few-shot CoT|0.5|0.27|0.0|   
|Few-shot CoT, traps removed|0.2|0.29|0.0|   
|Code Interpreter|0.05|0.1|0.05|


## Many-shot prompting of GPT-4 and Gemini-Pro
Following suggestions of DGs4, we increased the number of shots from 8 examples up to 32 examples (64 did not fit into the 8k context window of the old GPT-4 version we are benchmarking). However, we did not observe any performance improvement, as reported below.

|Model|Task |Termination Acc.|Match Acc.|Task Acc.|
|-----|---|----|----|----|
|GTP-4|PEN|0.16|0.06|0.0|   
|Gemini-Pro|PEN|0.15|0.2|0.0|   
|GPT-4|PERM|0.36|0.59|0.0|   
|Gemini-Pro|PERM |0.32|0.05|0.0|

We believe that the helpfulness of the additional examples might be dependent on the considered task and that, in some cases, there could be no improvements or even considerable sensitivity to the number of prompts.

## Different architectures/configurations
Several reviewers rightfully questioned whether the architecture we used should be expected to learn compositionally. We obtained results with several different architectures based on the Universal Transformer (UT) [61] and the more recent Hyper-UT [17], for both of which there is evidence that they exhibit better compositional generalization than the original Transformer. For instance, a UT-style transformer displayed good performance on compositional tasks like SCAN [61]. The model based on UT reached a similar performance as the original LLaMA model, as documented in Appendix B.5, which placed it into the H4 category. 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 accuracies below that of 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. However, to improve the generalizability of our findings, we will include results with this particular architecture in a new Appendix.

Meta-review: 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.
Decision: Accept (poster)