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

Thank you for dedicating your time and effort to our work.

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.

We conducted three experiments comparing our method with competitive baselines. The mean and standard deviation of the results are presented below:

Noticeably, our model, RethinkMCTS, consistently demonstrates a stable performance advantage across multiple experiments.

The run time of different algorithms should also be compared.

Here, we present a comparison of the inference time between our method and several major tree search baselines.

Our method indeed requires more time than other baselines. However, it is essential to note that, on average, tree search algorithms take significant time to solve each problem. This is because these methods aim to trade time for improved results, embodying the "slow thinking" approach to reasoning. For instance, OpenAI's o1 model[1] can also take 3-5 minutes to solve a single problem.

[1] https://openai.com/index/learning-to-reason-with-llms/

Dear Reviewer,

Thank you once again for your insightful comments and valuable suggestions.

We hope that our response has adequately addressed your concerns. If you have any further questions or feedback, please don't hesitate to let us know. We are committed to actively engaging with your input and continuously improving our paper.

We look forward to receiving your further comments.

Best regards,

The Authors

In Figure 5(a), as the number of rollouts increases from 43 to 58, the performance with rethink reduces, which is counterintuitive. Could the authors provide an explanation?

1. A key limitation lies in the evaluation stage. While the search algorithm generates multiple candidate codes, only one is ultimately selected for testing based on the pass rate on public test cases. However, the limited number of public test cases can lead to inaccuracies. For example, if multiple codes pass all public tests, one is selected at random, but it’s possible that the chosen code contains errors. As rollouts increase, the likelihood of erroneous codes passing all public test cases also rises. Despite using LLM evaluation as a secondary method, this margin of error remains, so more rollouts do not necessarily improve results.
2. Another possible explanation is that the model has reached its performance ceiling. Further searching may not generate better code, and the observed decline in performance could be due to evaluation inaccuracies rather than actual limitations in the search process.

The numbers in Table 3 are very different from those in Figure 3; is it a different metric, model, or dataset?

The metrics in Figure 3 represent the success rate of the final code generated by the tree search across 100 problems. The values in Table 3 are the proportion of correct codes found within one search tree. Table 3 aims to demonstrate that search trees incorporating the "rethink" mechanism discover more correct codes.

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?

HumanEval is indeed less effective for distinguishing differences in performance with models like GPT-4o-mini due to their already high baseline performance. Thus, our primary comparisons for GPT4o-mini are focused on the three difficulty levels of the APPS dataset.

However, we include HumanEval because it remains a standard benchmark in the code generation field [1, 4] and is effective for highlighting algorithmic differences in models like GPT-3.5, where there is still significant room for improvement.

[1] Shinn, N., et al. Reflexion: Language agents with verbal reinforcement learning. NIPS 2024.

[2] Zhang, S., et al. Planning with large language models for code generation. ICLR 2023.

[3] https://openai.com/index/learning-to-reason-with-llms/

[4] Zhou, A., et al. Language agent tree search unifies reasoning acting and planning in language models. PMLR 2024.

[5] Li, J., et al. CodeTree: Agent-guided Tree Search for Code Generation with Large Language Models. arXiv preprint arXiv:2411.04329.

[6] Huang, J., et al. Large language models cannot self-correct reasoning yet. arXiv preprint arXiv:2310.01798.

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.

1. We chose GPT-3.5 and GPT-4o-mini to compare a stronger reasoning model with a weaker one while keeping experimental costs reasonable. We did not choose smaller open-source models due to their limited reasoning capabilities. Similar to the "slow thinking" approach of OpenAI's o1 model, our enhancement methods aim to improve the reasoning performance of models already possessing some reasoning ability. Thus, a baseline model with sufficient capabilities is necessary, as pointed out in [5].
2. The APPS dataset offers a comprehensive range of problems with a broad difficulty distribution, featuring over 1,000 questions at each difficulty level. However, due to constraints on experimental costs, we initially tested only the first 100 questions at each difficulty level. In response to your concerns about performance comparisons, we have expanded the experimental scope to include 200 questions per difficulty level on GPT-4o-mini, allowing for a more thorough comparison across multiple models.

We can see that the advantage is more obvious when the number of questions rises.

Minor: There is an overloading of the term a.

Thank you very much for your feedback. We have noted the issue you mentioned and will use a different, non-repeating letter to represent the coefficient.

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?

1. Although RethinkMCTS shows more pronounced effects on GPT-3.5, the effectiveness of searching at the thought level, rather than focusing on code or tokens as other methods do, is evident in both base models. This supports our contribution of emphasizing the reasoning process behind the code.
2. As for whether it is more effective on weaker models, if a model has strong inherent reasoning capabilities (like 4o-mini), it may already perform sufficient reasoning when generating responses, making the improvements marginal. However, we do not believe that search methods are suitable for very small, weak models, as forcing them into complex reasoning might lead to incorrect or misleading reasoning and, therefore, might not be appropriate.

In Figure 3, the rethink mechanism seems not much impactful in determining performance. Could the authors clarify how these results were interpreted?

1. Verbal feedback forms the foundation of the "rethink" mechanism. Previous research has demonstrated that LLMs lack the ability to self-correct without external feedback[6]. We introduced the "rethink" mechanism to leverage the rich feedback available in coding environments; thus, verbal feedback may seem more pronounced in ablation.
2. On HumanEval, the model's initial pass rate is relatively high, limiting the opportunities for "rethink" operations since "rethink" is only executed when the initial code generated for the current node is incorrect.
3. Figure 6 in Appendix A further explores ablation on GPT-4o-mini. While the effect of "rethink" on HumanEval is similar to verbal feedback, it has a much greater impact on APPS, where the initial pass rate is lower. This aligns with the findings in Figure 3, suggesting that the limited impact on HumanEval is due to fewer opportunities for "rethink" to be utilized effectively.

[1] Shinn, N., et al. Reflexion: Language agents with verbal reinforcement learning. NIPS 2024.

[2] Zhang, S., et al. Planning with large language models for code generation. ICLR 2023.

[3] https://openai.com/index/learning-to-reason-with-llms/

[4] Zhou, A., et al. Language agent tree search unifies reasoning acting and planning in language models. PMLR 2024.

[5] Li, J., et al. CodeTree: Agent-guided Tree Search for Code Generation with Large Language Models. arXiv preprint arXiv:2411.04329.

[6] Huang, J., et al. Large language models cannot self-correct reasoning yet. arXiv preprint arXiv:2310.01798.

Thank you for dedicating your time and effort to our work.

The pass rate of PG-TD on APPS-Comp is higher.

Table 1 would be clearer to read if the best baselines that are at par with or better than RethinkMCTS were also highlighted.

There should be standard errors in Table 1.

It's our fault that the pass rate of PG-TD at the competition difficulty level was not bolded. We will correct this in the revision. Additionally, we will underline the second-best row in the table in the revised version to improve clarity. (We tried but openreivew's editor does not support underline, so we would not put the underline in the table below.)

Here, we ran each experiment involving GPT-4o-mini from the main table three times. The mean and std are presented below:

We want to point out that in code generation experiments, it is common not to compare std[1, 2] after setting the temperature to 0. The variations in LLM outputs are minimal under his setting.

If the baselines use fewer LLM calls at inference time than RethinkMCTS to generate the final output, this would not be a fair comparison.

First, we want to clarify that the goal of using tree search algorithms to enhance reasoning is to enable LLMs to engage in "slow thinking." Like in OpenAI's o1[3] model, the processing time and token consumption are not the goal of "slow thinking" (o1 could solve a simple problem with thousands of tokens in the hidden CoT and minutes to take [3]).

Our core contribution lies in focusing on the reasoning process in code generation tasks. This perspective had yet to be explored before OpenAI's o1 model (our work was conducted concurrently with o1). We propose a "rethink" mechanism to refine the thought process of writing 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 search for the correct codes simply.

The way to keep a fair comparison in tree search works is to keep the number of codes generated the same [2,4] (i.e., the rollout number in our paper). Regarding the number of LLM calls, RethinkMCTS involves additional calls for "rethink" during each rollout compared to ToT. However, it does not increase the number of LLM calls compared to LATS (MCTS + reflection), as the latter uses extra calls for summarizing reflections, whereas we use them for "rethink." Experiments demonstrate that our "rethink" mechanism is more effective.

[1] Shinn, N., et al. Reflexion: Language agents with verbal reinforcement learning. NIPS 2024.

[2] Zhang, S., et al. Planning with large language models for code generation. ICLR 2023.

[3] https://openai.com/index/learning-to-reason-with-llms/

[4] Zhou, A., et al. Language agent tree search unifies reasoning acting and planning in language models. PMLR 2024.

Dear Reviewer,

Thank you once again for your insightful comments and valuable suggestions.

We hope that our response has adequately addressed your concerns. If you have any further questions or feedback, please don't hesitate to let us know. We are committed to actively engaging with your input and continuously improving our paper.

We look forward to receiving your further comments.

Best regards,

The Authors

Please provide more details about the comparison setting for the number of tokens across different methods.

Our approach ensures the comparison fair by keeping the number of rollouts, i.e., the number of code generated during search, the same. This is following the previous work about tree search in code generation PG-TD[2] and LATS [3]. Here we present the token usage:

RethinkMCTS primarily incurs higher costs on input tokens than other methods. However, for LLMs, the cost associated with input tokens is significantly lower than that of output tokens. For instance, in the case of GPT-4-mini, the cost is $0.15 per million input tokens versus$0.60 per million output tokens.

Our increase in token usage is primarily due to the introduction of block-level analysis, which includes the values of variables before and after each block. These values are obtained through code execution, resulting in longer textual inputs to the LLM. 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[4]), our primary aim is not to optimize token count or computation time. Instead, the emphasis is on enabling LLMs to generate higher-quality reasoning processes and achieve superior reasoning outcomes.

Our core contribution lies in focusing on the reasoning process in code generation tasks. This perspective was not explored before OpenAI's o1 model (our work was conducted concurrently with o1). We propose a "rethink" mechanism to refine the thought process of writing 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 search for the correct codes simply.

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.

In Appendix B.5, we provide an example of verbal feedback, which includes a sample of block-level analysis. The concept of block-level analysis is inspired by prior work [5]. The basic principle involves transforming the code into a control flow graph. When a failed test case is input, it generates the execution trace corresponding to that failed test case, along with the variable values before and after each node on the trace. Each node in the trace represents a block, and by analyzing the changes in variable values before and after the execution of each block, we can assess the correctness of each block.

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

[2] Zhang, S., et al. Planning with large language models for code generation. ICLR 2023.

[3] Zhou, A., et al. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.04406.

[4] https://openai.com/index/learning-to-reason-with-llms/

[5] Zhong, L.,et al. Ldb: A large language model debugger via verifying runtime execution step-by-step. ACL 2024.

Thank you for dedicating your time and effort to our work.

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?

Here, we would like to clarify the difference between RethinkMCTS, LATS, and ToT.

1. Difference from LATS: LATS combines tree search with reflection. As illustrated in Figure 1 of our paper, the rethink mechanism differs fundamentally from reflection. Reflection summarizes past errors into textual feedback, which is then appended to the state of subsequent nodes. In contrast, our rethink mechanism directly corrects erroneous nodes. This approach offers a significant advantage over reflection by removing incorrect nodes from the tree expansion process, enabling the search to follow higher-quality traces. As shown in Figure 5, our experiments confirm that as the number of rollouts increases (i.e., the tree expands further), the rethink mechanism effectively enhances search quality.
2. Difference from ToT: 1)The ToT tree search lacks feedback and refinement mechanisms, while our rethink mechanism significantly improves search quality by addressing these limitations. 2) Regarding the exploration of "thoughts": Although the ToT paper's title suggests a focus on searching "thoughts," its actual method involves decomposing tasks into steps and performing searches within each step. We adapted ToT's search to align with the code reasoning search approach used in RethinkMCTS, which resulted in strong performance. In another study of code generation AgentCoder[1], ToT performed poorly because the authors do not adopt ToT to code as we do.

Why RethinkMCTS is not simply a combination of LATS and ToT: 1) The rethink mechanism is unique for both ToT and LATS. 2) Neither approach utilizes fine-grained block-level feedback to enhance tree search. 3) Our dual-evaluation method, which combines public test case evaluation with LLM-based scoring, is absent in either of these prior works.

The improvements over baselines, especially ToT, are small.

About ToT baseline implementation. Here, we would like to address some details about the ToT baseline:

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 Tree of Thought and adapt a task-decomposition version of ToT as ToT(Ori); we show the results below:

It is clear that 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 significantly when adapted to our code reasoning-based version of ToT (as the version in our paper). This highlights the effectiveness and contribution of our work in exploring the reasoning process behind code generation.

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

Dear Reviewer,

Thank you once again for your insightful comments and valuable suggestions.

We hope that our response has adequately addressed your concerns. If you have any further questions or feedback, please don't hesitate to let us know. We are committed to actively engaging with your input and continuously improving our paper.

We look forward to receiving your further comments.

Best regards,

The Authors

Minor points: Add average pass rate/pass@1 for APPS; PG-TD has 43.16 for APPS Comp. with 4o-mini but RethinkMCTS's 42.50 was bold instead.

Thank you for your suggestion. Here we present the average performance of several competitive methods. And we will add these columns in the final version.

For the PG-TD's 43.16, it should be bold and we would fix it at the revision.

Thank you for dedicating your time and effort to our work.

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''.

The primary contribution of our work is indeed the "rethink" mechanism. One of the motivations we propose "rethink" is effectively leveraging the execution feedback from code environment. Empirically, the experiments have confirmed the effectiveness of verbal feedback in enhancing the performance of RethinkMCTS.

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.

We present the results for the base model rollout 16 here.

The pass@ 1 metric is obtained by using tree search to identify one and only one code solution, which is then tested on private test cases. The term "base model" refers to the outcome when the model independently performs simple reasoning and submits one code. To ensure a fair comparison, we followed the same evaluation approach commonly used in other tree search works [1, 2], which are usually compared directly with the base model.

About ToT baseline implementation.

A comprehensive ablation should be conducted versus ToT: Rethink only without feedback.

We would like to 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[3], 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 ToT and adapt a task-decomposition version as ToT(Ori).

We also add RethinkOnly experiments and present the results:

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 significantly when adapted to our reasoning-based version of ToT (as the version in our paper). This highlights the effectiveness and contribution of our work in exploring the reasoning process behind code generation.

[1] Zhang, S., et al. Planning with large language models for code generation. ICLR 2023.

[2] Zhou, A., et al. Language agent tree search unifies reasoning acting and planning in language models. PMLR 2024.

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

Dear Reviewer,

Thank you once again for your insightful comments and valuable suggestions.

We hope that our response has adequately addressed your concerns. If you have any further questions or feedback, please don't hesitate to let us know. We are committed to actively engaging with your input and continuously improving our paper.

We look forward to receiving your further comments.

Best regards,

The Authors