Faith and Fate: Limits of Transformers on Compositionality
Authors: Nouha Dziri
Ximing Lu
Melanie Sclar
Xiang Lorraine Li
Liwei Jiang
Bill Yuchen Lin
Sean Welleck
Peter West
Chandra Bhagavatula
Ronan Le Bras
Jena D. Hwang
Soumya Sanyal
Xiang Ren
Allyson Ettinger
Zaid Harchaoui
Yejin Choi
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Natural language processing
large language models
multi-step reasoning
TL;DR: We study the limits of Transformers confronted with compositional tasks that require multi-step reasoning to arrive at the solution.

Abstract: Transformer large language models (LLMs) have sparked admiration for their exceptional performance on tasks that demand intricate multi-step reasoning. Yet, these models simultaneously show failures on surprisingly trivial problems. 
This begs the question: Are these errors incidental, or do they signal more substantial limitations?
In an attempt to demystify transformer LLMs, we investigate the limits of these models across three representative compositional tasks---multi-digit multiplication, logic grid puzzles, and a classic dynamic programming problem. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.  We formulate compositional tasks as computation graphs to systematically quantify the level of complexity, and break down reasoning steps into intermediate sub-procedures. 
Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching, without necessarily developing systematic problem-solving skills.  To round off our empirical study, we provide theoretical arguments on abstract multi-step reasoning problems that highlight how autoregressive generations' performance can rapidly decay with increased task complexity.

Faith and Fate:
Limits of Transformers on Compositionality
Nouha Dziri' Ximing Lu Lu+ Melanie Sclar?
Xiang Lorraine Li Liwei Jiang 1.21 Bill Yuchen Lin
Peter West 1.2 Chandra Bhagavatula', Ronan Le Bras' Jena D. Hwang', Soumya Sanyal'
Sean Welleck Xiang Ren 1.3, Allyson Ettinger Zaid Harchaoui 12, Yejin Choil.2
Allen Institute for Artificial Intelligence Univerrity of Washington
University of Southern California *University of Chicago
nouhad@allenai.co org,
kiminglu@@lleenii.oom msclarθcs washington edu
Abstract
Transformer large language models (LLMs) have sparked admiration for their exceptional performance on tasks that demand intricate multi-step reasoning. Yet, these models simultaneously show failures on surprisingly trivial problems. This begs the question: Are these errors incidental, or do they signal more substantial limitations? In attempt to demystify transformer LLMs, investigate the limits these models across three representative compositional tasks tasks-multi-digg multi-digit multi- plication, logic grid puzzles, and classic dynamic programming problem. These tasks require breaking problems down into sub-steps and synthesizing these steps into precise answer. We formulate compositional tasks as computation graphs systematically quantify the level of complexity, and break down reasoning steps into intermediate aob-procedures. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reason- ing into linearized subgraph matching, without necessarily developing systematic problem-sol voiiig skills. To round off our empirical study, we provide theoretical arguments abstract multi-step reasoning problems that highlight how autoregres- sive generations' performance can rapidly decay with increased task complexity.
Introduction
"It was the epoch of belief. it was the epoch of incredulity."
Charles Dickens, Tale of Two Cities
55 demonstrate unprecedented capa- stark contrast, the same models For instance, humans can solve 3-digit by 3-digit multiplication arithmetic after learning basic calculation rules [2 34 Yet, off- off-the-shelff
Large-scale transformers such as ChatGPT (57] and GPT4
bilities [57]
15 (85] even noted "sparks of AGI"
sometimes struggle with simple, intuitive tasks 9 62 40
ChatGPT and GPT4 achieve only 55% and 59% accuracies on this task, respectively ($3).
The striking discrepancy between the impressive successes of transformer LLMss seemingly complex tasks and the astonishing failures on seemingly trivial tasks spark critical open questions about how faithfully interpret their mixed capabilities. Under what conditions do transformers succeed, fail, and why? What types of errors do they make? Can transformers uncover implicit problem-solving rules or be taught to follow reasoning paths?
Seeking thorough answers to these questions remains an open research challenge. However, we offer novel insights into the fundamental limits of transformery? centered around compositional
First co-authors. Second co-authors.
For brevity, use "raanffrmmes' to refer to 'autoregressive transformer L.Mss throughout the paper.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

problems that require strict multi- reasoning to derive correct predictions. Applying step-by-step reasoning is fundamental to human intelligence [69 68]. These compositional problems present compelling challenges for Al systems as they require combining basic reasoning operations to follow computational paths that arrive at unique correct solutions. In particular, we study three straightforward and flexible representative compositional tasks: forgform multiplication, logic grid puzzles (i.e., Einstein's 's puzzle [61]), and a classic dynamic programming problem.
We propose two hypotheses. First, transformers solve compositional tasks by reducing multi-step compositional reasoning into linearized path matching. This contrasts with the systematic multi-step reasoning approach that learns to apply underlying computational rules required for building correct answers [7] 37 (7). Shortcut learning [29] via pattern- mattehnn may yield fast correct answers when similar compositional patterns are available during training but does not allow for robust generalization to uncommon or complex examples. Second, due to error propagation, transformers may have inherent limitations on solving high-complexity compositional tasks that exhibit novel patterns. Errors in the early stages of the computational process can lead to substantial compounding errors in subsequent steps, preventing models from finding correct solutions.
To investigate our hypotheses, we formulate compositional tasks as computation graphs These graphs break down problem-solving into submodular functional steps, enabling structured measurements of complexity and verbalization of computational steps as input sequences to language models. Moreover, we leverage information gain to predict patterns that models are likely to learn based on the underlying task distribution without the need to perform full computations within the graph.
Empirical results show that training on task-specific data leads to near-perfect performance on in- domain instances and under low compositional complexity, but fails drastically on instances outside of this region. This substantial gap suggests that systematic problem-solving capabilities do not emerge from maximum likelihood training (5] on input-output sequences, even when prompted or trained with human-like reasoning steps (i.e., a linearization of computation graphs; $3.1). Models' success can be attributed, in part, to their exposure training examples sub-graphs that involve the same computations required for solving test examples (see Section B.2.2] In order to gain a deeper understanding of models' failures, we conduct a comprehensive analysis by decomposing their computation graphs and examining different error types. We find that while models can memorize single-step operations, they fail to compose them into correct reasoning paths, suggesting that they mostly make predictions based on shallow, rote learning rather than deep, holistic task understanding ($3.2.3). Importantly, we provide theoretical evidence of exponential error accumulation using abstract compositional tasks. All tasks analyzed empirically in this paper are instantiations of these abstractions ($4). We argue that transformers could be inherently limited in solving compositionally complex tasks out-of-the-boxf
As transformers continue to make tangible real-world impacts, is pressing to interpret their re- markable performance critically. Our work takes a realistic look at the limitations of transformers in the context of compositional tasks. To shed light on practical future steps. we identify directions for addressing these limitations, such as using transformers for tasks that could be decomposed into few reasoning steps, tasks where evaluation may afford some leniency, and using transformers in combination with planning modules or refinement methods to improve their generations. To advance language AI, fundamental innovations are required to address or complement these limitations.
2 Measuring Limitations of Transformers in Compositional Tasks
Human probiem-solving skills can be conceptualized sents a partial solution and the edges represent operators that can be applied to modify these solutions. As we will outline next and illustrate in Figure [ we use computation graphs and corresponding metrics to methodically evaluate transformers' reasoning abilities.
graph structure, where each vertex repre-
2.1 Computation Graph Definition
Let A be deterministic algorithm (function), and let FA be a set of primitives (functions) the algorithm uses in its execution. Assuming the inputs x algorithm are given, we define A(x)'s static computation graph GA(X)- G = (V, E, s, op) is directed acyclic graph. Nodes V
"oode and data available at http:///gttttu...o/oooooouttttht http:/ddiiitttaaatt--------t-tt-
2

---

function multiply (x]1..pl, 91)..1) miterply y(!)
28
for i ç to
carry for x[j] y[a]
A(x) for
[7,49]
14
carry
63
4
343
carry =t // 10
digitn[3] nod 10
[ummanda[1] digits
purtink sumlts (ewputtacion showa)
product Yi. (umandalgr:-41) 104-1
return product
A(X)
Color legend:
muiltppyy 1-cipit
carry
mod
sum
concat
Figure I: Transformation of algorithm A to its computational graph G.(o)) The depicted example is of long-form multiplication algorithm A, for inputs [7, 19] (i.e. computing 7 49).
represent all variables' values during A's execution: each node v E V has a value s(v) E R associated. Edges E represent the function arguments involved in some computation: for each non- source node v E V, let U {ui..... Uj} C V be its parent nodes. Then, s(v) f(u..... Uj) for some FA- Since each node is uniquely defined by the computation of single primitive we define op : V + FA as op(v) =
Let S C V be the source nodes of G Aix) and without loss of generality, let o E V be its sole leaf node. By definition, S = and Axx) = s(o), representing the input and output of A respectively.
To be able to train and evaluate language model's 's ability to follow algorithm A we must linearize G G((s)) Since we only consider autoregressive models, this linearization must also be a topological ordering.
Quantifying Compositional Complexity using Graph Metrics
A' representation as computation graph G A(x) enables measuring task complexity from many angles.
We define node E V's layer number as the length of the longest path from source node in the directed acyclic graph G Aíe))- We then define the reasoning depth as the largest layer number in the graph. In computation graphs, reasoning depth a proxy for the maximum level of multi-hop reasoning required to solve the task.
Let ds V - No be the shortest distance to any of G's source nodes S C V. We define the reasoning width a graph as the mode of {d(v) v E V}. This metric aims to measure the maximum number of variables required maintain in parallel during the computation. Relatedly, also define the average parallelism of a graph as the ratio between [V] and reasoning depth. This aims compute the average width in computation through the graph, and not just in its mode.
2.3 Predicting Surface Patterns through Relative Information Gain
When evaluating model performance, we may observe partially correct answers even in an overall incorrect response. To understand model strategies in these partial successes, we use Relative Information Gain to predict surface patterns that models are likely to recognize. We We represent task 7 as a distribution (X,,..., Xn, Yi,... Yn)) and measure the amount of (normalized) information gained about an output element Y, by observing a subset of input random variables X C [X,]
RelativelG(Y,. HYY)) (Y,1)) [0,
(1)
H(Y,)
RelativeIG may be used to analyze the influence of any node in the computation graph (as defined in with respect set of its ancestors; in particular, output nodes with respect input nodes.
2..
2.4 Exploring Three Representative Compositional Tasks: Definitions
Multiplication Multi-digit multiplication requires executing operations with numerical symbols based on procedural rules 34 This task has multiple algorithmic solutions; in constructing computa- tion graphs, we use the well-known Okk k2) long-form multiplication algorithm for computing x y, where x has h < 5 digits and y has ha S 5 digits in base 10. See $A.1 for data construction details.

---

(8)
GPT4 zero-shot (Multiplication)
GPT4 zero-shot (Puzcle)
CPT4 pero-shas shot (DP)
(b),
GPT4 zero-shot (Multiplication)
1
0.9
0.72
0.6
0.6
0.88
0.63
0.45
0.30
0.31
1.20
0.98
m
0.1
0.3
GPT3.5 zero-shot
Accuracy
2.0
0.50
0.97
0.59
0.8
0.00
0.04
0.25
0.96
0.78
0:23
0.04
0.1
0.1
0
0
GPT3 pero-shot (DP)
0.91
0.54
0:09
0.01
0.3
0:23
0.05
0.04
0.04
-0.5
Average parallelism
Figure 2: (a) Zero-shot accuracy. Axes refer problem sizes (number of digits in multiplication, number of houses and attributes puzzle, and sequence length the DP task). Transformers' accuracy decreases near zero as task complexity increases, measuring task complexity by the problem size. (b) Average parallelism negatively correlates with accuracy.
To instantiate G((x). let FA {one-digit multiplication, sum, mod 10, carry over. concatenation): Source nodes S are digits of input numbers, leaf node o is the final output, and intermediate nodes are partial results generated during execution of the long-form multiplication algorithm (see Figure I.
Einstein's Puzzle Einstein's 's puzzle is a well-known logic puzzle often used as a benchmark for solving constraint satisfaction problems [6T]. involves list of houses with different attributes (e.g.. owner's s name, pets), and the goal is to determine which attributes belong to each house by combining set of pre-defined natural language clues or constraints. The solution to the puzzle is a matrix of size K' x M,, where K represents the number of houses and M the number of attributes. As K and M increase, synthesizing different partial solutions that satisfy individual constraints becomes highly compositionally complex. To construct the computation graph, we consider a greedy algorithm that iteratively eliminates possible solutions by filling at least one cell each time. deterministically fills the cell(s) that requires the minimum number of clues among all current unfilled cells. We refer to this as the elimination function. See for examples, data construction, and algorithm details.
To instantiate G GA(X). let FA = =eelmmination function]. The source nodes are the clues, all intermedi- ate nodes are partially-fille filled matrices, and the output node is fully-filled solution matrix.
Dynamic Programming Problem
Dynamic programming (DP) recursively breaks down complex problems into simpler sub-problems, problems solved using this technique are compositional. We analyze a classic relaxation of the NP-complete Maximum Weighted Independent Set problem [39] Given sequence of integers, find subsequence with the highest sum, such that no two numbers in the subsequence are adjacent in the original sequence. This relaxation may be solved in O(n) time using DP. See the solution $A.3 In the experiments, we restrict each integer to the [-5,5] range.
To instantiate G A(n)). 1ct FA {equals, and, not, indicator function, sum, max]. Source nodes are elements of the input list, and the output node is list that for each element indicates whether it should be selected. We select an (n) algorithm since G A(x) 's size is proportional to A's complexity.
3 Testing the Limits of Transformers: Empirical Evidence
Experimental Setup To understand the capabilities LLMs, we evaluate GPT3 (text-davinci-003) M.. ChatGPT (GPT-3.5-turbe (57] and GPT4 (gpt-4) (58) using zero- shot, few-shot, and finetuning techniques. enable the generation of computation graphs beyond the final answers, computation graphs (i.c., a lincarized representation of topological ordering of G Overall, we consider mestion-answer and question-scratchppe formats for few-shot and finetuning settings to gauge models' capabilities for learning with and without explicit reasoning. See details of additional models and experimental configurations in and examples of seratchpad in AA
the concept of scratchpads [56]. Scratchpads are verbalization of the
3.1 Testing the Limits of Transformers with Zero-shot, Few-shot and Finetuning
Limits of transformers in zero- and few-shot settings To investigate the inherent problem-solving capabilities of LLMs, we begin by analyzing models' zero-shot and few-shot performances our compositional tasks. shown in Figure task performances deteriorate significantly from near perfection to zero with increasing complexity when measured by either problem size (Figure 2 a))or

---

GPT3 ft w/o scratchpad (Multiplication)
domdomann valiationn
validation
stopping CPT3 finetured Scratchpad
GPT3 ft w/o scratchpad (DP)
finetured w/o Scratchpad
0.000:00
3 4 5
10
Accurscy
0.99
GPT3 ft w. scratchpad (DP)
0.97
0:57
0.07
0.24
4
5
10
.08 1088 158 200, 100, 305 Number steps
150
206
Problem size
Problem size
Number of steps
GPT3 finetuned exhaustively on task- specific data up to certain problem size. The blue region represents
Figure 3:
Figure 4: Results of training beyond the overfitting point for the multiplication task with the goal of ex- ploring whether OOD generalization capabilities (i.e.. grokking) arise.
in-distribution examples and the red region refers to OOD examples. The same trend is observed for the puzzle task (See B.2)
average parallelism (Figure bb)) The trend remains the same for few-shot prompting (see $B.2). These results indicate that pre-training is in fact not sufficient to teach models how to combine basic operations to solve compositional problems, especially as problems grow more complex.
Limits of transformers with question-answer training The limited performance of models may attributed to the lack of task task-specific data during pre-training. To fully bring out models' potentials in solving these tasks, we next exhaustively finetune GPT3 with question-answe multiplication and DP, we finetune models with all enumerations of questions up to the maximum problem sizæ within reasonable training budget, leaving out 10% for validation and 10% for testing. In puzzles, we train on a subset of all instances up to (K, M) S (4, 4) due to combinatorial explosion. We separately finetune GPT3 models ~ 1..8M multiplication pairs, ~ ~142K DP pairs, and ~41K puzzle pairs (see details in $ (.3).. Additionally, to examine problems of different complexity, we consider different training splits based on the depth and width of computation graphs.
pairs. In
Figure 3 and Figure Sai show high accuracy for examples with splits seen during training, i.e., in- domain. However, the performance sharply declines when evaluating unseen splits during training, i.e., out-of-domain (OOD). Similar trends hold in all tasks (see $ |B.3), suggesting that systematic problem-solving capabilities do not emerge via exhaustive training on task-specifi data.
Limits of transformers with explicit scratchpad training Next, we test whether we can explicitly teach models the required computational operations via scratchpads. To do so, finetune GPT3 with question-seratehpad pairs for all tasks. We consider the same distribution splits as before. The results, presented in Figure 5b] show that once again GPT3 achieves pear-perfect performance on in-distribution, but fails entirely in generalizing to OOD cases in particular, wider or deeper computation graphs. These results indicate that even when training directly with guidance on the computation steps, models still fail to learn component operations in a generalizable manner. This observation holds for all tasks (See details in B.4. Similarly, prompting transformers with question-scratchpad pairs enhances the performance compared to the zero-shot setting (refer to $B.5). However, this performance boost diminishes to zero as complexity increases. These findings suggest that the autoregressive characteristic of transformers, which forces them to tackle problems sequentially, presents a fundamental challenge that cannot be resolved by instructing the model to generate a step-by-ste solution. Instead, models depend on greedy process of producing the next word to make predictions without a rigorous global understanding of the task.
Limits of transformers with grokking We explore whether extended training beyond overfitting leads to improved generalization abilities, a phenomenon known as grokking [59] 53]. Due to budget constraints, we only experiment the multiplication task. Following [53], fine-tune GPT3 with question-answer pairs for 420K steps and separately finetune GPT3 with question-scren scratchharcaa pairs for 30K steps. Both models' training far exceeded the point at which in-domain accuracy plateaus Figure shows no improvement in generalization for OOD cases beyond the overfitting point, even
'We consider all ki-by-ke digit multiplications with 1 ki, A2 4 and kı k2 9; and all DP problems up to 5 elements. We selected sizes based on budget constraints for GPT3 finetuning, see BB. for cost details.
'The training duration for question- mnestoon-answer answer pairs is equivalent to 60 epochs and costs 50,000 USD. Training on question-scratchpaae scratchpad pairs conducted for 40 epochs and costs 40,000 USD.
5

---

Multippiiation w/o Scratchoad
Multiplization w/o Scretchpad
Multiplication w, Scratchpad
Multiplication w. Seratchpad
GPT3 finetuned live-nss
finetuned
GaTa five that
GPta five
oirss
0.8
zero shot
6.8
amra zers-inet
0.8
0.6
0.6.
0.4
04
0.0
4.0
0.0
Graph depth
Graph width
Graph depth
Graph width
(a) Results on question-answer pairs.
(b) Results on question--eratehpad pairs.
Figure 5: GPT3 finetuning and prompting accuracy different data splits. Although the in in-distribution performance almost perfect, GPT3 exhibits poor generalization with increasing graph depth and width. Refer to $..3 and $B.4 for results on the puzzle and DP tasks.
after extensive training periods. We hypothesize that the absence of grokking may be due to the level of difficulty of the task. We speculate that increased task difficulty significantly impedes learning a well-structured representation, which, according to [47]. aligns with achieving grokking. Even if grokking were to emerge through more prolonged training, such an approach would prove inefficient and unscalable. Future work is required to accurately explain when and how grokking occurs.
3.2 Breaking Down Successes and Failures of Transformers
3.2.1 Information Gain Explains Where Transformers Partially Excel
At times transformers predict partially correct answers even when the overall response is incorrect. We speculate that this may be due to particularities in the task distribution that allow for guessing partial answers without performing the full multi-step reasoning that the task requires.
Using relative information gain (defined in $2.3). D, we can predict surface patterns that a model is likely to learn and contrast them empirically. For multiplication, relative information gain shows that the first digit (two digits) of the output highly correlates with the first digit (two digits) of each input number (see SC.II. Hence, this spurious pattern is likely to be learned by a model. Similarly, the prediction of the last digit (or two digits) of the output is observed to solely rely on the last digit (or two digits) of each input number. This pattern holds true due the principles of modulo arithmetic, which ensures the validity of this relationship in all cases. Empirically, we verify that models indeed learn the patterns we predicted and other patterns as well (c.g., order of magnitude of the answer, number of trailing zeros for multiplication) in all the settings with and without scratchpad. See details for multiplication, plus dynamic programming task analysis in S
These experiments suggest that if an output element heavily relies on a single or a small set of input features, transformers are likely to recognize such correlation during training and directly map these input features to predict the output element in testing, without going through the rigorous multi-hop reasoning and giving a false illusion of performing compositional reasoning.
3.2.2 Transformers Reduce Multi-Step Compositional Reasoning into Linearized Subgraph Matching
We now explore whether models' correct predictions on unseen test data are due to learning the un- derlying algorithm or, instead, explainable by exposure to similar training examples. We hypothesize that, beyond simple memorization, transformers largely rely on pattern matching for solving these tasks. To test this, we calculate the average frequency with which partial computations needed to solve instance appear in the training data, for both correctly and wrongly predicted examples.
Given a model-generated computation graph G(x) we analyze how often the full computation of each node e E V is seen in training. We define v's full computation as the subgraph induced by all ancestors of including v, denoted FC ((m) (v). We say that FC (v) is seen during training if
FC& Atx) (v) = FCGAL,, (w) for some computation graph G G(())) in training, and for some w e V. We characterize complexity of a full computation subgraph by its depth, defined in $2.1
F that full computation subgraphs appear significantly more frequently the training data for correctly predicted test examples than for incorrectly predicted ones, for both the multi-

---

Fine-tuned GPT3 Multiplication
Five-dun GPT1 Malspication
Five-daat GPT4 GP144 UP
Fiveahet GPT4 Puole
mg dat
1014
Fine-tuned
Fine-uned GPT3 Muilipliaaiion
Frovaned GPTSS
Fiac-tazed GPT3 - Pazzlo
1000: Inc
10
20
full computation subgraph depth
rumber
number
bayermmmer
Correct Final Auswer + Incomeet Final Auswer
Fully Conrect
Local
Propogation Erav
Eror
Figure 6: Average frequency in which test examples' full computa- tions subgraph appear in the train- ing data w.r.t. the subgraph depth, grouped by final answer.
Figure 7: Ratio of nodes in each of the four correct/error categories for each layer in computation graph. Results shown for few-shot prompting and fine-tuning with scratchpad.
plication and DP task (both frequencies tend to zero for large depths since we ensured disjoint train/test split). This high correlation suggests that pattern matching- capabilities may be the cause behind correct model outputs. This type of learning could be largely effective when the compositional complexity of tasks low but it becomes less efficient when tasks increasingly complex. This may elucidate the observed performance gain in low-complexity and in-domain cases and the striking performance drop in OOD and highly complex cases.
not general reasoning
3.2.3 What Types of Errors do Transformers Make at Different Reasoning Depths?
For clearer understanding of where transformers fall short, we analyze the types of errors that transformers make for nodes different layers in the computation graph. For every input x, we compare the ground truth computation graph G (xx) with the (possibly incorrect) model-ggenertte
computation graph G A(x- We consider node as having correct value if and only if s(e) 3())
We consider a node be derived from correct computation if given that U {ui..... ... uy are the immediate predecessors of e in A(xx and that (p) = f. we have that f(u1,.... U2) = (v)). Note that the notion of correct computation is independent of G. and that node derived from correct computation may not have the correct value if an error occurred in some of its ancestors.
We classify each node v E V into one of four categories. Node e fully correct u and its ancestors have correct values and are derived from correct computations. If a node is not fully correct, its error can be of the following types: v has a local error its parent nodes have correct values but is derived from incorrect computation (i.e., one-hop reasoning error); has propagation error if v is derived from a correct computation but some of its parent nodes have incorrect values; v has a restoration error it has correct value but derived from an incorrect computation.
Figure shows results for few-shot GPT4 and fine-tuned GPT3 with scratchpad, with respect to graph layer number for each node. In all settings, the ratio of fully correct nodes is almost perfect but sharply decreases toward zero with increasing graph layers. Moreover, the ratio of propagation errors is usually higher than the ratio of local errors. Both phenomena suggest that models are able to correctly perform single-step reasoning, potentially due to memorizing such single-step operations during training, but fail plan and compose several of these steps for overall correct reasoning.
Both the DP and the puzzle tasks have high ratio of restoration errors, suggesting memorization since correct outputs are produced despite incorrect computations. There are signs of memorization even when restoration errors are near zero: 82.3% of the final correct answers for 4-digit by 2-digit multiplications (a setting unseen during training) had at least one error in the computation graph. but still produced correct answers. These patterns are possibly due to high frequency of (input, output) multiplication pairs in the pretraining data, in contrast to intermediate reasoning steps.
II' node does not appear in the ground truth graph G, we consider it have incorrect value.

---

4 Error Propagations: The Theoretical Limits
Experiments ($3) highlight the limitations of current transformers in handling complex, multi-step reasoning tasks. Concretely, we show that errors rapidly escalate as the problem size grows ($3.2.3) Here, we aim to provide theoretical insights into why autoregressive transformer LLMs can perform significantly worse in compositional tasks as the problem size increases, making explicit the different ways in which compounding stochastic errors affect final performance. We argue using stylized examples that transformers may be too limited to solve compositionally complex tasks. Formal statements and full proofs are provided in $D
Algorithms designed to solve compositional tasks typically involve multiple independent applications of a function and/or iterated applications of the same function. A transformer executing such an algorithm acts as an estimator of these functions. In this context, we examine the probability of such an estimator reaching the correct answer as the problem size increases. We first consider a scenario where a transformer estimates an algorithm requiring n independent applications of function:
Proposition 4.1 (informal). Let Jn involve the combination hn of independent applications of a func- tion g. Let f. g. hn be their estimators. Assume that hn is a perfect estimator of hn and that h.p has low collision, with Cn being upper bound of hn, 's collision rate (cn, < c Vn, with & 1). If P( + () c > where g's errors are independent, then P(fn *(fx fu) > 1 Cn -(1 -1--)) -)) (1
Cn). This implies
that P(fn + Sm) decreases exponentially as n. increases, with lim inf ( & fm) 2 1 - c. Moreover, n-++00
if Cn S 3,8 for some a E 1),8 > 0, P( + fn) tends exponentially to 1 as increases.
Prop 4.1 proof ($D.I) shows the rate of convergence is exponential, thus concluding that transform- ers will rapidly fail with increasing Let's now analyze the iterated application function scenario.
Proposition 4.2 (informal). Let fx(x)=g" (x) involve the repeated application of g. Assume that the probability of recovering from a mistake due to the randomness of applying the estimator on
an incorrect input has probability at most e. If [g # 9) = > 0, then P(Jn + [n) decreases exponentially with n. Precisely, Pf x Fr) 2 1- (1 -E c)---cc-----0-0-- - c/ (c + e)), implying
lif P(fn # Fn) 2 c)
n=+x
The argument is as follows. Let sn := Pfnn = Fr). where $1 = 1 c by definition. Derive 8n < (1- c)- Sn-1 + using law of total probability. Then, prove by induction non-recursive upper bound for sn with limit o+e when n + +00. See formal statement and derivation in $D2
Prop. 4.2 proof also shows an exponential rate of convergence. Note that if c < then lim inl Pf * Pa)) 2 1. It is reasonable to assume e < when g has low collision, since e a-+
represents the probability of the estimator F(y) arriving at the correct output g(x)) by chance when given the wrong input y # ær More details in D.3
Moreover, repeated applications of a function often imply unbounded errors: if g(x) can be expressed as affine transformation Fc, then it may be viewed first-order vector autoregression, which are known to be unstable when |X| 2 1 for at least one eigenvalue of F [31 Prop. 10.1]. While we make these arguments with affine maps. similar behaviors, possibly even more acute, could occur with nonlinear maps 25 but their study is beyond the scope of this paper.
In Prop. 4.2 current form, we implicitly assume that there is single valid reasoning for each input since g is a function. We can potentially generalize this assumption with a state-transition framing, where the probability of transitioning from a valid state to an invalid one is and the probability of recovering from an invalid state is at most e. See formal statement in D.2
All tasks evaluated in the present work can be seen as instances of the results just proven. Prop. 4. directly applies to multiplication, since m-by-n digit multiplication can be seen as independent instances of m- digit multiplication (see Cor. D.I. Prop. 4.2 directly applies to the recursive function of the dynamic programming task, as well as to m-by-1 digit multiplication, and to the puzzle through its elimination function (details in D.3 They are also all low collision settings.
Note that Prop 4.1 and 4.2 apply any nigh-performant estimator of reasoning tasks. We focus on out-of-the-box transformers to align with the scope of our experiments and with the goal of framing empirical results. In $5) we discuss how these propositions may inform future research directions.
8

---

5 Discussion
Collapsed Compositionality and Robustness Implications Transformers today demonstrate undeniably powerful empirical results. Yct, our study suggests that they may have fundamental weaknesses in certain intellectual tasks that require true multi-step compositional operations such as multiplications and logic puzzles. Our careful study based on the computation graph and analyses demonstrates that transformers can often solve multi-step compositional problems by collapsing the depth of the compositional operations via analogical pattern matching. More broadly, our findings suggest that the strong performance of transformers should be taken with a certain grain of salt: Despite initially appearing challenging, certain tasks may not possess the inherent compositionality they seem have. This is due to the fact that desired solutions could be readily derived from input-output sequences present in the training data, allowing for shortcut pattern matching to produce acceptable solutions. However, such an approach can ultimately result in poor generalization as shown in our study. For example, fine-tuning GPT3 on our tasks both with and without explicit reasoning graphs shows that models' learning fails to generalize beyond levels of complexity seen in training.
Theoretical Findings and their Empirical Implications The proofs presented in $ show that, under reasonable assumptions, the probability of incorrect predictions converges exponentially to 1 for abstract compositional tasks. Importantly, these proofs apply to autoregressive LMs in general. Our insights indicate that the current configuration of transformers, with their reliance on greedy process for predicting the next word, constrains their error recovery capability and impedes the development of a comprehensive global understanding of the task. Building on these findings, we suggest several empirical strategies for harnessing the potential of transformers. Firstly, transformers may be employed in ways that require chaining only few compositional steps to reach a solution rather than lengthy reasoning steps (e.g.. (35)). Secondly, transformers may be best suited for compositional tasks where evaluation metrics can afford some leniency; for example, finding approximate solutions that do not require executing the whole graph, such as identifying the most significant digit in multiplication. Finally, we suggest augmenting transformers with planning modules as well as using refinement methods, that can iteratively improve their generations
Call for Broad Participation to Investigate Limitations Identification of limitations is an im- portant step towards achieving greater robustness. Our study suggests fundamental limitations that impede transformers from fully mastering certain compositional operations. However, we acknowl- edge that due our compute budget constraints well as limited access to the largest language models such as GPT4, we are unable to push the empirical limits of transformers even further in terms of training data size and number of epochs. We invite the broader research community, particularly those with more extensive resources at their disposal, to investigate these possibilities further.
Related Work
Reasoning abilities in transformer LLMs Recently, transformers [1] 58 57 16
63
73 74
have demonstrated impressive reasoning abilities across wide range of tasks, even outperforming
humans in certain cases 779, 28 13 85 This success has been largely attributed to the scaling effect, where larger models and training datasets result in improved performance [38 33 []. However, these models have also been shown to struggle across multiple domains (32]. including algorithmic reason- ing 778), commonsense reasoning (62] 40). theory of mind (65) planning (76). logical reasoning (70),
and ethical reasoning [36]. These difficulties have motivated us to take a step back and thoroughly examine both the successes and failures of transformers from empirical and theoretical perspectives on compositional reasoning tasks.
Challenges of transformers in compositional tasks Transformers perform fairly well in single- step reasoning tasks (70). but face challenges when it comes effectively combining multiple steps to solve compositionally complex problems 84 [55] 66 81] Recent research has focused on overcoming these limitations through various approaches. First, fine-tuning transformers to directly generate the final answer while keeping the reasoning implicit [8] Second, encouraging transformers to generate reasoning steps explicitly within a single generation
[55] 80 42). For example, Nye et al.
(55) and Zhou et al. [86] used scratchpads to teach transformers how to perform algorithmic reasoning tasks such as addition by splitting the task into intermediate steps 80 Further, leveraging LLMSs
to generate each reasoning step iteratively via selection and inference mechanism 220 19 72).

---

Lastly, choosing training split that maximizes the number of observed patterns between the train and test data [TO], or diversifying in- in-rompt examples to cover the maximum of patterss [4], ultimately enhancing generalization. The primary focus of these studies is to enhance model performance on compositional problems without striving for complete mastery. contrast, our work explores the fundamental limits of vanilla transformers in achieving full mastery, striving for 100% performance in both in-domain and OOD settings. Our findings show that reaching full mastery is inherently challenging, providing insights into the complexities involved.
Challenges of transformers in generalization Extensive research has been done to investigate the 8
generalization capabilitiess of transformers [3 5454
26
64
46
This encompasses various facets of
generalization, including easy-to-hard generalization 67 length generalization [2 60 54
g
and generalization on symbolic mathematical integration 8 Schwarzschild et al. [67] and Bansal et
al. 4 employ weight-tied neural networks to generalize from easy to hard examples. Liu al., 45 found that shallow transformers learn shorteuts during training, leading to poor OOD generalization. Razeghi et al. (64] revealed positive correlation between the frequency of training terms and their test performance. Building upon this line of inquiry, we present a more rigorous examination of sub-graph matching between training and test instances for complex compositional tasks where we demonstrate how pattern matching can hinder generalization. We complement our empirical results with theoretical insights on transformers' limits.
Grokking The phenomena of models' gaining generalization capabilities when training signifi- cantly beyond overfitting, known as grokking was recently introduced in [59]. Subsequent works focus on characterizing when and why grokking arises: 47 show that perfect generalization in an arithmetic addition task happens when there is sufficient data to determine the appropriate structured representation, later extended to sparse parity in [52] where sparse subnetwork of neurons is shown responsible for generalization behavior. Recently, [77 propose that grokking occurs when task admits a generalizing and memorizing solution, and the former is slower to learn. In this present work, our aim is not to explain grokking but rather to observe its emergence. We do not observe grokking arising in the context of multiplication, and we leave it to future work to explore whether this may be due to task difficulty hindering the learning of well-structured representations.
Transformers' theoretical expressiveness Lin et al. [43 study autoregressive models' limitations from computational complexity theory perspective. Transformer-specific work has focused on quantifying the class of problems that (not necessarily autoregressive) transformers can express assuming perfect parameters [51 50 49 inter alia]. All tasks analyzed in our work belong to a class expressible by transformers, suggesting that known upper bound might not be tight. Importantly, Hahn [30) shows that transformers cannot robustly model noncounter-Fe frre regular languages even when allowing infinite precision. In contrast, our focus is on error accumulation, which enables to investigate if reasoning tasks theoretically solvable by transformers are likely to be solved by them.
Additional literature and societal impact discussion can be found in
Conclusions
On a broader scope, as transformers continue to gain widespread deployment with significant real- world impacts, it is ever more urgent to understand their successes and failures. Our study critically investigates transformers' limitations and emphasizes the need to develop models capable of robust generalization and systematic problem-solving. By examining the compositional capabilities of these models, we aspire to work towards more reliable Al systems that excel not only in tasks where abundant training examples are sufficient, but also in cases requiring precise compositional reasoning.
8 Limitations
We focus on analyzing compositional reasoning capabilities through the lens of computation graphs. Although they are a useful way to systematically represent rigorous reasoning processes, it is important to note that for the scratchpad approach, we are limited to only establishing a correlation between the model generation and its preceding context, as we cannot inspect the exact tokens model attends to when making the prediction. This limitation arises from our lack of access to the activations of the studied models. Furthermore, we posit that alternative approaches to linearizing reasoning processes may yield different performances and provide opportunities for further exploration.
10

---

Acknowledgements
We thank members of the Mosaic team at A12 for valuable feedback on this project, as well as Agustín Santiago Gutiérrez and Kawin Ethayarajh for valuable discussions. This research was supported by the NSF 34012, DARPA MCS program through NIWC Pacific (N66001-19-2-4051), and the Allen Institute for AI.

---

References
[1] Armen Aghajanyan, Lili Yu, Alexis Conneau, Wei-Ning Hsu, Karen Hambardzumyan, Susan Zhang, Stephen Roller, Naman Goyal, Omer Levy, and Luke Zettlemoyer. Scaling laws for generative mixed-modal language models. CoRR, 0ttp/23011.037222 2023.
[2] Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari. Ethan Dyer, and Behnam Neyshabur. Exploring length general- ization in large language models. In S. Koyejo, S. Mohamed, A. Agarwal. D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 38546-38556. Curran Associates, Inc., 2022.
[3] Cem Anil, Yuhuai Wu, Anders Johan Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Venkatesh Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. In Advances in Neural Information Processing Systems, volume 35, pages 15446-88556. Curran Associates, Inc., 2022.
[4] Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. End-to-end algorithm synthesis with recurrent networks: Extrapolation without overthinking. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 20232-20242. Curran Associates, Inc.. 2022.
[5] Yoshua Bengio, Réjean Ducharme, and Pascal Vincent. A neural probabilistic language model.
In Advances Neural Information Processing Systems, volume 13. MIT Press, 2000.
[6] D. Bertsekas. Abstract Dynamic Programming: 3rd Edition. Athena scientific optimization and computation series. Athena Scientific., 2022.
[7] Gregor Betz, Christian Voigt, and Kyle Richardson. Critical thinking for language models. In Proceedings of the 14th International Conference Computational Semantics (IWCS), pages 03-75,20 2021.
[8] Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the practical ability of recurrent neural networks to recognize hierarchical languages. In Donia Scott, Núria Bel, and Chengqing Zong, editors, Proceedings of the 28th International Conference on Computational Linguistics, COL.- ING 2020, Barcelona, Spain (Online), December 8- 8-13, 2020, pages 1481-1494, International Committee on Computational Linguistics, 2020.
[9] Ning Bian, Xianpei Han, Le Sun, Hongyu Lin, Yaojie Lu, and Ben He. ChatGPT knowl- edgeable but inexperienced solver: An investigation of commonsense problem in large language models. CoRR, abs/2303. 2023.
[10] Ben Bogin, Shivanshu Gupta, and Jonathan Berant. Unobserved local structures make composi- tional generalization hard. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 2731-2747, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
[11] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel HierbertVVoss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are fhw-shot learners. In Advances in Neural Information Processing Systems, volume 33, pages 1877-1901, 2020.
[12] Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott M. Lundberg, Harsha Nori, Hamid Palangi, Marco Túlio Ribeiro, and Yi Zhang. Sparks of artificial general intelligence: Early experiments with GPT-4. CoRR, abs/2303. 127 2023.
12

---

[13] Mirelle Bueno, Carlos Gemmel, Jeffrey Dalton, Roberto de Alencar Lotufo, and Rodrigo Fras- setto Nogueira. Induced natural language rationales and interleaved markup tokens enable extrapolation in large language models. CoRR, abs/2208. 1445, 2022.
[14] David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. Proceedings of the 40th International Conference on Machine Learning, 202:5544- 5562, 2023.
[15] Jonathan H Choi, Kristin E Hickman, Amy Monahan, and Daniel Schwarez. ChatGPT goes to law school. Available SSRN, 2023.
[16] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung. Charles Sutton, Sehastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez. Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Mísra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thamumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Hellsterm,,,, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language modeling with pathways. CoRR, abs/2204.02311, 2022.
[17] Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph. Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghami, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Y. Zhao, Yanping Huang, Andrew M. Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoe V. Le, and Jason Wei. Scaling cdaructiionfinettnee language models. CoRR, abs/2210. 1416, 2022.
[18] Peter Clark, Oyvind Tafjord, and Kyle Richardson. Transformers as soft reasoners over language. In Proceedings of the Twenty-Ninth International Conference on International Joint Joint on Artificial Intelligence, pages 3882-3890, 2021.
Conferences
[19] Antonia Creswell and Murray Shanahan. Faithful reasoning using large language models. CORR, hls/2208.142711 2022.
[20] Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inference: Exploiting large language models for interpretable logical reasoning, In International Conference on Learning Representations, 2023.
[21] Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient smt solver. In Tools and Algorithmm for the Construction and Analysis of Systems: 14th International Conference, TACAS 2008, Held as Part of the Joinl European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29-April 6, 2008. Proceedings 14, pages 337-340. Springer, 2008.
[22] Stanislas Dehaene, Nicolas Molko, Laurent Cohen, and Anna Wilson. Arithmetic and the brain. Current opinion in neurobiology, 14(2):218 22,224,,, 2004.
[23] B. Delyon and A. Juditsky. On small perturbations of stable markov operators: Unbounded case. Theory of Probability & Its Applications, 4374) 1999.
[24] Persi Diaconis and David Freedman. Iterated random functions. SIAM review, 41(1):45-76.
1999.
[25] R. Douc, E. Moulines, and D. Stoffer. Nonlinear Time Series: Theory, Methods and Applications with R Examples. Chapman & Hall/CRC Texts in Statistical Science. Taylor & Francis, 2014.
[26] Yann Dubois, Gautier Dagan, Dieuwke Hupkes, and Elia Bruni. Location attention for extrapo- lation to longer sequences. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 403-413, 2020.
13

---

[27] Jonathan St BT Evans. Bias in human reasoning: Causes and consequences. Lawrence Erlbaum Associates, Inc, 1989.
[28] Hao Fu, Yao; Peng and Tushar Khot. How does gpt obtain its ability? tracing emergent abilities of language models to their sources. Yuo Fu's 'ss Notion, Dec 2022.
[29] Robert Geirhos, Jörn- Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. Shortcut learning in deep neural networks. Nature Machine Intelligence, 2(1 ((1)):655667) 2020.
[30] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020.
[31] James Douglas Hamilton. Time series analysis. Princeton university press, 1994.
[32] Chadi Helwe, Chloé Clavel, and Fabian M. Suchanek. Reasoning with transformer-based mod- els: Deep learning, but shallow reasoning. In Danqi Chen, Jonathan Berant, Andrew McCallum, and Sameer Singh, editors, 3rd Conference on Automated Knowledge Base Construction, AKBC 2021, Virtual, October 4-8, 2021, 2021.
[33] Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B. Brown, Prafulla Dhariwal, Scott Gray, Chris Hallacy, Benjamin Mann, Alec Radford, Aditya Ramesh, Nick Ryder, Daniel M. Ziegler, John Schulman, Dario Amodei, and Sam McCandlish. Scaling laws for autoregressive generative modeling. CoRR, abs/2010.14701, 2020.
[34] James Hiebert. Conceptual and procedural knowledge: The case of mathematics. Routledge, 2013.
[35] Albert Qiaochu Jiang, Sean Welleck, Jin Peng Zhou, Timothee Lacroix, Jiacheng Liu, Wenda Li, Mateja Jamnik, Guillaume Lample, and Yuhuai Wu. Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. In The Eleventh International Conference Learning Representations, 2023.
[36] Liwei Jiang, Jena D. Hwang, Chandra Bhagavatula, Ronan Le Bras, Maxwell Forbes, Jon Borchardt, Jenny Liang, Oren Etzioni, Maarten Sap, and Yejin Choi. Delphi: Towards machine ethics and norms. CoRR, abs/2110.07574 2021.
[37] Philip N Johnson-Laird, Sangeet S Khemlani, and Geoffrey P Goodwin. Logic, probability, and human reasoning. Trends in cognitive sciences, 19(4):201-214 2015.
[38] 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. CORR, abs/2001 108361, 2020.
[39] Jon Kleinberg and Eva Tardos. Algorithm Design. Medisenn-essey Longman Publishing Co., Inc., USA, 2005.
[40] Philipp E. Koralus and Vincent Wasi-nasca Humans in humans out: On GPT converging toward common sense in both success and failure. CoRR, ab$/2303.17276, 2023.
[41] Itay Levy, Ben Bogin, and Jonathan Berant. Diverse demonstrations improve in-context compositional generalization. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1401-1422, Toronto, Canada, July 2023. Association for Computational Linguistics.
[42] Zhengzhong Liang, Zeyu Zhang, Steven Bethard, and Mihai Surdeanu. Explainable verbal rea- soner plus (evr+): A natural language reasoning framework that supports diverse compositional reasoning. arXiv preprint arXiv:2305.0000 2023.
[43] Chu-Cheng Lin, Aaron Jaech, Xin Li, Matthew R. Gormley, and Jason Eisner. Limitations of autoregressive models and their alternatives. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pages 5 5177-5173, Online, June 2021. Association for Computational Linguistics.
14

---

[44] Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale generation: Learning to solve and explain algebraic word problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pages 158-167, 2017.
[45] Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans- formers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations, 2022.
[46] Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans- formers learn shortcuts to automata. In International Conference on Learning Representations, 2023.
[47] Ziming Liu, Ouail Kitoumi, Niklas S Nolte, Eric Michaud, Max Tegmark, and Mike Williams. Towards understanding grokking: An effective theory of representation learning. Advances in Neural Information Processing Systems, 35:34651-34663 2022.
[48] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. CoRR, abs/2303. 17651, 2023.
[49] William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint arXiv:2310.00992; 2023.
[50] William Merrill and Ashish Sabharwal. A logic for expressing log-precision transformers. Advances in Neural Information Processing Systems, 2023.
[51] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023.
[52] William Merrill, Nikolaos Tsilivis, and Aman Shukla. tale of two circuits: Grokking as competition of sparse and dense subnetworks. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2023.
[53] Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher Manning. Grokking of hicrarchical structure in vanilla transformers. In Proceedings of the 6lst Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 439-448, Toronto, Canada, July 2023. Association for Computational Linguistics.
[54] Benjamin Newman, John Hewitt, Percy Liang, and Christopher D Manning. The eos decision and length extrapolation. In Proceedings of the Third BlackboxNLLP Workshop on Analyzing and Interpreting Neural Networks for NLP, pages 276-291, 2020.
[55] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate computation with language models, 2021.
[56] Maxwell I. Nye. Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate computation with language models. CoRR, wttp/2112.00111 2021.
[57] OpenAl. ChatGPT: Optimizing language models for dialogue, 2022.
[58] OpenAl. GPT-4 technical report, 2023.
[59] Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Gen- cralization beyond overfitting on small algorithmic datasets. arXiv preprint arXiv:2201.02177, 2022.
[60] Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations, 2022.
15

---

[61] Patrick Prosser. Hybrid algorithms for the constraint satisfaction problem. Computational intelligence, 9(3):268- 2999, 1993.
[62] Chengwei Qin, Aston Zhang, Zhuosheng Zhang, Jiaao Chen, Michihiro Yasunaga, and Diyi Yang. Is ChatGPT a general-purpose natural language processing task solver? CoRR, abs/2302.06476, 2023.
[63] Jack W. Rae, Sebastian Borgeaud, Trevor Cai. Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John F. J. Mellor, Irina Higgins, Antonia Creswell, Nathan McAleese, Amy Wu, Erich Elsen, Siddhant M. Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, L. Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, -ean-Baptiste Lespiau, Maria Tsimpoukelli, N. K. Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Tobias Pohlen. Zhitao Gong, Daniel Toyama, Cyprien de Masson d' Autume, Yujia Li, Tayfun Terzi. Vladimir Mikulik, Igor Babuschkin. Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew G. Johnson, Blake Hechtman, Laura Weidinger, Iason Gabriel, William S. Isaac, Edward Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem W. Ayoub, Jeff Stanway, L. L. Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving. Scaling language models: Methods, analysis & insights from training gopher. ArXiv, abs/2 12. 1446, 2021.
[64] Yasaman Razeghi, Robert L Logan IV, Matt Gardner, and Sameer Singh. Impact of pretraining term frequencies on few-shot numerical reasoning. In Findings of the Association for Computa- tional Linguistics: EMNLP 2022, pages 840-854, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
[65] Maarten Sap, Ronan Le Bras, Daniel Fried, and Yejin Choi. Neural theory-of-mind? on the limits of social intelligence in large LMs. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 3762-3780, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
[66] Abulhair Saparov and He He. Language models greedy reasoners: A systematic formal analysis of chain-of-thought. In International Conference on Learning Representations, 2023.
[67] Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. In Advances in Neural Information Processing Systems, volume 34, pages 6695-6706. Curran Associates, Inc., 2021.
[68] Herbert A. Simon. The architecture of complexity. Proceedings of the American Philosophical Society, 106(6):467-482, 1962.
[69] Herbert A Simon and Allen Newell. Human problem solving: The state of the theory in 1970. American psychologist, 26(2):145, 1971.
[70] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, Agnieszka Kluska, Aitor Lewkowyez, Akshat Agarwal, Alethea Power, Alex Ray, Alex Warstadt, Alexan- der W. Kocurek, Ali Safaya, Ali Tazary, Alice Xiang, Alicia Parrish, Allen Nie, Aman Hussain, Amanda Askell, Amanda Dsouza, Ameet Rahane, Anantharaman S. Iyer, Anders Andreassen, Andrea Santilli, Andreas Stuhlmüller, Andrew M. Dai, Andrew La, Andrew K. Lampinen, Andy Angela Jiang, Angelica Chen, Anh Vuong, Animesh Gupta, Anna Gottardi, Antonio Norelli, Anu Venkatesh, Arash Gholamidavoodi. Arfa Tabassum, Arul Menezes, Arun Kirubara- jan, Asher Mullokandov, Ashish Sabharwal, Austin Herrick, Avia Efrat, Aykut Erdem, Ayla Karakas, and et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. CoRR, abs/2206.0461 2022.
[71] Keith Stenning and Michiel Van Lambalgen. Human reasoning and cognitive science. MIT Press, 2012.
16

---

[72] Oyvind Tafjord, Bhavana Dalvi, and Peter Clark. Proofwriter: Generating implications, proofs. and abductive statements over natural language. In Findings of the Association for Computa- lional Linguisties: ACI-IIICNLP 202/, pages 3621-3634, 2021.
[73] Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic. Galactica: A large language model for science. CoRR, 0t//2211.099085 2022.
[74] Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng-Tze Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du YaGuang Li, Hongrae Lee, Huaixiu Steven Zheng, Amin Ghafouri, Marcelo Menegali, Yanping Huang, Maxim Krikun, Dmitry Lepikhin, James Qin, Dehao Chen, Yuanzhong Xu, Zhifeng Chen, Adam Roberts, Maarten Bosma, Yanqi Zhou, Chung-Chine Ching Chang. Igor Krivokon, Will Rusch, Mare Pickett, Kathleen S. Meier-Hellstern, Meredith Ringel Morris, Tulsee Doshi, Renelito Delos Santos, Toju Duke, Johnny Soraker, Ben Zevenbergen, Vinodkumar Prabhakaran, Mark Diaz, Ben Hutchinson, Kristen Olson, Alejandra Molina, Erin Hoffman-John, Josh Lee, Lora Aroyo, Ravi Rajakumar, Alena Butryna, Matthew Lamm, Viktoriya Kuzmina, Joe Fenton, Aaron Cohen, Rachel Bernstein, Ray Kurzweil, Blaise Aguera-Arcas Claire Cui, Marian Croak, Ed H. Chi, and Quoc Le. Lamda: Language models for dialog applications. CoRR, abs/2201 (.82399 2022.
[75] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. LLaMA: Open and efficient foundation language models. CoRR, abs/2302. 13971, 1, 2023.
[76] Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large language models still can't 't plan (a benchmark for LLMs on planning and reasoning about change). In NeurIPS 2022 Foundation Models for Decision Making Workshop, 2022.
[77] Vikrant Varma, Rohin Shah, Zachary Kenton, János Kramár, and Ramana Kumar. Explaining grokking through circuit efficiency. arXiv preprint arXiv:2309.0233 2023.
[78] Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Patterns, 2(7):100273, 2021.
[79] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Perey Liang, Jeff Dean, and William Fedus. Emergent abilities of large language models. Transactions Machine Learning Research, 2022. Survey Certification.
[80] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoe V Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, pages 24824-24837. Curran Associates, Inc., 2022.
[81] Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi. NaturalProver: Grounded mathematical proof generation with language models. In Advances in Neural Information Processing Systems, volume 35, pages 4913-4927. Curran Associates, Inc., 2022.
[82] Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. In International Conference on Learning Representations, 2023.
[83] Sean Welleck, Peter West, Jize Cao, and Yejin Choi. Symbolic brittleness in sequence models: on systematic generalization in symbolic mathematics. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8629-8637. 2022.
[84] Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with LEGO: synthetic reasoning task. CoRR, 0440220000.401,,,, 2022.
[85] Haoyi Zheng and Huichun Zhan. ChatGPT in scientific writing: a cautionary tale. The American Journal of Medicine, 2023.
[86] Hattie Zhou, Azade Nova, Aaron Courville, Hugo Larochelle, Behnam Neyshabur, and Hanie Sedghi. Teaching algorithmic reasoning via in-context learning, 2023.
17

---

Appendices
Compositional Tasks
A.I Multiplication
19
A.2 Einstein's 's Puzzle
20
A.3
Dynamic Programming Problem
22
B Experimental Setups & Empirical Results
24
Models
24
B.2
Limits of Transformers Zero- and Few-shot ................................
24
B.3
Limits of Transformers with question-answer Training
24
B.4
Limits of Transformers with Explicit Scratchpad Training
................................
26
B.5
Limits of Transformers with Explicit Scratchpad Prompting
26
Surface Patterns
29
C.1
Relative Information Gain Predictions for Multiplication
29
Empirical Surface Pattern Analysis for Multiplication with GPT4, ChatGPT and GPT3
30
Relative Information Gain Predictions for Dynamic Programming Task
31
Empirical Surface Pattern Results for Dynamic Programming Task
33
Theoretical Results: Derivations
35
D.I Error accumulates with larger parallel applications of an estimated function (width)
35
D.2 Error accumulates with larger iterative applications of estimated function (depth)
36
D.3 Discussing in the context of Proposition 4.2
38
Additional Literature and Societal Impact
40
Additional L Literature
40
Societal Impact Discussion
40
18

---

A Compositional Tasks
A.1 Multiplication
Data Construction We exhaustively generate multiplication problems question-amm -nnseer pairs (e.g., Q: "What is times 32?" A: "128"). We focus on multiplications of two numbers ..............
(21, 22, and y = (1/1 ... .bk) where each number can have up to k digits, amounting to x 10(k-1) combinations per each number. We set k to 5 in our experiments. showcases an example prompt for performing few-shot learning without the inclusion of scratchpad, while Figure demonstrates an example prompt using scratchpad. Throughout our experimentation, we explored various versions of the scratchpad, ranging from verbose and detailed to more concise alternatives. Among these variations, the scratchpad version depicted in Figure Jultimately produced the most favorable outcomes. Listing T shows the Python code for solving the task.
To multiply tuo numbers, start by multiplying the rightmost digit of the multiplicand by each digit of the multiplier, writing down the products and carrying over any remainders. Repeat this process for each digit of the multiplicand, and then add up the partial products obtain the final result.
Questions:
what's s 22 times 2? Answer 44.
Figure Example prompt for the multiplication task used for the few-shot setting.
Question: What is 35 times 90?
Scratchpad: Let perform the miltiplication step by step:
Let's multiply 35 by the digit in the ones place of 90, which is 0.
1. Multiply by the digit in the place of which is This gives
0. Write down the result 0.
2. Multiply by the digit in the tens place of 35, which is 3. This gives 3 x
0. Write down the result 0.
3. The partial product for this step is A-0 which is the concatenation of the digits we found each step.
Now, let's multiply 35 by the digit in the tens place of 90, which is 9.
4. Multiply by the digit in the
place of which is This gives 45. Write down the result 5 and carry over the 4 the next step.
5. Multiply by the digit in the tens place of 35, which is 3. Add the carryover from the previous step to account for this. This gives (3 9) + 4 = 31. Write down the result 31.
6. The partial product for this step B-315 which is concatenation of digits we found in each step.
Now, let's sum the 2 partial products A and B, and take into account the position of each digit: Λ=0 (from miltiplication by 0) and B=315 (from multiplication by but shifted one place the left, so it becomes 3150). The final answer is x + 315 x 10 3150 3150.
Figure A sample scratchpad for the multiplication task.
def multiply (x, y):
summands - [0] * len(y)
for i in range (len 1, -1, -1)
19

---

digits = [0] * len (x)
carry =
for j in range (1en
1, -1, -1):
t - xx[]] y[i]
t +* carry
carry t // 10
t digits insert (0, carry)
digita
11
12
summands [i] = aum [digits[-k] * (10 ** (k 1)) for k in range (diggit)s) + 1))
(1,
14
product sum (summands [-i] (y) 1))
(i 1)) for i range (1, len
15
return product
Listing I: Example Python code for solving the multiplication task.
A.2 Einstein's Puzzle
Data Construction In our experiments, we initially establish set of properties, such as Color, PhoneModel, Pet, and so forth, along with their corresponding values expressed in natural language templates (e.g.. "The house has red color."). We then devise fundamental and straightforward set of clue types: 1) 'found_ne at', e.g.. "Alice lives in House 2", 'same mavee__hue', e.g., "The person who is a cat lover lives in the house that has has dog as pet lives to the left of the person who lives in a red house.". and 4) 'besides', e.g., "The person who has a dog as a pet and the person who has a red house live next to each other." In addition, also set up harder clue types such as 'not_at at', 'lefit of (not necessarily directly left of), hoo__hose_bbrrre
color.", 3) 'direct_left' e.g., "The person who
etc. which are only used in auxiliary experiments.
The solution to the puzzle is a matrix of size K x M, where K represents the number of houses and M the number of attributes. During the puzzle generation, the M properties are randomly selected from the candidate pool, followed by the random sampling of K values for each property. The sampled values are then randomly permuted and assigned within the table create the solution. important to note that we ensure one of the sampled properties is 'Name" to enhance the readability and comprehensibility of the puzzles. To construct the clues, we initially over-generate valid clues based on the solution and subsequently remove redundant clues at random until we obtain a set with
General Unique Rules
There are houses (numbereed on the left, 3 on the right). Each hos different penson in them. They have different churacteristies:
Each person unique peter, erie, amold
People have different favorito sports: soccer, sonnis, basketball
<UniqueValues>
Ground-Trutt Table
People different car models: ford, camry
Sports
Clues
1. The person who a Ford is the who loves teanis.
Basketball
Camry
Arnold the thind house.
3, The
Camuy is directly left the person who Ford. 4. Eric is the person who owns Camry.
who
2
Peter
Tennis
5. The person who loves basketball Frie.
3
Amold
Soccer
Tesla
6. The person who loves tennis and the person who loves soccer are next to each other.
Reasoning Path Generation
Outpet: Peesentng park function PrspusdiicaaaaCaaa
f
Name
Name
Sports
Namt
Spocts
Lefectiwn clesn walle Luteziunnl of
Cluc
Erie
Baskethall
Eric
Budkettaall
Cansy
(hacitueey for clis sn Cuosickcetiuns do mennelllees
Peter
Peter
Tznnis
Arsold
Amoöd
Socoer
Amaid
Soceer
Pack appen
retum Push
Figure 10: A sample of the puzzle task and the reasoning path to reach solution.
20

---

This is logic puzzle. There are 3 houses (numbered 1 the left, the right). Each has different person in them. They have different characteristics: Each person has a unique name: peter, eric, arnold
People have different favorite sports: soccer, tennis, basketball
People own different car models: tesla model 3, ford f150, toyota camry
1. The person who
Ford F-150 is the person who loves tennis.
2. Arnold is in the third house.
3. The person who owns a Toyota Camry is directly left of the person who owns Ford F-150.
4. Eric is the person who
Toyota Camry.
5. The person who loves basketball is Eric.
6. The person who loves tennis and the person who loves soccer are next to each other.
Let's think step by step. Please first briefly talk about your reasoning and show your final solution by filling the blanks in the below table.
$ House:
$ Name: --- $ Sports:
Car:
House:
Name:
Sports:
Car:
House:
Name:
Sports:
Car
Reasoning:
Step 1: First apply clue <Arnold is in the third house.> We know that The Name in house is arnold.
Step Then combine clues: <The person who loves tennis the person who loves soccer are next to each other.> <The person who loves basketball is Eric.> Unique Values Rules and the fixed table structure. We know that The Name in house 1 is eric. The FavoriteSport in house 1 is basketball. The Name in house 2 is peter.
Step Then apply clue <Eric the person who owns a Toyota Camry >> know that The CarModel in house is toyota camry.
Step 4: Then apply clue <The person who owns Toyota Camry is directly left of the person who house is ford f150. The CarModel
Ford F-150.> and Unique Values We know that The CarModel in house is tesla model Step 5: Then apply clue <The person who owns a Ford F-150 is the person who loves tennis.> > and Unique Values We know that The FavoriteSport in house 2 is tennis. The FavoriteSport in house is soccer. The puzzle is solved.
Final solution:
$ House: 1 $ Name: Eric $ Sports: Basketball
$ Car Camry
House: 2 $ Name: Peter $ Sports: Tennis
Car: Ford
House: 3 $ Name: Arnold Sports: Soccer
Car: Tesla
Figure 11: A sample scratchpad for the puzzle task.
unique solution, as previously sampled. This process ensures a coherent and engaging puzzle-solving experience. Refer Figure [or example.
Graph Construction Algorithm To solve the complex compositional reasoning process for a logical grid puzzle, the basic greedy principle of applying the minimum number of rules to solve any cell, i.c., if using only one rule solve any given cell, then apply this rule. This algorithm iterates through all clues in the clue set until one or set of clue combinations can solve any cell in the table. While it may not be the most efficient way to solve the puzzle, provides models with explicit scratchpad verbalization through an intuitive computation graph. Refer to Figure for the pseudo-code of the process, and Figure for a scratchpad example.
existing puzzle solvers (21) to generate the computation graph. It follows
21

---

A.3 Dynamic Programming Problem
A.3.1 Solution this problem
Let (ai..... an) be an input. Let dp; be the maximum sum of subsequence that does not include adjacent elements, when considering only the elements of the input from the i-th position onwards.
- Trivially, dpn - max((n On. 0) since we only want to choose a number if it is non-negative. Moreover,
dpn-1 max(an, an-1 0) since we cannot choose adjacent numbers.
For any given dp; with i Σ n 2, we can express it in terms of dpi+1 and dp.+2- Concretely, the maximum sum of subsequence starting position i may may not include the element in the i-th position, ag. the subsequence includes 0g then the maximum sum is a, + dp:+2, since using og blocks us from using the next element. If the subsequence does not include ag then its sum is dp.+1- Moreover, the answer may never be less than zero, because otherwise we would select the empty sequence In summary,
dp, max(dp:+1. a; dp;-2. 0)
We now have recursion with its base cases dpn. max(an, 0) and dpn-1 max(an, 1n-1, 0), and we can therefore compute values in O(z). It now only rests to reconstruct the lexicographically smallest subsequence that maximizes the desired sum, based solely the computed dp values.
Starting from dp1 and iterating sequentially through dpn-2. we choose an item if and only dp: = + dp++2 (that is, the maximum sum comes from choosing the current element) and we have chosen the previous element. This helps disambiguate cases where choosing or not choosing yields the same sum, but possibly only one of those will not incur in choosing adjacent numbers. Similarly, for positions i
and n we choose the element if dp, a, (that is, choosing the element yields the maximum sum) and we have not chosen the immediately previous element. See an example Python solution in
Given sequence of integers, find subsequence with the highest sum, such that no two numbers in the subsequence are adjacent in the original sequence.
Output list with "1" for chosen numbers and "2" for unchosen ones. If multiple
solutions exist, select the lexicographically smallest. input [3, 2, 1, 5, 2]
Figure 12: Example prompt for the DP task, used for zero-shot and few-shot settings. def maximum, sum ce sub.euuueeeeueeeeeeeeeeeeeee (arr):
len (arr)
dp = [o for in range (N))
dp 1] max (arr 1]. 0)
dp 2] (max (arr [N 11, arr 21), 0)
for i in range (N 3, -1, -1) dp [i] max (max (dp (i 11, arr[i] dp [i 2]), 0)
11
13
reconstruct the answer with fixed-sizz graph result []
13
can use__eex_iiten True
16
for i range 2): dp[i 2] and can_use_next_
17
if dp[1] arr arr [i]
18
result append (1) Lan_use_next_icoe
False
else:
WWe don't i need to explicitly check for this since dp.. 2 0. However, we include the condition to ease the scratchpad logic.
22

---

result append (2)
can_ _extt item True
25
24
1f dp [N 2]
arr [N 2] and can_use_next_
25
result... append (1)
can_use_next_iee neet_ False
elae:
28
result append
29
can
= True
30
if dp [N 1l arr (N 1] and can_use_next_itee
32
result (ppend(1)
33
else:
34
result. result.append(C (2)
return result
Listing Example Python code for solving the DP task. We chose this implementation because the computation graph has always the same topology for any given input length.
Question: Let 's solve input [3, 1, 2].
Scratchpad: dp [4] max (input [4], 0) max (2, 0) = 2
dp [3] max (input [3], input [4], 0) max (5, 2, 0)
dp [2] max (dp [3], input [2] + dp[4], 0) max
0)
dp [1] max (dp [2], input[1 [1] dp[3], 0) max (5, 2 5, 0)
dp[01 max (dp [1], input[O) [o] + dp[2], 0) max (7, 3 + 5, 0) =
Finally, reconstruct the lexicographically smallest subsequence that fulfills the task objective by selecting numbers as follous. We store result on list named "output".
Let can_use pt__use_next_itee item = True.
Since [0] input [0] [2[ (8 == + 5) and can_us we__uuuee___ttteeeeeeeee True,
store output [0] 1. We update can_use cise_next_iteen
False.
Since dp[1] != input [1] dp[3] (7 != 2 + 5) or
False, we
store output [1] 2. We update can_use, wus__eet__iieeeeeeeeeeeee_e____e itemm = True.
Since [2[ != input [2] dp[4] (5 != + 2) fan_use_next_ieee item == False,
store output [2] 2. We update can pat_uuse_eet_. use_next_item True.
Since dp
input[3] (5 == and
True, we store
output[[] 1. We update can_uss__exx__iee
False.
Since dp [4] != [4put[[] (2 != 2) or can_use_next__tte item == False, store output [4] 2.
Reconstructing all together, output- (1, 2, 2, 1, 2]
Figure 13: A sample scratchpad for the DP task used for fine-tuning with few-shot settings.
Data Construction We exhaustively generate data for this DP task. For question question-answer answer setting, we include a thorough explanation of the task before asking generate solution (see Figure T2). We use all lists up to elements as training, and we consider only lists where elements are in the range [-5, 5] (giving total of lists for an input list size rτ). For out-of-domain evaluation, we use lists of sizes 6 to 10 inclusive. Example scratchpads and zero-shot prompts are shown in Figure
13 and (2 [n respectively. The scratchpad generated automatically through templates. We considered five exemplars for the fhw-shot setup.
23

---

B Experimental Setups & Empirical Results
B.1 Models
For our experiments, we evaluate the performance of LLMs: GPT4 (gpt-4) 158 ChatGPT (GPT3. -- 5-turbo) [57, GPT3 (text-davinci-003. [TI FlanT5 [7 and LLaMa 75 The evalua- tions were conducted from January 2023 to May 2023 using the OpenAl API. We perform fine-tuning on GPT3 (text-ddvvnci-005 for the three tasks, observing faster convergence when training on question-scratchien pairs rather than question-answer pairs. For question-answer pairs fine-tuning, train separately the model for [14, 12, 4) epochs for multiplication, puzzle, and DP respectively, saving the best model based on the validation set. Regarding training on
pairs, train the model for 16, 8, 2) epochs for multiplication, puzzle, and DP. The batch size is set to approximately 0.2% of the number examples in the training set. Generally, we observe that larger batch sizes tend yield better results for larger datasets. For the learning rate multiplier, experiment with values ranging from 0.02 to 0.2 to determine the optimal setting for achieving the best results and chose 0.2. During inference, set nucleus sampling p to 0.7 and temperature 1. For each task, we evaluate the performance of each model on 500 test examples.
B.2 Limits Transformers Zero- and Few-shot Settings
Figure 13 Figure 17 and Figure 20 show the zero-shot performance of GPT4 ChatGPT, LLaMA and FlanT5 on the three tasks. Overall, there a notable decline performance as the task complexity increases (measured by graph parallelism for multiplication and DP, and propagation steps for puzzles as shown in Fig The few-shot performance with question-anse -anwwer pairs results in minimal improvement over the zero-shot setting depicted in Figure and Figure 20 for the multiplication and DP tasks. In contrast, the seo-shot setting did not lead to any improvement in the puzzle task.
(Multiplication)
GPT4 zero-shot (DP)
GPT4 zero-shot (Puzzle)
1.5
1.0
Accuracy
Accuracy
Accuracy
0.5
8
0.5
10
Graph parallelism
Graph parallelism
Propagation steps scale)
Figure 14: Graph parallelism vs accuracy.
The accuracy decreases as the complexity increases.
ChatGPT zero-shet
GPT3 zero-shot
LLaMA zero-shot (138)
FlanT5-XXL zero-shot (118)
0.6
0.96
0.5
0.99
0.85
0.55
0.97
0.41
0.09
0.32
0.19
0.17
0.15
0.D2
0.98
0.51
0.11
0.01
0.85
0.28
0.04
0.22
0
0.15
0
0
0.98
0.26
0.02
0.76
0.1
0.07
2
5
2
5
2
5
5
Figure 15: Zero-shot accuracy. Performance of ChatGPT, GPT3, LLaMA and FlanT5 on the multiplication task.
B.3 Limits Transformers with question-answer Training
Figure 18 and Figure 21 show the performance of GPT3 finetuned on question-anee ansserr pairs. The model was trained various splits, considering the problem size, depth, and width of the computation graph. Specifically, for the multiplication task, the model was fine-tumed on range of multiplication problems, spanning from 1-digit by I-digit multiplication to 4-digit by 2-digit nultiplication amount- ing to 1.8M pairs. As for the puzzle task, the model was fine-tuned on puzzles of sizes ranging from 2x2 to 4x4 resulting in a total of 142k pairs. Additionally, for the DP task, the model was fine-tuned on problems with sequence length of 5 resulting in 41K pairs In an additional setup, we divided

---

GPT4 few-shot
ChatGPT Tew-shot
GPT3 few-shot
LLaMA few-shot (138)
FlanT5-XXL few-shot (11B;
0.98
0.99
0.88
0.52
0.42
0.42
0.05
0.93
0.70
0.38
0.03
0:94
0.45
0.08
0.02
0.88
0.23
0.06
0
0:22
0
0:16
0.02
5
Figure 16: Few-shot accuracy with question-answer pairs. Performance GPT4, ChatGPT, GPT3, LLaMA and Flan'S on the multiplication task. ChatGiP zero-shot (Puzzle) GPT3 zero-shot (Puzzle)
LLaMa zero shot (Puzzle)
Flan T5 zero shot (Puzzle)
0.8
0.4
0.1
0.4
0.6
0.5
0.2
0.1
eN
0.44
0:25
09
0.08
0.41
0.22
0.02
0.02
0.5
0.1
0.02
0
0
0
0
0
0
0
0
0
60
0
6
0
Figure 17: Zero-shot accuracy. Performance of ChatGPT, GPT3, LLaMA and FlanT5 on the puzzle task. Fow-shot performance led to worse performance.
GPT3 ft w/o scratchpad (Puzzle)
Puzzle w/o Scratchpad
Puzzle w/o Scratchpad
0.95
0.89
0.85
0.65
GPT3 Fine-tuning
GPT3 Fine-tuning
GPT3 five-shat
1.0
five-shet
0.7
0.55
0.45
0.8
GPT3 Zero-shot
0.8
GPT3 Zero-shot
Accuracy
0.6
0.6
4
0.8
0.6
0.4
0.3
0
0.4
0.1
0.1
0
Indemmain cata
0.0
In-domals
6
Number of houses
Number of properties
Figure 18: GPT3 finetuned on the puzzle task using question-answer pairs. The training data consisted of puzzles of size 4x4, and the model was subsequently evaluated on larger puzzle sizes for OOD testing.
those datasets based on the depth and width of the computation graph for all the tasks and finetuned on different splits. The results indicate lack of generalization for out-of-domain (OOD) examples while showcasing near-perfect performance for in-domain examples. One hypothesis on why the model exhibit such a poor generaliztion tokenization. So we train GPT2-XL. from scratch on up to 4x4 (90M data points), we assign each digit to one token and each math symbol as well. However, the performance still low and GPT2-XL. fails answer correctly 3x3 test examples.
GPT3 finetuning cost We will discuss here the approximate cost of fine-tuning GPT3 for the multiplication task. When fine-tuning with question-answer pairs, each example typically consists of around 20 tokens, and 250 tokens for question-scratehpal pairs. The cost for utilizing the pext-davvnci--00 model amounts to $0.02 (USD) per 1,000 tokens. With this particular setup, the total number of training examples required for multiplication up to 5 digits by 5 digits reaches an astonishing figure of approximately 9.1 billion examples. Should we choose to fine-tune GPT3 for 4 epochs on question-answer pairs, the cost would amount $12 million and $700 million for inestion-scratchhe training. For a more comprehensive breakdown of the cost per problem size, please refer to Table [
25

---

Multiplication w/o Scratchpad
Multiplication w/o Scratchpad
GPT3 finetuned
GPT3 finetuned
five-shet
1.0
GPT3 five shot
0.8
GPT3 zero-shot
0.8
GPT3 zero-sho
Accuracy
0.6
Accuracy
0.6
0.4
0.0
0.0
in-domain data
10
15
20
10
15
20
Graph depth
Graph width
Figure 19: GPT3 finetuned on the multiplication task using question-answer pairs
GPT4 (Dynamic Programming)
ChatGPT (Dynamic Programming)
GPT3 (Dynamic Programming)
GPT4 zero-shot
0.6
ChatGPT zero-shot
0.5
GPT3 zero-shol
CPT4 five
0.5
ChatSPT five-shat
0.4
GPT3 sivt
Accuracy
0.6
0.4
0.3
0.3
0.4
0.2
0.2
0.2
0.1
0.1
0.0
0.0
2
8
10
2
6
10
2
6
10
Problem Size
Problem Size
Problem Size
Figure 20: Zero-shot and Few-shot accuracy using question-answer pairs. Performance of GPT4, ChatGPT, and GPT3 on the dynamic programming task. LLaMA and FSan'T5 results are near zero for problem sizes.
B.4 Limits of Transformers with Explicit Scratchpad Training
Figure 23 24 22 show the performance of GPT3 fine-
tuned on different splits of the tasks using question- scratchpad pairs. Specifically, for the multiplication task, the model was fine-tuned plication problems, spanning from I-digit by I-digit multiplication 3-digit by 2-digit multiplication.
GPTS finatured w. scratchpad
Multiplicetion w. Scratchpad
Gmra Finetuiing five-shst
range of multi-
0.92
0.0
Agcuracy
0.06
0.28
0
As for the puzzle task, the model was fine-tuned on puzzles of sizes ranging from 2x2 to 4x4. Addition- ally, for the DP task, the model was fine-tuned on
0
00
Indoens ASC
6
10
Outout lenoth
Figure 23: GPT3 finetuned exhaustively on task- specific data up to a certain problem size. In partic- ular, we train on examples multiplication (left) and examples that have up to digits in the output response (right). The blue region represents the in-distribution examples and the red region refers to OOD examples.
problems with a sequence length of 5. Furthermore, different data splits were considered, including varia- tions based on the number of hours, number of prop- erties, depth and width of the graph, and the number of digits in the multiplication output. On all tasks, we can see that the model fails to generalize to OOD data while achieving perfect accuracy on in-domain data, indicating that it cannot learn the underlying computational rules.
to 3-digit by 2-digit
B.5 Limits of Transformers with Explicit Scratchpad Prompting
Figure 25 shows the results. GPT-4 exhibits an increase in few-shot accuracy in most problem sizes when using
pairs of shot examples across the three tasks. While its performance surpasses that of zero-shot and few-shot with question-answer pairs, it tends to decline as the complexity of the tasks increases. The same applies for the rest of the models.
26

---

Dynamic Progremming w/o Scratchped
Dynamic Programming w/o Scratchped
Dynamic Programming w/o Scratchpad
GPT3 finetuned
finetuned
1.0
GPT3 five-shot
GPT3 five-shot
1.0
GPT3 five-shot
0.8
zero-shol
zcro
accuracy
0.6
0.6
0.6
0.4
0.2
0.2
0.2
in-oomali
20 Depth
Problem
Wilth
Figure 21: GPT3 finetuned on the dynamic programming task using question-answer pairs. We consider different data splits: problem size, depth, and width of the graph. Specifically, the model was trained with a problem size of 5, and the graph's depth and width were set to 18.
Dynemic Programming W. Scratchpad
Dynamic Pregramming W. Scretchoad
Dynemic Programming Scratchpad
GPT3 finetuned
GPT3 five shot
1.0
GPT3 five-shot
finetuned
1.0
GPT3 finetuned
five-shot
0.8
GPT3 zero-shot
GPT3 zero-shot
0.8
GPT3 zero shot
Accuracy
0.6
Accuracy
0.6
0.4
0.4
0.2
0.2
0.0
In-domatn
0.0
in-ummenn data
15
25
30
10
15
20
25
30
35
Problem
Depth
Width
Figure 22: GPT3 finetuned on the dynamic programming task using question-scratehpal pairs. We consider different data splits: problem size, depth, and width of the graph. Specifically, the model was trained with a problem size of 5, and the graph's hsp depth and width were set to 18.
GPT3 ft w. scratchpad (Puzzle)
Puzzle w. Scratchpad
Puzzle w. Scratchpad
2
1
1.0
Fine-tuning
1.0
fine-tuning
GPT3 five-shot
GPT3 five-shot
0.82
0.87
0.88
0.65
0.55
GPT3 Zero-shot
0.8
GPT3 Zero-shot
Accuracy
Accuracy
0.6
0.57
0.4
0.4
5
0.1
0.1
0
D
0.2
0.2
In-dimai OICA
In-d0T al data
2
4
5
4
6
8
Number of houses
Number of properties
Figure 24: GPT3 finetuned on the puzzle task using question-scratehaal pairs. The training data consisted of puzzles of size 4x4, and the model was subsequently evaluated on larger puzzle sizes for OOD testing.
27

---

GPT3 Cost
Problem size
examples
scratchpad
scratchpad
1xl
81
S0.12
$7.44
2x
810
$1.28
$74.4
2x
8100
$12.96
$744
3x1
8100
$12.96
$744
81000
$129.6
$7440
3x3
810000
$1296
$74,404
81000
$129.6
$7440
4x2
810000
$1296
$74,404
4x3
8100000
$12,960
$744,040
4x4
81000000
$129,600
$7,440,400
5X1
810000
$1296
$74.404
8100000
$12,960
$744,040
81000000
$129,600
$7,440,400
5x4
810000000
$1,296,000
$70,440,400
5x5
8100000000
$12,960,000
$700,440,400
Table 1: Finetuning cost of GPT3 model the multiplication data.
GPT4 prompting w. scratchpad (Multiplication)
GPT4 prompting scratchpad (Puzzle)
GPT4 prompting w. scratchpad (DP)
1
1
0.8
0.9
0.7
0.99
0.5
0.5
0.2
0.2
0.1
0.15..002
0.94
0.92
0.4
0.4
0.1
0.1
0.1
3
6
9
0.78
0.2
0.02
0.2
0
0
0.1
0.37
0.1
0.1
2
2
3
4
5
6
Figure 25: GPT4 few-shot accuracy with question cooustion-scren scratchpad pairs on the tasks. The performance improves for most problem sizes compared to zero-shot performance and few-shot using question- answer pairs but degrades to zero the complexity increases.
28

---

C Surface Patterns
C.1 Relative Information Gain Predictions for Multiplication
Relative Information Gain
Input variable
Output variable
2x2
3x3
4x4
5x5
Zn
Zzn
0.223
0.223
0.223
0.223
yn
22n
0.223
0.223
0.223
0.223
J1
21
0.198
0. 0.199
0.199
0.199
1/1
21
0.198
0.199
0.199
0.199
In Yn
Z2n
1,000
1.000
1.000
1.000
In-1 En
22n
0.223
0.223
0.223
0.223
In-1 Yn
Z2n
0.223
0.223
0.223
0.223
Nn Ya
22n
0.110
0.101
0.101
0.101
Yn -1 y/a
22n
0.032
0.036
0.036
0.036
In- Zn
22n-1
0.032
0.036
0.036
0.036
Tn-1 1 Yn-1
22n-1 1
0.018
0.025
0.025
0.025
21 8/1
22
0,099
0.088
0.088
0.088
22 y/2
22
0.025
0.016
0,016
0.016
1 3/1
21
0.788
0.792
0.793
0.793
y1 1/2
21
0.213
0.211
0.211
0.211
T2
21
0.213
0.211
0.211
0.211
Table Highest Relative Information Gain Elements and Pairs Elements, for multiplications
between æ (#1...., .x, and y (yi,-... Mn), with 2 < n < 5. We define 2 == y, which will always have size 2n (with possibly leading zero). 22n denotes the least-signiffcant digit of and 21 denotes the left-most digit. Only (input, output) pairs above 0.01 are shown. Note that since multiplication commutative, several pairs input variables (e.g. ag and bp) exhibit the same relative information gain.
29

---

C.2
Empirical Surface Pattern Analysis for Multiplication with GPT4, ChatGPT and GPT3
Accuracy Trailing
Accuracy last digit
Accuracy last two digits
0.99
0.98
0.98
0.72
0.99
0.98
0.99
0.98
0.98
0.68
0.58
0.63
2
3
5
Accuracy # digits
Accuracy first digit
Accuracy first two digits
2
3
0.99
0.99
0.99
0.99
0.99
0.99
0.98
2
1
2
3
5
Figure 26: GPT4 zero-shot accuracy in predicting partially correct responses. This evidences surface pattern learning, since the accuracy of full answer prediction is significantly lower-and often near zero (see Figure 2). Specifically, "accuracy trailing zeros' pertains to accurately predicting the number of zeros in the output number, which known be relatively easy predict based on arithmetic calculations.
Accuracy Trailing 0
Accuracy last digit
Accuracy last two digits
0.99
0.99
m
0.93
0.91
0.98
0.93
0.95
0.99
0.98
0.97
0.89
0.88
0.87
0.98
0.8.3
0.8
2
3
5
Accuracy # digits
Accuracy first digit
Accuracy first two digits
2
0.99
0.99
0.96
0.97
0.98
0.97
0.96
0.94
0.95
0.94
0.99
0.86
0.91
0.84
2
1
3
5
Figure 27: ChatGPT zero-shot accuracy in predicting partially correct responses. We observe the same trend for GPT3 predictions.
30

---

Accuracy Trailing 0
Accuracy last digit
Accuracy last two digits
0.99
3
0.99
0.99
m
0.97
0.89
0.69
0:99
0.97
0.99
0.98
0.98
1
0.9
0.98
0.86
un
0.99
0.63
Accuracy digits
Accuracy first digit
Accuracy first two digits
0.99
m
0.99
0.98
0.99
0.9
0.98
0.98
in
0.99
0.99
0.98
0.98
Figure 28: GPT4 five-shot accuracy in predicting partially correct responses. trend for ChatGPT, GPT3 few-shot predictions.
We observe the same
Accuracy Trailing
Accuracy last digit
Accuracy last two digits
0.98
0.99
0.76
0.8
0.65
0.8
0.98
0.93
0.96
0.94
0.1
2
1
2
3
5
Accuracy # digits
Accuracy first digit
Accuracy first two digits
0.99
0.5
0.12
0.54
0
0.86
0.97
0.64
0.32
0.69
0.1
0.01
0.02
0.84
0.62
0.16
0.12
2
1
3
5
Figure 29: GPT3 finetuned on question- pairs. Accuracy of predicting partially correct responses.
C.3 Relative Information Gain Predictions for Dynamic Programming Task
Let a, be the i-th element of the input sequence, and let o, be the i-th element of the output sequence. As shown T a, is a good predictor of o,, and this is especially true for aj and an-1, the first and last elements of the sequence. This matches the task intuition, since one would never pick an element a; < and decrease the final sum (one may pick a; = if it makes a lexicographically smaller output sequence).
a; weakly helps to predict its neighbors. The only case of this behavior with RelativelG>0.1 is at the start of the sequence, where the first element helps predict the value of the second. This again matches intuition, since a very high o1 indicates that with high probability 02 will not selected for the final subsequence.
31

---

Relative Information Gain for each problem size
Input variable
Output variable
3
5
7
9
10
01
02
0.15
0.13
0.14
0.14
0.14
0.14
0.14
0.14
0.14
01
01
0.64
0.71
0.69
0.69
0.69
0.69
0.69
0.69
0.69
02
02
0.53
0.42
0.45
0.44
0.45
0.44
0.44
0.45
0.44
03
03
0.64
0.49
0.53
0.52
0.52
0.52
0.52
0.52
04
0.60
0.46
0.50
0.49
0.49
0.49
0.49
05
0.62
0.47
0.51
0.50
0.50
0.50
06
06
0.61
0.47
0.51
0.49
0.50
0.61
0,47
0.51
0.50
0g
08
0.61
0.47
0.51
0.61
0.47
010
010
0.61
an-1
On-1
0.64
0.60
0.62
0.61
0.61
0.61
0.61
0.61
Qn-2
On-2
0.46
0.47
0.47
0.47
0.47
0.47
an-3
On-3
0.51
0.51
0.51
0.51
ap-1
On-1
0.49
0.50
Table Highest Relative Information Gain Elements, for DP problems of size 2 < n S 10.
We only show the (input, output) pairs where at least three problem sizes have RelativelG>O, and least one with RelativelG>O.1. On-1 refers to the last element of the sequence, regardless of its actual id in the sequence.
Similar behaviors, but with higher relative information gains overall, are observed when analyzing triples consecutive elements in the list. Table shows that o, is highly predicted by (aş-1 as as+ 1). Moreover, is highly predicted by both (a.-2, a;-1: a:) and (a,, a,+1, a1+2), with the former generally having higher scores than the latter. This again matches the task intuitions, since the value of the neighbors helps determine whether to select number for the subsequence; and asking for the lexicographically smallest sequence biases the output subsequence to care more about the previous numbers rather than the following ones. We believe that this last point is the cause of the weakly predictive power of (a;-3, Q;- 0;-1) to predict o,; whereas (a:+1 0242, a.43) is not shown, since all the relative information gain values were below 0.1.
32

---

Relative Information Gain for each problem size
Input variable
Output variable
3
5
7
9
10
an-3 an-2 On-1
0n-1
0.95
0.95
0.95
0.95
an-3 ap-2 On-1
On-2
0.87
0.87
0.87
0.87
4n-3 ap-2 On-1
On-3
0.64
0.64
0.64
0.64
Q1 02 03
01
1.00
0.96
0.97
0.97
0.97
0.97
0.97
0.97
01 (22 0g
02
1.00
0.91
0.92
0.91
0.92
0.91
0.92
0.91
02 0g 04
02
0.56
0.55
0.55
0.55
0.55
0.55
0.56
01 (2 03
03
1.00
0.66
0.73
0.71
0.72
0.72
0.72
0.72
04
03
0.86
0.77
0.78
0.78
0.78
0.78
0.78
03 04 05
03
0.67
0.66
0.66
0.66
0.66
0.66
04
0.94
0.64
0.7
0.68
0.69
0.69
0.69
0g 04 (1s
04
0.88
0.79
0.81
0.8
0.8
0.8
d6
0.63
0.62
0.62
0.62
0.62
0g 04 as
05
0.95
0.65
0.71
0.69
0.7
0.7
05 a6
05
0.87
0.78
0.79
0.79
0.79
05 06 a7
05
0.64
0.63
0.63
0.64
0.94
0.64
0.71
0.69
0.7
05 G6 07
06
0.87
0.78
0.8
0.8
07 d8
06
0.64
0.62
0.63
as 06 07
07
0.95
0.64
0.71
0.69
07 as
07
0.87
0.78
0.8
ag 07 ag
0g
0.95
0.64
0.71
a 02 03
04
0.12
0.1
0.11
0.11
0.11
0.11
0.11
02 03 04
05
0.1
0.09
0.1
0.09
0.1
0.1
a3
06
0.11
0.1
0.1
0.1
0.11
04 0g a6
07
0.11
0.09
0.1
0.11
Gg 07
0g
0.11
0.09
0.11
Table 4: Highest Relative Information Gain Contiguous Triples, for DP problems of size
3 S n S 10. We only show the (input, output) pairs where at least three problem sizes
have RelativeIG>O, and at least one with RelativelG>O.1. an-1 refers the last element of the sequence, regardless of its actual id in the sequence.
C.4 Empirical Surface Pattern Results for Dynamic Programming Task
We observe that all analyzed models match the Relative Information Gain prediction that or (whether the first element goes into the output sequence or not) should be the easiest value to predict (see Figures 30 31 and 32). However, since GPT3 often predicts shorter output sequences than the required size, the analysis of the predictive power of on-1 is only done for GPT4 In GPT4, we observe that 0 is among the casiest values to predict as expected by Relative Information Gain.
0_(m1) c_(n2) o_(m+) o.(())
Cutpor Model Model the conditin
1.00
1.00
Azumay
0.90
0.90
0.90
0.00
0.80
0.70
0.70
0.80
Urpui lenght)
leight
Diruet lenght)
Figure 30: GPT4 five-shot with scratchpad accuracy predicting output elements o, in the DP task. All o; are predicted with high accuracy with and 0,-1 being consistently among the highest. These observations go line with the Relative Information Gain prediction.
33

---

0
Output Model chooses negatives
Model respects the non-adjacent condition
1.00
Accuracj
0.75
Accuracy
0.50
0.45
0.25
0.35
0.00
7
10
8
Problem size (input list length)
Problemn size (input list longth)
Figure 31: GPT3 few-shot without seratchpad accuracy in predicting output elements o, in the DP task. As predicted by Relative Information Gain, the model predicts correctly with the highest probability. However, because GPT3 often does not produce the correct output size, it hinders us from analyzing On-1-
2.2
0_4 o_5
Output correct
chooses negalives Model respects the non-adjacent condition
1.0
1.00
Accuracy
0.9
0.75
Accuracy
0.50
0.25
0.7
0.00
9
Problem (input length)
(input length)
Figure 32: GPT3 fine-tuned without scratchpad accuracy in predicting output elements o, in the DP task. As predicted by Relative Information Gain, the model predicts or correctly with the highest probability. However, because GPT3 often does not produce the correct output size, it hinders us from analyzing 0p-1.
34

---

D Theoretical Results: Derivations
D.1 Error accumulates with larger parallel applications of an estimated function (width)
Here we provide formal statements and derivations Propositions and shown in the main paper. The mathematical framework used is a simplified representation of how multi-step reasoning works, showing two quintessential reasoning types: independent applications of the same step, or consecutive applications of the same step. We take an error estimation and accumulation perspective, since transformers are still being investigated from a theoretical standpoint.
Proposition D.I. Let fa(x) = ln x, 1x, 2)), I(x, n.)). Let Nnn I, Sn be estimators of h 9: fn. respectively. Assume P(h,, = h.,) = 1 and P(,, = hY) X & Y) < Cno where On < c.for some constant < 1 (i.e. hi perfectly estimates hn and hy is almost injective). If P(g + g) = <>>>0 and errors in 9 are independent, liminf (fa * fn) 11)21. n
Moreover, cn S Ba for some some E 10, and B > 0. then lim P(fn + fn)=1. =1 n-++0
t), and let X (X .,,) and Y = (Y,,...,Y, Y,).. We will compute some auxiliary probabilities, and then upper bound P(f = f). finally compute its limit.
Proof. For ease of writing. let X, = a and Y, (X,
P(X = Y) P(X, Y1,X, Y2, ....... X,, Y,) P(X, = -Y) -P(22 = 122 P(X, = YY,) = P -)" -0-=--"--0 = c))" (2)
Since by hypothesis we know P(), = =hn, (Y)) = 1, we have that:
(X) - (8) x XY) = P( (X) (.. = - (x) X +X)
P(hi (X) = -Y, = (Y) x x
$ (P(nn(X) = (Y) X XY
(3)
We will now estimate P(fn- = Fn) using the law of total probability w.r.t. the event X = YY
P(f= = f.) = (X) = (Y))
= (X) = (Y) X = Y) P(X = P = (Y) x Y): P(X *Y)
= (X) = (x)))) P(X = Y) + P (h,, (X) (Y) X Y) (1 - P
=1. (1 - c)" PPhh,. (x) (Y) x Y) (1 - (1-(1=))))
(using 2 and hypothesis)
< (1 c)" c 111-(11) (1) (using
G. + (1 e)" (w-c.)
To conclude our proof, will compute lower bound for lim inf P(fn # f.). Note that since Gn < e for all n, we know that (P[,, = (n)) < c (1 - (1= 10"......) (1 c). Then, P(ʃn * f.) >
1 - -c- (1 - e)n (1 c). Since c E [0, 1), lim c - (1 - -))" (1 = 1 c. Thus,
n
lim inf inf P(fa + Fw)) 2 lim 1- - c- (1 c) (1 c) = 1-
t=*
++000
which concludes our proof.
Note:
In the case where en S Ba", we can derive an even stronger conclusion. In this case, we can
prove that lim P(fn = fn) = 1. Recall that P(fn = f.)) < a,3" + (1 c)" (1 - a,3"). Note
20
that since 1 c [0. 1) and (0, 1), trivially lim 3a + (1 11= (1 -3a") 0. n
0 < inf [f = F..) < sum P(fn = F..) < sim 3a" + (1 - -)" (1 - =Ba") = 0
n
to
35

---

Then, +om P(fn fa) = and we conclude lima-++0e P(fn + fr) = 1, assuming that On I $a" " for some adequate a.
Corollary D.1. Assume that model M solves shifted addition perfectly. but it incorrectly solves at least one mn digit by I digit multiplication for some fixed m. Then, the probability that M will solve any digit by n digit multiplication using the long-form multiplication algorithm tends to O when tends to infinity.
Proof. Let g = d o define the base-10 multiplication between m-digit numbers (21 ... Fmm and - N x denotes the selection the numbers to multiply and d N x 210 + N denotes the actual multiplication:
1 ddigtt numbers (Im+g), where & : -21
9 = dos
d(r x: y
s([21.... Im, Im+1. T mm))l:5) == (I1 + D2 ++ .... + 2m 2m+ts)
where
+ Im denotes concatenating digits 2;
Let hn. : N - N describe the shifted addition used the end long-form multiplication to combine m-digit by 1-digit multiplications, and let fn g N describe the long-form multiplication of m-digit by n-digit numbers:
hn II,,,,,,,a In) Σ x,10n-3
[n = 1n( (g(x, 1),g(xx 2)), ...))...................... .xx,.)))
By hypothesis, Pg # = and P(h,, = kn,) = 1, where 9 and hn denote estimators using model M. It can be shown that P(h, (X) hn (Y) x Y) < 3a for 0.1 and B 10" Using Lemma D.1
lim P(nn # Fn) = which concludes our proof.
n
Note that Lemma D proofs gives us empirical bounds once c and a are approximated. Also note that definition of in the proof of Corollary Diihhiggl two possible sources of error: errors in the selection of the numbers to multiply and errors in the actual m-digit by 1-digit multiplication d.
D.2 Error accumulates with larger iterative applications of an estimated function (depth)
Proposition D.2. Let fx(x) = (x). Assume P(g(X) ī(Y) Y) S e (i.e. recovering from mistake due to the randomness of applying the estimator on an incorrect input has probability at most c). If P(g # 9)
0 with + then lim inf P( fa) 1 - c/(c e).
Proof. We first derive recursive upper bound using the law of total probability, and then prove non-recursive upper bound by induction.
8, = P(r= Л.)) P(g(g"~1(Z) = -0-"~'"--- (Z))) (2)))
P(((X) -(YY) where X (n
P()(X) 3(Y) X x= P(X P - x(Y) ( -
P()(X) = -(X))
P(X =
X
= P(g(X) = ((X))
88-1
x (1-8m-1
x
I (1 c)
+ e. ...11 (1- (1-$
I (1 - c) 8n-1 +c
We know 81 (1 <) since 81 P(1i A1) = =Pp(g g g) Let - for ease of writing. Then, we have
8n S 8n-1 +
It can be easily shown by induction that s. < b- E) + 2n-2 2
36

---

The base case = 2 is true since we know 82 S b. + c, and 81 +1+c +c= +c=
6² b2-1(1 c) + >.=0 b', thus showing $2 S 62- Ei= 2-2 00 6²
The inductive step yields directly using Equation I b. 8h-11-1 +c
< b. (1- (1-16 c Σ b'
+cs
+ Σ b 6" ( +
We can rewrite the geometric series
Σ === b' in its closed form 1-b=-1 and recalling b : c-c 1-b
bー-1
b"- t) + 1 6n
8n 2 6 (1 <) + 1
c+6
6 (1 <) + -b-1
C+E
c+e
bm-1 - (
c+c c+é
Recalling that 8n P(fn = fn), we compute the limit inferior of P(Jn & [n)
8n 2
1 6" (1-c- atc)
inf Pff # Fn) n-+000
lim 1- 1-60-1(1 -E _ n+000
c
= c
ctt
c+
C+
that concludes our proof.
We can generalize the proof in Lemma(42 to tasks where there are potentially many valid reasoning chains with the following alternative dtate-transitinn framing.
Lemma D.2. Let S denote the set of all possible states language model can generate, and let S + {0. defines if state is valid (0 = invalid). Let g + II(S) ) be a state-transition function representing language model's 's probability distribution of generating each possible next state when attempting to perform a single reasoning step. Assume (()(((X)) = 2(X) = 0) S c and 0 with < 1. Then, lim inf (2) 0) = c/ c).
P(2(O(X)) 2(X) = 1)
If for task T we know that all valid reasoning chains arrive correct result have least length (i.e., the equivalent of defining fn = g" in Lemma D.I) then the probability of solving task T correctly tends at most c/(c+
Corollary D.3. The recarsions for dynamic programming lasks, the m-by-1 digit multiplication, and the puzzle's 's elimination function are all lasks where there is a fixed reasoning step being repeatedly applied. Therefore, we directly apply Proposition 4.2 to these tasks.
Proof. Let's analyze the three tasks separately below.
m-by-1 digit multiplication may be viewed as (x) Let x = (Z1...., Zm)) be the m-digit number that multiply by the 1-digit number y (0 S y 10). Let (Z1,..., Zm++1 denote
2 = x y, which guaranteed to have exactly m + digits (with possibly leading zeros). We define as:
far,..., Fmn U, 1, = (2). (Z1...., 2/ Ti Ken D. 1,)))
where 24 = (z; y c) mod 10 and d' == [(:; y c)/10j. Note that of = 21+1 since f is performing one step of the long-form multiplication algorithm.
Let the initial input be x = (.i,.....e Tm, y, m, 0). Then, can be easily shown that (x(x)
(=2...., 2m+1, 2m 0, c). Since is the left-most carry, it is the leading digit of 2, i.e. c = 21 (possibly zero). Thus, the value of can be directly extracted from (x(x) (22.... 2,..1, V, 21).
37

---

In the DP task, dp's computation may be viewed as (z) for list of size See A.3.1 for details on the solution to this problem. We will use identical notation. Let a.,.... am be an input list. Let x (a1..... 0m--2 - "m= m 2), where dn == max 0) and dn=1- == max(An-11 am, 0). Intuitively, this means that we have applied the first two steps of the dp computation, and stored the results in n and a'm- Let f be function representing the recursive computation of dp,;
f(e1...... az 04..441.....
dm = (aI..... a-1, d....... a'm 1)
where de := m 0 02+2.0).
Note that since 4141 stores the value of dpi+1 and 0/42 stores the value of dp;-2, it can be easily shown that (x-=(xx (a'..... o'm 0) (dpı. dpm; Therefore, fm-2 computes all recursive values of dp, when given the base cases.
In the DP task, the reconstruction of the desired subsequence given already computed dp values may be viewed as fm(x) (x) for an input list of size m. This case similar to the previous one. Let r (fi..... Tmm) be the result, where = 1 if a, was selected for the desired subsequence, and ri = 2 otherwise. Let x == (dpl...., dpm O, 0,0,11,... am 1, 1). Let f be defined as follows:
fddp..... dpm, 0,0, di................... d/-1 a.....y am, u. (dp
(dp....... .... . 0, 0, ai. ................................ d, a.41, Oml 1, u')
where df : 2 11 lidp; a; dp and 1} and = l'dpi a; + dp and 1}. Intuitively, ae stores whether the i-th element of the list should be selected for the final subsequence, assigning the element should be taken, and 2 otherwise (i.e., at = r;). Moreover, if the i-th element has been selected, we mark that the next item will not be available using u'. Therefore, f performs one step of the final output reconstruction as defined in $A.3.I
It can be easily shown that (*'(x) = (dpı,-.., dpm, O, O, ",a'....,,'' m + 1, = (dp1,-.., dpm, O, 0, r1,-.., Tim + u'). Note that the extra two elements in the input state allow lifting the special cases m - and m in the solution shown $A.3. without falling out of bounds.
Solving the puzzle task may be seen as fr for some m, where if is the elimination function Let C1y..-966 Gn be the list of clues, let H be the number of houses, and let A be partially filled solution of size x M as defined in $2.4. Each cell Ai can take H + values: the H options for the cell and the value implying this cell has not been filled. An elimination step may be defined as:
f(i..... Cn. An.... AIM...., AKı.... AKM) = (CI, Cr. A A AKI.... A ar)
where A' is also partially filled matrix, with Aij = A for every Aij to and where A' has at least one more filled cell.
Let x = (Ci...., Cn, E) where E is an empty matrix of size K x M (all cell values of E are ø). Then, full solution is computed fd (x) for some value of that increases with the problem size. In contrast to other tasks, the value of m is not fixed, and depends on the task instance, but using solvers we know that m increases with problem size.
D.3 Discussing < e in the context of Proposition 4.2
Note that in Proposition 4.2 if e < e then lim inf P(fn * Fa) 1. This because assuming -
e for some monotonically increasing function for all m > 0 that tends to 1 when m goes to infinity. Therefore, large m's 's (or alternatively, e & c) imply m
O, have
_ = c+m.c
m+I1 m+I and m+1 is
ctc
m will be close 1.
It is reasonable assume c< when g has low collision, since represents the probability of the estimator g(y) arriving at the correct output g(x) by chance when given the wrong input + x.
If g is discrete, it can take [Im(g) values, where [m([)] denotes the cardinal of the image space of g. Assuming approximately uniform errors, e R e/ [m([)], which in turn implies & 6 since g being low collision implies [Im(g)) is large.
38

---

If is continuous, under appropriate assumptions it seems plausible that we can prove that e =2 0 (e.g. if errors are approximately uniform).
Summarizing both cases, if errors are approximately evenly distributed we obtain that lim Conin P(fn # fn) = 1. a-+
39

---

E Additional Literature and Societal Impact
E.1
Additional Literature
The process of repeatedly applying noisy single operation or function can be related to iterated random functions [24]. In this latter literature, the focus is usually on the contractive regime which accrued errors can be kept under control, and the subsequent convergence guarantees (e.g., 23 When f is an affine transformation, the process falls simultaneously between two perspectives: time series [3T] and dynamic programming and control 66. We leverage the former to discuss the often explosive errors of f
Iterated Functions
E.2 Societal Impact Discussion
Our work on analyzing the limitations of current transformers in compositional tasks can have positive societal impact in several ways. By shedding light on these limitations, we contribute to deeper understanding of the capabilities and constraints of these models. This knowledge essential for researchers, developers, and policymakers in making informed decisions regarding the application of transformers in various domains.
Understanding the limitations of transformers in compositional reasoning is crucial for developing more reliable and robust Al systems. By identifying these shortcomings, we can direct future research efforts toward addressing these limitations and developing models that exhibit improved performance in handling complex tasks requiring compositional reasoning.
We do not foresee any negative societal impacts, as our analysis aims to understand the reasons behind transformers' failures and successes, but does not introduce any model dataset that future work may leverage.
40


Reviews:
[{"review_id": "GMXhxSd1Eh", "reviewer": "Reviewer_fn75", "summary": "This paper develops empirical and theoretical studies on the limitations of Transformers for solving compositional tasks. It defines computation graphs and quantifies compositional complexity with the graph metrics and uses relative information gain to predict surface patterns learned by Transformer. It conducts extensive experiments on three representative compositional tasks and finds that Transformers rely on pattern matching and exhibits poor generalization in compositionality. ", "questions": "1. Based on the findings, what could be a possible solution for improving Transformers in multi-step compositional problems? \n2. Can the computational graph definition and graph metrics be generalized to other compositional tasks, for example geometry problems? \n", "limitations": "The paper lacks methodologies or instructions for improving the model based on the obtained empirical findings and driven conclusions. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper conducts extensive experiments and profound analysis. The idea of quantifying compositional complexity with computational graphs is inspiring.", "weaknesses": "The empirical findings and the driven conclusions are quite trivial. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer fn75 for their feedback. We are excited that reviewer fn75 stated our paper includes **“extensive experiments”** and **“profound analysis”** and found the idea of using computational graphs **“inspiring”**. As a result, we would like to seek clarification on some conflicting comments made by the reviewer.\n\n### “The empirical findings and the driven conclusions are quite trivial”\n\nWe would appreciate it if reviewer fn75 could clarify their reasons behind this comment. If Reviewer fn75 meant that Transformers are expected to fail on compositional tasks with increasing complexity, we would like to highlight the fact that there is a great deal of hype in the field around the capabilities of Transformers to the point that some people believe they can handle *any* task effortlessly. In this context, we believe that our findings are critical and timely to address potential hypes and misconceptions.\n\nHowever, going beyond demonstrating that Transformers struggle with compositional tasks (to which we only dedicate a single subsection $\\S$3.1), more importantly, our findings and conclusions provide novel insights and a nuanced understanding of **why and when** Transformers succeed and struggle. To the best of our knowledge, no other research paper to date has tackled this question to the scale and depth to which this paper investigates. Moreover, we explore whether pushing Transformers to their limits can lead to complete mastery of tasks.\n\n\nWe'd like to highlight the following valuable insights and contributions of our work:\n\n* **Formalization of tasks as computational graphs ($\\S$2):**  This approach allowed us to provide a systematic and acute explanation of Transformers failures and successes. By quantifying compositional complexity using graph metrics, we gained a deeper understanding of their pattern matching behavior and could analyze errors at each reasoning step.\n\n* **Comprehensive analysis from multiple perspectives ($\\S$3.2):** We used information gain ($\\S$3.1) to explain instances where Transformers partially succeeded, performed subgraph matching analysis ($\\S$3.2) to reveal Transformers' reliance on pattern matching, and carried out fine-grained error analysis ($\\S$3.3) to categorize and illustrate various types of reasoning failures. \n\n* **Theoretical insights on Transformers' failure with increasing graph complexity ($\\S$4):** We provide mathematical arguments that Transformers' performance struggles with problems that require increasingly larger iterative applications of a function (depth) and larger parallelism (width). These proofs conclusively indicate that Transformers, in their current state, can easily fail with highly complex compositional tasks.\n\n### “The paper lacks methodologies or instructions for improving the model based on the obtained empirical findings”\n\nEnhancing Transformers' capabilities in compositional tasks **falls outside the scope of our work**. We would like to reiterate that our main goal is to explore Transformers' limits and gain a comprehensive understanding of the factors contributing to their success and failure. We've nonetheless provided a discussion ($\\S$5) in our initial submission on promising avenues to improve performance based on our theoretical results. For example, augmenting Transformers with planning modules as well as using refinement methods, that can iteratively improve their generations. We believe that these possible avenues for improvement can be valuable directions for future research.\n\n### “Can the computational graph definition and graph metrics be generalized to other compositional tasks, for example geometry problems?”\nDefinitely! Any task for which a deterministic executable program can provide a solution is one where computational graphs can be directly applied. This includes computational geometry problems, with famous examples such as convex hull, Voronoi diagram generation, closest pair of points, polygon triangulation, among others. Additionally, other problems such as graph algorithms like BFS or Dijkstra, as well as sorting algorithms can be framed as computational graphs. Tasks with low computational complexity (e.g. O(n log n) for convex hull) are great candidates for scratchpad generation since scratchpad length correlates with the algorithm’s complexity. \n\nIn conclusion, we hope our clarifications help to emphasize the significance of our paper's findings and the substantial contribution it makes. We are happy to address any additional concerns.\n\n\n\n\n\n"}, {"review_id": "jOwiSi9lZ6", "reviewer": "Reviewer_euRW", "summary": "This paper contributes to the literature on analyzing the limitations of Transformer models in compositional tasks by presenting an analysis based on computation graphs. Based on these computation graphs, some interesting new observations are made, which I believe are worth publishing.\n\nI found the paper a great read and very interesting. I have many comments/criticisms/questions below, but I would like to clarify that these are not attempts to attack the content, and more aiming for constructive criticisms for trying to make the paper more clear and situated in the literature, as I think the work is very solid.\n\nSome typos/comments:\n- Part of this work has already been studied in the past, and I think the authors should do a better job in differentiating the new insights from previously known parts. For example, I think it'd be great to discuss the new findings given: \"Making transformers solve compositional tasks\" (2021), \"The devil is in the detail: Simple tricks improve systematic generalization of transformers\" (2021), and \"Grokking: Generalization beyond Overfitting on Small Algorithmic Datasets\" (2022)\n- Page 2: \"This substantial gap suggests that systematic problem-solving capabilities do not emerge from maximum likelihood training\" -> See the Grokking paper I mentioned above, as they show that maybe systematic problem-solving abilities can improve when training beyond the overfitting threshold.\n- Section 3: As discussed in \"Making transformers solve...\" mentioned above, even if \"vanilla\" Transformers really struggle to solve compositional tasks, slight modifications to the architecture show significant gains. So, when only evaluating variants of the GPT architecture, it seems like conclusions are limited to GPT-like models, and not to \"Transformers\" in general, as small architectural decisions can have big impact in these types of tasks. For example GPT models being decoder-only models, they employ causal attention, where as encoder-decoder models would be able to deploy bidirectional attention to the input problem, which can give very different inductive biases. Carefully clarifying the extent of the conclusions would be better.\n- Section 3.1: \"suggesting that systematic problem-solving capabilities do not emerge via exhaustive training on task-specific data.\" -> Again, I'd like to bring up the Grokking paper results, and I wonder if the authors could comment on the implications for their results here.\n- Section 3.1: Although results are very interesting, I think the authors over-generalize the conclusions from experiments with one particular model pretrained in one particular way. I think it might be good to constrain conclusions of results to decoder-only-GPT-style-pretrained-Transformer models.\n- Propositon 4.1: this has very little to do with Transformers, but with any method that approximates steps. And btw, this proposition applies to humans as well, as the probability that a human makes a long calculation correct decreases with the length of the calculation due to the growing probability that at least one of the steps is wrong. So, again, I think that clarifying the extent of the conclusions in the paper needs some work, whereas above I was pointing out that experiments show failure cases for GPT-style models and you are overgeneralizing to Transformers, here you are showing a limitation of sequential prediction models, and too narrowly just blaming Transformers. Moreover, I see this proposition very related to the classic error compounding in the literature of imitation learning (e.g., see \"Efficient Reductions for Imitation Learning\", 2010), and usual solutions, e.g. Dagger, rely on training models to recover from mistakes, mitigating the problem. It'd be great to comment on the relation if the authors see it appropriate.", "questions": "- In Section 3.2.3: How were these errors analyzed? Was the text output of the models parsed to find the intermediate steps? Assuming many of these are in natural language, how accurately were you able to recover these intermediate steps?\n- Concerning memorization/shortcuts: We humans use memorization and shortcuts all the time for performing some of these operations (e.g., we know that X times 0 is 0, no matter how many digits does X have, and hence we will skip all the computation graph, etc.). The key it seems to me is to know when these shortcuts are applicable, and when they are dangerous. Did you see any case of the former (correct application of shortcuts)? (apologies if this is explained somewhere in the paper or appendix, but I was unable to find it).\n- As a curiosity, where does the \"faith and fate\" from the title come from, it might be a lack of familiarity with some English idioms, but I am struggling to make the connection with the paper.\n", "limitations": "As acknowledged by the authors in their own section, the main limitation is that experiments were conducted with just GPT models, and it's unclear if we can generalize from those, given these are all the same Transformer architecture, and pretrained in a particular way.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Even if the weaknesses of Transformers in compositional tasks have been studied many times in the recent past, this paper brings an interesting new perspective based on computation graphs that allows for a more finegrained analysis than previous work.", "weaknesses": "Perhaps the two main weaknesses (fixable) are that (1) conclusions seem to be overgeneralizing to the whole class of Transformer models, when only one instance of them was used for evaluation, and (2) it seems that some of the most relevant pieces of work in the literature were not discussed, making it harder to see what are the new pieces of knowledge that this paper is bringing compared to what was already known. Both of them fixable with small modifications to the manuscript though.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer euRW for their comprehensive, insightful, and constructive feedback! We’re thrilled to hear that they found our paper **“a great read”**, **“very interesting”**, containing **“interesting new observations”** and **“worth publishing”**.\n\n### On Grokking\nWe thank Review euRW for bringing the grokking phenomenon to our attention! We are aware of this behavior and had already conducted experiments for the multiplication task. We observed no grokking behavior, and have already incorporated the new results and discussion: see Figure 1 in the additional page for results. We will also discuss the relevant literature in the Related Work section.\nFollowing Murty et al., 2023, we trained GPT3 with question-answer pairs for 420K steps, far exceeding the point at which in-domain accuracy plateaus (~90K steps). This training duration is equivalent to 60 epochs and **costed 50,000 USD**. We also trained GPT3 with question-scratchpad pairs for 30K steps, **costing 40,000 USD**. Our findings reveal that there is no improvement in generalization beyond the overfitting point, even after extensive training periods.\n\n**We postulate that the extent to which generalization improves beyond overfitting is intricately linked to the inherent complexity of the task.** First, as suggested by Nanda et al. 2022, grokking may emerge as the model’s regularization encourages generalization even beyond the point of overfitting. Second, as concluded by Liu et al 2022, generalization during grokking corresponds with the emergence of well-structured representations. However, the model might struggle to learn well-structured representations from the training data, leading to a failure in achieving grokking. Therefore, we suspect that grokking might not necessarily arise in all tasks. **We speculate that the inherent complexity of the multiplication task makes it significantly more challenging to learn a well-structured representation.**\n\nFuture work is needed to understand grokking better, and as we mention in L319-326, we invite those equipped with much more substantial funding to investigate this further, as we couldn’t afford to spend any more than we have. It is important to note that even if some grokking were to happen through more prolonged training, such an approach would be inefficient and not scalable to more complex tasks. \n\n### “Conclusions are limited to GPT models, and not to \"Transformers\" in general” E.g. encoder-decoder models. Clarify the extent of the conclusions.\"\nOur primary focus is to understand the performance of the most powerful general-purpose models available to date, hence the emphasis on GPT-like models.  In our initial submission, we had already included explorations of other models–FlanT5-11B and LLaMA-13B–in the appendix. We will add explicit pointers to these analyses in the main text. FlanT5, an encoder-decoder model, exhibits performance trends similar to the decoder-only models. Notably, we observe a decline in performance as the task complexity increases regardless of the model architecture, as illustrated in Figure 14, 15, 16. For more in-depth details, please refer to these figures.\n\n### “Proposition 4.1: this has little to do with Transformers, but with any method that approximates steps. This proposition applies to humans as well (...)”\nOur main goal in the theoretical section is to provide further perspective on the presented empirical results, making explicit the ways in which compounding stochastic errors affect final performance. We talk about out-of-the-box autoregressive transformers to align with experiments, and because of recent claims of their reasoning skills. We agree that propositions apply to any high-performant estimator of reasoning tasks, as we allude in $\\S$5: we will expand upon the discussion in $\\S$4.\nPropositions potentially do not apply to humans, who can review and correct their computations, possibly making the hypothesis $P(\\hat{g} != g) = \\epsilon > 0$ not hold. This would also be the case when pairing Transformers with inference-time algorithms–a direction that our propositions enable us to discuss in $\\S$5.\n\n### Proposition 4.1 is “very related to the classic error compounding in the literature of imitation learning (...). It'd be great to comment on the relation”\nThanks for bringing this to our attention! We will mention this in the discussion, as the analogy with imitation learning may spark future work on mitigating these issues in LLMs through novel algorithms in line with e.g. DAgger.\n\n### How were errors analyzed? Parsing scratchpad? \nThe models generate scratchpads using 2 approaches. 1) \"in-context learning\": prompting with 5 examples of question-srcatchpad pairs. 2) \"finetuning on the question-scratchpad pairs\". We build a computation graph out of the generated scratchpad via string regex parsing. Since the scatchpad language is templated (see Figure 8 in Appendix), our parsing accuracy is near perfect. This accuracy was confirmed through manual inspection of a randomly selected small set.\nTo analyze errors, we compared the generated computation graph to the ground truth computation graph, and categorized each model \ngenerated step to four categories (fully correct, local error, propagation error, restoration error) as described in $\\S$3.2.3. \n\n### Concerning shortcuts\nWe observed that, for problems with low complexity, Transformers could provide correct answers by relying on learned surface patterns, like \"X times 0 is 0\". In general, Transformers appear to struggle in discerning when to employ shortcut learning versus using the computation graph. Shortcut learning can be a speedy solution,  but it becomes brittle when machines lack the knowledge of when to use it. \n\n### \"faith and fate\" meaning\nWe wanted to allude to the faith (part of) the community has in Transformers’ general reasoning capabilities and contrast it with the fate of them failing when tested in the limit. We also think it is a nice alliteration!   \n\n\n"}, {"review_id": "iasVjnOyRh", "reviewer": "Reviewer_cZLE", "summary": "This work studies the ability of LLMs for compositional tasks. They propose a formalization called computation graphs. With this formalization, they further propose three different tasks: multi-digit multiplication, Einstein’s puzzle, and a dynamic programming problem. They test multiple LLMs on these three tasks with different training and inference settings. By varying the depth and width of the graph, they show that LLMs do not do well when the scale of the problem is large. In their further analysis, they point out two problems of LLM models: relying on single-step shortcuts and relying on similar training subgraphs. They also conduct an error classification and notice many hints for memorization (e.g., restoration error). Finally, this work presents a theoretical analysis showing the effect of error propagation.", "questions": "1.\tThe prompt in the scratchpad seems to be carefully designed. How many different prompts have you tried? How do different prompts influence the findings?\n2.\tHow do you compute the entropies used in the information gains?\n3.\tJust to confirm, when doing the question-answer training, is there no scratchpads? \n", "limitations": "This work provided a limitation section in Sec. 8 in the main paper and a societal impact statement in Appendix E.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.\tThis work presents a relatively comprehensive and detailed evaluation of the compositional abilities for LLMs. The empirical results contain multiple training settings, and results w/wo scratchpads. \n2.\tThe three tasks designed in this work can be valuable for future work on compositional tasks.\n3.\tThe error analyses in this work are detailed and insightful. I really like the error classification analysis, which shows a more detailed description about LLM behaviors, and provide concrete and quantitative evidence for memorization, restoration error and error propagation.\n", "weaknesses": "1.\tWhile the theoretical derivation is interesting, I find the takeaways and the perspective to be slightly underwhelming. The main takeaway seems to be error propagation lead to bad results when the problem scale is sufficiently large. This is true, but this is also true for everything, and for both machines and humans. To me, the more interesting problem lies in that why even n is not very large, compositional problems still seem to be relatively hard. Additionally, I think the theoretical derivation applies to sampling but not to greedy decoding. \n2.\tThe idea of using a computation graph to control and analyze the difficulty of composition is not novel, see related works in [1][2][3]. While I do feel that the approach and objective of this paper are different enough compared to previous works, there should still be a discussion about these works.\n3.\tMinor presentation issue: Some experimental setup details are hard to find. For example, I cannot find how large the finetuning datasets are. And some of the other important details (e.g., how you split the train/test for finetuning experiments) are in the appendix. I understand the space is tight in the main paper, but I would encourage the authors to add some details to the main paper so that the results can be interpreted more easily.\n\n\n\n[1] Josef Valvoda, Naomi Saphra, Jonathan Rawski, Adina Williams, and Ryan Cotterell. Benchmarking Compositionality with Formal Languages. In COLING 2022.\n\n[2] Keysers, Daniel, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev et al. Measuring Compositional Generalization: A Comprehensive Method on Realistic Data. In ICLR 2020.\n\n[3] Ben Bogin, Shivanshu Gupta, and Jonathan Berant. Unobserved Local Structures Make Compositional Generalization Hard. In EMNLP 2022.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer cZLE for their helpful feedback. We appreciate that Reviewer cZLE found our evaluation study **“comprehensive”** and **“detailed”**, and the designed tasks **“valuable”** for future work. We are also thrilled that Reviewer cZLE found the error analysis to be **“detailed”** and **“insightful”**, providing **“concrete”** and **“quantitative”** evidence for LLM behaviors.\n\nThe key clarification points are outlined below, grouped by theme.\n\n### “The main takeaway seems to be that error propagation lead to bad results when the problem scale is sufficiently large. (...) this is true for everything, and for both machines and humans. To me, the more interesting problem lies in that why even n is not very large, compositional problems still seem to be relatively hard”\n\nOur main goal in the theoretical section is to provide further perspective on the presented empirical results, making explicit the different ways in which compounding stochastic errors affect final performance. The current form of the propositions aims to emphasize performance degradation in the limit, but we will change the statements to explicitly show the bounds we derivate: **probability of success decreases exponentially with the required level of compositionality, which helps explain high failure rates even with small values of n**. \n\nWe agree that **propositions apply to any high-performant estimator of reasoning tasks**,  in particular Transformer models. In fact, we mention in $\\S$5 that these propositions do apply more broadly, and we will expand upon this discussion in $\\S$4 as well. \nWe focus on out-of-the-box autoregressive Transformers, aligning with the scope of our experiments and the recent claims about their general compositional capabilities. By employing the propositions, we intend to inform future research directions as outlined in $\\S$5, including intriguing avenues like self-correction.\nThis is a point where we believe out-of-the-box Transformers and humans differ, making propositions potentially not applicable: humans can review and correct their computations, possibly making the hypothesis $P(\\hat{g} != g) = \\epsilon > 0$ not hold. \n\n### “I think the theoretical derivation applies to sampling but not to greedy decoding”\nIt applies in both cases! For the case of greedy decoding, $\\hat{g}$ is deterministic and the proofs can be read as a combinatorial solution, where the probability would literally be the fraction of results with the desired condition.\n\n### “How many different prompts have you tried? How do different prompts influence the findings?”\nWe thank Reviewer cZLE for these great questions.  We experimented with several scratchpads to identify the optimal prompt that yielded the best results for all models, including GPT-4, ChatGPT, and GPT-3.  Notably, we observed that when the scratchpad primarily consists of mathematical symbols without sufficient natural language explanations for the math operations, the models tend to exhibit poorer performance. As a result, we took great care to provide detailed and natural sentence explanations for each reasoning step. For reference, please see Figure 8 in Appendix A.1, which showcases the scratchpad used for multiplication.\n\n### “How do you compute the entropies used in the information gains?”\n\nWe exhaustively compute the Shannon entropy for all possible input-output pairs for the specified problem sizes: in other words, and following $\\S$2.3’s terminology, we enumerate (X_1, …, X_n, Y_1, ..., Y_m)’s sample space. We have made sure to clarify this in the paper. For faster computation, one could randomly sample input-output pairs when computing entropy--of course, assuming a large enough sample size for the dimensionality of the features being considered. \n\n### “when doing the question-answer training, is there no scratchpads?”\nYes, when training on question-answer pairs, the “answer” contains the final answer without the inclusion of the scratchpad. \n\n### Discuss additional related works\nThanks for bringing up additional related work! Please refer to our overall response for a more detailed discussion of them.\n\n### Fix the presentation issue about the training data details.\nWe apologize for this inconvenience. We have made sure to bring those details to the main paper to remove any ambiguity. \n\n\n\n"}, {"review_id": "OXGNqjSUvZ", "reviewer": "Reviewer_jnqc", "summary": "This paper studies the compositional reasoning capability of Transformer models on three kinds of tasks, namely multi-digit multiplication, logic grid puzzles, and a dynamic programming problem. The compositional complexity of a given task, or the number of reasoning steps, can be easily controlled by varying lengths of inputs. This paper formulates the reasoning steps as a computation graph and uses characteristics like lengths and widths of the computation graph to qualify the level of complexity. For experimental evaluation, this work evaluates several Transformer models (i.e., GPT3, ChatGPT, GPT-4) using zero-shot, few-shot, and finetuning techniques. This paper shows that in zero-shot and few-shot settings, all three Transformer models deteriorate sharply from nearly perfect to nearly zero when increasing compositional complexity. Furthermore, finetuning GPT-3 with or without scratchpads does not help GPT-3 generalize to unseen and more complicated task instances. To gain a deeper understanding of these failures, this work finds that 1) Transformer models are likely to give partially correct predictions on outputs that can be determined by a small set of input features, and 2) Transformer models are likely to rely on computation patterns seen in training data and generalize poorly when they are not sufficient for OOD tests. Finally, with reasonable assumptions, this work gives a theoretical justification for why any models fail to generalize longer compositional reasoning tasks. Informally, as long as every single step is not perfect, the error will happen for a sufficiently long reasoning chain. ", "questions": "Even assuming the computation graph is unique for a specific problem instance, exponentially many different sequential steps could express the same computation. How many sequences are extracted for a problem instance? \n\nThe definition (line 213) of whether a full computation is seen during training is not quite clear, particularly what's the precise meaning of the sign $\\equiv$ here?\n\nFigure 5b shows that predictions with large graph depth (e.g., > 16) tend to be all correct and have zero frequencies. It seems the Transformer models do generalize to more complicated tasks without reusing seen computation patterns in the training. Is it a plotting issue? Or is this interpretation wrong for some reason?", "limitations": "The authors discussed potential limitations, and there is no (obvious) negative societal impact of this work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This work carefully selects three representative compositional tasks and introduces computation graphs to systematically quantify the level of complexity. \n- State-of-the-art transformer models like GPT-3, ChatGPT, and GPT-4 are used in the experimental evaluations. The observed limits are likely to be universal for existing transformer models. \n- Some new insights in analyzing the successes and failures of Transformer models are presented. Specifically, relative information gain seems a likely reason that Transformer models tend to predict partially correct answers; and linearized subgraph matching suggests Transformer models tend to capture spurious patterns in the training.\n- Four interesting categories of errors are proposed and can effectively characterize the mistaken behaviors of Transformer models when the compositional complexity increases. The restoration error is particularly interesting, as it captures an often ignored problem -- the model could give correct answers but because of wrong reasons. \n- Some simple but formal analyses are proposed to illustrate the theoretical limits of Transformer models. \n", "weaknesses": "- It is well-known that large language models like GPT-3, ChatGPT, and GPT-4 behave poorly on complicated reasoning and planning tasks.  So, most results of this work are somewhat expected.\n\n- Only three tasks are evaluated, and only one specific algorithm is chosen for each task. Although the chosen algorithm seems straightforward, it is possible that the particular algorithm may not be appropriate for Transformer models to learn. It does not rule out that the Transformer models may be good at learning other less intuitive algorithms for the evaluated tasks. \n\n- Finetuning is only performed on GPT-3. It is understandable that finetuning larger models like ChatGPT or GPT4 is computationally prohibitive for a small research group. But, from a scientific point of view, the observations on GPT-3 may not generalize to ChatGPT or GPT4, and the emergent capabilities of larger language models may overcome the limits observed on GPT-3.\n\n- The claim of subsection 3.2.2 is a bit subjective. Linearized subgraph matching is a means proposed in this work to better understand Transformer models. It does shine some light on why Transformer models fail for the chosen tasks, however, whether that's indeed Transformers' internal dynamics is not quite clear. \n\n- The theoretical justification seems oversimplified. It has nothing to do with the Transformer models. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer jnqc for their encouraging and detailed feedback. We are glad they highlighted we provide **“new insights in analyzing the successes and failures of Transformers”** using state-of-the-art models, which implies that **“the observed limits are likely to be universal for existing transformer models”**; as well as **“interesting”** error categorization analysis, which **“captures an often ignored problem”**.\nKey clarifications are outlined below, and we respond inline.\n\n### “It is well-known that large language models (...) behave poorly on complicated reasoning and planning tasks. So, most results of this work are somewhat expected.”\nAs reviewer jnqc highlights in their review, **our work focuses on providing novel insights on why and how models fail through the use of computation graphs**, and not merely on observing Transformers’ failure rates for reasoning tasks. We only dedicate a single subsection $\\S$3.1 to reporting Transformers’ failures. We would nonetheless like to emphasize that a fraction of our research community tends to **glorify** models like GPT-4 as possessing **superhumans** reasoning capabilities. Thus, including this report ensures a more balanced portrayal of LLMs. Moreover, in $\\S$3.2.3, we show that Transformers’ successes correlate with having seen significant subgraphs of the full graph required during training, which could help explain the underlying reasoning behind some of the impressive generations reported in prior work (e.g. Bubeck et al., 2023).\n\n\n### “Only three tasks are evaluated, and only one specific algorithm is chosen for each task. (...) It does not rule out that the Transformer models may be good at learning other less intuitive algorithms for the evaluated tasks.”\n\nOur focus is on evaluating how/if models can follow the straightforward algorithms described, and in $\\S$3.1 we correlate accuracy with algorithmic difficulty using metrics such as width, depth, and average parallelism. We intentionally selected very diverse task+algorithm pairs, and consistently saw similar behaviors throughout $\\S$3. This consistency suggests that it's unlikely that different algorithms would give radically different results, especially taking into account $\\S$4’s theoretical justifications.\n\nEven if unlikely, we acknowledge that one can never rule out this possibility completely, and we will add it to our limitations. We emphasize that our work serves as a stepping stone, laying the groundwork for future investigations into these unresolved questions. This is particularly crucial in the current AI landscape.\n\n### “Finetuning is only performed on GPT-3. (...) finetuning larger models like ChatGPT or GPT4 is computationally prohibitive (...) But, from a scientific point of view, the observations on GPT-3 may not generalize to ChatGPT or GPT4, and the emergent capabilities of larger language models may overcome the limits observed on GPT-3.”\n\nOpenAI does not currently allow ChatGPT or GPT4 finetuning, and we, unfortunately, have no official information even on whether ChatGPT is a larger LM than GPT3 or not. Nonetheless, we observe similar limitations (in the limit) on ChatGPT and GPT4 as those shown for GPT3 in the zero-shot and few-shot settings, which leads us to believe that we would see similar trends on the finetuning case as well. We encourage OpenAI to publicly share findings if these limitations do not hold with GPT4! \n\n###  \"Linearized subgraph matching is a means proposed in this work to better understand Transformer models (...) whether that's indeed Transformers' internal dynamics is not quite clear.\"\nIn  $\\S$3.2.2, we highlight a notable correlation between the frequency of subgraph data and task performance. This observation led us to hypothesize that models rely on pattern matching rather than general reasoning abilities to predict correct outputs. However, we acknowledge that our results only indicate a correlation, not a causal relationship. This limitation arises because our access to large language models is restricted to limited API calls, preventing us from examining their internal dynamics. In fact, we had actually addressed this concern in our initial submission's Limitations section ($\\S$8). \n\n### “The theoretical justification (...) has nothing to do with the Transformer models.”\nPlease refer to the joint response for a detailed explanation. \n\n### What does sign ≡ mean in line 213?\nWe mean that these graphs are isomorphic, with also a correspondence in the labels assigned–that they are essentially the same graph. To enhance clarity, we'll consider using the symbol ≅ and ensure this is explicitly mentioned in the text.\n\n### \"In Figure 5b, why do predictions with large graph depth (e.g., > 16) tend to be all correct and have zero frequencies?\"\nThis comes as a byproduct of having virtually no subgraphs of that depth. For the dots reported for graph depth >= 16, we have $log_{10}(x)≈0.02$ per the logarithmic plot, showing that there are only ~2 subgraphs of that depth. Readers should focus on the differences between correct and incorrect final answers for smaller depths, where there are a vast number of subgraphs of that depth seen during training. We will modify the plots to only report points where there are at least 30 subgraphs of that depth.\n\n### “Even assuming the computation graph is unique for a specific problem instance, exponentially many different sequential steps could express the same computation. How many sequences are extracted for a problem instance?”\nWe agree that there are multiple valid linearizations for a given computation graph, i.e. any topological ordering would work. We maintain the order in which nodes are generated in the canonical solutions for each task, and report the scratchpad used in Appendix A. \n\n\n\n\n\n\n"}]

Author rebuttal:
## Overall Response
### Discuss Additional Related Work

We appreciate reviewer euRW and reviewer cZLE for bringing additional relevant works to our attention! Given the page limit constraint, we were unable to discuss those works in our initial submission. However, we will incorporate them into the related work section along with other works in the same vein in the revision. While relevant, these works have different goals from our study:

The following works [1, 2, 3] focus primarily on how to enhance LLMs performance on compositional problems. In contrast, we aim to investigate the **fundamental limits** of Transformers in achieving full mastery of the task by pushing the models’ limit in terms of training and prompting. Our primary goal is to determine **whether and why** the most powerful LLMs, such as GPT-4 and ChatGPT, can consistently achieve perfect performance in both in-domain and out-of-domain settings as the complexity of tasks increases. We offer novel insights into the intricacies involved, shedding light on the reasons why achieving full mastery on compositional problems is inherently challenging. 

The works [4,5] propose novel methods to construct compositionality benchmarks and subsequently evaluate LLM behavior against these benchmarks. The work [6] discusses that improvement in generalization can happen well past the point of overfitting through a process called "grokking". However, these findings are limited to "small transformer model" and "small algorithmically generated datasets". It remains unclear whether the conclusion would generalize to LLMs dealing with complex tasks. We conducted additional experiments to investigate this phenomenon in our setting, please see the response to R2 for more details and the attached page.


### Expanding characterization of our theoretical results: we agree they apply to more agents than just Transformers!

Our main goal in the theoretical section is to provide further perspective on the presented empirical results, making explicit the different ways in which compounding stochastic errors affect final performance. We agree that **propositions apply to any high-performant estimator of reasoning tasks, and we mention in $\S$5 that they apply more broadly**: we will expand upon this discussion and mention this in $\S$4 as well. We focus on out-of-the-box autoregressive Transformers, aligning with the scope of our experiments and the recent claims about their general compositional capabilities. By employing the propositions, we intend to inform future research directions as outlined in $\S$5,  such as augmenting models with self-correction modules.

The current form of the propositions aims to emphasize performance degradation in the limit, but we will change the statements to explicitly show the bounds we derivate: **the probability of success decreases exponentially with the required level of compositionality**, which helps explain high failure rates even with small values of n. Providing *specific bounds for transformers based on their specific architecture is an interesting future work direction*.


**Bibliography**

[1] Ontanón, Santiago, Joshua Ainslie, Vaclav Cvicek, and Zachary Fisher. Making Transformers Solve Compositional Tasks. ACL 2022.

[2] Csordás, Róbert, Kazuki Irie, and Jürgen Schmidhuber. The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers. EMNLP 2021.

[3] Bogin, Ben, Shivanshu Gupta, and Jonathan Berant. Unobserved Local Structures Make Compositional Generalization Hard. In EMNLP 2022.

[4] Valvoda, Josef, Naomi Saphra, Jonathan Rawski, Adina Williams, and Ryan Cotterell. Benchmarking Compositionality with Formal Languages. In COLING 2022.

[5] Keysers, Daniel, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev et al. Measuring Compositional Generalization: A Comprehensive Method on Realistic Data. In ICLR 2020.

[6] Power, Alethea, Yuri Burda, Harrison Edwards, Igor Babuschkin and Vedant Misra. “Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets.” arXiv preprint arXiv:2201.02177 (2022).

[7] Nanda, Neel, Lawrence Chan, Tom Liberum, Jess Smith, and Jacob Steinhardt. "Progress measures for grokking via mechanistic interpretability." In ICLR 2022.

[8] Liu, Ziming, Ouail Kitouni, Niklas S. Nolte, Eric Michaud, Max Tegmark, and Mike Williams. "Towards understanding grokking: An effective theory of representation learning."  In NeurIPS 2022.

[9] Murty, Shikhar, Pratyusha Sharma, Jacob Andreas, and Christopher D. Manning. Grokking of Hierarchical Structure in Vanilla Transformers.  In ACL 2023


Meta-review: The paper investigates the limitations of Transformer-based large language models in handling compositional tasks. It presents a thorough empirical study on three different types of tasks—multi-digit multiplication, logic grid puzzles, and a classic dynamic programming problem—to assess how these models perform in solving problems that require multi-step reasoning. The work introduces computation graphs as a novel metric for quantifying compositional complexity, and finds that these models often resort to mimicking patterns seen during training rather than developing genuine problem-solving capabilities.

The reviewers were particularly impressed by the extensive experiments and deep analysis presented in the paper. They found the idea of using computation graphs to measure compositional complexity inspiring and lauded the paper's comprehensive and detailed evaluation. The tasks designed for this study were considered valuable for future research on compositional reasoning, and the categories of errors identified were noted to be intriguing. Nevertheless, some reviewers pointed out that the empirical findings could be perceived as trivial, and the conclusions might be overgeneralized. Additionally, the theoretical justification was seen as somewhat oversimplified. However, these weaknesses do not significantly detract from the paper’s overall contribution and could be addressed in revisions. Hence, the paper receives a strong accept recommendation.
Decision: Accept (spotlight)