Elamur Research⌕
☰
home / papers / 2022 / What Can Transformers Learn In-Context? A Case Study of Simple Function Classes

What Can Transformers Learn In-Context? A Case Study of Simple Function Classes

Paper · 2022 · Shivam Garg, Dimitris Tsipras, Percy Liang et al.

Summary

GPT-3 and similar models can solve tasks from examples in a prompt, but it is unclear whether they learn new tasks this way or only recall tasks from pretraining. Garg et al. turn this into a controlled question. Given input–output pairs from a randomly drawn function of a known class, plus a query point, can a model be trained to predict the function's value at that query? They train a GPT-2-style Transformer from scratch on synthetic prompts with no natural text, drawing a fresh function for every prompt. A curriculum starts from easy functions and gradually increases difficulty. For 20-dimensional linear functions, the model's error matches the optimal least squares estimator. It stays robust under distribution shifts, such as noisy outputs or a query drawn from a different region than the examples. Similar success holds for sparse linear functions, small ReLU networks and decision trees. The study shows that standard Transformers can carry out nontrivial learning algorithms in a single forward pass. This gives a clean testbed for studying in-context learning.

Key points

  • Model and training: decoder-only Transformer from the GPT-2 family with 12 layers, 8 heads and a 256-dim embedding (about 9.5M parameters). It is trained with squared loss, batch size 64, for 500k steps.
  • Linear functions: inputs and weights come from an isotropic Gaussian in d = 20. The model's performance is on par with least squares on unseen functions.
  • Harder function classes:
    • On 3-sparse linear functions, the model beats least squares and rivals Lasso.
    • On two-layer ReLU nets with 100 hidden units, it rivals the same architecture trained by gradient descent.
    • On depth-4 decision trees, it learns from about 100 examples and outperforms greedy and boosting baselines.
  • Curriculum and capacity: the curriculum speeds up training dramatically. Larger models handle higher dimensions and distribution shifts better.
  • Resources: code and models are released at github.com/dtsip/in-context-learning.

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, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

Cite

Cite as Shivam Garg, Dimitris Tsipras, Percy Liang and Gregory Valiant. 2022. What Can Transformers Learn In-Context? A Case Study of Simple Function Classes. arXiv:2208.01066.

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

@misc{garg2022what,
  title = {{What Can Transformers Learn In-Context? A Case Study of Simple Function Classes}},
  author = {Shivam Garg, Dimitris Tsipras, Percy Liang and Gregory Valiant},
  year = {2022},
  doi = {10.48550/arxiv.2208.01066},
  eprint = {2208.01066},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2208.01066}
}

References

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

  1. Maria-Florina Balcan. Data-driven algorithm design. In Tim Roughgarden, editor, Beyond Worst Case Analysis of Algorithms. Cambridge University Press, 2020. find
  2. Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. Proceedings of the National Academy of Sciences, 2019. find
  3. Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016. find
  4. Samy Bengio, Yoshua Bengio, Jocelyn Cloutier, and Jan Gecsei. On the optimization of a synaptic learning rule. In Preprints Conf. Optimality in Artificial and Biological Neural Networks, 1995. find
  5. Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In International Conference on Machine Learning (ICML), pages 41–48, 2009.
  6. Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. arXiv preprint arXiv:2009.11264, 2020a.
  7. Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006.09286, 2020b. find
  8. Sid Black, Stella Biderman, Eric Hallahan, Quentin Anthony, Leo Gao, Laurence Golding, Horace He, Connor Leahy, Kyle McDonell, Jason Phang, et al. Gpt-neox-20b: An open-source autoregressive language model. arXiv preprint arXiv:2204.06745, 2022.
  9. Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan. Decision tree heuristics can fail, even in the smoothed setting. arXiv preprint arXiv:2107.00819, 2021. — [arXiv:2107.00819](https://arxiv.org/abs/2107.00819) find
  10. 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. Neural Information Processing Systems (NeurIPS), 2020.
  11. Alon Brutzkus, Amit Daniely, and Eran Malach. Id3 learns juntas for smoothed product distributions. In Conference on Learning Theory, pages 902–915. PMLR, 2020. find
  12. Stephanie CY Chan, Adam Santoro, Andrew K Lampinen, Jane X Wang, Aaditya Singh, Pierre H Richemond, Jay McClelland, and Felix Hill. Data distributional properties drive emergent few-shot learning in transformers. arXiv preprint arXiv:2205.05055, 2022. find
  13. Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In conference on knowledge discovery and data mining (KDD), 2016. find
  14. Yanda Chen, Ruiqi Zhong, Sheng Zha, George Karypis, and He He. Meta-learning via language model in-context tuning. arXiv preprint arXiv:2110.07814, 2021. find
  15. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Łukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018. find
  16. Tuan Dinh, Yuchen Zeng, Ruisu Zhang, Ziqian Lin, Shashank Rajput, Michael Gira, Jy-yong Sohn, Dimitris Papailiopoulos, and Kangwook Lee. Lift: Language-interfaced fine-tuning for non-language machine learning tasks. arXiv preprint arXiv:2206.06565, 2022. — [arXiv:2206.06565](https://arxiv.org/abs/2206.06565) find
  17. Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
  18. Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning (ICML), 2022. find
  19. Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Ja… find
  20. Jeffrey L Elman. Learning and development in neural networks: The importance of starting small. Cognition, 1993. find
  21. Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning (ICML), 2017.
  22. Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, 2001. find
  23. Marta Garnelo, Dan Rosenbaum, Christopher Maddison, Tiago Ramalho, David Saxton, Murray Shanahan, Yee Whye Teh, Danilo Rezende, and SM Ali Eslami. Conditional neural processes. In International Conference on Machine Learning, pages 1704–1713. PMLR, 2018a. find
  24. Marta Garnelo, Jonathan Schwarz, Dan Rosenbaum, Fabio Viola, Danilo J Rezende, SM Eslami, and Yee Whye Teh. Neural processes. arXiv preprint arXiv:1807.01622, 2018b. — [arXiv:1807.01622](https://arxiv.org/abs/1807.01622) find
  25. Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 2020. find
  26. Sepp Hochreiter, A Steven Younger, and Peter R Conwell. Learning to learn using gradient descent. In International conference on artificial neural networks (ICANN), 2001. find
  27. Eric Horvitz, Yongshao Ruan, Carla Gomes, Henry Kautz, Bart Selman, and Max Chickering. A bayesian approach to tackling hard computational problems (preliminary report). Electronic Notes in Discrete Mathematics, 2001. find
  28. Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey. arXiv preprint arXiv:2004.05439, 2020. find
  29. Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Neural Information Processing Systems (NeurIPS), 2017. find
  30. Hyunjik Kim, Andriy Mnih, Jonathan Schwarz, Marta Garnelo, Ali Eslami, Dan Rosenbaum, Oriol Vinyals, and Yee Whye Teh. Attentive neural processes. arXiv preprint arXiv:1901.05761, 2019. find
  31. Diederik P Kingma and Jimmy Ba. arXiv:1412.6980, 2014.
  32. Adam: A method for stochastic optimization. Louis Kirsch and Jürgen Schmidhuber. Meta learning backpropagation and improving it. Neural Information Processing Systems (NeurIPS), 2021. find
  33. Andrew K Lampinen, Ishita Dasgupta, Stephanie CY Chan, Kory Matthewson, Michael Henry Tessler, Antonia Creswell, James L McClelland, Jane X Wang, and Felix Hill. Can language models learn from explanations in context? arXiv preprint arXiv:2204.02329, 2022.
  34. Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint arXiv:1606.01885, 2016. — [arXiv:1606.01885](https://arxiv.org/abs/1606.01885) find
  35. Opher Lieber, Or Sharir, Barak Lenz, and Yoav Shoham. Jurassic-1: Technical details and evaluation. White Paper. AI21 Labs, 2021. find
  36. Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good in-context examples for gpt-3? arXiv preprint arXiv:2101.06804, 2021.
  37. Kevin Lu, Aditya Grover, Pieter Abbeel, and Igor Mordatch. Pretrained transformers as universal computation engines. arXiv preprint arXiv:2103.05247, 2021a. — [arXiv:2103.05247](https://arxiv.org/abs/2103.05247) find
  38. Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.08786, 2021b.
  39. Sewon Min, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Noisy channel language model prompting for few-shot text classification. arXiv preprint arXiv:2108.04106, 2021a.
  40. Sewon Min, Mike Lewis, Luke Zettlemoyer, and Hannaneh Hajishirzi. Metaicl: Learning to learn in context. arXiv preprint arXiv:2110.15943, 2021b. find
  41. Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202.12837, 2022.
  42. Nikhil Mishra, Mostafa Rohaninejad, Xi Chen, and Pieter Abbeel. A simple neural attentive meta-learner. In International Conference on Learning Representations (ICLR), 2018. find
  43. Swaroop Mishra, Daniel Khashabi, Chitta Baral, Yejin Choi, and Hannaneh Hajishirzi. Reframing instructional prompts to gptk’s language. arXiv preprint arXiv:2109.07830, 2021.
  44. Samuel Müller, Noah Hollmann, Sebastian Pineda Arango, Josif Grabocka, and Frank Hutter. Transformers can do bayesian inference. arXiv preprint arXiv:2112.10510, 2021. — [arXiv:2112.10510](https://arxiv.org/abs/2112.10510) find
  45. Devang K Naik and Richard J Mammone. Meta-neural networks that learn by learning. In International Joint Conference on Neural Networks (IJCNN), 1992. find
  46. Preetum Nakkiran. More data can hurt for linear regression: Sample-wise double descent. arXiv preprint arXiv:1912.07242, 2019. — [arXiv:1912.07242](https://arxiv.org/abs/1912.07242) find
  47. Tung Nguyen and Aditya Grover. Transformer neural processes: Uncertainty-aware meta learning via sequence modeling. arXiv preprint arXiv:2207.04179, 2022. — [arXiv:2207.04179](https://arxiv.org/abs/2207.04179) find
  48. Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amode… find
  49. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2011. find
  50. Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. arXiv preprint arXiv:1901.03429, 2019. find
  51. Lovre Pesut. Who models the models that model models? an exploration of gpt-3’s in-context model fitting ability, 2022. URL https://www.alignmentforum.org/posts/c2RzFadrxkzyRAFXa/who-models-the-models-that-model-models-an-exploration-of. ↗
  52. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. OpenAI blog, 2018. find
  53. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 2019. find
  54. Jack W Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, et al. Scaling language models: Methods, analysis & insights from training gopher. arXiv preprint arXiv:2112.11446, 2021. find
  55. Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. International Conference for Learning Representations (ICLR), 2017. find
  56. 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
  57. Frieda Rong. Extrapolating to unnatural language processing with gpt-3’s in-context learning: The good, the bad, and the mysterious), 2021. URL http://ai.stanford.edu/blog/in-context-learning/. ↗
  58. Ohad Rubin, Jonathan Herzig, and Jonathan Berant. Learning to retrieve prompts for in-context learning. arXiv preprint arXiv:2112.08633, 2021.
  59. Terence D Sanger. Neural network learning control of robot manipulators using gradually increasing task difficulty. IEEE transactions on Robotics and Automation, 1994. find
  60. Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap. Meta-learning with memory-augmented neural networks. In International conference on machine learning (ICML), 2016. find
  61. Jürgen Schmidhuber. Evolutionary principles in self-referential learning, or on learning how to learn: the meta-meta-... hook. PhD thesis, Technische Universität München, 1987. find
  62. 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. Neural Information Processing Systems (NeurIPS), 2021. find
  63. Daniel Selsam, Matthew Lamm, B Benedikt, Percy Liang, Leonardo de Moura, David L Dill, et al. Learning a sat solver from single-bit supervision. In International Conference on Learning Representations (ICLR), 2018.
  64. Charlie Snell, Ruiqi Zhong, Dan Klein, and Jacob Steinhardt. Approximating how single head attention learns. arXiv preprint arXiv:2103.07601, 2021. find
  65. Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Neural Information Processing Systems (NeurIPS), 2017. find
  66. Sebastian Thrun and Lorien Pratt. Learning to learn. Springer Science & Business Media, 2012. find
  67. Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 1996. find
  68. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Neural Information Processing Systems (NeurIPS), 2017.
  69. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Neural Information Processing Systems (NeurIPS), 2015. find
  70. Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Conference on Machine Learning, 2021. find
  71. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoe… — Transformers: State-of-the-Art Natural Language Processing
  72. Xiaoxia Wu, Ethan Dyer, and Behnam Neyshabur. When do curricula work? arXiv preprint arXiv:2012.03107, 2020. find
  73. Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations (ICLR), 2022.
  74. Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Satzilla: portfolio-based algorithm selection for sat. Journal of artificial intelligence research, 2008. find
  75. Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. arXiv preprint arXiv:2105.11115, 2021. find
  76. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? arXiv preprint arXiv:1912.10077, 2019.
  77. 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
  78. Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models. In International Conference on Machine Learning (ICML), 2021.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/garg-2022-transformers-learn-context-case-study/