Elamur Research⌕
☰
home / papers / 2023 / Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding

Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding

Paper · 2023 · Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru et al.

Summary

Language models aligned with PPO are usually deployed using only the policy network. The value network that PPO trains alongside it is typically thrown away. The authors argue that this byproduct is well suited to scoring candidates during guided decoding. It is trained to estimate the expected return of unfinished sequences, and it is tied to that specific policy.

They propose PPO-MCTS, which runs Monte-Carlo Tree Search before emitting each token. The PPO policy supplies prior probabilities over candidate tokens, and the value model rates partial continuations. A key change to standard MCTS is to initialize the Q of child actions from the parent node's V, which promotes exploration. The authors also describe approximations for setups where exact computation is not feasible.

Across four tasks, PPO-MCTS output was judged more preferable than sampling from the PPO policy alone. The tasks were sentiment steering, toxicity reduction, knowledge introspection, and helpful/harmless dialogue. The method also outperformed longer PPO training and best-of-n decoding. The authors conclude that practitioners should keep value checkpoints, while noting that the search adds significant inference cost.

Key points

  • Sentiment steering (OpenWebText): success rate rose by 30 points absolute over direct sampling from the same PPO policy. Fluency, diversity and topicality were preserved, and human raters preferred PPO-MCTS by a 20-point margin.
  • Toxicity reduction (RealToxicityPrompts): toxicity fell by 34% relative, with a 30% relative human preference margin.
  • Other tasks:
    • Knowledge introspection: generated commonsense knowledge was 12% (relative) more useful for downstream QA benchmarks.
    • HH-RLHF chatbot: human-evaluated win rate rose by 5 points absolute.
  • Search settings: the number of simulations per token (S) and the branching factor (k) were tested at 10, 20 and 50, with S = k = 50 chosen. Larger values improved goal satisfaction and diversity but slightly hurt fluency.
  • Cost and scope:
    • A naive estimate puts PPO-MCTS about 2S times slower than plain decoding; reusing the subtree under the chosen token partly offsets this.
    • Methods without a value model (DPO, Quark, SLiC) cannot directly use this approach.

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

🎓University of WashingtonSeattle · United States353 works · 200,043 citations🔬Allen Institute for Artificial IntelligenceSeattle · United States275 works · 97,634 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

Cite

Cite as Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi and Asli Celikyilmaz. 2023. Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding. arXiv:2309.15028.

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

@misc{liu2023don,
  title = {{Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding}},
  author = {Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi and Asli Celikyilmaz},
  year = {2023},
  doi = {10.48550/arxiv.2309.15028},
  eprint = {2309.15028},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2309.15028}
}

References

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

  1. Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, T. J. Henighan, Nicholas Joseph, Saurav Kadavath, John Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Hatfield-Dodds, Danny Hernandez, Tristan Hume, Scott Johnston, Sha… find
  2. Yonatan Bisk, Rowan Zellers, Ronan LeBras, Jianfeng Gao, and Yejin Choi. PIQA: reasoning about physical commonsense in natural language. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2…
  3. AAAI Press, 2020. URL https://aaai.org/ojs/index.php/AAAI/article/view/6239. ↗
  4. Antoine Chaffin, V. Claveau, and Ewa Kijak. Ppl-mcts: Constrained textual generation through discriminator-guided mcts decoding. In North American Chapter of the Association for Computational Linguistics, 2021. URL https://api.semanticscholar.org/CorpusID: 248512793. ↗
  5. Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. Plug and play language models: A simple approach to controlled text generation. ArXiv, abs/1912.02164, 2019. URL https://api.semanticscholar.org/ CorpusID:208617790. ↗
  6. Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A. Smith. Realtoxicityprompts: Evaluating neural toxic degeneration in language models. In Findings, 2020. URL https://api.semanticscholar.org/CorpusID:221878771. ↗
  7. Aaron Gokaslan and Vanya Cohen. Openwebtext corpus. http://Skylion007.github.io/ OpenWebTextCorpus, 2019. ↗
  8. Jean-Bastien Grill, Florent Altch’e, Yunhao Tang, Thomas Hubert, Michal Valko, Ioannis Antonoglou, and Rémi Munos. Monte-carlo tree search as regularized policy optimization. In International Conference on Machine Learning, 2020. URL https://api.semanticscholar.org/CorpusID:220769401. ↗
  9. Sylvain Gugger, Lysandre Debut, Thomas Wolf, Philipp Schmid, Zachary Mueller, and Sourab Mangrulkar. Accelerate: Training and inference at scale made simple, efficient and adaptable. https://github.com/huggingface/accelerate, 2022. ↗
  10. Shibo Hao, Yilan Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. ArXiv, abs/2305.14992, 2023. URL https://api.semanticscholar.org/CorpusID:258865812. ↗
  11. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. ArXiv, abs/1904.09751, 2019. URL https://api.semanticscholar.org/CorpusID:127986954. ↗
  12. Muhammad Khalifa, Lajanugen Logeswaran, Moontae Lee, Ho Hin Lee, and Lu Wang. Discriminator-guided multi-step reasoning with language models. ArXiv, abs/2305.14934, 2023. URL https://api.semanticscholar.org/CorpusID:258865395. — [arXiv:2305.14934](https://arxiv.org/abs/2305.14934) ↗
  13. Daniel Khashabi, Sewon Min, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Hannaneh Hajishirzi. UNIFIEDQA: Crossing format boundaries with a single QA system. In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 1896–1907, Online, 2020. Association for Compu…
  14. Tushar Khot, Peter Clark, Michal Guerquin, Peter Jansen, and Ashish Sabharwal. QASC: A dataset for question answering via sentence composition. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference,… find
  15. AAAI Press, 2020. URL https://aaai.org/ojs/index.php/AAAI/article/view/6319. ↗
  16. Levente Kocsis and Csaba Szepesvari. Bandit based monte-carlo planning. In European Conference on Machine Learning, 2006. URL https://api.semanticscholar.org/CorpusID: 15184765. ↗
  17. Ben Krause, Akhilesh Deepak Gotmare, Bryan McCann, Nitish Shirish Keskar, Shafiq R. Joty, Richard Socher, and Nazneen Rajani. Gedi: Generative discriminator guided sequence generation. In Conference on Empirical Methods in Natural Language Processing, 2020. URL https://api.semanticscholar.org/Corpus… ↗
  18. Kalpesh Krishna, Yapei Chang, John Wieting, and Mohit Iyyer. Rankgen: Improving text generation with large ranking models. ArXiv, abs/2205.09726, 2022. URL https://api.semanticscholar.org/CorpusID:248887396. ↗
  19. Rémi Leblond, Jean-Baptiste Alayrac, L. Sifre, Miruna Pislar, Jean-Baptiste Lespiau, Ioannis Antonoglou, Karen Simonyan, and Oriol Vinyals. Machine translation decoding beyond beam search. In Conference on Empirical Methods in Natural Language Processing, 2021. URL https://api.semanticscholar.org/Co… ↗
  20. Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, B. Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Annual Meeting of the Association for Computational Linguistics, 2022. URL https://api.semanticscholar.org/ CorpusID:259370847. ↗
  21. Hunter Lightman, Vineet Kosaraju, Yura Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. ArXiv, abs/2305.20050, 2023. URL https://api.semanticscholar.org/ CorpusID:258987659. ↗
  22. Jiacheng Liu, Alisa Liu, Ximing Lu, Sean Welleck, Peter West, Ronan Le Bras, Yejin Choi, and Hannaneh Hajishirzi. Generated knowledge prompting for commonsense reasoning. In Annual Meeting of the Association for Computational Linguistics, 2021. URL https://api. semanticscholar.org/CorpusID:239016123… find
  23. Jiacheng Liu, Skyler Hallinan, Ximing Lu, Pengfei He, Sean Welleck, Hannaneh Hajishirzi, and Yejin Choi. Rainier: Reinforced knowledge introspector for commonsense question answering. ArXiv, abs/2210.03078, 2022. URL https://api.semanticscholar.org/ CorpusID:252735191. ↗
  24. Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Neurologic decoding: (un)supervised neural text generation with predicate logic constraints. ArXiv, abs/2010.12884, 2020. URL https://api.semanticscholar.org/ CorpusID:225067055. ↗
  25. Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. Neurologic a*esque decoding: Constrained text generation with lookahead heuristics. In North American Chapter of the Association for…
  26. Ximing Lu, Sean Welleck, Liwei Jiang, Jack Hessel, Lianhui Qin, Peter West, Prithviraj Ammanabrolu, and Yejin Choi. Quark: Controllable text generation with reinforced unlearning. ArXiv, abs/2205.13636, 2022. URL https://api.semanticscholar.org/ CorpusID:249152301. ↗
  27. OpenAI. Introducing chatgpt, November 2022. chatgpt. find
  28. URL — GPT-4 Technical Report https://openai.com/blog/OpenAI. Gpt-4 technical report. Technical report, OpenAI, 2023. URL https://cdn.openai. com/papers/gpt-4.pdf. ↗
  29. Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Low… — Training language models to follow instructions with human feedback
  30. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soum… — PyTorch: An Imperative Style, High-Performance Deep Learning Library
  31. Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. 1994. URL https://api.semanticscholar.org/CorpusID:122678161. ↗
  32. Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019. URL https://api.semanticscholar.org/CorpusID:160025533. ↗
  33. Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. ArXiv, abs/2305.18290, 2023. URL https://api.semanticscholar.org/ CorpusID:258959321. ↗
  34. Colin Raffel, Noam M. 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, abs/1910.10683, 2019. URL https://api.semanticscholar.org/CorpusID:204838007. ↗
  35. Christopher D. Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61:203–230, 2011. URL https://api.semanticscholar.org/ CorpusID:207081359. ↗
  36. Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020… find
  37. AAAI Press, 2020. URL https://aaai.org/ojs/index.php/AAAI/article/view/6399. ↗
  38. Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi. Social IQa: Commonsense reasoning about social interactions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EM… find
  39. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abs/1707.06347, 2017. URL https://api.semanticscholar.org/CorpusID:28695052. ↗
  40. David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, L. Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavu… find
  41. David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, L. Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without… find
  42. Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQA: A question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume…
  43. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models. ArXiv, abs/230…
  44. Hugo Touvron, Louis Martin, Kevin R. Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Daniel M. Bikel, Lukas Blecher, Cristian Cantón Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Bria… — Llama 2: Open Foundation and Fine-Tuned Chat Models
  45. Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, L. Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process- and outcome-based feedback. ArXiv, abs/2211.14275, 2022. URL https://api.semanticscholar.org/CorpusID:254017497. ↗
  46. Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models. ArXiv, abs/2205.12910, 2022. URL https://api.semanticscholar.org/CorpusID:249063060. ↗
  47. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface’s transformers: State-of-the-art natural language processing. ArXiv preprint, abs/1910.03771, 2019. URL https://arxiv.org/abs/… ↗
  48. Zeqiu Wu, Yushi Hu, Weijia Shi, Nouha Dziri, Alane Suhr, Prithviraj Ammanabrolu, Noah A. Smith, Mari Ostendorf, and Hanna Hajishirzi. Fine-grained human feedback gives better rewards for language model training. ArXiv, abs/2306.01693, 2023. URL https://api.semanticscholar.org/CorpusID:259064099. ↗
  49. Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, MingSung Kan, Junxian He, and Qizhe Xie. Decomposition enhances reasoning via self-evaluation guided decoding. ArXiv, abs/2305.00633, 2023. URL https://api.semanticscholar.org/CorpusID:258426922. ↗
  50. 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. ArXiv, abs/2305.10601, 2023. URL https://api.semanticscholar.org/ CorpusID:258762525. ↗
  51. Yao Zhao, Rishabh Joshi, Tianqi Liu, Misha Khalman, Mohammad Saleh, and Peter J. Liu. Slic-hf: Sequence likelihood calibration with human feedback. ArXiv, abs/2305.10425, 2023a. URL https://api.semanticscholar.org/CorpusID:258741082. ↗
  52. Zirui Neil Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense knowledge for large-scale task planning. ArXiv, abs/2305.14078, 2023b. URL https://api.semanticscholar.org/CorpusID:258841057. ↗
  53. Daniel M. Ziegler, Nisan Stiennon, Jeff Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. ArXiv, abs/1909.08593, 2019. URL https://api.semanticscholar.org/ CorpusID:202660943. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/liu-2023-don-t-throw-away-value/