How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad
Authors: Emmanuel Abbe
Samy Bengio
Aryo Lotfi
Colin Sandon
Omid Saremi
Venue: NeurIPS 2024 poster (2024)
Keywords: Transformer
reasoning
scratchpad
length generalization
Primary area: learning_theory

Abstract: Can Transformers predict new syllogisms by composing established ones? More generally, what type of targets can be learned by such models from scratch? Recent works show that Transformers can be Turing-complete in terms of expressivity, but this does not address the learnability objective. This paper puts forward the notion of 'globality degree' of a target distribution to capture when weak learning is efficiently achievable by regular Transformers. This measure shows a contrast with the expressivity results of Transformers captured by $TC^0/TC^1$ classes (further studied here), since the globality relates to correlations with the more limited $NC^0$ class. We show here experimentally and theoretically under additional assumptions that distributions with high globality cannot be learned efficiently. In particular, syllogisms cannot be composed on long chains.  Further, we develop scratchpad techniques and show that: (i) agnostic scratchpads cannot break the globality barrier, (ii) educated scratchpads can break the globality with intermediate steps, although not all such scratchpads can generalize out-of-distribution (OOD), (iii) a notion of 'inductive scratchpad', that composes the prior information more efficiently, can both break the globality barrier and improve the OOD generalization. In particular, some of our inductive scratchpads can achieve length generalizations of up to $6\times$ for some arithmetic tasks depending on the input formatting.

How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad
Emmanuel l.b Samy Bengio , Aryo Lotfi', Colin Sandon', Omid Saremi! Apple
2EPFL
Abstract
Can Transformers predict new syllogisms by composing established ones? More generally, what type of targets can be learned by such models from scratch? Recent works show that Transformers can be Turing-complcte in terms of expressivity, but this does not address the learnability objective. This paper puts forward the notion of globality degree of a target distribution to capture when weak learning is efficiently achievable by regular Transformers. This measure shows a contrast with the expressivity results of Transformers captured by TC /TC' classes (further studied here), since the globality relates to correlations with the more limited NC class. We show here experimentally and theoretically under additional assumptions particular, that distributions with high globality cannot be learned efficiently. syllogisms cannot be composed on long chains. Further, we develop scratchpad techniques and show that: (i) agnostic scratchpads cannot break the globality barrier, (ii) educated scratchpads can break the globality with intermediate steps, although not all such scratchpads can generalize out-of-distribution (OOD), (iii) a notion efficiently, both break the globality barrier and improve the OOD generalization. In particular, some of our inductive scratchpads can achieve length generalizations of up to 6 for some arithmetic tasks depending on the input formatting.
'inductive seratchpad', that composes the prior information
Introduction
Transformers [1] have proved to have strong learning capabilities, in particular in applications with large amounts of text, image, or audio data [2, 3]. Some reasoning capabilities are also notable in these settings, however, the picture deteriorates when the target complexity increases, such in tasks involving more advanced forms of 'reasoning' [4, 5, 6, 7, 8, 9, 10]. While reasoning is present at all levels of learning, it is pushed to a higher level in tasks such logic or mathematies, where 'learning by seeing enough representative examples' is precluded by the more combinatorial nature of the task. For such tasks, combining learned concepts in order extrapolate seems necessary, as for the length generalization problem [11]. Current Transformer baassorrmrr-baedd models exhibit difficulties learning at scale on such tasks. Can we understand why and what is missing? We start with specific motivational example before expanding the discussion to more general tasks.
1.1 Syllogisms composition
Reasoning relates to the process of inferring new knowledge by composing efficiently some prior knowledge. A basic notion of reasoning syllogism composition, e.g., inferring c from = b and > For instance, one may be given a set of implications:
task has priority over task 2 task has priority over task 3 task has priority over task 1 task has priority over task
x x>2
+
x² +>
x>2
2
4
(x-1)(2+1)
4
> 17
2>2
x>
2
F
>
1-
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

100000
Model sice
10M
80000
Rorations to losm
BSM
40000
20000
Class two disjoint eycles length
Class cycle length
5
Size of problem
(a) Cycle task: binary classification to predict whether
(b) Nb. of iterations with 512 fresh samples to learn
two vertices (the red squares) connected not the above two graph topologies.
(2 95% acc.) the cycle task of size a using GPT2-
style models with 10M, 25M, 85M parameters.
Figure 1: Illustration of the cycle task for 4 (left) and the complexity to learn it (right).
and without additional background information, one would like to know using logic whether
task 3 has priority over task 5?
4"
17
3.
The goal here is to identify whether a syllogism can be composed' by prior ones. Simplifying the input format, the above correspond to identifying paths in token sequences describing the directed edges of an underlying graph, i.e., whether there is a directed path 3 + (case 1) or 4 + 2 (case 2) using the directed edges {(1 - 2), (1 3). (4 + 1). (1 5)}.
This type of task is nontrivial for current LLMs, and we refer to Appendix for experiments with not interested specifically in solving graph-based task, but
GPT models.? Note that here rather in understanding when Transformers can compose and more generally how far they can do so. We would like to identify particular measures on the data distribution (e.g., syllogisms topologies in the above example) that capture when Transformers can efficiently learn.
1.2 Hardness of long compositions
Consider the previous syllogism composition task where implications are drawn on a graph with 24 edges drawn randomly over 24 vertices. Picking vertices at distances to for the connected case and picking disconnected vertices uniformly at random lets Transformer achieve a test accuracy of more than 80% after about 2000 iterations. However, does this mean that the model has learned to compose syllogisms, has it found shortcuts, c.g., based on node degrees, to guess the implications often enough? In Appendix B.I, we provide empirical evidence supporting the latter. Motivated by this issue and to preclude spurious correlations, we consider the following distribution.
Definition 1 (Cycle task). For n 2 1, consider the binary classification task with equiprobable classes defined by
1. Class I: a graph uniformly drawn on 2n vertices with two disjoint cycles of length v. and pair of vertices in disjoint cycles queried for puth;
2. Class 2: graph uniformly drawn 2n vertices with cycle of length 2n and a pair of vertices at distance n queried for path.
The imput of this task is the graph edge set with the queried vertices. The label is O if the two queried vertices are not connected (Class and if they are (Class 2). See Figure la for an illustration.
Figure 1b shows that the learning complexity increases 'exponentially" as n grows using GPT2-style Transformers of more than 10M, 25M, 85M parameters; e.g., the 10M model fails learn for in 100k iterations. Why is that? Can a larger scale further help here?
Can large (poly-size) Transformer learn the cycle task when gets large? If not, why so?
A challenge for the cycle task is that there is clear 'low-complexity pattern' in the input representa- tion that indicates whether there are or 2 cycles. No simple statistics based on degrees, edge counts,
AAsswrring 'yes/1' the syllogism can obtained by composing input ones or 'cannot tell/0' otherwise. At the time of the experiments, ChatGPT was in particular not successful at these two tasks.

---

or finite motif counts that can tell if the vertices are connected or not. One has to consider at least n edges in order to get any correlation with the presence of path. In other words, the task requires a "global reasoning" involving a 'large' number of input tokens and this seems hard for Transformers.
1.3 Hardness of global reasoning
As discussed, the cycle task appears to be challenging for Transformers as requires some global reasoning. Other tasks such as subset parities exhibit the same challenge. However the latter can be proved to be not efficiently learnable by various regular neural networks and noisy gradient descent, as one can get explicitly class of functions (through orbit arguments [12, 13]) that has large statistical dimension [14] or low cross-predictability [12. 15] (see Appendix A.4). For the cycle task, we have single distribution, and it is unclear how to use the invariances of Transformers to get arguments as in [12, 13], as the input distribution is not invariant under the symmetries of the model. We thus would like to develop more general complexity measure that unifies why such tasks are hard for Transformer-like models and that formalizes the notion of "global reasoning barrier' when models are trained from scratch. We also would like to understand how the scratchpad methodologies that have proved helpful in various settings (see Section 3) can help here. This raises the questions:
(I) How can we formalize the "global reasoning barrier' in general terms? (2) Can we break the "global reasoning barrier' with scratchpad methodologies?
1.4 Our contributions
We provide the following contributions:
We introduce the notion of globality degree in Definition 2 to capture when weak learning is efficiently achievable by Transformers. The globality degree measures the least number of tokens required in addition to the token histogram to correlate nontrivially with the target; it is also related in Lemma 6 to correlations with NC circuits, showing the contrast between learnability and expressivity controlled by TC /CC/TT' with constant/logaritnnic depth [16]. It is an explicit measure that applies to data distribution without requiring orbit argument to infer a class of distributions [12, 13], giving a tight proxy for models like Transformers. We provide the following results based on the globality degree:
A general conjecture (Conjecture 1), backed by experimental results, that claims efficient weak learning is achievable by a regular Transformer if and only if the globality degree is constant.
Theorem that proves the negative side of the above conjecture, the globality barrier, in an instance of the cycle task under certain technical assumptions. (The cycle task is also put forward in the paper as a simple benchmark to test the global reasoning capabilities of models.)
We then switch to the use of 'scratchpads' to help with the globality barrier:
Agnostic scratchpad: we extend Theorem 1 to cases where a poly-size scratchpad is used by the Transformers, without any direct supervision of the scratchpad (i.e., the scratchpad mainly provides additional memory/compute). This shows that efficient weak learning is still not possible with such an agnostic scratchpad if the globality is non-constant. An educated guess about what to learn in the scratchpad based on some target knowledge is thus required.
Educated scratchpad: we generalize the measure of globality to the 'autoregressive globality' to quantify when educated scratchpad is able to break the globality of task with subtasks of lower globality. We give experimental results showing that educated scratchpads with constant autoregressive globality allow Transformers to efficiently learn tasks that may originally have high globality. This gives a way to measure how useful a scratchpad can be to break a target into easier sub-targets.
We introduce the notion of inductive scratchpad, a type of educated scratchpad that exploits 'induction' compared to a fully educated scratchpad and thus composes more efficiently the prior state information. We show that when the target admits an inductive decomposition, such as for the cycle, arithmetic, or parity tasks, the inductive scratchpad both breaks the globality and improves the OOD generalization in contrast to fully educated scratchpads. This gives significant length generalization on additions (from 10 to 18 or from 4 to 26 depending on the method) and parities (from 30 to 50-55). For instance, using different methods, [17] can length generalize from 10 to 12 digits for additions, and [11] can get roughly 10 extra bits for parities.
3

---

2 Results on the global reasoning barrier
Prior literature. Much work in the literature has been devoted to complexity measures for the sample/time complexity of learning. The largest portion is devoted to target classes in PAC settings, e.g., with the VC dimension measures [18], and some to statistical query (SQ) settings with the statistical dimension measures [14, 19I. Here, we are however interested in measures that are relevant to (1) regular Transformers trained by (S)GD, and (2) data distribution fixed by a task. Some recent neural networks. Various settings and measures have been used, such as the noise sensitivity [20, 6, 21]. the cross- pross-predcctabiiity [12, 15], the NTK alignment [22, 23), the INAL [24], the G-alignment [13], the information and generative exponents [25, 26, 27] and the leap [28]: we refer to Appendix A.4 for discussions on these.
works have studied complexity measures for (S)GD-traine
However, despite this significant body of work, finding simple measure giving tight proxy for Transformer weak learning (i.e., the first non-trivial learning requirement) on given data distribution, remains unsettled. We next propose such measure.
2.1 Defining globality and auto-regressive globality
We define now the notion of globality degree, which in turn will quantify the notion of globality (or global reasoning) barrier.
Definition 2. (Globality degree) For (a sequence of) distributions D on A x A, where A is finite alphabel set of poly(n) (n)-cr))inaaityy define the globality degree of D, glob(D), as the smallest number of variables k E [n] for which there exists S, |S| ====00 such that
T(X(S),Px:)
-001)
where (X2Y) D and Px is the empirical measure of X (i.e., the histogram of tokens in X). Remark 1. The globality degree, or simply globality, of a distribution measures the least number of input tokens to attend to order to correlate non-trivially with the label when also given the histogram of tokens. The specific choice of the mutual information is not crucial, but one must use proper measure of dependency (i.e., not just linear correlations). and the mutual information can have convenient chain rule properties. The definition can be related to correlations with N C circuits (besides for the histogram requirement, see Lemma 6) and also to low- low-degree polynomial testing, except that it is more general than the latter as it applies to arbitrary token space (without requiring polynomial definitions). Finally, we require the globality achieve an inverse-polye polysssmol mutual information, the weakest form relevant to weak learning with inverse-pols polyyommll edge, but one may naturally define the stronger notion with a mutual information of ((1))
We now define the globality in the autoregressive setting.
Definition 3. (Globality degree in autoregressive setting) For D on A x A define glob(D) as the smallest integer for which there exist sets of indices Si...., Sm. Se < k for all t E [m], such that
Px,xe. Yi) -(1)
where (X,Y) ~ D and Px,Ye, is the empirical measure of (X, Yee).
In the auto-regressive setting, the globality is mostly relevant when weak learning gives strong learning, in order to let the scratchpad learn each step.
As we will see in the next section, the globality degree is put forward as a tight proxy to understand efficient weak learning of regular Transformers for arbitrary data distributions. We first present the operational advantages of the definition, going back to the running example of the cycle task.
Attributes of glob and some examples. The globality has the attributes of being (i) a fairly explicit measure, (ii) applicable to any data distribution on tokens without having to infer a distribution class from the model invariances to estimate the distribution complexity, (iii) not limited to i.i.d. inputs but any input distribution, (iv) relevant to current models of interest such as Transformers.
In particular, back to the cycle task, we have that any set of n. edges have the same distribution in Class 1 or 2, therefore the globality is at least ne
Lemma 1. We have glob
globeCycle Cycle task(n:) n.

---

As discussed in the next section, this explains why the cycle task is hard to learn. In contrast, the example at the beginning of Section 1.2 has a much lower globality, as being connected correlates to query nodes having large enough degrees, and thus it can be expected for the model to learn with non-trivial accuracy (e.g., by using degree shorteuts).
2.2 Transformers require low globality: formal results
Definition 4. A neural network of input dimension nt (t.e., directed acyclic graph with n inputs) and depth d (i.e., the longest path length from input to output) is
1. T-regular if it is Transformer (e.g.. [1, 29]) of polynomial size with Normal Gaussian i.i.d. positional embeddings, Normal Gaussian i.i.d. weights, and bidirectional attention.
2. T-regular with s- s-scratchpad if we have a constant sized token alphabet E and a T-regular Transformer that takes an m-sequence in E and outputs probability mass function on E (with well-behaved softmax). To compute the value of this nel and scratchpad on an input X E En we set X,, = X and then for each m E (n....,.. + 8 11 draw Fmn-1 from the probability distribution represented by the net's 's value on Xm. and set X x = Xm Fm++1 (concatenation). Then, we consider In-s to be the overall output of the net.*
Remark 2. In this paper, we focus on learnability via descent algorithms, but for the simpler question of expressivity, one wants to know whether there is any choice of parameters for which a Transformer can compute target function (with limits to how precisely it can record values).
(i) In [16]. the expressivity of Transformers with constant alphabet size and values recorded to inverse-polynone
accuracy is investigated. It is shown that such Transformer of constant depth was limited to computing functions in TC Conversely, it also showed that for any TC function, there is constant-deptl Transformer and instruction string such that when the Transformer is given the instruction string and x as its input it computes the function on x. The same technique would extend to show that with logarithmic depth, one can reach TC (which includes connectivity tasks). (ūi) In [30], well-behaved Transformers with a scratchpad are considered. It is shown that a Transformer with scratchpad of logarithmic length is limited to computinng functions in logspace. We tighten this to TC in Lemma 5 in Appendix H. On the other hand, [30] also shows that any function in P is computable by a Transformer with scratchpad of polynomial length.
(iii) If we allow Transformers poly depth then we can convert any poly-sized circuit to a Transformer by replacing each gate the circuit with an attention head that attends to the values of the appropriate input tokens or attention heads and performs the appropriate computation on them. That means any function in P (including the cycle task) is computable by Transformer of poly depth and size.
We now state the general conjecture putting forward the globality barrier for learning.
Conjecture 1. A distribution Px.Y with well-behaved Px is efficiently weakly" learnable by a T-regular Transformer if and only if Px, has constant globulity.
Remark 3. (1) An essential property of the model for the above conjecture is that the probability distribution of the function computed by the model is invariant under permutations of the inputs, and if it is trained reasonably on samples drawn from a distribution drawn from a class that is symmetric under permutations of the inputs, its distribution will retain its symmetry under permutations of the inputs. For MLPs, we expect most of the results in this paper to apply. with the modification of
'Le. there exists e such that for any two vectors u and v' the total variation distance between the softmax's 's probability distributions on these vectors is at most cllu - u/112. Note that this does still allow a softmax which returns a specific value with probability 1 some vectors.
* "Normally when using a scratchpad we would use causal masking to make it so that we do not need to recalculate previous entries of lists in the Transformer whenever new entry is added to the scratchpad. We use this one for simplicity, but still expect all conjectures involving scratchpad to hold when apply causal masking to the scratchpad, and Theorem 2 and its proof unchanged.
*They assumed constant alphabet size, inverse-polynomial accuracy, constant depth, causal masking, averaging hard attention, and projected pre-norm. We suspect that all of these requirements other than the constant alphabet size and constant depth could be dropped without changing the results we state here.
"Conditions such as assuming that there is no value of X that is frequent enough that the model weakly learns the function simply by memorizing the value of that input. Most distributions of interest are well-bebaved (including the cycle task). See Definition 6 in Appendix D for formal definition and additional discussion.
2 Le.., with an accuracy that improves on the trivial accuracy by at least n -c for a constant c.
More specifically, for the converse statement (learning due constant globality) assume that |A| is constant.
5

---

0_0
c_1
6_3
4_2
0_2
e_3
Figure 2: The cycle task variant used in Theorem the above example is stored as a_00b_1;b_00e 12t________________ 12 2ib 2;e_ 2b._,,,,,.bb...., 3i______2____5 3ra_ 0ib_0 3rt.__rr_0aa.000000.
the globality not having access to the empirical measure of X. since one has additional symmetry obtained by exchanging tokens. (2) If we were to use causal masking or a specific choice of positional embeddings that would make it easier for the Transformer to focus specific relevant subsets of the inputs, one could potentially learn functions with higher globality. For instance, we would expect to be unable to learn function thut computes the parity of some subset of log(n) input bits. However, if we had a positional embedding that gave one value for all of the active bits and mapped other bits to O, then the Transformer would probably be able learn the function in question. Likewise, causal masking makes it so that the first few elements of any list the Transformer computes depend only on the first few tokens, which makes it easier to learn functions that would rely on those symbols.
We prove the negative side of Conjecture 1 for variant of the cycle task.
Theorem 1. Let G be a directed graph which consists of a cycle of length 3n with probability 2/3 and 3 cycles of length otherwise. Nexi, if there 3 cycles pick one verlex from each and if there is one cycle pick vertices that are each n. edges apart. Then, label these vertices with o_0, b_0, c_0 uniformly random. Next, number every other vertex by the distance from one of these three to and for each i, label uniformly at random the verfices at distance i by o_i, b_i, and c_i. Finally, store and d_i,b_i, b_i,c, c_i in X (as described in Figure 2), and
the edges between a_i L, b,c
let Y report whether a a_0, 6_0_ O, c_0 are in the same cycle or not. Then if we train T-regular neural network on (X, Y) generated in this manner using population' gradient descent with polynomial hyperparameters" 16 and a differentiable loss function then the network fails to weakly learn.
The proof of Theorem is presented in Appendix F.
2.3 Agnostic seratchpads cannot break the globality
Next, we put forward conjecture that agnostic scratchpads (scratchpads without direct supervision on the scratchpad tokens) cannot break the globality barrier. See Appendix for further discussion.
Conjecture 2. Consider training T -rregular net with s-scratchpad to learn Px,y sized alphabet by means of the following SGD algorithm. At each timestep. we draw a random sample (X, Y) and compute a value for the net with scratchpad for each S s and each a + Sú, define an alternative scratchpad by setting the first - 1 entries of this scratchpad equal those of S, setting its i-th entry to a, and using the net compute the rest of its values. Then, regard the loss associated with setting the ith entry of the scratchpad to a as the loss resulting from the associated scratchpad, and use the resulting gradient to carry out one step of SGD. Then if Px is well-behaved probability distribution, Px, is efficiently weakly learnable by T-regular neural network with scratchpad if and only if Px,y has constant globality.
constant-
X. Let S be the resulting scratchpad and
natural counterpart of Theorem 1 holds for the previous conjecture (see Theorem 2). In order to define the Transformer's loss on any given input it takes the expectation over every possible value of the scratchpad might generate, and its proof essentially identical to that of Theorem
TTiis would also be true for batch GD with batches of size n", dependent on the other hyperparameters. Le... either polynomial learning rate, polynomial clipping [12, 31], and weights stored using logarithmic number of bits of precision and random rounding: for a < < e 6 needs to be rounded to a or then it rounds to e with probability (b- a)/ (c a). or with polynomial learning rate, polynomial clipping and polynomial noise added to the gradients.

---

Y=Y
min |S]: < 1(X, Y.21 Pxr. 15)
Figure 3: An illustration showing how scratchpads break the globality. The target may be efficiently learned if each scratchpad step is of low globality given the previous ones.
3 Scratchpads to break the globality
Prior literature. has been shown that training Transformers with the intermediate steps required to solve a problem can enhance learning. This idea is usually referred to as providing models with a scratchpad [32]. The improved performance due scratchpads has been reported on variety of tasks including mathematical tasks and programming state evaluation [32, 11, 17]. See Appendix A for further references.
3.1 Educated scratchpad
We now provide a quantitative understanding of how the scratchpad can help with the notion of globality the autoregressive setting (Definition 3). Assume that we want learn target Y E .A from input X E A" such that (X, Y) ~ D and glob(D) is high. If one can design intermediate targets Yi..... Y&
such that Y = Y and the sequence (X.Y Ye.) + Yú has low globality according to Definition 3, then one can expect to learn each step of the sequence efficiently and thus the target the end. In this case, the intermediate targets give the 'educated scratchpad' (see Figure 3 for an illustration). We now show how designing low-globality scratchpads can help with learning by focusing on two examples: parity functions and the cycle task.
Results for learning parities. Consider learning parity function y - f (I,,,.,,,,, ,,..,,,,) where æ1,.... Tn are drawn i.i.d. in {+1} with uniform distribution. For < 5. one can easily check that the globality of this task is k as any k - coordinates are independent of the output and the histogram of the tokens does help. Parity functions are known be hard learn [12]. More specifically, it has been previously shown that as & increases the parity task becomes harder to learn to the point that parity of degree min(k: [ n k) (11) cannot learned in poly(n) time with standard poly-size neural networks under standard training assumptions [12]. Note that this is consistent with our results, as the globality is non-constant.
x
Now, consider learning this task with a scratchpad that breaks down the learning with intermediate targets y1, 3/,.................. Uk such that
51 31, ie., Yi is the cumulative product the first bits. Note that each intermediate target ys can be computed by using at most 2 of the previous tokens, implying the following lemma.
1/2 21
y1 Di- 126
Ve 21 ... Ix f(x),
Lemma 2. The parity task with the cumulative product scratchpad has a globality of
Transformers with such scratchpad can in fact easily learn parity targets, see Appendix B.3.
Results for the cycle task. Consider the eycle task and scratchpad that learns the depth-first search (DFS) algorithm from the source query node."! For example, consider the following input corresponding to two cycles a, xr, q and n. y, d: a>x; n>y; q>a; t>n; y>t; x>q; a?t;. this case, doing DFS from node gives a>>>q>a where the fact that we have returned to the source node a and not seen the destination indicates that the two nodes are not connected. Therefore, the full scratchpad with the final answer can be designed as a>x>q>a; 0. Similarly, if the two nodes were connected the scratchpad would be .>...>t;1 1. One can easily check that the cycle task becomes low-globalip with the DFS scratchpad.
ll For the particular graph structure of the cycle task, DFS is the same the breadth-firs search (BFS).
7

---

100000
No pcratchoed
DF5 scratchpad
80000
Inductive scratchpad
0.8
Accuracy
60000
0.6
Iteratoon
40000
DFS scratchpad- In DFS scratchpad - 0OD Indurtive scratchpad In
20000
0.2
scratchpad
0.0
5000
1000
15000
20000
Size of problem in)
Iteration
(a) The cycle task is learned easily when the DFS scratchpad is used.
(b) The DFS scratchpad fails to generalize OOD samples while the inductive scratchpad can,
Figure 4: (Left) Learning the eycle task with scratchpad. (Right) OOD generalization for the DFS and inductive scratchpads (see Section 3.2.1).
Lemma 3. The cycle task with the DFS scratchpad has globality 3.
This follows from the fact that one only needs to find the next node in the DFS path (besides the label), which one can check with polynomial chance by checking the first edge.
In Figure 4a we show that decoder-only Transformer with the DFS scratchpad in fact learns the cycle task when n scales.
Remark 4. If one has full knowledge of the target function,, one could break the target into sub-targets using an educated scratchpad keep the globality low and thus learn more efficiently (of course one does not have to learn the target under full target knowledge, but one may still want to let a model learn it to develop useful representations push this to learning any target that is poly-time computable by emulating a Turing machine in the steps of the scratchpad to keep the overall globality low. Some works have derived results in that direction, such as [33] for some type of linear autoregressive models, or [12] for more abstract neural nets that emulate any Turing machine with SGD training. However, these are mostly theory-orienter works. In practice, one may be instead interested in devising more 'generic' scratchpad. In particular, a relevant feature in many reasoning tasks is the power of induction. For instance, the parity and cycle tasks are two examples where learning induction step function appears useful.
broader/meta-leane -eeaneinn--nnggggg-eee context). One could in theory
3.2 Inductive Scratchpads
As discussed, scratchpads can break the global reasoning barrier with appropriate mid-steps. In this part, however, we show that fully educated scratchpads can be sensitive to the number of reasoning steps, translating into poor out-of-distribution (OOD) generalization. As a remedy, we put forward the concept of inductive scratchpad which applies to various reasoning tasks as in previous sections.
3.2.1 Educated seratchpad can overfit in-distribution samples
Consider the cycle task with 24 nodes. For the test distribution, cycle task, i.e., either two cycles of size 12 and the nodes are not connected or a single cycle of size 24 where the distance between the query nodes is 12. For the train distribution, we keep the same number of nodes and edges (so the model does not need to rely on new positional embeddings for the input) but break the cycles have uneven lengths: (1) a cycle size 6 and a cycle of size 18 when the two nodes are not connected (the source query node is always in the cycle of size 6) or (2) cycle of size 24 where the nodes are at distance Thus, in general, we always have 24 nodes/edges in the graphs. However, the length of the DFS path (i.e., number of reasoning steps) is 6 at training and 12 test. We trained our model on this version of the task with the DFS scratchpad. The results are shown in Figure 4b. We observe that the model quickly achieves perfect accuracy on the training distribution, yet, it fails to generalize OOD as the model overfits the scratchpad length and number of reasoning steps. In the next part, we introduce the notion of inductive scratchpad to fix this problem.
the normal version of the
8

---

3.2.2 Inductive seratchpad: definition and experimental results
In a large class of reasoning tasks, one can iteratively apply an operation to some state variable (e.g., a state array) to compute the output. This applies in particular to numerous graph algorithms (e.g., shortest path algorithms such as BFS or Dijkstra's algorithm), optimization algorithms (such as genetic algorithms or gradient descent), and arithmetic tasks.
Definition 5 (Inductive tasks). Let Q be the question (input). We say that a task can be solved inductively when there is an induction function (or a state transition function)) g such that
* [1] = 0)Q,0),
s(2) = g(Q,,(1)),
s[K] =
where s(1]..... s[k] are the steps (or states) that are computed inductively. For example, the steps/states could be array or the state of automata that is being updated. Note that the termination is determined by the state. In the context of Transformers, one can use the generation of the end of sequence token <EOS> to terminate.
Inductive tasks with a fully educated scratchpad can overfit proofs. The fully educated scratch- pad for the question Q as input would be [1] ; [2] :...;8 [k] <EOS>, where the token <EOS> ends the generation. However, this method may not fully utilize the fact that each state is only generated from the last state by applying the same (set of) operation(s). In particular, [k] typically attends to all of the previous states. Further, the model may not be able to increase the number of induction steps beyond what it has seen during training, as shown in Figure 4b for the cycle task.
Now we show that by using attention masking and reindexing the positions of the tokens, one can promote the desired 'inductive' behavior. We call this the inductive scratchpad. As three showcases, we demonstrate that the inductive scratchpad can improve OOD generalization on the cycle task and length generalization on parity and addition tasks.
Inductive scratchpad implementation. The inductive scratchpad for an inductive task is similar in format to the fully educated scratchpad but it has the following modifications: (1) tokens: two new special tokens are used: the <START> token which separates the question from the intermediate states and the <STATE> token (denoted # hereafter) separate the states. Using these tokens, for an input question Q, the format of the inductive scratchpad reads <START>s [1] #s [2] # #s [k] <EOS>. (2) generation: we want the model promote induction and thus 'orgget' all the previous states except the last one for the new state update. L.e., we want to generate tokens of s [i+1] as if the input was Q<START>> [i]# #. To implement this, one can use attention masking and reindex positions (in order to have a proper induction) or simply remove the previous states at each time; (3) training: when training the scratchpad, we want the model to learn the induction function g, i.e., learning how to output [i+1]# # from Q<START>s [i] #, which can be achieved with attention masking and reindexing the positions. As a result, the inductive scratchpad can be easily integrated with the common language models without changing their behavior other tasks/data. We refer to Appendix C.2 for a detailed description of the inductive scratchpad implementation.
Inductive scratchpad for the cycle task. The DFS scratchpad of the cycle task can be made induc- tive by making each step of the DFS algorithm a state. E.g.. for the input a>x;n>y: pebyyyaxe ppa;t>n;;) x>q;a?t;, the DFS scratchpad is a>x>q>a; O<EOS>, and the inductive scratchpad becomes <START>a***Qaa; O<EDS>> where each state tracks the current node in the DFS. In Figure 4b, we show that the inductive scratchpad for the cycle task can generalize to more reasoning steps than what is seen during training, and thus generalize OOD when the distance between the nodes is increased.
Length generalization for parity and addition tasks. We can use inductive scratchpads to achieve length generalization for the parity and addition tasks. For parities, we insert random spaces between the bits and design an inductive scratchpad based on the position of the bits and then compute the parity iteratively. The performance of this inductive scratchpad is depicted in Figure 5a where we can see a Transformer trained on inputs with up to 30 bits can generalize to samples with up to 50/55 bits depending on the seed. For the addition task, we propose two inductive scratchpads. (1) Random space method that requires random spaces between the digits in the input and uses the position of the digits to compute the addition digit-by-digit (similar to the parity). With this scratchpad, we can generalize to numbers with 18 digits while training on numbers with up to 10 digits. (2) Shift method that uses random tokens in the input and computes the addition bigit-by-digii by shifting

---

1.0
0.8
0.8
0.6
Accuracy
0.6
0.4
0.1
0.2
0.2
Formel
random space
shift
30
35
40
15
50
55
60
12
14
16
18
20
22
24 digits
26
28
30
bits
(a) Length generalization for parity when training done up to bits.
(b) Length generalization for addition where the random space method trained up to digits and the shift method is trained up to 4 digits.
Figure 5:
Length generalization for parity and addition tasks using different random seeds. The medians of the results are highlighted in bold.
the operands. The latter enables us to generalize from to 26 digits at the cost of having a less natural input formatting. The results for different seeds provided in Figure 5b. See details of these scratchpads in Appendices B.4, B.5. A rough comparison between the performance of different methods for addition is given in Table 1. Note that the settings used in these works not exactly the same, e.g., our methods often work with smaller models and more natural input formatting, See Appendix A.2 for detailed comparison for both the parity and addition tasks.
Table 1: Length generalization of different methods for the addition task where our methods are shown in bold. b means generalizing b digits when trained a digits.
Method
[34]
[77]
35]
[36]
[37]
random space method shift method
Performance
9
10
12
40
50
5
15
40
65
10 - 18
4 - 26
Conclusion
This paper shows that for the learning objective and in contrast to expressivity results, Transformers trained from scratch have a "global reasoning barrier' quantified by the globality degree. The globality measure has simpler form and broader applicability range than prior measures discussed in Appendix A.4, also has tighter applicability for Transformers. The measure is currently defined for weak learning (inverse- weweersepoolnoomaa
constant edge), and natural next step is to consider stronger learning requirements with notions "globality leap' e.g., expanding the current work in the direction of [28] but for more general distributions. Investigating the role of curriculum learning is another natural direction and we provide preliminary results here in Appendix B.2.
The globality is also defined in the autoregressive setting, to better quantify when scratchpads can break targets into easier sub-targets. Two negative results are shown for scratchpads: agnostic scratchpads still suffer from the globality barrier, and fully educated scratchpads can have poor OOD generalization. This motivates the introduction of the inductive scratchpad.
The inductive scratchpad can be used for a broad range of reasoning/algorihmmic tasks and can easily be integrated into Transformers. The inductive scratchpad is independent of the number of reasoning steps since the model only learns the induction function. Consequently, the model better generalizes to inputs requiring different numbers of reasoning steps. This gives improvements of OOD/length generalization for the cycle task (Figure 4b), parity (Figure 5a), and addition (Figure 5b).
Another interesting aspect is whether the model can use an inductive behavior on new tasks if it was pre- pre-trained on prior inductive tasks. Note that the inductive behavior of the inductive scratchpad only determined by two special tokens. Thus, in principle, models can generate these special tokens and go into the inductive state for other tasks if pre-trained on inductive data. We leave the general investigations of pre-trained models and the automated learning of more general scratchpads, capitalizing on the measures defined here, to future works.
12 Our code is available https: ttttpp://github http:///w....////aaaeeeeeeeaeaae
10

---

Acknowledgments
We thank Samira Abnar, Tatiana Likhomanenko, Joshua Susskind, and Russ Webb for stimulating discussions and useful feedback on the research of this paper, as well as Etai Littwin and Preetum Nakkiran for giving feedback on the paper's writing.
References
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[2] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010.11929 2020.
[3] Ibrahim Alabdulmohsin, Behnam Neyshabur, and Xiaohua Zhai. Revisiting neural scaling laws in language and vision. arXiv preprint arXiv:2209.0666 2022.
[4] David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. arXiv preprint arX4v:1904.011 2019.
[5] Aitor Lewkowyez, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski. Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Son et al. Solving quantitative reasoning problems with language models. arXiv preprint arXiv:2206.1488 2022.
[6] Chiyuan Zhang, Maithra Raghu, Jon M. Kleinberg, and Samy Bengio. Pointer value retrieval: A new benchmark for understanding the limits of neural network generalization. ArXiv, abs/2107. 12s/2007.11580, 2021.
[7] Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Fei-Fei, Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2901-2910 2017.
[8] Anton Bakhtin, Laurens der Maaten, Justin Johnson, Laura Gustafson, and Ross Girshick. Phyre: A new benchmark for physical reasoning. Advances in Neural Information Processing Systems, 32, 2019.
[9] Petar Veličković, Adrià Puigdomenech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning benchmark. arXiv preprint arXiv:2205. 15659, 2022.
[10] Sadegh Mahdavi, Kevin Swersky, Thomas Kipf, Milad Hashemi, Christos Thrampoulidis, and Renjie Liao. Towards better out-of-distribution generalization of neural algorithmic reasoning tasks. ArXiv, 221 2.00629, 2022.
[11] Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowyez, Vedant Misra, Vinay Ra- masesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. arXiv preprint arXiv:2207.0m 04901, 2022.
[12] Emmanuel Abbe and Colin Sandon. Polynomial-time universality and limitations of deep learning. Communications on Pure and Applied Mathematics,
11:3443-335444 2023.
[13] Emmanuel Abbe and Enric Boix-Adsert On the non-universality of deep learning: quantifying the cost of symmetry. In Koyejo, Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 172011. Curran Associates, Inc., 2022.
[14] Michael Kearns. Efficient noise-tolerant learning from statistical queries. ACM, 45(6):983-
1006, November 1998.

---

[15] Emmanuel Abbe and Colin Sandon. On the universality of deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin. editors, Advances in Neural Information Processing Systems, volume 33, pages 20061-20072. Curran Associates, Inc., 2020.
[16] William Merrill and Ashish Sabharwal. The parallelism tradeoff:: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics. 11:531-545, 2023.
[17] Ruoqi Shen, Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, Yuanzhi Li, and Yi Zhang. Po- sitional description matters for transformers arithmetic. arXiv preprint arXiv:2311.1477 2023.
[18] Shai Shalev-Shwarde and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, NY, USA, 2014.
[19] Vitaly Feldman. A general characterization of the statistical query complexity, arXiv preprint arXiv:1608.00 02198, 2016.
[20] Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
[21] Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? arXiv preprint arXiv:2402.09900 2024.
[22] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl:: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[23] Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Algorithms for learning kernels based on centered alignment. J. Mach. Learn. Res., (3(1):795-828, mar 2012.
[24] Emmanuel Abbe, Elisabetta Cornacchia, Jan Hazla, and Christopher Marquis. An initial alignment between neural network and target is needed for gradient descent to learn 2022.
[25] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. J. Mach. Learn. Res., 22: 12:106-1, 2021.
[26] Joan Bruna, Loucas Pillaud-Vivee and Aaron Zweig. On Single Index Models beyond Gaussian Data. arXiv e-prints, page arXiv:2307.15804 July 2023.
[27] Alex Damian, Loucas Pillaud-Vivii Jason D. Lee, and Joan Bruna. Computationall-tatin Statistical Gaps in Gaussian Single-Index Models. arXiv e-prints, page S1ii:22403.05522 March 2024.
[28] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning neural networks: leap complexity and saddle-to-saddee dynamics. In The Thirty Sixth Annual Conference on Learning Theory, pages 2552-2623, PMLR, 2023.
[29] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever, Lan- guage models are unsupervised multitask learners, 2019,
[30] William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. ArXiv, abs/2310.07923, 2023.
[31] Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. On the power of differentiable learning versus PAC and SQ learning. In Advances in Neural Information Processing Systems, volume 34, 2021.
[32] 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.
[33] Eran Malach. Auto- Regrossiee Next-Token Predictors are Universal Learners. arXiv e-prints, page MrXiv:2309.06977 September 2023.
12

---

[34] Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact positional encoding on length generalization transformers. arXiv preprini arXiv:2305. 19466, 2023.
[35] Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers learn? a study in length generalization. arXiv preprint arXiv:23 16028, 2023.
[36] Samy Jelassi, Stéphane d' Ascoli, Carles Kamingo-Enricle Yuhuai Wu, Yuanzhi Li, and François Charton. Length generalization in arithmetic transformers. arXiv preprint arXiv:2306. 15400, 2023.
[37] Yongchao Zhou, Uri Alon, Xinyun Chen, Xuezhi Wang, Rishabh Agarwal, and Denny Zhou. Transformers can achieve length generalization but not robustly. arXiv preprint xXXiv:2402.09371,2222 2024.
[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. arXiv preprint arXiv:2001.08.0 2020.
[39] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization, 2016.
[40] Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33:2881-2891, 2020.
[41] Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. arXiv preprint 1rXiv:2202.076444 2022.
[42] Nikhil Kandpal, Eric Wallace, and Colin Raffel. Deduplicating training data mitigates privacy risks in language models. In International Conference Machine Learning, pages 10697- 10707. PMLR, 2022.
[43] Sadegh Mahdavi, Renjie Liao, and Christos Thrampoulidis. Memorization capacity of multi- head attention in transformers. In The Twelfth International Conference on Learning Repre- sentations, 2024.
[44] Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with lego: a synthetic reasoning task. arXiv preprint arXiv:2206.04300 2022.
[45] Wojeiech Zaremba and Iya Sutskever. Learning to execute. arXiv preprint arXiv: 1410.465. 2014.
[46] Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-tee soquence-to-sequueee sequence recurrent networks. In International conference on machine learning, pages 2873-2882. PMLR, 2018.
[47] Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795. 2020.
[48] Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk. Generalization on the unseen, logic reasoning and degree curriculum. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 31-60. PMLR, 23-29 Jul 2023.
[49] Nayoung Lee, Kartik Sreenivasan, Jason D. Lee, Kangwook Lee, and Dimitris Papailiopoulos. Teaching arithmetic to small transformers. The Twelfth International Conference on Learning Representations, 2024. 2024.
13

---

[50] Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attentn with relative position representations. In North American Chapter of the Association for Computational Linguistics, 2018.
[51] Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoe V. Le, and Ruslan Salakhut- dinov. Transformer-xl: Attentive language models beyond a fixed-length context. In Annual Meeting of the Association for Computational Linguistics, 2019.
[52] Colin Raffll, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of Machine Learning Research, 21((40):1-61 2020.
[53] Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference Learning Representations, 2022.
[54] Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568: 127063, 2024.
[55] Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The devil is in the detail: Simple tricks improve systematic generalization of transformers. arXiv preprint arXiv:2108. 12284, 2021.
[56] Santiago Ontanon, Joshua Ainslie, Zachary Fisher, and Vaclav Cvicek. Making transformers solve compositional tasks. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, Proceedings of the 60th Annual Meeting of the Association for Computational Linguis- tics (Volume I: Long Papers), pages 3591-3607, Dublin, Ireland, May 2022. Association for Computational Linguistics.
[57] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers, 2019.
[58] DeLesley Hutchins, Imanol Schlag, Yuhuai Wu, Ethan Dyer, and Behnam Neyshabur. Block- recurrent transformers. Advances in neural information processing systems, 35:33248-33261, 2022.
[59] Angeliki Giannou, Shashank Rajput, Jy- Yo-Yong& Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 11398 11442. PMLR, 23-29 Jul 2023.
[60] Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv:1603.08900 08983, 2016.
[61] Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The neural data router: Adaptive control flow in transformers improves systematic generalization. In International Conference on Learning Representations, 2022.
[62] Nikita Nangia and Samuel R. Bowman. Listops: A diagnostic dataset for latent tree learning. ArXiv, 800.08804 2018
[63] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. (hain-of-thougle prompting elicits reasoning in large language models, 2023.
[64] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners, 2023.
[65] Hattic Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanic Sedghi. Teaching algorithmic reasoning via in-context learning, 2022.
[66] Jack Lanchantin, Shubham Toshniwal, Jason Weston, Sainbayar Sukhbaatar, et al. Learning to reason and memorize with self-notes. Advances in Neural Information Processing Systems,
36, 2024.
14

---

[67] Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan. Think before you speak: Training language models with pause tokens. In The Twelfth International Conference on Learning Representations, 2024.
[68] Jiashuo Sun, Yi Luo, Yeyun Gong, Chen Lin, Yelong Shen, Jian Guo, and Nan Duan. En- hancing chain-of-thoughts prompting with iterative bootstrapping in large language models, 2024.
[69] Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inference: Exploiting large language models for interpretable logical reasoning. 2022.
[70] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36, 2024.
[71] Vivien Cabannes, Charles Arnal, Wassim Bouaziz, Alice Yang, Francois Charton, and Julia Kempe. Iteration head: A mechanistic study of chain-of-thougee arXiv preprint arXiv:2406.02 02/8 2024.
[72] Shanda Li, Chong You, Guru Guruganesh, Joshua Ainslie, Santiago Ontanon, Manzil Za- heer, Sumit Sanghai, Yiming Yang. Sanjiv Kumar, and Srinadh Bhojanapalli. Functional interpolation for relative positions improves long context transformers. arXiv preprint arXiv:2310.04418. 2023.
[73] Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generalization of transformers. arXiv preprint 0rXiv:2305.16844 2023.
[74] Jian Liu, Leyang Cui, Hanmeng Liu, Dandan Huang, Yile Wang, and Yue Zhang. Logiqa: A challenge dataset for machine reading comprehension with logical reasoning, 2020.
[75] Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. Drop: reading comprehension benchmark requiring discrete reasoning over paragraphs, 2019.
[76] Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. Clutrr: A diagnostic benchmark for inductive reasoning from text, 2019.
[77] Bo Wu, Shoubin Yu, Zhenfang Chen, Joshua B Tenenbaum, and Chuang Gan. Star: A benchmark for situated reasoning in real-world videos. In Thirty-fifth Conference on Neural Information Processing Systems (NeurIPS), 2021.
[78] Santiago Ontanon, Joshua Ainslie, Vaclav Cvicek, and Zachary Fisher. Logicinference: new dataset for teaching logical inference to seq2seq models, 2022.
[79] Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language?, 2024.
[80] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like graph: Encoding graphs for large language models, 2023.
[81] Xikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren, Percy Liang, Christo- pher D. Manning, and Jure Leskovec. Greaselm: Graph reasoning enhanced language models for question answering, 2022.
[82] Kewei Cheng, Nesreen K. Ahmed, and Yizhou Sun. Neural compositional rule learning for knowledge graph reasoning, 2023.
[83] Theo Olausson, Alex Gu, Ben Lipkin, Cedegao Zhang, Armando Solar-Lezama, Joshua Tenen- baum, and Roger Levy. Line: A neurosymbolic approach for logical reasoning by combining language models with first-order logic provers. In Proceedings of the 2023 Conference on Em- pirical Methods Natural Language Processing. A Association for Computational Linguisties, 2023.
15

---

[84] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng. Guolin Ke, Di He. Yanming Shen, and Tie-Yau Liu. Do transformers really perform bad for graph representation?. 2021.
[85] Oshin Agarwal, Heming Ge, Siamak Shakeri, and Rami Al-Rfou. Knowledge graph based synthetic corpus generation for knowledge-enhanced language model pre-training, 2021.
[86] Bowen Jin, Wentao Zhang, Yu Zhang, Yu Meng, Xinyang Zhang, Qi Zhu, and Jiawei Han. Patton: Language model pretraining on text-rich networks, 2023.
[87] Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Hal- crow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. arXiv preprint arXiv:2405. 185 /2, 2024.
[88] Emmanuel Abbe, Samy Bengio, Elisabetta Cornacchia, Jon Kleinberg, Aryo Lotfi, Maithra Raghu, and Chiyuan Zhang. Learning reason with neural networks: Generalization, unseen data and boolcan measures. Advances in Neural Information Processing Systems, 35:2709-
2722. 2022.
[89] Emmanuel Abbe, Enric Boix-Adsera and Theodor Misiakiewicz. The geerged-staircant property: necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks, COLT. 2022.
[90] Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Conference on Machine Learning, pages 11000-11090, PMLR, 2021.
[91] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, page 41-48, New York, NY, USA, 2009. Association for Computing Machinery.
[92] Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the benefit using differentiable learning over tangent kernels. In Marina Meila and Tong Zhang, editors, Proceedings the 38th International Conference Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 7379-7389. PMLR, 18-24 Jul 2021.
[93] Elisabetta Cornacchia and Elchanan Mossel. A mathematical model for curriculum learning. arXiv preprint arXiv:2301.1388. 2023.
[94] Emmanuel Abbe, Elisabetta Comncchiaa, and Aryo Lotfi. Provable advantage of curriculum learning on parity targets with mixed inputs. Advances in Neural Information Processing Systems, 36, 2024.
[95] Petru Soviany, Radu Tudor lonescu, Paolo Rota, and Nicu Sebe. Curriculum learning: A survey. International Journal of Computer Vision, pages 1-40, 2022.
[96] Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. CoRR, abs/1711.05101, 2017.
[97] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[98] Andrej Karpathy. Nanogpt. https: http:///tthhuuu.c./ma/atateettee 2024.
Accessed: April
[99] Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In Waleed Ammar, Annie Louis, and Nasrin Mostafazadeh, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations), 2019.
[100] Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant Nair, llya Soloveychik, and Purushotham Kamath. Keyformer: Ky cache reduction through key tokens selection for efficient generative inference. Proceedings of Machine Learning and Systems, 2024.
16

---

A Further related literature
A.1 Reasoning capabilities of Transformers
Reasoning vs. memorization. The performance of large language models and Transformers has been shown to improve as the model size, amount of data, and training time are increased [38, 3]. Furthermore, it has been shown that Transformers are prone to memorizing the training data [39, 40, 41, 42, 43J. Thus, it is natural to ask whether Transformers mostly rely on memorization or if they in fact use memorization along with a significant degree of reasoning. Reasoning is also essential in solving more challenging tasks such as planning and mathematics. In recent years, the reasoning power of Transformers has been studied on synthetic reasoning tasks such as PVR [6], LEGO [44], algorithmic tasks such as CLRS [9]. and more natural settings such as solving math problems [4. 5]. Note that reasoning tasks often have a combinatorial nature and thus an exponentially large input space. Moreover, this input space may not lie on a low-dimensional manifold which makes memorization approaches ineffective. For example, in arithmetic, all digit combinations are often possible and also change the result significantly, whereas, in text, only specific combinations of words are valid and besides changing a single word often does not change the meaning of the text drastically. Another important criterion for reasoning is the ability to generalize to -utto-ddistriuution (OOD) samples and in-particular length generalization [45, 46, 47, 11, 48). It has been observed that simple tasks such as addition, multiplication, and parity are generally hard for Transformers both in the tn-distribution setting and more notably in the length generalization setting [11, 49].
Positional embeddings. An important component of length generalization the positional embed- ding of the model. It has been shown that various forms of relative positional embedding [50, 51] including T5's relative positional embedding [52], ALiBi [53], and Rotary [54] can yield better length generalization performance than absolute positional embedding [55, 56, 34). In particular, the recent work of Kazemnejad et al. [34] evaluates different positional embeddings for decoder-only Transformers on benchmark of reasoning tasks where it is shown that relative positional embeddings perform better than absolute ones. Interestingly, it is also shown that decoder-only Transformers with positional embedding (NoPE) can still encode positional information and in fact have better length generalization performance than absolute/relative positional embeddings on certain tasks. The inductive scratchpad put forward in this paper also reindexes the position of the tokens for each new state. Using this technique, the inductive scratchpad circumvents the need for learning new positional information as the number of reasoning steps (i.e., the number of states) increases. Nevertheless, the inductive seratchpad can be used with both absolute and relative positional embeddings. We further discuss the relation between the inductive scratchpad and relative positional embeddings in Appendix C.3.
Architectural modifications. Several architectural modifications have also been proposed that can potentially enhance the reasoning ability of Transformers certain tasks. A line of work focuses on adding recurrent structures to Transformers [57, 58, 59]. In particular, Universal Transformers [57], share the weights between Transformer layers and also have variable depth (similar to adaptive computation time [60]) implemented using a dynamic halting mechanism. Generally scratchpads and in particular the inductive scratchpad also share some recurrent flavor since when each token of the scratchpad is generated, the whole input and the seratchpad tokens are given to the Transformer again. The differences are however quite significant both on the side of supervision (e.g., scratchpads are usually supervised) and halting mechanism (e.g., generation of <EOS> token ends the process for scratchpad models). Another relevant architecture is the neural data router [61] where the weights shared among transformer layers and also copying gates and a special attention format, geometric attention, are used. The copying gate allows some tokens not to be transformed and instead just be copied at certain transformer layers while geometric attention induces a recency bias. The neural data router is shown generalize to samples with up three more operations than what seen during training for simple arithmetic tasks and ListOps dataset [62]. We note that our inductive scratchpad can also generalize to samples with a higher number of operations/reasoning steps. Note that the neural data router approach requires the model's depth to be (at least) equal to the maximum number of operations, while our model does not have such limitations and can thus be trained and tested on samples with larger numbers of operations than the neural data router approach. Moreover, intermediate steps are supervised through the scratchpad mechanism in our approach while there no supervision for intermediate steps in the neural data router.
17

---

Scratchpad and chain-of-thought. Nye et al. [32] put forward the idea of using scratchpads by showing that training Transformers on the intermediate steps in addition to the final answer can improve their performance on different tasks such as executing Python code, addition, and evaluating polynomials. Similarly, in chain-of-though reasoning (CoT) [63] models are shown step-by-step demos of problem-solving (or models generate chains of thought without any examples as in zero-shot CoT [64], among other variants). It has been further shown that using explicit explanations and reducing ambiguity can be proven useful as in the notion of algorithmic prompting [65]. Lanchantin et al. [66] introduced the concept of self-notes, showing that interleaving the intermediate reasoning steps within the question/context rather than after the question can boost the performance of scratchpad/CoT on certain tasks. Goyal et al. [67] introduced pause tokens which act as dummy tokens that provide models with more compute time and processing before the generation of the true next token. On a related note, the iterative prompting method in [68] involves querying LLMs iteratively to optimize question prompts. Further, the Select and Inference framework (SI) [69] utilizes pre-trained LLMSs as general processing modules, alternating between selection and inference to generate interpretable reasoning steps leading to the final results.
The work of [70] studies the role of scratchpad from an expressivity point of view. Assuming TC o NC!, they show the existence of tasks that are not expressible by constant-depth Transformers without scratchpad and expressible by constant-depth Transformers with scratchpad. is further shown that dynamic programming (DP) algorithms can be expressed by constant- depth Transformers with scratchpad [70]. In this work, however, we used the concept of autoregressive globality to explain why scratchpads are helpful and how to design them from the learning point of view. Further, introduced inductive scratchpads that are suitable for a broad range of algorithmic reasoning tasks and can potentially generalize to more complex samples than what appears in the train distribution. We note that inductive scratchpads are also suitable for DP algorithms thanks to their iterative structure (the variables of the DP algorithm can be updated in each state of the inductive scratchpad). We stress that our inductive scratchpad potentially enables models to generalize to OOD samples for such DP algorithms and/or to work with longer scratchpads because of the attention masking which reduces the effective context size. In concurrent research, [71] shows that a restricted class of iterative algorithms with scratchpad (including parity task) are expressible by 2-layer Transformers. Compared to our inductive scratchpad, [71] I] does not have any length generalization result.
A.2 Length generalization for parity and addition tasks
Parity and addition tasks are two essential reasoning tasks that are challenging in the setting of length generalization where the number of bits/digits is increased. These tasks can also be hard in the in-distribution setting if the number of bits/digits is large enough. It has been shown that certain forms of craacchpad/channoo-thhouut
reasoning and relative positional embedding can achieve a modest length generalization on the parity task (around 5/10 more bits depending on the method and the seed) [11, 34]. The RASP-L work [35] considers the parity task and can get length generalization from 30 to 50 bits (depending on the random seed) by using 'index hints' which are special tokens that come before the input bits in a specific order. For instance, an input could look like a060cldled e0. Our proposed inductive scratchpad for the parity task only requires the use of random spaces in the question formatting and can generalize to 55 bits when trained on samples with up to 30 bits. Different works use different input formatting, techniques, model sizes, and train/test datasets, nevertheless, a rough comparison between different works for the parity task is given in Table 2 (learning is defined as above 80% accuracy for the majority/median of the results for different seeds, some seeds do better than others).
For the addition task, Lee et al. [49] use a decoder-only model similar to ours (also similar in size) showing that generating the output in the reverse format and using scratchpads are helpful. However, they are not able to get length generalization with their model size. Nevertheless, it has been shown that large enough models (with more than 10 parameters) with scratchpad can generalize to numbers with 9/10 digits while being trained on numbers with up to 8 digits [32]. Jelassi et al. [36] show that encoder-only models with relative positional embedding can generalize to numbers with 15 digits when they are trained on numbers with up to 5 digits. The RASP-L work [35] considers the addition task and can get length generalization from 35/40 to 50 digits (depending on the seed) by outputting the result in the reverse order and also using "index hints" (special tokens coming before the operands' digits in a specific order). For instance, an example would look like a5l4 + a3b7 = bl. Zhou et al. [37] further improve the latter by using FIRE relative positional embedding [72] and
18

---

Table 2: Length generalization performance of different methods for the parity task
Work
Performance
Method and Assumptions
Kazemnejad et al. [34] From 8 bits to 12 bits
Using NoPE (no positional embedding)
Using scratchpad 'index hints' (special tokens before each bit in the input), an input & output look like a060c1d1e)
RASP-L work [35]
From 30 bits to 50 bits
d+
Using large pre-trained models (128B)
Anil et al. [11]
From 8 bits to 20 bits
prompting + fine-tuning + scratchpad
Using random spaces in the input (e.g.. _01_1100_1__ + inductive scratchpad
Our method
From 30 bits to 55 bits
randomized position encoding [73], generalizing to numbers with 65 digits when trained on numbers with up to 40 digits. The work of Shen et al. [17] uses scratchpad with a recursive format for the addition task to generalize to numbers with 12/13 digits while the training data includes numbers with up to 10 digits. Our special case of inductive scratchpad based on shifting the numbers is similar to their recursive scratchpad, however, [17] does not enforce any inductive structure (as achieved with the attention masking for the inductive scratchpad) and hence [17] gets much more limited length generalization.
In this work, we proposed two inductive scratchpads for the addition task. The inductive scratchpad that requires random spaces in the question can generalize to numbers with 18/20 digits when trained on numbers with up to 10 digits. The other inductive scratchpad based on shifting the operands at each step can generalize to numbers with up to 26 digits when trained on numbers with up to digits at the cost of having a less natural question formatting. Different works use different input formatting, techniques, model sizes, train/test distribution, and evaluation procedures, nonetheless, rough comparison between different works for the addition task is provided in Table 3 (reported results correspond to the median performance given by different seeds). We believe our solutions for both the parity and addition tasks require one of the least stringent modifications of the input and provide a significant improvement of the length generalization performance compared to prior works even though the models that we have used are often remarkably smaller.
Table 3: Length generalization performance of different methods for the addition task
Work
Performance
Method and Assumptions
Kazemnejad et al. [34]
From 8 digits to 9 digits
Using NoPE (no positional embedding)
Shen et al. [17]
From 10 digits to 12 digits
Scratchpad with recursive format
Reverse order of the output + 'index hints" (special tokens before each digit). e.g., a5b4 + a367 = bla9
RASP-L work [35]
From 40 digits to 50 digits
Encoder-only model
Jelassi et al. [36]
From 5 digits to 15 digits
relative pos. emb. padded inputs
FIRE relative pos. emb. randomized position encodings + reversed output index hints
Zhou et al. [37]
From 40 digits to 65 digits
Inductive scratchpad + random space the input (e.g.. 94 + 3 =)
Our random space method
From 10 to 18 digits
Inductive scratchpad + random text before each operand (c.g.. fs846 - ih$98)
Our shift method
From 26 digits
A.3
Reasoning over graphs
Numerous reasoning tasks can be thought of as some form of rule-based logical inference entail- ments, over implicit or explicit graphs, where at their core sit common graph operations such as graph connectivity checks (as in the cycle task in the present paper). Here, we review a sample of
19

---

notable related works on logical reasoning over graphs sharing the same primary motivation as the one behind our current work.
In recent years, several benchmarks have emerged, focusing on logical inference over diverse modali- ties. Within the context of natural language, LogiQA [74], DROP [75] or the Cluttr benchmarking set [76] are worth mentioning. These benchmarks assess logical relational reasoning abilities concerning entities and relations expressed in natural language. Another example but from different modality is STAR [77], which focuses on situated logical reasoning over video clips. The work by Ontanon et al. [78] introduced the LogicInference dataset for training and benchmarking sequence-to- sruuencc-to-eequence sequence mod- els for logical inference tasks. The work by Wang et al. [79] introduces NLGraph, a benchmarking set for measuring LLMs' capabilities in solving graph- based problems, including the graph connectivity task studied in the current paper. GraphQA, as presented in the work by Fatemi et al. [80], explores the impact of graph structure on language model prompting while separating the impact of graph encoding and question prompting on the final performance. The common denominator of these studies' results is that while language models excel as shallow reasoners, their performance in logical reasoning deteriorates with an increase in the number of required reasoning steps [69].
On the modeling front, a group of efforts have primarily focused on baking the appropriate inductive biases into the models for reasoning and logical inference over graphs. The work [81] proposes architectural innovations to use both the context and external knowledge sources. [82] proposes an end-to-end neural model for learning compositional logical rules. The Neurosymbolic approach, presented in [83] involves performing semantic parsing on natural language input using neural components to transform the input into discrete structures suitable for symbolic reasoning by the logic theorem provers. Graphomer [84] extends standard Transformer architecture with a graph reasoning inductive bias. The work of [57] combines Transformers with the inductive bias of the recurrent models. Other works take the route of generating more data using external sources like Knowledge Graph [85] or extending pre-training [86]. The work in [79] evaluates LLMs' graph reasoning capabilities in the presence of various prompting techniques like scratchpads/CoT and their variants. This study introduces Build-a-Graph Prompting, an instruction- based prompting method, as well as Algorithmic Prompting, which includes references to relevant graph algorithms in the prompts, as two approaches for enhancing LLMs in solving graph tasks in natural language.
Concurrently with our work, [87] studies the graph reasoning abilities of Transformers. They focus on different tasks such as node count, edge count, connectivity, and shortest path. On the theoretical side, they focus on the expressivity of Transformers. In particular, they show that log-depth Transformers can express the graph connectivity task. This is while in our paper, focus on learning, showing that for hard enough distributions (i.e., distributions with high globality), regular Transformers cannot learn the connectivity task despite being able to express it. On the empirical side, they show that Transformers can perform well on the connectivity tasks GraphQA dataset [80], outperforming graph neural networks (GNNs). We note that this is not in contrast to results. As we saw in Section 1.2 with random graphs, if the input distribution has low globality the connectivity task can become Iearnable for Transformers.
A.4 Learning measures and lower-bounds for GD
Some recent literature has studied complexity measures for (S)GD-trained neural networks. In particular, the noise sensitivity [20, 6, 88, 21]. which applies mostly to settings with i.i.d. inputs and is known to be loose for strong learning [89. 28]; the statistical query (SQ) dimension [14, 19] and the pross-rrdiittabilityy [12]. which are usually defined for class of targets/distributions rather than single distribution (in particular the full parity is efficiently SQ learnable since there is a single function); the NTK alignment [22, 23] that are limited to the NTK framework; the initial alignment (INAL) [24], which is also related to the noise-sensitivity with the advantage of depending on the network initialization at the cost of being a more implicit measure; the information exponent [25, 26), generative exponent [27] and leap [28], which measure when fully connected neural networks can strongly learn target functions on i.i.d. or isotropic input distributions and sparse or single/multi--ng -nddx functions.
We now discuss the proof techniques for Theorem 1. We prove that the Transformer cannot learn to distinguish between 1 cycle and 3 cycles by means of statistical query argument. We find group of permutations that preserve the input distribution, take the orbit of the target function under these permutations, and show that a random pair of functions in the orbit are nearly uncorrelated.
20

---

Then we argue that that means that no function is significantly correlated with random function in the orbit, so the gradient is uninformative and the net fails to learn anything meaningful. The main complication to this argument is the fact that the input distribution is fairly complicated, in contrast to orbit arguments used in previously discussed works (e-g., for subset parities). The majority of the symbols in the input are fixed and the rest have nontrivial dependencies. However, we get around that by dividing the input into blocks and observing that switching the nonfixed symbols in any two blocks leaves the overall probability distribution unchanged. This argument would largely carry over to other cases with a sufficiently symmetric input distribution and high globality target function.
A.5 On RASP and RASP-L
In [90], the authors define a programming language, RASP, model the types of computations a fixed-size Transformer can compute. This is more about expressivity than learnability, but to the degree that Transformer will tend to learn computation representable by short RASP program if there is one that achieves low loss, it does have some implications for learning. For instance, [35] observes that Transformers tend to generalize different input lengths on tasks that can be represented by short RASP programs but not on other tasks. It also seems plausible that for tasks that can be solved by short RASP programs a sufficiently small Transformer would have a nontrivial probability of stumbling on the solution. However, we expect that randomly initialized large Transformers would tend to mix together a large number of computations in a chaotic manner, at least until they find some computation that they can improve their performance by focusing more on. So, we do not expect the existence of a short RASP program solving a problem to imply that Transformers would learn to solve it easily.
Also, RASP-L [35] is a variant of RASP that does not contain the full parity function as a short program. Our globality theory predicts that the full parity can be learned by some regular Transformer (in contrast to subset parities), so this also gives a nuance. Incidentally, our reason for expecting that some regular Transformer can learn the parity is that if the Transformer is set to mostly ignore the positional embeddings then the first layer it will essentially average all of the inputs together. The correct label is function of this average and it only has n + 1 possible values, so it seems likely that with the right setup it would be able to memorize the appropriate response to each of them.
B
Additional experiments
B.1
Implications on random graphs
Here, we further discuss the disadvantages of using random graphs as the graph distribution for the implications task. There are two main downsides using random graphs distribution instead of the cycle task distribution (Definition 1):
1. The distance between nodes (i.e., the number of statements to compose) does not scale well with the number of nodes/edges in the graph.
2. Whether two nodes are connected or not often correlates with low-complexity patterns such as the degree the nodes random graphs, thus, weak learning on random graphs does not necessarily imply that the model has truly learned to find a path between two nodes. In other words, the model may be able to rely on shortcuts instcad of solving the composition task.
In this section, we provide empirical evidence for both of the claims above.
First, we consider random graphs with n nodes and a varying number of edges e. For each pair of (n, e). we compute the average of maximum distance and the average of the average distance in random graphs with n nodes and e edges. (We ignore the nodes that are not connected.) The results for n = 128 are presented in Figure 6. It can be seen that the distances in the graphs do not scale well with the number of nodes and edges in the graph. (E.g., compare this to having distance n in the cycle task with 2n nodes/edges.) This is because high number of edges usually results in very well-connected graph and a low number of edges leads to mostly isolated edges.
Now, we move to the second claim, i.e., the model using low-complexity patterns and correlations. As an example, we take random graphs with 24 nodes and 24 edges. In order to have a balanced dataset with samples of mixed difficulties, create the dataset as follows. We first sample random
21

---

Max distance Average distance
Distance
2500 5000 7500 10000 12500 15000 17500 Number edges, e
Figure 6: The average of the maximum and average distance directed random graphs with n 128 nodes and varying number of edges.
1.0
0.8
Accuracy
0.6
Validation set
Distance 1,2,3,4 (averaged) Not connected
OOD 2,3,4 (averaged)
2000
4000
6000
8000
Iteration
Figure 7: Performance of a model trained on balanced distribution of random graphs with 24 nodes and edges where with probability 0.5 the query nodes not connected and with probability 0.5 they are connected and their distance uniformly selected from 1, 2, 3, The validation set has the same distribution the training showing that the model reaches around 80% accuracy in-distribution samples. Particularly, the model has perfect accuracy on connected nodes (distance 1-4) and around 60% accuracy the nodes that not connected. However, when tested the model on OOD samples (where some spurious correlations are not present) the model showed chance level performance. Note that these samples would be of low complexity the model was actually checking whether there exists a path or not.
graph with 24 nodes and edges. Then with probability 0.5 we select two nodes that are not in the same connected component (label and with probability 0.5 we choose a distance d 21,2,3, 4) uniformly and we choose two nodes that have distance d (if the graph does not have any two nodes with distance d, we sample another random graph). As result, our dataset is balanced and 12.5% model this dataset and
of the samples have distance d for d 2,, 3..). We trained observed that the model reaches an average accuracy roughly 80%. The results are shown in Figure 7. More precisely, we observed that the model has perfect accuracy when the two nodes are connected (there is a path), and has around 60% accuracy when the two nodes are not connected (the nodes not in one connected component). In other words, the default behavior of the model is to say that the nodes are connected and the model can also detect that two nodes are not connected in 60% of the cases.
To further test whether the model is truly understanding that the two nodes are not connected is only relying low-complexity correlations, designed new data distributions and assessed
22

---

the model's behavior on these new distributions. The samples in the new distributions also have 24 nodes and edges so the model does not have a length generalization problem. More specifically, for i E {2, 3, 4), we designed distribution OOD+ such that each dataset is balanced and for each sample, the two nodes are either in a cycle of size with distance i or they are in two disjoint cycles of size i. All the other nodes are also in different cycles. 13 Note that these distributions are motivated by the cycle task. For example, it is not possible for the model to merely rely on the degree of the nodes. However, if the model uses the correct algorithm (i.e., tries to find a path) then the number of reasoning steps (e.g., length of the BFS/DFS search) is as the distance between the nodes is i when they are connected and otherwise they connected exactly to - 1 other nodes. As it can be seen in Figure 7, the model has 50% (random) accuracy on these distributions meaning that is not really checking whether there is path between two nodes or not, even for simple examples in OOD 2 supporting that the model is relying on correlations rather than finding a path. (In particular, the model always outputs connected these OOD datasets.)
We tried to further understand the behavior of this model. By sampling, we computed that one can get accuracy of around 82% on in-distribution samples just by outputting not-connected if the out-degree of the source query node or the in-degree of the destination query node is zero and connected otherwise. Further, we noticed that this predictor has high correlation with the output of the model. In particular, in almost all of the cases that the model predicts 'not-connected, the source's 's out-degree or the destination's 's in in-degree is zero. (The model may still misclassify some of such samples depending on the random seed.) The latter shows that the model is indeed relying on the degrees of the query nodes as shortcut.
B.2 Change of distribution and curriculum learning
We have defined the cycle task such that all samples in the dataset have the same difficulty. More specifically, if the two nodes are connected their distance is and if they are not connected they are each in a cycle with n vertices. Thus, is a natural question to ask what would happen if the training distribution included samples of varying difficulties. To investigate the answer to this question, use a distribution with samples of mixed difficulties for the training. Furthermore, we try curriculum learning [91] by increasing the samples' difficulty throughout the training.
Mixed distribution. We change the training distribution to a uniform mixture of the cycle task distribution for sizes i = 2.... ... n, i.e., each sample comes from the distribution of the cycle task for size i (having 2i nodes and edges) with probability n-1- _ Therefore, in the mixed distribution setting, the number of reasoning steps varies between 2 to n. As an example, we set n = 7 and train our model with fresh samples from the mixed distribution. We assess the model's 's performance on cycle task samples of sizes 2,.... n = 7 (where we include both connected and disconnected cases as in the original definition). The results are shown in Figure 8a. It can be seen that the cycle task is learned in the order of difficulty (i.e., size). Further, note that when a mixed distribution is not used, weak learning of the cycle task for here, weak learning for n = 7 begins in the first 30k iterations. Note that this is not in contrast with our theoretical results since including easy samples reduces the globality. Analogously, in the setting of learning parities, it has been shown that using a biased rather than uniform distribution (which makes the distribution simpler) can make parity targets easier leam [92, 93].
7 is not possible up to 100% iterations (see also Figure lb), whereas
Curriculum learning. Next, we try curriculum learning, i.e., we give samples in the order of difficulty (size in the cycle task) to the model during training. We consider two settings: (1) setting in which the model has to fit samples of all difficulties and (2) a setting in which the model is allowed to forget easier samples. In other words, in the first setting, we want the model to fit cycle task samples of sizes 2...., n while in the second setting, we only care about fitting samples of size n. We start with the first setting which is closer the notion of mixed distribution above. We consider distributions Dz.... D,, such that distribution D, is uniform mixture of cycle task samples of sizes 2, 3, (e.g.. Dn is the mixed distribution used for the mixed distribution setting of Figure 8a). We start training on D2 and we change training distribution from D; to D;+1 when reaching a 95% accuracy on D.. The results for this curriculum setting are provided in Figure 8b. Comparing this
13 For example, for i = 3. distribution OOD 3 consists of graphs with 4 cycles of size 6 where the nodes are in a single cycle and their distance is 3 and graphs with 5 cycles of sizes 3,3,6,6,6 where the query nodes are in the two cycles of size 3.
23

---

1.0
0.8
0.8
cycle
Accuracy
0.6
cycle
0.4
0.4
0.2
0.0
0.0
10000
20000
30000
40000
50000
60000
10000
20000
30000
40080
50000
60000
Iteration
Iteration
(a) Mixed distribution of different sizes training time.
(b) Curriculum learning during training where pre- vious samples are repeated avoiding them from being forgotten.
Figure 8: Accuracy for cycle tasks of varying sizes where mixed distribution (left) and curriculum learning (right) have been used during training. can be seen that using both a mixed distribution of samples with different difficulties and curriculum learning can reduce the learning time.
1.0
50000
task size
Ittraaions to leam
40000
Accuracy
0.6
30000
0.4
0.2
10000
5000 10000
15000 20000 25000 30000 25000
Iteration
Cycle task
(a) Accuracy curves for cycle tasks of different sizes when curriculum is used. We see that this version of the curriculum where do repeat the samples, samples from the previous dis- tribution are indeed forgotten by the model.
(b) Average number of steps for learning the cycle task with curriculum learning where previous sam- ples are repeated and allowed be forgotten.
Figure Curriculum learning based on sizes of the task used training time. Here, samples of smaller sizes are allowed to be forgotten. The left plot presents accuracy for different sizes for single run while the plot on the right presents the average number of iterations required for learning using curriculum for different sizes.
curriculum setting the use of mixed distribution without curriculum (Figure 8a), we can see that curriculum learning helps the model reach high (e.g., 80%) accuracy slightly faster. Nevertheless, note that weak learning starts earlier in the mixed distribution setting, as the model is trained on samples of all difficulties from the beginning. The general observation that beyond using mixed distribution, curriculum is helpful for learning has been previously shown both thcoretically [94] and empirically [95].
Now, we move the second setting where we allow easier samples be forgotten. More precisely, we consider distributions D2..... Dn such that distribution D, is the distribution of samples of the cycle task of size (i.e.. 2i nodes and edges). Similarly, we start training on D: and we go from D, to Di+1 when reaching a 95% accuracy on D. We present the accuracy curves for single random seed Figure 9a. We further provide the average number iterations required to reach 0.95% accuracy for the cycle task of different sizes in Figure 9b. It can be seen that the time complexity for this variant of the curriculum method is lower than the former curriculum method at the cost of forgetting samples of smaller sizes.

---

6000
5000
Iterations to learn
4000
3000
2000
1000
80
160
240
320
400
Total number of bits
Figure 10: Learning the half-parity function (learning the parity of the first n/2 bits from the total bits) for different numbers of bits using scratchpad. learned efficiently as the number of bits grows. Note that the random seed of the experiment can cause some variation
be seen that the half- half-parity targets can be
number of iterations required for learning the parity.
In sum, using distributions with samples of a mixed difficulty and also curriculum learning can reduce the learning complexity. (E.g., they made cycle task of size learnable). Nevertheless, the scratchpad approaches are still significantly more efficient (see Figure 4a).
B.3 Learning parities with scratchpad
Consider n bits E1..... In E {-1,+1} with uniform distribution over the Boolean hypercube. As discussed in Section 3.1, learning the parity of any fixed bits is exponentially hard (e.g., an exponential number of iterations in n if the model size is fixed). Note that the globality is in this setting. Here, particularly focus on learning the parity of the first z bits with a scratchpad of cumulative parities as discussed in Section 3.1. In other words, we design scratchpad given by the sequence
1/1 = 11: 1/2 22 M/ = T232
Me+1 T4+14/h.
M1/2 = 22222 In/21
where the autoregressive globality is 2. With this scratchpad of cumulative parities, we expect the half-parity function to be learned efficiently. We confirm the latter empirically Figure 10. It can be seen that our decoder-only Transformer can efficiently learn half- hali-parities of growing sizes (e.g., parity of the first 200 bits from 400 bits is the rightmost data point). We note that we have repeated each experiment for 10 different random seeds and we observed that the number of iterations depends on the the random seed of the experiment. Nevertheless, for all of the seeds, the parities are learned efficiently with low number of iterations.
B.4 Length generalization for the parity task
Here, we provide an inductive scratchpad for the parity task which makes length generalization possible. We focus on the full parity problem, i.e., given sequence of Os and 1s determining whether the number of 1s is even (output 0) or odd (output 1).
First, we explain the input data format. We fix an ambient dimension damb and also assume that have n < damb bits. Then, we choose random positions among damb possible ones and embed the input in dimension damb- For the unused positions, we use a placeholder token such as space or, here, for better presentation, an underscore. An example for damb = 12 and = 6 could be _01_10_0___1_
We design the inductive scratchpad as follows. Assuming that input has n bits we define n + states for the inductive scratchpad. For i n, the ith state is defined
[<pointer>]
<vaile <value of the ith bit> sparity of the first bits>
25

---

where <pointer> determines the position of the ith bit and <value of the ith bit> is the value of the ith bit (which the model can learn to retrieve using the pointer) and <parity of the first i bits> is the cumulative parity of the first i bits that can be computed using its value in the previous state (parity of the first - 1 bits) and the value of the ith bit. For the last state, state n + 1, we use [damb]_ -, <finll parity><EOS> where final parity is equal to the parity of the first bits that is computed in state n. So, one can easily check that this scratchpad is of low globality and each state can be easily computed using the previous state and question. As example consider input _01_10_0_____ again. The inductive scratchpad for this example can be written as
<START> [1]0, 0# [2] 1# [4]1, 0# [5]0, O# [7]0, 0# [10] 1# [12] <<0SS>
where different states are shown by different colors. To show the length generalization ability of the
inductive seratchpad we set damb = 60. Moreover, we train on samples with up to n S Nusiin = 30
bits. Particularly, we use fresh samples and generate each sample such that the number of bits n has a uniform distribution over {1, 2....... ..0). We train our base decoder-only model for 2000
30).
iterations and we test length generalization ability for different number of bits between Nurain 30
and damb = 60. Results are reported in Figure 5a. As it can be seen the model generalizes well to inputs with 50 bits. We also observed that the generalization ability on longer sequences (e.g., 55
bits) is not robust and depends on the random seed of the model.
B.5 Length generalization for the addition task
Length generalization arithmetic tasks and particularly on addition has received surge of interest recently 36]. In this section, we focus on length generalization on the addition task where the model has seen the addition of numbers with up to Nirain digits, and the model is tested on more digits Nust.. In particular, we provide two formats for the data and scratchpad which allow the model to length generalize.
Inductive scratchpad using random spaces. The first format is similar to our solution for the parity length generalization problem. First, we fix ambient dimension damb. Assume, we want to add two operands with n S damb digits. We embed the two numbers and the plus sign + in a 2damb 1 positions. Between them, put spaces, or for better readability underscores. Also, put an = at the end. For example, for x = 94, y = 31 and damb = 4 we can have 94_ 94_+_3__1 3-_ Now we explain the generation of the scratchpad. First, we generate random sequence of tokens with size damh + 2 such that it begins with '$' e.g., $xgug6 we call this text ans [O]. Now, we enter the induction mode. For i >> 0, each state in the induction mode is given by
s [i]] [<pointer to the ith digit of x>] <ith digit of x> [<pinter to the ith digit of y>] <ith digit of y> <current value of the carry> <ans [i+]}>
where v y are the operands, the pointer is counted from zero, and ans [i+1] is computed inductively
ans [i+1] (<ith digit of x> <ith digit of y> <carry from the previous state> % 10) <ans [i] [:-1]>
In other words, at each iteration, shift the ans the right (and lose the rightmost token). Instead, we concatenate the ith digit of the summation to it from the left. So in general, the model has to increase the pointers in the scratchpad, read their corresponding values, and do one summation using them (and the carry in the previous state) at each reasoning step. The scratchpad ends when both numbers are finished. Note that the answer is always the string to the left of $ at the end of the text. Thus, the completed scratchpad for our example (where input is 94_ + +_3_____ 1=) can be given by
$Xgug6<START> [01] 4 [08] 1 1cOr5$xgag# [00] 9 [05] 3c 3c1r255xgu# [-1]_ [03] (00_0)__001200x0000000
where different states are represented in different colors. With this scratchpad format, Nurain 10, and damb = 30 we can generalize to numbers with up to 18/20 digits (depending on the seed). See the results in Figure 5b.
Inductive scratchpad using shifts. For the second solution, we also fix an ambient dimension. damb. Assume, we want to add two operands with n < damb digits. For input formatting, first
26

---

are concatenate a S to the left of the two operands. Next, for each operand, we generate a random text of size damb and concatenate to the left of the operands and call them x [0] and y [O]. Lastly, we use an = to finish the question. For the scratchpad, we first generate random text with damb + tokens such that the leftmost token is $. We call this ans [O]. Also, we use a variable for keeping the carry and we call it which is zero at the beginning. In this format of the scratchpad, we do not use the <START> token meaning that the input question is also treated as a state (and is forgotten by the future states). We define each state (i 0, i 0 corresponds to the question)
[i]
<x <x[i]>+<y [i]>aans [i] [c[i]
where x x[i], y [i] are computed by right cyclic shifts of x x[i-1], y [i-1] and ans ans[i], c[i] computed using
ans [i] (< (XI + <c[i-1]> % 10) ans [i-1] [ <c[i-1]> < 10) else
(x
[[i] = O if (<RMD (x (x1)x=x11)))+<<N(((((>-<>>
where RMD represents the rightmost digit operator. In other words, at each step, we shift both the operands and the answer with the difference that operand shifts are cyclic, while for the answer we always add one digit of the correct answer to it from the left (and lose one digit from the right). Note that the position of the digits that we are adding always remains the same. Also, the addition is finished when $ is the rightmost digit of both operands. When the addition is finished, we use one more state to output the final answer (possibly using the last carry variable). For example, for = 2 and damb = 4, $s$46+in$98 could be an input example. In this case, the scratchpad can be written
$kckn I (0wf=#$48ihh0--555511
lasttc//##1444eee #144$$c<E00S>
where different colors are used for different states, In the example above one can note that some part of the [o] is in the question and some part of it is in the scratchpad.
Note that the formatting required for the input of this scratchpad is stronger than the previous scratchpad. However, here can get much stronger length generalization. By setting damb = 30 and training on numbers with up to 4 digits, we can generalize to numbers with up to 26 digits and even 30 digits for some of the seeds (see Figure 5b).
For both addition methods, we sampled numbers with n S Nurain digits with a probability propor- tional to Nevertheless, we did not observe much dependency in the design of scratchpads for both addition and parity, we have used techniques such as inserting random spaces and embedding in fixed dimension. We note that this is unavoidable for the input as we have used absolute positional embedding for it. Nevertheless, we expect that by using an inductive scratchpad along with relative positional embedding and pre-trate pre-training, the same length generalization with fewer assumptions on the format of the input.
the distribution. Also, note that
would be able to achieve
C Experiment and implementation details
C.1 Architecture and datasets
In all of the experiments, we use GPT2-style [29] decoder-only Transformers and we train them from scratch in autoregressive manner with the cross-entropy loss and AdamW [96] optimizer. Our implementation uses the PyTorch framework [97] and is mostly built on NanoGPT's implementation [98]. In particular, our Transformers embeddings. For most experiments, we use small model with 6 layers, heads, and an embedding dimension of 384 which results in model with approximately 10M parameters." We only change the size of the model in Figure 1b where we use models with 8 layers, 8 heads, and an embedding dimension of 512 (approximately 25M parameters), and 12 layers, 12 heads, and embedding dimension of 768 (roughly 85M parameters).
causal attention masking and absolute learnable positional
For the cycle task, we use 1000 node names formatted like v123. For simplicity of analysis, regard each node name as a single token. Other than that and for the other tasks, we treat each character single token.
"The exact number depends on the task and the vocabulary size of it.
27

---

For the length generalization experiments, we realized that the performance of the model depends on the random seed of the network. So we repeated each experiment 10 times and reported the median of the results in the plots (along with other runs). For other experiments, we did not observe much variation between seeds and repeated each experiment 5/10 times and reported 95% confidence intervals. We used different Nvidia GPU devices for running our experiments including H100, A A100, and RTX4090. We approximate that the runtime for experiments presented in this paper is around 200 hours (excluding hyperparameter search).
Our code is publicly available at attpppss///attat..c.co/rr//////t coop///rpo//nadiiieeeeerraaaaaap
C.1.1 Hyperparameter tuning and sensitivity
In general, we tried different values for the learning rate (with different schedules), batch size, dropout, and weight decay. For different tasks, we have used the hyperparameters that were the most stable and fast. The most significant sensitivity is to the batch size. We often find that larger batch sizes help with the training to the point that some tasks cannot be learned with batch sizes smaller than 256." 15 Also, in the length generalization experiments, we observed that the experiments are rather sensitive the dropout and weight decay parameters. Generally, strong regularizations can increase the uncertainty of the models. Considering the large number of tokens in the scratchpad of the length generalization experiments and their sensitivity, this uncertainty can increase the probability of error. Of course, a weak regularization can also result in a worse generalization. In addition, for most of the experiments, we used either fresh samples or rather large number of samples as our objective is mostly measuring the time complexity or OOD generalization. The exact value of hyperparameters for each task is available in our code.
C.2 Implementation of the inductive scratchpad
Here we describe the implementation of the inductive scratchpad. Assume that the question and seratchpad sequence are given by Q<START>s [1] #s [2] #. #ss [k] <EOS>. Note that Q and [i]s can each contain a number of tokens. Moreover, note that Q can also include a part of the scratchpad besides the question. Anything that comes before <START> acts like permanent memory and the model can attend to it for the generation of all states. So for example, if there is some shared information between all states, it is more efficient to put it in the scratchpad before <START> rather than including it in all of the states. Note that, in general, our goal is to only learn the induction function. In other words, we want generate tokens of the ith state s [i] as if the sequence this point was only <<START>s [i-1]# #. We now explain how this can be achieved during training and generation.
First, we provide two solutions for training time. One simple way is to break the original sequence Q<START>s #s [2] # #s [k] <EDS> into
Q<START>s [1], <<START>#s [1] #s [2] .... Q<START>s [k- #s [k] <EOS>.
We also need to make sure that no loss is not computed for Q<START>s [i]# part of Q<START>s [i] [i+1]# for < i k which can be easily done using a loss mask. This approach ensures that the loss is computed once for the question and each state and also each state is generated from the previous state and the question in identical manner. Note that all of these operations are done once as a preprocessing step. Now, we describe a second imple- mentation method for the train time. We first duplicate each state other than the last state, i.e., Q<START>> [1] #s [1] #s [2] #s [2] # [k] <EOS>. Next, we group the consecutive states, rein- dex the position of the tokens, and design attention masks and loss masks as follows:
Tokens
D<START>
s [[]
s [1]#
s[2]#
s s[]]#
s[3]#
s s[k-1]# s [k] <EOS>
...
Loss
1
1
0
1
1
0
1
mask
Attention
0
1
2
3
group
Positional
1....,-- 1 1, 1....
1, + 1,...
( + 1,...
1 + 1....
indices
For some experiments, we increased the gradient accumulation steps instead of the batch size to get the same effect with less memory consumption.
28

---

where we have assumed that t tokens have appeared before the first state [1]. Note that this number may vary across samples. We can easily create an attention mask based on the attention groups. All groups only attend to tokens in their group and tokens in group 0 (everything that comes before <START>>. Also, using the loss mask vector, we do not compute the loss for the second copy of each state (where the loss mask is equal to zero). Also, for each state generation, we reset the positional indices of the tokens. Using the appropriate loss mask, attention mask, and positional indices explained above guarantees that the loss is computed exactly once for each state, and each state is generated based on the previous state and tokens before <START> (i.e., the question Q) in an identical manner. Note that both approaches that we discussed for the train time can be implemented easily for conventional Transformer models. Further, they do not change Transformer models' behavior on non-inductive samples. Our methods also work with both absolute and relative positional embeddings. Note that the first approach favors Transformers with a small block size (context length) and the second approach is more suitable when the block size is large. So based on the block size, a mixture of these two approaches can be used. In our implementation, we use the second approach as we do not have issue with the block size.
Now, we discuss token generation. Assume that we are generating the tokens of ith state s [i], i.e., Q<START>> [1] #s [2] s [i-1] # have already been generated. To have the inductive behavior, we need the model to generate tokens of s [i] using only the last state and the tokens before <START> Similar to the training time, this is achievable through using two methods. The first method is to change the input of the model, basically, we can give Q<START>s [i-1] # as the input to the model when generating tokens for [i]. Alternatively, we can keep the input intact and just use an attention mask that prevents s [i] tokens from attending to any token other than tokens of Q<START> and [i Similar to the training time, one also needs to reindex the position of tokens of [i-1]# and s [i]# # so that they appear exactly after Q<START>. Note that is still possible to do key-value (KV) caching [99, 100] increase the decoding speed. KV caching stores previous keys and values corresponding to the previous tokens and does not compute them again at the expense of the memory. Generally, for KV caching, we are only in trouble when going from (i 1)th state the ith state, because the current keys and values of tokens of s [ii-] are computed based on [i-2]. However, for the generation of s [i], we only attend to s [i-1] and do not want s [i-1] to attend to any of the previous states to conserve the inductive behavior. One solution to this problem is to compute the key-value pairs for tokens of [ii1] again with the correct positional indices and attention masking once we have the transition from s [i-1] to s [i]. Alternatively, one can always cache two versions of keys and values, one for the generation of the current state and one for the generation of the future state.
We note that in the inductive scratchpad, all the states except the penultimate one are ignored. As a result, the effective number of tokens is significantly reduced compared to the full scratchpad. Consequently, the inductive scratchpad works better for longer scratchpads and models with more limited context sizes and generally scales better.
Also, note that the inductive scratchpad can generally be used for a wide range of algorithmic tasks. For example, consider an algorithm with for loop that updates some variables. One can easily put the variables of the algorithm in the state of inductive scratchpad, and use the Transformer for computing the values at each iteration (and also determining the halting of the loop). The inductive scratchpad for the parity, addition, and cycle tasks all fall into this category.
C.3 Comparison with relative positional embeddings
In this section, we discuss whether it is possible to induce an inductive structure for the scratchpad using relative positional embedding [50, 51] instead of using the explicit inductive scratchpad format introduced in this paper. For an inductive structure to work, we want each state to be generated using only the tokens of the previous state and the question in an identical manner for different states.
More precisely, assume that the question and scratchpad are given by Q<START>s [1]#s [2]#...#* #s [k] <EDS> (one can also decide to remove <START> and to- kens). For simplicity, assume that the size of all states (i.e., the number of tokens in each state) is equal to T (where we also include
used). Relative positional embeddings compute the attention between two tokens based on their distance instead of their absolute positions in the sequence. Therefore, the attention pattern between s [i+1] and s [i] is similar to the attention pattern between s [i] and s [ii1], and one could hope for inductive structure to emerge.
29

---

There are a few obstacles, however:
1. The distance between the states and question tokens increases as each state is generated. However, in order to have an inductive structure, we want the attention pattern between different states and the question not to change. One could think of using encoder-decoder architectures where the question is in the encoder part and computing the aross-attention between states and the question ignoring the positions of the state tokens in the decoder part. However, even this approach would lose some information. I.e., the attention between the seratchpad tokens and the question tokens cannot use the position of the scratchpad tokens within state.
2. Most of the relative positional embeddings [52, 53, 54] allow tokens attend all other tokens. Even if one uses an attention mechanism that limits the attention to the D previous tokens, after L transformer layers, tokens of up to distance DL can attend to each other. So in general, it is most likely, that tokens of s [i] can attend to tokens of other states as well as tokens of s [i-1] which hinders the inductive behavior.
3. Similarly, assume that the Tth (last) token of s [i] attends all tokens of [i-1] including its first token. Note that the distance between the last token of state s [i] and the first token of state s [i-1] is 2T'
As result, the first token of [i] would also attend all tokens of [i-2] except the first one in a similar manner (because the distance between the first token of [i] and the second token of s [i-2] is 27 which undesirable.
Note that in the analysis above we assumed a fixed number of tokens per state. If the number of tokens in each state varies, issues like (2) and (3) above can become more difficult to handle for model that only relies relative positional embedding. To sum up, there is minor similarity between relative positional embeddings and the idea of induction in the scratchpad. Factors such as pre-training and the recency bias of attention may promote inductive behavior in the model to some extent. Nevertheless, there is no reason to think that the model can implement the inductive behavior relying only relative positional embeddings for general inductive task. In general, one can use the inductive scratchpad idea along with relative positional embedding to get better length generalization. Note that inductive scratchpad can generalize on the number of training steps. However, understanding an input with growing length still requires relying on relative positional embeddings.
As an alternative solution, independent of positional embeddings being absolute or relative, one can use special tokens <START> without hard-coding their meaning and hope the model realizes the meaning of these two tokens on its own and implement a soft inductive structure (same attention masking but in soft manner). However, such an event is also very unlikely for moderate amounts of inductive data.
D Further discussion and specification of Conjecture 1
Definition 6 (Well-behaver distribution for Conjecture 1). Input distribution Px over alphabet A with |A| = O(n)) is well-hehaved if for X ~ Px there is value that X takes with probability M(n-i for any ej >> O, and every eigenvalue of X 's covariance matrix of the indicator functions for the values of X entries has absolute value O(n EiT1 Var(X.)) for some 02 0.
In other words, the first requirement means that there is no value of X that is frequent enough that allows the model to weakly learn the function simply by memorizing the value of that input. The second rules out the possibility of an input distribution with a few important components that are easy to notice and determine the output, such as scenario where there are log(n) blocks of (nllog(nn)) bits such that all of the bits in block are always the same and the output depends only on the values of the blocks. Other than that, many distributions of interest are well-behaved, such as the i.i.d. measure as in [12, 25, 24, 28, 26, 27]. measures with dependencies for the cycle task considered in this paper.
Intuition on Conjecture To see the role of the histogram, Px, note that one removes positional embeddings from Transformer, the Transformer would become permutation invariant. In this case, learning functions like full parity (parity of all the bits) becomes very easy as there are only n + possibilities for n bits in the eyes of a permutation invariant model. One could potentially achieve
30

---

similar effect to removing the positional embeddings, if one initializes positional embeddings with a small enough (or vanishing) scale. That is the reason that Px needs to be included in the definition of the globality degree. Further see Appendix F for more intuition on Conjecture
E Intuition on the agnostic scratchpad
In a lot of the cases where there is scratchpad, we assume that during training we know what the Transformer should write in the scratchpad and just need to teach it to do However, this tends to be an unrealistic assumption in practice. If we knew how to compute the appropriate scratchpad entries from the imputs then we could just give the Transformer prefilled scratchpad instead of training it to write the appropriate entries in the scratchpad. Admittedly, we could have a scenario where it is expensive for to compute the appropriate scratchpad entries and are hoping teach the Transformer to do for us, but there is a limited middle ground between it being cheap enough that we do not need the Transformer compute the entries and it being too expensive to compute the correct scratchpad entries for all the training data. The other case where we would know what the correct scratchpad entries were during training is if the training data already came with scratchpad entries, which could happen if our training data includes some kind of explanation, which might not often be the case.
So, we could easily have a case where we are trying to train a Transformer with a scratchpad but do not know what it should write in the scratchpad. In that case, it seems like the best available way to evaluate whether an entry the model wrote in the scratchpad is right or not is to judge it based on the end result of writing that entry. In other words, we define loss function for entries in the scratchpad by taking the scratchpad with that entry, extending it to a full scratchpad, and checking if the transformer ends up giving the right answer. This the mechanism behind the algorithm proposed in Conjecture 2 for optimizing the network based on agnostic scratchpads.
F Proof of Theorem 1
In order to prove that a T-regular Transformer cannot learn to distinguish between the case where there are 3 cycles and the case where there is only one, we will take advantage of the fact that the probability distribution of the positional embeddings is invariant under permutations of the embeddings. So, if such a Transformer could learn to solve this problem would also be able to learn version where an arbitrary permutation was applied to the inputs. However, we will show that no function has significant correlation with a random element of the orbit of this function under reordering of its inputs. That in turn will imply that Transformer trained by gradient descent fails to learn anything meaningful when trained on this function. However, before we do that we will need to consider the setup for the theorem more carefully. The input in this problem is a series of blocks, each of which specifies how a;-1, b,-1. and c connect to a,, b, and c,. So, each of these blocks can be viewed representing permutation in Sg. in which case their product will give the needed information the overall graph structure. We can effectively reorder these permutations by permuting the tokens in the input. So, in order show that permuting the tokens to show that the function taking the product of a series of permutations is largely uncorrelated to the function taking a product of the permutations in different order, which can be made rigorous as follows.
completely alter the function it suffices
Lemma 4. Let Px be the probability distribution on the subset of S with an even number of odd permutations and f : Sz > (-2,11 1} be the function such that f(X) is -2 if IT X; is the identity and otherwise. Next, select E {0, 1)/(m1)) uniformly at random. Then, let (111) (2i - 1, 2i). In other words, is the permutation that switches its (2i - 1)th and (2i)th inputs 2, is 1 and leaves them otherwise. Now, let f((x) (x(()) for all x. Then
LX ((X)I 2. 2-33
Proof. We start by considering a single pair of permutations a, o' drawn uniformly and independently from S₁ and comparing oa' to a'o. At this point, it is helpful to think of a and o' function on F
of the form ax + with a E [1, 11 and E 1,2. If (x)) = x + and a d'(x) xr D/ then
clearly o ood' o' o'o However, if or (z) + and o' (xx - + b' then ol (o(()) -- +b +
31

---

while (d(z))==z-bl b. The cases where - b are similar. So, conditioned on any fixed values of the signs of a and o' which at least one of them is odd, a''a-lo'' is equally likely to be any even permutation. That means that if this holds and o" is another random permutation of a known sign then the probability distribution of (aa'a", a"; a d'aa") is the uniform distribution on
pairs of permutations of the correct sign. That in turn means that conditioned on the signs of all of the elements of X and the value of 2, the values of f(X) and ('(X) are independent of each other unless X 1 and X2: are both even permutations for every for which value of z, Ex-Px[[(X) ['(X)] = 2 411 That in turn means that
1. So, for any fixed
E, xxExxxxI(((X) f f') 4- (17/32) (n- 1n-1)/21 < 28.2-5 2-
Corollary Let Px be the probability distribution on the subset of S3 with an even number of odd permutations and f Sz + 1-2,1} be the function such that f() is -2 if II; X; is the identity and 1 otherwise. Next, select {0, 1]1(=11//2) uniformly at random. Then, let IIsg (iis((n11))))) (0--1)22:0000 12/2| (2i - 1, 21). In other words, π the permutation that switches its (2i 1)th and (2i inputs if 2; is and leaves them otherwise. Now, let f'(x) = f(((2)) ( for all x, and let g 5g 1- 1] be a function. Then
π =
E, g(X)] 3.22
Proof. First of all, let (z', (") be drawn from the same probability distribution as (z, n, J') but independently of it. We have
Eg, Ex-e 10 (X) ['()]] = E (f
= E,, Exxxx (((()))((((((()))))()(
8 n-n/3
Using the inequality that given a fixed vector and probability distribution over vectors Pu. F Fuwry (w u) S 110112 V.a.uun.. [u w')3,, which follows from
Eu~P,,(u u
Fawpy [Vv 60 v) (u v)
(v -mm-p_
S ||U @ u||2|| [uu u)]l(z
=11u1B2 Fu (u u')
where u and n' are drawn independently from P, in the last expectation, we have
(((x) (
< xxxxx [x(( E, (xxP)11((xx-000)
< 8 2-n/3
At this point, we are finally ready to prove Theorem I as follows.
Proof. First, observe that in the setup in Theorem 1, an input consists of a series of blocks where the ith block specifies where the edges from a;-1, by-1. and C--1 go. These edges always go to a, b, and o in some order (Regarding a,, b,, and c, alternate names for ag. by. and cg). So, each block can be viewed as permutation in 53. Call these permutations dI...., Jn. The first n of these permutations are mutually independent, but the requirement that there be 1 or 3 cycles rather than forces the last one to take on a value for which their product is even. If there are 3 cycles their product the identity and if there is one cycle their product one of the other even permutations with which it is determined by whether the vertex edges from do is by or cp- So, the probability distribution of a the uniform distribution on the subset of Sy with an even number of odd permutations and the label specifies whether or not Th= oe is the identity.
32

---

The positional encodings are iid and there is no causal masking, so the probability distribution of the Transformer is symmetric under permutations of the inputs. In particular, for an arbitrary permutation E S,, we can move all of the letters in block i to the corresponding position in block л (i) for each i
to essentially apply this permutation to the a. Now, let Y be the indicator function for I oe being
(2i - 1, 21) and the identity. Then, for every select 2 E (0,1)[m--))/) 1)/2) let π= = [ (o-1))))))
Y, be the indicator function for Ih Tn (6) being the identity. By the symmetries of the Transformer, it will have as hard a time learning to compute Y as it would have learned to compute Y, for any z. Next, let Ya be 1 with probability 1/3 and 0 with probability 2/3, independently of X. We claim that the probability distribution of the Transformer's weights when it is trained on Y, will be essentially the same its weights when it is trained on Yg. In order to formalize that, let (2c) be the output the Transformer gives when its edge weights and positional encoding take on the values given by w on an input of xr Next, let Pw.a. be the probability distribution of the weights and positional embeddings after /. time steps of training on Y and Pw...t be the probability distribution of the weights and positional embeddings after time steps of training on Y,. For each t, Pwrp, is symmetric under permutations of the positional embeddings.
By the assumption on hyperparameters, we are using gradient descent with clipped gradient with some B polynomial in n such that if there exist (X, Y') for which any entry of the gradient of the loss with respect to the edge weights has absolute value higher than B it is reduced to = when calculating the overall gradient. Let ()x denote this clipping operator. For any given set of edge weights and positional embeddings w and a random 2, the expected square of the difference between the ith elements of the clipped gradient of the loss when the net is trained on Y, and the clipped gradient of the loss when the net is trained Ye is
dT(Y=, TTL(Y,TT<<M) (x))
dd. (
1)
E,
Ex
EX,Y
dw;
dw,
(Ys - 1/3)- (( (dII(1,TTmnx)
ILs
Lx
dwi
dw;
- (1/3) 3. 2- = (4B²/33 ~
n//6
by the previous corollary. There are a polynomial number of weights and small difference in gradients results in a total variation distance between the probability distributions of the weights one step later than is most polynomially larger, so for any t, we have that
Pw.0,e+1) S [VV Pw...)) + poly(n) 2 2
That in turn means that
TV TV(Pw... Pw..,.) = [TV D
Pw.o.)) = poly(n) 2 2-1112
for all & polynomial in Now, let yo be chosen to minimize the value of (I/3) mo) + (2, vo). Then, let L'(p. q) = min q), max(L(1, yo), L(O. yo)) for all p and y be a bounded version of the loss function. The previous argument shows that the expected bounded loss of the Transformer on (X, Y) after f. training steps is within poly(n). 2-n/12 of the expected bounded loss of Transformer trained on (X, Yo) for steps and then tested on (X,Y) which is
E Pw... [Ex (X))
EuwPi.o. [X
EmmPrro. El Wx,,, L' (X)II
(T..
= Pww.Pwo. [Ex.y, [L (Yo: (X))]
+ EwwPrre. [E,[Ex [(Y 11/3) (L,
2 F Fn Pw.o. [x Ex,yo [T' (Yo. sn)]l
[V VE - 1/3) (I'(1, (x)) - L'(0,T=
- -EnnPr.e.
-00) 0/2
as desired.
33

---

If we used batch gradient descent with a polynomial batch size instead of full gradient descent that would essentially add an inverse polynomial perturbation to the gradiens. In the version of this where we are storing weights and embeddings to a limited degree of precision then for large enough polynomial batch size the expected number of times this perturbation actually causes a parameter to get set to a different value than it would otherwise have is O(1/n). In this case, we could show that with probability 1 1-n
Remark 5.
there are at most log(n) cases of a weight being set differently than it otherwise would have as a result of the limited batch size. There are only 20(log" (m) choices of which weights get changed in which steps and how they are changed. For any one of these options the expected loss is still within poly(n). 2-nn/12 of what it would be if the net was run entirely on random labels. So, even assuming we end up with the best option the net will still have a loss that at best n -=11) better than that attained by ignoring the input and always returning yo- If instead of having limited parameter precision we instead have inverse polynomial noise we can still make variant of this argument but we would need to be more careful about exactly how the net differs when the perturbation to the gradient affects the results.
E.1 Extension to agnostic seratchpads
Theorem can also be generalized to Transformers trained with agnostic scratchpads in order to get the following.
Theorem 2. Lei G be a directed graph which consists of a cycle of length 3n with probability 2/3 and 3 cycles of length n otherwise. Next, if there are cycles pick one vertex from each and if there is one cycle pick three vertices that are each edges apart. Then, label uniformly at random these vertices with o b_0, c_O. Next, number every other vertex by the distance from one of these three to it, and for each i, label uniformly at random the vertices at distance by a_i, b_i, and c_i and store in X the edges between a_i- 1,b_i 1,c_i - 1 and a_i, b_i, i.e.
X = =O >
(ecci>ieec)) e(b Dbc
where e(v) represents the vertex that v's edge points to, all of the instances i or + 1 should have the appropriate value substituted in and the symbols in black should be used exactly as stated. See Figure 2 for an example. Finally, let Y report whether a a_0, b 0, c =0 are in the same cycle or not. Now, consider training a T-regular neural network with scratchpad of polynomial length on (X,Y) generated in this manner. For any given (X, Y), we will regard the net's 's loss on (X, Y) as the expectation over all possible scratchpads that it might generate X of the loss of its eventual output. If we train it on (X,Y) using population 16 gradient descent with polynomial hyperparameters 17 and a differentiable loss function then the network fails weakly learn to compute Y.
The proof of this theorem is not meaningfully different from the proof of the previous version, but for completeness we include it below.
Proof. First, observe that in the setup in the theorem, an input consists of a scries of blocks where the ith block specifies where the edges from 0;-1, b;-1, and G-1 go. These edges always go to a; b, and oj in some order (Regarding a., bn. and c, as alternate names for ag. by, and cg). So, each block permutation in Sz. Call these permutations 01, on. The first
can be viewed permutations are mutually independent, but the requirement that there be 1 or 3 cycles rather than 2 forces the last one to take on value for which their product is even. If there are 3 cycles their product is the identity and if there is one cycle their product is one of the other even permutations with which it is determined by whether the vertex edges from ao is by or cp- So, the probability distribution of o is the uniform distribution on the subset of Sy with an even number of odd permutations and the label specifies whether or not IT= 0 the identity.
1 of these
The positional encodings are iid and there is no causal masking of the original input, so the probability distribution of the Transformer is symmetric under permutations of the inputs. In particular, for
Khhis would also be true for batch GD with batches of size n with chosen as a function of the other hyperparameters.
LL... either polynomial learning rate, polynomial clipping [12, 31J, and weights stored using logarithmic number of bits of precision and random rounding: for a < 6 < e 6 needs to be rounded to a or c then it rounds to e with probability (b- a)/(e (c a). or with polynomial learning rate, polynomial clipping and polynomial noise added to the gradients.
34

---

an arbitrary permutation π E Sn we can move all of the letters in block to the corresponding position in block xi)) for each essentially apply this permutation to the d. Now, let Y be the indicator function for IT= 0; being the identity. Then, for every 2 E {0, ( 1)/2] let 2i) and Yz be the indicator function for II; (() being the identity. By the symmetries of the Transformer, it will have hard a time learning to compute as it would have to learn to compute Yg for any 2. Next, let Y be 1 with probability 1/3 and 0 with probability 2/3. independently of X. We claim that the probability distribution of the Transformer's weights when it is trained on Y; will be essentially the same as its weights when it is trained on Yg. In order to formalize that, let (1:) be a random output the Transformer with scratchpad gives when its edge weights and positional encoding take on the values given by w on an input of x. Next, let Pw,d, be the probability distribution of the weights and positional embeddings after / time steps of training on Yo and Pw.z,t be the probability distribution of the weights and positional embeddings after l time steps of training on Y.. For each I, Pw.o, is symmetric under permutations of the positional embeddings.
TT 1I<s((--1)/2)=== (2i
By the assumption on hyperparameters. we are using gradient descent with a clipped gradient with some B polynomial in n such that if there exist (X, Y) for which any entry of the gradient of the loss with respect to the edge weights has absolute value higher than calculating the overall gradient. Let () denote this clipping operator. For any given set of edge weights and positional embeddings w and a random 2, the expected square of the difference between the ith elements of the clipped gradient of the loss when the net is trained on Y, and the clipped gradient of the loss when the net is trained on Yg is
reduced to = when
(
ddLY,; (X))))
dL To (X))
27
F.
E Ex.Tu(x)
13 EXT.
dw;
dw;
= = (xxTx()) (82-1/3) (( (II(1,
[dL(O,TT (X))
dw;
dw,
B
< (1)3) 3. 2- = (3B²/3)- 2
by the previous corollary. There are a polynomial number of weights and small difference in gradients results in a total variation distance between the probability distributions of the weights one step later than is at most polynomially larger, so for any t, we have that
[T Puol..t1)) S [TV Pw.,,d) + poly(n) 2
That in turn means that
TV Pw...)) =
= poly(n) 2 221112
for all t polynomial in n. Now, let you be chosen to minimize the value of (1, yo) + (2/3) so). Then, let L'(p.g) q) min( [(p, q), max(L(1, L(.,
for all p and g be bounded version of the loss function. The previous argument shows that the expected bounded loss of the Transformer on (X, Y) after t training steps is within poly(n). 2 n/12 of the expected bounded loss of Transformer trained on (X, Y2) for steps and then tested on (X, Y) which is
E PwrPo
(x))I
= EuwPwis. [E (x
EwwPP. Exx.T (L [L,
EmmPProd [E,, (XX,, L"Y,,,
- [ Ex).x
+ +EWNPWO [E -X
2 F FooP E (X,, (Vo.
EmpPreo [V (x (Y- 113)) -
Ex (LY,, v0)] 012
as desired.
35

---

G Comment on Lemma 1
For S such that |S| < n, X[S] is independent of Y, since the distribution of such subsets of edges is the same for both classes.
Let S be such that |S| n. Let Zş be the ternary random variable that records whether there is cycle or an open path on S. Then,
(I)
since I(X(S]:Y) - I(zs; = H( H(Y)Zs) and H(Y[X[S]) H()
= H(Y|X(S), 2s) since Zg contains all the information about X[S] that is dependent on Y. Hence,
- ()) H(Y) - Z(s)
(2)
1 2Y 1) 1) HY 1 2Zs 2) HY 0) 0)
(3)
~ - 0- 0 P +0) = P(Zs #).
(4)
Now,
P + 0) = P(3 a cycle on S) + P(3 an open path on S).
(5)
There is cycle on the graph is sampled from the two-cycle distribution and there are only two possible choices of eycles versus (²r) possible selections of edges, so
P(3 a cycle on S) = 2/ 2n
(6)
There is an open path on S if the graph is sampled from the one-cycle distribution and there are 2n possible selections of such paths for (2n) possible selections of the edges, so
22n n
P(3 open path on S) 2n/
Thus
(2n) n
V
P(Zs -2 2n)/
(2n)3/22-22 2n
(8)
2
Therefore, even for sets of size n, the mutual information is exponentially low, implying that glob D) greater than
H Discussion on circuit complexity connections
One approach we can use to analyze what we can learn with different methods is to consider the complexity class the problems that can be solved by algorithms of a given type. Constant depth neural nets with well-behaved activation functions and weights of size at most polynomial in the input length are limited to computing functions in (possibly nonuniform) TC", the class functions computable by polynomial-sized constant depth circuits built from AND, OR, NOT, and threshold gates. Likewise, constant depth Transformers with polynomial-siee sized weights, polynomial alphabets, and attention matrices whose entries rational with polynomial-sizeee numerators and denominators are limited to computing functions in TC
The next circuit complexity class above TC is NC1, the class of functions computable by polynomial-sized circuits of logarithmic depth that are built from AND gates on pairs of val- ues, OR gates pairs of values, and NOT gates. It has not been proven that NC * TC", but it is suspected to be the case. Among other things, the problem of determining whether product of permutations in S₁ is the identity permutation mutation is NC -complet, so TC" circuits cannot compute it unless TC NC Further- more, given any permutations σ1, O2,
some other specified even per-
Ss and random Po...., F' E Ss. it is the case that (rn-12 " ")),,, and (roa))) -1 ),... (rn-10m.,,5) is random string of permutations. So, computing the product of a string of permutations is essentially as hard in the average case in the worst case.
σ 02 on ro 1 (1oa1r
36

---

Now, one of these products of permutations can be converted to a graph as follows. First, the graph has a set of vertices representing the 5 possible imputs to the product, and another set of 5 vertices representing the 5 possible outputs of each permutation in the product. Each vertex has an edge to the vertex representing the value the next permutation in the product maps its value to, and there are edges from each of the final 5 vertices to the corresponding one of the first 5 vertices. If the product of permutations is the identity, then this graph consists of cycles of length n + 1, while otherwise has smaller number of cycles. So, determining whether or not the product of permutations is the identity can be reduced to determining which pairs of the first vertices are in the same component. Thus, if TC * NC then constant-depth neural nets and Transformers cannot determine whether or not two vertices in an arbitrary graph are in the same component with nontrivial accuracy.
On the other hand, with appropriate setup, deep neural nets, recurrent neural nets, and Transformers with scratchpads are Turing complete. Furthermore, they can simulate a Turing machine using resources polynomial in the number of steps the Turing machine runs for and the input length. So, with appropriate parameters these can efficiently solve any problem that it is possible to solve efficiently. A little more precisely, given a neural net where the input bits are 0 or 1, it is fairly easy to set a neuron to compute an AND, OR, or NOT of one or more previous values, so any circuit can be converted into neural net of at most equal size. Any efficient computation can be performed by polynomial-sizee sized circuit, so it can also be performed by a polynomial -izze deep neural net. Also, given a Turing machine in state where all entries in its tape that more than steps away from the head or heads are in their initial state, there is a circuit of depth (1)) and size ((n) that computes the next state of the Turing machine. That means that running a Turing machine for T steps an input of length n can be simulated by a recurrent neural net of size O(T + n) and T recurrences. Conversely, given neural net with reasonable activation function and subexponential edge weights, one can estimate the output of each neuron to within an exponentially small error in time polynomial in the size of the net.
The topic of the capabilities of a Transformer with a scratchpad is a bit more complicated. The work of [30] analyses the capabilities of a Transformer with constant-sized alphabet, constant depth, intermediate variables expressible in logarithmic numbers of bits, causal masking, and a form of hard attention where self self-attention operations always average over all previous entries that maximize the attention score. It shows that given an input of length n and scratchpad of length T such a Transformer can perform any computation doable in time T, and conversely that any computation such a Transformer can perform is doable in O + n² )polylog(T + +)) time and Ó(T + log(n)) space. They note that this means that Transformer with logarithmic length scratchpad is limited to performing computations in logspace, while a Transformer with a scratchpad of linear length can simulate a finite state machine, and Transformer with a suitably long polynomial length scratchpad can perform any computation in P.
TC versus logspace limitation. We now tighten the logspace result from [30].
Lemma 5. A constant-depth Transformer with intermediate values recorded to pelyomiall
accuracy, logarithmic length scratchpud, and constant alphabet size is still limited to computing functions in TCO
Proof. First, recall that one can compute the probability distribution of the Transformer's output on any given input in TC by a result of [16]. So, for any given partial scratchpad one can determine the probability distribution of the Transformer's 's output for the scratchpad's 's next entry with T T function. That means that one can find the probability that the Transformer would generate any given scratchpad in TC" by checking the probability that it outputs each entry when anverse-polynome polynomial accuracy. There only polynomial number of possible strings the Transformer could write in its scratchpad, so a TC' circuit can check them all in parallel in order to determine how likely they each are and then add up the contributions to the probability of each output from each possible scratchpad in order to determine the probability distribution of the Transformer's 's output.
on the previous
scratchpad entries and the original input and then multiplying them to inverse-
Connection between globality degree and NC We next show that, putting aside the histogram knowledge and using constant alphabet size, having low globality means having correlations with NC circuits, a class of circuit weaker than TC by constraining the number of fan-in to be constant (and not allowing for threshold gates).
37

---

Lemma 6. Let Px be a probability distribution over {0. 11"h and f: [0. - {0.1} be function. correlates non-trivially with a function computable in C if and only if gglob(f) (1) when X ~ Px.
Proof. The NC functions are exactly the binary functions that only depend on constant number of input bits. So, for any NC function g. there exists a set of input bits S such that [S] 0(1) and g( X) only depends on the restriction of X to S. That means that if has a nontrivial correlation with g then f(X) has a nontrivial correlation with X[S] and thus has globality at most |S|| O(1).
Now, assume that glob(f) = (I))) and choose with |S| - O(1) such that 1 [S) f(X)) = n -11),, Next, define the function g': {0, 13" + [0, 1] such that g (τ) = E[](X) = x[S|] for
all and g: {0, 13"h + {0,1] 1} such that
s(x) = {
if gx) F[((X)
otherwise
for all x E {0, 13". This function is in NC because g(x) depends only on 2|S]. Furthermore, the correlation between / and g
covar (f. 9)/ l//////ooo /ur((/)orr(f(
2 covar(f.g)
Ex ((x(X) (Xg(X)))((( E[S(X)I)
Ex (X) E(((X))(((X)) EIf(X'II
Ex (X) E(((X))) E[f(X)I)
2 Ex [(0 (X) - -E(S(X))
= n -(1)
as desired.
Experiments with ChatGPT
Height comparison. For n 2 1, we consider 3n + 2 people having different heights. We give the model 3n + 1 pairwise relations between the consecutive people (in order of height) in random order. Using this information, one can understand the order of the heights for all people by combining the given information. We ask the model about the relation between person example for
and 2n + 2. An
is
"Omar taller than Sara. Vlad is taller than David. Farah is taller than Omar. Sara is taller than Vlad. Is Omar taller than Vlad?"
where the answer is true. Note that to answer this question correctly one has to combine at least + 1 relations. Thus, the globality of the task is always larger than n. (The exact globality would depend on the tokenization.) We found out that ChatGPT (GPT3.5) fails at this task even for n = 1 (simplest case). Note that when working with the GPT3.5 model used the following prompt so that the model is able to use chain-of chain-of-thought reasoning: "You can reason if you want but make sure include yes/no your answer." Interestingly, GPT4 performs much better than GPT3.5. We also observed that it is often the case that when GPT4 answers correctly to the question, it orders people based on their height, very similar to what we in the scratchpad of the graph task. Motivated by this, we tested one more setting where we prompted GPT4 with "Answer only with yes or no." to avoid the of-in-of-thoughl reasoning. this case, as expected, the model couldn't solve the height comparison task for > 1. The results are shown in Figure 11.
38

---

1.0
0.8
Accuracy
0.6
0.4
GPT-3.5-turbo-0125 (with CaT)
0.2
GPT-4-turbo-2224444000 (with CaT)
GPT-4-turbo-222--04000 (no CoT)
0.0
n - showing the complexity of the task
Figure 11: For complexity n we have 3n + people and there are n people between the two names query (see example above). We found out that ChatGPT(3.55 can hardly go beyond the random baseline on this task even for n = while GPT4 performs much better. However, GPT4 does not CoT reasoning, its performance would be near random for 1. Note that used 1000 examples for each value of n.
39

---

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

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We gave detailed descriptions of the hypotheses required for the theory results to hold.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes].
The paper focuses on artificial data that can easily be reproduced, details of the exact models used are provided in the appendix. Further, our code publicly available at https: //g /ttp///ggtt.....// thub. com/ aryol/ hwtii/uiiiiiieeeeeee wnduetiie-scraatcppeee scratchpad.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
41

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes].
Our code (data generation, models, and training) is publicly available at https://github htmmm//rooo/nuutiveeeeee
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
onPolicy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. wwtpcccpppccpcppttcccccccccccttt wttp://giieeeeeeeeeeeeeee htteeee///oSSSeeeseeeeeeee ssi aesionoolccyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes].
Justification:
The appendix provides all the hyper-parameters and implementation details of our experiments. Further specifications are visible our code.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes].
Justification: We provide confidence regions experiments where varying the initialization or other random parameters made a difference in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
42

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes].
Justification: The appendix provides all details regarding model architectures and sizes, which are all small enough use only small number GPUs. We have also provided estimate of the resources needed to reproduce the experiments in the paper. For the hyper--arameter search, in one case, we used up to 128 A100s for 3 days and around 20 V100s for 15 days.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics attps://neurr/ ct/ccc//p//c hptpulic//thisssiiiddeeopoppppee
Answer: [Yes].
Justification: The paper only deals with artificial data, and thus is conform in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
43

---

Answer: [NA].
Justification: The paper is about foundational research aiming at better understanding reasoning capabilities and limitations of current approaches in that respect, with suggestions how to address them. It is not tied to any particular application deployment. Improving the reasoning capabilities machine learning approaches could eventually lead to negative purposes of course, but only in very generic sense and not in the short term.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: We used only artificial data and models that are either already open source or small enough to not convey any risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]..
44

---

The only external asset we used was to test some of our experiments on widely available versions of GPT models from OpenAl: GPT2, ChatGPT 3.5-turbo-0125 and GPT44turbo-2224--04-009
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswithcode thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
There are no new assets introduced in the paper, except the source code used to rum the experiments supporting the theory the paper (so as be able to reproduce them), all of which are on artificial data, which are also provided with the source code.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification:
The paper did not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
45

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: The paper did not involve crowdsoureing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
46


Reviews:
[{"review_id": "tZPxzXkaBz", "reviewer": "Reviewer_cmbZ", "summary": "This paper proposes the concept of a \"locality barrier\" and conjectures that transformers can (weakly) learn to solve a problem only if it doesn't have a locality barrier, i.e., doesn't require global reasoning (as specifically defined by the authors). They prove, in particular, that for the cycle task that they propose, there exists a locality barrier and that transformers struggle to learn it.\n\nThese results about learnability of Transformer models nicely complement recent literature on their expressivity.\n\nLastly, the authors propose the concept of an \"inductive scratchpad\", which takes the special form Q#state1#state2#... and uses attention masking, etc., such that predicting state5 from the entire prefix looks just like predicting state5 from Q#state4#, forcing models to learn an explicit state representation and to condition only on it in a Markovian way. The paper reports empirical results showing that when trained this way, models generalize better to larger input length.", "questions": "Please see notes about clarifications in the weaknesses section above.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The notion of \"locality barrier\" seems interesting and, to my (somewhat limited) knowledge, novel. The study of learnability in transformers is a good complement to recent studies on transformer expressivity.\n\n* The idea of \"inductive scratchpad\" is intuitive. (I assume it is novel, deferring to other reviewers on novelty.) Using masking to force models to pay attention only to the current state (and the full input) seems effective for certain problems, and experiments confirm this.\n\n* The intuitive claims / conjectures in the paper are supported by sufficient focused experiments.", "weaknesses": "* Intuitively, I don't quite see why global reasoning (as suggested by the proposed locality barrier) should, in fact, be hard for transformers. After all, full attention gives them access to the entire input and entire sequence of past states, in the case of a scratchpad. In fact, having \"all to all attention\" is one of the key distinguishing strengths of a Transformer model, compared to, say, RNNs. Could the authors clarify why global reasoning seems to be a fundamental hurdle?  (Note that some prior papers have noted *sequentiality* rather than global reasoning as a big hurdle.)\n\n* While the paper tries to be formal with theorems and conjectures, the way it is written is somewhat informal. E.g., conjecture 1 mentions phrases like *inverse polynomial edge* without full clarification, as far as I saw); Theorem 1 and Conjecture 2 are written in a very lengthy and verbose way (it would be more standard to define concepts in text, and then have a succinct theorem/conjecture about them).\n\n* The paper can use some more intuition. E.g., the remark right after Definition 2 (distribution locality) tries to explain what the definition is trying to capture. However, I still struggled to understand it fully. E.g., why exactly is the mutual information targeted to be $n^{O(-1)}, what's the role of the *histogram* of tokens, etc., can be better clarified. Lemma 1 is an important illustration of the notion of locality, but is stated with only a brief explanation. A sketch of the proof from the appendix would be valuable. In general, wherever proofs are deferred to the appendix, a mention of this in the main paper (ideally with a brief proof sketch) would be useful for the readers.\n\n* While the notion of an *inductive scratchpad* is nicely general, the specifics of the state are highly dependent on the problem at hand. The authors showed that if the notion of state is appropriately chosen, models are able to learn (and generalize) on the few considered tasks. What remains unclear is, whether appropriate notions of state can be learned for new tasks and whether this concept works well in the popular \"in-context learning\" setting.\n\nMINOR (typos etc.):\n\n* line 12: \"breaks the locality barrier\" instead of \"breaks the locality\"\n\n* line 45: did you mean test accuracy of more than 80% or test error?\n\n* line 85: [16] seems to be about chain of thought and relation to Turing machine based computation classes. Here and in some other places, did you mean the paper titled *The Parallelism Tradeoff: Limitations of Log-Precision Transformers* by the same authors? That work showed TC^0 as the bound, not TC^1, though the generalization you mention in line 171 is accurate.\n\n* line 193: I'm not sure why a_i etc should be uniform random. Shouldn't the vertex be labeled a_i (and not b_i) is it's at distance i from a_0?\n\n* line 307: did you mean \"as if the input was\"? (rather than \"as the input was\")", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. We address the rest of the remarks and questions below.\n\n> Q. Intuitively, why is global reasoning hard for transformers?\n\nPlease see first the global response. For more intuition: we train transformers using a gradient descent algorithm, which means we need to have a significant gradient in order to make progress. I.e., we need the target function to have a nontrivial correlation to the derivative of the function the transformer is currently computing with respect to at least one of its weights. If there is a constant-sized set of inputs that can be used to predict the target function with nontrivial accuracy then that means there is a low-degree polynomial in the inputs that is correlated with the target function, and we would expect at least some of the derivatives to be significantly correlated with it. However, if there is no such set of inputs then that means that no low-degree polynomial is significantly correlated with the target function. There are a superpolynomial number of uncorrelated high-degree polynomials, so the derivatives of the transformer with respect to its weights cannot be nonnegligibly correlated with a nonnegligible fraction of them. So, we will tend to be unable to learn the target function in that case.\n\n> Q. Terms like *inverse polynomial edge* in Conjecture 1 can be further clarified. Theorem 1 and Conjecture 2 are written in a verbose way.\n\nPlease see the general comments. We can split Theorem 1 and Conjecture 2 into a definition part first and then the theorem/conjecture statement to enhance the readability. \n\n> Q. The paper can use some more intuition. E.g., why is the mutual information targeted to be $n^{-O(1)}$? What's the role of the histogram. Lemma 1 can be further explained. A sketch of the proof from the appendix would be valuable.\n\nWe can certainly add more intuition, differing other parts to the appendix. Please see the general comment and the previous question’s answer as a starting point. Regarding Lemma 1’s intuition: if you see only $n-1$ edges in this task, then those $n-1$ edges do not tell you anything useful because you miss one edge to conclude that you have in fact a short n-long cycle closing, or instead a longer path in the (2n)-long cycle not closing. Because of the uniform distribution on how the vertices are labeled, the two scenarios are equally likely and you can thus not infer any useful information. This means that you need at least $n$ edges to get at best a non-zero correlation, so the locality is at least $n$. Further see Appendix E. \n\nThe role of histogram is also natural for the Transformer’s architecture. To see this, consider removing positional embeddings; the remaining architecture would see the input as a set, using the number of times each token is appearing. This effect can also be observed if for example positional embeddings are initialized small enough. As a result, Transformers can easily access the token count (histogram) information of the input. Here, the histogram is similar to the bag of words in the natural language processing domain. We will add more details on this. \n\nAlso, note that there is a sketch of proof at the beginning of Appendix D.\n\n> Q. While the notion of an *inductive scratchpad* is nicely general, the specifics of the state are highly dependent on the problem at hand. How can other inductive tasks be learned, in particular using \"in-context learning\".\n\nPlease see our general response on the broader applicability of the inductive scratchpad. In-context learning of new inductive tasks is indeed an interesting future research direction. We can imagine two settings for in-context learning of inductive tasks. (1) Having a normal pre-trained model (without the inductive scratchpad implementations or tokens). With the general advancement of LLMs, we think in-context learning of some inductive tasks may be possible. However, the family of such tasks will probably be limited as the model needs to see similar tasks to the target in question during pre-training. Also, the (OOD) performance of the induction would probably be much more limited than the architecture that enforces the inductive behavior. As seen in our paper, even training on standard scratchpad fails at OOD generalization. (2) The second setting is to have a model with inductive scratchpad (with the special tokens) pre-trained on other inductive tasks. In this setting, in-context learning of new inductive tasks seems more likely; nevertheless, this direction requires new investigations for future works.\n\n> Q. Line 85: Did you mean to cite the paper titled The Parallelism Tradeoff: … by the same authors? That work showed TC^0 as the bound, not TC^1, though the generalization you mention in line 171 is accurate. \n\nYou are right we will cite [The Parallelism tradeoff…] when there is no CoT, and you are also right it should say TC^0 instead of TC^1 there.\n\n> Q. In line 193, shouldn't the vertex be labeled a\\_i (and not b\\_i) if it's at distance i from a\\_0?  \n  \nThe 3 nodes that are at distance i from a\\_0, b\\_0, c\\_0 are randomly called a\\_i, b\\_i, c\\_i. If we always called the vertex i edges from a\\_0 a\\_i then solving the problem would reduce to checking if the next vertex after a\\_{n-1} was a\\_0, which would be easy to learn. Randomizing the names is necessary to make it harder. Naming the vertices in a manner that does not specify how far they are from a\\_0, b\\_0, or c\\_0 would probably make it even harder to learn, but it would not work with our current proof technique, so we are sticking with these vertex labels for now. And again, the original cycle task is also expected to be hard enough, but this would likely require even more proof technicalities.\n\n\n\nWe also thank the reviewer for the typos; we will fix them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SFzceFhlWl", "reviewer": "Reviewer_apUt", "summary": "In the context of Chains-of-Thoughts prompting, Transformer models can solve more reasoning problem when recording their intermediate reasoning steps on a 'scratchpad'. This paper attempts to formulate the hardness of reasoning tasks (i.e., locality barrier), and explore the limitation of 'scratchpad' in seq2seq (i.e., Transformer) reasoning. Three kinds of scratchpads (agnostic, educated, and inductive) are studied, and their effectiveness in breaking the locality barrier are empirically validated on a synthetic cycle task (against their locality degree).", "questions": "- line 229, 'Parity functions are known to be hard to learn []': I guess a reference is intended but missed here.\n- line 231, '(n-k) = w(1)': I don't quite understand what 'w(1)' means here. The whole sentence could use some elaboration. I believe another intended reference is missed as well.", "limitations": "N.A.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Given the emerging need of LLM reasoning, the studied subject is of great interest, both theoretically and practically.\n- This paper is mostly well-written and easy to follow. The mathematical formulation of locality degrees is natural.\n- I especially appreciate the introduction/formulation of the educated and inductive scratchpads (though I am not sure if they are first formulated by the authors or not). Unlike standard agnostic scratchpads, both educated and inductive scratchpads serve as theoretical testbeds and provide practical guidance for building effective LLM reasoning pipelines.", "weaknesses": "I don't see any major weakness except for that the formulated inductive scratchpads bear some similarity with a previous design of scratchpads based on dynamic programming (https://openreview.net/pdf?id=qHrADgAdYu). Some comparisons and discussions could be used here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. We address the rest of the remarks and questions below.\n\n> Q. What is the connection to the “Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective“ paper which considers dynamic programming tasks solved by scratchpad?\n\nThank you for introducing this paper, we will add it to our literature review. In comparing it with the inductive scratchpad part of our paper, the inductive scratchpad is indeed suitable for learning DP tasks. DP tasks can be implemented using a loop, and the inductive scratchpad can easily learn algorithms with loops. In order to learn such algorithms with loops one has to put all the variables/arrays that are updated in the loop in the state of the inductive scratchpad (including the counters of the loop). In that case, each state generated by the inductive scratchpad becomes similar to one iteration of the loop. The inductive scratchpads that we have provided for the parity, addition, and the cycles task can also be viewed as algorithms with loops. \n\n**Nevertheless, we clarify that the mentioned paper does not use induction or any similar idea.** Note that in our paper, we make Transformers behave inductively on such reasoning tasks with the introduction of two special \\<START\\> and \\<STATE\\> (also denoted as \\#) tokens and dynamic attention masking according to these new tokens. As a result, we obtain strong length generalization performances (e.g., almost double length for parity and addition tasks) while without the inductive scratchpad idea length generalization property is weak or absent (e.g., in the DP paper the length generalization is from 15 to 17/18). Further, note that the inductive scratchpad allows Transformers to work with reasoning tasks with longer scratchpads/contexts thanks to the dynamic attention masking. For example, the tasks considered in the DP paper have remarkably shorter scratchpads than the parity and addition tasks we have in our work and hence could be considered simpler for the Transformers. \n\nOn the theoretical side, the suggested paper focuses only on the representation power of constant-depth transformers. It shows that there are tasks that cannot be represented by constant-depth Transformers, however, they can be expressed by a constant-depth Transformer with a scratchpad. We note that our paper considers learnability hardness (beyond expressivity). For example, the cycles task can be represented by polynomial size transformers with logarithmic depth however cannot be learned by them as shown in Theorem 1. \n\n> Q. Missing reference on line 229.  \n\nThanks for noticing the typo. The intended reference was \\[12\\] (Emmanuel Abbe and Colin Sandon. Polynomial-time universality and limitations of deep learning. Communications on Pure and Applied Mathematics, 76(11):3493–3549, 2023).\n\n> Q. Line 231: What does $k\\wedge (n-k) \\= \\\\omega(1)$ mean? Elaborate on the whole sentence.   \n\nHere, by $k\\wedge (n-k)$ we meant $\\\\min\\\\{k, n-k\\\\}$ operation and by the little omega $\\\\omega(1)$ we meant any quantity that grows at any rate beyond constants (as $n$ scales). In other words, a parity function of degree $k$ is learnable in polynomial time only if either $k$ or $n-k$ is constant. Note that the locality of the parity task is also equal to $\\\\min\\\\{k,n-k\\\\}$ (because of the histogram). Therefore, the constant locality requirement is consistent with prior works on the hardness of parities. Note that in the locality definition, we have access to the histogram of all tokens, and as a result, the full parity $x\\_1x\\_2 \\cdots x\\_n$ has locality $0$. Thus, thanks to the histogram, the hardness of learning for $x\\_1x\\_2 \\cdots x\\_k$ (degree $k$ parity) and $x\\_{k+1} \\cdots x\\_{n}$ (degree $n-k$ parity) is similar, hence we use $\\\\min\\\\{k, n-k\\\\}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HJg1nbTYDU", "reviewer": "Reviewer_eJe3", "summary": "The paper investigates the conditions for Transformers to learn algorithms with length-generalization. The paper proposes a formal definition of “distribution locality” and conjectures that the measure is highly correlated with the capability of Transformers to weakly learn. The (inverse of) conjecture is theoretically justified in one particular case by showing that a class of graph classification problem with high distribution locality cannot be weakly learned. The paper then shows that scratchpads that reduces distribution locality can improve length generalization and inductive scratchpads which removes previous intermediate states from the context can improve length generalization.", "questions": "Is the graph classification task possible to be solved by a Transformer regardless of training procedure? In particular, does there exist a set of weights for a Transformer with log-precision, constant depth and heads that can solve the graph classification task for all n? This is quite important since the work is focused on the learnability of Transformers instead of expressiveness, which is greatly studied in prior works, but if the Transformers cannot express the task, then the learnability impossibility result seems trivial.\n\nAdditional comments:\nThe appendix section B repeatedly refers to $d_\\text{emb}$ and seems to use $d_\\text{emb}$ to denote the naximum length of the input string (i.e. prompt/question). However, $d_\\text{emb}$ typically refers to the embedding dimension (i.e. number of entries in the embedding vector) of every token. Why is there a relationship between $d_\\text{emb}$ and input lenth?\nIn appendix section B.2 “Length generalization for addition”, why is “First, we generate a random sequence of tokens with size $d_\\text{emb}$ + 2 such that it begins with ‘$’, e.g., $xgwg6 we call this text ans[0]” useful and necessary?\n\nDoes “pointer” denote a separate pointer token for each possible input position? Are “[00]” one single token or 3/4 separate tokens? What does it mean by the value of the ith bit ”can be retrieved using the pointer”, is this specially processed in the generation process?\nWhy does pointer retrieval operation not break the distribution locality? It seems that for different pointers the model need to copy different positions in the input (the pointer position), but distribution locality requires that the positions that affect the label is the same for any possible input. Doesn’t retrieving the ith position break distribution locality?", "limitations": "The inductive scratchpad requires that each reasoning step is only dependent on one previous reasoning step and the input. However, this is less realistic in more complex reasoning tasks such as mathematical reasoning.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides exact definitions for “Distribution Locality” as and states solid conjectures that connects between the measure and learnability. If proven, these conjectures can significantly advance our understanding of Transformers trained from scratch. The work also shows the connection between scratchpads/Chain of Thought and reduction of distribution locality, which could further our understanding on the success of CoT. The work presents a formal proof of an impossibility result for weakly learning Transformers, which to the best of my knowledge, is novel in the field since most prior works focused on limitations on expressivity.", "weaknesses": "The theoretical result does not rigorously prove the “negative side” of the conjecture, since it’s unclear what properties of the graph classification task make the problem unable to be weakly learned. Further theoretical connection is require to show the connection between distribution locality and learnability.\nThe presentation of the paper could be improved to facilitate the clarity and understanding of the core results of the paper. In particular, in section 2, the authors should consider using shortened/less formal definitions and remarks and putting extended versions in separate sections or the appendix. For example:\nConjecture 1: Can be shortened using “if and only if” instead of having 2 sentences for “if” and “only if”?\n\nRemark 2 seems loosely relevant to the main results of section 2 or the main flow of the paper. It is recommended to have a separate discussion section for these extensions and/or put them in the supplemental materials\n\nConjecture 2 is hard to understand on it’s own and is not explained from a higher-level perspective (i.e. exactly what is a agnostic scratch pad?). It’s recommended to provide a definition and it’s high-level explanation and shorten Conjecture 2 using the definition for better clarity\nIn Theorem 1, it’s unclear why are the label names a_i, b_i, c_i are necessary. It seems that the label names does not impact the correctness of the theorem and thus their descriptions can be removed for clarity of the theorem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. We address the rest of the remarks and questions below.\n\n> Q. Is the graph classification task possible to be solved by a Transformer regardless of training? This is quite important since the work is focused on the learnability of Transformers instead of expressiveness but if the Transformers cannot express the task, then the learnability impossibility seems trivial.\n\nYes it can express the task. As mentioned in the general comment, this is not a case where the failure comes from expressivity limitations. In the specific version of Theorem 1, the problem is equivalent to checking if a product of permutations in $S\\_3$ is the identity, which is solvable by a constant depth transformer. The versions with a less restrictive formatting of the input are probably not expressible by a transformer with log-precision, constant depth and polynomial size. However, we do not restrict ourselves to this specific regime, and our definition of T-regular allows an arbitrary polynomial depth, and a logarithmic depth transformer can solve the graph classification task by finding the vertex $2$ edges from each vertex, then finding the vertex $4$ edges from each vertex, and then finding the vertex $8$ edges from each vertex and so on and then combining those to find the vertex $n$ edges from some designated starting vertex and checking if it is the same vertex.\n\n> Q. Appendix B repeatedly refers to  $d\\_{emb}$ and seems to use  $d\\_{emb}$  to denote the maximum length of the input string. However,  $d\\_{emb}$ typically refers to the embedding dimension of every token. Is there a relationship between the two?\n\nHere we used embedding dimension $d\\_{emb}$ for the input space as in “a two-digit number embedded in a dimension $d\\_{emb}=5$ such as \\_6\\_1\\_”. In other words, we used embedding dimension as the number of tokens that the input uses given the random spacing that we use. **This is completely independent of the embedding dimension of the Transformer architecture.** You’re right that this is not an ideal notation. We will update this.\n\n> Q. In Appendix B.2 “Length generalization for addition”, why is generating an initial random answer ans\\[0\\] (starting with $ token) useful?\n\nWe generate a random sequence of tokens with size+2 elements starting with \\\\$ as ans\\[0\\]. In each of the steps afterward we shift ans\\[i\\] one unit to the right (losing the rightmost token) and concatenate the computed digit of the correct answer from the left, i.e., ans\\[i+1\\] \\= \\<computed digit of the answer\\> ShiftRight(ans\\[i\\]). Note that initializing ans\\[0\\] with a random placeholder text ensures that the length of ans\\[i\\] does not change during different generation steps. If we had initialized ans\\[0\\] with an empty string, then ans\\[i\\] would have had $i$ tokens. As a result, during the length generalization, the Transformer would have had to write tokens on the positions it had never seen during the training which is impossible as we train from scratch and use absolute positional embedding. Hence, the initial random text for ans\\[0\\] ensures that the Transformer will not see unseen positions during generation. We expect one can avoid this placeholder by using an appropriate relative positional embedding (potentially in addition to pre-training).  \nWe simply use \\\\$ as the first token of ans\\[0\\] so that the final answer can always be easily recognized (it’s the number left to the $).\n\n> Q. Does “pointer” denote a separate pointer token for each possible input position? Are “\\[00\\]” one single token or 3/4 separate tokens? What is the meaning of \"the value of the ith bit can be retrieved using the pointer\", is this specially processed in the generation process? It seems that for different pointers the model needs to copy different positions in the input (the pointer position), doesn’t that result in a high locality?\n\nIn this example, \\[00\\] has 4 separate tokens. In the examples of lines 594 and 629, each character is an individual token (other than special tokens \\<START\\> and \\<EOS\\>). **We emphasize that we do not do any processing for the pointers during the generation and all is learned by the Transformer model itself.** By retrieving, we simply meant that the Transformer can learn to generate the token that is appearing at a specific location indicated by the pointer. We will further clarify this part and the tokenization process in our revision. \n\nAlso, note that the pointer retrieval is a low locality operation in the setting that we consider and hence easily learnable. For simplicity, assume that we have 2 pointer tokens \\[pq\\] and we have $N$ potential tokens (t\\_0,..., t\\_{N-1}) for retrieving. Denote the output by $Y$. For simplicity also assume that the probability for retrieving each of these tokens is the same. In this case, the locality is 1\\. Indeed it’s enough for the model to attend to  t\\_0 to get a significant correlation with the output. More precisely, with probability $1/N$ (if the pointer is pointing to the first token), the output $Y$ will be equal to t\\_0. Hence, the mutual information $I(Y;t\\_0) = poly(1/N)$ (as we can determine $Y$ in $1/N$ of the cases based on t\\_0). Therefore, retrieving based on the pointer is indeed a low locality task. \n> Q. How does the inductive scratchpad work for more complex reasoning tasks such as mathematical reasoning?\n\nPlease see the global response on the broader applicability with a focus on math. \n> Q. The theoretical result does not rigorously prove the “negative side” of the conjecture.\n\nIndeed, we do not prove the “negative side of Conjecture 1” and are careful to never make that claim. We prove only a specific case falling under the negative side of Conjecture 1 that relies on this variant of the cycle task. We believe that this variant is interesting in view of prior lower-bound work as it does not follow from any previous papers providing negative results such as \\[12, 13, 28\\] (refs in our paper).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bH2znUNYik", "reviewer": "Reviewer_GsuG", "summary": "The paper contributes a new metric for measuring the difficulty of a task for a transformer model to learn, called distribution locality. This refers to the amount of an input x that needs to be seen by a model for it to be able to return the corresponding output y. A high locality means that a large amount of the input would need to be made available for the model to correctly predict y, while a low locality means that only some small part of x needs to be given to the model. \n\nThis represents a barrier in the kind of tasks that can be learned by transformer models, which the authors call the locality barrier. Above a certain threshold of locality a task becomes impossible for a given transformer to learn. \n\nTo overcome the locality barrier, the authors propose various scratchpads as tools that the model can use in getting to its answer. They demonstrate that naive and educated models are insufficient to overcome the locality barrier, but provide a new type of scratchpad called an inductive scratchpad which is able to overcome the locality barrier.\n\nThe scratchpads in the paper are essentially structures that the model trains on that help to format the answer in a way that helps the model arrive at the correct answer. During training the model is given input and output pairs where the output is structured according to a given scratchpad. The output of the model essentially consists only of the scratchpad workings and the answer. Each scratchpad type works by enforcing a certain structure on the steps taken during the working out process.\n\nThe inductive scratch pad works by trying to solve a problem at each step through iteratively applying the same learned rule repeatedly until an answer is found. The key is that each step is based only on the previous state and the original question. By applying this problem solving solution over and over again it is possible for it to learn to solve problems outside of its original training distribution.", "questions": "To what extent would training other transformer models be possible with this approach? For example, could this technique feasibly be used in language models? Some mention is given to various algorithmic tasks, but it is unclear to what extent these techniques are bottlenecked by current methods, and some discussion of how broader application may be done may help strengthen the paper. Particularly discussing scalability.\n\nDoes this approach generalise to other architectures at all?\n\nHow much does this approach impact compute demands if at all?\n\nCan you provide a step by step method for implementing this in other kinds of problems?\n\nCan you provide a more fleshed out discussion of impacts on the broader field and applicability to other problems?", "limitations": "The discussion of limitations is fairly clear in the paper discussing the fact that it primarily only applies to transformers, the limits of its generalization, and the fact that applying it to other problems is left as future work.\nHowever, discussion of implementation is not explicitly mentioned, and could be included to improve the discussion.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This paper offers many strong theoretical aspects and tackles some of the fundamental problems underlying transformers and cutting edge AI systems. \n\nOriginality:\nThe paper defines a useful and coherent metric for approximating the limits of learning tasks that a model is capable of, in distribution locality, and the mathematics underlying this idea seem sound. This idea is an intuitive explanation of the limits of transformers and is useful in predicting future model capabilities. \n\nThe idea of the inductive scratchpad, training the model in ways that inherently include a reasoning step, is a novel idea, and seems broadly applicable to many applications of language models.\n\nQuality:\nThe level of thinking displayed in the development of these ideas is very impressive, and shows a strong grasp of the problems at the heart of the field. The solution to the problem is both elegant, and argued convincingly, though applications at larger scales of models would have been very interesting to see.\n\nClarity:\nThe method of demonstrating the problem of distribution locality helps to make the problem clear, and the mathematics describing it are very clear and crisp. The tests and results presented are also a clear indication of the efficacy of the solution.\n\nSignificance:\nAs mentioned earlier, the problem being approached here is a fairly fundamental one in the domain of AI and of transformers in particular, and if the inductive scratchpad technique is able to generalize to other kinds of models may have a large impact on the way in which future transformer models are trained and can help with fundamental issues of memorisation vs generalization in model training.", "weaknesses": "The paper has good ideas but the language used in describing the ideas is often slightly awkward. \n\nFor instance we have this sentence: “This takes place for instance in the last 2 examples (parity and cycle task) where it appears useful to learn inductive steps when possible.” This sentence is awkwardly constructed because it is not immediately clear what “this” is referring to, and it feels roundabout in the way it makes its point. \n\nAn alternative construction could read:\n“The parity and cycle task examples demonstrate how inductive steps can be useful in solving problems, making them illustrative candidates for the inductive scratchpad.”\n\nThere are many such instances in the paper, and I think focusing on clear sentence construction would significantly improve the readability of the paper.\n\nThe examples given for the scratchpad outputs are very difficult to parse visually, and use different symbols between tasks which makes them hard to compare. If the components of the task were clearly broken down per example this would make it much easier to read, or if the same notation was used across examples. Potentially more human readable examples could have been provided alongside the technical outputs.\n\nThe use of some real world tasks with the different scratchpads would have significantly strengthened the claims of the authors. While the examples given are clear indicators of the efficacy of the inductive scratchpad it is still somewhat difficult to infer that the solution will scale.\n\nIt would have been useful to compare the inductive scratchpad to other state of the art capabilities for extending the reasoning of transformer models to give a better sense of the scope of the problem and the impact of the solution.\n\nThe paper also doesn’t offer clear implementation steps for how the inductive scratchpad might be implemented in other types of problems. The implementation as presented here seems quite tricky to apply to other common transformer applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer’s feedback on the writing of the paper, we will revise the paper accordingly to enhance its readability. In particular, we will use different colors alongside annotations for the inductive scratchpad examples to make reading and parsing them easier. \n\nFurther, note that we include the details of the implementation of the inductive scratchpad in Appendix C.2; does the reviewer suggest that we should move this to the main text? This may be challenging with the available space. \n\nPlease read the answers to the questions below. \n\n> Q. How would the inductive scratchpad scale? What’s the impact on the compute demands?\n\nThe inductive scratchpad approach can scale easily to larger models, datasets, and context lengths as it reduces the attention computations and the *effective* context size.  Assume, we have states s\\[0\\], …, s\\[k\\] in the inductive scratchpad. The inductive scratchpad enforces s\\[i\\] to only use the information of s\\[i-1\\]. This behavior can be either implemented by masking the attention between s\\[i\\] and all the previous states except s\\[i-1\\] or by trimming the states prior to s\\[i-1\\] manually. As a result, the inductive scratchpad actually reduces the ‘effective’ context size. Thus, this method can easily scale. Note that due to the reduced effective context length, one can also use less memory during both training and inference. We have already discussed the implementation of the inductive scratchpad and its efficiency in Appendix C.2 and we will further extend it focusing on its scalability.\n\n> Q. Does this approach generalize to other architectures and language models?\n\nYes, this approach is easily implementable for other variants of Transformers and language models. First, note that the inductive behavior is controlled by two special tokens: the \\<START\\> and \\<STATE\\> (denoted \\#) tokens. Thus, for inputs that do not require induction (such as normal text generation) the model would keep its default behavior (as it would not generate \\<START\\>/\\<STATE\\> tokens). Regarding the implementation, assume that we have states s\\[0\\], …, s\\[k\\]. As discussed in Appendix C.2, there are two methods for implementing the inductive scratchpad. The first approach is based on masking the attention between s\\[i\\] and all previous states except s\\[i-1\\] and reindexing the positions of the tokens of s\\[i-1\\] and s\\[i\\] as if s\\[i-1\\] was generated right after the question. This implementation would only require attention masking and reindexing of positions of tokens which is easily doable in all variants of Transformers (e.g., whether they use absolute or relative positional embedding). The second approach is also implemented by manually removing the states prior to s\\[i-1\\] for generating s\\[i\\] before giving the text to the model during inference and splitting the input into pairs of states (s\\[i-1\\]\\#s\\[i\\]) during training. The second implementation method only modifies the input/training data of the Transformer prior to feeding it to the model (for generation this is in the outer loop that calls the model for generating one token at a time) and hence would work with any Transformer model.   \n\nFinally, note that our current implementation is for the decoder-only Transformers as they are more common nowadays. Nevertheless, encoder-decoder Transformers can be handled in the same fashion. The only difference is that in the encoder-decoder models, the question (Q) is already separated from the rest of the tokens as it is in the encoder part of the architecture, this would make the implementation slightly easier as we can consider removing the \\<START\\> token. \n\n> Q. Can you provide a step by step method for implementing this in other kinds of problems?\n\nAs a large class, here we consider the algorithms that have a loop in which they update some variables/arrays until the answer is computed. To design an inductive scratchpad for such algorithms, we first put the input data of the question (e.g., a graph) and all other constant and permanent information before the \\<START\\> token so that the Transformer attends to this information in all of the generation steps. Afterward, we define the states of the inductive scratchpad to be all of the variables that are being updated in the loop of the algorithm (including the loop counters). Now, generating the next step/state in the scratchpad becomes equivalent to one iteration in the loop. For example for the cycles task, we keep the graph input as the permanent info in the question part before the \\<START\\> token. After that in each state, we keep track of the node that we are visiting in our search, this is equivalent to having a variable that keeps track of the current node of the search in a for loop. Also, the Transformer learns the termination condition of this loop which is reaching the source/query vertex. Similarly, for the parity/addition task (random space method), we keep the input as the permanent part before the \\<START\\> token. In the states of the inductive scratchpad, we keep track of the location of the corresponding digit(s) and their values along with other variables like the current value of the parity, carry, and the addition result. This is again, similar to a for loop that updates these variables in each iteration. Note that the inductive scratchpads for addition use some minor adjustment in the inductive scratchpad format, i.e., the initial generation of a random answer. This part is simply added for the length generalization of our experiments and to prevent scenarios in which the Transformer has to generate tokens for unseen positions during training (note that we train our Transformers from scratch with absolute positional embedding). However, we expect one can skip such adjustment when using a pre-trained Transformer with proper relative positional embedding. \n\n> Q. Broader application and comparison of the inductive scratchpad?\n\nPlease see the global response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their constructive comments. We address some of the remarks and questions in the list below.

**I. On the “locality/globality” message:** this paper puts forward the claim \-with both theoretical and experimental results supporting it- that Transformers can efficiently learn (i.e., achieve non-trivial generalization of edge n^{-O(1)} or O(1) in at most polynomial time in the input dimension) if and only if the target at hand has constant *distribution locality*. The “if and only if” is discussed under some assumptions (e.g., regular distributions that prevent non-trivial learning by simply memorizing the output for a very high probability input, or largely scaling alphabet size). It is important to note that:

* **A constant distribution locality means that the target correlates weakly with a constant number of inputs, not that the target only depends on a constant number of inputs**. The target “weakly correlates” with some inputs means that the correlation is inverse polynomial with these, i.e., $n^{-c}$ for some constant $c$. This covers many functions that depend on many/all inputs, and that are thus “global” in that sense. For instance, the majority function of all the tokens correlates weakly at $1/\\sqrt{n}$ (because there is a $1/\\sqrt{n}$ chance that all the other inputs are tied up and flipping one makes a difference) with any single input, so its locality is at most 1, and in fact it is efficiently learnable by Transformers. Moreover, the formal definition of distribution locality allows for a little more than that, because there is also the histogram of all the input tokens that is given in the mutual information. This means for instance that the modular-sum target (i.e., sum modulo $q$ when tokens are on a field with $q$ elements, or parities when $q=2$), which does not correlate with a single input as opposed to the majority function, is still efficiently learnable because this time the histogram takes down the locality. The intuition of the histogram is that when a function is symmetric (permutation invariant) on the inputs, then the model can ignore the positional embeddings and just compute the function from the histogram which gives major dimensionality reduction (the histogram knowledge is similar to the bag of words in natural language processing). So indeed, Transformers can learn some tasks that are “global” in the sense of involving many variables. **The globality notion that we claim is truly hard for Transformers (the non-constant locality) means that no constant number of inputs (on top of the histogram) can even weakly correlate with the target**. Examples where this takes place are target like the modular sum of an unknown but fixed subset of say half the inputs, which was shown in prior works to be hard (experimentally or theoretically under technical assumptions, see refs in the paper). With our definition of the distribution locality, we can now capture many more target classes than this specific case, such as the cycle task, with a **precise, general, and concise definition**.    
  (Also we indeed allow here for all to all attention, as we want the model to be as general as possible.)  
* **The failure of efficient learning does not follow from a limitation of the model expressivity:** A regular Transformer as defined in our paper can in fact encode the cycle task of Theorem 1\. The reason why the model cannot learn efficiently is that it is trained by a descent algorithm with a random initialization. 

**II. Broader applicability of the inductive scratchpad idea.** We believe that the inductive scratchpad idea and more generally **the idea of dynamically masking the input based on the generated tokens to remove unnecessary information** will be helpful for reasoning tasks beyond the specific algorithmic/arithmetic tasks considered here. For instance, consider mathematical reasoning as raised by a reviewer. When proving a maths result, one typically breaks the argument with multiple steps, aka lemmas, that provide the dynamic flow of the proof. The proof of a new lemma $n$ relies on some of the previous lemmas from $1$ to $n-1$, but ideally the proof of the new lemma can be composed on the previous lemmas without requiring their proofs; otherwise, there exists a more composable proof that does not repeat unnecessary arguments. Thus, we expect that an approach that masks the unnecessary information (here, proof of the previous lemmas, or unnecessary lemmas which sometimes lead to an intermediate theorem) to be indeed useful for reasoning. In the inductive scratchpad framework, this corresponds to having states that only include all of the lemmas proven to the moment, the current objective (claim that the model is trying to prove), and the steps that the model is taking towards proving the current objective. **This should generally allow the model to handle computationally larger solutions/context sizes and better compose in OOD settings, thus eventually improving the model’s performance as was seen in the considered tasks.** Implementing this for more general tasks such as maths requires nonetheless major dataset preparations which is beyond the scope of the current paper.

**III. Formal and informal statements.** We had reviewers requests on both sides. We can write very formal and very informal versions of the results. For instance, Conjecture 1 informally reads as “Regular transformers can efficiently weakly learn a well-behaved distribution if and only if the distribution has constant locality”, while the formal version add all quantifiers: there exists $c_1,c_2=O_n(1)$ such that in time $n^{c_1}$ the Transformers trained by SGD (details of what this means) learns the target function with an accuracy $\geq 1/2 + n^{-c\_2}$, etc. Some may have to go to the appendix due to space limitations.

Meta-review: The authors propose the concept of a "locality barrier" and conjecture that transformers 
can (weakly) learn to solve a problem only if it doesn't require global reasoning. The authors propose 
various scratchpads as tools that the model can use in getting to its answer, including an 
inductive scratchpad which is able to overcome the locality barrier. The reviewers appreciated
the originality, but had some minor concerns about presentation.
Decision: Accept (poster)