Exploring Length Generalization in Large Language Models

Real-world datasets often contain few long problem instances.

“real-world datasets often contain few long instances (see Figure 2).”

• Also stated in: § Contributions Our main contributions are as follows: · p. 3 · plain

  “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]”

• cites [6] [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 preprint arXiv:2103.03874 , 2021. - sourceCould not verify

  The Introduction (p. 1) describes the MATH dataset, and A.4 Difficulty Analysis (p. 14) compares the difficulty of long and short problems. Neither reports how frequently long instances occur in real-world datasets. Searches for “few long instances” and problem-length distributions found no passage addressing that claim. (LLM, conf=0.74)

  Experimental — accuracy not yet measured

Finetuning with scratchpad also fails to generalize to longer problems.

“We establish finetuning with scratchpad also fails to generalize to longer problems, in contrast to what is suggested by previous works [3].”

• Also stated in: § 4 Scratchpad Finetuning Still Fails at Length Generalization · p. 6 · plain

  “we find that scratchpad finetuning suffers from similar length generalization pathologies than vanilla finetuning does.”

• cites [3] [3] 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:2112.00114 , 2021. - sourceSupported

LaMDA models use T5 position biases to handle position information.

“LaMDA models use T5 position biases [16] to handle position information.”

• cites [16] [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:1910.10683 , 2019. - sourceSupported

Nye et al. [15] use scratchpad finetuning to achieve strong in-distribution performance on execution-based tasks such as code execution and computing polynomials.

“Nye et al. [15] use scratchpad finetuning to achieve strong in-distribution performance on execution based tasks such as code execution and computing polynomials.”

• cites [15] [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:2112.00114 , 2021. - sourceSupported

Unlike raw finetuning, few-shot scratchpad prompting scales with model size.

“Unlike raw finetuning, this approach does scale with model size [4].”

• cites [4] [4] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models, 2022. URL https://arxiv.org/abs/2201.11903 . - sourcePartly supported

  The Results (p. 4) report that few-shot chain-of-thought prompting gains performance as model size increases, with gains emerging around 100B parameters. The Discussion (p. 8) contrasts its scaling with standard prompting, not raw finetuning; our copy does not establish that raw finetuning fails to scale. (LLM, conf=0.86)

  Experimental — accuracy not yet measured

Wei et al. [4], Nye et al. [15] and Lewkowycz et al. [5] showed that combining prompting (in-context learning) with scratchpad strategies presents a powerful combination.

“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 a powerful combination.”

• cites [4] [4] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models, 2022. URL https://arxiv.org/abs/2201.11903 . - sourceSupported
• cites [15] [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:2112.00114 , 2021. - sourceSupported
• cites [5] [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. - sourceSupported

Naively finetuning transformer-based language models on length generalization tasks shows significant generalization deficiencies independent of model scale.

“We first establish that naively finetuning transformers on length generalization tasks shows significant generalization deficiencies independent of model scale.”

• Also stated in: § 3.1 Scale Doesn't Improve Length Generalization · p. 4 · plain

  “We find that model scale has a little effect on length generalization.”

Computational graph depth captures the difficulty of variable assignment problem instances better than the number of program operations.

“We again observed that a different notion of length (which we call computational graph depth ) captures the difficulty of problem instances better than number of program operations.”

• Also stated in: § 3.2 Transformers Prefer Parallel Strategies over Sequential Ones · p. 5 · hedged

  “We present two results that suggest that computational graph depth is a more relevant notion of length for transformers.”

In the finetuning regime, scaling data, model sizes, and compute does not improve length generalization.

“We find that in the finetuning regime, scaling data, model sizes, and compute does not improve length generalization (Section 3.1).”

• Also stated in: § 3.1 Scale Doesn't Improve Length Generalization · p. 4 · plain

  “We find that model scale has a little effect on length generalization.”

The number of 1s in the parity task appears to capture a more relevant notion of length for transformer models than the number of bits.

“The number of 1 s stands for the number of state changes contained in the input bit-string, and actually appears to capture a more relevant notion of length for transformer models (see Section 3.1).”

Even when a finetuned model attains perfect in-distribution accuracy, it performs poorly in out-of-distribution domains on length generalization tasks.

“We also observe that even when the model attains perfect in-distribution accuracy, it performs poorly in out-of-distribution domains.”

Trying to further enhance the performance of few-shot scratchpad prompted LLMs via finetuning yields mixed results, depending on the non-finetuned performance of the base model at the target task.

“Trying to further enhance the performance of few-shot scratchpad prompted LLMs via finetuning yields mixed results, depending on the non-finetuned performance of the base model at the target task.”

Distracting input tokens hurt length generalization performance more than distracting scratchpad tokens.

“The distracting input tokens are hurt length generalization performance more.”

Few-shot scratchpad prompting leads to dramatic improvements on longer problem instances.

“leading to dramatic improvements on longer problem instances.”

With the right scratchpad prompt, LLMs are able to generate correct scratchpad solutions.

“We find that with the right scratchpad prompt, LLMs are able to generate correct scratchpad solutions.”

On out-of-distribution data, the performance of the shuffled-ops baseline is on par with the models trained with the clean version of the variable assignment dataset.

“On OOD data, the performance of the shuffled-ops baseline is on par with the models trained with the clean version of the dataset.”

Length generalization pathologies persist even when using the padded scratchpad strategy.

“length generalization pathologies persist even when we use the padded scratchpad strategy”

Performance of the trained transformer on variable assignment is strongest on examples with small computational graph depth, even if these examples are long in terms of number of operations.

“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 terms of number of operations.”

Transformers initially pick up how to handle programs with a small computational graph depth throughout training and then move to more difficult programs.

“Transformers initially pick up how to handle programs with a small computational graph depth throughout training and then move to more difficult programs.”

Scratchpad prompting endows pretrained LLMs with the capability of variable length template matching.

“We corroborate these findings, and report that scratchpad prompting endows pretrained LLMs with the capability of variable length template matching (see Figure 8).”

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

“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-distribution.”

The few-shot finetuned model on the alternative synthetic prompt style for the coin-flip task shows significant length generalization pathologies.

“we observed that the few-shot finetuned model on this task also shows significant length generalization pathologies.”

• Also stated in: § E Effect of Prompt Style on Few-Shot Finetuning Performance · p. 16 · plain

  “the few-shot finetuned performance shows significant length generalization pathologies.”

The distribution shift induced by changing problem lengths falls outside the category where in-distribution loss predicts out-of-distribution generalization.

“Our experiments on the parity task indicate that the distribution shift induced by changing problem lengths falls outside of the this category.”

Generalizing in length is a challenge for language models at least up to the 100B parameter scale.

“Generalizing in length is a challenge for language models at least up to the 100B parameter scale.”

Removing all distractor tokens results in perfect length generalization.

“Removing all distractor tokens does result in perfect length generalization.”

Few-shot finetuning with scratchpad performs significantly better than the baseline model on both in- and out-of-distribution lengths for parity.

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

On the variable assignment task, length generalization is not strong with no finetuning.

“that's not the case for variable assignment”

On the parity task, length generalization is already strong with no finetuning.

“while length generalization is already strong with no finetuning on parity”

There are non-trivial interactions among finetuning, few-shot prompting, and scratchpad techniques.

“Interestingly, we observe non-trivial interactions among the three techniques; see Table 1.”

On the variable assignment task, few-shot finetuning and vanilla finetuning result in similar length generalization behavior.

“Both few-shot finetuning and vanilla finetuning result in similar length generalization behavior (Figure 7).”

Few-shot scratchpad prompting enables pretrained large language models to pick up scratchpad-templates that extrapolate to arbitrary lengths.

“Few-shot scratchpad prompting enables pretrained large language models to pick up scratchpad-templates that extrapolate to arbitrary lengths”

Distractors are the main culprit of failures for length generalization in scratchpad finetuning.

“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).”

When presented with sequential length generalization problems, transformers are biased toward learning non-sequential 'shortcut' solutions that fail at longer problem instances.

“The results presented in Section 3.1 establish that, when presented with sequential length generalization problems, transformers are biased toward learning non-sequential 'shortcut' solutions that fail at longer problem instances.”

For LLMs, certain skills, like length generalization, can be learned through in-context learning rather than through finetuning even in the presence of infinite data.

“This capability is significant, as it implies that for LLMs, 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.”

The non-sequential counting strategy does not allow for knowledge transfer between problems of different lengths.

“This strategy doesn't allow for knowledge transfer between problems of different lengths.”

Transformers are learning a non-sequential solution on parity that involves counting the number of ones in the input and then thresholding the output.

“This suggests that the transformers are learning a non-sequential solution that involves counting the number of ones in the input, and then thresholding the output.”

Computational graph depth captures a more relevant notion of difficulty on the variable assignment task for transformers.

“Computational graph depth captures a more relevant notion of difficulty on the variable assignment task for transformers.”

The lack of length generalization in vanilla finetuning and finetuning with scratchpads is caused by models' tendency to pick up non-sequential patterns that don't apply to longer problem instances.

“caused by models' tendency to pick up non-sequential pattern that don't apply to longer problem instances.”

It is not the number of operations, but computational graph depth that captures a more relevant notion of difficulty on the variable assignment task.

“it's not the number of operations, but computational graph depth that captures a more relevant notion of difficulty.”

The primary source of lack of length generalization is transformers' tendency to prefer parallel strategies that don't generalize to larger lengths over picking up sequential algorithms.

“the primary source of lack of length generalization is the transformers' tendency to prefer parallel strategies that don't generalize to larger lengths over picking up sequential algorithm”

For LLMs, certain skills, like length generalization, can be learned better through in-context learning rather than through finetuning, even in the presence of infinite data.

“This capability is also significant in that it implies that for LLMs, 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.”

Innovations in transformer architectures and/or training methodology/objective that alleviate the issues caused by distractor tokens have a chance at significantly improving length generalization.

“innovations in transformer architectures and/or training methodology/objective that alleviate the issues caused by distractor tokens have a chance at significantly improving length generalization.”