Exploring Length Generalization in Large Language Models
Authors: Cem Anil
Yuhuai Wu
Anders Johan Andreassen
Aitor Lewkowycz
Vedant Misra
Vinay Venkatesh Ramasesh
Ambrose Slone
Guy Gur-Ari
Ethan Dyer
Behnam Neyshabur
Venue: NeurIPS 2022 Accept (2022)
Keywords: length generalization
multi-step reasoning
large language models
out-of-distribution generalization

Abstract: The ability to extrapolate from short problem instances to longer ones is an important form of out-of-distribution generalization in reasoning tasks, and is crucial when learning from datasets where longer problem instances are rare. These include theorem proving, solving quantitative mathematics problems, and reading/summarizing novels. In this paper, we run careful empirical studies exploring the length generalization capabilities of transformer-based language models. We first establish that naively finetuning transformers on length generalization tasks shows significant generalization deficiencies independent of model scale. We then show that combining pretrained large language models' in-context learning abilities with scratchpad prompting (asking the model to output solution steps before producing an answer) results in a dramatic improvement in length generalization. We run careful failure analyses on each of the learning modalities and identify common sources of mistakes that highlight opportunities in equipping language models with the ability to generalize to longer problems.

Exploring Length Generalization in Large Language Models
Cem Anil -1,3, Yuhuai Wu', Anders Andreassen', Aitor Lewkowyez'
Vedant Misral, Vinay Ramasesh', Ambrose Slone', Guy Gur-Ari',
Ethan Dyer', Behnam Neyshabur'
Google Research, Blueshift Team
Google Research
University of Toronto, Vector Institute
Abstract
The ability extrapolate from short problem instances to longer ones is im- portant form of out-of-distribution generalization in reasoning tasks, and is crucial when learning from datasets where longer problem instances are rare. These include theorem proving, solving quantitative mathematics problems, and reading/- summarizing novels. In this paper, run careful empirical studies exploring the length generalization capabilities of transformer- based language models. We first establish that naively finetuning transformers on length generalization tasks shows significant generalization deficiencies independent of model scale. We then show that combining pretrained large language models' in-context learning abilities with scratchpad prompting (asking the model to output solution steps before producing an answer) results in a dramatic improvement in length generalization. We run careful failure analyses on each of the learning modalities and identify common sources mistakes that highlight opportunities in equipping language models with the ability to generalize to longer problems.
1 Introduction
Many natural problems, such as theorem proving and program synthesis, have a notion of length that strongly correlates with the difficulty of the task. However, in these domains, the number of available problems typically drops rapidly as a function of problem length (e.g. Figure 2). Hence, is desirable to learn from examples of shorter lengths to generalize to longer ones at least reduce the number of samples required for longer examples. We refer to this type problem as length generalization.
Recent work on large language models (LLMs) has shown consistent improvement in their per- formance by scaling model and dataset size. However, such models are still incapable of length generalization. For example, [1] shows that even though scale helps with solving arithmetic problems, scale alone likely insufficient for learning to solve instances of arbitrary lengths. This implies that models fail to learn the general algorithms that would enable this kind of generalization. Indeed, Razeghi et al. [2] showed that the performance of LLMs on mathematical calculations correlates with term frequency in the training data. This suggests that LLMs might have gained their current performance from surface-level memorization instead of learning to apply the correct algorithm.
A recent line of work proposes to use scratchpad, or chain-of-thoupg reasoning, when prompting LLMs [3, 4, 5] on multi-step tasks. Breaking down tasks into multiple small steps and presenting these steps to the model leads to improved performance across variety of reasoning tasks including word problems, arithmetic, and code execution.
We perform a systematic study of length generalization with transformer-based large language models. We consider problems in which learning an algorithm can principle enable model to extrapolate
'Work done while interning at Google Research, Blueshift Team. anilcem0cs. toronto. edu, mnhuai@google com, neyshabur@google com.
Correspondence to:
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In Distribution Lengths
Out-of-Distribution Lengths
Length
Length
Length
Length 29
True
True
True
False
False
1 False
Falss
1f x == True:
1f a = False:
a True
z True
y True
if True
k and
2 and y (...) if y:
print(y)
False
print(k)
print(a)
true
2 = and x y x!
print(2))
Figure I: Examples of variable assignment problems: Can transformer language models learn from short
instances of the Variable Assignment task (left) extrapolate much longer instanees (right)? Length generalization the ability to learn from shorter/easier instances a problem handle longer/harder instances.
Techniques
In-distribution
Out-of-distribution
Improves with scale
Fine-tune
Prompting
Fine-tune Prompting
X X
XX
Fine-tune Scratchpad
Prompting Scratchpad
Fine-tune Prompting Scratchpad
Table I: Performance on length generalization tasks of three techniques that language models admit: (1) Finetuning, (2) Prompting (or in-context few-shot learning) and (3) Scratchpad (Chain-of-Thouue Thouuhh reasoning). We find that each technique (and the combinations thereof) have different modes of failure and present different trade-offss regarding in and out-of-distribution coverage. signifies poor / signifies nontrivial, /V signifies near-perfect performance. (*) Refers to task- disk-dependency.
from short examples to problems of arbitrary length. In particular, we focus on two simple algorithmic tasks, parity and variable assignment, in which the model needs to keep track of state in order to extrapolate to longer lengths (see Figure 1). These problems are illuminating because their simplicity allows us probe the failure modes as well contrast the learned solutions with the ground truth algorithm. They provide us with a setting to study how/when these large language models start to fail.
We study combinations of three kinds of techniques for LLMs: finetuning, few shot prompting (also referred to as in-context learning), and use of scratchpad (also referred to as chain-of soan-offthouu of-thought), to understand the role of each method and the interplay among the three in length generalization. Interestingly, we observe non-trivial interactions among the three techniques; see Table 1.
Contributions Our main contributions are as follows:
We define and characterize the problem of length generalization using notions such as state tracking. execution depth, and per-step error rate. We study and carefully design two tasks, parity and variable assignment, that measure length generalization (Section 2).
We find that in the finetuning regime, scaling data, model sizes, and compute does not improve length generalization (Section 3.1). We also observe that even when the model attains perfect in in-distribution accuracy, it performs poorly in out-of aatto--distribution domains. Surprisingly, different hyperparameter choices for finetuning have large effect on length generalization performance, while having minimal effeec the final in-distribution performance (Section 3.3).
We establish finetuning with scratchpad also fails to generalize to longer problems, in contrast to what is suggested by previous works [3]. We look into three potential failure cases: positional encoding, the presence of distractors, and end of token prediction, and conclude that distractors are the main culprit of failures for length generalization (Section 4).
We show that in the in-context learning regime, use of scratchpad shows a qualitatively different behavior and significantly alleviates the decay of performance on longer problems. This capability is significant, as it implies that for L.Ms, there are certain skills, like length generalization, that can be learned through in-context learning rather than through finetuning even in the presence of infinite data. This is in stark contrast to the common norms of machine learning (Section 5).

---

Archive of Formal Proofs
MATH dataset
10
10
10a
count
10a
count
10a
102
10
10a
100
1000
2000
3000
1000
2000
3000
proof length
number of tokens solution
Figure 2: Real world datasets have heavy tails in length: (left) Histogram of lengths for proofs presented in the Archive of Formal Proofs (right) Histogram of the number of tokens for solutions in the MATH dataset. [6]
2 Length Generalization
Many sequence easks-lsyy ones that require reasoning capabilities-hawv problem instances that differ terms of their lengths. Shorter instances often easier state, process, and handle, and require less compute to find the answer. By contrast, longer instances are more challenging to parse and require more compute solve. Tasks that have a reasoning component are especially well represented in this category multi-hop reasoning [7], program execution [8], deductive reasoning [9] and theorem proving [10], to name a few. Note that having to deal with differing problem lengths poses two significant challenges. First, it is often the case that one encounters longer problem instances than the ones ever encountered during training, and is required to extrapolate. Second, even though longer problem instances have much more variety, real-world datasets often contain few long instances (see Figure 2). Both these challenges are exacerbated learning agents are not able to generalize across and beyond the lengths they learn from during training. This paper about investigating to what extent transformer based language models are able to observe short problem instances and extrapolate longer ones.
Instance Length as Number of Steps in Markov Process It is possible to define problem length in many different ways to capture different aspects of problem difficulty. Does there exist notion problem structure observed in
of length that would expose the same seggthheneraliiation-eeeeee qualitatively very different settings? Such a framing would enable researchers to design algorithms and interventions that have the potential to generalize across broad range of tasks. To this end, we take the approach of characterizing length in the context of deterministic Markov process. From this perspective, length simply the number state transitions experienced by an initial world state. In other words, the data-generation process can be described sampling an (1) initial state and a (2) variable number of state transformations to be applied sequentially on the initial state. The agent is provided both the initial state and the transformations, and is asked to predict the final state. This framing applies to a wide range of sequence problems, if not all of them ranging from more mechanical tasks such code and algorithm execution and theorem proving, less structured tasks, such as solving math problems and summarizing novels.
In our empirical investigation we focus on two synthetic tasks: parity and variable assignment. These tasks avoid problem-specific subtleties that could mislead our analyses, while strongly capturing the deterministic Markov process structure.
2.1 Tasks
Parity: The parity task is an age-old learning problem that requires the trained agent to predict whether a bit-string has an even or odd number of ones in it. For example, the parity of the bitstring [0, 1, 0, is "odd" (or 1) opposed to "even" (or 0), because there is an odd number of is in the bit-string. The parity task admits a sequential solution that enables length generalization in straightforward way: simply process the bits left-to-right and record the parity of the bits processed so far as the state. The default notion of length in the parity task is the number of bits in the input. However, we also experiment with a version where the number of bits is kept constant, and the number of 1s (i.e. the parity flipping bit) is systematically varied. The number of is stands for the number of state changes contained the input bit-string, and actually appears to capture a more relevant notion of length for transformer models (see Section 3.1).
3

---

Parity- Vanilla Finetuning
Variable Assignment Vanilla Finetuning
100
model: 2 244m
100
model el: 244m
model: 422m
95
model: el: 422m
90
model: 1b
model: 1b
model: 64b
model:
accuracy
training
accuracy
training
80
70
60
70
65
60
10
20
30
40
10
15
lengths
lengths
Figure 3: Finetuned Length Generalization performance doesn't improve with scale: Models of vastly different scales fail length generalization both Parity and Variable Assignment tasks, displaying identical generalization pathologies. The x-axis represents problem length and the y-axis represents the accuracy attained at that problem length. The training lengths are highlighted in grey.
The Boolean Variable Assignment task is designed to capture arbitrarily long, potentially branching unidirectional exccution flows. An instance of this task can be seen in Figure The inputs consist of semantically correct (i.e. bug-free) Python programs in which each line contains a boolean variable assignment operation. The output is simply the value of the variable presented in the final line of the program. The sequential solution to this task is simply execute the program line by line while keeping track of the state of all variables.
Boolean Variable Assignment Task:
The data generation procedure involves randomly generating execution flows that involve Boolean operations; see Supplementary Material (SM) for details.
We focus evaluations two variants of this dataset. (1) The diverse variable assignment split consists of a wide range of boolean operators available and is intended to contain maximally diverse programs. (2) The chain-like variable assignment split consists only of operations that compose the values of already defined variables. This results in long chains of dependencies between the initial values of the variables and the queried one, ensuring that there almost no redundant operations in the program (i.e. operations that can be removed without affecting the output of the program). This split emphasizes the sequential nature of the variable assignment problem.
3 Standard Finetuning Fails at Length Generalization
We begin by demonstrating that finetuning transformer models on aangth-generalization tasks results in poor out-of-distribution performance. In experiments use LaMDA 2 decoder-only models. These checkpoints were trained using general natural language data. We use the AdaFactor optimizer [1]] during finetuning, and tune the learning rate, batch size and dropout. We trained the networks until the in-distribution validation accuracy settles (20000 gradient steps for parity and 18000 gradient steps for variable assignment). The loss was only computed on the target tokens (i.e. the model wasn't 't trained to model the input questions).
3.1 Scale Doesn't Improve Length Generalization
Parity: We finetuned four pretrained LaMDA models with 244m, 422m, 1 and 64b parameters on the parity task, where the training distribution included randomly sampled bitstrings of length 10 to 21. We then evaluated the performance on bitstrings of length 3 to 40; see Figure 3. We find that model scale has a little effect on length generalization.
Variable Assignment: We finetuned the same models on the chain-like Variable Assignment Task, described in Section 2. We kept the in-distribution lengths at to 8. and evaluated the test performance on lengths 3 to 19. The results can be seen in Figure 3. Just like in the parity task, while the in- distribution performance (near) perfect, distr--iitti performance degrades rapidly as length increases. To get sense of just how weak the out-of-distributin a 422m model on the same dataset, except we shuffled the operations before feeding to the model. This removes the sequential dependency between the operations, and helps us establish a
performance is, we also trained
We omit the name of the model for the purpose of anonymization.
4

---

Parity Scratchpad Finetuning
Variable Assignment -cratchpad Finetuning 100
100
model: 125m
model: 244m
model: 244m
model: 422m
model: 422m
model: 1b
model: 64b
model: 64b
accuracy
60
training
accuracy
training
70
20-
60
30
10
155
lengths
lengths
Figure 4: Scratchpad finetuning displays poor length generalization: Scratchpad finetuning displays quali- tatively similar length generalization pathologies as vanilla finetuning. The x-axis represents prohlem length and the y-axis represents the accuracy attained at that problem length. The training lengths are highlighted grey.
strong baseline that only predicts the answers based on non-sequential, spurious correlations. The accuracy-length curves for the baseline can be found in SM.
3.2 Transformers Prefer Parallel Strategies over Sequential Ones
The results presented in Section 3.1 establish that, when presented with sequential length generaliza- tion problems, transformers are biased toward learning non- con-sequential "shortcut" solutions that fail at longer problem instances. We ran additional experiments to gain a better understanding of the nature of this generalization pattern.
On parity, we ran finetuning on a different distribution of bit-strings: Instead of first randomly sampling the number of bits the input bit-string, then sampling the values of the bits, we fixed the total number of bits in the input, and only varied the number of ones in the bit-string uniformly. We trained with 10 to 20 ones in the input distribution and tested on an interval containing to 30 ones. This makes sure that the number of tokens (now fixed at 30) is now disambiguated from number of state changes, which for parity is equal to the number of ones. The difference between in and out-of- distribution performance is even starker for this data distribution (Figure 5) while in-distribution performance was 100%, OOD performance was roughly equivalent to random prediction'. This suggests that the transformers are learning non-sequential solution that involves counting the number of ones in the input, and then thresholding the output. This is not surprising, given that self-attention is an equivariant transformation capable of performing pooling operations like max-pooling [12]. This strategy doesn't allow for knowledge transfer between problems of different lengths. Note that this bottom-up counting behaviour is complementary to the left-to-right counting behaviour displayed by recurrent models Suzgun et al. [13]. On the variable assignment dataset, we finetuned a 255m LaMDA model on the diverse split of the variable assignment dataset of programs up to 16 lines, and evaluated on the same data generating distribution up to 32 lines. We measured the evolution of the model's 'ss accuracy with respect training iterations on different program lengths (quantified by number of lines). The results are in SM.
We again observed that different notion of length (which we call computational graph depth) captures the difficulty of problem instances better than number of program operations. A variable assignment program can be represented as computational graph where each node corresponds to a variable, and each edge corresponds to an operation. Computational graph depth is the length of the longest dependency chain that connects to the queried variable node. This notion of length corresponds to the highly parallelizable strategy of executing programs by iteratively resolving computational graph dependencies. We present two results that suggest that computational graph depth is a more relevant notion of length for transformers. (1) Inspecting the order of problem instances in which the trained transformer correctly solves this task, we find that performance is strongest on examples with small computational graph depth, even if these examples are long in
'The periodic 0% and near 100% performance on OOD lengths is due to the models' tendency to output 0 or 1 depending on whether the input has a significantly higher ratio of Os or 1s. On average, the accuracy on OOD length is not better than random guess.
5

---

Parity fixed length
Parity 00D sensitivity
100
100
I: 2e-05,
bs: 32
2e-05,
bs:
80
80
Ze: 04,
bs: 32
2e-04,
bs:
accuracy
accuracy
2e-03,
bs: 32
2e-03,
bs: 128
training
20-
model: 422m
model:
training
20
10
20
40
number of ones
lengths
Figure (left) Complete lack length generalization: Transformers trained on the parity task have difficulty generalizing to bit-strings that have a different number of 1s. (right) Sensitivity to hyperparameters: Trained networks sharing architecture, data and in in-distribution loss can have very different length generalization performances. Ir stands "learning rate" and by stands for "batch size".
terms of number of operations. (2) The transformer does a good job of handling programs with an out-of-distribution number of operations, but for which computational graph depth is in in-distribution.
3.3 In-Distribution Generalization Doesn't Predict OOD Generalization Length Generalization Tasks
Prior work on out-of-distribution generalization establishes that in many tasks, in-distribution loss is a strong predictor of out-of-distributtion generalization [14]. Our experiments on the parity task indicate that the distribution shift induced by changing problem lengths falls outside of the this category. Figure 5 shows how the same model trained on the same data achieving roughly the same in-distribution cross entropy loss behaves on OOD data, where the difference solely induced by the choice of different hyperparameters.
4 Scratchpad Finetuning Still Fails at Length Generalization
has been shown in prior work that it's possible to get pretrained LLMs to solve a given task by not only outputting the answer, but also the solution steps behind it. Nye et al. [15] scratchpad finetuning to achieve strong in-distribution performance on execution based tasks such as code execution and computing polynomials. While they also report modest length generalization results on integer arithmetic, we find that scratchpad finetuning suffers from similar length generalization pathologies than vanilla finetuning does. The results on parity and variable assignment tasks can be seen in Figure 4. The precise scratchpad strategies used for these tasks are described in detail in SM.
Error analysis: To understand the causes of failure in training scratchpad strategies, focused on two architectural choices that could account for the poor performance: (I) how transformers encode position information, and (2) whether the transformers are trained to predict end-of-sequence (EOS) token. LaMDA models use T5 position biases [16] to handle position information. If the network is only trained with short instances, position biases that handle longer positional distances might not be trained, explaining poor length generalization. Similarly, Newman et al. [17] report that networks trained with EOS token prediction often suffer from generalizing to longer problem instances, because of the models' tendency to emit EOS tokens prematurely, as well as the EOS tokens' effect the representations that get learned.
We tested the extent to which these effects can explain lack of length generalization as follows. We padded both the input bit-strings and the scratchpad content with dummy padding tokens to make the token count the same. We also augmented the input and scratchpad targets with the same number of padding tokens on the left and right that the relevant bit to attend to when executing the sequential scratchpad strategy corresponds to the same T5 position bias bin. Examples of the updated taput-target pairs be in SM. While this intervention helps, the trained models still display significant length generalization issues.
To gain further insight about the source of the problem, we plotted how the scratchpad target prediction
error rates change as a function of (1) how far along one constructing the scratchpad, and (2) the length of the input bit-string. The results can be seen in Figure 6. The fact that the model makes

---

Partial sequence accuracy
First Error Rate
3.0
100
training
35
Error Rate (percent)
2.5
instance length
accuracy
2.0
60
1.5
40
1.0
20
0.5
0-
10
20 30
0.0
1
7
9 11 position
13
15
17
19
scratchpad steps
Figure 6: (left) Effect of imput length on per-step seratchpad accuracy: Points corresponds to the accuracy (y-axis) of the first scratchpad steps (x-axis) parity instances of variable length (color). If the input length out-of-distribution even in- diddribbuttion scratchpad steps are inaccurate, implying the model hasn't learned an attention pattern that generalizes to longer bit strings,,s. (right) Roughly constant per-step error rate: The per-step error rates of the LaMDA 128b model, few-shot finetuned on the coin-flip version of the parity task remain roughly constant across the scratchpad steps. This is in stark contrast with zero-shot scratchpad finetuned increase abruptly when the model is evaluated OOD lengths.
models, where the per-step
mistakes in in-distribution scratchpad steps when the input has an OOD length implies that the attention mechanism isn't capturing the relevant part of the input form the scratchpad output. See SM for additional analysis.
5 Scratchpad Prompting Significantly Improves Length Generalization
Wei et al. [4], Nye et al. [15] and Lewkowycz et al. [5] showed that combining prompting (i.e. in-context learning) with scratchpad strategies present powerful combination. They demonstrate that pretrained LLMs, without the help of any finetuning, can solve grade school math word problems and execute pieces of code with nontrivial correctness [15], when prompted with the right scratchpad strategy. We corroborate these findings, and report that scratchpad prompting endows pretrained LLMS with the capability of variable length template matching (see Figure 8). That is, in-context learning enables the model to "learn" solution steps from a small number of short instances, and apply the same template on significantly longer instances with a high degree of accuracy.
5.1 Few-shot scratchpad
Contrary to vanilla and scratchpad finetuning, we find that under the right conditions, few-shot scratchpad strategies sometimes significantly improves LLMs' capability to extrapolate lengths much further than what pretraining weights grant them.
To evaluate the performance of few-shot conditioning with scratchpad inputs without any finetuning, we phrase the parity problem in natural language as a coin flipping task. An example for the few-shot prompts used can be seen in Figure 8. Wei et al. [4] also report results the coin-flip task: the scratchpad format we used differs from theirs in that while ours respects the sequential nature of the task (i.e. each coin flip corresponds strategy involves summing up the number coin flips, then deciding on the final output based on the evenness/oddness of the sum. Also, while they only test up to 4 flips, we go up 20 flips while still attaining highly nontrivial accuracy levels.
step in the scratchpad solution), Wei et al. [4]'s seratchpad
For the variable assignment task, scratchpad strategy involves copying over the program that's being executed, with comments added between lines specifying the value of the variable that was assigned in the line above. Instances of this scratchpad strategy be in SM.
Figure shows the performance of the pretrained LaMDA 128b model on the coin-flip version of the parity task. Figure 8 shows an instance of how length 3 prompt can induce the model to correctly output step scratchpad. We find that with the right seratchpad prompt, LLMSs are able to generate correct scratchpad solutions. This reduces the problem simply filling in the content of
7

---

Parity scratchpad prompting
Var. Assignment scratchpad prompting
100
100
90
80
accuracy
accuracy
70
60
no finetuning few shot eval
60
zero shot finetuning zero shot eval few shot finetuning few shot eval codex
no finetuning few shot eval
zero shot finetuning zero shot eval
few shot finetuning few shot eval training
training
30
5
10 lengths
15
20
5
10
15
20
lengths
Figure Few-shot finetuning with scratchpad displays qualitatively different behaviour on parity and variable assignment tasks. On parity, where the non-finetuned model already performs very well, few-shot- finetuning with scratchpad leads to significant performance boost over zero-shot finetuning with scratchpad. On variable assignment, where the hase model doesn't 't perform poorly, there's not a significant gap between few-shot finetuning and pero-shot finetuning with scrathpad. The performance OpenAl's Codex model [18] on the variable assignment task is also provided.
Exemplars (x3)
Question: The cain heads up. (3) Then Kara fliss. (2) Then Luke doeent fip. (1)
Then Auslin flips. the still heads up?
Solution: Coin initially heads up. (3) After
Solution: Coin initially heeds up. (20) After
Kara fllss, coin becomes talls. (2) Luke
Anthony doeen't flip, coin remeins heads. (19)
doesn't flip, so coin stays tails. (1) After Austin heads.
Eric flips,
(18)
flip,
Elizabeth doesn't flpp coin remains tals. (17)
After Adam doesn't flip, coin remains tails.
(16) Melissa flips,
Query
(15) Afler Kevin flips, coin becomes talls. (14)
After Steven flips, soin becomes heads. (13)
doesn't flp. (16) Then Melissa fips. (15)
Then Elizabeth doesn't fip. (17) Then Adam
Anthony doesn't fip. (19)
Question: The coin is heads (20) Then
Eric fipe. (18)
After Thomas
(4) After Amy flips, coin becomes heads. (3)
(...K5) After Jeffrey flips, cain becomes
becomes tails. (12)
Than Kovin fips. (14) Then Stavan fliss.
After Crystal flips, coin becomes tails
Then Thomas fliss. (12) (.. Then Jeffrey
Michelle doesn't flip,
tails,
flipe. (4) Then Amy flips. (3) Then Cryetal
(1) Aftor Jeromy fips, coin becomes heads.
flips. (2) Then Michelle doesn't flip. (1) Then
Jeremy flips.
still up?
Figure 8: Few-shot length generalization: The largest LaMDA model is able to map the seratchpad solution template from few short exemplars onto much longer queries.
the generation correctly by inferring the right state transitions without having to figure out how to extrapolate the solution template.
Few-Shot Finetuning with Scratchpad Strategies: ing, and scratchpad strategies improve length generalization?
Does combining finetuning, few-shot prompt-
We find that the answer is yes in the case of parity. As seen in Figure 7, few-shot finetuning performs significantly better than the baseline model, both on in- and out-of-distribution lengths. Note that the vanilla (i.e. no shot) finetuning baseline also outperforms the no no-finetuning baseline, it actually does worse on the larger lengths - a pathology that docsn't 't appear with few-shot finetuning.
The results point to a qualitatively different picture for the variable assignment task. Both few-shot finetuning and vanilla finetuning result in similar length generalization behavior (Figure 7). We hypothesize that this distinction is caused by the different pretrained performances that the model displays on these tasks: while length generalization is already strong with no finetuning on parity, that's 's not the case for variable assignment. In the latter case, the model is forced to acquire new skill via finetuning, which displays the same pathologies as zero-shot finetuning with scratchpad. As sanity check, we evaluated the (few-shot) finetuned performance of the pretrained model on an alternative, synthetic prompt style that yields poor performance without any pretraining: As expected by the aforementioned hypothesis, we observed that the few-shot finetuned model on this task also shows significant length generalization pathologies. The results can be found in SM. We leave more rigorous evaluation of this hypothesis as future work.
8

---

6 Related Works
There have been many attempts to study generalization from shorter/casier to longer/harder examples. Challenges in length generalization: Several existing works have investigated pathologies that arise when models are asked to generalize to processing and generating longer (measured by number of tokens) sequences. Newman al. [17] find that sequence models trained with and in the absence of the end-of-sequence token display qualitatively different length extrapolation behaviour and learn different representations. Dubois et al. [19] proposes modifications to the commonly used dot-product attention to improve the models' ability to extrapolate to longer sequences. Murray and Chiang [20] demonstrate that neural machine translation models tend to have bias towards generating shorter- than-desired translations. Yehudai et al. [21] show that length generalization issues are also present in training graph neural networks, where extrapolating across graph size presents a challenge. Ju et al. [22] propose a new attention mechanism to facilitate recurrent processing in transformer models. Press et al. [23] propose modifying transformer attention biases to facilitate generalization beyond the training context length. Concurrent work [24] propose a synthetic dataset named LEGO (Learning Equality and Group Operations), an instantiation of which resembles our variable assignment task where the only boolean operations allowed are assign and negate and assign, and overriding the values of variables is not allowed. Their analyses on OOD generalization largely complement ours: while we focus on decoder-only architectures and scratchpad strategies as way of carrying over state, they focus on encoder-only architectures, and investigate the effect of weight-sharing.
Easy-to-Hard generalization: Schwarzschild et al. [25] and Bansal et al. [26] use weight-tied neural networks to generalize from easy to hard examples. Schwarzschild et al. [25] also provide three tasks to benchmark easy-to-hard generalization. Dehghnn et al. [27] and Kaiser and Sutskever [28] assess the capabilities of their proposed architectures on easy-to-hard generalization problems.
Inductive Biases Related to Lenght Generalization: McCoy et al. [29] study the inductive bias of seq-to-seq learners on English question formation and English tense reinflection tasks and find that LSTM and GRU networks often display differing strategies, caused by the use of differing activation functions. Suzgun al. [13] find that recurrent networks can perform dynamical counting, and encode hierarchical representations, which enables them to solve nontrivial Dyck tasks using k-counters. Kharitonov and Chaabouni [30] also study the inductive bias of different architectures, and conclude that transformer and LSTM architectural have a tendency to learn hierarchical strategies, whereas CNN based strategies display more linear structure. He al. [31] propose a method to learn natural inference models that are not biased on spurious correlations. McCoy et al. [32] show that transformer models that display strong performance natural language inference can have superficial biases that fool them in systematic ways and proposes framework to think about these biases.
7 Conclusion
The ability to learn from shorter/easier problem instances to generalize to longer/harder ones is key capability in a large number of tasks, especially ones requiring reasoning. We defined the concept of length generalization and measured language models' length generalization capabilities. After conducting careful experiments using finetuning, scratchpads, and few-shot prompting, we reached the following conclusions: (1) Generalizing in length is challenge for language models least up to the 100B parameter scale. Both vanilla finetuning and finetuning with scratchpads suffer from lack of length generalization caused by models' tendency pick up non-sequential pattern that don't apply to longer problem instances. (2) Few-shot scratchpad prompting enables pretrained large language models to pick up scratchpad-tempie templates that extrapolate to arbitrary lengths, leading to dramatic improvements on longer problem instances. Unlike raw finetuning, this approach does scale with model size [4]. (3) Trying to further enhance the performance of few-shot scratchpad prompted LLMs via finetuning yields mixed results, depending on the oon-fineunned performance of the base model at the target task. We emphasize that the aforementioned few-shot variable length pattern matching capability - something that doesn't It require changing model architecture offers a qualitatively different approach to handle length generalization in contrast to prior art that introduced architectural modifications to achieve the same goal. This capability is also significant in that it implies that for L.MMs, there are certain skills, like length generalization, that can be learned better through in-context learning rather than through finetuning, even in the presence of infinite data.

---

References
[1] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 13:1877-1901, 2020.
[2] Yasaman Razeghi, Robert L Logan IV, Matt Gardner, and Sameer Singh. Impact of pretraining term frequencies on few-shot reasoning. arXiv preprint arXiv:2202.07226, 2022.
[3] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowyez, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114, 2021.
[4] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoe Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models, 2022. URL
https://arxiv.. org/ 2201 11903.
[5] Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, et al. Solving quantitative reasoning problems with language models. arXiv preprint arXiv:2206. 14858, 2022.
[6] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprini arXiv:2 2021.
[7] Haoyu Wang, Mo Yu, Xiaoxiao Guo, Rajarshi Das, Wenhan Xiong, and Tian Gao. Do multi-hop readers dream of reasoning chains? arXiv preprint A910: 14520, 2019.
[8] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732. 2021.
[9] Peter Clark, Oyvind Tafjord, and Kyle Richardson. Transformers as soft reasoners over language. arXiv preprint arXiv:2002.05867, 2020.
[10] Yuhuai Wu, Albert Qiaochu Jiang, Jimmy Ba, and Roger Grosse. Int: An inequality benchmark for evaluating generalization in theorem proving. arXiv preprint arXiv:2007.0292. 2020.
[11] Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning, pages 4596-4604. PMLR, 2018.
[12] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention- permutation-inven innvaaaatiinnn neural networks. In International Conference Machine Learning, pages 3744-3753, PMLR, 2019.
[13] Mirac Suzgun, Sehastian Gehrmann, Yonatan Belinkov, and Stuart M Shieber. Lstm networks can perform dynamic counting. arXiv preprint arXiv: 190.0399060034488 2019.
[14] Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understanding the failure modes of out-of distribbbiin generalization. arXiv preprint Stti::2010.15755, 2020.
[15] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski. Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:21 2021.
[16] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv: 101.19900....... 2019.
[17] Benjamin Newman, John Hewitt, Percy Liang, and Christopher D Manning. The eos decision and length extrapolation. arXiv preprint arXiv:2010.07174.0 2020.
10

---

[18] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et Evaluating large language models trained on code. arXiv preprint arXiv: arXiv:2107.03374 07700334, 2021.
[19] Yann Dubois, Gautier Dagan, Dieuwke Hupkes, and Elia Bruni. Location attention for extrapo- lation to longer sequences. arXiv preprint wrXiv:1911.0387, 2019.
[20] Kenton Murray and David Chiang. Correcting length bias in neural machine translation. arXiv preprint arXiv: 1808. 10006, 2018.
[21] Gilad Ychudai, Ethan Fetaya, Eli Mcirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pages 11975-11986. PMLR, 2021.
[22] Da Ju, Stephen Roller, Sainbayar Sukhbaatar, and Jason Weston. Staircase attention for recurrent processing of sequences. arXiv preprint 1oXiv:2/06.0445 04279,, 2021.
[23] Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations. 2022. URL https: / /ttp////epeeeeeeeee//eoem weetforumnidd-Reeeeee
[24] Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with lego: a synthetic reasoning task. arXiv preprint wrXiv:2206.0430) 2022.
[25] Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang. Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. Advances in Neural Information Processing Systems, 34, 2021.
[26] Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Gold- blum, and Tom Goldstein. End-to-end algorithm synthesis with recurrent networks: Logical extrapolation without overthinking. arXiv preprint arXiv:2202.05826. 2022.
[27] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. arXiv preprint arXiv:/807.0338 038/9, 2018.
[28] Eukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. arXiv preprint
arXiv:1511.08228, 2015.
[29] R Thomas McCoy, Robert Frank, and Tal Linzen. Does syntax need to grow on trees? sources of hierarchical inductive bias in eequence-to-sequee for Computational Linguistics, 8: 1210-,440, 2020.
networks. Transactions of the Association
[30] Eugene Kharitonov and Rahma Chaabouni. What they do when in doubt: study of inductive biases in seq2seq learners. arXiv preprint arXiv:2006.1499 2020.
[31] He He, Sheng Zha, and Haohan Wang. Unlearn dataset bias in natural language inference by fitting the residual. arXiv preprint arXiv: /00. 2019.
[32] Thomas McCoy, Ellie Pavlick, and Tal Linzen. Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference. arXiv preprint arXiv: 2019.
[33] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 121191992-1958 2014.
11


Reviews:
[{"review_id": "qqjv8sqO8Ve", "reviewer": "Reviewer_eFNS", "summary": "Inputs to transformers can be categorized by many different properties. Here the authors note that longer inputs might require more 'reasoning' steps and therefore they evaluate multiple different strategies, through the lens of input hardness (decided by the length). \n\nThey analyze chain-of-thought/scratchpad prompting on a few different artificial tasks and show that transformers have a hard time extrapolating to longer input lengths (and sometimes even to shorter ones). \n\nI feel like the contribution is important and the discussions here are new and interesting. The main downside is that the tasks are artificial and pretty far away from anything that could be useful in production (and that's OK). ", "questions": "There are many ways to 'prompt' for each task and it's hard to draw conclusions based on one prompt. For example, for the parity prompt, I think you may achieve better results if you use a prompt that's more similar to the one you used for the variable assignment problem- as in- compute the intermediate steps within the sequence of bits. \n\n1: parity-1\n\n1: parity- 0\n\n0: parity- 0\n\n......\n\nI'm wondering if you've tried that.\n\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. New discussion of the ability of transformers to extrapolate to longer sequences with scratchpad prompting and/or finetuning. \n2. Interesting analysis of why the models that fail do so in some cases.\n\nWeaknesses:\n1. Only artificial toy tasks are experimented with. It's not super clear which more 'realistic' tasks can be used here, but python programs might be applicable. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lzqXsQU2LdI", "reviewer": "Reviewer_4u87", "summary": "The paper studies the problem of length generalization in large language models (LLM) w.r.t fine-tuning and in-context learning approaches. To isolate the superficial artifacts in testing data that LLMs could exploit to make correct prediction without generalization, the paper sets up controlled experiments using two synthetic tasks: parity and variable assignment,  Studying two current common practice of fine-tuning and incontext learning on the controlled tasks, the paper found that (1) \tfinetuning fails at length generation regardless of model sizes.  When controlling the fixed length of input bit-string in parity task, but varying the number of bit 1, the paper shows that (2) transformer prefers parallel strategy but sequential one and still fails at generalization to the larger number of bit 1. In contrast to previous work, the paper points out that the in-distribution loss is not an indicator for OOD generalization.\nIn addition to fine-tuning, the paper also studies the length generalization for scratchpad finetuning and scratchpad prompting. The analysis shows that scratchpad prompting generalizes better than the finetuning and scratchpad finetuning. Combining finetuning and scratchpad prompting only improves the parity task. \n", "questions": "In the footnote 2, the authors said that they didn't constrain the the output of the models to 0s and 1s. I wonder what the picture would look like if the output is constrained to 0 and 1. I can imagine that for downstream application using LLMs, it's possible to allow the user to specify the constrain of the output. For instance, in Machine Translation, constrained decoding is desirable [1].\n\n[1] [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://aclanthology.org/N18-1119/). Matt Post, David Vilar. NAACL 2018\n\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The paper sets up controlled experiments with two synthetic tasks to probe the generaliability over sequence length of LLMs in fine-tuning and prompting setups.\n- By controlling the sequence length and the number of bit 1 in parity task and the length of the chain in the variable assignment task, the paper draws meaningful conclusions from the experiments.\n- The paper also studies three popular approach for downstream applications of LLMs, namely finetuning, scratchpad finetuning, and prompt based method.\n- Overall, I like the analysis presented in the paper.\n\n### Weaknesses\n- I think that the length generalization in the study is a particular kind of length generalization: linear generalization. By linear generalization, I mean that the information needed to solve the task can be stored incrementally in a window of context. For example, to solve the parity task, one can just keep track of odd/even at each input position. This is reflected in the format of coin tossing where the states can be tracked effectively. Thus, it provides a strong recency signal to the model to complete the task. I wonder if there is a synthetic task that requires non-linear generalization?\t\n\t\t\t\t\t\t \t", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EW8oAY2UCLM", "reviewer": "Reviewer_zzMA", "summary": "This paper shows that large language models (LLMs) trained on tasks of a certain length fail to generalize to longer sequence lengths. Long sequence length tasks introduce the difficulty of 1) extrapolation and 2) limited number of examples. They show that a combination of fine-tuning, scratchpad, and few-shot can partially overcome this deficiency up to 1b model scales. \n\nI believe this paper has the raw material to be significant, but it requires some updates to the plots and writing. This is an important analytical piece that is part of the solution for useful, long-range models. After the questions and limitations I've raised are sufficiently handled, I am willing to increase my score.\n", "questions": "- Related to the above weaknesses comment, I don't know precisely what you did to make this work? Your best method is described as \"Fine-tuning + prompting + scratchpad\". Does this mean you constructed examples using the scratchpad, fine-tuned on that data, but then at inference time, you additionally provided a few examples in the context? Please contrast this explicitly with \"Fine-tuning + scratchpad\" which performs poorly.\n- I don't understand the \"short-cut\" solution explained here: \"involves counting the number of ones in the input, and then thresholding the output\". What does \"thresholding the output\" mean? If the model counts the number of 1s and reports the parity, isn't that the true algorithm that generalizes?\n- In Figure 5, why were your fine-tuned models ever outputting tokens different than 0 or 1? In my experience, the label distribution is one of the first things learned when fine-tuning a LLM and anything other than that being output usually indicated a bug or an undertrained model. How did you confirm there was no error?\n- How are the authors supporting their claim about poor length generalization to the 100B model scale? Please cite or show data. Note that Codex models were only trained up to 12B parameters.\n", "limitations": "None listed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- This addresses an important problem in the deployment and useful of LLMs\n- Naively training on more long-sequence lengths tasks is a solution, however, the number of tasks with very long sequences often diminishes.\n- This work crucially focuses on the scaling properties of these techniques, rather than focusing on a single model scale.\n- They examine the \"short-cut\" solutions of the models to determine how they can do nearly perfect in the sequence range but rapidly diminish outside of it.\n\nWeaknesses\n- Unless I'm misunderstanding, it seems that many figures are computing the accuracy over a __single__ sequence. Can you please construct a full test set and compute the average accuracy for each sequence length (potentially including error bar ranges if it's not too cluttered). Figure 5 was especially confusing seeing accuracy fluctuate from 0% to 100% accuracy.\n- Is it possible your models are undertrained? Did you hold fixed the number of examples of the number of training steps? If the latter, please rerun each such that the stopping condition is peak validation accuracy. I'm noticing that for both cases when the learning rate is fairly high, the larger batch size outperformed the smaller batch sizes. If your models turn out to be undertrained, please redo the figures as well as adjust the writing elsewhere in the paper. For instance, the claim \"Surprisingly, different hyperparameter choices for finetuning have a large effect on length generalization performance\" may be explained by in-distribution examples being learned first followed by out-of-distribution examples and sufficient training normalizes these differences.\n- I find the constant switching of \"chain of thought\" vs. \"scratchpad\" confusing. For instance, it switches between both terms in Table 1 and its caption. It's good to describe that these are similar approaches, but perhaps then tell the reader that you're sticking with one for ease of reading. \n- Figure 6 (right) is very noisy and may not be suitable for a conference publication, as is. Please try to collect statistics and create smoothed plots with error bars.\n\nSuggestions\n- In addition to plotting the accuracy, an interesting appendix figure might be to plot the log-probability to the correct token on a log-log axis. This, in addition to reducing noise by including many examples per sequence length, may actually reveal non-trivial scaling properties (I guess it might). If so, please adjust the writing elsewhere in the paper and the Table. You might say it's \"poor scaling with model size\", but the data might not support definitive claims like \"We find that in the finetuning regime, scaling data, model sizes, and compute does not improve length generalization\" (L49).\n- Reverse the plot order for vanilla fine-tuning and scratchpad fine-tuning.\n- For each row of Table 1, please describe with an example and show the empirical results (at least in supplementary material). As a reader, I'm left wondering where this near-perfect approach appears and where I can see the failed results of \"Prompting\", \"Fine-tune + Prompting\", etc. Ensure all claims are backed with empirical results. If it's too long, put in supplementary.  \n- Put Figure 2 in supplementary and move up one of the results plots. \n- Provide an example using either the parity or variable assignment task for the \"Instance Length as Number of Steps in a Markov Process\" section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "66-le9Jbgeq", "reviewer": "Reviewer_jC5u", "summary": "This paper is about the performance of large language models (LLMs) when tested against longer sequences than seen in their training data, referred to as length generalization. The authors perform an analysis using two synthetic datasets of their design: 1) parity task (predicting whether the number of 1s in a binary sequence is odd or even), and 2) variable assignment task (predicting the value of a specified variable from a short python snippet). The experiments explore three specific settings with LLMs: 1) fine-tuning, 2) few-shot prompting, 3) scratchpads (which involves augmenting input and predictions with intermediate values). These settings are combined, i.e. fine-tuning + prompting. The main takeaway is that finetuning and prompting alone both fail on length generalization, and that scratchpad prompting (with and without finetuning) is effective for length generalization. At face value, these findings have substantial value for the research community, as scratchpad prompting is a relatively new technique, and is simple and highly effective. That being said, although synthetic tasks are often used in AI, the tasks presented by the authors are not well justified in the text and potentially faulty. Also, while the paper is mostly straightforward to follow, several experimental details are missing and related work is missing.\n", "questions": "Have the authors considered the interplay between finetuning and catastrophic forgetting? Prompt tuning (Lester et al.) has previously been shown to be effective as an alternative to full model finetuning, and I imagine it would have some benefits over few-shot prompting without pitfalls of finetuning. Lester et al. 2021 The Power of Scale for Parameter-Efficient Prompt Tuning\n\nThe parity task simply measures counting behavior. This is discussed in detail in McCoy et al. and Suzgun et al., and I believe should apply here as well. The observations in that paper are tied to specific architecture decisions (i.e. non-linearity). How do these prior works relate to the analysis you have presented? McCoy et al. 2020 Does Syntax Need to Grow on Trees? Sources of Hierarchical Inductive Bias in Sequence-to-Sequence Networks. Suzgun et al. 2019, LSTM Networks Can Perform Dynamic Counting.\n\n“...transformers are biased toward learning non-sequential “shortcut” solutions that fail at longer problem instances…” There is a large body of work about the bias of transformers. For instance, see He He et al. 2019. Unlearn dataset bias in natural language inference by fitting the residual; or McCoy et al. 2019. Right for the Wrong Reasons: Diagnosing Syntactic Heuristics in Natural Language Inference. Do these prior works present solutions to what you describe as a shortcut, and if so, why would scratchpad be preferable?\n\nDid you consider alternative synthetic tasks? For instance ListOps (Nangia and Bowman) or the various tasks from Zaremba and Sutskever 2015. Some of these other tasks include interesting properties not related to length, which I suppose could be a distraction from the analysis you set out to perform. Although this perspective potentially contradicts your statement, “This framing [related to Markov Process] applies to a wide range of sequence problems, if not all of them…”\n", "limitations": "This is analysis work and is directly about measuring limitations of various techniques. Perhaps the claims are over stating that we can extrapolate from small synthetic tasks to real world data, but certainly the results provide some value to that end.\n\nI agree with the authors, and don't see negative societal impact caused by this work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ Controlled experiments to test for length generalization.\n+ Detailed experiments in various settings.\n+ Analysis demonstrating benefits of existing technique scratchpad, also called chain-of-thought, compared with finetuning and few-shot prompting.\n\nWeaknesses\n- Although it is great to use synthetic tasks to measure for model ability, the parity task is not particularly well justified. In the parity task, the history is not necessary if the parity of the history is known. I realize this is by design to mimic a Markov process, but it remains unclear why it is important to think of data this way. Also, the 0% accuracy is concerning and seems easily fixable by constrained decoding like you suggest in footnote 2, perhaps by using a special indicator before predicting the parity label, or even running the sequence twice with continuation of {0, 1} and comparing their probabilities.\n- (minor weakness) The experiments explore only a highly specific mode of length generalization related to comprehending long sequences, and not for generating long sequences. Ironically, the best performing setting is the one that requires a variable amount of computation.\n- There are specific directions the paper explores that have been explored extensively in prior art: synthetic tasks, bias in data leading to shortcut strategies, and counting behavior in neural nets.\n- Some experimental details are missing, like dataset sizes, number of epochs finetuned, and whether the finetuning was done using only the labels or the full sequence.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept