Universal Length Generalization with Turing Programs
Authors: Kaiying Hou
David Brandfonbrener
Sham M. Kakade
Samy Jelassi
Eran Malach
Venue: ICML 2025 poster (2025)
Keywords: length generalization
deep learning
Primary area: theory->deep_learning

Abstract: Length generalization refers to the ability to extrapolate from short training sequences to long test sequences and is a challenge for current large language models. While prior work has proposed some architecture or data format changes to achieve length generalization, these proposals typically apply to a limited set of tasks. Building on prior scratchpad and Chain-of-Thought (CoT) techniques, we propose *Turing Programs*, a novel CoT strategy that decomposes an algorithmic task into steps mimicking the computation of a Turing Machine. This framework is both universal, as it can accommodate any algorithmic task, and simple, requiring only copying text from the context with small modifications. We show that by using Turing Programs, we obtain robust length generalization on a range of algorithmic tasks: addition, multiplication and in-context SGD. We then demonstrate that transformers achieve length generalization on random Turing Programs, suggesting that length generalization is possible for any algorithmic task. Finally, we theoretically prove that transformers can implement Turing Programs, constructing a simple RASP (Weiss et al.) program that simulates an arbitrary Turing machine.

Universal Length Generalization with Turing Programs
Kaiying Hou David Brandfonbrener" Sham Kakade
Samy Jelassi
Eran Malach
Abstract
Input: 9 o B
Length generalization refers to the ability to ex- trapolate from short training sequences long test sequences and is challenge for current large language models. While prior work has pro- posed some architecture or data format changes to achieve length generalization, these proposals typically apply to a limited set of tasks. Building on prior scratchpad and Chain-of of-Thhught (CoT) techniques, we propose Turing Programx, novel CoT strategy that decomposes algorithmic task into steps mimicking the computation of Tur- ing Machine. This framework is both universal, as it can accommodate any algorithmic task, and simple, requiring only copying text from the con- text with small modifications. We show that by using Turing Programs, we obtain robust length generalization range of algorithmic tasks: addition, multiplication and in-context SGD, We then demonstrate that transformers achieve length generalization on random Turing Programs, sug- gesting that length generalization is possible for any algorithmic task. Finally, we theoretically prove that transformers can implement Turing Programs, constructing simple RASP (Weiss et al. (Weiss al., 2021)) program that simulates an arbitrary Turing machine.
Target: <scratch> (A) 0
(8)
(N)
</acratch>
Figure 1. Turing Program example for simulating Turing Ma- chine with scratchpad.
et al., 2021; Chowdhery et al., 2023; Lewkowycz et al., 2022; Gunasekar et al., 2023; Touvron et al., 2023). De- spite these impressive abilities, transformers struggle with length generalization, which refers to the ability to gener- alize to longer sequences than seen during training (Abbe et al., 2023; Anil al., 2022; Jelassi al., 2023; Zhou et al., 2023). This limitation raises central question about transformers: are they capable of actually learning an al- gorithm or do they solve algorithmic tasks by resorting to memorization or shortcuts (Liu et al., 2022)?
Recently, several works have reported poor length gener- alization of transformers on a wide range of algorithmic tasks (Anil al., 2022; Delétang al., 2022; Dziri et al., 2024; Zhang et al., 2022). In parallel, myriad of papers (Jelassi et al., 2023; Kazemnejad et al., 2024; Shen et al., 2023; Zhou et al.. 2023; 2024) have optimized the data formats choice (see section 3 for details) to improve the length generalization of transformers when trained to per- form multi- addition of two numbers. While the recent progress impressive-
1. Introduction
Transformer-based language models have shown impressive abilities in natural language generation, reading comprehen- sion, code-synthesis, instruction-followingg commonsense reasoning, and many other tasks (Brown al., 2020; Chen
"Equal senior contribution. 'Department of Mathematics, Har- vard University, Cambridge, MA, United States 'Department of Mathematics, UC Berkeley, Berkeley, CA. United States Kemmpner Institute, Harvard University, Cambridge, MA, United States "Center of Mathematical Sciences and Applications, Harvard Uni- versity, Cambridge, MA, United States, Correspondence Kaiy- ing Hou <kaiying @ beds.ley.edus.
al., 2024) achieve almost perfect accuracy addition with 100-digit operands while trained on 40-digit, all these "tricks" are specific to the case of addition and may not generalize to other tasks. In contrast, our goal is to develop a technique that is general enough to enable length generalization on any algorithmic task.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Universal Length Generalization with Turing Programs
a RASP program (Weiss al., 2021) simulating Turing machines.
Table 1. Length generalization results on various problems with Turing Programs. We use to denote training on and generalizing to n = y.
In section 5, we demonstrate that Turing Programs are general and lead novel length generalization results in unexplored algorithmic tasks: multiplication by or 3-digit operand, SGD for linear regression, performing sequences of arithmetic operations, and Turing Machine simulation.
Problem
Generalization
Accuracy
Addition (n - n)
50 + 100 (2x)
98%
Multiplication (n x 1)
50 + 100 (2x)
97%
Multiplication (n x 3)
50 > 100 (2x)
97%
SGD (n examples)
50 + 80 (1.6x)
95%
To achieve this, we introduce Turing Programs, a novel scratchpad technique that may be applied to general algo- rithmic tasks. This technique is motivated by the operations of a Turing Machine, a mathematical model of computation that is capable of implementing any computable algorithm. A Turing machine consists of "tape" with symbols and "head" that, at each step, moves left right on the tape, and can read and write symbols in single tape cell. Therefore, when a Turing Machine processes an input, the tape at each step is a copy of the previous one up to a few changes. Our Turing Programs follow this philosophy by decomposing an algorithmic task into a series of steps. At each step we update a "tape" by copying the previous tape with a few elementary changes. We refer the reader Figure for the correspondence between Turing Machines and Turing Programs and to Figures 2 and 13, for examples of Turing Programs.
Related work
Length generalization remains an important challenge for large language models as underlined in several works (Delé- tang et al., 2022; Dziri et al., 2024; Hupkes et al., 2020; Schwarzschild et al., 2021; Zhang et al., 2022). Despite their advanced reasoning capabilities, transformer-based large language models struggle to process longer sequences than they were trained on (Anil et al., 2022). The main approaches for improving length generalization focus on changing the positional encoding and optimizing the data format.
Positional encodings for length generalization. Shaw et al. (Shaw et al., 2018) were early to notice that the weak length generalization of Transformers was due to the choice of absolute positional encoding. Following this, many al- ternatives were proposed to replace the absolute positional encoding: relative positional encodings, which focus on the relative distances between tokens (Dai et al., 2019); and weighted attention mechanisms in place of position embed- dings (Chi et al., 2022; Jelassi et al., 2023; Li et al., 2023; Press et al., 2021; Raffel et al., 2020). These alternatives showed substantial improvements in length generalization on natural language processing tasks. On the other hand, (Kazemnejad et al., 2024) found that causal language model with no positional encoding can length generalize better than some of these specialized positional encodings on algorithmic tasks. In this work, we apply the Hard-ALiBi positional encoding (Jelassi et al., 2024), that achieved state- of-the-art length generalization on the specific task of copy- ing, to more general algorithmic tasks.
Using the Turing Programs technique, we show that trans- formers enhanced with the Hard-ALiBi positional encoding (Jelassi et al., 2024)-a recent encoding that achieves state- of-the-art length generalization copying are capable of length generalization on wide range of algorithmic tasks. Our method achieves non-trive non-trivial length generalization on addition, multiplication and simulation of SGD steps (see Table 1). Additionally, we show that transformers can be trained to execute random Turing machines, extrapolating from 50 to over 100 input tokens, suggesting that our method can work for general algorithmic tasks. To our knowledge, these are the first results showing non-trivial length gener- alization on multiplication, and the first attempt to study length generalization on complex algorithms like SGD. We hope that this recipe will be further used to unlock novel length generalization on other algorithmic tasks.
Data formatting for length generalization. A wide range of data formatting methods have been introduced to achieve length extrapolation in algorithmic tasks. Scratchpad and Chain-of- Thouuht formats were proposed to learn arithmetic either through finetuning or in-context learning (Anil et al., 2022; Zhou al., 2023). When training from scratch, some other proposed techniques to improve length generalization on addition include: reversed formatting and random space augmentation (Shen et al., 2023), adding padding to the se- quence (Jelassi et al., 2023), and setting index hints in front of each digit (Zhou et al., 2023). Closer to our work, several
Our key contributions are summarized as follows:
In section 3, we present length generalization results on multi-digit addition using a Turing Program and Hard-ALiBs positional encoding.
In section 4, we present the Turing Program framework in full generality and its connections to Turing ma- chines. Additionally, we theoretically prove that trans- formers can implement Turing Programs, constructing
2

---

Universal Length Generalization with Turing Programs
works (Anil et al., 2022; Dziri al., 2024; Hu et al., 2024; Kazemnejad et al., 2024; Lanchantin et al., 2024) report that training or finetuning a model on scratchpad data does not yield any significant length generalization improvement. In our work, we demonstrate that length generalization is possible using a combination of a particular scratchpad vari- ant and a favorable positional encoding. Additionally, we develop Turing Programs, novel scratchpad strategy that is general and may be applied to achieve length generalization on any algorithmic task.
quences of tokens describing the task (e.g. addition, multi- plication) and outputs that are the corresponding solutions. We assume that the language model is allowed to generate (many) intermediate tokens before outputting the answer. Then formally, the length generalization problem consists of training a language model on inputs of length I L and solving problems of length > L at test time.
2.2. Scratchpad
It has been shown in prior work that the performance of LLMs on algorithmic tasks can be greatly improved by generating step-by-step solutions instead of immediately outputting the final answer (Wei et al., 2022b). Among the multiple methods described in the literature, we focus on the scratchpad method (Nye et al., 2021). Given an algorithmic task, this method encodes the intermediate steps of the algorithm as text and trains the model to emit them to a buffer that is referred to as the "scratchpad".
Neural networks and Turing Machines. Many prior works designed architectures inspired by Turing Machines (Dehghani et al., 2018; Graves et al., 2014; Kaiser & Sutskever, 2015). From a theoretical perspective, some works proved the Turing completeness of RNNs (Chen et al., 2017; Siegelmann& & Sontag, 1992), transformers (Bhat- tamishra et al., 2020; Chung & Siegelmann, 2021; Pérez et al., 2019; Wei et al., 2022a; Merrill & Sabharwal, 2023) and even linear next-token predictors (Malach, 2023) under wide range of assumptions. Lastly, another line of work characterizes the computational model that Transformers express: (Weiss et al., 2021) introduce RASP, human- readable programming language that can be implemented by transformers, (Lindner et al., 2024) show how human- readable programs are compiled into transformer models and other works (Giannou et al., 2023; Jojic et al., 2023) study how transformers can emulate computer programs. Closer our work, (Zhou al., 2024) hypothesize that Transformers can length generalization any algorithmic task that may written as a "simple" RASP program. In this work, we construct a simple RASP program that generates Turing Programs to simulate arbitrary Turing machines.
Nye et al. (Nye al., 2021) showed that scratchpad fine- tuning can be used to achieve strong in-distribution perfor- mance on execution based tasks such as code execution and computing polynomials. They also report modest length generalization results on integer arithmetic. The limitation of scratchpad training for length generalization is further highlighted in (Anil et al., 2022; Dziri et al., 2024; Hu et al., 2024; Kazemnejad et al., 2024; Lanchantin et al., 2024).
In this paper, revisit the use of scratchpad training to achieve length generalization on algorithmic tasks. We be- gin with the observation that the scratchpad technique can be realized as an iterative sequence of copying operations, where at each iteration the input is slightly modified. Build- ing on previous works showing that with the right positional encoding, transformers can achieve length generalization on the copying operation (Jelassi al., 2024), we hypothesize that combining the scratchpad technique with favorable positional encoding can unlock length generalization capa- bilities. We verify this hypothesis in section 3 and section 5, but first we review various choices of positional encoding.
2. Setting
In this section, present the length generalization problem and some instances where it appears. Then, we discuss scratchpad prompting (Nye et al.. 2021), a technique that lets the model generate solution steps before producing the final answer. Finally, we introduce various positional encoding methods and discuss their implications on length generalization.
2.3. Positional encodings
The inability of transformers to extrapolate to longer se- quences has been primarily attributed to the positional en- coding (Shaw et al., 2018; Shen et al., 2023). In this section, we review the different positional encoding schemes and in section 3, we report their length generalization performance. We review here specific choices for positional encodings that are known to perform well for length generalization, and discuss additional encoding schemes (such as absolute and relative positional encodings) in Appendix A.
2.1. Length generalization
Many sequence modeling tasks have problem instances of different lengths. Shorter instances are often easier to state, process and handle, and require less compute find the answer. By contrast, longer instances are more challenging to parse and require more compute to solve. Reasoning tasks such as multi-hop reasoning, program execution, deductive reasoning, and theorem proving fit in this category.
No Positional Encoding (NoPE). Decoder-only models with causal attention, as shown by (Haviy et al., 2022),
Algorithmic reasoning tasks consist of inputs that are se-
3

---

Universal Length Generalization with Turing Programs
acquire positional understanding, without explicit positional encoding. (Kazemnejad al., 2024) shows that model without positional encoding extrapolate better than those with specialized positional encodings on some algorithmic tasks.
which showed weak length generalization performance. As mentioned, there is long list of works that foeus on length generalization on addition (see Appendix B for a complete review). Notably, (Zhou et al., 2024) report somewhat better length generalization results compared to our results. How- ever, we note that these results rely on particular choices for the formatting of the input and the output, which are "tailored" for the task of multi-digit addition.
ALiBi. (Press et al., 2021) introduces this additive posi- tional encoding where the bias function follows b(i, = -rl²- - jl. where r > 0 is some hyperparameter. This
scheme has led to state-of-the-arl length generalization on
3.1. Length generalization on addition with Turing Programs and Hard-ALiBi
natural language tasks. However, (Jelassi et al., 2024) no- tices that it struggles at length generalization on the copy task and hypothesize that it is due to the slow decay of r.
In this section, we present our Turing Program scratchpad strategy for addition and report length generalization results.
Hard-ALiBi (Jelassi al.. 2024) introduce Hard-ALiBi an additive positional encoding where the bias satisfies b(i.j) -oo for j S i and j(i.j) 0 for j > i - m, for some hyperparameter m > O. Intuitively, with this hard thresholding, tokens can only attend to the m closest tokens. Different heads may have different values of m and some heads use m = oo which corresponds to softmax attention with no positional embedding at all (allowing for propa- gation of global information). The authors demonstrate empirically that models equipped with the Hard-ALiBi po- sitional encoding achieve remarkable length generalization on the copy task. In this work, we use the Hard-ALiBi posi- tion encoding to enable length generalization on algorithmic tasks as we show below.
3.1.1 EXPERIMENTAL SETUP
Data. We adopt the scratchpad format and write all the steps into one sequence, where steps are separated by a separator token. Figure 2 shows our scratchpad strategy for getting length generalization on addition not specified otherwise, our token space is of size 24 and made of V
(0, , 9, +, at....................... ^, BOS >>, < EOS| >, < >>} All the digits sampled uniformly as follows: we first sample the length of each operand (between 2 and L = 50) and then independently sample each digit. Finally, we "pack the context" with i.idd. sequences during training, i.e. we fill the context with multiple independent samples of the task (similarly to (Zhou et al., 2023)). We set the training context length 500. At test time, we evaluate our models using a sliding window: we generate tokens until the training context length (500) is filled, and then each additional token is generated by feeding the context of the most recent 500 tokens, effectively dropping all past tokens'. This way, we are able to generate very long sequences of tokens without training or evaluating on long context windows. To evaluate the accuracy at a given length, we test the model's 's output on 288 examples. We report the accuracy of exactly matching the desired output.
3. Length generalization on addition
Imput: 3 2 4 1
Target:
<ecratch>
3
4 2 1 J (13) added 4 9. carzy
1 (0,63)
added 2
6 carry
++4+ b (0,463)
# added 3 + 1 carry 0 a added + 0 m 4 carry 0
(0,4463)
6 3
</ecratch>
Model and Training. Our base model is 150M param- eter Transformer with L. = 12 layers, D = 1024 hidden size, feedforward layer with a hidden dimension of 4096 and H = 16 attention heads. The backbone of our model is based on the GPT-NcoX architecture (Black et al., 2022). We pick context length of 500 tokens. We use the Adam W optimizer (Loshchilov & Hutter, 2017) train the model with weight decay value of 0.1 and no dropout, for 200,000 steps. The learning rate schedule incorporates an initial 100- step linear warm-up, followed by a linear decay, starting at 7
Figure 2. Turing Program for addition, text in comments is not part of the input.
In this section, we address the length generalization problem for addition. We first review prior results on this problem and describe the techniques used in these works. We then demonstrate that Transformers trained with Turing Program scratchpads and Hard-ALiBi positional encoding achieve good length generalization performance, extrapolating from length-50 to length- 100 addition. This is a remarkable im- provement over previous length generalization results using the "vanilla" scratchpad technique (e.g. (Nye et al., 2021)),
Forr efficiency reasons, once reach the context length we advance the "window" by 20 tokens.
4

---

Universal Length Generalization with Turing Programs
Hard-ALiBi positional encoding. Similarly to (Jelassi et al., 2024), we use M masked heads and (H M) NoPE heads. In the masked heads, we respectively set the hyperparameter m to 1, 2.... and M. We swept over {3, 4, 5, 6, 7, 7. and found that M = 6 is the best choice.
modified copy of the previous one where few elemen- tary changes are applied, e-g- removing one digit for each operand and updating the intermediate result/carry. Since Hard-ALiBi yields robust length generalization copying, this may explain why we achieve better extrapolation than previous works that trained their models with seratchpad.
In this section, we generalize this approach and claim that every algorithmic task can be written as a sequence of mod- ified copy operations: i.e. copy operations with small and localized modifications. Such decomposition follows imme- diately from the standard construction of a Turing Machine, a universal model of computation. We therefore refer to this scratchpad strategy as a Turing Program. We start this sec- tion introducing the standard definition of Turing Machine, and then present Turing Programs, our scratchpad strategy for achieving length generalization on any algorithmic task. Lastly, we present our main theoretical result: Transformers can implement Turing Programs over long sequences of inputs.
100
80
Accuracy
60
40
HAID: + Direct
HAlB +
Taring Program
20
Turing Program
NoPE Turing Program
RoPE Turing Pregram
20
40
60
80
100
120
Length Number
Figure 3. Comparison of different positional encodings and data formats for length generalization on addition. We see significant extrapolation to longer sequenee lengths with Hard-ALiBi and scratchpad. The shade shows the 93% confidence intervals.
4.1. Background: Turing Machines
A Turing Machine (Turing, 1950) is a computational model that consists of an infinite tape* with cells, a head that can read from a cell, write to a cell and move left or right over the tape, and a set of rules which direct the head based on the symbol it reads and the current state of the machine, More formally, Turing Machine is defined follows.
3.1.2. RESULTS
In Figure 3 we show the length generalization performance of transformers trained to perform multi-digit addition us- ing the scratchpad described above. We compare the per- formance of different choices of positional encodings, as well as comparing to the performance on addition without scratchpad (directly outputting the answer).
Definition 4.1. A Turing Machine is specified as a quadru- ple T = (Q, 8) where: 1) Q is a finite set of states, 2) E is finite set of symbols, 3) 8 E Q is the initial state and f E Q is the final state, 4) 5 is transition function deter- mining the next move: d: (Q Σ) - (E x { Rý x Q).
We observe that by using ALBii together with scratch- pad, transformers are able to generalize well beyond the length of the training examples. In particular, the Hard- ALiBi model achieves a 98% accuracy at length 100. As shown by Figure 11 in Appendix C, the model also length generalizes well when the operands are of different lengths. In, Figure 8 in Appendix C, we analyze the robustness of length generalization performance different choices of ini- tialization seed. We observe that, while there is significant variance in performance when testing on longer sequences, our method is more robust compared to prior results (as reported in (Zhou et al., 2024)). Finally, we plot the per- formance of alternative data formats, such as the "index hints" from (Zhou et al., 2023), with various positional en- codings under the same experiment conditions in Figure 12 of Appendix C.
At the first iteration, the machine is set to state E Q. the head is on the first (leftmost) cell of the tape, and the input is written on the tape from left to right. At each iteration, the head on the i-th cell in the tape, is in state q E Q and reads the i-th symbol on the tape a. Then, if 8(g, a) = (a', D. g' the head writes the symbol a', moves in the direction D E {T., R). and the machine changes its state to g'. If the machine reaches the state f. it stops, and its "output" is written on the tape.
Turing Machines are powerful model for solving algo- rithmic tasks since (a) the framework is universal i.e. it is possible to write any algorithmic task in the Turing Machine formalism, (b) Turing Machines can solve a wide range of algorithmic problems- ranging from simple arithmetic to
4. Turing Programs
"We assume that the tape is unbounded from the right side, but bounded from the left. Namely, there are infinitely many cells to the right of the input, but no empty cells to the left. This is computationally equivalent tape that is infinite from both sides.
In section 3, we showed that Transformers with Hard-ALiBi trained on a specific choice of scratchpad format can length generalize to sequences that are 2x longer. On closer in- spection, each line in the scratchpad in Figure 2 is a slightly
5

---

Universal Length Generalization with Turing Programs
determining whether number is a prime (Agrawal al., 2004)-in polynomial number of steps. In the next sec- tion, we show how to use the Turing Machine formalism to obtain a novel scratchpad strategy that unlocks length generalization on any algorithmic task.
To avoid index operations, we leverage the n-gram hashing mechanism suggested by (Jelassi et al., 2023) as basis for the copying ability of transformers. In their construction, copying a string from the input was achieved by storing a sequence of n preceding tokens (n-gram) at each position, and iteratively retrieving the next token after the uniquely matched n-gram. Our Turing Program construction is very similar, except that instead of copying string from the input, we copy the next state of the Turing machine com- puted from the previous string. As in the construction of (Jelassi et al., 2023), our RASP program is limited to op- erating on inputs that have no repeated n-grams (i.e., no sequence of n tokens appears twice in the input), which can be guaranteed with high probability for uniformly random sequences of tokens of length S exp(n). Additionally, we require that the Turing machine does not generate repeated n- M-grams when processing the input, and that all the opera- tions of the Turing machine are applied in-memory". Under these assumptions, we get the following result:
4.2. Turing Programs: a universal scratchpad strategy for length generalization
The left panel of Figure represents the simulation of a Turing Machine and shows how the state, the head and the tape evolves with time. Note that at each time step, the state of the tape a copy of the previous tape with a few elementary changes such as a move of the head, an edit of single symbol and change of state.
The steps in a Turing Machine simulation are similar to a scratchpad strategy where each string is a copy of the previous one with a few modifications. Therefore, we claim that for any algorithmic task that can solved by Turing- computable algorithm, there is corresponding scratchpad strategy for solving this problem (as demonstrated in the right panel of Figure 1). We refer to this novel scratchpad strategy as Turing Programs.
Theorem 4.2. Let T be Turing Machine s.t. 1) T does not generate repeated n-grams and 2) T operates in-memory. Then, there exists a RASP program P of size (number of lines) O(n) s.t. for every input x without repeated n-grams, P correctly simulates T for exp(n) steps.
Turing Programs decompose an algorithmic task into a se- ries of intermediate reasoning steps. Each step is a "tape" that maintains the state of the machine, and the next step is copy of the previous tape with a few elementary changes, such as trimming of digits and update of carry/intermedi- ate result as in the case of addition and multiplication (see Figures? 2 and 13) or update of the parameters in the case of SGD on linear regression (see subsection 5.2). In section 5, we show how to use Turing Programs to unlock novel length generalization results on challenging algorithmic tasks.
We give the full code for the construction of such RASP programs in Appendix D.
5. Length generalization on other algorithmic tasks
Building upon the encouraging length generalization results on addition from section 3 and the Turing Programs frame- work from section 4, we show that Transformers enhanced with Hard-ALiBi may achieve robust length generalization complex algorithmic tasks. We show that our framework achieves length generalization multiplication by 1-digit and 3-digit operands, on SGD applied to linear regression, on performing sequences of arithmetic operations, and fi- nally, on next-state prediction of a random Turing Machine.
4.3. Theory: Turing Programs in RASP
To further motivate the use of Turing Programs to achieve length generalization on arbitrary algorithms, we prove that transformers can implement Turing Programs over long sequences of inputs. In particular, we show that Turing Programs can be implemented in RASP (Weiss et al., 2021), programming language that was suggested as an abstract description of the operations of a transformer. Following (Zhou et al., 2023), we use a restricted version of RASP that does not allow direct index operations, as (Zhou et al., 2023) hypothesized that RASP programs with index arithmetics may not length generalize". Therefore, our result should be viewed as transformer that can execute (most) Turing Programs (and hence, can simulate most Turing machines).
5.1. Multiplication by a fixed-length operand
Prior work. Multiplication is known to be a challenging task for length generalization and very few works report pos- itive length generalization results on this task. On pretrained models, (Zhou al., 2023) shows that elaborate prompt- ing techniques slightly improve the length generalization
construction of
'Namely, we assume that the head of the Turing machine does not go beyond the input sequence. We believe that this restriction may be removed at the cost of constructing a more complex RASP program. While this may seem like a limiting restriction, we note that this limitation can he easily mitigated by padding the input with random tokens.
OOur RASP program does not follow all the restrictions of the RASP-L language suggested in (Zhou et al., 2023), we do not restrict the tokens to have int8 values.
6

---

Universal Length Generalization with Turing Programs
of Codex on (n S m)mmlttiplication. (Dziri al., 2024) show that even fine-tuned GPT-3 struggles with performing 3-digit multiplication. On randomly intialized networks, (Lee et al., 2023) show that models can learn in-iitribution the 2-digit multiplication in a sample efficient way using scratchpad. (Shen et al., 2023) shows that with padding and reversed products it is possible to perfectly learn in- distribution 12-digit multiplication. (Jelassi et al., 2023) fo- cuses 3-digit multiplication and shows that when training and adding few examples of on (5 s--ddiittmultpplicati the model length generalizes (35 x 3) to (35 x miiipitmuliilliaaioon. In summary, prior work mainly focused on in-distribution learning of multiplication and did not manage to obtain length generalization results.
roughly the same ((n 1) has accuracy 97.1 % and (n x 3) has accuracy 96.8%), which demonstrates the generality of our Turing Programs framework. Both results are achieved with M = 7 masked heads and peak learning rate 0.0003. The head numbers were again chosen by sweeping over candidate numbers as before while the learning rates were chosen from the candidate set (, e-,,, 3e-4).
5.2. SGD on Linear Regression
160
Accurazy (84)
Data setup. Our experimental setup is similar the one in section 3. We focus on multiplication by fixed-length operand, i.e. (n
6.-
adigit-multiplication where the first operand has variable length n and the second operand al- ways has fixed length & E {1, 3} across all examples. We adopt the scratchpad format and write all the steps into one sequence, where steps are separated by a separator token. The Turing Program for multiplication described in Fig- ure 13 of Appendix E. Our token space is similar to the token space used in Section 3, using symbol instead of + and using an additional separator token ~., All the digits are sampled uniformly as follows: we first sample the length of the first operand (between 2 and 50) and then independently sample each digit. The remaining details of the training/test protocols are similar to those in section 3.
40-
Direct Arswer
HAlbl
"Tuing Progrem
Rurt luring hoggam
40
60
60
Size of Dataset
Figure 5. Length generalization on running the SGD algorithm, varying the number of examples.
In this section, we train a model to perform SGD and demon- strate its ability to length generalize. While in previous examples we varied the number of digits in the operands. here we instead vary the number of examples.
Problem Description. Let {(E,, beo))e........ with Z E TR2 and yi E TR be a dataset of size n. Given initial weights wo E R", we can obtain the final weight -n by performing gradient descent: W7 = w; XV w.. (3: - W, )²) where À is the learning rate. For our experiment, we pick x 0.5 and Wig = 0.
100
Accuracy (N)
60
x 1) HAlibi Turing Program In 1) Aliii Turngg Program
Tokenization and Data. We divide the interval [-1, 1] into 200 discrete tokens {ao, di,..., (199). As an input, the model receives sequence of n examples, each encoded as two input coordinate and one output (label) value. The model then needs to compute the iterates of the SGD algo- rithm when processing the data examples, starting from the last data point, and output the resulting weight vector Tn-1- A detailed description of the Turing Program for solving SGD is detailed in Appendix E.2.
NoPE+ Turing Program
In 1) RoPE + Turing Program
1) HAlbbi
0
50
70
90 100 110 120
Length Number
Figure 4. Comparison of different positional encodings and data formats for length generalization on (n x 1) D--ddiit-multiplican using the same hyperparameters. The shade shows the 95% confi- dence intervals.
Results. Unlike previous experiments, where we report accuracy w.r.t. exact string matching, here we allow the network to err by two quantization unit, counting any output that is within 2/100 from the ground-truth output (in foo norm) as correct. In other words, we disregard errors that may occur to differences in quantization of the real-valued iterates of SGD. As shown by the blue curve in Figure 5,
Results. Figure 4 reports length generalization results on (n x 1), while the plots for (n x 3) multiplications are shown in Figure 9 of Appendix C. We obtain robust length generalization by a factor x2 (from 50 to 100-digit numbers) on (n x 1) and (nx3 (3) multiplication. We note that, up to length 100, (n x 1) and (n x 3) multiplication perform
7

---

Universal Length Generalization with Turing Programs
training the transformer to perform SGD on dataset of sizes 50 generalizes with accuracy > 95% to datasets of size 80. Our HiBii model has M = 7 masked heads, a context length of 600, and was trained with peak learning rate 7 for 400, 000 steps with a batchsize of 16. For comparison, we also trained a model to directly compute the final answer as shown by the red curve in Figure 5. We observe that training the model immediately output the answer significantly degrades its performance.
100
20
40-
HAlbi
20
Aibi NoRE
RoPE
5.3. Sequences of Arithmetic Operations
30
40
50
60
70
00
Number of Celculations
In this seciton, we train model to perform sequences of Python arithmetic operations as shown below.
Figure 6. Lengthh generalization performance sequences of arith- metic operations.
x1 17
x2 11
Data setup. We first sample a random Turing Machine T with 5 states, 15 input symbols and a random transition func- tion (i.e., for every pair of state and symbol we randomly draw a triplet of state, symbol and move-direction). During training, each input example is generated as follows: we randomly choose an input sequence length between and 50, then randomly choose tokens, a random position for the head and a random state for the machine. At each step of training, we generate in an online manner a batch of size 16 of Turing simulations from T and focus on learning 1-step prediction: given the input tape, the model has to generate the output of the transition function followed by the next state of the tape. At test time, we evaluate the model on tapes of length L 2 50. Further details are in Appendix
x3 17
x4 = 15
= x4 x3
y y x3
y = y x1
print (y)
We vary the number of arithmetic operations before the final print (y) and test whether the models can generalize to programs with more number of operations than those seen in training.
5.3.1. IMPLEMENTATION
In our implementation, we always assign values to 20 initial variables x1,.. x20. Then we append n calculation steps, where n is a random length sampled from {1, 2, ..., 50} dur- ing training. The only operations involved are +, -, and +. We also make sure all initial and intermediate values are in the range of 0 to 20. For tokenization, our vocabulary consists of variable names, digits O through 9, arithmetic operators (+, -, and *), and various delimiters. We perform one line of calculation for every step of the Turing Program, while copying the initial value assignments and the unfin- ished calculation steps to the next block. An example of this Turing Program can be found in Appendix E.3.
100-
Turing Machine
Accuracy (%)
Turing Machine
60
Turing Machine 2
Turing Machine 3
Turing Machine
40-
Turing Machine 5
Turing Machine
Turing Machine 7
Turing Machine
Turing Machine
40
80
120
140
Length Tape
5.3.2. RESULT
Figure 7. Length generalization performance on 10 different ran- domly generated Turing machines.
As seen in Figure 6, training the transformer on data with number of calculation steps < 50 generalizes with ac- curacy > 97% to those with number of calculation steps n 80.
Results. Figure 7 shows that transformers enhanced with Hard-ALiBi predict almost perfectly the 1-step Turing Ma- chine transition of tapes that are 2 to 3x longer than those seen during training. Trained with a peak learning rate of 7 the models have M = 8 masked heads and a context length of 450. This experiment suggests that transformers may length generalize on arbitrary Turing Programs How- ever, this admittedly does not imply that transformers can
5.4. Turing simulations
In this section, we test the length generalization of transform- ers trained to predict the next state of an arbitrary, randomly generated, Turing machine. Our experimental setup is sim- ilar to the one in section except for the data as detailed below.
'We note that, formally, the experiment demonstrates the ability of transformers to learn in the "average case", but does not rule
8

---

Universal Length Generalization with Turing Programs
successfully execute Turing Programs for multiple steps, as accumulating errors might cause the programs to fail. That said, we note that in many cases we get length gener- alization with virtually zero error, suggesting that multiple steps of the machine can be execute while still maintaining accurate performance. The performance of different posi- tional encodings and data formats for Turing simulation can be found in Appendix C. We observed that both directly outputting the answer and using alternative positional en- codings significantly degraded the performance of length generalization.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
A Acknowledgements
This work has been made possible in part by a gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence. EM is supported by The William F, Milton Fund from Harvard University.
6. Discussion and Limitations
Studying and improving the length generalization abilities of transformers on algorithmic tasks has been the focus of various recent works. In parallel, it has been established experimentally that the ability of language models to solve algorithmic tasks is greatly enhanced when allowing them to use scratchpad/CoT data. Additionally, recent theoretical works demonstrate that transformers can use CoT to simu- late arbitrary algorithms (Merrill & Sabharwal, 2023), es- tablishing that they are computationally "universal". These results motivate to study whether transformers are univer- sal learners, able to learn from examples to execute arbitrary algorithms. Since algorithms are typically defined over ar- bitrary sequence lengths, we use length generalization as a measure of whether the model has learned the true algo- rithm. To establish this, we use the key observation that transformers can length generalize on the copying operation. Since executing algorithm can be implemented as se- quence of "smart" copy operations, the copying ability of transformers can be leveraged to achieve non- con-taiiial length generalization performance on a wide range of algorithmic tasks.
References
Abbe, E., Bengio, S., Lotfi, A., and Rizk, K. Generalization on the unseen, logic reasoning and degree curriculum. In International Conference on Machine Learning, pp.
31-60. PMLR, 2023.
Agrawal, M., Kayal, N., and Saxena, N. Primes is in p. Annals of mathematics, pp. 781-793, 2004.
Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V.. Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B. Exploring length generalization in large language models. Advances in Neural Information Pro- cessing Systems, 15:38546-35556 2022.
Bhattamishra, S., Patel, A., and Goyal, N. On the com- putational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006.09288 2020.
Black, S., Biderman, S., Hallahan, E., Anthony, Q., Gao, L., Golding, L., He, H., Leahy, C., McDonell, K., Phang, J., et al. Gpt-neox-208 An open-source autoregressive language model. arXiv preprint arXiv:2204.067455 2022.
That said, we acknowledge that our work still falls short of demonstrating that transformers can robustly length gener- alize any algorithmic task. In some of our results, the extrapolation to longer sequence length is not robust, and degradation in performance may appear shortly after mov- ing out-of-distribution. Additionally, our results rely on potentially very long and cumbersome CoT data, in a way that is not necessarily useful for real-world applications of language models. Thus, we view our results as theoretical evidence that length generalization is possible, and leave the development of more practical and robust methods for real-world length generalization to future work.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877-1901, 2020.
Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. O., Kaplan, J.., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. Evaluating large language models trained on code. arXiv preprint arXhv:2107.03374, 2021.
out the possibility that some "worst case" Turing Programs have much more restricted length generlization.
Chen, Y., Gilroy, S., Maletti, A., May, J., and Knight, K. Recurrent neural networks as weighted language recog- nizers. arXiv preprint 1rXiv:1711..540000 2017.
Chi, T.-C., Fan, T.-H., Ramadge, P. J.,, and Rudnicky, A. Ker- ple: Kernelized relative positional embedding for length
9

---

Universal Length Generalization with Turing Programs
extrapolation. Advances in Neural Information Process- ing Systems, 35:8386-8399, 2022.
Hu, Y., Tang, X., Yang, H., and Zhang, M. Case-based rule-based: How do transformers do the math? arXiv preprint 2xXi::2002.17709 2024.
Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C.,, Gehrmann, S., et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113 2023.
Hupkes, D., Dankers, V., Mul, M., and Bruni, E. Compo- sitionality decomposed: How do neural networks gen- eralise? Journal of Artificial Intelligence Research, 67: 757-795, 2020.
Chung. S. and Siegelmann, H. Turing completeness of bounded-precision recurrent neural networks, Advances in neural information processing systems, 34:28431- 28441, 2021.
Jelassi, S., d' Ascoli, S.. Comingo-Enrichh C., Wu, Y., Li, Y., and Charton, F. Length generalization in arithmetic transformers. arXiv preprint arXiv:2306. 15400, 2023.
Jelassi, S., Brandfonbrener, D., Kakade, S. M., and Malach, E. Repeat after me: Transformers are bet- ter than state space models at copying. arXiv preprint arXhv:2402.01032, 2024.
Dai, Z., Yang, Z.,, Yang, Y., Carbonell, J., Le, Q. V., and Salakhutdinov, R. Transformer-xl: Attentive language models beyond fixed-length context. arXiv preprint arXiv: /901. 02260. 2019.
Jojic, A., Wang, Z., and Jojic, N. Gpt is becoming a tur- ing machine: Here are some ways to program arXiv preprint arXiv:2303.14310 2023.
Dehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, E. Universal transformers. arXiv preprint arXiv: 1eXiv:18070038// 2018.
Kaiser, L. and Sutskever, Neural gpus learn algorithms. arXiv preprint arXiv:1511.08223 2015.
Delétang, G., Ruoss, A., Grau-Moya. J., Genewein, T., Wen- liang, L. K., Catt, E., Cundy, C., Hutter, M., Legg, S., Veness, J., et al. Neural networks and the chomsky hier- archy. arXiv preprint arXiv:2207.02098; 2022.
Kazemnejad, A., Padhi, I., Natesan Ramamurthy, K., Das, P., and Reddy, S. The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 36, 2024.
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for lan- guage understanding. arXiv preprint arXiv: 110.048800 2018.
Lanchantin, J., Toshniwal, S., Weston, J., Sukhbaatar, S., et al. Learning to reason and memorize with self-notes. Advances in Neural Information Processing Systems, 36, 2024.
Dziri, N., Lu, X., Sclar, M., Li, X. L., Jiang, L., Lin, B. Y., Welleck, S., West, P., Bhagavatula, C., Le Bras, R., et al. Faith and fate: Limits of transformers on compositionality. Advances in Neural Information Processing Systems, 36, 2024.
Lee, N., Sreenivasan, K.. J. D., Lee, K., and Papail- iopoulos, D. Teaching arithmetic to small transformers. arXiv preprint arXiv:2307.0338// 2023.
Giannou, A., Rajput, S., Sohn, J.-y,, Lee, K., Lee, J. D., and Papailiopoulos, D. Looped transformers pro- grammable computers. In International Conference Machine Learning, pp. 1 1139--11442 PMLR, 2023.
Lewkowyez, A., Andreassen, A., Dohan, D., Dyer, E., Michalewski, H., Ramasesh, V., Slone, A., Anil, C., Schlag, I., Gutman-Solo, T., et al. Solving quantitative reasoning problems with language models. Advances in Neural Information Processing Systems, 35:3843-3857 2022.
Graves, A., Wayne, G., and Danihelka, I. Neural turing machines. arXiv preprint 110541440..540,,200 2014.
Li, S., You, C.,, Guruganesh, G., Ainslie, J., Ontanon, S., Zaheer, M., Sanghai, S., Yang. Y., Kumar, S., and Bho- janapalli, S. Functional interpolation for relative posi- tions improves long context transformers. arXiv preprint arXiv:2310.04411 2023.
Gunasckar, S., Zhang, Y., Aneja, J., Mendes, C. C. T., Del Giorno, A., Gopi, S., Javaheripi, M., Kauffmann, P., de Rosa, G., Saarikivi, O., et al. Textbooks are all you need. arXiv preprint arXiv:2306. 1644, 2023.
Haviv, A., Ram, O., Press, O., Izsak, P., and Levy, O. Transformer language models without positional encod- ings still learn positional information. arXiv preprint arXiv:2203. 200..16634. 2022.
Lindner, D., Kramár, J., Farquhar, S., Rahtz, M., McGrath, T., and Mikulik, V. Tracr: Compiled transformers as a laboratory for interpretability. Advances in Neural Infor- mation Processing Systems, 36, 2024.
10

---

Universal Length Generalization with Turing Programs
Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shorteuts automata. arXiv preprint arXiv:2210. 10749, 2022.
Siegelmann, H. T. and Sontag, E. D. On the computational power of neural nets. In Proceedings of the fifth anmual workshop Computational learning theory, pp. 440- 449, 1992.
Loshchilov, I. and Hutter, F. Decoupled weight decay regu- larization. arXiv preprint arXiv: 2017.
Su, J., Ahmed, M., Lu, Y., Pan, S., Bo, W., and Liu, Y. Roformer: Enhanced transformer with rotary position embedding. Neurocompating, 568:127063, 2024.
Malach, E. Auto-regressive next-token predictors are uni- versal learners. arXiv preprint arXiv:2309.06977 2023.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. Llama: Open and efficient foundation lan- guage models. arXiv preprint arXiv:2302. 2023.
Merrill, W. and Sabharwal, A. The expresssive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023.
Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowyz,, A., Bosma, M., Luan, D., et al. Show your work: Seratchpads for intermediate computation with language models. arXiv preprint arXiv:2 12.001 2021.
Turing, A. M. Computing machinery and intelli- gence. Mind, 59(236):433-460, 1950. ISSN 00264423, 14602113. URL http:/ http://www.. jstor.
org/stable/22551
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.. Gomez, A. N., Kaiser, L., and Polosukhin, At- tention is all you need. Advances in neural information processing systems, 30, 2017.
Olsson, C., Elhage. N., Nanda, N., Joseph, N., DasSarma, N., Henighan, T., Mann, B., Askell, A., Bai, Y., Chen, A., al. In-context learning and induction heads. arXiv preprint arXiv:2209 /895, 2022.
Wei, C., Chen, Y., and Ma, T. Statistically meaningful approximation: case study on approximating turing machines with transformers. Advances in Neural Infor- mation Processing Systems, 15:12071-12088 2022a.
Pérez, J., Marinković, J., and Barceló, P. On the turing completeness of modern neural network architectures. arXiv preprint (XXix:90/1.0442) 2019.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-or of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:248244-2435 24837, 2022b.
Press, O., Smith, N. A., and Lewis, M. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint
2021.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S.,
Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21 1140):1-67, 2020.
Weiss, G., Goldberg, Y., and Yahav, E. Thinking like trans- formers. In International Conference on Machine Learn- ing, pp. 11080-11099 PMLR, 2021.
Zhang, Y., Backurs. A., Bubeck, S., Eldan, R., Gu- nasekar, S., and Wagner, T. Unveiling transformers with lego: a synthetic reasoning task. arXiv preprint 2rXiv:206604301,, 2022.
Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csor- dás, R., Bennani, M., Legg, S., and Veness, J. Random- ized positional encodings boost length generalization of transformers. arXiv preprint arXiv:2305. 16843, 2023.
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., and Nakkiran, P. What algo- rithms can transformers learn? a study length general- ization. arXiv preprint arXiv:2310. 2023.
Schwarzschild, A., Borgnia, E., Gupta, A., Huang, F,, Vishkin, U., Goldblum, M., and Goldstein, T. Can you learn an algorithm? generalizing from easy to hard prob- lems with recurrent networks. Advances in Neural Infor- mation Processing Systems, 34:6695-6706 2021.
Zhou, Y., Alon, U., Chen, X., Wang. X., Agarwal, R., and Zhou, D. Transformers can achieve length generalization but not robustly. arXiv preprint 402:22400.09377, 2024.
Shaw, P., Uszkoreit, J., and Vaswani, A. Self-attention with relative position representations. arXiv preprint arXiv: arXiv:1803.011 2018
Shen, R., Bubeck, S., Eldan, R., Lee, T. Li, Y., and Zhang, Y. Positional description matters for transformers arithmetie. arXiv preprint arXiv:2311.14737, 2023.

---

Universal Length Generalization with Turing Programs
A. Additional Positional Encodings Review
Absolute Positional Encoding (APE). APE consists in maintaining a positional vector p; for each position i. This vector either predefined via a sinusoidal function (Vaswani et al., 2017) or learned (Devlin et al., 2018). Then, P; is added the token embedding e, before being processed by the Transformer. Prior work observed that this positional encoding does not generalize well to longer sequences in both natural language (Press et al., 2021) and algorithmie tasks (Jelassi et al., 2023; Kazemnejad et al., 2024).
Additive Relative Positional Encoding (RPE). (Shaw et al., 2018) were the first to integrate positional encodings at the level of each attention layer (instead of doing at the input level). (Raffel al., 2020) built upon this approach and added scalar biases to pre-softmax logits follows:
A XWW( + B.
(I)
where X, Wq. Wx are the input and query and key weight matrices. The bias matrix B E R=x= is induced by some positional encoding function b: N - R. For instance, the T5 relative positional encoding (Raffel et al., 2020) set b(i.j) = f(i j), where f is some function. Most of the subsequent positional encodings such as ALiBi (Press et al., 2021), Kerple (Chi et al., 2022), Randomized Positional Encoding (Ruoss et al., 2023) and Fire (Li et al., 2023) rely on changing the pre-softmax logits and differ in their definition of b.
Rotary Positional Encoding (RoPE). RoPE (Su et al., 2024) encodes position information in attention logits by applying a rotation transformation to the query and key vectors based on their relative positions. Despite being widely used, RoPE exhibits limited length generalization (Press et al., 2021; Kazemnejad et al., 2024).
B. Prior results on multi-digit addition
In this section, we summarize the methods proposed by prior work to get length generalization on addition along with their corresoondigg performance. In what follows, we indicate in red the positional encoding and in green the data format used in these works. We also take as a running example the addition 57 576+361=937.
- (Lee et al., 2023) from 7 to 7-digit (1.0x). ). APE + Reversed format. They train their models by reversing each operand as Therefore, the causal model that processes information from left to right can start with the least significant digit and proceed to the most significant digit, which corresponds to the algorithm for addition. They do not achieve any length generalization.
(Kazemnejad al., 2024) from 8 to 9-digit (1.125x): NoPE + Reversed format. They show that model without positional encoding trained on reversed additions like 675+1 63=739 outperforms those with specialized positional encodings like T5's relative positional (Raffel et al., 2020) or RoPE (Su et al., 2024).
- (Shen et al., 2023) from 10 to 11-digit (1.1x): NoPE + Reversed format + random space augmentation. They introduced random spacing between digits, aiming to alleviate the model's reliance on absolute positional information. Combining this with the reversed format, the running example becomes 75+16 3=739. They show that NoPE Transformers length generalize from 10 to 11 digit-addition.
(Zhou et al., 2023) from 30 to 45 digits (1.5x): NoPE + Index Hints. They define "index hints", formatting that consists in adding a letter in front of each digit in the addition to indicate their position. For instance, the rumning example becomes a 5b776 aab 6c1=a 9b3c7. This change is applied during training and inference and enables transformers to execute indexing via induction heads (Olsson et al., 2022).
(Zhou et al., 2024) from 40 100 digits (2.5x): Fire (Li et al., 2023) + Randomized positional encoding (Ruoss et al., 2023) Reversed format + Index Hints. They use combination of two positional encodings: Fire (Li et al., 2023), a additive relative positional encoding that has obtained strong length generalization on natural language benchmarks and Randomized positional encoding (Ruoss et al., 2023): a technique that samples encodings from range exceeding test-time lengths. The goal is to ensure that Transformers can adapt to larger positional encodings during training and not encounter any OOD encoding at test- timt. With reversed format and index hints, the data format looks like (el77555abbc3342 using all these modifications, they reach state-of of-ee----harnn art performance on length generalization for addition. However, these choices seem to be specific to the addition case and hard to transfer to other algorithmic tasks.
By
12

---

Universal Length Generalization with Turing Programs
C. Additional experimental results
100
80
Accuracy (%)
60
40
20
80
90
100
Length of Number
Figure Hard-ALiBi with Turing Program, trained do addition with different initialization seeds. To clarify, the randomness used plot the 95% confidence intervals in Figure comes from the samples we draw to calculate the accuracy once a seed is fixed, not from different training seeds.
80
Accuracy (%)
40
(n 3) HAlibi Turing Program
[n 3) Alibi
Turing Program
(n 3) NoPE Turing Program
20
(n 3) RoPE + Turing Program
(n 3) HAlibi
Direct
100
120
Length of Number
Figure Comparison of different positional encodings and data formats for length generalization (n d)ddiigitmmuliiiiicaiio using the same hyperparamcters. The shade shows the 95% confidence intervals.
To the best of our knowledge, (Zhou et al., 2024) achieved length generalization mainly for addition when the two summands had the same length. Our method generalizes even when the two summands have different lengths. For L2 E {17, 32, 47, 62, 77, 92), we sampled 96 addition examples where the first summand has length L, and the second summand has length L2. The accuracy for each combination is shown in Figure 11. We see that it generalizes well beyond the trained distribution (L1, L2 50).
C.1. Comparison with Past Methods
In this section, we show the performance of some of the methods mentioned Appendix B under our experimental conditions. We consider three data formats:
Reversed format in (Shen et al., 2023).
Index hints in (Zhou et al., 2023)
Index hints + Reversed format in (Zhou et al., 2023)
Moreover, we consider three positional encodings: ALiBi, NoPE, and RoPE. We performed the addition experiments under the exact hyperparameter setting of Figure 3. The results are shown in Figure 12.
13

---

Universal Length Generalization with Turing Programs
100
80
Accuracy (%)
60
40
HAlibi
Allbi
20
NoPE
RoPE
40
60
80
100
120
140
Length of Tape
Figure 10. Comparison different positional encodings for length generalization on randomly generated Turing machine using the same hyperparameters (peak learning rate of 7e 5, batch size of 16, trained for 200, 000 steps).
Accuracy (%)
100.00
17
100
100
100
100
100
99
99.75
32
100
100
100
100
100
100
99.50
Length of Summand 2
99.25
47
100
100
100
100
100
100
99.00
29
100
100
100
100
99
100
98.75
98.50
77
100
100
100
99
99
98
98.25
92
99
100
100
99
99
99
98.00
17
32
62
Length of Summand
Figure 11. Grid displaying the accuracy of our model on addition when changing the length of each operand. We observe that our model is able generalize operands with different lengths.
14

---

Universal Length Generalization with Turing Programs
Accuracy (%)
60
40
20
NoPE Index Hint
20
Allii
Index Hint
Reverse
ARt
Reverse
NoPE Reversed Indox Hint
Reversed Index
0
40
50
60
70
80
90
50
60
80
90
Length Number
Length Number
(a)
(b)
20
RoPE Index Hint
Reverse
RoPE Reversed Indox Hint
40
50
60
70
90
Length Number
(c)
Figure 12. Comparison of different positional encodings and data formats for addition. All hyperparameters held fixed: learning
of 7e 5. batch size of 16, and trained for 200k steps.
15

---

Universal Length Generalization with Turing Programs
D. RASP Turing Programs
D.I. RASP Python Definitions (from (Zhou et al., 2023)
import numpy as np
def full (x, const): return
const, dtype=int)
def indices (x): return ap.arange (Le (x), dtype=int)
def tok map (x, func):
return np.array [func for xi in x]) asstye
def seq_map (x, y, func):
return np.array [func (xi, yi) for xi, yi in zip (x, y) astype (int)
def select (k, q, pred, causal=True):
= len (k)
np. zeros s), atype=bool)
for qi range(s):
for kj (qit1 if causal else s):
A[qi, kj] pred(k(k)) q[qi))
return
def sel width(A)
return np.dot (A, np. (len(A) astype (int)
def aggr_mean (A, default=0);
out np (A, v)
norm sel (A)
out = np. diiiidee (out, norm, full_pffllllkkee (v, default, dtype=float), where= (norm != 0))
return out astype (int)
def aggr_max (A, v, default=0);
out np. pplfull_like(v. default) for i, row in enumerate (A)
idxs flt.onaanooe (row)
if (idxs) 0:
outlil mp.max (v/idxs) return cut.astype (int)
def aggr_min (A, v. default=0); return -aggr_max (A, -v, -default)
def aggr (A, default=0, reduction='mean")
if reduction 'mean':
return aggr_mean (A, v, default)
elif reduction == maxx:
return aggr_max(A, elif reduction -- 'min': return aggr_min(A, v, default)
default)
def kqv (k, q, v, pred, default-0, reduction=/mean"):
return aggr (select (k, q, pred), default=default, reductioo=rreducioon
D.2. Additional Functions (from (Zhou et al., 2023))
import operator as op import numpy as np
Define comparison operators
equals, leq, 1t, geg, gt op.eg, op. op.le, le, op. 1t, op.ge, op.gt
16

---

Universal Length Generalization with Turing Programs
def shift_right (8, n, default=0);
shifts sequence to the right by n positions return kqv (indices (x) indices(x), equals, default-default)
def cumsum (bccc_array)
returns number of previous True elements in bool_array return sel_vidth (bool_array, bool_array, lambda k, k))
def where (cendition, x_if, y_else):
equivalent, to np. where (condition, x_ff, y_else)
x_masked - seq_map (x_if, condition, lambda m: x if m else 0) y_masked seq_map (y_e, condition, 1ambda Yr y if not else 0) return seq map (x masked, y y_maseed, lambda x, y: if 0 else y)
def mask (x, bool_ bock_mask, mask_val=0)-
equivalent to x=bool_mask + defaultx(-bol__aag)))
return where aoboo_lmask full (8, mask_val))
def maximum (x)
return kqv (x, x, lambda k, q: True, reduction='max
def minimum (x)
return -maximum (-X)
def argmax (x):
mm maximum (x)
return kqv (m,, x, indices (x), reduction= max!)
def (x)
return argmax(-x)
def num_prev (x, queries):
output [1] number of previcus elements of x equal to queries [1], inclusive
return sel_width (select (x, queries, equals))
def has_seen (x, queries):
return kqv (x, queries, fxll 1), equals, default=0)
def firsts (x, queries, default=-1):
find the index of the first eccurrence of each query[i] in queries min(()
out :- wxl.ftnnnzeroox(iia return (xv queries, indices()), equals, default=default, reduction='nl min')
def lasts (x, queries, default=-1):
find the index of the last eccurrence of each query[i] in out(i] := flttontnonzero (x[:i+1] queries .max() return kqv queries, indices equals, default-default, reduction='man
def index_select (x, idx, default-0);
indexes into sequence x, via index sequence idx i.e., return x[idx] idx[i] <= i else default return (qy(indices, (x), idx, x, equals, default-default)
def first_truett ix, default=-1):
returns the index of the first true value x
secn_true (xv full 1), full(x, 1), equals, default-0) shift_right (seen_true, 1), lambda curr, prev: curr and
first_occ = not prev)
return (firstt__occ,, full (x, 1), indices (x), equals, default=default)
def induct_kqv q, offset, default=0, null_vai=-999): get value of at index of: first occurrence of qii] found in k (if found) + offset. (excludes the last OFFSET tokens of from matching)
mull_ is special token that cannot appear or qi used to prevent accidental
17

---

Universal Length Generalization with Turing Programs
matches
indices_te_ccpp firsts (shift_right (k, offset, default-nullvval)) 9 default-null_val
copied_ index_selede select (v, indices_to_eet ctroessttt_coo___ default-default) return copied_values
def induct (k, q, offset, default=0, null_val=-999)
return induct_kqy (k, k, offset=offset, default=defaul;,
val)
def induct_prev (k, q, offset, default=0, pull_va==-999; A version of induct for negative offsets.
indi indicce_tt_ccpyy = firsts (k, default-null_vat offset
copied_values index_select (k, indices_to_copy default-default) return copied values
D.3. Utility Functions
def prefix_fiid fill (x, D value)
ones = full (x, 1)
no_fill shift_right (ones, return where (no_fill, x, full (x, value))
def where3 (cond, out where (cend =- 0, y) where (cond 2, 2, out)
2]
D.4. Turing Machine Transition Function
sep 0
bos
eos
empt
alphabet = list (range (4, 16))
state_space = list (range (16, )
la: [s: np. randem. choice (state_spaco for state_space) for in alphabet [bos, eos] }
symbol caabbll_raasitioon (a: {s: np. ra.denm choar..hhoiie ce (al phabet) for s in state_space} for a in al aiphabet]
move rectiio (a: np. www.rranccciccce... chaice 11) for state_space) for in alphabet)
def next__tteet state (state, token): if token in state www.sstttnnniinnneeeeeeeetotteet and state in state_space: return stade_transitiinnttoeel [state] else:
return
def next_ port_symbelloe (state, token)
if token in alphabet and state in state_space: return symbol_tramsitionnteee
[state]
elif token == bos:
return bes
elif token 80s:
return ecs
else:
return
def move (state, tcken)
if token alphabet state in state_space: [state]
return
elif token == bos:
return
else:
return
18

---

Universal Length Generalization with Turing Programs
D.5. Computation of Next Tape State
def
get_next (x, x_left, x_right):
compute the next state head and new symbol, without moving the head x_state map (x, x_eet, next_state)
x_symbo1 - seq_map (X_right x, next_symbol)
x_move_R seq_map (x, x_left, move)
is_head tck_map 1ambda
state_space)
is head right tok map (x right, lambda 2: z state_ space)
x next where his_hai x s_stat,, x)
nentxt where (is head_rraatttt,tteeeee_ee right, x_syrbol, x next)
x_move_R x_move_R & is_head return se_head, x_next, x_move_R
def select_meve_ttken (no_heade _roundd head head_lefttmove_leefe [ead_left_nove_ttee head_right_ left, aha__right_mov__rrhht, is_head_move__efr is_head_move_right LEFT_TOKEN full (no Loo_head_arroun 0)
CUR_TOKEN = full , 1)
RIGHT TOKEN = full (no he__hea__rooune 2)
out CUR_TOKEN
out where thead_left_move_riige out where thead_right__oveeer
is_head_move_left, LEFT_TOKEN, out)
is_head_moee_rige right, RIGHT_TOKEN, out)
return cut
def move_hee head (cur_state right_state);
is_head, cur_next, move_R cur_state Light_is_head right_nexts right_move__ = right_stats left_is_head, left_next, left_mcve_R shi ft_right (is_head, 1), shi thirthiight (cur_next, 1), shift_right (move_R, 1)
head_arour (-left_ _e_head & ~right head -is_bead)
head left move left left he_d head -left _ist___ooe_______
head_left_move_riihht left_is_head left_move_R head_right_nnve_leett right_is_heaa
<right_nove_R
[tt_riggh__moe_righht right_is_head & right_move_R is twead_move__ute head & -move_R is ss_hhad__move_rae is head move_R
x_sel_move [ollet_nove_okeenntt_hhheeee haa_lleft_overreeee met,, hood is nevve___ ho_heed__mve___e (rove]right) where3 sel__eelee,, left_next, cur_next, right_next)
head
def next_tape (x, shift):
compute the state of the head, after shifting by >=
x_ shift shift_right (x, shift)
x left = shift rightt ix, shift+l)
x_right = shift_right (x, shift-1)
rright_rightt shift (x, shift-2)
compute the next state (before noving the head) for current tape and right tape cur sar_state = get_next (x_, xelef,, x_right)
right_state = get_nextt (x_right, x x_right_right)
nexext move head state, right_state)
return X next
D.6. Hashing Functions
19

---

Universal Length Generalization with Turing Programs
INT
def hash_n_gram (8, D):
out x
@efore_last_st = tok_ma__ map (x, lambda == 0)
shifted Shift__rghhtit (x,
for range (n)
shi map tok_map (shifted, lambda 2: 2 == 0) before_last_ = shifted before_last_cee
te_add maq (shifted, refore_last_ee sep, Lambda b: (1-b)) add hash
out seq_map (out, to_add, lambda a, b: b MAX_INT INT a)
shifted - shi ft_ight (shi fted, 1)
return out
def hash n gram iter (x, n):
is_sep tck_map (x, lambda 2: == 0)
sep_cs cumsum (is_sep)
x_hash hash_n_gram (x, return req_map (sep_cs,, hash, lambda a, b:
(MAX INT AD) +b)
D.7. Next-Token Prediction for Turing Programs
def next_token_turingg
x_next_tape_2 next_tape (x, 2)
x_next_tape_3 next_tape (x, 3)
mext__ape__ prefix fill (x (x__ee_________ next_ _ext_tape_3, 2, empt)
q aish_n_gram_ites
1)
v = x_ncxt_tape_2
out kqv (k, return [-1]
equals, reduction=/mas
E. Turing Program Descriptions
E.1. Multiplication
Input:
4
Target:
<scratch>
4
3 2 3 (0540~0054,0)
4 135
0540 carry 054
3
c 1 (0270-002,,0)
# 2 + 135 0270 carry 032
4
3 (0405~0043,700
135 0405 earry 043
1 5 00500~058,37700
carry 0000 carry 005
A 3 (0000~-005,) 88740)
1 3.3. (0000--000,583740)
# 0 135 0000 carry 000
5 S </scratch>
Figure 13. Turing Program for 3-digit multiplication. At each step. we update three information: the head position, the result of the "local" multiplication, the carry and the intermediate result of the "global" multiplication.
E.2. SGD
We briefly describe here the Turing Program we used in subsection 5.2. Beyond the numerical tokens "a0, al, a2.... a199". we include tokens "S, yp. g cur, I" aid the calculation. typical CoT for gradient descent then looks like the
20

---

Universal Length Generalization with Turing Programs
following:
d al79 a166 a76 a80 a145, al02 d a77 a139, a103
d al79 a166, a76 d a80 a145, al02 d a77 a139, a103 yp a100 g a101 a99 a99 a101
d al79 a166, a76 d a80 a145 al02 yp a101 a a100 a99 cur a99 a102
d a a179 a166, a76 yp a100 g a120 al cur a79 a85
In the above example, the first line provides a dataset of size three where "d a179 a166, a76" denotes the first example ("a179"and "a166" are the coordinates of ž, "a76" is the value of and "d" is token that denotes the start of an example), From the second line onward, we perform gradient descent starting from the last data point, working backward: On the second line, the original dataset is copied, while the "a100" following "yp" the predicted value of y given the initial weight and the last feature vector "a77 a139", the "g al01 a99" says that X w. l1ys - Wi He has value "a101 a99", and "cur a99 a101" means that the current weight after update "a99 a101". After example's ' gradient is calculated, we delete that example.
E.3. Sequences of Arithmetic Operations
x1=16
x2=18
x3-7
x4=9
y=x1-x3
y=x4-y
y=y+x1
x1=16
x2=18
x3=7
x4=9
y-16-7
y-x4-y
y-yax1
current y=9
x1=16
x2-18
x3=7
x4=9
y=9-9
y=y*x1
current y=0
x1=16
x2=18
x3-7
x4-9
y-0+16
current y=0
F. Turing Programs for Simulating Turing Machines
We use the tokens space a1, a2....,
., b1, bg...., 81, 82, L, R). (1), (,),,, < BOS |>, < BOS >> < SEE >>, where the aj 's are input symbols, the by are symbols substituting the a,' 's when the head is pointing to them and 1,), L,, symbols used to encode the transitions. For instance, the transition (s1, ag. L) means that the Turing machines moves to state $1, edits the tape by writing ag and moves the head to the left.
21


Reviews:
[{"review_id": "h6yYqjLDQN", "reviewer": "Reviewer_RWaS", "summary": "This paper introduces Turing Programs, a novel CoT strategy that improves length generalization on a range of algorithmic tasks. By structuring algorithmic tasks as step-by-step computations resembling a Turing Machine, this method achieves robust generalization across tasks like addition, multiplication, and in-context SGD. The authors also provide theoretical proof that transformers can implement Turing Programs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback. We respond to the main points raised by the reviewer below.\n\n**Only algorithmic problems:** The reviewer is right to point out that currently the result is not immediately practical. For this work, our goal is to do a deep evaluation of how length generalization can arise in language models trained on next-token prediction. Following a large body of prior work (see the many papers on addition, such as https://arxiv.org/abs/2402.09371), we conduct these experiments on synthetic tasks. Therefore, we hope this won’t be considered as a fatal weakness for the paper.\n\n**Larger LMs:** We expect no reason why the same generalization won’t hold when our technique is applied to larger models. We want to make two points:\n\n- As model size grows, we expect the model to perform complex Turing programs better. (e.g. harder arithmetic tasks). It would be an interesting direction of future research to quantify and see how model size and task difficulty (maybe captured by the RASP program size as observed in https://arxiv.org/pdf/2310.16028) affect length generalization results.\n- Turing program may be a way to construct CoT for certain math problems (see the next section), which can be used to train large models.\n\n**Improvement in math reasoning:** Although it is unclear how general QA can be improved by the current iteration of Turing Program, there is certainly application to math problems that have good algorithmic solutions. Consider the game of 24 (analyzed in https://arxiv.org/abs/2404.03683): you win by manipulating 4 numbers to reach 24. It can be solved by DFS, which can be encoded into the Turing Program format. It would be interesting to see if including Turing Programs of various math problems into the training data mix can improve length generalization performance. We leave the study of how to use Turing Programs for more realistic math problems to future work.\n\nWe thank you again for the helpful comments on our paper. We believe that we answered the main drawbacks raised in the review, and would appreciate it if you would raise your score if you believe that your concerns were indeed addressed.", "claims_and_evidence": "Yes. The authors conduct experiments on three algorithmic tasks to demonstrate that transformers can achieve length generalization on random Turing Programs.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not find any major issues.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The paper builds on prior work in length generalization, scratchpad, and other CoT prompting methods.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "This paper is the first results showing non-trivial length generalization on multiplication. The experimental design is generally sound and supports the claim that Turing Programs achieve robust length generalization on three arithmetic tasks. However, since arithmetic problems can be effectively solved by deterministic algorithms or Program of Thoughts methods, this may limit the method's generalization to more complex tasks and weaken its practical applicability.", "other_comments_or_suggestions": "The abstract and introduction mention that length generalization is a challenge for current LLMs. Since the transformer used in this paper is relatively small (150M), it would be helpful to briefly discuss the potential application of Turing Programs to larger LMs.", "questions_for_authors": "Can the proposed Turing Programs method provide non-trivial performance improvements on real-world QA tasks, particularly in mathematical reasoning (e.g., MATH benchmark)?", "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": "FfepB8ZAOe", "reviewer": "Reviewer_L1eA", "summary": "The paper tackles the challenge of length generalization in transformer models—the ability to extrapolate from short training sequences to test sequences longer. The main contribution is Turing Programs, a novel scratchpad strategy inspired by Turing machine computations. In this framework, an algorithmic task is decomposed into a series of intermediate “tape” states, where each step is a slightly modified copy of the previous one. Combined with the Hard-ALiBi positional encoding, this approach enables robust length generalization on several algorithmic tasks, including multi-digit addition, multiplication (with both 1-digit and 3-digit operands), and an in-context simulation of SGD for linear regression. The paper also provides theoretical evidence by showing that transformers can implement Turing Programs via construction in the RASP programming language, thereby establishing a formal connection between the proposed method and Turing machine computations.\n\n## update after rebuttal\n\nThe authors' response explains the limitations of their work on real data and clarifies their focus on studying position encoding. I find their explanation sufficiently convincing.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback. We respond to the main points raised by the reviewer below.\n\n**Universality:** We understand that the word “universal” may not accurately capture the nature of our results, and we are open to removing it from the title if the reviewer thinks this will be adequate.\n\n**N-gram repetition**: We agree that relying on n-gram repetition may be a significant restriction of our theoretical construction, but note that for “random enough” inputs, repeated n-grams become very unlikely for large enough n. Additionally, we suspect that transformers in practice may be in fact utilizing an n-gram matching mechanism (as observed in prior works, e.g. https://arxiv.org/pdf/2402.01032), which means that this limitation reflects a true limitation of transformers and not just a problem in our theoretical construction. In that sense, we believe that our theoretical construction truly captures the nature of the solutions learned by the transformers, including the potential limitation of these learned solutions.\n\n**Gap with real-world tasks and data:** This is a legitimate concern. We want to make two points here:\n\n- For this work, our goal is to do a deep evaluation of how length generalization can arise in language models trained on next-token prediction. Following a large body of prior work (see the many papers on addition, such as https://arxiv.org/abs/2402.09371), we conduct these experiments on synthetic tasks. Therefore, we hope this won’t be considered as a fatal weakness for the paper.\n- There may be applications to math problems that have good algorithmic solutions. Consider the game of 24 (analyzed in https://arxiv.org/abs/2404.03683): you win by manipulating 4 numbers to reach 24. It can be solved by DFS, which can be encoded into the Turing Program format. It would be interesting to see if including Turing Programs of various math problems into the training data mix can improve length generalization performance. We leave this study to future work.\n\n**Role of Positional Encoding in Length Generalization:** This is a good point. We agree that many factors contribute to length generalization performance, but we chose to focus on the choice of positional encoding as it was pointed out to be a key factor in prior works studying length generalization. Controlled experiments on how other variables affect length generalization should be done in future research.\n\nWe thank you again for the helpful comments on our paper. We believe that we answered the main drawbacks raised in the review, and would appreciate it if you would raise your score if you believe that your concerns were indeed addressed.", "claims_and_evidence": "- Claims: The paper claims that using Turing Programs enables transformers to generalize to longer sequences on a variety of algorithmic tasks, achieving near-perfect performance (e.g., 98% accuracy on addition when generalizing from 50—to 100-digit numbers) and that transformers can theoretically implement these programs.\n- Evidence: The experimental results on addition, multiplication, and SGD, along with detailed comparisons of different positional encoding strategies, support these claims—the provided theoretical construction (Theorem 4.2) further bolsters the claim of universality.", "methods_and_evaluation_criteria": "The chosen methods and evaluation criteria are well-aligned with the problem of length generalization in algorithmic tasks.", "theoretical_claims": "The theoretical claim is solid under the assumptions.", "experimental_designs_or_analyses": "The experimental design is sound and thorough.", "relation_to_broader_scientific_literature": "- This paper extends ideas from previous studies on Hard-ALiBi and related positional encoding strategies and situates its contributions in the context of research on transformer expressiveness and Turing completeness.\n- By linking empirical improvements to theoretical constructs (RASP programs), the paper offers a meaningful contribution that advances our understanding of length generalization—a long-standing issue in the literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n- The approach is novel, drawing inspiration from Turing machines to design a universal method.\n- Empirical results across multiple tasks are strong and convincingly demonstrate improved length generalization.\n- The theoretical construction adds depth and rigor to the contributions.\n\nWeaknesses:\n- The claim of universality might be overextended given that experiments focus on a limited set of algorithmic tasks.\n- Some of the theoretical assumptions (e.g., non-repetition of n-grams) may not hold in more complex or noisy real-world scenarios.", "other_comments_or_suggestions": "- Gap Between the Assumptions and Real-World Data:\nIn practice, natural language often contains repeated patterns and more complex structures, which could affect the copying mechanism critical to the proposed Turing Program approach. While the authors acknowledge this gap, a deeper empirical or analytical exploration of how these assumptions might limit performance on actual data would be valuable.\n\n- Focus on Algorithmic Tasks vs. Real Language Tasks:\nReal-world language tasks could greatly benefit from these insights. It would be interesting to see future work that adapts the Turing Programs framework to more complex, natural language applications, thereby testing whether the benefits observed in algorithmic tasks translate to these richer, less structured domains.\n\n- Role of Positional Encoding in Length Generalization:\nWhile the experiments clearly demonstrate that the choice of positional encoding (notably Hard-ALiBi) is crucial for enabling robust length generalization, it is important to recognize that other components of the transformer architecture also play significant roles. For instance, the attention mechanism, model depth, and training protocols can influence how well the model generalizes to longer sequences.", "questions_for_authors": "See list above.", "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": "yfgGK6i8GI", "reviewer": "Reviewer_Wrzm", "summary": "The paper proposes a new method for designing chain-of-thought supervision for algorithmic tasks, termed \"Turing Programs\". Essentially, the state of a Turing machine (including the tape, head position, and internal state) before and after each transition are serialized and represented in a chain of thought. The authors explore how training with this trace supervision encoded in chain of thoughts improves length generalization on several tasks: addition, multiplication, and SGD on linear regression. This trace supervision combined with HAlibi positional encodings is shown to exhibit significant (although imperfect) length generalization on these tasks.\n\nThe paper also includes a theorem that relates to a constructive demonstration (via RASP) that a Transformer can emulate a Turing machine using the proposed encoding (with several simplifying assumptions).\n\n## Update after rebuttal\n\nI think clarifying the main claims of the paper would be an improvement. I also think if the main claims are related to the empirical performance of the proposed chain-of-thought format, a stronger CoT baselines such as the one proposed would be useful to support the claim.\n\nI like the general idea of the paper, and I think if the pledged changes were implemented well and the empirical results still support the main claims, I would likely update my score to a 3, but it is difficult to verify this given that the pledged changes are somewhat significant, and affect the clarity of and support for the main claims. Therefore I think the paper would benefit from resubmission to a future conference or workshop with the proposed changes. However, I don't want to block acceptance if the other reviewers have a different opinion.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. We respond to the main points raised by the reviewer below.\n\n**Key claims of the paper:** we want to emphasize that the key claim of our paper is that Transformers can achieve *length generalization* (generalization to problems longer than the ones observed in the training data) for a large class of problems. That is, we do not argue that we establish novel expressivity results—as you pointed out, the fact that language models can express a large class of functions using chain-of-thought has already been shown in various prior works. Rather, we argue, using a combination of empirical experiments and theoretical observations, that Transformers can extrapolate to longer sequence lengths when provided with chain-of-thought/scratchpad data of a particular format which tracks the step-by-step operation of a “Turing Machine” (the Turing Programs). This connection between the chain-of-thought format and length generalization goes far beyond what has been shown in prior works (including the works that you mentioned), which focus on a narrow set of algorithmic tasks. Instead, our results demonstrate the potential of “universal length generalization” — length generalization for any algorithmic tasks. While we do not establish this formally (due to limitations of our theoretical analysis), we believe that the combination of our extensive experimental results and theoretical insights suggests that Transformers can length-generalize on a far larger class of problems than previously acknowledged, a result that we see as the main novel contribution of our work. Therefore, we believe that our theoretical result should be viewed in the broader scope of the paper, coupled with the experiments on length generalization, and not as an independent expressivity result. Thank you for pointing this out, and we will clarify this in the final version of the manuscript.\n\n**Comparison to other baselines:** throughout the paper, we compare our method to training without chain-of-thought, which displays poor length generalization performance. However, we agree that adding a baseline where we train with another chain-of-thought format can help establish our claims, and we plan to run additional baseline experiments and add them to the final version of the paper. Specifically, we will compare our scratchpad technique to more minimal chain-of-thought, for example one that tracks only the current number and the carry digit in the case of multi-digit addition.\n\n**The choice of n in non-repeated n-grams:** we would like to clarify that Theorem 4.2 holds *for any choice of n.* I.e., for any $n \\in \\mathbb{N}$ there exists a RASP program of size (number of lines) which grows linearly with the chosen *n*, that satisfies the conditions of the theorem. We will clarify this in the final version of the paper.\n\n**Citations:** we will fix the citations format in the paper.\n\nWe thank you again for the helpful comments on our paper. We believe that we answered the main drawbacks raised in the review (in particular, about the key claim of the paper), and would appreciate it if you would raise your score if you believe that your concerns were indeed addressed.", "claims_and_evidence": "The key claims were a bit unclear to me.\n\nThere are specific empirical claims related to training with trace supervision in the form \"Turing Programs\" improving length generalization over training without such supervision, e.g. for addition and multiplication, which appear to be well supported (although could be strengthened by improving the baselines, e.g. considering other chain-of-thought formats).\n\nHowever, the title of the paper primes the reader to expect a definition of \"Universal Length Generalization\", and some related result for \"Turing Programs\". However, the definition and connection to \"Turing Programs\" was unclear to me. Maybe these are bit nitpicky but:\n\n1. The paper does not seem to establish new expressivity results for Transformers. \"Turing Programs\" are a specific convention for chain-of-thought sequences, and therefore do not formally extend the expressivity of Transformers. The expressivity of Transformers with chain-of-thought has been studied by prior work (e.g. the cited https://arxiv.org/abs/2310.07923, but also https://arxiv.org/abs/2406.14197 and https://arxiv.org/abs/2402.12875). A key point of complexity in these results is indexing and attending to evolving register states, as well as issues around finite precision. The proposed RASP program seems to avoid this issue through the non-repeated n-gram restriction, and does not restrict tokens to bounded integers, if I understood correctly. It's therefore not clear how this extends our understanding of Transformer expressivity. If this is a key contribution, it would be good to discuss the result in the context of prior work.\n\n2. The paper does not seem to establish a broad class of new learnability results for Transformers. It is already previously known that training with additional chain-of-thought supervision can improve generalization, especially when such chain-of-thoughts effectively \"unroll\" some dynamic loop (e.g. https://arxiv.org/abs/2310.16028 and https://arxiv.org/abs/2404.15758). \"Turing Programs\" are simply one specific convention for representing this information, so it's not clear that the result is categorically novel, even though the authors show that it is empirically effective for several tasks. The \"universal\" claim seems to relate to the fact that any algorithmic task can in theory be encoded as a Turing machine, however the theoretical results limit the set of Turing machines that can be emulated (e.g. the non-repeated n-gram restriction). Additionally, there is no automatic conversion from a given algorithmic task to a Turing Program. Therefore, it's unclear formally what the claim to \"universality\" is, and why \"Turing Programs\" have this property in a way that other schemes for encoding chain-of-thoughts do not. For example, chain-of-thoughts in natural language are also \"universal\" in the sense that they can be used for any task.\n\nIn summary: I think the key claims could be clarified for the reader. If the main claims are simply empirical results for the tasks studied, that is fine but should be clearer. If there is some qualitative property of \"Turing Programs\" that other chain-of-though conventions lack, this property should be more clearly formalized. If there is some new expressivity result, the difference from prior work should be emphasized.", "methods_and_evaluation_criteria": "The tasks seem reasonable, although the baselines could be improved. The authors could compare against other conventions for \"unrolling\" the underlying computation and representing it in a serialized chain-of-thought.", "theoretical_claims": "See above.", "experimental_designs_or_analyses": "See above concern related to baselines.", "relation_to_broader_scientific_literature": "I think the theoretical claims could be better contextualized in prior work, per above comments.", "essential_references_not_discussed": "Papers with theoretical results on Transformer decoder expressibility: https://arxiv.org/abs/2406.14197 and https://arxiv.org/abs/2402.12875\n\nThis paper discusses emulating Turing machines in a Transformer (with external memory): https://arxiv.org/abs/2301.04589", "other_strengths_and_weaknesses": "Strengths:\n\n* The paper presents a new scheme for representing unrolled computation traces in a serialized chain-of-thought, inspired by Turing machines.\n* The paper shows how training with such traces enables strong length generalization for several tasks, including those where training without trace supervision exhibits minimal length generalization.\n* The paper gives a constructive result (via RASP) for how Transformer decoders can emulate a subset of Turing machines.\n\nWeaknesses:\n\n* See confusion around key claims and relation to prior work above.", "other_comments_or_suggestions": "nits: Should use \\citet in several places.", "questions_for_authors": "What is the size of `n` for the \"non-repeated `n`-gram\" constraint of Theorem 4.2? It would be good to formalize this a bit more clearly. Can `n` be chosen, i.e. we just require that there exists some `n` such that there are no repeated `n`-grams? Maybe this is clearer from inspecting the RASP code in the appendix, but would be helpful to clarify in the actual theorem statement.", "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": "pDVtF4gwnk", "reviewer": "Reviewer_6SnS", "summary": "This work proposes Turing Program, which is a CoT strategy that decomposes an algorithmic task into steps mimicking the computation of a Turing Machine. The work showed that by using Turing Programs, they obtain robust length generalization on a range of algorithmic tasks: addition, multiplication and in-context SGD.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. We respond to the main points raised by the reviewer below.\n\n**Theoretical analysis may be missed:** If the reviewer can further explain what is lacking in terms of the theoretical analysis, we would love to further explain and add to the revision. From our perspective, theorem 4.2 is the main theoretical result: we show a Transformer of some fixed size can simulate Turing Programs up to length that is exponential in their size, which suggests that “small” Transformers can execute very long programs. This expressivity result is connected to length generalization because it is a necessary (but not sufficient) condition for length generalization to happen with Turing Programs (not sufficient because gradient descent might not learn this constructed solution). Therefore, we feel it provides theoretical backing for the empirical success we see in algorithmic tasks.\n\n**Why special data format works:** We should have made it clearer why the Turing Program data format is useful for length generalization. When we write out a task in this format, the task gets broken down to two subtasks: 1. modifying the tape content at a single position and 2. copying the tape content. The modification only requires the token at the head position and the positions where the Turing machine state is located, so is relatively independent to the overall length of the input. Copying is length dependent, but a past work (https://arxiv.org/abs/2402.01032) already showed that Hard-ALiBi could achieve length-generalization on copying. Thus, we expect Turing Programs combined with Hard-ALiBi to deliver length generalization results.\n\nWe explained this understanding in Section 2.2 of the paper (quoted below for ease of reading), but can add further explanation in the revision.\n\n“We begin with the observation that the scratchpad technique can be realized as an iterative sequence of copying operations, where at each iteration the input is slightly modified. Building on previous works showing that with the right positional encoding, transformers can achieve length generalization on the copying operation, we hypothesize that combining the scratchpad technique with a favorable positional encoding can unlock length generalization capabilities.”\n\n**Could be used for language modeling?:** Our method currently is most suited for algorithmic tasks, i.e. problems that can be decomposed into step-by-step solutions. Our work focuses on algorithmic problems that have closed and known solutions (e.g. arithmetic problems), similarly to many existing works on length generalization (e.g. https://arxiv.org/abs/2402.09371). However, we believe that this method can be adapted to a broader set of natural language problems that are of algorithmic nature, such as mathematical reasoning problems, and leave this study to future work.\n\nWe thank you again for the helpful comments on our paper. We are happy to provide further clarification, and would appreciate it if you would raise your score if you believe that your concerns were addressed.", "claims_and_evidence": "Yes, the claims made in the submission supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods make sense the problem or application at hand", "theoretical_claims": "There is no theoretical claims in the work.", "experimental_designs_or_analyses": "I have checked the experimental designs or analyses.", "relation_to_broader_scientific_literature": "This work propose a special data format for length generalization/extrapolation.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Weakness:\n* **The core weakness is the methodology of the work**. In this work, the authors propose a special data format for algorithmic tasks to improve the length generalization performance. Though the performance is promising, the theoretical analysis may be missed.\n* **Need More detailed analysis to support why such data format works for Transformer Length Extrapolation**. After reading the work, I am not sure why such a special data format is related to length extrapolation. Any special explanation?\n* **Why the method could be used for language modeling**? The paper claims that the method could be used for any algorithmic task, but we are curious where the Turing Program could be used for language modeling.\n\nTherefore, though the methods work well for length extrapolation, it sill needs more reason to explain why such methods work.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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:

Meta-review: This paper introduces Turing Programs, a novel CoT strategy that decomposes an algorithmic task into steps mimicking the computation of a Turing Machine. The main contribution involves showing that Turing Programs enables transformers to generalize to longer sequences on a variety of algorithmic tasks, achieving near-perfect performance (e.g., 98% accuracy on addition when generalizing from 50 to 100 digit numbers) and that transformers can theoretically implement these programs. After the rebuttal, most reviewers are satisfied with the authors’ responses, including the revisions and experiments that have been suggested based on the discussions. We encourage the authors to incorporate these revisions and experiments into the revised version of the paper.
Decision: Accept (poster)