Thank you for your review. We are glad you found the paper clear, well-motivated, and appreciated the progression of ideas and experimental results. Below, we hope to address your concerns.

o1-mini

Although the method shows promising results with models including Claude 3.5 sonnet and GPT-4o, etc., the improvement over o1-mini is marginal. Does this suggest the method is not compatible with other inference-time scaling compute?

Thank you for your observation. Our Appendix K describes our perspective on this observation, which we expand on here. Indeed, the gains on the test split of LiveCodeBench with o1-mini are somewhat marginal, but we believe this is in line with the main claims of our paper. The reasons are threefold:

• Firstly, our algorithm was not explicitly designed for search on top of existing search algorithms, and we conducted almost all our experiments before models such as o1 were announced. The purpose of our paper is mainly to show that using inference-time compute on top of standard post-trained models can be extremely effective, by adding much needed model diversity.
• o1-mini is already nearly saturated on LiveCodeBench. The pass@200 of o1-mini with naive repeated sampling is already hovering close to 0.9. Any additional method on top of an already-saturated method will likely show limited absolute improvements compared to unsaturated tasks. For example, we see analogous patterns when applying PlanSearch on models like GPT-4o on HumanEval+, which is notably saturated. In Figure 6 (top-right), PlanSearch on GPT-4o marginally improves over IdeaSearch and Repeated Sampling. However, on harder, unsaturated datasets such as LiveCodeBench (for non-o1 models), the pass@k of Repeated Sampling and PlanSearch clearly diverges again as k becomes large. Thus, with an even harder, unsaturated task, PlanSearch with o1-mini may exhibit large differences as well.
• Lastly, as seen in Figure 5, o1-mini is noticeably less diverse than all other models. (This may be due to the specific post-training algorithms o1-mini was trained with, referring back to the conversation with Reviewer 2 on lack of diversity in common post-training algorithms, or may be due to saturation on the dataset.) No matter the reason for this lack of diversity, it is true (as seen in all our diversity plots) that idea diversity is strongly correlated with relative gains from search. This correlation implies that models with lower diversity are predicted to exhibit less significant pass@k boosts, even with PlanSearch.

MCTS and Other Methods

While the proposed method shows promising improvement compared to naive sampling and Pass@1, how does it compare to another search-based method, like MCTS?

As far as we know, there is no well-established MCTS baseline for competitive coding and there are several reasons for this. Doing MCTS over token space would likely have nodes representing the current code prefix, with each step adding a new code token to the end of the prefix, and exploring only promising code prefixes through some value function. If the value function is some reasonable function of the LLM logprobs, this whole algorithm could be thought of as a sophisticated LLM sampling algorithm. The effect of this would only be to filter some generated code outputs from Repeated Sampling, which would not get rid of the inherent diversity problem in Repeated Sampling and may possibly even lose diversity given emphasis of the shared code prefixes.

However, suppose the MCTS is run instead on idea space. Viewing this algorithm at a high level, we see that the algorithm may be regarded as a derivative of PlanSearch, instantiated as a filtered tree search over ideas. Instead of going through all the brute-force combinations and rolling out every branch, an MCTS-like algorithm would filter the most promising branches to go down. We consider this to be an exciting future direction for improving PlanSearch and describe this and other variations in the Limitations section of our paper.

For other baselines, we show comparisons with an agentic model in our response above to Reviewer 2. We hope these responses address your questions and provide clarity on the points you raised. Thank you again for your thoughtful feedback, and we welcome any further discussion.

Note: we added one appendix (Appendix V) at the end of the paper addressing agent baselines. The rest of the paper is identical. We plan to address the sentence-level changes in our next revision.

We thank you for your detailed response, especially for your critical questions. We hope to address all your points below. We answer questions in a different order for clarity, flow, and better understanding of the underlying philosophy of our paper.

Test-time Compute

I don't think it's that surprising or impressive that burning more test-time compute [1, 2, 3] leads to better results. A fair comparison would involve, e.g. a scatter plot of pass@200 on X axis and compute spent on Y axis. Compute spent can be operationalized as either tokens or dollars spent (ideally you'd report both). Then, the question is: is your method strictly optimal? Is it Pareto-optimal? See [1, 2, 3] for a discussion.

Thank you for the insightful comment. This is a common idea that is brought up upon reading our paper. First, we do report compute-normalized results in our paper as seen in Figure 17, which shows a large margin between PlanSearch and Repeated Sampling at medium-to-high tokens spent. While PlanSearch is indeed more expensive in terms of computation per sample generated, it outperforms baselines even when this is taken into account.

This suggests perhaps a more interesting question which is the primary focus of the paper. If you can only evaluate k times, how would you optimize your chances of having a successful evaluation (with tractable compute)?

This question is not simple to answer, and requires more thought beyond algorithms that optimize “given X amount of compute.” In most real-world cases, evaluation is often the bottleneck over the precise amount of compute spent. Thus, in many applications (including this paper, where most of the compute time was actually spent running the generated codes), the amount of LLM inference used is not the main structural bottleneck.

By focusing on this question, we realize an interesting result; naive inference-time compute strategies hit diminishing returns rather quickly; if you want to push more compute into the strategy, the rate of pass@k increase (i.e., increase of pass@k per unit increase of compute) diminishes rather quickly as you scale inference-time compute.

So, if you want to spend more inference-time compute (which is common in applications today given how efficient LLM inference is), feeding the extra compute into current algorithms will only give you slight performance boosts, no matter how much extra compute you have. Our method makes it such that you can push in much more compute without plateauing performance than you otherwise would have been able to.

Therefore, if you only have enough compute to generate two or three solutions, naive sampling works well. However, existing algorithms do not scale well, and so if your inference-time compute budget reaches on the order of 5 to 10 solutions or more, these algorithms will begin to plateau while PlanSearch will still generate significant improvements, as seen in Figure 13 (although all result figures also show this).

Agentic Baselines

The authors do not compare with several important baselines, e.g. iterative methods such as ReAct, Reflexion and agentic approaches (e.g. AgentCoder). I thinks that a bit weakness: there are relatively simple methods and scale well to more complex tasks (e.g. SWE-Bench).

Thank you for the criticism.

Following your advice, we ran a new baseline ‘agentic’ model which generates code, runs the code on public tests, and then iterates. If there was an error in the public tests, the error is returned to the LLM, as well as the buggy code for fixing. We do wish to note that these agentic models operate in a different paradigm compared to our standard baselines, since the agentic models are given both 1) the exact public test cases in code and 2) liberal usage of code execution, both of which are extremely powerful (see Appendix R and all public test filtering figures), but a model may not have access to these in other tasks.

We draw two comparisons here. In variant 1, the agentic model stops iterating if the code is successful or if the number of iterations exceeds $T=10$. Only the last code returned (either successful or exceeding iteration limit) is finally submitted to the judging environment and counted for pass@k. We compare variant 1 with PlanSearch with public test filtering, since in both methods, all the faulty submissions which do not pass public tests are discarded unless there are none that pass public tests.

In variant 2, the agentic model continues iterating even if the code is successful. If the code is successful and uses $i$ iterations out of $T$, the agentic model starts over from scratch, except with $T-i$ total iterations instead. In this case, we submit all codes generated by the model to be counted for pass@k. We compare variant 2 with default PlanSearch, since for both methods, submissions are not guaranteed to pass public tests. This is still slightly unfair to PlanSearch baselines, since the last submissions of the agentic model will have already iterated and extracted sufficient signal from public test execution, whereas PlanSearch does not use any test execution signal at all.

These plots can be found in the new Appendix V. Figure 42 corresponds to variant 1, and Figure 43 corresponds to variant 2.

As seen in the plots for variant 1, the agentic model after 10 steps outperforms naive Repeated Sampling (with no public test filtering) by a margin of 0.05 as expected at pass@1. However, the pass@1 of the agentic model is not comparable to Repeated Sampling with public filtering.

PlanSearch with public filtering, in both GPT-4o-mini and GPT-4o, is strictly better than the agentic model at all k with large margins (between $0.1$ and $0.2$). Even without public filtering, basic PlanSearch still beats variant 1 past k=3, even though basic PlanSearch has zero environment interaction.

Shifting our analysis to variant 2 plots, we find similar results. As expected, without the filtering the generations of the agentic model by returning only the last generation, the agentic model roughly tracks naive Repeated Sampling, performing marginally better at large k. However, PlanSearch still outperforms with a significant margin past k on the order of 2 to 3.

Abstract Revision

I think the opening sentence of the abstract is false as of November 2024: "While scaling training compute has led to remarkable improvements in large language models (LLMs), scaling inference compute has not yet yielded analogous gains". See again [1, 2, 3].

We appreciate your comment and attentiveness. Due to recent events, this abstract is now likely indeed out of date. We plan on editing the sentence to say: “While scaling training compute has led to remarkable improvements in large language models (LLMs), scaling inference compute only very recently began to yield analogous gains…”

RL/DPO Comment

I don't understand this sentence: "LLMs as chatbots, in which models are oftentimes optimized to produce a single correct answer (Rafailov et al., 2024; Ouyang et al., 2022)." RL optimizes for reward (which could be correctness) and DPO optimizes a contrastive loss (e..g. preferring correct responses over incorrect ones). Neither optimizes for a single correct answer. This could be the case for supervised fine-tuning though.

We are happy to rephrase this section in the next revision. Our point was merely to convey that RL post-training methods do not place very much emphasis on generating a diverse set of correct answers. This is because a single correct answer with high reward would satisfy the RL constraint of maximizing reward. DPO is slightly better in this regard in that all correct responses are incentivized by the contrastive loss to rank correct answers higher than incorrect answers, but appears that it reduces diversity similarly to RL [1]. In any case, we will rephrase the above to be more clear.

Again, we thank you for your detailed review. We hope to have addressed your concerns, but please do let us know if you have any remaining questions.

[1] One fish, two fish, but not the whole sea: Alignment reduces language models’ conceptual diversity

We appreciate the detailed feedback and kind review.

PlanSearch Design

Regarding the design of PlanSearch, we explore several ablations on the design of PlanSearch in Appendix H. Despite this, we agree with the reviewer that there are likely even more optimal ways of eliciting diversity and exploration besides the concrete implementation of PlanSearch.

For example, when developing PlanSearch, we considered using previous ideas in sequence and prompting an LLM to produce ‘different’ generations. In fact, in Section 4.3.3, our algorithm supposes a generated idea is incorrect—adding another set of generations—which does indeed increase our pass@k by roughly 3 percent. However, as you scale up, you will need to either keep all past generations within the context length (and thus the LLM has a harder time to generate truly different ideas) or truncate at some point, which runs the risk of repeating. Therefore, we were unable to scale the technique suggested beyond the order of 5 or 10 generations. In addition, such sequential generations are slightly less efficient due to lack of batching.

IdeaSearch vs CoT

Regarding the source of differences between IdeaSearch and CoT. Indeed, the main difference between IdeaSearch and CoT is that IdeaSearch splits the idea and implementation into two model responses (ignoring subtle prompt differences). We believe that having a new message is surprisingly significant. One possible explanation for this phenomenon is that IdeaSearch allows the LLM to better follow the solution sketch. In the limit case, the prompt could be structured as “XYZ idea is guaranteed to be correct…” Whereas in CoT, the model is implicitly trained to follow its own chain-of-thought, but is not as bound to the chain-of-thought as IdeaSearch. Note that this is one possible explanation; further conclusions would be speculation, and we leave investigation of this interesting phenomenon to future work.

We thank you again for your feedback and insightful questions. We hope our responses clarify the points raised and look forward to any further discussions.