Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

I 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.

strengths_and_weaknesses: Strengths
- This addresses an important problem in the deployment and useful of LLMs
- Naively training on more long-sequence lengths tasks is a solution, however, the number of tasks with very long sequences often diminishes.
- This work crucially focuses on the scaling properties of these techniques, rather than focusing on a single model scale.
- 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.

Weaknesses
- 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.
- 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.
- 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. 
- 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.

Suggestions
- 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).
- Reverse the plot order for vanilla fine-tuning and scratchpad fine-tuning.
- 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.  
- Put Figure 2 in supplementary and move up one of the results plots. 
- Provide an example using either the parity or variable assignment task for the "Instance Length as Number of Steps in a Markov Process" section.
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.
- 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?
- 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?
- 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.

limitations: None listed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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). 

They 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). 

I 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). 
strengths_and_weaknesses: Strengths:
1. New discussion of the ability of transformers to extrapolate to longer sequences with scratchpad prompting and/or finetuning. 
2. Interesting analysis of why the models that fail do so in some cases.

Weaknesses:
1. 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. 
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. 

1: parity-1

1: parity- 0

0: parity- 0

......

I'm wondering if you've tried that.


limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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) 	finetuning 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.
In 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. 

strengths_and_weaknesses: ### Strengths
- 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.
- 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.
- The paper also studies three popular approach for downstream applications of LLMs, namely finetuning, scratchpad finetuning, and prompt based method.
- Overall, I like the analysis presented in the paper.

### Weaknesses
- 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?	
						 	
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].

[1] [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://aclanthology.org/N18-1119/). Matt Post, David Vilar. NAACL 2018


limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

strengths_and_weaknesses: Strengths
+ Controlled experiments to test for length generalization.
+ Detailed experiments in various settings.
+ Analysis demonstrating benefits of existing technique scratchpad, also called chain-of-thought, compared with finetuning and few-shot prompting.

Weaknesses
- 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.
- (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.
- 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.
- 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.

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

The 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.

“...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?

Did 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…”

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.

I agree with the authors, and don't see negative societal impact caused by this work.
review_title: null

Meta-review: metareview: This paper studies the problem of length generalization for LLMs, and shows that fine-tuning and prompting alone are not sufficient to address it. It introduces a "scratchpad" extension to LLM generation, which prompts the model to produce and condition on intermediate values during reasoning tasks, is a promising way of addressing this issue. The reviewers were unanimous in recommending acceptance, and thus I am happy to follow suit.
confidence: Certain
Decision: Accept