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

arXiv: https://arxiv.org/abs/2409.09584 · HTML: https://mlsanity.com/paper/2409.09584/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 32 of its 51 references that are in the map.
- First posted on arXiv 15 Sep 2024.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 30 of 32)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [StarCoder: may the source be with you!](https://mlsanity.com/paper/2305.06161/) (2023)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [WizardCoder: Empowering Code Large Language Models with Evol-Instruct](https://mlsanity.com/paper/2306.08568/) (2023)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [InCoder: A Generative Model for Code Infilling and Synthesis](https://mlsanity.com/paper/2204.05999/) (2022)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [CodeAgent: Enhancing Code Generation with Tool-Integrated Agent Systems for Real-World Repo-level Coding Challenges](https://mlsanity.com/paper/2401.07339/) (2024)
- [Using an LLM to Help With Code Understanding](https://mlsanity.com/paper/2307.08177/) (2023)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [SPoC: Search-based Pseudocode to Code](https://mlsanity.com/paper/1906.04908/) (2019)
- [Self-Organized Agents: A LLM Multi-Agent Framework toward Ultra Large-Scale Code Generation and Optimization](https://mlsanity.com/paper/2404.02183/) (2024)
- [Planning In Natural Language Improves LLM Search For Code Generation](https://mlsanity.com/paper/2409.03733/) (2024)
- [CodeScore: Evaluating Code Generation by Learning Code Execution](https://mlsanity.com/paper/2301.09043/) (2023)
- [Large Language Models are In-Context Semantic Reasoners rather than Symbolic Reasoners](https://mlsanity.com/paper/2305.14825/) (2023)
- [Iterative Refinement of Project-Level Code Context for Precise Code Generation with Compiler Feedback](https://mlsanity.com/paper/2403.16792/) (2024)
- [LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning](https://mlsanity.com/paper/2407.02511/) (2024)
- [Make Every Move Count: LLM-based High-Quality RTL Code Generation Using MCTS](https://mlsanity.com/paper/2402.03289/) (2024)
- [Uncertainty of Thoughts: Uncertainty-Aware Planning Enhances Information Seeking in Large Language Models](https://mlsanity.com/paper/2402.03271/) (2024)
- [AST-T5: Structure-Aware Pretraining for Code Generation and Understanding](https://mlsanity.com/paper/2401.03003/) (2024)
- [LiteSearch: Efficacious Tree Search for LLM](https://mlsanity.com/paper/2407.00320/) (2024)

## Built on by (most cited first, 26 of 26)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [S*: Test Time Scaling for Code Generation](https://mlsanity.com/paper/2502.14382/) (2025)
- [ReSo: A Reward-driven Self-organizing LLM-based Multi-Agent System for Reasoning Tasks](https://mlsanity.com/paper/2503.02390/) (2025)
- [Agentic Information Retrieval](https://mlsanity.com/paper/2410.09713/) (2024)
- [Navigating the Alpha Jungle: An LLM-Powered MCTS Framework for Formulaic Factor Mining](https://mlsanity.com/paper/2505.11122/) (2025)
- [MMSkills: Towards Multimodal Skills for General Visual Agents](https://mlsanity.com/paper/2605.13527/) (2026)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [SRA-MCTS: Self-driven Reasoning Augmentation with Monte Carlo Tree Search for Code Generation](https://mlsanity.com/paper/2411.11053/) (2024)
- [From Large to Small: Transferring CUDA Optimization Expertise via Reasoning Graph](https://mlsanity.com/paper/2510.19873/) (2025)
- [Optimizing Prompt Sequences using Monte Carlo Tree Search for LLM-Based Optimization](https://mlsanity.com/paper/2508.05995/) (2025)
- [ARCS: Agentic Retrieval-Augmented Code Synthesis with Iterative Refinement](https://mlsanity.com/paper/2504.20434/) (2025)
- [LLM-First Search: Self-Guided Exploration of the Solution Space](https://mlsanity.com/paper/2506.05213/) (2025)
- [NL-Debugging: Exploiting Natural Language as an Intermediate Representation for Code Debugging](https://mlsanity.com/paper/2505.15356/) (2025)
- [Seed-CTS: Unleashing the Power of Tree Search for Superior Performance in Competitive Coding Tasks](https://mlsanity.com/paper/2412.12544/) (2024)
- [Thinking Before Running! Efficient Code Generation with Thorough Exploration and Optimal Refinement](https://mlsanity.com/paper/2502.17442/) (2024)
- [Policy of Thoughts: Scaling Test-Time Training for LLM Reasoning via Online Policy Evolution](https://mlsanity.com/paper/2601.20379/) (2026)
- [Boost, Disentangle, and Customize: A Robust System2-to-System1 Pipeline for Code Generation](https://mlsanity.com/paper/2502.12492/) (2025)
- [Monte Carlo Tree Diffusion with Multiple Experts for Protein Design](https://mlsanity.com/paper/2509.15796/) (2025)
- [Plan-MCTS: Plan Exploration for Action Exploitation in Web Navigation](https://mlsanity.com/paper/2602.14083/) (2026)
- [Towards Stepwise Domain Knowledge-Driven Reasoning Optimization and Reflection Improvement](https://mlsanity.com/paper/2504.09058/) (2025)
- [DebugTA: An LLM-Based Agent for Simplifying Debugging and Teaching in Programming Education](https://mlsanity.com/paper/2510.11076/) (2025)
- [LogitsCoder: Towards Efficient Chain-of-Thought Path Search via Logits Preference Decoding for Code Generation](https://mlsanity.com/paper/2602.14054/) (2026)
- [ROSUM-MCTS: Monte Carlo Tree Search-Inspired HDL Code Summarization with Structural Rewards](https://mlsanity.com/paper/2606.07925/) (2026)
- [When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models](https://mlsanity.com/paper/2608.30395/) (2026)
- [ReMCTS: Reflection-Enhanced Monte Carlo Tree Search for Code Generation](https://mlsanity.com/paper/2609.34717/) (2026)

## Abstract (arXiv)

Tree search methods have demonstrated impressive performance in code generation. Previous methods combine tree search with reflection that summarizes past mistakes to achieve iterative improvement. However, these methods face significant challenges. First, they search directly within the code language space, neglecting the underlying reasoning process critical for effective code generation. Second, reflection-based approaches merely accumulate historical errors in memory without providing correct reasoning pathways, making it difficult for subsequent search iterations to identify optimal solutions, resulting in decreased search quality. In this work, we propose RethinkMCTS, a framework that systematically explores and refines the reasoning process for code generation. Specifically, we employ MCTS to search for thoughts before code generation and integrate MCTS with a refinement mechanism called rethink, which incorporates fine-grained code execution feedback to refine erroneous thoughts during the search. It ensures the search path aligns with better reasoning, improving overall search quality. Through extensive experiments, we demonstrate that RethinkMCTS outperforms previous search-based and feedback-enhanced code generation baselines.