Elamur Research
☰
home / papers / 2022 / Exploring Length Generalization in Large Language Models

Exploring Length Generalization in Large Language Models

Written for the Research library (claude-opus-5-5) from the paper text. Original — arxiv.org/pdf/2207.04901

Summary

In reasoning tasks such as formal proofs and math solutions, long examples are rare, so models must learn from short examples and still solve longer ones. This paper tests whether transformer language models can do that, which it calls length generalization. The authors define length as the number of state transitions in a deterministic Markov process. They build two synthetic probes: parity of bit-strings, and a Boolean variable assignment task made of Python-style programs, split into "diverse" and "chain-like" variants. Using pretrained LaMDA decoder-only checkpoints, they compare finetuning, few-shot prompting and scratchpad (chain-of-thought) outputs, alone and combined. Plain finetuning gets near-perfect accuracy on lengths seen in training but drops sharply on longer inputs, and bigger models do not fix this. Finetuning with a scratchpad also fails, mainly because of distractors. Few-shot prompting with a scratchpad, however, lets large models follow step-by-step templates that work on much longer problems, and this improves with scale. The main lesson is that some skills are learned better in context than through weight updates, with no change to the architecture.

Key points

  • Length distributions in real data are heavily skewed toward short instances. The examples given are proof lengths in the Archive of Formal Proofs and solution lengths in the MATH dataset.
  • Finetuned LaMDA models at 244M, 422M, 1B and 64B parameters all fail in the same way on longer instances. The authors say the problem persists up to about 100B parameters.
  • Finetuning used AdaFactor for about 20k steps on parity and 18k steps on variable assignment. Hyperparameter choices barely changed accuracy on seen lengths but strongly changed accuracy on longer ones.
  • For scratchpad finetuning, the authors checked three possible causes of failure: positional encoding, distractors, and end-of-sequence prediction. Distractors turned out to be the main cause. For parity, the number of 1s measures difficulty better than the total number of bits.
  • Few-shot scratchpad prompting gave dramatic gains on longer instances. Finetuning on top of it gave mixed results that depended on how well the base model already did the task.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Mathematics & statistics

Cited by

99 papers of our library cite it (of the 140673 whose bibliographies we read); 8 of them have a page here, 91 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2207.04901 · arXiv 2207.04901

@misc{anil2022exploring,
  title = {{Exploring Length Generalization in Large Language Models}},
  author = {Anil, Cem and Wu, Yuhuai and Andreassen, Anders and Lewkowycz, Aitor and Misra, Vedant and Ramasesh, Vinay and Slone, Ambrose and Gur-Ari, Guy and Dyer, Ethan and Neyshabur, Behnam},
  year = {2022},
  doi = {10.48550/arxiv.2207.04901},
  eprint = {2207.04901},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2207.04901}
}

References

33 references, 11 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  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:1877–1901, 2020. find
  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.07206, 2022. — [arXiv:2202.07206](https://arxiv.org/abs/2202.07206) find
  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. find our card
  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. ↗ our card
  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. find our card
  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. find our card
  7. Haoyu Wang, Mo Yu, Xiaoxiao Guo, Rajarshi Das, Wenhan Xiong, and Tian Gao. Do multi-hop readers dream of reasoning chains? arXiv preprint arXiv:1910.14520, 2019. find
  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. find our card
  9. Peter Clark, Oyvind Tafjord, and Kyle Richardson. Transformers as soft reasoners over language. arXiv preprint arXiv:2002.05867, 2020. find our card
  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.02924, 2020. find
  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. find
  12. Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invariant neural networks. In International Conference on Machine Learning, pages 3744–3753. PMLR, 2019. find
  13. Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M Shieber. Lstm networks can perform dynamic counting. arXiv preprint arXiv:1906.03648, 2019. find
  14. Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understanding the failure modes of out-of-distribution generalization. arXiv preprint arXiv:2010.15775, 2020. — [arXiv:2010.15775](https://arxiv.org/abs/2010.15775) find
  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. find our card
  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. find
  17. Benjamin Newman, John Hewitt, Percy Liang, and Christopher D Manning. The eos decision and length extrapolation. arXiv preprint arXiv:2010.07174, 2020. find
  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 al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021. find our card
  19. Yann Dubois, Gautier Dagan, Dieuwke Hupkes, and Elia Bruni. Location attention for extrapolation to longer sequences. arXiv preprint arXiv:1911.03872, 2019. find
  20. Kenton Murray and David Chiang. Correcting length bias in neural machine translation. arXiv preprint arXiv:1808.10006, 2018. find
  21. Gilad Yehudai, Ethan Fetaya, Eli Meirom, 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. find
  22. Da Ju, Stephen Roller, Sainbayar Sukhbaatar, and Jason Weston. Staircase attention for recurrent processing of sequences. arXiv preprint arXiv:2106.04279, 2021. — [arXiv:2106.04279](https://arxiv.org/abs/2106.04279) find
  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://openreview.net/forum?id=R8sQPpGCv0. ↗
  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 arXiv:2206.04301, 2022. find
  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. find
  26. Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. End-to-end algorithm synthesis with recurrent networks: Logical extrapolation without overthinking. arXiv preprint arXiv:2202.05826, 2022. find
  27. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Łukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018. find
  28. Łukasz Kaiser and Ilya Sutskever. arXiv:1511.08228, 2015. Neural gpus learn algorithms. arXiv preprint find
  29. R Thomas McCoy, Robert Frank, and Tal Linzen. Does syntax need to grow on trees? sources of hierarchical inductive bias in sequence-to-sequence networks. Transactions of the Association for Computational Linguistics, 8:125–140, 2020. find our card
  30. Eugene Kharitonov and Rahma Chaabouni. What they do when in doubt: a study of inductive biases in seq2seq learners. arXiv preprint arXiv:2006.14953, 2020. — [arXiv:2006.14953](https://arxiv.org/abs/2006.14953) find
  31. He He, Sheng Zha, and Haohan Wang. Unlearn dataset bias in natural language inference by fitting the residual. arXiv preprint arXiv:1908.10763, 2019. find our card
  32. R Thomas McCoy, Ellie Pavlick, and Tal Linzen. Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference. arXiv preprint arXiv:1902.01007, 2019. find our card
  33. Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929–1958, 2014. *Figure 9: Parity problem instances: (left) A sample 8-bit parity problem… find