Elamur Research⌕
☰
home / papers / 2023 / Chain-of-Thought Reasoning is a Policy Improvement Operator

Chain-of-Thought Reasoning is a Policy Improvement Operator

Paper · 2023 · Hugh Zhang and David C. Parkes

Summary

Large language models depend on human-written data, and that supply is running out. Zhang and Parkes ask whether a model can acquire new skills from data it produces itself. They present SECToR (Self-Education via Chain-of-Thought Reasoning), a proof of concept that uses multi-digit addition as a test task. The method treats chain-of-thought reasoning as a policy improvement operator, playing the role that Monte-Carlo Tree Search plays in AlphaZero.

After a short supervised phase on small numbers, the model uses step-by-step reasoning to solve slightly longer problems it cannot yet answer directly. The next version of the model is then fine-tuned to produce those answers immediately, without the reasoning steps. Training follows a digit-by-digit curriculum.

Errors in self-generated data tend to compound across iterations, a problem the authors call "error avalanching." SECToR limits it with self-consistency checks, but no external verification is used. Starting from ByT5, the model teaches itself addition far beyond the lengths it was supervised on. This suggests a route toward self-improvement whose scaling depends on compute rather than on the amount of available data.

Key points

  • 582M ByT5 model: received supervision only on 1–6 digit sums (about 0.5M examples). It then reached 29-digit addition at 98+% accuracy through 22 rounds of self-improvement.
  • 300M ByT5 model: needed supervision up to 8 digits and roughly 4M examples before it could begin self-training. It went on to reach 24 digits, which hints that larger models need less supervised data.
  • Error avalanching: this is the reason earlier self-training attempts stalled within a few steps. SECToR's checks, including "simplify-then-guess" and commutativity-based consistency, delay this collapse, though accumulated errors still end training eventually.
  • Curriculum design: the curriculum is built into self-training, because data for N+1 digits is produced by a model that has already mastered 1 to N digits.
  • Error analysis: on 30-digit sums (never seen during training), the final model's accuracy showed little relation to the total number of carries or the longest carry streak.

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

 Institutions

🎓Harvard UniversityCambridge · United States137 works · 45,850 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,948 works

Cite

Cite as Hugh Zhang and David C. Parkes. 2023. Chain-of-Thought Reasoning is a Policy Improvement Operator. arXiv:2309.08589.

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

@misc{zhang2023chain,
  title = {{Chain-of-Thought Reasoning is a Policy Improvement Operator}},
  author = {Hugh Zhang and David C. Parkes},
  year = {2023},
  doi = {10.48550/arxiv.2309.08589},
  eprint = {2309.08589},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2309.08589}
}

References

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

  1. Reza Yazdani Aminabadi, Samyam Rajbhandari, Ammar Ahmad Awan, Cheng Li, Du Li, Elton Zheng, Olatunji Ruwase, Shaden Smith, Minjia Zhang, Jeff Rasley, and Yuxiong He. DeepSpeed-Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale. In Proceedings of the International Co… find
  2. Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Olsson, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jamie Kerr, Jared… — Constitutional AI: Harmlessness from AI Feedback
  3. Emily M. Bender and Alexander Koller. Climbing towards NLU: On Meaning, Form, and Understanding in the Age of Data. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 5185–5198, Online, July 2020. Association for Computational Linguistics. doi: 10.18653/v…
  4. Yonatan Bisk, Ari Holtzman, Jesse Thomason, Jacob Andreas, Yoshua Bengio, Joyce Chai, Mirella Lapata, Angeliki Lazaridou, Jonathan May, Aleksandr Nisnevich, Nicolas Pinto, and Joseph Turian. Experience Grounds Language. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language P…
  5. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chri… find
  6. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/file/ 1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf. ↗
  7. Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching Large Language Models to Self-Debug, April 2023. URL http://arxiv.org/abs/2304.05128. arXiv:2304.05128 [cs]. ↗
  8. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emi… — PaLM: Scaling Language Modeling with Pathways
  9. Rémi Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. In H. Jaap van den Herik, Paolo Ciancarini, and H. H. L. M. (Jeroen) Donkers (eds.), Computers and Games, Lecture Notes in Computer Science, pp. 72–83, Berlin, Heidelberg, 2007. Springer. ISBN 978-3-540-75538-8. doi… — [doi:10.1007/978-3-540-75538-8](https://doi.org/10.1007/978-3-540-75538-8) find
  10. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volum…
  11. Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and Fate: Limits of Transformers on Compositionality,…
  12. Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective, June 2023. URL http://arxiv.org/abs/2305.15408. arXiv:2305.15408 [cs, stat]. ↗
  13. Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with Language Model is Planning with World Model, May 2023. URL http://arxiv.org/abs/2305.14992. arXiv:2305.14992 [cs]. ↗
  14. 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. NeurIPS, 2021.
  15. Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, E… — Training Compute-Optimal Large Language Models
  16. Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large Language Models Can Self-Improve, October 2022. URL http://arxiv.org/ abs/2210.11610. arXiv:2210.11610 [cs]. ↗
  17. Samy Jelassi, Stéphane d’Ascoli, Carles Domingo-Enrich, Yuhuai Wu, Yuanzhi Li, and François Charton. Length Generalization in Arithmetic Transformers, June 2023. URL http://arxiv.org/abs/2306.15400. arXiv:2306.15400 [cs]. ↗
  18. Jaehun Jung, Peter West, Liwei Jiang, Faeze Brahman, Ximing Lu, Jillian Fisher, Taylor Sorensen, and Yejin Choi. Impossible Distillation: from Low-Quality Model to High-Quality Dataset & Model for Summarization and Paraphrasing, May 2023. URL http://arxiv.org/abs/ 2305.16635. arXiv:2305.16635 [cs]. ↗
  19. Daniel Kahneman. Thinking, Fast and Slow. Thinking, Fast and Slow. Farrar, Straus and Giroux, New York, NY, US, 2011. ISBN 978-0-374-27563-1 978-1-4299-6935-2. Pages: 499. find
  20. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling Laws for Neural Language Models, January 2020. URL http://arxiv.org/abs/2001.08361. arXiv:2001.08361 [cs, stat]. ↗
  21. Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International conference on learning representations (ICLR), San Diego, CA, USA, 2015. tex.optmonth: 12.
  22. Nayoung Lee, Kartik Sreenivasan, Jason D. Lee, Kangwook Lee, and Dimitris Papailiopoulos. Teaching Arithmetic to Small Transformers, July 2023. URL http://arxiv.org/abs/ 2307.03381. arXiv:2307.03381 [cs]. ↗
  23. Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving Quantitative Reasoning Problems with Language Models, June 2022. URL http://a…
  24. Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s Verify Step by Step, May 2023. URL http://arxiv.org/abs/2305.20050. arXiv:2305.20050 [cs]. ↗
  25. Bill Yuchen Lin, Yicheng Fu, Karina Yang, Prithviraj Ammanabrolu, Faeze Brahman, Shiyu Huang, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. SwiftSage: A Generative Agent with Fast and Slow Thinking for Complex Interactive Tasks, May 2023. URL http://arxiv.org/abs/ 2305.17390. arXiv:2305.17390 [cs]… ↗
  26. Tiedong Liu and Bryan Kian Hsiang Low. Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Tasks, May 2023. URL http://arxiv.org/abs/2305.14201. arXiv:2305.14201 [cs]. ↗
  27. Gary Marcus. Deep Learning: A Critical Appraisal, January 2018. URL http://arxiv.org/ abs/1801.00631. arXiv:1801.00631 [cs, stat]. ↗
  28. Michael McCloskey and Neal J. Cohen. Catastrophic Interference in Connectionist Networks: The Sequential Learning Problem. In Gordon H. Bower (ed.), Psychology of Learning and Motivation, volume 24, pp. 109–165. Academic Press, January 1989. doi: 10. 1016/S0079-7421(08)60536-8. URL https://www.scien… ↗
  29. Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show Your Work: Scratchpads for Intermediate Computation with Language Models, November 2021. URL http://arx…
  30. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language Models are Unsupervised Multitask Learners. pp. 24, 2019. find
  31. Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering Atari, Go, Chess, and Shogi by Planning with a Learned Model. Nature, 588(7839):604–609,… find
  32. Noah Shinn, Federico Cassano, Beck Labash, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language Agents with Verbal Reinforcement Learning, June 2023. URL http://arxiv.org/abs/2303.11366. arXiv:2303.11366 [cs]. ↗
  33. Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Yarin Gal, Nicolas Papernot, and Ross Anderson. The Curse of Recursion: Training on Generated Data Makes Models Forget, May 2023. URL http://arxiv.org/abs/2305.17493. arXiv:2305.17493 [cs]. ↗
  34. David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukc… find
  35. David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, and others. Mastering the Game of Go Without Human Knowledge. Nature, 550(7676):354–359, 2017. Publisher: Nature Publishing Group. find
  36. Ronen Tamari, Chen Shani, Tom Hope, Miriam R L Petruck, Omri Abend, and Dafna Shahaf. Language (Re)modelling: Towards Embodied Language Understanding. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 6268–6281, Online, July 2020. Association for Computa… find
  37. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller,… — Llama 2: Open Foundation and Fine-Tuned Chat Models
  38. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need, August 2023. URL http://arxiv.org/abs/1706.03762. arXiv:1706.03762 [cs]. ↗
  39. Pablo Villalobos, Jaime Sevilla, Lennart Heim, Tamay Besiroglu, Marius Hobbhahn, and Anson Ho. Will We Run Out of Data? An Analysis of the Limits of Scaling Datasets in Machine Learning, October 2022. URL https://arxiv.org/abs/2211.04325v1. ↗
  40. Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An Open-Ended Embodied Agent with Large Language Models, May 2023a. URL http://arxiv.org/abs/2305.16291. arXiv:2305.16291 [cs]. ↗
  41. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-Consistency Improves Chain of Thought Reasoning in Language Models, March 2023b. URL http://arxiv.org/abs/2203.11171. arXiv:2203.11171 [cs]. ↗
  42. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. arXiv, 2022. doi: 10.48550/arXiv.2201.11903. URL http://arxiv.org/abs/2201. 11903. arXiv:2201.11903 [cs]. ↗
  43. Yiran Wu, Feiran Jia, Shaokun Zhang, Hangyu Li, Erkang Zhu, Yue Wang, Yin Tat Lee, Richard Peng, Qingyun Wu, and Chi Wang. An Empirical Study on Challenging Math Problem Solving with GPT-4, June 2023. URL http://arxiv.org/abs/2306.01337. arXiv:2306.01337 [cs, stat]. ↗
  44. Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. ByT5: Towards a token-free future with pre-trained byte-to-byte models, March 2022. URL http://arxiv.org/abs/2105.13626. arXiv:2105.13626 [cs]. ↗
  45. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of Thoughts: Deliberate Problem Solving with Large Language Models, May 2023. URL http://arxiv.org/abs/2305.10601. arXiv:2305.10601 [cs]. ↗
  46. Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman. STaR: Bootstrapping Reasoning With Reasoning, May 2022. URL http://arxiv.org/abs/2203.14465. arXiv:2203.14465 [cs]. ↗
  47. Mengxue Zhang, Zichao Wang, Zhichao Yang, Weiqi Feng, and Andrew Lan. Interpretable Math Word Problem Solution Generation Via Step-by-step Planning, June 2023a. URL http://arxiv.org/abs/2306.00784. arXiv:2306.00784 [cs]. ↗
  48. Muru Zhang, Ofir Press, William Merrill, Alisa Liu, and Noah A. Smith. How Language Model Hallucinations Can Snowball, May 2023b. URL http://arxiv.org/abs/2305.13534. arXiv:2305.13534 [cs]. ↗
  49. Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, and Ed Chi. Least-to-Most Prompting Enables Complex Reasoning in Large Language Models, April 2023. URL http://arxiv.org/ abs/2205.10625. arXiv:2205.10625 [cs]. ↗
  50. Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi. Teaching Algorithmic Reasoning via In-context Learning, November 2022. URL http://arxiv.org/abs/2211.09066. arXiv:2211.09066 [cs]. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2023-chain-thought-reasoning-policy-improvement/