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.
Paper
Similar papers
Peer review
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. This 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. To 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. The 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. The 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.
Strengths
This paper offers many strong theoretical aspects and tackles some of the fundamental problems underlying transformers and cutting edge AI systems. Originality: The 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. The 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. Quality: The 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. Clarity: The 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. Significance: As 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. For 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. An alternative construction could read: “The parity and cycle task examples demonstrate how inductive steps can be useful in solving problems, making them illustrative candidates for the inductive scratchpad.” There are many such instances in the paper, and I think focusing on clear sentence construction would significantly improve the readability of the paper. The 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. The 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. It 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. The 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.
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. Does this approach generalise to other architectures at all? How much does this approach impact compute demands if at all? Can you provide a step by step method for implementing this in other kinds of problems? Can you provide a more fleshed out discussion of impacts on the broader field and applicability to other problems?
Rating
7
Confidence
4
Soundness
4
Presentation
2
Contribution
3
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. However, discussion of implementation is not explicitly mentioned, and could be included to improve the discussion.
> Q. How does the inductive scratchpad compare to SOTA methods? The length generalization for tasks such as parity and addition has been studied rather extensively recently and overall the reported improvements remain fairly modest. We note that all of the proposed schemes have some additional conditions for their inputs and/or solution designs that are specific for the tasks (e.g., tailored positional embeddings). Our work trains the Transformers from scratch and uses absolute positional embeddings, however, we also ask for a mild condition on the input: random spaces for parity and additions. Since each work has its own modifications and solution design, it is not trivial to compare just the performance. However if one wants to compare the performance with a rough description of the approach, it would look like this: ### Addition work | performance | method and assumptions\ [1] | from 8 digits to 9 digits | Using NoPE (no positional embedding) \ [2] | from 10 digits to 12 digits | Scratchpad with recursive format\ [3] | from 40 digits to 50 digits | Reverse order of the output + ‘index hints’ (special tokens that go before each digit). An example looks like a5b4 + a3b7 = b1a9.\ [4] | from 5 digits to 15 digits | encoder-only model (no autoregressive generation) + relative positional embedding + padding inputs (input looks like 1 2 <PAD> + 3 9 <PAD>)\ [5] | form 40 digits to 60 digits | Fire relative positional embedding + randomized position encodings + reversed output + index hints (similar to the above input looks like a5b4 + a3b7)\ **Our random space method** | from 10 to 18 digits | Using random space in the input + inductive scratchpad. An input looks like 94\_+\_3\_\_1= (we use \_ instead of space for better readability). \ **Our shift method** | from 4 to 26 digits | Using a random text before each number + inductive scratchpad. An input looks like fs\\$46+ih\\$98. ### Parity work | performance | method and assumptions\ [1] | from 8 bits to 12 bits | Using NoPE (no positional embedding)\ [3] | from 30 bits to 50 bits | Using scratchpad + ‘index hints’ (special tokens that go before each bit in the input). An example looks like a0b0c1d1e0 > +c-d+\ [6] | from 8 bits to 20 bits | Using pretrained large models (128B) + prompting + fine tuning + scratchpad\ **Our method** | from 30 bits to 55 bits | Using random spaces in the input + inductive scratchpad. An input looks like \_01\_10\_0\_\_1\_ *(reported values are for median of the seeds, some seeds do better than others)* Therefore our solution requires one of the least stringent modifications of the inputs and provides a significant improvement of the length generalization compared to prior works. [1] The Impact of Positional Encoding on Length Generalization in Transformers, Kazemnejad et al. 2023\ [2] Positional description matters for transformers arithmetic, Shen et al., 2023\ [3] What algorithms can transformers learn? a study in length generalization, Zhou et al., 2023\ [4] Length generalization in arithmetic transformers, Jelassi et al., 2023\ [5] Transformers Can Achieve Length Generalization But Not Robustly, Zhou et al., 2024\ [6] Exploring Length Generalization in Large Language Models, Anil et al., 2022
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.
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. The 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: Conjecture 1: Can be shortened using “if and only if” instead of having 2 sentences for “if” and “only if”? Remark 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 Conjecture 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 In 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.
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. Additional comments: The 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? In 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? Does “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? Why 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?
Rating
5
Confidence
4
Soundness
3
Presentation
3
Contribution
3
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.
> Q. The presentation can be improved. 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: Conjecture 1: Can be shortened using “if and only if” instead of having 2 sentences for “if” and “only if”? Conjecture 1 is if and only if for constant size alphabets; we will update this; please see the global comment at the beginning in that regard. > Q. Remark 2 seems loosely relevant to 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 Thanks for the suggestion, we will revise the structure. > Q. Conjecture 2 is hard to understand on its own and is not explained from a higher-level perspective. We will break Theorem 1 and Conjecture 2 into a definition and then a conjecture/theorem to enhance readability. In the agnostic scratchpad version of the problem, we are giving the transformer access to a scratchpad but we have no prior knowledge on what the transformer should write in it. So, in order to train it to use the scratchpad well, we consider an entry it writes in the scratchpad to be “correct” if it leads to the transformer giving the right output at the end and “incorrect” if it does not and we define the loss of the scratchpad to be equal to the loss of the output. We can add more explanation to the paper. > Q. In Theorem 1, it’s unclear why are the label names a_i, b_i, c_i necessary? It seems that the label names do not impact the correctness of the theorem and thus their descriptions can be removed for clarity of the theorem. The justification for the vertex names in Theorem 1 is not trivial. In Theorem 1 the input is formatted in such a way that it can be divided into blocks that each specify how a_i, b_i, and c_i are connected to a_{i+1}, b_{i+1}, and c_{i+1} for some i (each corresponding to a permutation in $S_3$). Each block has 6 possible values and these blocks are independent except for the fact that their overall product is always an even permutation. If we were to change the way we assign labels to vertices in such a way as to make it so that the set of vertex names mentioned in a given block was not always the same then that would no longer be the case and the proof would require additional arguments.
author-reviewer discussion
Thank you for your review of this paper. The authors have posted rebuttals. Please could you enter into a discussion with them by replying to their rebuttal of your review. A simple 'Thank you for your rebuttal' acknowledges that you have read their rebuttal, even if you feel that their rebuttal does not require a detailed reply. Of course, a detailed reply is always preferable. Thanks! Area Chair
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).
Strengths
- Given the emerging need of LLM reasoning, the studied subject is of great interest, both theoretically and practically. - This paper is mostly well-written and easy to follow. The mathematical formulation of locality degrees is natural. - 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.
Questions
- line 229, 'Parity functions are known to be hard to learn []': I guess a reference is intended but missed here. - 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.
Rating
7
Confidence
2
Soundness
3
Presentation
4
Contribution
3
Limitations
N.A.
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. These results about learnability of Transformer models nicely complement recent literature on their expressivity. Lastly, 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.
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. * 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. * 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.) * 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). * 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. * 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. MINOR (typos etc.): * line 12: "breaks the locality barrier" instead of "breaks the locality" * line 45: did you mean test accuracy of more than 80% or test error? * 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. * 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? * line 307: did you mean "as if the input was"? (rather than "as the input was")
Questions
Please see notes about clarifications in the weaknesses section above.
Rating
6
Confidence
3
Soundness
3
Presentation
2
Contribution
3
Limitations
Yes
Reply to authors
I thank the authors for the careful responses to my questions. I hope that these can be used to clarify issues that I had questions about in the final version of the paper if it is to be accepted.
Many thanks for the detailed response!
Decision
Accept (poster)