Elamur Research⌕
☰
home / papers / 2024 / VinePPO: Refining Credit Assignment in RL Training of LLMs

VinePPO: Refining Credit Assignment in RL Training of LLMs

Paper · 2024 · Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance et al.

Summary

When large language models are trained with reinforcement learning on multi-step reasoning, the reward arrives only at the end. That makes it hard to tell which intermediate steps actually helped, a challenge known as credit assignment. PPO addresses this with a learned value network (critic), yet critic-free methods such as GRPO, RLOO and DPO perform comparably. The authors examine PPO's critic on math reasoning and find that its value estimates are biased and that it ranks candidate next steps barely better than chance.

They propose VinePPO, which keeps the PPO framework but removes the critic. A text environment can return to any partial solution by re-feeding the prefix, so VinePPO samples extra completions from each intermediate step and averages their rewards to get unbiased Monte Carlo value estimates. On MATH and GSM8K, VinePPO outperforms PPO and critic-free baselines and reaches their peak accuracy in less wall-clock time. It also achieves higher test accuracy at the same training accuracy, which matters because hard, verifiable reasoning tasks are scarce.

Key points

  • Experimental setup: experiments use the MATH and GSM8K datasets with models including DeepSeekMath 7B (the largest tested) and RhoMath 1.1B. Code is released at github.com/McGill-NLP/VinePPO, and the paper appeared at ICML 2025.
  • Speed: VinePPO is slower per iteration because of the extra sampling. It still matches the baselines' best results with fewer gradient steps and up to 3.0x less wall-clock time.
  • Diagnostic method: to build a "ground truth" value for each reasoning step, the authors averaged returns over 256 Monte Carlo samples.
  • Estimation accuracy: a prediction counted as correct if it fell within 0.05 of the ground truth. By this measure, PPO's critic gradually rises to about 65% accuracy, while VinePPO stays at 70–90% throughout training. On DeepSeekMath 7B / MATH, the reported MAE is roughly 0.03 for VinePPO versus 0.11 for PPO.
  • Error patterns: PPO's value error grows in later reasoning steps, which the authors attribute to the critic relying on memorization of early, familiar steps. VinePPO's error shrinks as the solution context lengthens. VinePPO also identifies the best next step reliably, whereas PPO's critic stays near chance for most of training.

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

🎓Université de MontréalMontreal · Canada87 works · 91,597 citations🎓McGill UniversityMontreal · Canada91 works · 11,178 citations🔬Canadian Institute for Advanced ResearchToronto · Canada35 works · 19,316 citations🎓HEC MontréalMontreal · Canada7 works · 9,970 citations

 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

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,894 worksReasoning · 1,685 works

Cite

Cite as Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville and Nicolas Le Roux. 2024. VinePPO: Refining Credit Assignment in RL Training of LLMs. arXiv:2410.01679.

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

@misc{kazemnejad2024vineppo,
  title = {{VinePPO: Refining Credit Assignment in RL Training of LLMs}},
  author = {Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville and Nicolas {Le Roux}},
  year = {2024},
  doi = {10.48550/arxiv.2410.01679},
  eprint = {2410.01679},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2410.01679}
}

References

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

  1. Ahmadian, A., Cremer, C., Gallé, M., Fadaee, M., Kreutzer, J., Pietquin, O., Üstün, A., and Hooker, S. Back to Basics: Revisiting REINFORCE-style Optimization for Learning from Human Feedback in LLMs. In Ku, L., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the A… find
  2. DeepSeek-AI, Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning, 2025. URL https://arxiv.org/abs/2501.12948. ↗
  3. Greensmith, E., Bartlett, P. L., and Baxter, J. Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning. In Dietterich, T. G., Becker, S., and Ghahramani, Z. (eds.), Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthe… find
  4. Anthony, T., Tian, Z., and Barber, D. Thinking Fast and Slow with Deep Learning and Tree Search. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Ha… find
  5. Problems with Language Models. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, 2022. URL http://papers.nips.cc… ↗
  6. Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Measuring Mathematical Problem Solving With the MATH Dataset. In Vanschoren, J. and Yeung, S. (eds.), Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, Neu…
  7. Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let’s Verify Step by Step. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, 2024. OpenReview.net. URL https://openreview.net/… ↗
  8. Lin, Z., Gou, Z., Gong, Y., Liu, X., Shen, Y., Xu, R., Lin, C., Yang, Y., Jiao, J., Duan, N., and Chen, W. Rho-1: Not All Tokens Are What You Need. CoRR, abs/2404.07965, 2024. doi: 10.48550/ARXIV.2404.07965. URL https://doi.org/10.48550/arXiv.2404.07965. ↗
  9. Huang, S., Noukhovitch, M., Hosseini, A., Rasul, K., Wang, W., and Tunstall, L. The N+ Implementation Details of RLHF with PPO: A Case Study on TL;DR Summarization. CoRR, abs/2403.17031, 2024. doi: 10.48550/ARXIV.2403.17031. URL https://doi.org/10.48550/arXiv.2403.17031. ↗
  10. Luo, L., Liu, Y., Liu, R., Phatale, S., Lara, H., Li, Y., Shu, L., Zhu, Y., Meng, L., Sun, J., and Rastogi, A. Improve Mathematical Reasoning in Language Models by Automated Process Supervision. CoRR, abs/2406.06592, 2024. doi: 10.48550/ARXIV.2406.06592. URL https://doi.org/10.48550/arXiv.2406.0659… ↗
  11. Hwang, H., Kim, D., Kim, S., Ye, S., and Seo, M. Self-explore to Avoid the Pit: Improving the Reasoning Capabilities of Language Models with Fine-grained Rewards. CoRR, abs/2404.10346, 2024. doi: 10.48550/ARXIV.2404.10346. URL https://doi.org/10.48550/arXiv.2404.10346. — [doi:10.48550/arxiv.2404.10346](https://doi.org/10.48550/arxiv.2404.10346) ↗
  12. Ma, Q., Zhou, H., Liu, T., Yuan, J., Liu, P., You, Y., and Yang, H. Let’s reward step by step: Step-level reward model as the Navigators for Reasoning. CoRR, abs/2310.10080, 2023. doi: 10.48550/ ARXIV.2310.10080. URL https://doi.org/ 10.48550/arXiv.2310.10080. find
  13. Ivison, H., Wang, Y., Liu, J., Wu, Z., Pyatkin, V., Lambert, N., Smith, N. A., Choi, Y., and Hajishirzi, H. Unpacking DPO and PPO: Disentangling Best Practices for Learning from Preference Feedback. CoRR, abs/2406.09279, 2024. doi: 10.48550/ARXIV.2406.09279. URL https://doi.org/10.48550/arXiv.2406.… ↗
  14. OpenAI. OpenAI o1 System Card, 2024. URL https://api.semanticscholar.org/CorpusID: 272684752. ↗
  15. Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P. F., Leike, J., and Lowe, R. Training language models to follow instructions w… — Training language models to follow instructions with human feedback
  16. Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J., Zhang, H., and Stoica, I. Efficient Memory Management for Large Language Model Serving with PagedAttention. In Flinn, J., Seltzer, M. I., Druschel, P., Kaufmann, A., and Mace, J. (eds.), Proceedings of the 29th Symposium on…
  17. Lewkowycz, A., Andreassen, A., Dohan, D., Dyer, E., Michalewski, H., Ramasesh, V. V., Slone, A., Anil, C., Schlag, I., Gutman-Solo, T., Wu, Y., Neyshabur, B., Gur-Ari, G., and Misra, V. Solving Quantitative Reasoning Pal, A., Karkhanis, D., Dooley, S., Roberts, M., Naidu, S., and White, C. Smaug: Fi… — Smaug: Fixing Failure Modes of Preference Optimisation with DPO-Positive
  18. Setlur, A., Garg, S., Geng, X., Garg, N., Smith, V., and Kumar, A. RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-fold. CoRR, abs/2406.14532, 2024. doi: 10.48550/ ARXIV.2406.14532. URL https://doi.org/ 10.48550/arXiv.2406.14532. find
  19. Putta, P., Mills, E., Garg, N., Motwani, S., Finn, C., Garg, D., and Rafailov, R. Agent q: Advanced reasoning and learning for autonomous ai agents, 2024. URL https://arxiv.org/abs/2408.07199. ↗
  20. Shao, Z., Wang, P., Zhu, Q., Xu, R., Song, J., Zhang, M., Li, Y. K., Wu, Y., and Guo, D. DeepSeek-Math: Pushing the Limits of Mathematical Reasoning in Open Language Models. CoRR, abs/2402.03300, 2024. doi: 10.48550/ARXIV.2402.03300. URL https://doi.org/10.48550/arXiv.2402.03300. ↗
  21. Qwen. Qwen2.5-Math: The world’s leading open-sourced mathematical LLMs. https://qwenlm.github.io/blog/qwen2.5-math/, 2024. Accessed: 2024-09-23. ↗
  22. Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T. P., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D. Mast… find
  23. Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. Direct Preference Optimization: Your Language Model is Secretly a Reward Model. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: A…
  24. Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T. P., Simonyan, K., and Hassabis, D. Mastering Chess and Shogi by Self-play with a General Reinforcement Learning Algorithm. CoRR, abs/1712.01815, 2017. URL htt…
  25. Schulman, J. Notes on the KL-divergence Approximation. http://joschu.net/blog/kl-approx.html, 2020. Accessed: 2024-09-23. ↗
  26. Singh, A., Co-Reyes, J. D., Agarwal, R., Anand, A., Patil, P., Garcia, X., Liu, P. J., Harrison, J., Lee, J., Xu, K., Parisi, A. T., Kumar, A., Alemi, A. A., Rizkowsky, A., Nova, A., Adlam, B., Bohnet, B., Elsayed, G. F., Sedghi, H., Mordatch, I., Simpson, I., Gur, I., Snoek, J., Pennington, J., Hro… — Beyond Human Data: Scaling Self-Training for Problem-Solving with Language Models
  27. Schulman, J., Levine, S., Abbeel, P., Jordan, M. I., and Moritz, P. Trust Region Policy Optimization. In Bach, F. R. and Blei, D. M. (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1889–1897, Lille, F… find
  28. Schulman, J., Moritz, P., Levine, S., Jordan, M. I., and Abbeel, P. High-dimensional Continuous Control Using Generalized Advantage Estimation. In Bengio, Y. and LeCun, Y. (eds.), 4th International Conference on Learning Representations, ICLR 2016Proceedings, San Juan, Puerto Rico, 2016. URL http://… find
  29. Sutton, R. S. and Barto, A. G. Introduction to Reinforcement Learning. In Introduction to Reinforcement Learning, 1998. URL https://api.semanticscholar.org/CorpusID: 261579713. ↗
  30. Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal Policy Optimization Algorithms. CoRR, abs/1707.06347, 2017. URL http://arxiv.org/abs/1707.06347. ↗
  31. Sutton, R. S., McAllester, D. A., Singh, S., and Mansour, Y. Policy Gradient Methods for Reinforcement Learning with Function Approximation. In Solla, S. A., Leen, T. K., and Müller, K. (eds.), Search Boosts Reasoning via Iterative Preference Learning. CoRR, abs/2405.00451, 2024. doi: 10.48550/ ARX… find
  32. Advances in Neural Information Processing Systems 12, [NIPS Conference, pp. 1057–1063, Denver, Colorado, USA, 1999. The MIT Press. URL http://papers.nips.cc/paper/1713-policy-gradient-methods-for-reinforcement-learning-with-function-approximation. ↗
  33. Xu, S., Fu, W., Gao, J., Ye, W., Liu, W., Mei, Z., Wang, G., Yu, C., and Wu, Y. Is DPO Superior to PPO for LLM Alignment? A Comprehensive Study. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, 2024. OpenReview.net. URL https://openreview.net/forum?id=6XH8R7Y… ↗
  34. Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L., Canton-Ferrer, C., Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V., Goyal, N., Hartshorn, A., et… — Llama 2: Open Foundation and Fine-Tuned Chat Models
  35. Yuan, Z., Yuan, H., Li, C., Dong, G., Tan, C., and Zhou, C. Scaling Relationship on Learning Mathematical Reasoning with Large Language Models. CoRR, abs/2308.01825, 2023. doi: 10.48550/ARXIV.2308.01825. URL https://doi.org/10.48550/arXiv.2308.01825. ↗
  36. Towers, M., Kwiatkowski, A., Terry, J., Balis, J. U., De Cola, G., Deleu, T., Goulão, M., Kallinteris, A., Krimmel, M., KG, A., et al. Gymnasium: A standard interface for reinforcement learning environments. arXiv preprint arXiv:2407.17032, 2024.
  37. Zhang, D., Zhoubian, S., Yue, Y., Dong, Y., and Tang, J. ReST-MCTS*: LLM Self-training via Process Reward Guided Tree Search. CoRR, abs/2406.03816, 2024. doi: 10.48550/ARXIV.2406.03816. URL https://doi.org/10.48550/arXiv.2406.03816. ↗
  38. Trung, L. Q., Zhang, X., Jie, Z., Sun, P., Jin, X., and Li, H. ReFT: Reasoning with Reinforced Fine-tuning. In Ku, L., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2024, pp. 7601–7614, Bangk…
  39. Zheng, L., Yin, L., Xie, Z., Sun, C., Huang, J., Yu, C. H., Cao, S., Kozyrakis, C., Stoica, I., Gonzalez, J. E., Barrett, C., and Sheng, Y. Sglang: Efficient execution of structured language model programs. CoRR, abs/2312.07104, 2024. URL https://arxiv.org/ abs/2312.07104. ↗
  40. Zheng, R., Dou, S., Gao, S., Hua, Y., Shen, W., Wang, B., Liu, Y., Jin, S., Liu, Q., Zhou, Y., Xiong, L., Chen, L., Xi, Z., Xu, N., Lai, W., Zhu, M., Chang, C., Yin, Z., Weng, R., Cheng, W., Huang, H., Sun, T., Yan, H., Gui, T., Zhang, Q., Qiu, X., and Huang, X. Secrets of RLHF in Large Language Mod… — Secrets of RLHF in Large Language Models Part I: PPO
  41. Uesato, J., Kushman, N., Kumar, R., Song, H. F., Siegel, N. Y., Wang, L., Creswell, A., Irving, G., and Higgins, I. Solving math word problems with process-and outcome-based feedback. CoRR, abs/2211.14275, 2022. doi: 10.48550/ARXIV.2211.14275. URL https://doi.org/10.48550/arXiv.2211.14275. ↗
  42. Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P. F., and Irving, G. Fine-tuning Language Models from Human Preferences. CoRR, abs/1909.08593, 2019. URL http://arxiv.org/abs/1909.08593. ↗
  43. Wan, Z., Feng, X., Wen, M., McAleer, S. M., Wen, Y., Zhang, W., and Wang, J. AlphaZero-like Tree-search can Guide Large Language Model Decoding and Training. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, 2024. OpenReview.net. URL https://openreview.net/ for… ↗
  44. Wang, P., Li, L., Shao, Z., Xu, R. X., Dai, D., Li, Y., Chen, D., Wu, Y., and Sui, Z. Math-shepherd: Verify and reinforce llms step-by-step without human annotations. CoRR, abs/2406.06592, 2024. URL https://arxiv.org/abs/2312.08935. ↗
  45. Xie, Y., Goyal, A., Zheng, W., Kan, M., Lillicrap, T. P., Kawaguchi, K., and Shieh, M. Monte Carlo Tree find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kazemnejad-2024-vineppo-refining-credit-assignment-rl/