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

• URL: http://arxiv.org/abs/2409.09584v2
• Date: Fri, 24 Oct 2025 08:10:43 GMT
• Title: RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation
• Authors: Qingyao Li, Wei Xia, Kounianhua Du, Xinyi Dai, Ruiming Tang, Yasheng Wang, Yong Yu, Weinan Zhang,
• Abstract summary: We propose RethinkMCTS, a framework that explores and refines the reasoning process for code generation.<n>Specifically, we employ MCTS to search for thoughts before code generation and integrate MCTS with a refinement mechanism called rethink.<n>We demonstrate that RethinkMCTS outperforms previous search-based and feedback-enhanced code generation baselines.
• Score: 71.88883580383039
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• LogitsCoder: Towards Efficient Chain-of-Thought Path Search via Logits Preference Decoding for Code Generation [86.08600027874662]
  We propose LogitsCoder, a novel framework that enhances chain-of-thought reasoning through lightweight, logit-level control mechanisms for code generation.<n>We show that LogitsCoder produces more efficient and higher-quality reasoning chains, leading to superior code generation performance compared to baseline methods.
  arXiv  Detail & Related papers  (2026-02-15T08:52:19Z)
• AlignCoder: Aligning Retrieval with Target Intent for Repository-Level Code Completion [55.21541958868449]
  We propose AlignCoder, a repository-level code completion framework.<n>Our framework generates an enhanced query that bridges the semantic gap between the initial query and the target code.<n>We employ reinforcement learning to train an AlignRetriever that learns to leverage inference information in the enhanced query for more accurate retrieval.
  arXiv  Detail & Related papers  (2026-01-27T15:23:14Z)
• Let's Revise Step-by-Step: A Unified Local Search Framework for Code Generation with LLMs [16.818072348542923]
  We propose a unified local search framework which effectively performs step-by-step code revision.<n>Specifically, ReLoc explores a series of local revisions through four key algorithmic components.<n>We develop a specialized revision reward model that evaluates code quality based on revision distance to produce fine-grained preferences.
  arXiv  Detail & Related papers  (2025-08-10T17:11:56Z)
• LLM-First Search: Self-Guided Exploration of the Solution Space [29.780554400938335]
  Large Language Models (LLMs) have demonstrated remarkable improvements in reasoning and planning through increased test-time compute.<n>We propose textbfLLM-First Search (LFS), a novel textitLLM Self-Guided Search method.
  arXiv  Detail & Related papers  (2025-06-05T16:27:49Z)
• Large Language Model Can Be a Foundation for Hidden Rationale-Based Retrieval [12.83513794686623]
  In this paper, we propose and study a more challenging type of retrieval task, called hidden rationale retrieval.<n>To address such problems, an instruction-tuned Large language model (LLM) with a cross-encoder architecture could be a reasonable choice.<n>We name this retrieval framework by RaHoRe and verify its zero-shot and fine-tuned performance superiority on Emotional Support Conversation (ESC)
  arXiv  Detail & Related papers  (2024-12-21T13:19:15Z)
• CodeXEmbed: A Generalist Embedding Model Family for Multiligual and Multi-task Code Retrieval [103.116634967815]
  We introduce CodeXEmbed, a family of large-scale code embedding models ranging from 400M to 7B parameters. Our novel training pipeline unifies multiple programming languages and transforms various code-related tasks into a common retrieval framework. Our 7B model sets a new state-of-the-art (SOTA) in code retrieval, outperforming the previous leading model, Voyage-Code, by over 20% on CoIR benchmark.
  arXiv  Detail & Related papers  (2024-11-19T16:54:45Z)
• Enhancing LLM Reasoning with Reward-guided Tree Search [95.06503095273395]
  o1-like reasoning approach is challenging, and researchers have been making various attempts to advance this open area of research. We present a preliminary exploration into enhancing the reasoning abilities of LLMs through reward-guided tree search algorithms.
  arXiv  Detail & Related papers  (2024-11-18T16:15:17Z)
• CodeTree: Agent-guided Tree Search for Code Generation with Large Language Models [106.11371409170818]
  Large language models (LLMs) can act as agents with capabilities to self-refine and improve generated code autonomously. We propose CodeTree, a framework for LLM agents to efficiently explore the search space in different stages of the code generation process. Specifically, we adopted a unified tree structure to explicitly explore different coding strategies, generate corresponding coding solutions, and subsequently refine the solutions.
  arXiv  Detail & Related papers  (2024-11-07T00:09:54Z)
• Scattered Forest Search: Smarter Code Space Exploration with LLMs [55.71665969800222]
  We introduce Scattered Forest Search to enhance solution diversity while searching for solutions. Experiments on HumanEval, MBPP, APPS, CodeContests, and Leetcode reveal significant performance improvements.
  arXiv  Detail & Related papers  (2024-10-22T01:58:29Z)
• Learning to Better Search with Language Models via Guided Reinforced Self-Training [15.289058352618468]
  We propose guided self-training (Guided-ReST) to improve the model's capability for effective search during inference.<n>Guided-ReST incorporates optimal solutions into the model's search procedure, enabling the generation of high-quality search traces.<n>Our method significantly enhances the search capabilities of language models on arithmetic reasoning and code self-repair tasks.
  arXiv  Detail & Related papers  (2024-10-03T21:07:59Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• RoT: Enhancing Large Language Models with Reflection on Search Trees [41.67536806038573]
  We introduce Reflection on search Trees (RoT), an LLM reflection framework designed to improve the performance of tree-search-based prompting methods. It uses a strong LLM to summarize guidelines from previous tree search experiences to enhance the ability of a weak LLM. We propose a novel state selection method, which identifies the critical information from historical search processes to help RoT generate more specific and meaningful guidelines.
  arXiv  Detail & Related papers  (2024-04-08T12:31:23Z)
• Rewriting the Code: A Simple Method for Large Language Model Augmented Code Search [7.822427053078387]
  Generation-Augmented Retrieval (GAR) framework generates exemplar code snippets to augment queries. We propose a simple yet effective method that additionally Rewrites the Code (ReCo) within the for style normalization. Code Style Similarity is the first metric tailored to quantify stylistic similarities in code.
  arXiv  Detail & Related papers  (2024-01-09T12:12:50Z)
• Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
  Large Language Models have excelled in remarkable reasoning capabilities with advanced prompting techniques. Recent works propose to utilize external programs to define search logic, such that LLMs can perform passive tree search to solve more challenging reasoning tasks. We propose a new concept called autonomous tree-search ability of LLM, which can automatically generate a response containing search trajectories for the correct answer.
  arXiv  Detail & Related papers  (2023-10-14T14:14:38Z)
• Constructing Tree-based Index for Efficient and Effective Dense Retrieval [26.706985694158384]
  JTR stands for Joint optimization of TRee-based index and query encoding. We design a new unified contrastive learning loss to train tree-based index and query encoder in an end-to-end manner. Experimental results show that JTR achieves better retrieval performance while retaining high system efficiency.
  arXiv  Detail & Related papers  (2023-04-24T09:25:39Z)
• Generation-Augmented Query Expansion For Code Retrieval [51.20943646688115]
  We propose a generation-augmented query expansion framework. Inspired by the human retrieval process - sketching an answer before searching. We achieve new state-of-the-art results on the CodeSearchNet benchmark.
  arXiv  Detail & Related papers  (2022-12-20T23:49:37Z)
• Zero-Shot Retrieval with Search Agents and Hybrid Environments [8.017306481455778]
  Current language models can learn symbolic query reformulation policies, in combination with traditional term-based retrieval, but fall short of outperforming neural retrievers. We extend the previous learning to search setup to a hybrid environment, which accepts discrete query refinement operations, after a first-pass retrieval step via a dual encoder. Experiments on the BEIR task show that search agents, trained via behavioral cloning, outperform the underlying search system based on a combined dual encoder retriever and cross encoder reranker.
  arXiv  Detail & Related papers  (2022-09-30T13:50:25Z)
• Searching for a Search Method: Benchmarking Search Algorithms for Generating NLP Adversarial Examples [10.993342896547691]
  We study the behavior of several black-box search algorithms used for generating adversarial examples for natural language processing (NLP) tasks. We perform a fine-grained analysis of three elements relevant to search: search algorithm, search space, and search budget.
  arXiv  Detail & Related papers  (2020-09-09T17:04:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.