Elamur Research⌕
☰
home / papers / 2025 / RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation

RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation

Paper · 2025 · Qingyao Li, Wei Xia, Xinyi Dai et al.

Summary

The paper tackles a weakness of tree-search approaches to LLM code generation. Existing methods such as LATS search directly over code and handle mistakes through reflection, which piles up summaries of past errors in memory but never repairs the flawed reasoning itself. The authors propose RethinkMCTS, which runs Monte Carlo Tree Search over intermediate reasoning steps ("thoughts") and generates code only once those steps are in place. When the code fails, the code is broken into basic blocks along a control-flow graph and its variable states are traced on public tests, following LDB. An LLM then judges each block, and this verbal feedback drives a "rethink" step that rewrites the faulty thought instead of merely logging it. Candidate code is scored by a dual evaluation that combines public-test pass rate with LLM self-assessment. On APPS and HumanEval, using GPT-4o-mini and GPT-3.5-Turbo, the framework beats prior search-based and feedback-driven baselines while spending fewer tokens than reflection. This suggests that fixing reasoning paths works better than accumulating error histories.

Key points

  • Benchmarks and models: evaluation covers competition-style APPS and HumanEval. Correctness is judged on hidden private tests, and only public tests are visible during search. The LLMs are GPT-4o-mini and GPT-3.5-Turbo.
  • Effect of rethink on the search tree: turning on rethink raises the share of tree-generated programs that pass public tests.
    • APPS Intro.: from 10.04 to 15.60.
    • HumanEval: from 48.30 to 53.29.
  • Rethink versus wider search: adding more rethink operations helps more than simply expanding exploration.
  • Reward weighting: a (0.8, 0.2) weighting, where self-evaluation separates programs that pass all public tests, outperforms (1.0, 0.2) and (1.0, 1.0). The latter two discard promising paths too early.
  • Limitations and availability:
    • The refined step is simply the most recent one that caused the error.
    • Transfer to domains lacking rich feedback, such as math, is uncertain.
    • Code is available at github.com/SIMONLQY/RethinkMCTS.

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

🎓Shanghai Jiao Tong UniversityShanghai · China149 works · 16,161 citations🏢Huawei TechnologiesShenzhen · China75 works · 12,975 citations

 Fields, topics and concepts

📚 Shelves 6The 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 worksInformation Systems · 1,437 worksComputer Science Applications · 102 works

🧭 Topics 1Research subjects and languages the work is about.Code & programming languages · 129 works

Cite

Cite as Qingyao Li, Wei Xia, Xinyi Dai, Kounianhua Du, Weiwen Liu, Yasheng Wang, Ruiming Tang, Yong Yu and Weinan Zhang. 2025. RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2025.emnlp-main.410

@inproceedings{li2025rethinkmcts,
  title = {{RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation}},
  author = {Qingyao Li, Wei Xia, Xinyi Dai, Kounianhua Du, Weiwen Liu, Yasheng Wang, Ruiming Tang, Yong Yu and Weinan Zhang},
  booktitle = {Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
  doi = {10.18653/v1/2025.emnlp-main.410},
  url = {https://doi.org/10.18653/v1/2025.emnlp-main.410}
}

References

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

  1. V Aho Alfred, S Lam Monica, and D Ullman Jeffrey. 2007. Compilers principles, techniques & tools. pearson Education. find
  2. Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and 1 others. 2021. Program synthesis with large language models. arXiv preprint arXiv:2108.07732.
  3. Zhangqian Bi, Yao Wan, Zheng Wang, Hongyu Zhang, Batu Guan, Fangxin Lu, Zili Zhang, Yulei Sui, Hai Jin, and Xuanhua Shi. 2024. Iterative refinement of project-level code context for precise code generation with compiler feedback. arXiv preprint arXiv:2403.16792. find
  4. Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. 2012. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43… find
  5. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, and 1 others. 2021. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374.
  6. Fanny Chevalier, David Auber, and Alexandru Telea. 2007. Structural analysis and visualization of c++ code evolution using syntax trees. In Ninth international workshop on Principles of software evolution: in conjunction with the 6th ESEC/FSE joint meeting, pages 90–97. find
  7. Michelle Cook, Megan Fowler, Jason O Hallstrom, Joseph E Hollingsworth, Tim Schwab, Yu-Shan Sun, and Murali Sitaraman. 2018. Where exactly are the difficulties in reasoning logically about code? experimentation with an online system. In Proceedings of the 23rd Annual ACM Conference on Innovation and… find
  8. Matthew DeLorenzo, Animesh Basak Chowdhury, Vasudev Gohil, Shailja Thakur, Ramesh Karri, Siddharth Garg, and Jeyavijayan Rajendran. 2024. Make every move count: Llm-based high-quality rtl code generation using mcts. arXiv preprint arXiv:2402.03289. — [arXiv:2402.03289](https://arxiv.org/abs/2402.03289) find
  9. Yihong Dong, Jiazheng Ding, Xue Jiang, Ge Li, Zhuo Li, and Zhi Jin. 2023. Codescore: Evaluating code generation by learning code execution. arXiv preprint arXiv:2301.09043. — [arXiv:2301.09043](https://arxiv.org/abs/2301.09043) find
  10. Xidong Feng, Ziyu Wan, Muning Wen, Ying Wen, Weinan Zhang, and Jun Wang. 2023. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.17179. find
  11. Data Flow. 1994. Control Flow Analysis. Ph.D. thesis, QUEENSLAND UNIVERSITY OF TECHNOL-OGY. find
  12. Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Wen-tau Yih, Luke Zettlemoyer, and Mike Lewis. 2022. Incoder: A generative model for code infilling and synthesis. arXiv preprint arXiv:2204.05999. find
  13. Linyuan Gong, Mostafa Elhoushi, and Alvin Cheung. 2024. Ast-t5: Structure-aware pretraining for code generation and understanding. arXiv preprint arXiv:2401.03003. find
  14. Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. 2023. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305.14992. find
  15. Zhenyu He, Jun Zhang, Shengjie Luo, Jingjing Xu, Zhi Zhang, and Di He. 2024. Let the code llm edit itself when you edit the code. arXiv preprint arXiv:2407.03157. — [arXiv:2407.03157](https://arxiv.org/abs/2407.03157) find
  16. Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and 1 others. 2021. Measuring coding challenge competence with apps. arXiv preprint arXiv:2105.09938.
  17. Zhiyuan Hu, Chumin Liu, Xidong Feng, Yilun Zhao, See-Kiong Ng, Anh Tuan Luu, Junxian He, Pang Wei Koh, and Bryan Hooi. 2024. Uncertainty of thoughts: Uncertainty-aware planning enhances information seeking in large language models. arXiv preprint arXiv:2402.03271. find
  18. Dong Huang, Qingwen Bu, Jie Zhang, Xiaofei Xie, Junjie Chen, and Heming Cui. 2023a. Bias assessment and mitigation in llm-based code generation. arXiv preprint arXiv:2309.14345. — [arXiv:2309.14345](https://arxiv.org/abs/2309.14345) find
  19. Dong Huang, Qingwen Bu, Jie M Zhang, Michael Luck, and Heming Cui. 2023b. Agentcoder: Multi-agent-based code generation with iterative testing and optimisation. arXiv preprint arXiv:2312.13010. find
  20. Jie Huang and Kevin Chen-Chuan Chang. 2022. Towards reasoning in large language models: A survey. arXiv preprint arXiv:2212.10403.
  21. Yoichi Ishibashi and Yoshimasa Nishimura. 2024. Self-organized agents: A llm multi-agent framework toward ultra large-scale code generation and optimization. arXiv preprint arXiv:2404.02183. — [arXiv:2404.02183](https://arxiv.org/abs/2404.02183) find
  22. Haolin Jin, Linghan Huang, Haipeng Cai, Jun Yan, Bo Li, and Huaming Chen. 2024. From llms to llm-based agents for software engineering: A survey of current, challenges and future. arXiv preprint arXiv:2408.02479. — [arXiv:2408.02479](https://arxiv.org/abs/2408.02479) find
  23. Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, and Percy S Liang. 2019. Spoc: Search-based pseudocode to code. Advances in Neural Information Processing Systems, 32. find
  24. James R Larus. 1999. Whole program paths. ACM SIGPLAN Notices, 34(5):259–269. find
  25. Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, and 1 others. 2023. Starcoder: may the source be with you! arXiv preprint arXiv:2305.06161. find
  26. Yichen Li, Yun Peng, Yintong Huo, and Michael R Lyu. 2024. Enhancing llm-based coding tools through native integration of ide-derived static context. In Proceedings of the 1st International Workshop on Large Language Models for Code, pages 70–74. find
  27. Ziyang Luo, Can Xu, Pu Zhao, Qingfeng Sun, Xiubo Geng, Wenxiang Hu, Chongyang Tao, Jing Ma, Qingwei Lin, and Daxin Jiang. 2023. Wizardcoder: Empowering code large language models with evol-instruct. arXiv preprint arXiv:2306.08568. find
  28. Silin Meng, Yiwei Wang, Cheng-Fu Yang, Nanyun Peng, and Kai-Wei Chang. 2024. Llm-a*: Large language model enhanced incremental heuristic search on path planning. arXiv preprint arXiv:2407.02511. find
  29. Daye Nam, Andrew Macvean, Vincent Hellendoorn, Bogdan Vasilescu, and Brad Myers. 2024. Using an llm to help with code understanding. In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering, pages 1–13. find
  30. Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, and 1 others. 2023. Code llama: Open foundation models for code. arXiv preprint arXiv:2308.12950.
  31. Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2024. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36.
  32. David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, and 1 others. 2017. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815.
  33. Xiaojuan Tang, Zilong Zheng, Jiaqi Li, Fanxu Meng, Song-Chun Zhu, Yitao Liang, and Muhan Zhang. 2023. Large language models are in-context semantic reasoners rather than symbolic reasoners. arXiv preprint arXiv:2305.14825.
  34. Ante Wang, Linfeng Song, Ye Tian, Baolin Peng, Dian Yu, Haitao Mi, Jinsong Su, and Dong Yu. 2024a. Litesearch: Efficacious tree search for llm. arXiv preprint arXiv:2407.00320. — [arXiv:2407.00320](https://arxiv.org/abs/2407.00320) find
  35. Evan Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, Will Song, Vaskar Nath, Ziwen Han, Sean Hendryx, Summer Yue, and Hugh Zhang. 2024b. Planning in natural language improves llm search for code generation. arXiv preprint arXiv:2409.03733. find
  36. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, and 1 others. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824– 24837.
  37. Lin Zheng, Jianbo Yuan, Zhi Zhang, Hongxia Yang, and Lingpeng Kong. 2023. Self-infilling code generation. In Forty-first International Conference on Machine Learning. find
  38. Li Zhong, Zilong Wang, and Jingbo Shang. 2024. Ldb: A large language model debugger via verifying runtime execution step-by-step. arXiv preprint arXiv:2402.16906. find
  39. Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. 2023. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.04406. find
  40. Changzhi Zhou, Xinyu Zhang, Dandan Song, Xiancai Chen, Wanli Gu, Huipeng Ma, Yuhang Tian, Mengdi Zhang, and Linmei Hu. 2025. Refinecoder: Iterative improving of large language models via adaptive critique refinement for code generation. arXiv preprint arXiv:2502.09183. — [arXiv:2502.09183](https://arxiv.org/abs/2502.09183) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/li-2025-rethinkmcts-refining-erroneous-thoughts-monte/