Faith and Fate: Limits of Transformers on Compositionality

Introduction

“It was the epoch of belief, it was the epoch of incredulity.” – Charles Dickens, A Tale of Two Cities

Large-scale transformers such as ChatGPT and GPT4 demonstrate unprecedented capabilities , even noted as “sparks of AGI” . In stark contrast, the same models sometimes struggle with simple, intuitive tasks . For instance, humans can solve 3-digit by 3-digit multiplication arithmetic after learning basic calculation rules . Yet, off-the-shelf ChatGPT and GPT4 achieve only 55% and 59% accuracies on this task, respectively (§3).

The striking discrepancy between the impressive successes of transformer LLMs on seemingly complex tasks and the astonishing failures on seemingly trivial tasks spark critical open questions about how to 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 transformersFor brevity, we use ‘transformers’ to refer to ‘autoregressive transformer LLMs’ throughout the paper., centered around compositional problems that require strict multi-hop reasoning to derive correct predictions. Applying step-by-step reasoning is fundamental to human intelligence . These compositional problems present compelling challenges for AI 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: long-form multiplication, logic grid puzzles (i.e., Einstein’s puzzle ), 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 . Shortcut learning via pattern-matching 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 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 to training examples sub-graphs that involve the same computations required for solving test examples (see Section 3.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 a 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-boxCode and data are available at https://github.com/nouhadziri/faith-and-fate.

As transformers continue to make tangible real-world impacts, it is pressing to interpret their remarkable 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.

Measuring Limitations of Transformers in Compositional Tasks

Human problem-solving skills can be conceptualized as a graph structure, where each vertex represents 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 1, we use computation graphs and corresponding metrics to methodically evaluate transformers’ reasoning abilities.

Let $S\subset V$ be the source nodes of $G_{A(\mathbf{x})}$ and without loss of generality, let $o\in V$ be its sole leaf node. By definition, $S\equiv\mathbf{x}$ and $A(\mathbf{x})=s(o)$, representing the input and output of $A$ respectively.

To be able to train and evaluate a language model’s ability to follow algorithm $A$ we must linearize $G_{A(\textbf{x})}$. Since we only consider autoregressive models, this linearization must also be a topological ordering.

2 Quantifying Compositional Complexity using Graph Metrics

$A$’s representation as a computation graph $G_{A(\mathbf{x})}$ enables measuring task complexity from many angles.

We define a node $v\in V$’s layer number as the length of the longest path from a source node to $v$ in the directed acyclic graph $G_{A(\mathbf{c})}$. We then define the reasoning depth as the largest layer number in the graph. In computation graphs, reasoning depth is a proxy for the maximum level of multi-hop reasoning required to solve the task.

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 represent task $T$ as a distribution $(X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{m})$ and measure the amount of (normalized) information gained about an output element $Y_{j}$ by observing a subset of input random variables $X\subset\{X_{1},\ldots,X_{n}\}$:

RelativeIG may be used to analyze the influence of any node in the computation graph (as defined in §2.1) with respect to a set of its ancestors; in particular, output nodes with respect to input nodes.

4 Exploring Three Representative Compositional Tasks: Definitions

Multi-digit multiplication requires executing operations with numerical symbols based on procedural rules . This task has multiple algorithmic solutions; in constructing computation graphs, we use the well-known $O(k_{1}k_{2})$ long-form multiplication algorithm for computing $x\cdot y$, where $x$ has $k_{1}\leq 5$ digits and $y$ has $k_{2}\leq 5$ digits in base 10. See §A.1 for data construction details.

To instantiate $G_{A(\mathbf{x})}$, let $\mathcal{F}_{A}=\{\text{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 $v$ are partial results generated during execution of the long-form multiplication algorithm (see Figure 1).

Einstein’s puzzle is a well-known logic puzzle often used as a benchmark for solving constraint satisfaction problems . It involves a list of houses with different attributes (e.g., owner’s name, pets), and the goal is to determine which attributes belong to each house by combining a set of pre-defined natural language clues or constraints. The solution to the puzzle is a matrix of size $K\times 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. It 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 §A.2 for examples, data construction, and algorithm details.

To instantiate $G_{A(\mathbf{x})}$, let $\mathcal{F}_{A}\!=\!\{\text{elimination function}\}$. The source nodes are the clues, all intermediate nodes are partially-filled matrices, and the output node is a fully-filled solution matrix.

Dynamic programming (DP) recursively breaks down complex problems into simpler sub-problems, so problems solved using this technique are compositional. We analyze a classic relaxation of the NP-complete Maximum Weighted Independent Set problem : Given a sequence of integers, find a 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 in §A.3. In the experiments, we restrict each integer to the $$ range.

To instantiate $G_{A(\textbf{x})}$, let $\mathcal{F}_{A}=\{\text{equals, and, not},\text{indicator function, sum, max}\}$. Source nodes are elements of the input list, and the output node is a list that for each element indicates whether it should be selected. We select an $O(n)$ algorithm since $G_{A(\mathbf{x})}$’s size is proportional to $A$’s complexity.

Testing the Limits of Transformers: Empirical Evidence

To understand the capabilities of LLMs, we evaluate GPT3 (text-davinci-003) , ChatGPT (GPT-3.5-turbo) and GPT4 (gpt-4) using zero-shot, few-shot, and finetuning techniques. To enable the generation of computation graphs beyond the final answers, we use the concept of scratchpads . Scratchpads are a verbalization of the computation graphs (i.e., a linearized representation of a topological ordering of $G_{A(\textbf{x})}$). Overall, we consider question-answer and question-scratchpad 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 §B and examples of scratchpad in §A.

1 Testing the Limits of Transformers with Zero-shot, Few-shot and Finetuning

To investigate the inherent problem-solving capabilities of LLMs, we begin by analyzing models’ zero-shot and few-shot performances on our compositional tasks. As shown in Figure 2, task performances deteriorate significantly from near perfection to zero with increasing complexity when measured by either problem size (Figure 2(a))or average parallelism (Figure 2(b)).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.

The limited performance of models may be attributed to the lack of task-specific data during pre-training. To fully bring out models’ potentials in solving these tasks, we next exhaustively finetune GPT3 with question-answer pairs. In multiplication and DP, we finetune models with all enumerations of questions up to the maximum problem sizeWe consider all $k_{1}$-by-$k_{2}$ digit multiplications with $1\leq k_{1},k_{2}\leq 4$ and $k_{1}\cdot k_{2}\leq 9$; and all DP problems up to $5$ elements. We selected sizes based on budget constraints for GPT3 finetuning, see §B.3 for cost details. 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)\leq(4,4)$ due to combinatorial explosion. We separately finetune GPT3 models on $\sim$1.8M multiplication pairs, $\sim$142K DP pairs, and $\sim$41K puzzle pairs (see details in §B.3). Additionally, to examine problems of different complexity, we consider different training splits based on the depth and width of computation graphs.

Figure 4 and Figure 5(a) 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-specific data.

Next, we test whether we can explicitly teach models the required computational operations via scratchpads. To do so, we finetune GPT3 with question-scratchpad pairs for all tasks. We consider the same distribution splits as before. The results, presented in Figure 5(b), show that once again GPT3 achieves near-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-step solution. Instead, models depend on a greedy process of producing the next word to make predictions without a rigorous global understanding of the task.

We explore whether extended training beyond overfitting leads to improved generalization abilities, a phenomenon known as grokking . Due to budget constraints, we only experiment on the multiplication task. Following , we fine-tune GPT3 with question-answer pairs for 420K steps and separately finetune GPT3 with question-scratchpad pairs for 30K steps. Both models’ training far exceeded the point at which in-domain accuracy plateausThe training duration for question-answer pairs is equivalent to 60 epochs and costs 50,000 USD. Training on question-scratchpad pairs was conducted for 40 epochs and costs 40,000 USD.. Figure 4 shows no improvement in generalization for OOD cases beyond the overfitting point, even 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 , 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.

2 Breaking Down Successes and Failures of Transformers

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), 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 §C.1). 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 to 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 (e.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 §C.

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.

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 underlying 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 an instance appear in the training data, for both correctly and wrongly predicted examples.

Given a model-generated computation graph $\widehat{G}_{A(\mathbf{x})}$ we analyze how often the full computation of each node $v\in\widehat{V}$ is seen in training. We define $v$’s full computation as the subgraph induced by all ancestors of $v$ including $v$, denoted $FC_{\widehat{G}_{A(\mathbf{x})}}(v)$. We say that $FC_{\widehat{G}_{A(\mathbf{x})}}(v)$ is seen during training if $FC_{\widehat{G}_{A(\mathbf{x})}}(v)\cong FC_{G_{A(\mathbf{x^{\prime}})}}(w)$ for some computation graph $G_{A(\mathbf{x^{\prime}})}$ in training, and for some $w\in V$. We characterize complexity of a full computation subgraph by its depth, as defined in §2.1.

Figure 7 shows that full computation subgraphs appear significantly more frequently in the training data for correctly predicted test examples than for incorrectly predicted ones, for both the multiplication and DP task (both frequencies tend to zero for large depths since we ensured a disjoint train/test split). This high correlation suggests that pattern matching—and not general reasoning capabilities—may be the cause behind correct model outputs. This type of learning could be largely effective when the compositional complexity of tasks is low but it becomes less efficient when tasks are 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.

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 at different layers in the computation graph. For every input $\mathbf{x}$, we compare the ground truth computation graph $G_{A(\mathbf{x})}$ with the (possibly incorrect) model-generated computation graph $\widehat{G}_{A(\mathbf{x})}$. We consider a node $v$ as having a correct value if and only if $s(v)=\widehat{s}(v)$.If a node $v$ does not appear in the ground truth graph $G$, we consider it to have an incorrect value.. We consider a node $v$ to be derived from a correct computation if given that $U=\{u_{1},\ldots,u_{k}\}$ are the immediate predecessors of $v$ in $\widehat{G}_{A(\mathbf{x})}$ and that $\widehat{op}(v)=f$, we have that $f(u_{1},\ldots,u_{k})=\widehat{s}(v)$. Note that the notion of correct computation is independent of $G$, and that a node $v$ derived from a correct computation may not have the correct value if an error occurred in some of its ancestors.

We classify each node $v\in\widehat{V}$ into one of four categories. Node $v$ is fully correct if $v$ and its ancestors have correct values and are derived from correct computations. If a node $v$ is not fully correct, its error can be of the following types: $v$ has a local error if its parent nodes have correct values but $v$ is derived from an incorrect computation (i.e., a one-hop reasoning error); $v$ has a propagation error if $v$ is derived from a correct computation but some of its parent nodes have incorrect values; $v$ has a restoration error if it has a correct value but is derived from an incorrect computation.

Figure 7 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 to plan and compose several of these steps for an overall correct reasoning.

Both the DP and the puzzle tasks have a 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.

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 a function:

Let $f_{n}$ involve the combination $h_{n}$ of $n$ independent applications of a function $g$. Let $\widehat{f}$, $\widehat{g}$, $\widehat{h}_{n}$ be their estimators. Assume that $\widehat{h}_{n}$ is a perfect estimator of $h_{n}$ and that $h_{n}$ has low collision, with $c_{n}$ being an upper bound of $h_{n}$’s collision rate ($c_{n}<c\ \forall n$, with $c\ll 1$). If $\mathds{P}(g\!\neq\!\widehat{g})\!=\epsilon>\!0$ where $\widehat{g}$’s errors are independent, then $\mathds{P}(f_{n}\!\neq\!\widehat{f}_{n})>1-c_{n}-(1-\epsilon)^{n}\cdot(1-c_{n})$. This implies that $\mathds{P}(f_{n}\!\neq\!\widehat{f}_{n})$ decreases exponentially as $n$ increases, with $\displaystyle\liminf_{n\rightarrow+\infty}\mathds{P}(f_{n}\!\neq\!\widehat{f}_{n})\geq 1-c$. Moreover, if $c_{n}\leq\beta\alpha^{n}$ for some $\alpha\in(0,1),\beta>0$, $\mathds{P}(f_{n}\!\neq\!\widehat{f}_{n})$ tends exponentially to $1$ as $n$ increases.

Prop. 4.1’s proof (§D.1) shows the rate of convergence is exponential, thus concluding that transformers will rapidly fail with increasing $n$. Let’s now analyze the iterated application function scenario.

Let $f_{n}(\mathbf{x})\!=\!g^{n}(\mathbf{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 $c$. If $\mathds{P}(g\!\neq\!\widehat{g})\!=\!\epsilon\!>\!0$, then $\mathds{P}(f_{n}\!\neq\!\widehat{f}_{n})$ decreases exponentially with $n$. Precisely, $\mathds{P}(f_{n}\!\neq\!\widehat{f}_{n})\geq 1-(1-\epsilon-c)^{n-1}(1-\epsilon-c/(c+\epsilon))$, implying $\displaystyle\liminf_{n\rightarrow+\infty}\mathds{P}(f_{n}\!\neq\!\widehat{f}_{n})\geq 1-c/(c+\epsilon)$.

The argument is as follows. Let $s_{n}:=\mathds{P}(f_{n}=\widehat{f}_{n})$, where $s_{1}=1-\epsilon$ by definition. Derive $s_{n}\leq(1-\epsilon-c)\cdot s_{n-1}+c$ using law of total probability. Then, prove by induction a non-recursive upper bound for $s_{n}$ with limit $\frac{c}{c+\epsilon}$ when $n\rightarrow+\infty$. See formal statement and derivation in §D.2.

Prop. 4.2’s proof also shows an exponential rate of convergence. Note that if $c\!\ll\!\epsilon$ then $\displaystyle\liminf_{n\rightarrow+\infty}\mathds{P}(f_{n}\,\neq\,\widehat{f}_{n})\approx 1$. It is reasonable to assume $c\!\ll\!\epsilon$ when $g$ has low collision, since $c$ represents the probability of the estimator $\widehat{g}(y)$ arriving at the correct output $g(x)$ by chance when given the wrong input $y\neq x$. More details in §D.3.

Moreover, repeated applications of a function often imply unbounded errors: if $g(x)$ can be expressed as an affine transformation $Fx\!+\!c$, then it may be viewed as a first-order vector autoregression, which are known to be unstable when $|\lambda|\geq 1$ for at least one $\lambda$ 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 —but their study is beyond the scope of this paper.

In Prop. 4.2’s current form, we implicitly assume that there is a 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 $\epsilon$, and the probability of recovering from an invalid state is at most $c$. 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.1 directly applies to multiplication, since $m$-by-$n$ digit multiplication can be seen as $n$ independent instances of $m$-by-$1$ digit multiplication (see Cor. D.1). 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 to any high-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.

Discussion

Transformers today demonstrate undeniably powerful empirical results. Yet, 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 to 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.

The proofs presented in §4 show that, under reasonable assumptions, the probability of incorrect predictions converges exponentially to $\approx 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 a 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 a few compositional steps to reach a solution rather than lengthy reasoning steps (e.g., ). 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 a multiplication. Finally, we suggest augmenting transformers with planning modules as well as using refinement methods, that can iteratively improve their generations .

Identification of limitations is an important step towards achieving greater robustness. Our study suggests fundamental limitations that impede transformers from fully mastering certain compositional operations. However, we acknowledge that due to our compute budget constraints as 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

Recently, transformers have demonstrated impressive reasoning abilities across a wide range of tasks, even outperforming humans in certain cases . This success has been largely attributed to the scaling effect, where larger models and training datasets result in improved performance . However, these models have also been shown to struggle across multiple domains , including algorithmic reasoning , commonsense reasoning , theory of mind , planning , logical reasoning , and ethical reasoning . 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.

Transformers perform fairly well in single-step reasoning tasks , but face challenges when it comes to effectively combining multiple steps to solve compositionally complex problems . 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 . Second, encouraging transformers to generate reasoning steps explicitly within a single generation . For example, Nye et al. and Zhou et al. used scratchpads to teach transformers how to perform algorithmic reasoning tasks such as addition by splitting the task into intermediate steps . Further, leveraging LLMs to generate each reasoning step iteratively via a selection and inference mechanism . Lastly, choosing a training split that maximizes the number of observed patterns between the train and test data , or diversifying in-prompt examples to cover the maximum of patterns , ultimately enhancing generalization. The primary focus of these studies is to enhance model performance on compositional problems without striving for complete mastery. In 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.

Extensive research has been done to investigate the generalization capabilities of transformers . This encompasses various facets of generalization, including easy-to-hard generalization , length generalization , and generalization on symbolic mathematical integration . Schwarzschild et al. and Bansal et al. employ weight-tied neural networks to generalize from easy to hard examples. Liu et al., found that shallow transformers learn shortcuts during training, leading to poor OOD generalization. Razeghi et al. revealed a 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.

The phenomena of models’ gaining generalization capabilities when training significantly beyond overfitting, known as grokking was recently introduced in . Subsequent works focus on characterizing when and why grokking arises: 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 where a sparse subnetwork of neurons is shown responsible for generalization behavior. Recently, propose that grokking occurs when a task admits a generalizing and a 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.

Lin et al. study autoregressive models’ limitations from a 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, 14, 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 shows that transformers cannot robustly model noncounter-free 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 §E.

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 AI systems that excel not only in tasks where abundant training examples are sufficient, but also in cases requiring precise compositional reasoning.

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.

Acknowledgements

We thank members of the Mosaic team at AI2 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 DMS-2134012, DARPA MCS program through NIWC Pacific (N66001-19-2-4031), and the Allen Institute for AI.

References

Appendix A Compositional Tasks

We exhaustively generate multiplication problems as question-answer pairs (e.g., Q: “What is 4 times 32?” A: “128”). We focus on multiplications of two numbers $x=(x_{1},x_{2},\dots,x_{k})$ and $y=(y_{1},y_{2},\dots,y_{k})$ where each number can have up to $k$ digits, amounting to $9\times 10^{(k-1)}$ combinations per each number. We set $k$ to 5 in our experiments. Figure 8 showcases an example prompt for performing few-shot learning without the inclusion of a scratchpad, while Figure 9 demonstrates an example prompt using a 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 9 ultimately produced the most favorable outcomes. Listing 1 shows the Python code for solving the task.

A.2 Einstein’s Puzzle

In our experiments, we initially establish a 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 a red color.”). We then devise a fundamental and straightforward set of clue types: 1) ‘found_at’, e.g., “Alice lives in House 2”, 2) ‘same_house’, e.g., “The person who is a cat lover lives in the house that has a red color.”, 3) ‘direct_left’, e.g., “The person who has a dog as a 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, we also set up harder clue types such as ‘not_at’, ‘left_of’ (not necessarily directly left of), ‘two_house_between’, etc. which are only used in auxiliary experiments.

The solution to the puzzle is a matrix of size $K\times 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 to create the solution. It is 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 all valid clues based on the solution and subsequently remove redundant clues at random until we obtain a set with a unique solution, as previously sampled. This process ensures a coherent and engaging puzzle-solving experience. Refer to Figure 10 for an example.

To solve the complex compositional reasoning process for a logical grid puzzle, we use existing puzzle solvers to generate the computation graph. It follows the basic greedy principle of applying the minimum number of rules to solve any cell, i.e., if using only one rule to solve any given cell, then apply this rule. This algorithm iterates through all clues in the clue set until one or a set of clue combinations can solve any cell in the table. While it may not be the most efficient way to solve the puzzle, it provides models with explicit scratchpad verbalization through an intuitive computation graph. Refer to Figure 10 for the pseudo-code of the process, and Figure 11 for a scratchpad example.

A.3 Dynamic Programming Problem

Let $a=[a_{1},\ldots,a_{n}]$ be an input. Let $dp_{i}$ be the maximum sum of a subsequence that does not include adjacent elements, when considering only the elements of the input from the $i$-th position onwards.

Trivially, $dp_{n}=\max(a_{n},0)$ since we only want to choose a number if it is non-negative. Moreover, $dp_{n-1}=\max(a_{n},a_{n-1},0)$ since we cannot choose adjacent numbers.

For any given $dp_{i}$ with $i\leq n-2$, we can express it in terms of $dp_{i+1}$ and $dp_{i+2}$. Concretely, the maximum sum of a subsequence starting at position $i$ may or may not include the element in the $i$-th position, $a_{i}$. If the subsequence includes $a_{i}$, then the maximum sum is $a_{i}+dp_{i+2}$, since using $a_{i}$ blocks us from using the next element. If the subsequence does not include $a_{i}$, then its sum is $dp_{i+1}$. Moreover, the answer may never be less than zero, because otherwise we would select the empty sequenceWe don’t need to explicitly check for this since $dp_{n}\geq 0$. However, we include the condition to ease the scratchpad logic.. In summary,

We now have a recursion with its base cases $dp_{n}=\max(a_{n},0)$ and $dp_{n-1}=\max(a_{n},a_{n-1},0)$, and we can therefore compute all values in $O(n)$. It now only rests to reconstruct the lexicographically smallest subsequence that maximizes the desired sum, based solely on the computed $dp$ values.

Starting from $dp_{1}$ and iterating sequentially through $dp_{n-2}$, we choose an item if and only if $dp_{i}=a_{i}+dp_{i+2}$ (that is, the maximum sum comes from choosing the current element) and we have not chosen the previous element. This helps disambiguate cases where choosing or not choosing $a_{i}$ yields the same sum, but possibly only one of those will not incur in choosing adjacent numbers. Similarly, for positions $i=n-1$ and $i=n$ we choose the element if $dp_{i}=a_{i}$ (that is, choosing the element yields the maximum sum) and we have not chosen the immediately previous element. See an example Python solution in 2.

We exhaustively generate data for this DP task. For question-answer setting, we include a thorough explanation of the task before asking to generate a solution (see Figure 12). We use all lists up to 5 elements as training, and we consider only lists where elements are in the range $$(giving a total of$11^{n}$lists for an input list of size$n$). 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 12 respectively. The scratchpad is generated automatically through templates. We considered five exemplars for the few-shot setup.

Appendix B Experimental Setups & Empirical Results

For our experiments, we evaluate the performance of 6 LLMs: GPT4 (gpt-4) , ChatGPT (GPT3.5-turbo) , GPT3 (text-davinci-003) , FlanT5 and LLaMa . The evaluations were conducted from January 2023 to May 2023 using the OpenAI API. We perform fine-tuning on GPT3 (text-davinci-003) for the three tasks, observing faster convergence when training on question-scratchpad pairs rather than question-answer pairs. For question-answer pairs fine-tuning, we 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 question-scratchpad pairs, we 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 of examples in the training set. Generally, we observe that larger batch sizes tend to yield better results for larger datasets. For the learning rate multiplier, we 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, we set nucleus sampling $p$ to 0.7 and temperature to 1. For each task, we evaluate the performance of each model on 500 test examples.

B.2 Limits of Transformers in Zero- and Few-shot Settings

Figure 15, Figure 17 and Figure 20 show the zero-shot performance of GPT4, ChatGPT, LLaMA and FlanT5 on the three tasks. Overall, there is a notable decline in performance as the task complexity increases (measured by graph parallelism for multiplication and DP, and propagation steps for puzzles as shown in Figure14). The few-shot performance with question-answer pairs results in minimal improvement over the zero-shot setting as depicted in Figure 16 and Figure 20 for the multiplication and DP tasks. In contrast, the few-shot setting did not lead to any improvement in the puzzle task.

B.3 Limits of Transformers with question-answer Training

Figure 18 and Figure 21 show the performance of GPT3 finetuned on question-answer pairs. The model was trained on various splits, considering the problem size, depth, and width of the computation graph. Specifically, for the multiplication task, the model was fine-tuned on a range of multiplication problems, spanning from 1-digit by 1-digit multiplication to 4-digit by 2-digit multiplication amounting 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 a sequence length of 5 resulting in 41K pairs. In an additional setup, we divided those datasets based on the depth and width of the computation graph for all the tasks and finetuned on different splits. The results indicate a 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 is 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 is still low and GPT2-XL fails to answer correctly 3x3 test examples.

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-scratchpad pairs. The cost for utilizing the text-davinci-003 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 to$12 million and $700 million for question-scratchpad training. For a more comprehensive breakdown of the cost per problem size, please refer to Table 1.

B.4 Limits of Transformers with Explicit Scratchpad Training

Figure 23, 24, 22 show the performance of GPT3 finetuned on different splits of the tasks using question-scratchpad pairs. Specifically, for the multiplication task, the model was fine-tuned on a range of multiplication problems, spanning from 1-digit by 1-digit multiplication to 3-digit by 2-digit multiplication.

As for the puzzle task, the model was fine-tuned on puzzles of sizes ranging from 2x2 to 4x4. Additionally, for the DP task, the model was fine-tuned on problems with a sequence length of 5. Furthermore, different data splits were considered, including variations based on the number of hours, number of properties, 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.

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 question-scratchpad pairs of few-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.

Appendix C Surface Patterns

C.2 Empirical Surface Pattern Analysis for Multiplication with GPT4, ChatGPT and GPT3

C.3 Relative Information Gain Predictions for Dynamic Programming Task

Let $a_{i}$ be the $i$-th element of the input sequence, and let $o_{i}$ be the $i$-th element of the output sequence. As shown in Table 3, $a_{i}$ is a good predictor of $o_{i}$, and this is especially true for $a_{1}$ and $a_{n-1}$, the first and last elements of the sequence. This matches the task intuition, since one would never pick an element $a_{i}<0$ and decrease the final sum (one may pick $a_{i}=0$ if it makes a lexicographically smaller output sequence).

$a_{i}$ weakly helps to predict its neighbors. The only case of this behavior with RelativeIG>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 $a_{1}$ indicates that with high probability $o_{2}$ will not be selected for the final subsequence.

Similar behaviors, but with higher relative information gains overall, are observed when analyzing triples of consecutive elements in the list. Table 4 shows that $o_{i}$ is highly predicted by $(a_{i-1},a_{i},a_{i+1})$. Moreover, $o_{i}$ is highly predicted by both $(a_{i-2},a_{i-1},a_{i})$ and $(a_{i},a_{i+1},a_{i+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 a 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_{i-3},a_{i-2},a_{i-1})$ to predict $o_{i}$; whereas $(a_{i+1},a_{i+2},a_{i+3})$ is not shown, since all the relative information gain values were below 0.1.

C.4 Empirical Surface Pattern Results for Dynamic Programming Task

We observe that all analyzed models match the Relative Information Gain prediction that $o_{1}$ (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 $o_{n-1}$ is only done for GPT4. In GPT4, we observe that $o_{n-1}$ is among the easiest values to predict as expected by Relative Information Gain.

Appendix D Theoretical Results: Derivations

Here we provide formal statements and derivations to Propositions 4.1 and 4.2 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.

Let $f_{n}(\mathbf{x})=h_{n}(g(\mathbf{x},1),g(\mathbf{x},2)),\ldots,g(\mathbf{x},n))$. Let $\widehat{h}_{n},\widehat{g},\widehat{f}_{n}$ be estimators of $h_{n},g,f_{n}$ respectively. Assume $\mathds{P}(h_{n}=\widehat{h}_{n})=1$ and $\mathds{P}(h_{n}(X)=h_{n}(Y)\ |\ X\neq Y)<c_{n}$, where $c_{n}<c$ for some constant $c\ll 1$ (i.e. $\widehat{h}_{n}$ perfectly estimates $h_{n}$, and $h_{n}$ is almost injective). If $\mathds{P}(g\neq\widehat{g})=\epsilon>0$ and errors in $\widehat{g}$ are independent, $\displaystyle\liminf_{n\rightarrow+\infty}\mathds{P}(f_{n}\neq\widehat{f}_{n})\geq 1-c$.

Moreover, if $c_{n}\leq\beta\alpha^{n}$ for some some $\alpha\in(0,1)$ and $\beta>0$, then $\displaystyle\lim_{n\rightarrow+\infty}\mathds{P}(f_{n}\neq\widehat{f}_{n})=1$.

For ease of writing, let $X_{i}=g(X,i)$ and $Y_{i}=\widehat{g}(X,i)$, and let $\boldsymbol{X}=(X_{1},\ldots,X_{n})$ and $\boldsymbol{Y}=(Y_{1},\ldots,Y_{n})$. We will compute some auxiliary probabilities, and then upper bound $\mathds{P}(f=\widehat{f})$, to finally compute its limit.

Since by hypothesis we know $\mathds{P}(h_{n}(\boldsymbol{Y})=\widehat{h}_{n}(\boldsymbol{Y}))=1$, we have that:

We will now estimate $\mathds{P}(f_{n}=\widehat{f}_{n})$ using the law of total probability w.r.t. the event $\boldsymbol{X}=\boldsymbol{Y}$.

To conclude our proof, we will compute a lower bound for $\liminf_{n\rightarrow+\infty}\mathds{P}(f_{n}\neq\widehat{f}_{n})$. Note that since $c_{n}<c$ for all $n$, we know that $\mathds{P}(f_{n}=\widehat{f}_{n})<c+(1-\epsilon)^{n}\cdot(1-c)$. Then, $\mathds{P}(f_{n}~{}\neq~{}\widehat{f}_{n})>1-c-(1-\epsilon)^{n}\cdot(1-c)$. Since $1-\epsilon\in[0,1)$, $\displaystyle\lim_{n\rightarrow+\infty}1-c-(1-\epsilon)^{n}\cdot(1-c)=1-c$. Thus,

Note: In the case where $c_{n}\leq\beta\alpha^{n}$, we can derive an even stronger conclusion. In this case, we can prove that $\displaystyle\lim_{n\rightarrow+\infty}\mathds{P}(f_{n}=\widehat{f}_{n})=1$. Recall that $\mathds{P}(f_{n}=\widehat{f}_{n})<\alpha\beta^{n}+(1-\epsilon)^{n}\cdot(1-\alpha\beta^{n})$. Note that since $1-\epsilon\in[0,1)$ and $\alpha\in(0,1)$, trivially $\displaystyle\lim_{n\rightarrow+\infty}\beta\alpha^{n}+(1-\epsilon)^{n}\cdot(1-\beta\alpha^{n})=0$.

Then, $\lim_{n\rightarrow+\infty}\mathds{P}(f_{n}=\widehat{f}_{n})=0$ and we conclude $\lim_{n\rightarrow+\infty}\mathds{P}(f_{n}\neq\widehat{f}_{n})=1$, assuming that $c_{n}\leq\beta\alpha^{n}$ for some adequate $\alpha,\beta$. ∎

Assume that a model $\mathcal{M}$ solves shifted addition perfectly, but it incorrectly solves at least one $m$ digit by 1 digit multiplication for some fixed $m$. Then, the probability that $\mathcal{M}$ will solve any $m$ digit by $n$ digit multiplication using the long-form multiplication algorithm tends to 0 when $n$ tends to infinity.

By hypothesis, $\mathds{P}(g\neq\widehat{g})=\epsilon>0$ and $\mathds{P}(h_{n}=\widehat{h}_{n})=1$, where $\widehat{g}$ and $\widehat{h}_{n}$ denote estimators using model $\mathcal{M}$. It can be shown that $\mathds{P}(h_{n}(X)=h_{n}(Y)\ |\ X\neq Y)<\beta\alpha^{n}$ for $\alpha=0.1$ and $\beta=10^{m}$. Using Lemma D.1, $\displaystyle\lim_{n\rightarrow+\infty}\mathds{P}(f_{n}\neq\widehat{f}_{n})=1$, which concludes our proof.

Note that Lemma D.1’s proofs gives us empirical bounds once $\epsilon$ and $\alpha$ are approximated. Also note that our definition of $g$ in the proof of Corollary D.1 highlights two possible sources of exponentially-accumulating error: errors in the selection of the numbers to multiply $s$, 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)

Let $f_{n}(\mathbf{x})=g^{n}(\mathbf{x})$. Assume $\mathds{P}(g(X)=\widehat{g}(Y)\ |\ X\neq Y)\leq c$ (i.e. recovering from a mistake due to the randomness of applying the estimator on an incorrect input has probability at most $c$). If $\mathds{P}(g\neq\widehat{g})=\epsilon>0$ with $c+\epsilon<1$, then $\displaystyle\liminf_{n\rightarrow+\infty}\mathds{P}(f_{n}\neq\widehat{f}_{n})\geq 1-c/(c+\epsilon)$.

We first derive a recursive upper bound using the law of total probability, and then prove a non-recursive upper bound by induction.

We know $s_{1}=(1-\epsilon)$ since $s_{1}=\mathds{P}(f_{1}=\widehat{f}_{1})=\mathds{P}(g=\widehat{g})$. Let $b:=1-\epsilon-c$ for ease of writing. Then, we have

It can be easily shown by induction that $s_{n}\leq b^{n-1}(1-\epsilon)+c\sum_{i=0}^{n-2}b^{i}$:

The base case $n=2$ is true since we know $s_{2}\leq b\cdot s_{1}+c$, and $b\cdot s_{1}+c=b(1-\epsilon)+c=b^{2-1}(1-\epsilon)+c\sum_{i=0}^{2-2}b^{i}$, thus showing $s_{2}\leq b^{2-1}(1-\epsilon)+c\sum_{i=0}^{2-2}b^{i}$

The inductive step yields directly using Equation 4,

We can rewrite the geometric series $\sum_{i=0}^{n-2}b^{i}$ in its closed form $\frac{1-b^{n-1}}{1-b}$, and recalling $b:=1-\epsilon-c$,

Recalling that $s_{n}=\mathds{P}(f_{n}=\widehat{f}_{n})$, we compute the limit inferior of $\mathds{P}(f_{n}\neq\widehat{f}_{n})=1-s_{n}\geq 1-b^{n-1}(1-\epsilon-\frac{c}{c+\epsilon})-\frac{c}{c+\epsilon}$.

We can generalize the proof in Lemma 4.2 to tasks where there are potentially many valid reasoning chains with the following alternative state-transition framing.

Let $S$ denote the set of all possible states a language model can generate, and let $z:S\rightarrow\{0,1\}$ defines if a state is valid (0 = invalid). Let $\widehat{g}:S\rightarrow\Pi(S)$ be a state-transition function representing a language model’s probability distribution of generating each possible next state when attempting to perform a single reasoning step. Assume $\mathds{P}(z(\widehat{g}(X))=1\ |\ z(X)=0)\leq c$ and $\mathds{P}(z(\widehat{g}(X))=0\ |\ z(X)=1)=\epsilon>0$ with $c+\epsilon<1$. Then, $\displaystyle\liminf_{n\rightarrow+\infty}\mathds{P}(z(\widehat{g}^{n})=0)=1-c/(c+\epsilon)$.

If for task $T$ we know that all valid reasoning chains to arrive at a correct result have at least length $n$ (i.e., the equivalent of defining $f_{n}=g^{n}$ in Lemma D.1) then the probability of solving task $T$ correctly tends to at most $c/(c+\epsilon)$.

The recursions for dynamic programming tasks, the $m$-by-$1$ digit multiplication, and the puzzle’s elimination function are all tasks where there is a fixed reasoning step $g$ being repeatedly applied. Therefore, we can directly apply Proposition 4.2 to these tasks.

Let’s analyze the three tasks separately below.

Let $x=(x_{1},\ldots,x_{m})$ be the $m$-digit number that we multiply by the 1-digit number $y$ ($0\leq y<10$). Let $z=(z_{1},\ldots,z_{m+1})$ denote $z=x\cdot y$, which is guaranteed to have exactly $m+1$ digits (with possibly leading zeros). We define $f$ as:

where $x_{i}^{\prime}:=(x_{i}\cdot y+c)\mod 10$ and $c^{\prime}:=\lfloor(x_{i}\cdot y+c)/10\rfloor$. Note that $x_{i}^{\prime}=z_{i+1}$ since $f$ is performing one step of the long-form multiplication algorithm.

Let the initial input be $\mathbf{x}:=(x_{1},\ldots,x_{m},y,m,0)$. Then, it can be easily shown that $f^{m}(\mathbf{x})~{}=~{}(z_{2},\ldots,z_{m+1},y,0,c)$. Since $c$ is the left-most carry, it is the leading digit of $z$, i.e. $c=z_{1}$ (possibly zero) . Thus, the value of $z$ can be directly extracted from $f^{m}(\mathbf{x})~{}=~{}(z_{2},\ldots,z_{m+1},y,0,z_{1})$.

See §A.3.1 for details on the solution to this problem. We will use identical notation. Let $a_{1},\ldots,a_{m}$ be an input list. Let $\mathbf{x}=(a_{1},\ldots,a_{m-2},a_{m-1}^{\prime},a_{m}^{\prime},m-2)$, where $a_{m}^{\prime}:=\max(a_{m},0)$ and $a_{m-1}^{\prime}:=\max(a_{m-1},a_{m},0)$. Intuitively, this means that we have applied the first two steps of the $dp$ computation, and stored the results in $a_{m-1}^{\prime}$ and $a_{m}^{\prime}$. Let $f$ be a function representing the recursive computation of $dp_{i}$:

where $a_{i}^{\prime}:=\max(a_{i+1}^{\prime},a_{i}+a_{i+2}^{\prime},0)$.

Note that since $a_{i+1}^{\prime}$ stores the value of $dp_{i+1}$ and $a_{i+2}^{\prime}$ stores the value of $dp_{i+2}$, it can be easily shown that $f^{m-2}(\mathbf{x})=(a_{1}^{\prime},\ldots,a_{m}^{\prime},0)=(dp_{1},\ldots,dp_{m},0)$. Therefore, $f^{m-2}$ computes all recursive values of $dp_{i}$ when given the base cases.

This case is similar to the previous one. Let $r=(r_{1},\ldots,r_{m})$ be the result, where $r_{i}=1$ if $a_{i}$ was selected for the desired subsequence, and $r_{i}=2$ otherwise. Let $\mathbf{x}:=(dp_{1},\ldots,dp_{m},0,0,a_{1},\ldots,a_{m},1,1)$. Let $f$ be defined as follows:

where $a_{i}^{\prime}:=2-\mathds{1}\{dp_{i}=a_{i}+dp_{i+2}\text{ and }u=1\}$ and $u:=1-\mathds{1}\{dp_{i}=a_{i}+dp_{i+2}\text{ and }u=1\}$. Intuitively, $a_{i}^{\prime}$ stores whether the $i$-th element of the list should be selected for the final subsequence, assigning 1 if the element should be taken, and 2 otherwise (i.e., $a_{i}^{\prime}=r_{i}$). Moreover, if the $i$-th element has been selected, we mark that the next item will not be available using $u^{\prime}$. Therefore, $f$ performs one step of the final output reconstruction as defined in §A.3.1.

It can be easily shown that $f^{m}(\mathbf{x}):=(dp_{1},\ldots,dp_{m},0,0,a_{1}^{\prime},\ldots,a_{m}^{\prime},m+1,u^{\prime})=(dp_{1},\ldots,dp_{m},0,0,r_{1},\ldots,r_{m},m+1,u^{\prime})$. Note that the extra two elements in the input state allow lifting the special cases $m-1$ and $m$ in the solution shown in §A.3.1 without falling out of bounds.

Let $c_{1},\ldots,c_{n}$ be the list of clues, let $H$ be the number of houses, and let $A$ be a partially filled solution of size $K\times M$ as defined in §2.4. Each cell $A_{ij}$ can take $H+1$ values: the $H$ options for the cell and the value ø, implying this cell has not been filled. An elimination step $f$ may be defined as:

where $A^{\prime}$ is also a partially filled matrix, with $A_{ij}=A^{\prime}_{ij}$ for every $A_{ij}\neq$ø and where $A^{\prime}$ has at least one more filled cell.

Let $\mathbf{x}=(c_{1},\ldots,c_{n},E)$ where $E$ is an empty matrix of size $K\times M$ (all cell values of $E$ are ø).

Then, a full solution is computed as $f^{m}(\textbf{x})$ for some value of $m$ 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 c≪ϵmuch-less-than𝑐italic-ϵc\ll\epsilon in the context of Proposition 4.2

Note that in Proposition 4.2, if $c\!\ll\!\epsilon$ then $\displaystyle\liminf_{n\rightarrow+\infty}\mathds{P}(f_{n}~{}\neq~{}\widehat{f}_{n})\approx 1$. This is because assuming $\epsilon=m\cdot c$ for some $m>0$, we have $1-\frac{c}{c+\epsilon}=1-\frac{c}{c+m\cdot c}=1-\frac{1}{m+1}=\frac{m}{m+1}$, and $\frac{m}{m+1}$ is a monotonically increasing function for all $m>0$ that tends to $1$ when $m$ goes to infinity. Therefore, large $m$’s (or alternatively, $c\ll\epsilon$) imply $\frac{m}{m+1}$ will be close to 1.

It is reasonable to assume $c\!\ll\!\epsilon$ when $g$ has low collision, since $c$ represents the probability of the estimator $\widehat{g}(y)$ arriving at the correct output $g(x)$ by chance when given the wrong input $y\neq x$.

If $g$ is discrete, it can take $|\text{Im}(g)|$ values, where $|\text{Im}(g)|$ denotes the cardinal of the image space of $g$. Assuming approximately uniform errors, $c\approx\epsilon/|\text{Im}(g)|$, which in turn implies $c\ll\epsilon$ since $g$ being low collision implies $|\text{Im}(g)|$ is large.

If $g$ is continuous, under appropriate assumptions it seems plausible that we can prove that $c\approx 0$ (e.g. if errors are approximately uniform).

Summarizing both cases, if errors are approximately evenly distributed we obtain that $\displaystyle\liminf_{n\rightarrow+\infty}\mathds{P}(f_{n}~{}\neq~{}\widehat{f}_{n})\approx 1$.

Appendix E Additional Literature and Societal Impact

The process of repeatedly applying a noisy single operation or function $f$ can be related to iterated random functions . In this latter literature, the focus is usually on the contractive regime in which accrued errors can be kept under control, and the subsequent convergence guarantees (e.g., ). When $f$ is an affine transformation, the process falls simultaneously between two perspectives: time series and dynamic programming and control . We leverage the former to discuss the often explosive errors of $f^{n}$.

E.2 Societal Impact Discussion

Our work on analyzing the limitations of current transformers in compositional tasks can have a positive societal impact in several ways. By shedding light on these limitations, we contribute to a deeper understanding of the capabilities and constraints of these models. This knowledge is 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 AI 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 new model or dataset that future work may leverage.