Planning in Natural Language Improves LLM Search for Code Generation
Authors: Evan Z Wang
Federico Cassano
Catherine Wu
Yunfeng Bai
William Song
Vaskar Nath
Ziwen Han
Sean M. Hendryx
Summer Yue
Hugh Zhang
Venue: ICLR 2025 Spotlight (2025)
Keywords: LLM
search
inference-time compute
competitive programming
reasoning
code generation
pass@k
diversity
Primary area: foundation or frontier models, including LLMs
TL;DR: Searching over high level plans in natural language rather than directly over code induces diversity in generated outputs, which drastically increases effectiveness of inference-time compute.

Abstract: While scaling training compute has led to remarkable improvements in large language models (LLMs), scaling inference compute only recently began to yield analogous gains. We hypothesize that a core missing component is a lack of diverse LLM outputs, leading to inefficient search due to models repeatedly sampling highly similar, yet incorrect generations. We empirically demonstrate that this lack of diversity can be mitigated by searching over candidate plans for solving a problem in natural language. Based on this insight, we propose PlanSearch, a novel search algorithm which shows strong results across HumanEval+, MBPP+, and LiveCodeBench (a contamination-free benchmark for competitive coding). PlanSearch generates a diverse set of observations about the problem and uses these observations to construct plans for solving the problem. By searching over plans in natural language rather than directly over code solutions, PlanSearch explores a significantly more diverse range of potential solutions compared to baseline search methods. Using PlanSearch on top of Claude 3.5 Sonnet achieves a pass@200 of 77.0% on LiveCodeBench, outperforming both the best pass-rate achieved without any search (pass@1 = 41.4%) and using standard repeated sampling on top of existing non-search models (pass@200 = 60.6%). Finally, we show that, across all models, search algorithms, and benchmarks analyzed, we can accurately predict performance gains from search as a function of the diversity over generated ideas.

Published as a conference paper at ICLR 2025
PLANNING IN NATURAL LANGUAGE IMPROVES LLM SEARCH FOR CODE GENERATION
Evan Wang! 2
Federico Cassano 3,4
Catherine Wut
Yunfeng Bai'
William Song!
Vaskar Nath Ziwen Han'
Sean Hendryx Summer Yue-
Hugh Zhang'
Scale AI California Institute of Technology 3 Anysphere
"Northeastern University Anthropie, work done while Scale AI
Correspondence to ezwang@caltechh edu and hugh. zhang@scale.com
ABSTRACT
While scaling training compute has led to remarkable improvements in large language models (LLMs), scaling inference compute only recently began to yield analogous gains. We hypothesize that core missing component a lack of diverse LLM outputs, leading to inefficient search due to models repeatedly sampling highly similar, yet incorrect generations. We empirically demonstrate that this lack of diversity can be mitigated by searching over candidate plans for solving problem in natural language. Based on this insight, we propose PLANSEARCII, a novel search algorithm which shows strong results across HumanEval+, MBPP+ and LiveCodeBench (a contamination free benchmark for competitive coding). PLANSEARCH generates diverse set of observations about the problem and uses these observations to construct plans for solving the problem. By searching over plans in natural language rather than directly explores a significantly more diverse range of potential solutions compared to baseline search methods. Using PLANSEARCII on top of Claude 3.5 Sonnet achieves pass @ 200 of 77.0% on LinchodeBench, outperforming both the best pass-rate achieved without any search (pass@1 I 41.4%) and using standard repeated sampling on top of existing non-search models (pass @200 = 60.6%) Finally, we show that, across all models, search algorithms, and benchmarks analyzed, we can accurately predict performance gains from search function the diversity over generated ideas.
code solutions, PLANSEARCH
INTRODUCTION
The bitter lesson (Sutton 2019) famously posits that two forms of scaling trump everything else:
learning and search. While recent advances in large language models (LLMs) have shown that
learning is extremely effective, search has not yet proven its value for LLMs, despite its success with
classical machine learning techniques (Campbell et al. 2002 Silver al. 2016 2017
Brown &
Sandholm 2018 2019
Bakhtin et al. 2022 FAIR et al.
2022
Here, refer search as any method of spending compute inference time improve overall performance (McLaughlin) 2024). In this work, we focus our efforts on improving LLM search for code generation, one of the most important current applications bottleneck preventing widespread use of search at inference time for code is lack of high-level objectives diversity in model outputs. This lack of diversity may arise since common favoring one correct typically do not emphasize generating diverse set of correct answers, implicitly answer (Rafailov et al. 2024 Ouyang et al.) 2022). We empirically demonstrate that this the case for many open-source language models which have undergone significant post-training. Specifically, we show that in many cases, despite instruction tuned models outperforming base models by large margins single sample regime (pass @ 1), this trend disappears sometimes even reversing a multi- sampl regime (pass@k). We refer to Figure 30 as an example of this phenomenon.
LLMs. We hypothesize the major
Furthermore, the lack of diversity is particularly harmful for search algorithms. In the most egregious of cases with little to no diversity, such as greedy decoding, repeated sampling from the model returns highly similar programs, resulting in minimal gain from additional inference-time compute. This

---

Published as a conference paper at ICLR 2025
Pass@k Scores by Method on LiveCodeBench
0.8
0,770
0.730
0.649
0.606
0.6
0.556
0.533
Pass
0.4
0.390
0.413
0.414
9.493
0.2
Repeated Sampling@1
Repeated Sampling@200
PlanSearch@200
0.0
GPT-4o-mini
GPT-40
DeepSeek Codera22
Sonnet-335 3.5
Figure I: Comparison of REPEATED SAMPLING, both pass @ and pass@k, and our novel method PLANSEARCH. On every model, our method outperforms baselines by a wide margin, with the best model- combination of Claude 3.5 Sonnet PLANSEARCH achieving performance nearly double that of the best model without search.
diversity problem is also not reflected in many public leaderboards (e.g. LMSYS Chatbot Arena (Chiang al. 2024). LiveCodeBench (Jain et al. 2024). OpenLLMLcaddrboaad (Aidar Myrzakhan 2024)), which often report only the pass rate from a single sample of the model, ignoring an entire dimension along which to compare models. While the performance of one sample is the primary metric of relevance for applications such as chatbots, as users typically are sensitive to latency, this single scalar is insufficient to fully capture the quality of a model when it allowed to use more inference-time compute.
In this paper, we explore several directions for improving the diversity of LLMs at inference time. We hypothesize that the right axis of diversity to search over is the natural language conceptual/idea space, and we validate our hypothesis across several experiments. First, we show that models can produce the correct final program when fed correct solution sketches, where these sketches have been "backtranslated" from passing solution code into sketches in idea space (Section 3.2). Second, we show that when models are asked to generate their own ideas before implementing them LiveCodeBench (IDEASEARCE)
their accuracy conditioned on a particular sketch trends towards either 0% or 100%, suggesting that most of the variance in passing a particular problem is captured by whether the sketch is correct rather than any other factor. These two experiments suggest a natural method to improving LLM search for code generation: by searching for the correct idea implement.
Guided by this principle of maximizing exploration of ideas, we propose PLANSEARCIL In contrast
many existing search methods that search over individual tokens (Zhang al. 2024 2023), lines
of code (Kulal et al., 2019), even entire programs (Li et al. 2022), PLANSEARCH searches over possible plans for ving the problem at hand, where plan is defined as a collection of high level observations and sketches helpful to solve a particular problem (Figure Zp. To generate novel plans, PLANSEARCH generates a number of observations about the problem, before combining these observations into candidate plan for solving the problem. This is done for every possible subset of the generated observations to maximally encourage exploration in idea space, before the codes eventually all translated into final code solution (Section 4.3). We find that searching over plans outperforms both standard repeated sampling and directly searching over ideas (IDEASEARCH, introduced in Section 4.2) in terms of effectively using compute at inference time.
Applying PLANSEARCH on top of Claude 3.5 Sonnet achieves a pass@ 200 of 77.0% on Live- CodeBench, outperforming both the best score achieved without search (pass @ 1 41. 41.4%) and
2

---

Published as a conference paper at ICLR 2025
Stage 1: Generate diverse observations
Stage Implement code from observations
observallons
First-order obsenvations
Mostions for eech
subcequence
Uso hashmaps
Strategy Descrition
the arroy ampty
Psoudecaad
Codo
Coding Problem
VUee greedy deerch"
Prompt new solutions with "Your idea is wrong"
Tidentity the longest subsequence"
Strategy Description
"Use bintrry Sparch"
Pscudocado
Codo
"uuchel each emay inlo ofroot
An example trajectory of PLANSEARCH, which searches over plans in natural language as a method of increasing diversity in the search process. PLANSEARCH first generates observations, then combinatorially samples subsets of these observations to generate the next step in the search process. To generate the next layer of observations, the combinations derived from the first observations used as a stepping stone to generate the next observations, and the process repeats. After generating both the first and second order observations, PLANSEARCH then generates natural language description of strategy to solve the problem. For additional diversity, the model is prompted to regenerate its strategy as an additional sample before generating code. See Section for additional discussion.
Figure 2:
the standard best-of-n sampling score on non-search methods (pass ppass@2000 200 60.6%) Furthermore, consistent with recent findings on the effectiveness of search on top of small models (Chen et al. 2024, Brown et al. 2024; Bansal et al.) 2024 Wu et al., 2024), running PLANSEARCH on top of small model (GP1-44-mmm) outperforms larger models not augmented with search after merely 4 attempts. Evaluations of PLANSEARCH across two other coding benchmarks, HumanEval+ and MBPP+ (Liu et al. 2023), suggest similar improvements.
Finally, we measure the diversity of output code over the idea space of all search methods via an L.LM-as-ajjudge procedure (Section 6.1 and show that the resulting diversity score is highly correlated with the performance gains generated by that search method. This provides further support for our hypothesis that the effective exploration of plans in idea space is key LLM search for code generation (Figure
2 RELATED WORK
We reiterate that search as defined in the context of our paper refers any method which expends inference-time compute to improve performance. We further specify planning as any form of high level observation or abstract thought that assists model in generating final solution. Our work builds off a long history of work in scaling search and planning. For information on relevant work in classical AI, general search, and filtering, see Appendix
Regarding searching over plans in natural language, several approaches have proposed generalizing ch thhtuughtt (Wei al. (022) reasoning into a search-like process, such Tree of Thoughts (Yao et al. (2023a) and Reasoning via Planning (Hao et al. (2033)) However, prior methods have largely demonstrated effectiveness on somewhat contrived problems designed to highlight the power of search, such the game of 24, classic planning benchmarks such as Blocksworld (McDermott) 2000), where both benchmarks are easier to solve by explicitly considering many options, and where the 'steps' over which to search over fairly obvious. By contrast, most real-world planning is used to assist in domains that are complex enough to benefit from, but not require, the additional exploration of plans. We demonstrate that PLANSEARCH, which plans in natural language, outperforms baseline
3

---

Published as a conference paper at ICLR 2025
search methods in one such domain: code generation. Moreover, our analysis reveals the underlying reason that such search is effective: it increases the diversity of the generated ideas, allowing more efficient search relative to other methods which repeatedly submit highly similar, incorrect solutions. This is consistent with prior work suggesting the importance of diversity in natural language generation (Hashimoto et al., 2019 Zhang al. 2021). Other directions for search include decomposing programs down into smaller parts before solving each one individually (Zelikman et al.
2023 Zhou al. 2023 Gao al. (023).
PLANSEARCI is also distinct from other methods which explicitly train a model to search or on reasoning traces sampled from the model (Zelikman et al., 2022 Zhang Parkes 2023 Zelikman ct al. 2024; OpenAl, (024) (002) in that PLANSEARCH induces diversity at inference- time and converts an L.MM API not designed for search into one that is capable of showing strong gains from search. Separately, there is a large family of work in the agent space, in which outputs from terminal commands or other tools are fed back into the model before the agent is queried for the next step
(Shinn et al. 2023 Yao et al. 2023b Schick et al. 2023 Chen al. 2022b).
3 MOTIVATION
Coding is a powerful area in which search should excel. While search in other domains requires both generating many solutions and selecting the correct solution amongst all the resulting generations, coding often only requires the former, as any valid piece of code can be tested via code execution against given test cases. This allows code search algorithms sidestep many of the issues that plague search algorithms for more open-ended domains (e.g. generating poetry) due to difficulty in selecting correct solutions out of all the generated solutions.
Effects Bacitrandictton on Performance
Distribution Salve Rates Conditioned on Idea
1.91
Passja
0.55
Froblem
3.5
Baneline Pamsg)
Pasags
3.90
Buselinc P
4.6%
0.99
0.5
345
Arerage Solution Iokonn Length
Solve
(a) Performance of GPT-4o-mini LiveCodeBencc when provided with backtranslated solutions vary- ing lengths. The baselines plot performance without backtranslated solutions. Providing the model with compressed solution in natural language, even short as 10 tokens, significantly increases performance.
(b) We plot the distribution of solve rates conditioned on being given a solution sketch and without. When conditioning on a given sketch, we notice that down- stream solve rates polarize towards either 0% or 100%. Most of the variance in performance is predicted by whether given idea is correct or not.
Figure 3: Backtranslation shows the promise of providing good sketches, and conditioning on idea shows the presence solution sketch polarizes performance.
3.1 DEFINING THE SEARCH SPACE
Perhaps the most important question for eliciting strong search capacities is determining which space to search over, as finding the proper layer of abstraction is critical to progress the field. Prior approaches have varied, with many people searching over individual tokens (Zhang et al., 2024 2023), lines of code (Kulal et al. 2011)) or even entire programs (Li et al. 2022). We hypothesize that the key factor is obtaining the correct solution sketch, which we define as a description of the correct program in natural language space. Intuitively, conducting the reasoning process in natural language space allows us to effectively harness the training process of LLMs, which have observed many human reasoning traces in both pre- and post-training. Prior work (Wei et al. 2022) has observed strong positive effects from being allowed to conduct such reasoning natural language, making it natural place to search over. We describe two experiments providing evidence for this hypothesis by testing on the LincCodeBench benchmark using GPT-4o-mini as our model.
4

---

Published as a conference paper at ICLR 2025
3.2 BACKTRANSLATION
To investigate the hypothesis whether the idea space, instantiated as solution sketches, is the right area of exploration, a natural question is whether L.LMs can correctly implement a correct code solution given correct sketch. Inspired by approaches to backtranslation in machine learning (Sennrich) jet al. 2016) Pham et al. | 2021 Edunov et al. 2018), we experiment with "backtranslating" passing code solutions back into idea space. First, generate code solutions using GPT-4o to generate 1000 attempts to solve the problem and filter out problems without any passing solutions. As we also do not have dataset of correct solution sketches associated with each solution, generate a candidate correct idea via backtranslation. We do this by feeding an LLM both the problem and code solution and asking the LLM convert said solution into natural language description of the solution. Additionally, we vary the detail of the backtranslated idea via instructions to the LLM in the prompt (e.g. 'in words'). A full description of the prompts can be found in Appendix M. alongside several example backtranslated solutions of various lengths.
We observe that prompting model with backtranslated idea significantly improves accuracy, increasing with the length of the translated idea (Figure Ba). which suggests that having a correct sketch is sufficient to produce the correct final solution with relatively high accuracy, even only after 10 tokens of backtranslated solution. This suggests that the correct direction of search is to explore through idea space to maximize the chance of arriving at a correct idea.
3.3 CONDITIONING ON IDEA QUALITY
In follow-up experiment, we prompt an LLM to generate its own sketches to solve LiveCodeBench problems instead of providing with golden ones via backtranslation. First, we generate ideas per problem using IDEASEARCH, defined in Section 4.2, For each idea, we then sample 25 candidate solutions and measure their pass rate. For this experiment, we filter out any problem that GPT-4o-mini solves with either 100% or a 0% solve rate, since such problems are either too easy or too hard for the model and would not informative for this experiment. We end with 75 problems and 375 sketches
To test our hypothesis that generating a correct sketch is critical factor for solving problems, we compare the distribution of solve rates for generating correct code solutions conditioned on given sketch to the distribution over solve rates given a sketch drawn at random, i.c., just the distribution over solve rates. While verifying whether a sketch is correct or incorrect is difficult without access to external labels, a key insight is that if generating the correct idea is a critical factor solving the problem, then conditioning on a particular sketch should polarize the distribution of solve rates towards {0, }.. If the model is given a correct sketch, it should consistently generate correct solutions, while if given bad sketch, it should consistently generate incorrect solutions.
Our results confirm this to be the case. Figure 3b shows the distribution of solve rates across problems, both unconditionally (in red) and conditioned on each sketch (in blue). We notice that when grouping by sketches, the solve rates indeed become polarized towards {0, This result has important implications for improving code generation, suggesting that large portion of variance in performance can be explained by whether the model is able to generate a correct idea or not. Therefore, a natural path for improvement to focus on the sketch generation step and search for correct sketches and observations in idea space before generating solution code.
METHODS
We provide a description of the various methods of search we explore our work. If additional background on competitive programming and related notation is desired, we provide more (optional) information in Appendix P
4.1 REPEATED SAMPLING
We consider the basic prompting approach as baseline, in which few-shot prompting by providing the LLM with a number of problem-solutine pairs before asking it to solve the desired question (Brown al. 2020). A full example of the prompt is given in Appendix M.2 In code
5

---

Published as a conference paper at ICLR 2025
generation, the most common variant of search utilized is repeated sampling, where models repeatedly sampled from until they generate an output that passes the test or the maximum number of samples is reached. Refer to the Related Work for more information (Section Q.2).
4.2 IDEASEARCH
A natural extension of the REPEATED SAMPLING approach discussed in Section 4.1 is to avoid prompting the LLM for the solution code immediately. This can be viewed as an application of the commonly used "chain-of-thooghh prompting to programming problems (Wei et al. 2022). although we find that IdeaSearch shows non-negligible performance boosts over standard "chain-of-thought" prompting (see Appendix E
In DEACHI, the LLM is given the problem P and is asked to output a natural language solution S of the problem. Then, a separate instance of the LLM is given P and S, and tasked to follow the proposed solution S to solve the problem P. The purpose of IDEASEARCH is to isolate the effectiveness of having the correct "idea/sketch" for solving the problem. Empirically, we find that explicitly forcing the search algorithm to articulate an idea for solving the problem increases diversity, See Appendix M.3 for detailed prompts.
4.3 PLANSEARCH
While both REPEATED SAMPLING and IDEASEARCH are successful and lead to improvement in the results on benchmark results, we observe that many of the cases, prompting multiple times (pass@k) (even at high temperatures) will only lead small, narrow changes in the output code that change minor aspects but fail to improve upon pitfalls in idea.
Ablations for many of the choices in the subsequent description of PLANSEARCI can be found in Appendix
4.3.1 PROMPTING FOR OBSERVATIONS
Starting from the problem statement P, we prompt an L.M for "observations" //hnnts to the problem.
We denote these observations as O where, i E (1, (1.....7) m1) observations. Typically, n1 is on the order of to 6. The exact number depends on the LLM output. To use these observations to inspire future idea generation, we create all subsets with size at most = 2² = { Oh,} Each of these subsets is a combination of observations, and for clarity we denote each subset as C. E (1, where 1 = 1 + m + (x)
due to the fact that they are first-order
4.3.2 DERIVING NEW OBSERVATIONS
The set of all observations can be thus defined as a directed tree with depth 1, where the root node is P, and edge exists for each C! pointing from P C... We then repeat this procedure from Section 1 on each leaf node C to generate a set of second order observations, sf ( O J. To obtain second order observations, problem P and all observations contained in C,,, framed as primitive observations that are necessary in order to solve P. The LLM is then prompted to use/merge the observations found in C/ in order to derive new ones.
prompt the model with both the original
The same procedure as Section 4.3.1 is used create all subsets C7,5 for all i f1....,47 4..,, This process may be arbitrarily repeated, but we truncate the tree at depth = 2 for computational constraints.
Note that there is no assumption any of the observations generated are correct. In fact, it is critical to note that many of them may be incorrect. The observations merely serve elicit the model search over a more diverse set of ideas.
4.3.3 OBSERVATIONS TO CODE
After the observations have been made, they must implemented as ideas before being translated into code. For each leaf node, prompt the model with all observations, along with the original

---

Published as a conference paper at ICLR 2025
problem P, in order to generate natural language solution to the problem P. To add more diversity, for each generated idea, we generate an additional idea by supposing the idea is wrong, and asking an LLM to give criticisms/feedbacck thus increasing proposed ideas by factor of 2.
These natural language solutions are then translated into pseudocode, which are subsequently trans- granular approach to reduce the translation error (which
lated into actual Python code. We take may cause the model to revert to its original mode, disregarding the reasoned-througe observations). We provide all prompts for all sections in Appendix M.4
EXPERIMENTAL RESULTS
Model
Eval
Pass @
Pass@200
IS@ 200 (ours)
PS@ 200 (ours)
GPT-4o-mini
LCB
39.0
53.3
59.4
64.9
GPT-4o
LCB
41.3
60.6
70.4
73.0
DeepSeck-Coder-No
LCB
41.4
53.2
65.9
70.3
Claude-Sonnet-3.
LCB
40.3
55.6
70.2
77.0
GPT-4o-mini
HE+
83.7
95.0
97.5
98.2
GPT-4o
HE+
86.4
98.2
97.6
99.5
DeepSeek-Coder--2
HE+
82.8
91.4
97.2
99.3
Claude-Sonnet-3.5
HE+
81.6
88.9
95.6
98.5
GPT-44-mini
M+
73.5
83.8
87.3
91.0
GPT-4o
M+
77.2
87.4
89.3
92.2
DeepSeek- -oobeekk--odrrV22 V2
M+
76.3
81.9
89.1
92.6
Claude-Somnet-3.5
M+
77.1
83.0
87.8
93.7
ol-mini (search model)
LCB
69.5
90.8
91.2
91.3
Table 1: LCB, HE+, M+ short for LiveCodeBench, HumanEval+, and MBPP+, respectively, IS short for IDEASEARCH and PS short for PLANSEARCH. We find that PLANSEARCH and IDEASEARCH improve upon search baselines across all models, with PLANSEARCH achieving the best results across models and benchmarks considered. Notably, using PLANSEARCH on top of Claude 3.5 Sonnet (Anthropic 2024) has pass @ 200 of 77.0 on LiveCodeBench,, which is nearly double the performance basic pass @ 200 ol-mini for LiveCodeBench. though since ol-mini already uses inference-time compute, the gap is much smaller than compared to non-search models. The full pass @ k curves are included in Appendix A
the top model without using search (41.4). PLANSEARCH also outperforms
5.1 DATASETS
We evaluate search methods three benchmarks: MBPP+, HumanEval+ (Luu al.) 2023). and LiveCodeBench (Jain et al.) 2024). MBPP (Austin et al. 2021) and HumanEval (Chen et al. 2021 some of the most widely used code benchmarks in the field. However, since both benchmarks provide only a few test cases, Liu et al. (202)) updates both benchmarks with additional test cases that increase the benchmarks' robustness reward hacking. LiveCodeBench is benchmark for coding that consists of competitive programming problems which typically require advanced reasoning capabilities. Given the reality that coding data often highly upsampled during pre-training (OpenAl et al., 2024 Dubey et al. (024)), LiveCodeBench differentiates itself from other benchmarks by taking care to segregate problems by date avoid data contamination concerns. For this paper, use only the subset of problems between May 2024 and September 2024 to avoid possibilities of contamination. We choose May 2024 as the cutoff date to ensure that our results with our best performing model (Claude 3.5 Sonnet) not due to contamination, because Claude 3.5 Sonnet has a knowledge cutoff of April 2024. To ensure fair comparison, we use the same cutoff for all models evaluated, even though the precise cutoff dates for other models may vary slightly from May 2024.
7

---

Published as a conference paper at ICLR 2025
Pass@k vs k for Methods with Public Filtering on LiveCodeBench
GPT-4o-mini
GPT-4o
DeepSeek-Coders
Sonnet-3.5
Public Filtering
----
No Public Fibteing
0.7
0.7
0.6
0.6
0.5
0.5
0.4
0.4
Repeated Sampling
IdeaSearch
0.3
PlanSearch
Figure 4: Performance of all models and methods on LiveCodeBench with public test filtering. The purpose of filtering is to shift pass@k curves leftward (i.e., bringing performance high to low k), plot curves in detail over & (1, ....... 20). Even 10 completions, PLANSEARCE outperforms filtered REPEATED SAMPLING by a flat 30 to 40%. Again, full pass@ plots are included in their entirety in Appendix A
5.2 EXPERIMENT DETAILS
For all search algorithms, we require that all output code be in the correct format specified, and we mark solution as incorrect if does not follow the intended formatting. The extracted code is then run through all tests of the program and marked as correct if and only if it passes all tests.
models are run with temperature 0.9 and top-p of 0.95. (ol-mini was run with temperature and top-p of 1.0 because of API constraints.) Temperature determined through coarse hyper- parameter sweep on REPEATED SAMPLING and IDEASEARCH from T E {0.0, 001, 0.2, 1.2]. which we describe in Appendix M
Both REPEATED SAMPLING and IDEASEARCH generate exactly n codes, whereas PLANSEARCH generates variable number of codes, usually ranging on the order of 300 to 400. To compute @ass@k, @k we use the unbiased estimator in Equation CCen et al. 2021
If k n1, assume the remaining generations did not pass. To compute @ for filtering, limit the pool of codes to those that are filtered, meaning that both n and e may shrink in size. This be thought of conditional probability, where the condition is that the code passes public tests. For more information on public test filtering, see Appendix R
Note that the estimator in Equation 4 theoretically requires that the number of successes follows a binomial distribution. REPEATEd SAMPLING and IDEASEARCH obey this, but PLANSEARCH generations may not be independent. See Appendix O for more discussion.
8

---

Published as a conference paper at ICLR 2025
5.3 RESULTS
Our summarized results for REPEATED SAMPLING, IDEASEARCH, and PLANSEARCH can be found in Table Figure 1 and Figure We find that PlanSearch improves over existing methods for all models and benchmarks considered.
Additionally, plot full pass@k k curves for all methods, models, and datasets in Appendix Due to prohibitively high costs, we only evaluate ol-mini on LiveCodeBench, as HumanEval+ and MBPP+ show strong saturation effects ol-mini and associated discussion can be found in Appendix
with weaker models like GPT4o-mini. The pass @k curves of
K For sake of easy comparison, we also plot all relative gains compared REPEATED SAMPLING @ averaged over all models in Appendix For compute-nommee normalizd comparison between REPEATED SAMPLING and PLANSEARCH, see Figure 17 Additionally, we ablate over the design choices made for PLANSEARCH in Appendix
6 ANALYSIS
Our results suggest that both PLANSEARCH and IDEASEARCH outperform basic sampling by wide margin (Figures II 12 13), with PLANSEARCH achieving the best score across all methods and models considered. Since ol-mini is unique from all other models tested, we show and discuss its unique results in Appendix K We show the detailed pass @k results for each dataset in Figures 7 and8 We also compare with Chain-of-Thoupe find that IDEASEARCH performs somewhat better, which we speculate comes from differences in splitting solution sketch into two model responses, instead of doing both chain-of-thought and code solution in one model response.
(Wei
2022) Appendix E Interestingly, we
Investigating the differences in specific models, we notice that trends exhibited by the pass@k curves are not uniform across all models; in fact, each curve seems unique. We hypothesize that these differences are part due to changes idea diversity, as investigated in Figures 25 26 Figure 5 includes o1-mini diversities, which also follow the observed trend. From the figures, we can see that our approximate diversity score accounts for much the variance we see in the relative improvement that arrives from scaling-up inference-time compute. This correlation holds across all methods and models on the same dataset, thus suggesting that diversity score can be used as a proxy to predict for relative pass @k k improvement. For further discussion the specifies of the diversity score, Section 6.
One interesting point of observation is that PLANSEARCH often hurts pass@ @ for several models, including most notably Sonnet 3.5 on LiveCodeBench, our best performing combination. Intuitively, this is because increasing the diversity across ideas likely dilutes the probability that any particular idea is generated, while simultaneously increasing the chance of having at least one correct idea within said pool. Therefore, pass@1 may be slightly lower than usual, yet pass @k k will likely surpass "pools" of ideas lacking diversity for this reason. See Figure 41 for a graphical intuition.
Finally, in Table [ and Figure I we present our main results normalized across attempts/complltion. where each search method is allowed k attempts to solve each problem. An alternative method of normalizing across methods is to equalize the amount of compute spent on each method. Since PLANSEARCH and IDEASEARCH first plan out an idea before implementing the final solution, they both spend more compute at inference time per solution generated. In Appendix D we report the equivalent plots normalized across compute. Our findings are highly similar and suggest that PLANSEARCH outperforms other methods if sufficient compute expended at inference time.
6.1 MEASURING DIVERSITY
We find that idea-space diversity strongly predicts search performance, measured by the relative improvement between pass @1 and pass@200 (Figure 5). While entropy is a common diversity measure (Shannon 1948), it is inadequate for LLM settings (Hashimoto et al. 2019 Zhang et al. 2021). For instance, model generating variations of the same program and another producing distinct programs may have equal entropy, yet the latter will perform better in search- aurrc-a tasks.

---

Published as a conference paper at ICLR 2025
Idea Diversity vs Relative Gains from Search (on LiveCodeBench)
1.8
Repeated Sampling
Relative Gains (Pass@] to Pass@2001
IdeaSearch
1.6
PlanSearch
1.4
GPT-4o-mini
0.6
GPT-4o
DeepSeek-Coder-V2
0.4
Sonnet-3.5
ol-mini
0.4
0.5
Idea Diversity
Figure 5: We observe a strong positive correlation between the measured amount of idea diversity (higher score is better) in a search algorithm and the resulting improvements due to search. See Section 6.1 for information regarding the diversity score.
We measure diversity in idea space via pairwise comparisons across all generated programs. Let fci...., Cn be a set of n code generations, each corresponding to a latent idea. Two sketches can be thought be considered similar if they are within some of each other in idea space, noting that transitivity may not hold here.
To compute diversity, we construct the (2) pairs and evaluate their similarity using an LLM, defining S(c,, cj) 1), where S(G,, ey) iff & and ej are similar. The diversity score is:
D 1 Eies S(G,,))
model producing all identical ideas has O, while one generating all unique ideas has D 1. A score of D is also equivalent to the probability that two randomly selected programs similar to each other (see Appendix for more details).
For each method, we report the diversity score across all problems. For large we sample 40 codes and compare all pairs. GPT-4o-mini is used to evaluate S, and full prompt details are in Appendix 0.1
CONCLUSION
In this work, we find that diversity in idea space incredibly useful unlock significant achievements in the effectiveness of inference-ting time compute otherwise referred to search particularly in code generation tasks. We propose PLANSEARCH, which obtains great performance on all datasets tested, almost doubling baseline performance pass @ 200. Additionally, we find strong correlation between our diversity metric and resulting performance gains from evaluating at pass@k k instead of pass@) 1, which underscores the importance of idea diversity in effective scarch. We believe that these insights can applied to many other domains and will be crucial realize the full potential LLMs to unlock significant performance gains seen here.
compute-othervise
However, while PLANSEARCH substantially improves diversity over idea space at inference-time fundamentally, improvements in diversity should also come at the post-training stage, like with methods such as of (OpenAl 2024). This likely requires re-imagining the post-training pipeline for L.MMs around search.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Zhiqiang Shen Aidar Myrzakhan, Sondos Mahmoud Bsharat. Open-lim-leaderboard: From multi- choice to open-style questions for Ilms evaluation, benchmark, and arena. arXiv preprint
NAXiv:2406.07545, 2024.
Anthropic.
Claude 3.5 sonnet.
https:/www.cnirroooccccoo./..
claude-33 1-adde-3-55 3-5 5- sonnneett] June 2024.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe Le, and Charles Sutton. Program synthesis with large language models, 2021. URL https: www.aaxxivv........a.... www.orgggsb....o.. abs 0t/./2118.0077 07732
https://acxiv.rrg
Anton Bakhtin, David J. Wu, Adam Lerer, Jonathan Gray, Athul Paul Jacob, Gabriele Farina, Alexander H. Miller, and Noam Brown, Mastering the Game of No-Press Diplomacy via Human- Regularized Reinforcement Learning and Planning, October 2022. abs/22100 05492 arXiv:2210.05492 [cs].
Hritik Bansal, Arian Hosseini, Rishabh Agarwal, Vinh Q. Tran, and Mehran Kazemi. Smaller, weaker, yet better: Training Ilm reasoners via compute-optimal sampling. 2024. URL https
7/arxiv. hwwpg///bb//la/ 2408 16737
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling, 2024. httttttt://aaattt.t
abs 2a.p///240..0m 2274777717877
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 35966774):418-424, 2018. Publisher: American Association for the Advancement of Science
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456): 885-890, 2019. Publisher: American Association for the Advancement of Science.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Ben- jamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33. pp. 1877-1901. Curran Associates, Inc., 2020. URL httpt:ttt//............t http://///ppooeeeenggg... cc/ cc/papper2022//1122 75w544557760ccc00 96747777777 41741115
ps pdf
Murray Campbell, J.Joseph Hoane, and Feng hsiung Hsu. gence, 134(1):57-83, 2002. ISSN 0004-3702.
Deep blue. Artificial Intelli- doi: http://ko..ogg1o0000600004770700
00129-1. URL https::/wwww http::/wwwwwcciiiee. scienced rect. rrectt.ccm//cceeeee/atttiiiieeee
SDC0437020100122
Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen. Codet: Code generation with generated tests. arXiv preprint arXiv:2207. 2022a.
Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Codet: Code generation with generated tests, 2022b. URL
Lou, and Weizhu Chen.
10397
Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei Zaharia, and James Zou. Are more Ilm calls all you need? towards scaling laws of compound inference systems, 2024.
URL https:///a/tttttt
wrw. hbtp:/bb/224000 02419
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph. Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger. Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavloy, Alethea Power, Lukasz Kaiser, Mohammad Bavarian,
11

---

Published as a conference paper at ICLR 2025
Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba, Evaluating Large Language Models Trained on Code, July 2021. URL http: arwiv. www.w/ggg/aab///0 arXiv:2107.033: [cs].
03374
Wei-Lin Chiang, Lianmin Zheng, Ying Sheng. Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang, Banghua Zhu, Michael Jordan, Joseph E. Gonzalez, and Ion Stoica. Chatbot arena: An open platform for evaluating Ilms by human preference, 2024. URL
abs/2403 04132
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783 2024.
Sergey Edunov, Myle Ott, Michael Auli, and David Grangier. Understanding back-translation scale, 2018. URL
FAIR, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, Athul Paul Jacob, Mojtaba Komeili, Karthik Konath, Minae Kwon, Adam Lerer, Mike Lewis, Alexander H. Miller, Sasha Mitts, Adithya Renduch- intala, Stephen Roller, Dirk Rowe, Weiyan Shi, Joe Spisak, Alexander Wei, David Wu, Hugh Zhang, and Markus Zijlstra. Human-level play in the game of Diplomacy by combining lan- guage models with strategic reasoning. Science, 37866624) 10. (ea11///ciencee.dee000
December 2022. doi: www.sciieeccc.ccc..oo..e..eee..e wwwp///o...////oo./////o 111.0.16//ccienee
[RL[hhtps:////
ade9097
Publisher: American Association for the Advancement of Science.
Markus Freitag and Yaser Al-Onaizan. Beam search strategies for neural machine translation. In Proceedings of the First Workshop Neural Machine Translation. Association for Computational Linguistics, 2017. doi: 10. 1/153/////111-327.. URL http: //xx doi http://t.ddoooggg....11...
01/017-3207
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. Pal: Program-aide aided language models, 2023. URL httpp:://axxi..or.t..tt/
abs/ 22111221112 10435
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with Language Model is Planning with World Model, May 2023a. http:
//arxiv. wwt.orgg//baaa. httpg//ab/2330555 2305 14992 arXiv:2305. 14992 [cs].
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting
Hu. Reasoning with language model is planning with world model, 2023b. URL https
/arxiv. wwwp/ba......... /ttp:/335...1. 14992
Tatsunori B. Hashimoto, Hugh Zhang, and Percy Liang. Unifying Human and Statistical Evaluation for Natural Language Generation. North American Association for Computational Linguistics arviv: 1904.02792.
(NAACL)., April 2019. URL BRLLattt:///axv.coo wwwp:///.///aao...ooooo......aaa 1904 02792
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and lon Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint arXiv:2403.07974, 2024.
Andy Jones. Scaling scaling laws with board games, 2021. URL / 2104. 03113
Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, and Percy Liang. Spoc: Search-base based pseudocode to code, 2019. URL https: h/tp:///xxxvvo/// org/ /bs/ 1906.c 04908)
12

---

Published as a conference paper at ICLR 2025
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition--evel code generation with alphacode. Science, 37866624) 2022.
Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang. Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https
/ //penrevveww net htte://ormmmiidlixaeee
Drew M. McDermott. The 1998 ai planning systems competition. Al Magazine, 21(2):35, Jun. 2000.
doi: 10. 10..1609/ama...22i... v2122.1106. URL https::/ojss..... aaai http://orgaaaaaaaaeeeee index
Aidan McLaughlin. AI Search: The Bitter-er Lesson, 2024. Accessed on September 3, 2024.
Sidharth Mudgal, Jong Lee, Harish Ganapathy, YaGuang Li, Tao Wang, Yanping Huang. Zhifeng Chen, Heng-Tze Cheng. Michael Collins, Trevor Strohman, Jilin Chen, Alex Beutel, and Ahmad Beirami. Controlled decoding from language models, 2024. URL https: /tttps://arx.e http/xxxxvvv..o/
abs/ abs/23100 2tt//231..1122
OpenAl. Learning to reason with 1lms.
bttps://openai.cmm com/ index/
learning nn- reason- wi th 11ms/ Sep 2024. Accessed: October 2024.
OpenAl, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidr, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine. Gabriel Sermadett-Shapiro Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson. Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, łukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan. Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanic Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini. Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichiro Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O'Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish. Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng. Adam Perelman, Fillipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokomny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Prochl, Raul Puri, Alec Radford. Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam. Kyla Sheppard, Toki Sherbakov, Jessica Shich, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers,
13

---

Published as a conference paper at ICLR 2025
Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arum Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, C. J. Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojeiech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. GPT-4 Technical Report, March 2024. URL http: orq/ ats/ 08774 arXiv:2303.085 08777 [cs].
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730- 27744, 2022.
Hieu Pham, Xinyi Wang, Yiming Yang, and Graham Neubig. Meta back back-translation, 2021. URL https://arxiie org/ httpa/b////12.22222
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36, 2024.
Stuart Russell and Peter Norvig. Artificial intelligence: modern approach. 2002.
Timo Schick, Jane Dwivedi-Yis Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools, 2023.
Rico Senmrich, Barry Haddow, and Alexandra Birch. Improving neural machine translation models with monolingual data, 2016. URL https: wttp:/iwwwogg/bbb////ae 06709
Claude E Shannon. A mathematical theory communication. Bell System Technical Journal, 27(3): 379-423, 623-656, 1948.
Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023. URL
23003 11366
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonogiou, Veda Pannecrshelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529(7587)4844449 January 2016. ISSN 0028- 0836, 1476-4687, doi: 10. 10.8////a 16911. URL http:/t///// www. www.wwwwww...........w...wwwwwww nwwura..uee..... naturell 16661
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, and others. Mastering the Game of Go Without Human Knowledge. Nature, 550(7676):354-3555 -59,, 2017. Publisher: Nature Publishing Group.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling I1m test-time compute ops can be more effective than scaling model parameters, 2024. URL https: BtR.tttps./aaaiiiooo/////
2408 03314
Richard S Sutton.
The bitter lesson. Incomplete Ideas, 2019.
URL http:/ /www
incompl 1 eeeeeeeiieeee.eeee deas net.
Inc Sinc.deaa//itterleessss BBitterreesso......mm html
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of-Thoughe Prompting Elicits Reasoning in Large Language Mod- els. arXiv, 2022. doi: 10.48550/axiiv2220..1 1903. URL htll:ttt:://aaa org. /bs// /2001 11 11903
arXiv:2201. 1903 [es].
14

---

Published as a conference paper at ICLR 2025
Yangzhen Wu, Zhiqing Sun, Shanda Li. Sean Welleck, and Yiming Yang. An empirical analysis of compute-optimal inference for problem-solving with language models, 2024. URL https //axxiv.org////ooo....ooooooo abs/ 2408 00724
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of Thoughts: Deliberate Problem Solving with Large Language Models, May 2023a. URL http: arxiv.vi......... wwl.yorg//aaee hzgg/bbs/330 10601, arXiv:2305.1060) [cs].
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, 2023b. URL https: //arxiv org/abs//211sr aawaaa///2222 03629
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman, STaR: Bootstrapping Reasoning With Reasoning, May 2022.
14465 arXiv:2203.14465
[cs].
Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D. Goodman, and Nick Haber. Parsel: Algorithmic reasoning with language models by composing decompositions, 2023. URL Ittpp://arxiv org/abs 2212. 10561
Eric Zelikman, Georges Harik, Yijia Shao, Varuna Jayasiri, Nick Haber, and Noah D. Goodman. Quict-star: Language models can teach themselves to think before speaking, 2024. URL https
//axxiv.crg/abs:..... http:/bbb2223....0 09629
Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. Rest-mets*: Llm self-training via process reward guided tree search, 2024. URL htttt:://txxii..rrrrtr
2406. 03816
Hugh Zhang and David C. Parkes. Chain-of-thouuht reasoning a policy improvement operator, 2023. URL
08589
Hugh Zhang, Daniel Duckworth, Daphne Ippolito, and Arvind Neelakantan. Trading off diversity and quality in natural language generation. In Proceedings of the workshop on human evaluation of NLP systems (HumfEval), pp. 25-33, Online, April 2021. Association for Computational Linguistics. URL wttpthttt//cccc antho ogy..o.......................... orgg..rg//000 2021 www.hhummaaala.
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B. Tenenbaum, and Chuang Gan. Planning with large language models for code generation. The Eleventh International Conference Learning Representations, 2023. URL
Id=
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe Le, and Ed Chi. Least-to-most prompting enables complex reasoning in large language models, 2023. /tt.ttps:///arii..rr//abbbs
15

---

Published as a conference paper at ICLR 2025
A
FULL PASS @ K CURVES FOR ALL MODELS AND ALL BENCHMARKS
See Figures 6
7 8
We plot all models and methods on HumanEval+, MBPP+ (Liu et al. 2023). and
LiveCodeBench (Jain al. 2024 respectively.
@ass@k vs k for Methods on HumanEval+
GPT-4o-mini
GPT-4o
1.0
1.0
0.9
0.9
Pass@k
0.8
0.8
0.7
0.7
0.6
0.6
10
100
10
100
SrepSeek-Coder-V.
Sonnet-3.5
1.0
1.0
0.9
0.9
Pass@k
0.8
0.8
0.7
0.7
0.6
0.6
Repeated Sampling
IdeaSearch
Planš earch
10
100
10
100
k
Figure @ass@k performance all models and methods on HumanEval+, plotted over .0....
16

---

Published as a conference paper at ICLR 2025
@ass@k k vs k for Methods on MBPP+
GPT-4o-mini
GPT-4o
0.9
0.9
0.8
0.8
Pass@k
0.7
0.7
0.5
0.5
10
100
10
100
DeepSeek-Coder:v2
Sonnet-3.5
0.9
0.9
0.8
0.8
Pass@k
0.7
0.7
Repeated Sampling
IdeaSearch
PlanSearch
0.5
0.5
1
10
100
10
100
Figure Pass performance of all models and methods on MBPP+, plotted over is E f1,...,,000
17

---

Published as a conference paper at ICLR 2025
Pass@k vs for Methods on LiveCodeBench
GPT-4o-mini
GPT-4o
0.6
0.6
Pass@k
0.5
0.4
0.4
0.3
0.3
10
100
10
100
Deed5eek
Sonnet-3.5
0.6
0.6
Pass@k
0.5
0.4
0.4
Repeated Sampling
IdeaSearch
0.3
0.3
10
100
10
100
k
Figure 8: @ass@k performance of all models and methods on LiveCodeBench, plotted over k {1. (1....,000) 200).
18

---

Published as a conference paper at ICLR 2025
B FULL PASS @K K CURVES WITH PUBLIC FILTERING
See Figures 10
We plot all models and methods with public test filtering on HumanEval+, )023), and LiveCodeBench (Jain al. 2024). respectively.
MBPP+ Liu
Pass@k k vs k for Methods with Public Filtering on HumanEval+
GPT-4o-mini
GPT-4o
1.0
1.0
0.9
0.9
Pass@k
0.8
0.8
0.7
0.7
0.6
0.6
10
10
DeepSeek-Codes
Sonnet-3.5
1.0
1.0
Public Filtering
No Public Filtering
0.9
0.9
Pass@k
0.8
0.8
0.7
0.7
0.6
0.6
Repeated Sampling
IdeaSearch PlanS earch
10
10
Figure 9: Pass@k performance of all models and methods on HumanEval+, with public test filtering, plotted over & (1...., 20). Note that dotted lines are provided for reference of the base method pass@r @k before filtering.
19

---

Published as a conference paper at ICLR 2025
Pass@k vs for Methods with Public Filtering on MBPP+
GPT-4o-mini
GPT-4o
0.90
0.90
0.85
0.85
0.75
0.75
Pass@k
0.70
0.70
0.60
0.60
0.55
0.55
0.50
10
10
DeepSeek-Code
Sonnet-3.5
0.90
0.90
Public Filtering
No Public Filtering
0.85
0.85
0.75
0.75
Pass@k
0.70
0.70
0.60
0.60
Repeated Sampling
0.55
0.55
IdeaSearch
PlanSearch
0.50
Figure 10: @ass@k performance of all models and methods on MBPP+, with public test filtering, plotted over k: (1...., 20). Note that dotted lines are provided for reference of the base method @ k before filtering.
20

---

Published as a conference paper at ICLR 2025
C AVERAGE RELATIVE IMPROVEMENTS
To create these graphs, the relative improvements of each point on all pass@k curves computed and compared to the respective pass@ of REPEATED SAMPLING. Then these values are averaged over all models, so that there is one curve per method per dataset. The datasets are HumanEval+, MBPP+ (Liu et al. 2023). and LiveCodeBench (Jain et al. 2024), respectively. For the public test filtered versions, see Figures 15
See Figures
16
Average Gains HumanEval+
20
10
Relative Gain (%)
10
13
Repeated Sampling
IdeaSearch
PlanSearch
-20
10a
10
k
Figure 11: Performance gain over REPEATED SAMPLING averaged over all models on Hu- manEval+, plotted over ls E (1....,200),
Average Gains on MBPP+
Relative Gain (96)
-10
Repeated Sampling
IdeaSearch
-20
PlanSearch
10a
10a
10
Figure 12: Performance gain over REPEATED SAMPLING@) I averaged over all models on MBPP+. plotted over (l00..,00)).
21

---

Published as a conference paper at ICLR 2025
Average Gains on LiveCodeBench
60
Relative Gain (%)
40
Repeated Sampling
IdeaSearch
10a
10:
10a
Figure 13: Performance gain over REPEATED SAMPLING@! averaged over all models on Live- CodeBench, plotted over i E (1...., 200)..
Average Gains with Public Filtering on HumanEval+
Public Filtering
15
No Public Filtering
10
Relative Gain (%)
-10
-15
Repeated Sampling
IdeaSearch
PlanSearch
102
107
Figure 14: Average performance gain over all models of methods with public test filtering compared to REPEATED S SAMPLING@* 1, plotted over k E ......,00, Note that dotted lines are provided for reference of the base method pass@t @k k (before filtering).
22

---

Published as a conference paper at ICLR 2025
Average Gains with Public Filtering on MBPP+
20
Public Filtering
No Public Filtering
Rel velatiiee Gain (%)
-10
Repeated Sampling
IdeaSearch
-20
PlanSearch
10a
16'
Figure 15: Average performance gain over all models of methods with public test filtering compared to REPEATED SAMPLING@) 1, plotted over E (1....,.0 20). Note that dotted lines are provided for reference of the base method pass @k (before filtering).
Average Gains with Public Filtering on LiveCodeBench
Public Filtering
No Public Filtering
Relative Gain (9))
40
20
Repeated Sampling
IdeaSearch
PlanSearch
10F
10
Figure 16: Average performance gain over all models of methods with public test filtering compared to REPEATED SAMPLING@1 1, plotted over (1...., 203. Note that dotted lines are provided for reference of the base method pass @k k (before filtering).
23

---

Published as a conference paper at ICLR 2025
D COMPUTE NORMALIZED PASS @ K GRAPHS
For each run of method Appendix A needed per completion, per problem, independently on each dataset. Then, average across all datasets to obtain 244 generated tokens per completion per problem for REPEATED SAMPLING, and 428 generated tokens per completion per problem for PLANSEARCH.
See Figure 17
we compute the number of generated tokens
Nompute-Normalized Repeated Sampling vs PlanSearch
0.8
PlanSearch
Repeated Sampling
0.7
0.6
Solve-rate
0.5
0.4
GPT-4o-mini
GPT-4o
DeepSeek-Coderv2
0.3
Sonnet-3.5
10a
10
10a
Average Tokens Used (per problem)
Figure 17: Normalized p by average tokens used per problem. REPEATED SAMPLING uses roughly 244 tokens per completion per problem, and PLANSEARCH uses roughly 1428 tokens per completion per problem. When we normalize compute across methods, we find that PLANSEARCH begins to be more effective than repeated sampling the user willing to sample least 10,000 tokens per problem.
24

---

Published as a conference paper at ICLR 2025
E COMPARISON WITH CHAIN-OF-THOUGHT
See Figures 18 19 20 which are run on LiveCodeBench (Jain et al. 2024). MBPP+, and Hu- + (Lu et al.
) respectively. These are the same plots as Appendix A with CoT (Wei
et al. 2022 See Figures 21 22 23 for the public test filtered versions.
@ass@k vs k with CoT on LiveCodeBench
GPT-4o-mini
GPT-4o
Passigg
0.5
0.5
0.4
0.4
0.3
0.3
10
100
100
DeepSeek-Coder.22
Sonnet-3.5 5.
0.7
0.6
0.6
Passikk
0.5
0.5
0.4
0.4
Repeated Sampling
IdeaSearch
Thouph:
0.3
0.3
10
100
30
100
Figure 18: Pass@k graphs on LiveCodeBench, with the Chain-of Maain-of-Thouse Thought baseline.
25

---

Published as a conference paper at ICLR 2025
Pass@k vs k with CoT on MBPP+
GPT-4o-mini
GPT-4o
0.9
0.9
0.8
0.9
Pessigk
0.7
0.7
0.8
0.6
0.5
10
100
0.5
100
DeepSeek-Coderv22
Sonnet-3.5
Pesggk
0.7
Repeated Sampling
Chain-at-hought
Plantsearch
0.5
0.5
Figure 19: Pass@k graphs on MBPP+, with the Thain-of-Thought baseline.
Pass@k vs k with CoT on HumanEval+
GPT-4o-mini
GPT-4o
1.0
1.0
Possgll
0.8
0.8
0.6
0.6
100
DeepSeek.Coder.V2
Sonnet-3.5
0.9
0.9
Pessigk:
0.7
0.7
Repeated Sampling
IdeaSearch
Chain-o--hought
PlanSsarch
10
100
100
Figure 20: Pass @k graphs on HumanEval+, with the Shain-of-Thoughh baseline.
26

---

Published as a conference paper at ICLR 2025
Pass@k vs k with CoT (Public Filtering) on LiveCodeBench
GPT-4o-mini
GPT-4o
0.7
PassiB
0.3
0.3
DeepSeek-CodrrV2
Sonnet-3.5
Publl fitering
0.6
Pessigk
0.5
0.5
0.4
0.4
Repeated Sampling
IdcaSearch
Chair of Thought
0.3
0.3
FlanSearch
10
10
Figure 21: Pass@k graphs on LiveCodeBench, with the Chain-of-Thought baseline and public filtering.
Pass@k with CoT (Public Filtering) on MBPP
GPT-4o-mini
GPT-4o
0.90
0.90
0.85
0.85
Pass@g
0.75
0.70
0.70
0.85
0.65
0.50
0.50
DeepSeek-Coder-V2
Sonnet-3.5 3.5
0.90
0.90
Public Filtering
Pessgg
0.75
0.75
0.70
0.70
0.50
0.50
Ropeated Sampling
0.5%
0.55
Chain-of Thouphh
PlanSsarch
0.50
Figure 22: Pass @ k graphs on MBPP+, with the Chain-of Siiin-of-Thhughh baseline and public filtering.
27

---

Published as a conference paper at ICLR 2025
Pass@k vs k with CoT (Public Filtering) on HumanEval+
GPT-4o-mini
GPT-4o
1.0
1.0
Pass
0.8
0.9
0.8
0.6
DeepSeek Coder-V2 2V
Sonnet-3.5
Public Ritering fittriing
0.9
0.9
Pas508
0.8
0.7-
0.7
Repeated Sampling
IdeaSearch
Chan-of-Thught
Plandsearch
Figure 23: @ass@k k graphs on HumanEval+, with the Chain-of- Chain-of-Thought Thought baseline and public filtering.
28

---

Published as a conference paper at ICLR 2025
F ABLATION ON TEMPERATURE FOR REPEATED SAMPLING AND IDEASEARCH
See Figure 24 We sweep over temperature increments of 0.1 from 0.0 1.2, inclusive, with top-p of
0.95, on REPEATED SAMPIING and IDEASEARCH.
Temperature Effects on Pass@k (on LiveCode
1.2
Repeated Sampling
0.575
IdeaSearch
11.
0.550
0.525
-0.8
0.500
Temperature
Pass@k
0.6
0.475
0.450
0.4
0.425
0.2
0.400
0.375
0.0
10
k
Figure 24: Sweep over temperature in 0.1 increments from 0.0 1.2. REPEATED SAMPLING and IDEASEARCH both exhibit pass@k k improvements at higher temperature, although seems that higher temperatures may begin plateau.
29

---

Published as a conference paper at ICLR 2025
G DIVERSITY SCORE VS SEARCH IMPROVEMENT PLOTS FOR MBPP+ AND HUMANEVAL+
Each figure is made through running the diversity measure described in Section 6. on the generated codes of each run, then compared with the relative gain from pass @k compared to pass@1 1.
See Figures 25
26
Idea Diversity vs Relative Gains from Search (on HumanEval+)
0.9
Repeated Sampling
Relative Gains (Pass@1 to Pass@
IdeaSearch
0.8
PlanSearch
0.7
0.6
0.5
0.3
+
GPT-4o-mini
GPT-40
0.2
DeepSeek-Coder//
0.1
Sonnet-3.5
0.3 Idea Diversity
Figure 25: Relationship between the measured diversity score described in Section 6.1 (where higher is more diverse) and relative improvement from the pass @ I of the method to the pass @ 200 of the method.
30

---

Published as a conference paper at ICLR 2025
Idea Diversity vs Relative Gains from Search (on MBPP+)
0.9
Repeated Sampling
Relative Gains @Pass@1 to Pass@200 200
IdeaSearch
0.8
PlanSearch
0.7
0.6
0.5
0.4
0.3
GPT-4o-mini
0.2
GPT-4o
DeepSeek-Coder-22
0.1
Sonnet-3.5
0.1
0.2
0.3 Idea Diversity
0.4
0.5
0.6
Figure 26: Relationship between the measured diversity score as described in Section 6.1 (where higher is more diverse) and relative improvement from the pass @ I of the method the pass 200 of the method on MBPP+.
31

---

Published as a conference paper at ICLR 2025
H ABLATIONS
We run ablations on the core parts of PLANSEARCH, using GPT-4o-mini on LiveCodeBench (Jain al., 2024). On the diverse observation generation side, we first verify our choice of S the
maximum subset size to sample from out of a given pool of observations and also compare perfor-
mance across varying the number of observation layers used (Figures 27 28 On the implementation side, we compare different sections of the proposed pipeline (see Figure 2 to translate combinations
of observations to code in Figure 29
We compare each method's pass @# from k
200.
Ablations Varying S on LiveCodeBench
0.65
0.60
0.55
Pass@k
0.50
0.45
0.40
PlanSearch (S=1)
PlanSearch (S=2)
PlanSearch (S=3)
10
100
Figure 27: We run ablations PLANSEARCH with different S S-controlling the maximum subset size from given pool of observations. There is not large difference between different S, but find that or 2 is slightly more optimal, although if more completions are desired, S can be increased well.
The effect S, the maximum observation subset size to build upon, has on performance not overly significant; there small degradations S is increased to 3, but not noticeable. We choose S to obtain more code completions. See Figure 27
Increasing L, the maximum number of layers of the observation tree, increases pass @k at large enough (above 50). We choose L = 2 to strike a balance between extracting a large pass @ k gain while keeping compute costs reasonable. See Figure 28
we see that our overall translation step adds minor pass gains. We deconstruct the translation step into parts: the pseudocode step, the fix step (i.e., asking the model to fix its proposed solution sketch), and creating the solution sketch at all (which includes the fix step).
From Figure 2
"No solution sketch, pseudocode" implies using a given observation combination directly prompt for the solution code.
"No pseudocode" implies skipping the pseudocode step. In other words, given solution sketch, the sketch directly translated into code.
"No fix step, pseudocode" implies the fix step is skipped, well the pseudocode. In order to have the same number of completions, the whole PLANSEARCH pipeline is run twice.
32

---

Published as a conference paper at ICLR 2025
Ablations Varying L on LiveCodeBench
0.65
0.60
0.55
Pass@k
0.50
PlanSearch (L=1)
PlanSearch (L=2)
PlanSearch (L=3)
10
100
Figure 28: We run ablations of PLANSEARCH with different L- controlling the maximum order of observation used, i.e., how many layers the observation tree will search. We find pass@ scales with respect to increasing T.
Ablations Varying Observation to Code LiveCodeBench
0.65
0.60
0.55
Pass@k
0.50
0.45
PlanSearch
PlanSearch (No pseudocode)
0.40
PlanSearch (No fix step, pseudocode)
PlanSearch (No solution sketch, no pseudocode)
10
100
k
Figure 29; We run ablations of PLANSEARCH with different methods of translating combination of observations to code.
33

---

Published as a conference paper at ICLR 2025
Pass@k for Conbeeek-CoderV2-Liie Lite Models on MBPP+
0.80
Pass@k
0.65
0.00
De StrsSeee--ooere/-lll----ooe
Figure 30: Despite DeepSeek-Codee Coder- V2-Lite- Base having significantly lower pass@) I than its instruct counterpart, we observe that this trend reverses as increases, suggesting that the instruct model has less diversity than its base model counterpart. We observe this trend for many, but not all, models and benchmarks, and provide the full data in Appendix [
I BASE MODELS VS. INSTRUCT MODELS FOR LARGE SAMPLES
We find that base models, despite performing poorly relative their instruct counterparts for evaluated with pass @ 1, will frequently match or even exceed performance on pass @k for sufficiently high k. This is likely due to higher amounts of diversity in base models, which have not undergone post-training designed to elicit a single strong response from the model.
We this effect across all models for HumanEyal+ and MBPP+, but only the DeepSeek-Coder- family for LiveCodeBench.
See Figure 31 for all base and instruct model comparisons between CeapsSeek-Code--22---1 Llama- 3.1-8B, and -la0 on all three datasets.
We also provide Llama-3.1-88 and CeepSeee-Cooee--2--11 pass@k comparisons for A: up 10, 000:
see Figures 33 32
J BASE MODELS VS. INSTRUCT MODELS WITH PUBLIC TEST FILTERING
We repeat the graphs from Appendix[[ | but with public test filtering. We find that base models with public filtering almost always exceed the pass@) of their instruct model variants.
See Figure 34 for all base and instruct model comparisons between DeepSeek-Codeer--2--e Llama- 3.1-8B, and L- all three datasets with public test filtering.
We also report Llama-3.1 1-8b and DeepSeek-Coders V--iit pass@k comparisons with public test filtering for k up to 10, 000; see Figures 35 36
34

---

Published as a conference paper at ICLR 2025
Pass@k of Base and Instruct Models
0.9
0.8
MBPP+
Pass@ak
0.7
0.7
0.7
0.6-
0.6
0.6
0.5
0.5
0.5
10
100
100
100
0.9
0.9
0.9
0.8
0.8
0.8
HumanEval+
0.7
Pass@k
0.6
0.5
0.5
0.5
0.4
0.4
0.4
0.3
10
100
100
100
0.6
0.6
0.6
0.5
0.5
0.5
LiveCodeBench
pas50t
* 0.4
0.4
0.4
0.3
Base Model
0.1
0.1
0.1
Instruct Model
10
100
10
100
100
DeepSeck-Coder-V-LLite
Llama-3.1-88
Llama-3,1-708
k
k
k
Figure 31: Pass curves comparing DeepSeek-Cooder----Lie Llama-3.1-8B. and Llama-3. 3.1-70B base and instruct performance.
Pass@k for DeeeSeekk.Cdder-V--iitt Models LiveCodeBench
0.6
0.5
Pass.lk
0.4
DeepSeek-Cadees22 -iie-Base
DecpSeek- Ltte-nstruct
10
100
1,000
10.000
Figure 32: @ass@k curves comparing SrepSeek-Codeer V2-Lit''s base and instruct versions on LiveCodeBench with up to 10, 000 completions.
35

---

Published as a conference paper at ICLR 2025
Pass@k k for Llama 3.1-8B Models LiveCodeBench
Pass@k
0.3
0.2
0.1
Lama--31--B--Ban
Uama-31-88B.nstracc
20
100
1,000
10,000
Figure 33: Pass @as curves comparing Llama-3. 1-8B'ss base and instruct versions on LiveCodeBench with up to 10, 000 completions.
Pass@k of Base and Instruct Models
0.9
0.9
0.9
MBPP+
Pass
0.7
0.7
0.7
0.6
0.6
0.6
10
10
0.9
0.9
0.9
HumanEval+
0.7
0.7
0.7
Pass@k
0.6
0.8
0.6
0.4
0.3
0.3
0.3
0.6
0.6
0.6
Public Filtering
0.5
0.5
0.5
Public Filtering
LiveCodeBench
0.4
Base Model
Instruct Model
0.1
0.1
0.1
DeepSeek-Coder-V2-I5 Coder-VV-Litee
Llama-3.1-88
Llama-3.1-708
k
k
Figure 34: Pass curves comparing DeepSeek- Conee--CCor---aee Codee-VV-LLtee, Alama-3.1--8. and Llama-3 3.1-70B base and instruct performance with public filtering.
36

---

Published as a conference paper at ICLR 2025
Pass@k vs k for Llama-3.1-88 Models on LiveCodeBench
Public Filtering
Fitteing
0.5
0.4
Pass@k
1amma-1.1-t--4e 1.1-4t--laee Uamma331-88-tssraut
100
1,000
Figure 35: Pass @k curves comparing Llama-3. 3.1-BB'ss base and instruct versions on LiveCodeBench with up to 1, 000 completions and with public test filtering.
Pass@k vs for DeepSeek-Coder-VV-Lic Models on LiveCodeBench
0.6
Public Fitering
fitteing
Pass@k
0.4
1,000
Figure 36: @ curves comparing PrepSeek-Coder-V--Ling base and instruct versions on LiveCodeBench with up to 1, 000 completions and with public test filtering.
37

---

Published as a conference paper at ICLR 2025
K OPENAI O1
We also do a brief analysis of OpenAl's ol (OpenAI 2024) models. We run PLANSEARCH on top of ol ol-mini, which is the best ol model available through API access at the time of writing for competitive coding. Due to both severe cost constraints and dataset saturation on HumanEval+ and MBPP+, we only run o1-mini on LiveCodeBench (Jain al. 2024).
First, we investigate its pass@k trends on LiveCodeBench. (See Figure 37 As expected, PLANSEARCH trails REPEATED SAMPLING for low k. However, at high PLANSEARCH competes with/slightly outperforms REPEATED SAMPLING.
We believe there to be two reasons why there is not large an improvement compared other non-search- based models. First, there may be diminishing returns when stacking multiple search methods on top of each other naïvely. Second, LiveCodeBench noticeably saturated, reaching solve-rates of over 90%. Thus, it is much harder notice large jumps in dataset performance, as can be seen pass@ k curves (see Figure 6 on HumanEval+ (Liu et al. 2023). There, REPEATED SAMPLING, IDEASEARCH, and PLANSEARCE all perform roughly the same, with PLANSEARCH only slightly outperforming the others. We believe a combination of these effects also implies greater & is required to notice large difference between REPEATED SAMPLING and PLANSEARCH.
Pass@k vs k for ol-mini on LiveCodeBench
0.90
0.85
Pass@k
0.80
0.75
Repeated Sampling
IdeaSearch
PlanSearch
10
100
k
Figure 37: Pass@k performance methods applied on top of ol-mini, on LiveCodeBench, plotted over E (1,..., 200}. PLANSEARCH slightly outperforms REPEATED SAMPLING high k;; larger not run due to cost constraints.
We notice that the OpenAl frequently refuses to answer queries from PLANSEARCH, likely due to efforts to minimize revealing the full tfain-of-thought the model is using. To combat this, we find that filtering out the words steps. st ep, and quote reduces the fraction of unanswered queries from roughly 40% to less than 0.5%. For any query that is still refused after this approach, we route the same prompt to GPT-4o. In addition, we remove the pseudocode step to reduce the amount of flagged responses.
On the diversity end, we apply the same methodology described in Section 6. plot can be found in Figure 5] Even though -mii is strong on own, we find that it is not very diverse, which is consistent with our claim that diversity correlates with relative performance gain seen with increasing k.
The corresponding
38

---

Published as a conference paper at ICLR 2025
L BAR CHARTS
See Figures 38 39 I These plot pass@1 I and pass @20 of select methods between REPEATED
SAMPLING and PLANSEARCH, on datasets MBPP+, HumanEval+ (Liu et al. 2023). and Live- CodeBench JJin al. 2024).
Pass@k Scores by Method on MBPP+
0.910
0.922
0.926
0.937
0.874
0.838
0.819
0.8
0.777
0.771
0.735
Pass@k
0.4
0.2
Repeated Sampling 1
Repeated Sampling@200
PlanSearch@200
0.0
GPT-4o-mini
GPT-4o
DeepSesk- Coder
Sonnet-3.5
Figure 38: Bar chart with REPEATED SAMPLING@1, REPEATED SAMPLING@20K, and PLANSEARCH@200, MBPP+.
Pass@k Scores by Method on HumanEval+
1.0
0.982
0.982 0.395
0,985
0.950
0.914
0.889
0.837
0.816
0.8
Pass@k
0.6
Repeated Sampling@1 1
Repeated Sampling@200
PlanSearch@200
0.0
GPT-4o-mini
GPT-40
Deep Seek-CCoo C2deerV2
Sonnet-3.5
Figure 39: Bar chart with REPEATED SAMPLING@1, REPEATED SAMPLING@200, and PLANSEARCH@200 200. on HumanEval+.
39

---

Published as a conference paper at ICLR 2025
M PROMPTS
M.I BACKTRANSLATION
M.I.1 BACKTRANSLATE SYSTEM PROMPT
You are an expert Python programmer. You will be given an algorithmic question (problem specification). You will return high-level, natural language solution to the question, like an editorial. You will NOT return any code. Be as creative as possible, going beyond what you think is intuitively correct.
M.1.2 IMPLEMENT BACKTRANSLATION IDEA
You are expert Python programmer. You will be given question (problem specification) and a natural language solution/tutorial that describes how to solve the problem. You will generate correct Python program that matches said specification and tutorial and passes all tests. You will NOT return anything except for the program inside markdown codeblocks.
M.2 REPEATED SAMPLING
You are an expert Python programner. You will be given question (problem specification) and will generate correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program inside Markdown codeblocks.
M.3 SIMPLE IDEA
You will given a competitive programming problem; please output high-level description of how to solve the problem in natural language. Below are examples:
Example input: PROBLEM DESCRIPTION HERE
Example output: EXAMPLE OUTPUT HERE Here is the competitive programming problem: PROBLEM TO SOLVE
Brainstorm a high-level, natural language solution to the problem above. Note that your inzuition may lead you astray, come up with simple, creative ideas that go beyond what you would usually come up with and go beyond your narrow intuition. Brainstorming solutions that do not seem intuitively correct IS CRUCIAL.
M.4 PLANSEARCH
M.4.1 PROMPT FOR OBSERVATION PART 1
You are an expert Python programmer. You will be given an competitive programming question (problem specifications will return several useful, non-obvious, and correct ioservations about the problem, like hints to solve the problem. You will NOT return any code. Be as creative as possible, going beyond what you think is intuitively correct.
You
M.4.2 PROMPT FOR OBSERVATION PART 2
You are an expert Python programmer. You will be given an competitive programming question (problen em speci ficatinittion) and
40

---

Published as a conference paper at ICLR 2025
several correct observations about the problem.
You will brainstorm several new, useful, and correct observations about the problem, derived from the given observations. You will NOT return any code. Be creative possible, going beyond what you think is intuitively correct.
M.4.3 COMBINING OBSERVATIONS
Here is sample prompt from the function with placeholders:
Here is the competitive programming problem:
Problem statement placeholder
Here are the intelligent observations to help solve the problem:
Observation placeholder
Observation placeholder Observation placeholder
Use these observations above to brainstorm a natural language solution to the problem above. Note that your intuition may lead you astray, so come up with simple, creative ideas that go beyond what you would usually come up with and exceeds your narrow intuition.
Quote relevant parts of the observations EXACTLY before each step of the solution. QUCTING IS CRUCTAL.
N A MODEL OF REPEATED SAMPLING: PASS@K
Consider a simplified model repeated sampling for code generation. Suppose we have a dataset D = (P..... P.} with I problems. For some problem P,, define the probability p: the probability that our code generation model solves the problem P: in one submission. The pass @k (Chen et al. 2021 Kulal al. 2019) metric (for problem P:) defined the probability that code generation model solves the problem P; at least once out of k submissions. Thus, we know the true pt of our model, we may compute our pass@k simply:
pass@k; = =1- (1- pt)x
(2)
pass@k Σ pass@k,/1
However, it turns out that for & > 1, the naïve estimator as seen in Equation biased, if we sample n, from our code model to solve P.. c; S nı are correct, and compute p; c//n4 n/4 (Chen et al. Instead, pass@k, is typically computed using the unbiased estimator:
2021
pass@k, =
Note that reporting pass@1 @k on a dataset where | is rather pointless, since pass can be derived using only pass@1, 1 and n2. Every curve, over suitable range of & values, will look like the S-curve seen in Figure 40 (as & is plotted on a log scale).
However, with datasets where / > models are able to differentiate themselves through larger k since the overall pass@1 @k is an average of these I curves. For example, for / = 3, it is less optimal to have solved probabilities of Set1 {0.001, (01100 0.7, 0.9) versus Set2 (0.05, 0.1, 0.25). in the regime of roughly & = 20 to 2, 000 (in which both converge to 1), even though Set1 has a pass@ I of 53% and Set.2 has pass @ of 1 13%. See Figure 41
41

---

Published as a conference paper at ICLR 2025
Pass@k for Solve Probability p=0.04
Pass@k
0.6
0.4
0.2
p-0.04
0.0
10"
10²
Figure 40: A simple pass@k 'S-curve' plotted with 1 (1 p)*, where p = 0.04.
Although not shown in the graph, Set2 converges close to 1 at roughly A: = 400, several orders of magnitude below 1. In addition, note that the slight notch seen in Set ls curve at large k is due the presence of low, but non-zero solve-rates, which can be seen in empirical pass @k curves later on. (These can be thought the beginning of the 'ramping-up' regime of the typical S-curves in Figure 40
Pass@k Across Different Solve Probability Sets
1.0
0.8
0.6
Pass@k
Average (Set
0.4
p=0.001 (Set 1)
p=0.7 (Set 1)
p-0.9 (Set
0.2
Average (Set 2)
p-0.01 (Set 2)
p=0.1 (Set 2)
p=0.25 (Set 2)
10a
10'
10a
k
Figure 41: Two @ass@k curves on a hypothetical dataset of length and the solve probabilities of Set are (0.001, 0.7, 0.9} and Set 2 are (0.05, 0.1, 0.25). Note that the pass@ is 53% and 13%. respectively. However, at roughly & = 20, Set 2 surpasses Set and within an order of magnitude, achieves pass @k of roughly 1.0.
42

---

Published as a conference paper at ICLR 2025
O BIASED ESTIMATOR FOR PASS @ K DUE TO NON-INDEPENDENCE OF PLANSEARCH
From a pure theoretical standpoint, the expression is biased (if using the same interpretation). but it still leads to a similar the set of samples we already generated contains least one success, (These given samples were generated by one run of PLANSEARCH.) As such, in theory, the estimator may be slightly biased in the PLANSEARCI case when computing true pass@k. @k In practice, we do not believe this to be large concern, especially as our primary results feature relatively large h: = 200.
the probability that a subset of size drawn from
0.1 MEASURING DIVERSITY
You are an expert Python programner. You will be given a competitive programming problem and two pieces of code which are attempts to solve the problem. For your convenience, you will also be given the idea for each code, summarized in natural language. You will be asked to answer whether the ideas behind the code are the same. You must ONLY output 'Yes.' or 'No.'
P COMPETITIVE PROGRAMMING
Competitive programming is popular subset of programming tasks that involve solving complex algorithmic reasoning. Typically, problems consist of a problem statement (written in natural language) P, with associated tests: (z), E m.. for which any solution must pass all of them.
The number of tests m depends the problem, but typically ranges on the order of 25 100. A small subset of the tests are typically given to the solver (we call these public tests) to use as validation that their program passes simple cases. The rest of the tests are hidden. Solutions to the problems must generally pass all the tests to be considered correct. Formally, we let f(z) denote the output of said code ran on input æ. The solution code is considered correct (passing) if and only f (xx) V: for all i E {1, m......
Each dataset consists of many (on the order of low-hundreds) independent problems, and models are evaluated on each of these problems independently.
Q OTHER RELATED WORK
Q.1 SEARCH IN CLASSICAL AI
Classical search algorithms like breadth-first search, depth-first search, and A* search have been widely used for pathfinding, planning, and optimization (Russell & Norvig. 2002). More advanced search techniques like Monte Carlo Tree Search (MCTS) have achieved remarkable success in domains like game playing, enabling superhuman performance in Go (Silver et al.) 2016; 2017). Poker (Brown& & Sandholm 2018 2019) and Diplomacy (FAIR et al. (022). More recently, scaling laws have been found for the performance of Al systems in board games, where ELO improves logarithmically with the amount of compute spent at inference (Jones 2021)
Q.2 SEARCH WITH LANGUAGE MODELS
Applying search on top of LL.Ms has been a topic of much interest, especially with an eye towards
code generation (Chen et al.) 2021 Li et al. 2022). Historically, methods such as beam search significantly improved performance for translation systems (Freitag & Al-Onaizan 2017). Closer to the present day, several recent works have explored repeated sampling (Chen et al. 2024 Brown et al. 2024, Bansal et al. 2024: Wu et al. 2024) as search method for improving performance. Repeated sampling method which directly generates candidate code solutions from the model many times at moderate to high temperatures in hopes that one of the resulting generations will be correct. However, although these works address the roughly linear increase in pass @ k with respect
43

---

Published as a conference paper at ICLR 2025
to log k, they only focus the most basic version of repeated sampling, without searching in idea space.
When combined with verifier, reward model, other filtering algorithm to select the best generation (in cases where pass@k @k not a viable metric due to lack test cases), is also known under the name of best-of-n sampling (Mudgal et al. 2024 Many works show somewhat good results under intelligent selection of such a filtering a algorithm (Chen et al.] 2022a 2024). Recently, several approaches have demonstrated the power of repeated sampling. For example, repeated sampling from a small model can sometimes outperform taking single sample from a large model on an equalized compute bases (Snell al. 2024). Unlike algorithms such as repeated sampling, which search over the output space, the key insight of PLANSEARCH is that it is far more effective to instead search plans over the latent idea space. By explicitly searching over different natural language plans before generating the code, we significantly increase the diversity of the final code outputs and thus, the resulting pass@k k scores for sufficiently large
R PUBLIC TEST FILTERING
Public test filtering is method which only chooses samples out of the original pool n which pass the public tests. This is particularly useful in settings such as code deployment where exccuting the full suite of tests may be computationally costly otherwise undesirable (e.g. in coding contest where every incorrect submission is penalized). Thus, instead of submitting all n codes, after public test filtering, only codes e; would be submitted such that o: (x(gg) = y/ for all j E {I,..., u), where o, (ar) refers to the output from running the code on some input æ. The primary effect of public test filtering is to shift the pass @K k curve leftward, since public test filtering will discard low quality candidate solutions that either fail to compile or fail elementary test cases for the problem.
All problems in MBPP+, HumanEval+, and LiveCodeBench come with a few public tests which are usually used to sanity check any submissions. We can further improve performance by filtering on these public tests before final submission, as described. Applying public test filtering reduces the number of samples to achieve the same accuracy by tenfold: PLANSEARCH to achieve a 77.1 % accuracy on LiveCodeBench after just 20 submissions (pass @ 20) compared to a pass @ 200 of 77.0% without using public filtering (see Figure 4) We provide full results for the other datasets in Appendix B
MATHEMATICS AND EXAMPLES OF THE DIVERSITY MEASURE
While our choice of diversity metric is intuitive, one should note that there number of intriguing details that result from our definition.
For example, it is the case that with & unique ideas and n samples of each idea, respectively (for total of kn total generated codes), we achieve a diversity score approaching (I: 1)/k.
For quick proof, suppose that there are i cliques, each of size. Each clique represents a unique idea. We wish to capture the number of unfilled edges over the number of possible edges as our diversity score:
( (n)2
(I: - 1)m
(5)
km
kn - 1
which converges to k-1 " as n. grows large.
Our formulation
intuitive than other proposals, such as that simply counts how many unique ideas k lie within a pool of size n to compute k/n as the diversity score.
For instance, suppose there are only unique ideas, clique of which is of size 2n - 1. and the other only output once. The simple proposal would compute both the diversity score of this uneven group and that of an even group (where both ideas are output n times) to be 2
However, our score would compute the even group to be
n 2n-1 and the uneven group as:
1
2n
1
1
(6)
2n
2n
2n.
1
44

---

Published as a conference paper at ICLR 2025
Instead of counting edges, compute the probability that two randomly selected outputs have similar idea to each other, which is another interpretation of our diversity score.
It seems clear that than a case with n instances of both idea I and idea 2. A naive proposal may score these two as being the same diversity, whereas score scores them 1 1/n and roughly 1/2, respectively.
with 2n 1 instances of idea and 1 instance of idea 2 is 'less diverse'
T LIMITATIONS AND FUTURE WORK
While PLANSEARCH substantially improves diversity over idea space at inference-time, fundamen- tally, improvements in diversity should come the post-training stage, like with methods such as ol Op (2024). This likely requires re- re-imagini the post-training pipeline for LLMs around search, instead of the current paradigm optimized for single correct response. We optimistic about future work in designing improved post-training objectives to maximize both quality and diversity, while specifically optimized
inference-time compute maximum effectiveness.
PLANSEARCH and DEARCH tradeoff' a slight deterioration of pass @ performance for large improvement in pass pass@k @k performance. However, in many such cases outside of code generation, is infeasible to run an LLM-based model for more than a few attempts at most, For example, in Figure PLANSEARCH does not significantly outperform REPEATED SAMPLING until &: 2
Fortunately, many filtering algorithms exist, which mitigates this tradeoff by implicitly bringing pass@k @ass@k (for high k) pass@ @ (or lower i.c. shifting the original pass @k curve leftward. Even the simplest tntering-publec test filtering-improves PLANSEARCH'S pass@1 significantly above REPEATED SAMPLING'S 's pass@1 1, which continues as increases. Moreover, most to almost all base models with public test filtering outperform their instruct model variants at pass @ 1, matter the dataset (see Appendix D). Since base models' pass@1 known to be worse than instruct models to trade off for higher diversity, we suggest a new paradigm- developing search algorithms which tradeoff pass@1 1 performance for much stronger pass @k performance, then filtering the generated solutions to extract the pass @k k back into pass@1.
With good filtering methods, which we demonstrate can be simple in nature, pass @k, for medium k be effectively brought down to pass@) 1, emphasizing similar paradigm of increasing diversity, then strengthening existing filtering methods, even for domains outside of code generation that are of scope of this paper.
A natural extension of this work is training the underlying model itself on successful plans and code solutions obtained from PLANSEARCH. This has the potential to distill the pass into the pass@1 1 1-without inference-tima methods like filtering- reducing the likelihood of the model going down unfavorable branches of the search tree. We believe that such training is likely to significantly improve the model and look forward to future work in this direction.
In terms of methodological improvements to PLANSEARCH, PLANSEARCH currently searches all leaf nodes in the search tree uniformly. Because of this, it becomes quickly intractable to go further than a few levels deep, and in our experiments, we are only able to go two levels down the tree. Several approaches based on Monte-Carlo Tree Search (MCTS), such as Tree of Thought Yao et al. (2023a) or Reasoning as Planning (Hao et al. | 2003a)), have suggested that some form of dynamic pruning and expansion of nodes can be very helpful. We are optimistic that PLANSEARCH can be further improved by such methods.
Furthermore, PLANSEARCH is fairly elementary method taking advantage of the paradigm that searching over a conceptual or idea space is an effective method to improve diversity, and thus, downstream task performance. It completely feasible to search at an even higher level of abstraction than observations, which may be used to inject even more diversity into the final generated outputs.
U COMPARISON WITH AGENTIC MODELS
We also baselines with basic 'agentic' model which is allowed code execution environment with the given public tests. To do this, it first generates code similar to REPEATED SAMPLING, then runs said code the given public tests. If the code does not pass, the error is returned the model
45

---

Published as a conference paper at ICLR 2025
and the model is prompted fix the code. This process continues until either the model successfully passes the public tests or it reaches a certain iteration limit T.
We compare such model with our basclines well. For all comparisons, set T 10. Note that the agentic models do have access to a code exccution environment, which is an inherently different paradigm than all of our baselines. Thus, we do two comparisons.
We first compare the last submission of the agentic model (which is either passing public tests or does complete in the allotted iteration limit) versus the cublic-filtered versions of each of our baselines. The rationale behind this is that in both methods, all the faulty submissions which do not pass public tests are discarded, and both have access code execution. The results seen in Figure 42
@ass@k vs k for Methods with Public Filtering on LiveCodeBench
GPT-4o-mini
GPT-4o
0.70
0.70
Filtering
Submission
No Public Filtering
0.65
0.60
0.60
0.50
0.50
0.45
0.45
Repeated Sampling
IdeaSearch
0.40
0.40
PlanSearch
Public Test Agent
0.35
0.35
10
10
Figure 42: Pass @k curves comparing the basic agentic model's last submissions only on Live- CodeBench with up to 20 completions and public test filtering.
Next, instead of stopping when successful, the agentic model continues iterate even when 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 total iterations instead. We compare all submissions this agentic model versus the default versions of each of our baselines, since the submissions of both methods are not guaranteed to pass public tests. Note that this setup is still slightly unfair for our baselines, since the last submissions of the agentic model will have already iterated and extracted sufficient signal from public tests, whereas our baselines do not use any test execution signal at all. The results can be found in Figure 43
46

---

Published as a conference paper at ICLR 2025
Pass@k vs k for Methods on LiveCodeBench
GPT-4o-mini
GPT-4o
0.70
0.70
0.65
0.65
0.60
0.60
0.55
0.55
0.45
0.45
Repeated Sampling
IdeaSearch
0.40
0.40
PlanSearch
Public Test Agent
0.35
0.35
10
100
10
100
k
k
Figure 43: Pass@k curves comparing the basic agentic model with all T generations on Live- CodeBench with up to 200 completions.
47


Reviews:
[{"review_id": "yuwlM8N4HP", "reviewer": "Reviewer_DNQT", "summary": "This paper investigates the effect of inference-time search in LLMs applied to contemporary coding benchmarks. The investigations start by asking about the appropriate level of abstraction at which to perform search, and identifies \"natural language plans\" as a useful level through clear experimentation. They introduce a new inference-time search algorithm for LLMs in code generation called \"PlanSearch\". The algorithm appears general enough to be applied to other domains, though the paper does not pursue this. In the main experiments, the authors find that PlanSearch improves LLM performance on coding benchmarks significantly, and by a large margin compared to standard inference-scaling methods (RepeatedSampling). Further experiments identify \"idea diversity\" as the key driving factor for PlanSearch's success, with their custom measures of idea diversity being predictive of downstream performance. The authors further discover that instruction-finetuned models can have less diverse ideas than base model variants, raising important questions around the best way to perform LLM post-training.", "questions": "- > Interestingly, we find that IDEASEARCH performs somewhat better, which we speculate comes from differences in splitting solution sketch into two model responses, instead of doing both chain-of-thought and code solution in one model response.\n\n  This is surprising. Is the only difference here that a new model response comes as a new \"message\" in the chat LLM API?", "limitations": "", "rating": 10, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "There were a great many things I liked about this paper, and I learned a lot from its experiments.\n- Figure 1 is very compelling and sells the main takeaway immediately: Searching over *ideas* in natural language (PlanSearch) is a significantly more effective way to spend inference-time compute than naive repeated sampling of direct solutions.\n- The broad strategy of \"generate plan first then generate the solution based on that\" is highly applicable to other domains; PlanSearch can be used to generate plans for anything, and could plausibly improve performance across many domains besides code generation.\n- Useful takeaway that performance can be seen as a function of diversity of ideas. This is an important lesson for the field which is not currently prioritizing LLMs' diversity of ideas, but should take idea diversity more seriously given this evidence.\n- Interesting to see that instruction-tuned models can sacrifice the diversity of ideas present in base models, Figure 30 is a great figure illustrating this effect! This line was quite surprising to me:\n  > in many cases, despite instruction tuned models outperforming base models by large margins on a single sample regime (pass@1), this trend disappears—sometimes even reversing—on a multi-sample regime (pass@k). We refer to Figure 30 as an example of this phenomenon\n\n  and this further line in the Conclusion is clear-sighted in pointing out the implication of the problem of losing diversity during post-training:\n  > while PLANSEARCH substantially improves diversity over idea space at inference-time, fundamentally, improvements in diversity should also come at the post-training stage\n- Section 3 builds a great foundation to motivate why we care about searching over idea sketches: Starts by considering the correct layer of abstraction to search over, run experiments showing the power of the right \"idea sketch\". Figure 3a and 3b are great.\n- Interesting to see that o1-mini, a model which itself already scales inference-time compute, benefits less from this method (which makes sense, but good to know).\n- Impressive thoroughness in sharing results, with >40 figures throughout the paper and appendices!\n\nOverall, the paper is very well-written, adds new insights to an emerging topic (diversity and search) with important ramifications for the field, and is very thorough with well-designed experiments, with many interesting results.", "weaknesses": "Few complaints overall. One minor weakness that doesn't cut against the broader claims and lessons of the paper:\n- The actual search algorithm of PlanSearch in Section 4.3 feels somewhat arbitrary. If the goal is simply to generate diverse plans, I suspect there will be many other different ways to prompt LLMs to generate diverse ideas besides the specific PlanSearch algorithm as described. Did the authors try other algorithms / prompts? Would have been nice to see the failure cases and understand why this specific design was selected.\n  - Ablations in Appendix H address this complaint somewhat, but still assumes the same algorithm structure and is mostly just a \"hyperparameter search\" which has small effect on the results.\n  - To give a concrete example of what I imagine could be a completely different approach: directly prompting models with previously sampled ideas, and asking models to generate different plans.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J39LffYkwI", "reviewer": "Reviewer_CksG", "summary": "The authors describe a new method for code generation (for short problems). It involves generating a set of observations about the problem (in natural language), constructing plans to solve it and then generating solutions.", "questions": "See weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors achieve impressive results on three benchmarks, e.g. they make Claude 3.5 Sonnet achieves a pass@200 of 77.0% on LiveCodeBench.\n2. They provide an interesting motivation for their work: showing that idea generation, not idea execution is the bottleneck of LLMs and they the solutions they generate lack diversity. It's interesting that \"a correct sketch is sufficient to produce the correct final solution with relatively high accuracy, even only after 10 tokens of backtranslated solution.\" and that conditioning on a correct idea or bad idea polarizes the score distribution that much.\n3. They provide and elaborate scaffolding for generating solutions.\n4. The conducted experiments are sound. I like showing scaling of pass@k as a function of k. I like that all frontier models as well as open-weight models were used in experiments.\n5. Results are complemented with an interesting analysis of the role of diversity (Fig. 5)\n6. The paper is clearly written", "weaknesses": "1. 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).\n2. 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.\n\nMore specific points:\n3. 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]. \n4. 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.\n\n\n[1] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling\n[2] An empirical analysis of compute-optimal inference for problem-solving with language models\n[3] OpenAI O1 system card\n[4] AI Agents That Matter", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nOhDe4d2Am", "reviewer": "Reviewer_KeqM", "summary": "The paper proposes a new methodology to improve language model test time scaling efficiency. Their study shows that simply sampling more outputs from the same input prompt will have limited diversity, thus limiting the improvement of the model performance. To avoid this issue, they propose to sample the natural language plan of the solution first and then ask the language model to generate a solution based on the plan. They propose an effective method for sampling various plans, and experiments show that the proposed method improved the model accuracy in best-of-n settings.", "questions": "Please refer to the weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written. Analysis and ideas are presented progressively, making it easier to follow. The proposed method is well-motivated by the polarized results of different solution sketches. The experiment results also show clear improvement over the baseline model and methods.", "weaknesses": "1. 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?\n2. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)