What Algorithms can Transformers Learn? A Study in Length Generalization

Learned positional embedding is better than a number of more sophisticated embedding approaches on length generalization.

“This is consistent with the findings reported in Kazemnejad et al. (2023), which showed that learned positional embedding is better than a number of more sophisticated embedding approaches on length generalization.”

• cites Kazemnejad et al. (2023) sourceDisputed

  The Model Evaluation section says the study used sinusoidal absolute position embeddings, not learned ones, because learned embeddings cannot produce embeddings for unseen positions. The Discussion reports that NoPE outperformed explicit positional encodings and that Rotary marginally outperformed APE—the opposite of the claimed comparison. (LLM, conf=0.88)

  Checked by a reasoning model — may be wrong.

  Experimental — accuracy not yet measured

Even models finetuned from pretrained LLMs struggle on simple algorithmic tasks.

“even models finetuned from pretrained LLMs struggle on simple algorithmic tasks (Anil et al., 2022).”

• cites Anil et al., 2022 sourcePartly supported

  Section 3 (p. 4) reports that models finetuned from pretrained language-model checkpoints perform poorly on out-of-distribution lengths in simple algorithmic tasks. The Contributions section (p. 2) also says they can attain perfect in-distribution accuracy, so the unqualified claim that they struggle on the tasks omits the crucial length-generalization condition. (LLM, conf=0.88)

  Experimental — accuracy not yet measured

Transformers trained from scratch on addition and other arithmetic tasks exhibit little to no length generalization in prior work.

“Transformers trained from scratch on addition and other arithmetic tasks exhibit little to no length generalization in prior work (Nye et al., 2021;Nogueira et al., 2021;Lee et al., 2023)”

• cites Nye et al., 2021 sourcePartly supported

  Section 3 (Addition; page unavailable) reports that baseline Transformers trained on 1–8-digit addition completely failed on out-of-distribution 9–10-digit problems. But Section 2 (Method; page unavailable) says all experimental models were pre-trained before task-specific fine-tuning, not trained from scratch. The cited result therefore supports poor length generalization on addition, but not the claim about from-scratch training or other arithmetic tasks. (LLM, conf=0.88)

  Experimental — accuracy not yet measured
• cites Nogueira et al., 2021 sourcePartly supported

  Appendix C (pp. 10–12) reports poor extrapolation on many addition and subtraction tests, supporting a limitation in length generalization. But its largest model achieves high accuracy on several 50-to-60-digit tests. Appendix E (p. 13) compares models trained from scratch with pretrained models only when training and testing cover the same lengths; it does not establish the claimed length-generalization result specifically for models trained from scratch. (LLM, conf=0.85)

  Experimental — accuracy not yet measured
• cites Lee et al., 2023Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The copy with unique tokens task is easy because an induction head can be leveraged.

“Intuitively, this task is easy because we can leverage what is called an “induction head” (Olsson et al., 2022).”

• cites Olsson et al., 2022 sourceSupported

Models trained from scratch show little to no length generalization on addition.

“Models trained from scratch show little to no length generalization on addition (Nye et al., 2021;Lee et al., 2023)”

• cites Nye et al., 2021 sourcePartly supported

  Section 3 (page not specified) reports that models trained without scratchpads completely failed to generalize from 1–8-digit addition to 9–10-digit addition. But Section 2 (page not specified) says all experiments used pre-trained language models, and Section 3 says they were fine-tuned for addition. This paper therefore supports the length-generalization result for fine-tuned models without scratchpads, not models trained from scratch. (LLM, conf=0.88)

  Experimental — accuracy not yet measured
• cites Lee et al., 2023Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Models trained from scratch show little to no length generalization on parity.

“and parity (Bhattamishra et al., 2020;Chiang & Cholak, 2022;Ruoss et al., 2023;Delétang et al., 2023)”

• cites Bhattamishra et al., 2020 sourceSupported
• cites Chiang & Cholak, 2022 sourcePartly supported

  Section 5.1 reports that standard transformers trained from scratch were unable to learn PARITY. It does not report a parity-specific test of generalization from shorter to longer strings; the length-generalization results in that section concern FIRST. Thus the paper supports poor learning on parity, but not the claim’s specific length-generalization finding. (LLM, conf=0.85)

  Experimental — accuracy not yet measured
• cites Ruoss et al., 2023 sourceSupported

A Transformer cannot even fit the training set of parity sequences over some minimal length.

“Many works have shown that a Transformer cannot even fit the training set of parity sequences over some minimal length (Hahn, 2020;Delétang et al., 2023).”

• cites Hahn, 2020 sourcePartly supported

  The Discussion says that any fixed transformer will make mistakes on PARITY when inputs are sufficiently long. It does not establish that a Transformer cannot fit a finite training set beyond a particular minimum length; the same section says a transformer can be constructed to achieve perfect accuracy on all examples up to any chosen finite length bound. (LLM, conf=0.88)

  Experimental — accuracy not yet measured
• cites Delétang et al., 2023Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Pretrained LLMs cannot solve addition and parity robustly without careful prompting.

“even pretrained LLMs cannot solve these tasks robustly (Brown et al., 2020;Chowdhery et al., 2022;Anil et al., 2022) without careful prompting (Zhou et al., 2022b).”

• cites Brown et al., 2020 sourcePartly supported

  Section 3.9.1 (p. 22) supports a limitation for harder addition: GPT-3 achieved 25.5% few-shot accuracy on four-digit addition and 9.3% on five-digit addition. But it achieved 100% on two-digit addition, so the claim is too broad for addition generally. The paper does not report a parity task; the separate citation to Zhou et al. is attached to the careful-prompting qualification. (LLM, conf=0.88)

  Experimental — accuracy not yet measured
• cites Chowdhery et al., 2022 sourcePartly supported

  Table 10 (Results, p. 21) reports 17% accuracy for PaLM 540B on GSM8K math word problems without chain-of-thought prompting, versus 54% with it. That supports difficulty on an arithmetic task, but the paper does not establish the claim specifically for addition and parity. The separate citation to Zhou et al. is attached to the careful-prompting clause. (LLM, conf=0.83)

  Experimental — accuracy not yet measured
• cites Anil et al., 2022 sourcePartly supported

  The Introduction (p. 1) says LLMs struggle to generalize to problems of arbitrary length, and Section 5.1 (p. 7) reports that the right scratchpad prompt improves pretrained models’ performance on a parity-based coin-flipping task. But the paper’s own tasks are parity and variable assignment, not addition; its evidence therefore does not establish the claim for both named tasks. (LLM, conf=0.84)

  Experimental — accuracy not yet measured

Induction heads work by identifying a previous instance of the current token, finding the token that came after it, and predicting the same completion to the current token.

“Induction heads work by identifying a previous instance of the current token, finding the token that came after it, and predicting the same completion to the current token.”

• cites Olsson et al., 2022 sourceSupported

Numerical algorithms, such as in-context gradient-descent and linear regression, are ill-suited for RASP.

“A notable class of Transformer algorithms which are ill-suited for RASP are numerical algorithms, such as incontext gradient-descent and linear regression, which involve high-dimensional matrix and vector floating-point operations (Akyürek et al., 2022;Garg et al., 2022;Charton, 2021).”

• cites Akyürek et al., 2022 sourcePartly supported

  Section 3.1 (p. 4) describes matrix multiplication as a computational primitive, and Sections 3.2–3.3 (p. 4) show how transformers can implement gradient-descent and regression computations. The cited paper does not address RASP or say these algorithms are ill-suited for it; that part of the citing sentence is unsupported by this source. (LLM, conf=0.85)

  Experimental — accuracy not yet measured
• cites Garg et al., 2022 sourcePartly supported

  Section 3.1 (p. 5) reports that a Transformer learns linear functions in context, and Section 5 (p. 9) compares its performance with gradient descent on in-context examples. Appendix A.3 (p. 20) describes linear regression using a matrix and vectors. The paper does not assess whether these algorithms are ill-suited for RASP or establish that the Transformer performs gradient descent in context. (LLM, conf=0.82)

  Experimental — accuracy not yet measured
• cites Charton, 2021 sourcePartly supported

  Section 2 (p. 2) studies Transformer performance on floating-point matrix and vector operations, supporting the numerical-operations part of the citation. The paper does not assess RASP or identify in-context gradient descent and linear regression as algorithms ill-suited for it. (LLM, conf=0.82)

  Experimental — accuracy not yet measured

The Transformer implementation of selector width requires weights which grow linearly with sequence length.

“since the Transformer implementation of selector width requires weights which grow linearly with sequence length (Lindner et al., 2023).”

• cites Lindner et al., 2023 sourcePartly supported

  Appendix D.2 describes Tracr’s selector-width implementation using an attention layer and an MLP layer. It does not state that the implementation requires weights that grow linearly with sequence length; searches for weight scaling did not establish that part of the claim. (LLM, conf=0.81)

  Experimental — accuracy not yet measured

Linear-attention Transformers can evaluate their next-token function in O(n) time in their input length.

“Linear-attention Transformers can evaluate their next-token function in O(n) time in their input length, as observed by Katharopoulos et al. (2020).”

• cites Katharopoulos et al. (2020) sourceSupported

Models trained on sequences of length 60 or more exhibit near perfect length generalization up to length 150 on the counting task.

“Models trained on sequences of length 60 or more exhibit near perfect length generalization up to length 150 (max evaluation length).”

Poor scratchpad formats can make tasks harder.

“We also show how poor scratchpad formats can make tasks harder, by giving an example for the Mode task.”

For certain hard tasks, constructing new versions that admit RASP-L solutions by modifying input and scratchpad format makes those versions length generalize.

“For certain hard tasks we construct “new” versions which admit RASP-L solutions, by carefully modifying the input and scratchpad format, and these versions length generalize.”

There exist algorithmic tasks where Transformers trained from scratch generalize naturally far outside the training distribution.

“we show that there exist algorithmic tasks where Transformers trained from scratch generalize naturally far outside of the training distribution.”

Models trained on mode scratchpad converge much more slowly during training than no scratchpad.

“Moreover, we show in Figure 6c that models trained on scratchpad converges much more slowly during training than no scratchpad.”

Increasing data diversity in the form of maximum training length leads to better length generalization on mode.

“Similar to count, we also observe here that increasing data diversity in the form of maximum training length leads to better length generalization.”

Another variant of the mode scratchpad with tokens presented in order of appearance, such that no sorting is required, shows a similar effect.

“In Appendix D.2, we evaluate another variant of the scratchpad with the tokens presented in order of appearance, such that no sorting is required, and observe a similar effect.”

The forward-order addition RASP-L program is much longer than the reverse-order one.

“Comparing Listing 9 and Listing 10 reveals how much more complicated the forward algorithm is-it results in a much longer RASP-L program.”

Models trained on count can generalize near perfectly to double the training lengths.

“We find that models trained on count can generalize near perfectly to double the training lengths.”

Models fail to generalize to longer lengths on the copy with repeating tokens task.

“We show in Figure 3b that models fail to generalize to longer lengths on this task.”

Training speed is correlated with how difficult the task is under RASP-L.

“we show that training speed is also correlated with how difficult the task is under RASP-L.”

The trained Transformer reaches 100% test accuracy on the unseen test set in the boolean conjunction experiment.

“The trained Transformer reaches 100% test accuracy on the unseen test set.”

Reverse addition optimizes more quickly than forward addition during training.

“Moreover, we observe in Figure 6a that reverse addition optimizes more quickly than forward addition during training.”

As training length scales up, the number of tokens beyond the training length that the model can successfully generalize to increases.

“Moreover, as we scale up training length, we observe a corresponding increase in the number of tokens beyond the training length that the model can successfully generalize to.”

For parity with scratchpad, when training length reaches 40, all models achieve perfect length generalization on length 50.

“When training length reaches 40, all models achieve perfect length generalization on length 50.”

Parity without any scratchpad requires operations that are forbidden under RASP-L.

“Similarly, parity without any scratchpad requires operations that are forbidden under RASP-L.”

Even models trained on sequence length up to 10 can achieve a median test accuracy of 50% on sequences of length 60 for mode.

“even models trained on sequence length up to 10 can achieve a median test accuracy of 50% of sequences of length 60.”

RASP and RASP-L are not complete: not all functions which can be efficiently represented by Transformers have efficient RASP implementations.

“For one, RASP and RASP-L are not complete: not all functions which can be efficiently represented by Transformers have efficient RASP implementations.”

Addition is difficult to write in RASP-L.

“Indeed, addition is also difficult to write in RASP-L.”

The paper's approach results in the first instance of strong length generalization on parity and addition for Transformer models trained from scratch.

“which results in the first instance of strong length generalization on parity and addition for Transformer models trained from scratch.”

Balanced carry training unlocks the model's ability to length generalize on forward addition, even under hard carry evaluation.

“We see that this more careful training unlocks the model's ability to length generalize on forward addition, even under the hard carry evaluation.”

For parity with scratchpad, some runs trained with sequences up to 30 in length can generalize perfectly on sequences of length 50.

“We find that some of the runs trained with sequences up to 30 in length can generalize perfectly on sequences of length 50.”

It is crucial that the training distribution contain samples ranging from length 1 to maximum training length, which adds diversity as training length scales up.

“It is crucial that our training distribution contain samples ranging from length 1 to maximum training length, which adds diversity as we scale up training length.”

The minimum-degree-interpolator will not depend on the last k=5 bits of the input, since these bits are constant on the train set.

“To see this, observe that the minimum-degree-interpolator will not depend on the last k = 5 bits of the input, since these bits are constant on the train set.”

The RASP conjecture is consistent with experiments on a variety of algorithmic tasks.

“we show that the RASP conjecture is consistent with experiments on a variety of algorithmic tasks.”

Models trained on mode generalize strongly to sequences far longer than the training lengths.

“We find that models trained on mode generalize strongly to sequences far longer than the training lengths.”

There is a one-line RASP-L program which computes the boolean AND of all input bits.

“On the other hand, there is a one-line RASP-L program which computes the boolean AND of all input bits:”

For the sort task, strong length generalization is observed on length 50 for models trained with sequences of length 35 or more.

“We observe strong length generalization on length 50 for models trained with sequences of length 35 or more.”

The natural algorithm for parity cannot be directly implemented in RASP-L, because RASP-L does not allow loops.

“Unfortunately, this algorithm cannot be directly implemented in RASP-L, because RASP-L does not allow loops”

Models trained on copy with unique tokens on sequence length up to 40 can generalize perfectly to length 50.

“For models trained on sequence length up to 40, we find that they can generalize perfectly to length of 50.”

No generalization is observed if training is on sequences of all the same length.

“For example, no generalization is observed if we train on sequences of all the same length.”

RASP-L programs can be learned by Transformers in a length-generalizing way.

“In the experimental section, we will argue that RASP-L programs can in fact be learned by Transformers, in a length-generalizing way.”

Models trained with 35 or higher maximum training length show strong generalization to length 50 on the sort task.

“We see that models trained with 35 or higher length show strong generalization to length 50.”

Utilizing the alternative mode scratchpad still results in much worse length generalization performance than using no scratchpad.

“We see that utilizing this scratchpad still results in much worse length generalization performance than using no scratchpad.”

With balanced carry training, strong length generalization is observed for both forward and reverse addition on the hard carry evaluation setting.

“With balanced carry training, strong length generalization is observed for both forward and reverse addition on the hard carry evaluation setting.”

• Also stated in: § shifts sequence x to the right by n positions return kqv(indices(x) + n, indices(x), x, equals, default=default) · plain

  “With balanced carry training, strong length generalization is observed for both forward and reverse addition on the hard carry evaluation setting.”

The max and min aggregations of RASP-L can be represented by an Attention layer.

“Here we describe how the”

Models trained with rotary positional embedding show worse length generalization across the tasks.

“We observe worse length generalization across the tasks with rotary positional embedding.”

Models that do not have strong generalization also fail to output EoS only at the appropriate time, on both in-distribution and out-of-distribution lengths.

“we see that models that do not have strong generalization also fails to output EoS only at the appropriate time.This failing is observed on both in-distribution and out-of-distribution lengths.”

Most runs start to length generalize perfectly on 50 digit addition once the training length is greater than 40 for reverse addition with index hints on hard carry examples.

“Most runs start to length generalize perfectly on 50 digit addition once the training length is greater than 40.”

If two pre-softmax matrices are constructable, then any linear combination of them is also constructable.

“Now, if two matrices M 1 , M 2 are constructable, then so is any linear combination αM 1 + βM 2 for α, β ∈ R.”

All models generalize perfectly to 10 or more additional tokens at test time for the mode task.

“All models generalize perfectly to 10 or more additional tokens at test time.”

On models trained on longer sequences and with better length generalization, the end-on-last behavior is more robust.

“However, on models trained on longer sequences (and has better length generalization), this behavior is more robust.”

For the start-on-first and increment-by-1 counterfactual tests, all models exhibit near perfect performance both in-distribution and out-of-distribution.

“We see that for the start-on-first test and the increment-by-1 test, all models exhibit near perfect performance both in-and out-of-distribution.”

Better generalization is observed when models see greater coverage of sequence lengths at train time.

“We observe better generalization when models see greater coverage of sequence lengths at train time.”

The paper observes quite strong length-generalization even in its relatively small experiments.

“and indeed we observe quite strong length-generalization even in our relatively small experiments.”

There is strong correspondence between the model's behavior and what would be expected from the correct algorithm.

“Overall, we observe strong correspondence between the model's behavior and what we would expect from the correct algorithm.”

RASP program length does not perfectly correspond to Transformer-complexity.

“However, depending on the operations, it can be possible to represent multiple lines of RASP-L in a single layer of a Transformer, and so RASP program length does not perfectly correspond to Transformer-complexity.”

For a boolean function that depends on its first coordinate, restricting that coordinate to 1 strictly reduces its degree profile.

“Then, restricting the first coordinate of f to be 1 strictly reduces its degree profile: DegP(f | x1=1 ) < DegP(f )”

Easy Scratchpad exhibits significantly stronger length generalization than Hard Scratchpad.

“We observe that Easy Scratchpad exhibits significantly stronger length generalization than Hard Scratchpad, shown in Figure 10b.”

For the end-on-last counterfactual test, models trained with shorter lengths do not learn to robustly output EoS on long test sequences once the ending condition is met.

“For the end-on-last test, we see that models trained with shorter lengths do not learn to robustly output EoS on long test sequences once the ending condition is met.”

For the mode task, no scratchpad significantly outperforms scratchpad, whether measured on final answer accuracy or exact match of the entire scratchpad output.

“We see that no scratchpad significantly outperforms scratchpad, whether measured on the final answer accuracy or the exact match of the entire scratchpad output.”

The construction for max-aggregation yields an attention matrix that selects the argmax over v_m P(q_i, k_m).

“= 1{j = arg max m v m P (q i , k m )}(6) as desired.”

Length generalization is not inherently problematic for the Transformer architecture.

“suggests that length generalization is not inherently problematic for the Transformer architecture-though it clearly does not occur for all tasks.”

The RASP-Generalization Conjecture captures most known instances of length generalization on algorithmic tasks.

“This simple conjecture remarkably captures most known instances of length generalization on algorithmic tasks.”

If the minimal RASP-L program correctly length-generalizes, then the Transformer will length-generalize.

“Thus, if this minimal program correctly lengthgeneralizes, then so will the Transformer.”

If positional encodings are omitted, a fixed setting of Transformer weights defines a sequence-to-sequence function on sequences of arbitrary length.

“If we omit positional encodings for simplicity, then a fixed setting of Transformer weights defines a sequence-to-sequence function on sequences of arbitrary length.”

The Transformer architecture is already equipped with a natural notion of length-extension.

“The crucial observation is that the Transformer architecture is already equipped with a natural notion of length-extension.”

For symbolic tasks, Transformers tend to learn the shortest RASP-L program that fits the training set.

“Toy Model (RASP MDL Principle).For symbolic tasks, Transformers tend to learn the shortest RASP-L program which fits the training set.”

There is no unifying framework for reasoning about length generalization in Transformers that captures both their failures and capabilities and applies to a broad class of symbolic reasoning tasks.

“However, there is no unifying framework for reasoning about length generalization in Transformers which captures both their surprising failures and surprising capabilities, and applies to a broad class of symbolic reasoning tasks.”

If that function applies the correct transformation for inputs of any length in the context, then the Transformer can be expected to length generalize.

“If this function applies the correct transformation for inputs of any length in the context, then we can expect it to length generalize.”

The RASP toy model of learning predicts the correct experimental result in the boolean conjunction setting.

“Thus, our RASP toy model of learning predicts the correct experimental result in this setting.”

The count task can be solved by the RASP-L program in Figure 2.

“This task can be solved by the RASP-L program in Figure 2.”

If the internal state is written on the scratchpad each iteration, then the Transformer only needs to simulate one iteration in one forward-pass, which is now possible.

“However, if the internal state is written on the scratchpad each iteration, then the Transformer only needs to simulate one iteration in one forward-pass, which is now possible.”

We cannot expect to learn a 'sum' operation which generalizes to numbers larger than the training sequences.

“Moreover, we cannot expect to learn a 'sum' operation which generalizes to numbers larger than the training sequences.”

The carry propagation required by the standard addition algorithm is difficult to simulate due to causal masking.

“but this is difficult to simulate due to causal masking.”

• AssumptionRests on an assumption: The standard addition algorithm requires the carry value to be propagated in reverse order from least- to most-significant digit.

The mode scratchpad reduces the likelihood that the final token corresponding to the answer learns the correct solution.

“This shows that not only is the scratchpad difficult to generalize on (low EM), but it also reduces the likelihood that the final token corresponding to the answer learns the correct solution.”

These results demonstrate the first instance of strong length generalization on decimal addition for Transformer models trained from scratch.

“To our knowledge, these results demonstrate the first instance of strong length generalization on decimal addition for Transformer models trained from scratch.”

These factors are necessary to prevent shortcut programs from being learned.

“These factors are necessary in preventing shortcut programs from being learned.”

Formatting the output in reverse-order enables simple and causal propagation of the carry.

“This enables simple and causal propagation of the carry where each step can reference the previous output to determine the current carry, similar to the standard addition algorithm.”

A Transformer-specific measure of complexity can be more predictive than architecture-agnostic measures of complexity, in certain settings.

“Rather, this section illustrates how a Transformer-specific measure of complexity can be more predictive than architecture-agnostic measures of complexity, in certain settings.”

Addition is a difficult task for Transformers.

“Addition and parity have both been studied extensively as difficult tasks for Transformers.”

Taking the sum of the entire sequence and determining its parity cannot naturally be computed in a numerically stable way for arbitrarily large sums.

“This cannot naturally be computed in a numerically stable way for arbitrarily large sums.”

In copy with repeating tokens, since the tokens are not unique, the induction-head is no longer helpful.

“Since the tokens are no longer unique, the induction-head is no longer helpful.”

In addition, the iteration's state is external: it can be decoded from the input context itself.

“Both tasks require some form of sequential iteration, but in the case of addition, the iteration's state is external: it can be decoded from the input context itself.”

Parity is a difficult task for Transformers.

“Addition and parity have both been studied extensively as difficult tasks for Transformers.”

The minimum-degree-interpolator of the train set does not behave like the Transformer in the boolean conjunction experiment.

“We now claim that the minimum-degree-interpolator of the train set does not behave like the Transformer in the above experiment.”

Reverse-order addition is easier for autoregressive Transformers.

“The observation that reverse-order addition is easier for autoregressive Transformers was made in Lee et al. (2023)”

• cites Lee et al. (2023)Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

These results demonstrate the first instance of strong length generalization on parity for Transformer models trained from scratch.

“To our knowledge, these results demonstrate the first instance of strong length generalization on parity for Transformer models trained from scratch.”

The mode scratchpad is a more difficult task when considered in terms of RASP-L.

“However, although this scratchpad provides more supervision for what algorithm the model should learn, it is a more difficult task when considered in terms of RASP-L.”

Adding index hints allows avoiding index-arithmetic, which is the most prohibitive aspect of representing the addition algorithm in RASP-L.

“Adding index hints thus allows us to avoid index-arithmetic, which is the most prohibitive aspect of representing the addition algorithm in RASP-L.”

The Transformer correctly computes the boolean AND, even on bits which were irrelevant at train time.

“That is, the Transformer correctly computes the boolean AND, even on bits which were irrelevant at train time.”

Scratchpads can simplify the next-token prediction task, making it amenable to a short RASP-L program.

“scratchpads can simplify the next-token prediction task, making it amenable to a short RASP-L program.”

The failures of length generalization can be attributed to prematurely outputting an EoS token before the full length of the sequence is outputted.

“This suggests that the failures of length generalization can be attributed to prematurely outputting an EoS token before the full length of the sequence is outputted.”

The RASP conjecture provides a unifying perspective on when length generalization and algorithm learning are possible.

“Remarkably, our RASP conjecture captures most if not all known instances of length generalization, and provides a unifying perspective on when length generalization and algorithm learning are possible.”

The RASP conjecture captures most if not all known instances of length generalization.

“Remarkably, our RASP conjecture captures most if not all known instances of length generalization, and provides a unifying perspective on when length generalization and algorithm learning are possible.”

Copying unique tokens makes length generalization much easier, since it can be solved by an induction head.

“Copying unique tokens makes length generalization much easier, since it can be solved by an induction head.”

The linear-time restriction applies to any RASP-L program which does not use max/min aggregation types.

“However, this restriction applies to any RASP-L program which does not use these types of aggregation.”

Increased data diversity increases the likelihood that the model learns a length-generalizing solution.

“This demonstrates that with increased data diversity, we also increase the likelihood that the model learns a length-generalizing solution.”

• Also stated in: § shifts sequence x to the right by n positions return kqv(indices(x) + n, indices(x), x, equals, default=default) · boosted

  “This demonstrates that with increased data diversity, we also increase the likelihood that the model learns a length-generalizing solution.”

Whether Transformers compositionally generalize depends crucially on the structure of the task.

“The resolution here is that whether Transformers compositionally generalize or not depends crucially on the structure of the task, as we have discussed.”