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
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords: Code Generation, Large Language Model Agent, Monte Carlo Tree Search

Abstract:
LLM agents enhanced by tree search algorithms have shown significant performance in code generation. However, existing search methods generally operate directly in the code language space, leading to suboptimal search quality due to ignoring the reasoning process behind the code. Specifically, two key challenges remain largely unaddressed: 1) A lack of exploration for the reasoning process, which is essential for high-reasoning-demand tasks like code generation, and 2) Inadequate search quality due to the absence of refinement mechanism. In this paper, we introduce RethinkMCTS, a framework that explores and refines the reasoning process for generating code. Specifically, we employ MCTS to search for the 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 the better reasoning, improving overall search quality. Through extensive experiments, we demonstrate that RethinkMCTS outperforms previous search-enhanced and feedback-enhanced code generation baselines. On the HumanEval dataset, it boosts the pass@1 of GPT-3.5-turbo from 70.12 to 89.02 and that of GPT-4o-mini from 87.20 to 94.51. By conducting thought-level exploration and integrating the rethink mechanism, it significantly enhances the search quality of the entire search tree

Decision: reject
Reviewer scores: 3, 3, 6, 6

Reviews and discussion:
<thread>
creation date:
1729840494712

thread_type:
official_review

<thread_object>
creator: reviewer_gprr

<content>
summary:
This paper proposes to use Monte-Carlo tree search to discover useful rationale for code generation. It also incorporates block-level info feedback and self-evaluation for better value estimate of nodes in the tree. Experiment results show that the proposed method achieves SOTA performance compared to other augmented code generation method, such as reflexion and tree-of-thoughts.

strengths:
The propose method is novel and provides a nice way to combine MCTS and chain-of-thoughts. The paper is well-written and easy to understand.

weaknesses:
The experiment results can be further strengthen:
1. for such a searching algorithm, the results between different runs might differ a lot. Thus, it is better to incorporate std information for pass rate.
2. The run time of different algorithms should also be compared.

questions:
Nothing necessary stands out.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730377542434

thread_type:
official_review

<thread_object>
creator: reviewer_vezu

<content>
summary:
This paper proposes an MCTS-based approach to incorporate reasoning into code generation. A key hypothesis is that searching in the space of thoughts is better than searching in the space of code, and that searching in thought space allows the LLM to explore better as well as have a higher quality of search by refining its intermediate outputs. The feedback used in MCTS is a combination of scalar feedback and verbal feedback generated by the LLM. This approach differs from other reflection-based approaches using tree search in that intermediate nodes in the tree are refined so that the LLM can follow a better path to the solution using the reasoning provided in the form of verbal feedback. This work also proposes combining LLM self-evaluations with public test cases to evaluate the generated code, to compensate for the low coverage of public test cases with respect to the problem, leading to inaccurate assessment of the generated solution. The results of the proposed RethinkMCTS approach are demonstrated on the HumanEval and Apps datasets, for GPT-3.5-turbo and GPT-4o-mini.

strengths:
- The paper proposes a neat, conceptually simple way of doing MCTS in the space of LLMs for code generation.
- This work suggests an alternative to current approaches to handle incomplete coverage of solutions by public test cases by proposing LLM self-assessment instead of generating synthetic test cases that may not always be accurate.
- The method section is written well, clearly outlining the different parts of the MCTS algorithm and what they correspond to in this context, as well as the additional verbal feedback and rethink stages that are the novel contributions of the proposed approach.
- The ablation results in Figure 3 and Figure 6, and the search granularity results in Figure 4 and Figure 7 tie together each individual contribution in the paper with the main rethink hypothesis in the paper.
- The proposed approach is compared with several feedback based and tree-search based baselines.

weaknesses:
- In Table 1, the RethinkMCTS results have been marked in bold, which I presume indicates the superior performance of this method over other baselines. However, it seems to be the case that for GPT-4o-mini, the results shown by the Tree-of-Thought baseline are in most cases, at par with RethinkMCTS, and the pass rate of PG-TD on APPS-Comp is actually higher than that of RethinkMCTS. This table would be clearer to read if the best baselines that are at par with or better than RethinkMCTS were also highlighted.
- The absence of standard errors in Table 1 makes it difficult to see if the performance improvements are significant or not.
- One important detail that would warrant some discussion in this paper is the number of LLM calls used to generate the final output. Ideally for a fair comparison with baselines, this would be an important parameter to standardise, since recent work in inference-time approaches have shown that given more compute during inference, LLMs can exhibit superior performance. If the baselines use fewer LLM calls at inference time than RethinkMCTS to generate the final output, this would not be a fair comparison.
- The choice of datasets and models makes the evaluation of this approach difficult: given that the base models already show strong performance on these datasets, it becomes difficult to assess the contribution of this approach, which has several components, in increasing performance. If this approach shows significant gains in performance, for either a) a more difficult dataset, or b) weaker models, that might make the strength of the approach as well as its individual components clearer.
- Minor: There is an overloading of the term $a$, in some places it is used to denote the action, in others it is used as a coefficient for the reward weight vector.

questions:
- The improvements shown by RethinkMCTS compared to other baselines seem to be more pronounced on GPT-3.5-turbo compared to GPT-4o-mini. Is there anything that can be inferred from this result that can tie the effectiveness of this approach with the capabilities of the base model?
- In Figure 3, the result on HumanEval indicates that the rethink mechanism seems to have the least effect out of all components on performance. For all of the other results as well (except APPS Intro. in Figure 6), the rethink component is not the most impactful in determining performance. This appears to be contrary to the claim of this paper. Could the authors clarify how these results were interpreted?
- In Figure 5(a), as the number of rollouts increases from 43 to 58, the performance with rethink reduces, which is counterintuitive. The result in 5(b) is more consistent with what we could expect as we increase the number of rollouts: performance would plateau beyond a certain number of rollouts. Could the authors provide an explanation for why we see the drop in performance in Figure 5(a)?
- The numbers in Table 3 are very different from those in Figure 3; is it a different metric, model, or dataset?
- GPT-4o-mini has comparable token-level search performance compared to RethinkMCTS on HumanEval; is it possible that HumanEval is not the best testbed for this approach, given that base performance is already quite high?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730431682640

thread_type:
official_review

<thread_object>
creator: reviewer_vanh

<content>
summary:
In this paper, the authors propose an enhancement of Monte-Carlo Tree Search, named RethinkMCTS, that refines reasonings with feedback in code generation tasks. The search incorporates both execution feedback and verbal feedback to refine reasonings. Empirical evaluations on two coding benchmarks show modest pass metrics improvements over existing baselines.

strengths:
1. This paper is well-written and easy to understand. The various feedback and the rethink process are integrated quite well.

2. The included baselines are comprehensive.

weaknesses:
1. The novelty of this paper seems limited. I am struggling to understand the difference from the LATS and ToT work. In comparison, it seems like the proposed method is essentially LATS + ToT? If that is correct, I think the contribution is of limited significance.

2. The improvements over baselines, especially ToT, are small. With GPT-4o-mini, the differences were quite small. As there are no confidence intervals, there is doubt about the statistical significance of those improvements.

3. It is unclear to me whether the experiment results in Table 1 were controlled for the number of tokens across different methods, which is crucial for a fair comparison. Please provide more details about the comparison setting.

4. One part of the novelty is the block-level feedback, however, there is no example given for what this type of feedback looks like and no explanation about implementation details. Please provide more information.

questions:
Please see the weakness section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730596383667

thread_type:
official_review

<thread_object>
creator: reviewer_ruo1

<content>
summary:
This work proposed a MCTS variant that allows node level self-refinement as a alternative way to ``expand'' the search tree with ``refined nodes''. This refinement method prompt an LLM to self-refine the thought and corresponding code, conditioned on a erroneous node. In addition to the public test cases, the authors incorporated ``block-level analysis'' and ``LLM self-evaluation'' as feedback signals to improve the evaluation of search rollouts.

strengths:
- The problem, search in LLM code generation, is very relevant
- Ablation in Figure 3 shows each component plays certain role in the framework

weaknesses:
- The evaluation strategy and refinement in tree search appears to be stitched for final performance but are totally irrelevant strategies. As the paper is titled as RethinkMCTS, adding additional feedback effort may make it more difficult for the audience to evaluate the role of ``rethink''.
    - for example, RethinkMCTS without VF (39 in Figure 3) can be lower than PG-TD (40 in Table 1) for APPS Intro. It is not clear what is the performance of rethink only, in comparison with the baselines, as the baselines are mainly about correction/refinements.


- My biggest concern is that, if my understanding is correct, since RethinkMCTS can have maximum 16 rollouts (meaning maximum 16 evaluations with public tests), it is not fair to compare ``pass@1'' to the base model.
    - A important baseline is: run 16 responses with a base model, and then filtered out those failed public tests, and then compute pass@1 using the responses which are correct for public tests for instance by randomly sample 1 multiple times and take the average.
    - If an additional evaluation is available, then another baseline could be best-of-N with such evaluation. For example, with the responses passed the public tests, one could for example use LLM to rank and select the BON

questions:
- ToT appears very strong in the baselines, a more comprehensive comparison with ToT might be helpful to understand the contributions
    - According to my understanding the major differences are: RethinkMCTS has refine but ToT not, and the difference between evaluation strategy.
    - A comprehensive ablation should be conducted versus ToT:
        - There should be one more case: w Rethink only in Figure 3 so that the audience could understand how the Rethink mechanism improves ToT
        - While conducting the experiment with Rethink only, please include all difficulty levels (and both models as well), 

- Minor points:
    - Please add an average pass rate/pass@1 for APPS (weighted by number of problems in each difficulty level)
    - PG-TD has 43.16 for APPS Comp. with 4o-mini but RethinkMCTS's 42.50 was bold instead.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732173368192

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
Thank you again for all your valuable feedback and constructive suggestions. Based on the feedback from reviewers, we have identified some common concerns. Here, we provide a general response to address these shared questions and clarify our approach:

> Regarding the performance improvements of our method compared to baselines, particularly compared with ToT.

We would like clarify some key points about ToT:
1. The search for reasoning/thought process for code is one of our key contributions. The strong performance of ToT is largely because we did not implement it strictly as described in the original paper. While "thoughts" are mentioned in its title, the original paper would decompose the task into fixed steps and search for solutions within each step. In our implementation, we merged ToT with our method by defining the search space in terms of reasoning "thoughts." This significantly improved its performance, making the ToT implementation in the paper an ablation of our method. The implementation approach likely plays a significant role in determining its performance. For instance, in the AgentCoder paper[1], ToT performs poorly, whereas when integrated with our searching reasoning process, it achieves much better results. 
2. Our model demonstrates a clear advantage, especially on models like GPT-3.5, which have weaker coding capabilities. This advantage persists even in the rethink-only setting.

To better illustrate our point, we strictly follow the paper of ToT and adapt a task-decomposition version of ToT as ToT(Ori), and we also add the RethinkOnly as a comparison:

| Model| APPS-intro. (Pass Rate %) | APPS-inter. (Pass Rate %) | APPS-comp. (Pass Rate %) | APPS-intro. (Pass@1) | APPS-inter. (Pass@1) | APPS-comp. (Pass@1) | HumanEval (Pass@1) |
|-|-|-|-|-|-|-|-|
| **(GPT3.5)**||||||||
| ToT(Ori) |62.56|57.97|28.00|38|25|10|76.22|
| ToT(In our paper)| 63.21 | 63.49 | 26.30 | 37 | 33| 11| 84.15|
| RethinkMCTS(Ours)| **67.09**|**68.65**| **29.50** | **45** | **38**| **13**| **89.02**|
| **(GPT4o-mini)**||||||||
| ToT(Ori) |71.03|67.84|37.17|52|46|23|92.68|
| ToT(In our paper)| 74.34 | 71.83 | **42.50** |55| 47|27| 93.29|
| RethinkMCTS(Ours) | **76.60**|**74.35**| **42.50**| **59** |**49**| **28**| **94.51**|

The original version of ToT, which employs task decomposition into steps followed by searching each step individually, performs relatively poorly. In contrast, the performance improves largely when we adapt ToT to our code reasoning-based version (as the version in our paper). This highlights the effectiveness and contribution of our work in exploring the reasoning process behind code generation.

> Regarding the time and token cost.

RethinkMCTS consumes more tokens and time due to the inclusion of verbal feedback, specifically the block-level analysis. However, the feedback makes our model deliver significantly better results. It is essential to the success of the "rethink" mechanism, and it represents an important characteristic in the coding environment (there would be no such detailed feedback for the math reasoning problem). Therefore, incorporating such feedback is crucial. Like OpenAI's o1 model (which solves one problem with thousands of tokens in the hidden CoT and minutes to take[2]), our primary aim is not to optimize token count or computation time. This "slow thinking" mode emphasizes enabling LLMs to generate higher-quality reasoning processes and achieve superior outcomes.

Our core contribution lies in focusing on the reasoning process in code generation tasks. This perspective was not explored in code generation tasks before OpenAI's o1 model (our work was conducted concurrently with o1). We propose a "rethink" mechanism to refine the thought process involved in generating code. We believe this introduces a new research focus for code generation tasks: emphasizing the thought process behind writing code rather than merely aiming to simply search for the correct codes.

We sincerely thank all the reviewers for their feedback. We hope that our responses address some of your concerns and provide clarity on the contributions of this work. We look forward to your further comments and discussions.

[1] Huang, D., et al. Agentcoder: Multi-agent-based code generation with iterative testing and optimisation. arXiv preprint arXiv:2312.13010.

[2] https://openai.com/index/learning-to-reason-with-llms/
</content>
</thread_object>

</thread>


Metareview:
metareview:
The reviewers agree that this is an interesting topic, but differ in how novel they consider the paper to be. Crucially, however, the reviewers have concerns about the evaluation. This boils down both to how significant the improvement is and how fair the comparison is. The improvement of the new method over the authors' own version of Tree-of-Thought is small and may not be significant (there does not appear to be any statistical significance testing done). The authors point out that the improvements over "original" ToT are larger, and that they first tested against their own, improved ToT. This does not really make things any better for the method that is supposed to be the contribution of the paper - the authors seem to just have invented an unnecessarily strong baseline. Normally, I would not hold this against them, if it wasn't for RethinkMCTS being much more resource-intensive (it uses more tokens). Some reviewers argue that this means that the comparison is not fair. I agree. If there was a convincing performance improvement, I think the additional token usage could be justified, but the lack of convincing improvement over ToT combined with much higher token usage makes the performance less impressive.