SFS: Smarter Code Space Search improves LLM Inference Scaling
Authors: Jonathan Light
Yue Wu
Yiyou Sun
Wenchao Yu
Yanchi Liu
Xujiang Zhao
Ziniu Hu
Haifeng Chen
Wei Cheng
Venue: ICLR 2025 Poster (2025)
Keywords: LLM
code generation
optimization
search
agent
inference scaling
black-box optimization
exploration-exploitation
tree search
Monte Carlo Tree Search (MCTS)
evolutionary search
large-scale inference
solution diversity
textual optimization
prompt engineering
reinforcement learning
metaheuristic search
computational efficiency
program synthesis
Primary area: applications to computer vision, audio, language, and other modalities
TL;DR: We frame code generation as a black-box optimization problem over textual space and introduce optimization-inspired search techniques to enhance LLM inference scaling, achieving state-of-the-art performance with fewer iterations.

Abstract: We frame code generation as a black-box optimization problem within the code
space and demonstrate how optimization-inspired techniques can enhance inference
scaling over text. Based on this perspective, we propose **SCATTERED FOREST
SEARCH (SFS)**, a novel approach that improves solution diversity during evolutionary search,
thereby avoiding local optima. Our theoretical analysis illustrates how these
methods improve exploration and enhance efficiency. Extensive experiments
on *HumanEval, MBPP, APPS, CodeContests,* and *Leetcode* reveal significant
performance gains. For instance, our method achieves a **pass@1 rate of 67.1% on
HumanEval+** and **87.2% on HumanEval with GPT-3.5**, marking improvements of
**8.6%** and **4.3%** over the state-of-the-art, while also halving the iterations needed
to find the correct solution. Furthermore, our approach scales more efficiently
than existing search techniques, including **tree search, line search,** and **repeated
sampling (Best of N)**.

Published as a conference paper at ICLR 2025
SFS: SMARTER CODE SPACE SEARCH IMPROVES LLM INFERENCE SCALING
Jonathan Light*), Yue Wu?, Yiyou Sun?, Wenchao Yu?, Yanchi liu S Xujiang Zhao?, Ziniu Hu", Haifeng Chen², Wei Cheng
Rensselaer Polytechnic Institute, Princeton University, NEC Laboratories America, 4XAi 11j54rpi.edd edu
ABSTRACT
We frame code generation as a black- box optimization problem within the code space and demonstrate how optimizatiooninspire techniques can enhance inference scaling. Based on this perspective, we propose SCATTERED FOREST SEARCH (SFS), novel approach that improves solution diversity and better exploits feed- back during evolutionary search. Our theoretical analysis illustrates how these methods help avoid local optima during optimization. leading to more efficient exploration, Extensive experiments on HumanEval, MBPP, APPS, CodeContests, and Leetcode reveal significant performance gains. For instance, our method achieves pass @1 rate of 67. 1% on HumanEval+ and 87.2% on HumanEval with GPT-3.5, marking improvements of 8.6% and 4.3% over the state-of-the-art, while also halving the iterations needed to find the correct solution. Furthermore, our approach scales more efficiently than existing search techniques, including tree search, line search, and repeated sampling.
INTRODUCTION
Code space optimization
Recent work highlights the effectiveness of scaling infer- ence compute over training compute (Snell et al., 2024; Brown al., 2024; Gandhi et al., 2024). The most com- mon approach by far is to repeatedly sample from the LLM with the same prompt and filter out the best response using verifier, also known best-of-N sampling (Cobbe et al., 2021; Lightman et al., 2023). Methods that leverage feed- back from the verifier to revise previous solutions in line or tree-like fashion have also been explored (Feng et al., 2023; Chen et al., 2024a). Code generation is one such setting where scaling LLM inference through repeated sampling has also been effective (Wang et al., 2024; Chen et al., 2022).
?
?
?
passed
passed
?
tests passed
Inference scaling is effective because, given enough at- tempts, the LLM is likely to sample the correct solution eventually (Snell et al., 2024; Brown et al., 2024). There- fore, generating diverse solutions is crucial for effective exploration. Our experiments show that existing methods such as best-of-N (BoN) and tree search often produce similar solutions, leading to insufficient exploration of the solution space (refer to Sec.3.5). Hence, a sampling and testing approach that balances exploration and exploitation can greatly improve inference scaling,
Figure 1: 2D Visualization of Code Space represents each point as a possible code solution. The goal is to efficiently search this space for the solution with the best performance, defined by the number of unit tests passed, as indicated by the contours above.
To tackle this issue, we propose framing solution generation as a black-box optimization problem (Golovin et al., 2017) (as illustrated in Figure 1), in which validation tests serve as the black box and the LLM functions the optimizer (Yang al., 2024). Drawing from optimization theory, develop SCATTERES FOREST SEARCH (SFS) to efficiently search for code solutions that successfully pass the maximum number of validation tests through generating and evolving (refining) solutions.
Work done during the internship at NEC Laboratories America. "CCoresponding author.

---

Published as a conference paper at ICLR 2025
Our method: 1) enhances exploration by enabling the LLM to propose diverse search directions, 2) improves exploitation by leveraging feedback and prior search experiences, and 3) initializes various random seed code solutions to ensure broader search coverage.
Specifically, SFS contains three key techniques. SCATTERING is a novel technique that dynamically varies input prompts when sampling from LLMs, driving more diverse and exploratory outputs. In SCATTERING, the LLM suggests different textual optimization directions and steps, analogous gradients in numerical optimization, before advancing towards a new solution. During tree search refinement, SCATTERING effectively perturbs or mutates previous solutions, resulting in an evolutionary search process. We further propose FORESTING, the tree search equivalent of multi-start optimization, where SCATTERING plays a crucial role in diversifying initialization seeds, ensuring they are well-distributed throughout the search space. This enhances the breadth of exploration while effectively mitigating clearly incorrect solutions, such as those with syntax errors.
Scaling curves for different methods
Additionally, drawing inspiration from ant colony optimization and particle swarm opti- mization, we introduce SCOUTING to enhance SCATTERING by sharing feedback and experi- ences across search branches. When one branch discovers positive (or negative) results by fol- lowing a specific textual direction, this infor- mation is relayed to guide future search steps, encouraging or discouraging exploration in that direction. Consequently, SCOUTING improves exploitation by intensifying the search around promising textual directions. We also provide a theoretical explanation demonstrating how our methods enhance exploration and circumvent lo- cal search regions when sampling from I.I.Ms.
0.325
Ours
BeN
Line
0.275
Tree (MCTS)
Proportion
0.225
0.200
0.175
6 Number solutions generated
10
Figure 2: Scaling curve for different search methods. We run each method for 10 iterations total using gpt-3. 5 5-turbo on APPS and re- port the proportion of problems where the correct solution has been discovered each iteration.
Our parameter-free method is simple yet ef- fective. It does not require additional training or labelled data, yet achieves great performance. As illustrated in Figure 2, our method able to discover the correct solution significantly faster than the other approaches. We evaluate method on five different code generation benchmarks, HumanEval (Chen et al., 2021) MBPP (Austin et al., 2021), APPS, CodeContests, and Leetcode, showing increased inference time performance across the board, as well as better inference scaling. Our method also outperforms prior state-of-the-at techniques on HumanEval+ and MBPP+. Additionally, it generates higher solution diversity than previous methods, hence balancing exploration and exploitation, resulting in faster discovery of correct solutions and better scaling.
To sum up, our contributions are as follows:
We frame code generation as a black-box optimization problem over the code/text space and demonstrate how gradient-free optimization techniques be adapted to enhance inference scaling. This perspective highlights the importance of balancing exploration and exploitation in search-based code generation and the need for diverse generation.
We introduce SCATTERED FOREST SEARCH (SFS), which applies optimizationninspires search techniques to improve exploration and avoid local optima. Specifically, SCATTERING and FORESTING enhance search diversity through textual optimization and seed initialization, while SCOUTING refines search efficiency by leveraging shared insights across search trajectories.
We empirically validate our approach across multiple code generation benchmarks, including Hu- manEval, MBPP, Leetcode, APPS, and CodeContests, demonstrating significant improvements in accuracy, scalability, and solution diversity over existing search methods.
BACKGROUND
2.1 PROBLEM DESCRIPTION
In a program synthesis task æ = (p. H), the solver is given a prompt p in natural language, which asks the solver to write code for some object The goal is to complete the code implementation of
2

---

Published as a conference paper at ICLR 2025
Figure 3: Overview of prior methods used for code generation with LLMs. Points represent solutions. Hexagons represent initial solutions. Star represents the final selected solution.
search
Tree search
paosd
wath passd
paoed
wal paisud
2 wit pasud
wal passed
pound
Repeated sampling generates multiple solutions using the LLM without leveraging feed- back from previous iterations.
Line search rigidly exploits feedback and cannot revert to previous solution if a change worsens the outcome
Tree search is more flexible but still lacks sufficient explo- ration, the generated solu- tions tend to very similar.
such that it passes all the hidden tests H. The solver is allowed to see the hidden tests. Sometimes, the solver is also given validation (visible) tests V that they can test their solution 8 on before they validation tests V.
submit it for evaluation on the hidden tests H. They can also generate their Usually both hidden and validation tests are in the form of a set of assert statements that test the functionalities of A description of one such code generation task is shown in Appendix B.
A solution s' is said to be correct if it passes all the hidden tests H. The solver is allowed submissions [s] to the hidden tests. at least one submission passes all the hidden tests, then the task is considered to be solved. Given a set of tasks X, the proportion of tasks (p. H) E X that are solved by the agent is called the pass rate (Chen et al., 2021).
2.2 PRIOR METHODS
A couple of different inference time methods have been tried in prior works to enhance the code generation capabilities of the I.L,, which are shown in Figure 3. We elaborate more on the pros and cons of each method under code space optimization framework below:
Best N (BoN), or repeated sampling, involves sampling multiple independent solutions [s] s LLM(p) from a language model using the same prompt p. The best solution s* is then selected based on a verifier, commonly the number of validation tests passed (Li et al., 2022: Chen et al., 2024a).
Line search begins by sampling an initial seed code previous solution s,-1 based on its test feedback f:-1 (Shinn et al., 2023; Madaan et al., 2023). This iterative self-refinement leverages test execution feedback to guide the model toward sampling successful solutions, i.c. 8; ~ SIM(p)s;-1) fi-1). However, line search limited by its rigidity requiring improvements the most recent solution, even if the latest edits incorrect. Thus, struggles to effectively explore the search space and is more likely to get stuck local optima.
T.T.(p).. It then iteratively refines the
Tree search overcomes the rigidity of line search by generating multiple child solutions for each parent solution, utilizing tree-structured exploration methods such as BFS, DFS, and MCTS (Feng al., 2023; Chen al., 2024a; Hao et al., 2023; Yao et al., 2023; Zhou al., 2024; Tian al., 2024). Given parent solution 8; and its feedback ft. the LLM produces & child solutions 8;0, 8;1, ..., 8ik- Although higher temperatures can produce diverse solutions, resemble each other because they originate from the same prompt (refer to Sec. 3.5). Consequently, tree search still faces challenges in fully exploring the search space.
practice these solutions often
METHODOLOGY
Our method incorporates three optimization inspired techniques to enhance both exploration and exploitation of tree search (MCTS) using L.LMs. More details in Appendix C. with pseudocode.

---

Published as a conference paper at ICLR 2025
Figure 7: Core techniques used by SFS. Points represent solutions. Hexagons represent initial solutions. Star represents the final selected solution.
Scottering
Foresting
Scouting
Saccess dirazs
paosed
wath paued
paoed
passed
wil passed
2 wit pasund
wil passed
posod
SCATTERING encourages uree search to explore more diverse solutions by using varied directional prompts for each branch or seed solution
FORESTING boosts explo- ration by performing tree search dynamically from mul- tiple random seed solution starting points
SCOUTING shares success- ful search directions across branches of the search tree, providing general insights to better exploit feedback
3.1 TREE BRANCII SCATTERING
In tree search, children solutions of the same parent solution tend to be highly similar to one another since the LLM given the same prompt generate the children. We encourage more exploration when generating children solutions by querying the LLM to generate possible improvement directions [d,, first. The LLM is then instructed implement a specific direction d, for each child s;y that generates from parent 8;. This helps explore different, often orthogonal, improvement directions that help us explore wider region of the search space, similar to trust-region methods numerical optimization (xiang Yuan, 2015). We refer to this technique SCATTERING the tree branches.
feedback from validation tests
propose new textual directions using LLM
choose direction implement when branching
Example SCATTERING Directions
Thoughts: The feedback suggests that the main problem is that the function is returning the first element of minn k and max-k instead the catire lists.
Direction Modify the return statement to return min and max instead (min k II0.. max x[0], min k 11. max-k[ [-1]). This will ensure that the function returns the entire lists of minimum and maximum k elements.
Update the function handle the when greater than the length of the tuple. In this the entire sorted tuple as both the minimum and maximum clements.
Direction 2:
Furthermore, we employ MCTS and utilize the UCT formula (Eq. I) to dynamically select directions for exploration, as illustrated below
UCT(s, = (s,, + In (E, n( b))
(I)
n18, d)
where c is the exploration parameter, n(s, d) is the number of visits of direction at solution s, and (s,, d) is the estimated v-vulue which is updated via backpropogation follows:
Q(s,, d [t+1) + (1 Q( (1 + a, max Q(s;, d (+), Q(1 d.42)
(x42)(+11) (++1))
(2)
where an is the weighted average parameter that depends n( d). The backpropogation occurs along the entire MCTS simulated trajectory ((++1) (g. d1 82, ...,. 8 d s_1), where the q- value for the penultimate state s is updated using the value of the final state (% of validation tests passed) (( d_,,,,,,,,__ ((+1)
v(s-)). We take the max of Q( 1 and ((: d to ensure that if the next solution is worse, the current solution can be used instead. This approach dynamically selects which direction to explore, prioritizing more promising parent solutions s, exploring all directions parent solution s; Using UCT to select distinct actions has been effective in balancing exploration and exploitation in other settings (Browne al., 2012).
4

---

Published as a conference paper at ICLR 2025
3.2 FOREST SEARCH AND FOREST SCATTERING
Iterative refinement faces the challenge that very faulty initial seed solution may be difficult to correct effectively during the search process. An intuitive approach to address this issue is to generate multiple seed solutions and perform tree search from each one. refer to this technique as FORESTING, in which generate seed solutions [s], and dynamically select which seed function to evolve from using the UCT formula (Eq. 1). Specifically, for each MCTS simulation, we select seed function with the highest UCT value and conduct the simulation from that point. This closely resembles random seed initialization, a widely and effective approach in optimization literature.
Similar to branch SCATTERING, forest SCATTERING by providing the LLM with different instructions prior to generating solutions. We investigate the impact of various SCATTERING instructions on performance in Sec. 3.5.
also promote more diverse seed solution generation through
Example Forest Seed Instructions
Seed instruction Write in modular and extensible manner, casuring each function and cun be easily extended or modified without impacting other parts of the system. Prioritize cleur interfaces and loose coupling between components.
single responsibility
Seed instruction 2: Focus on writing highly efficient code with minimal memory usage and fast execution times. Use data structures and algorithms optimized for performance, and consider edge that could lead bottlenecks. Prioritize speed and efficiency over rendability.
Seed instruction 3: Prioritize readabilit and maintainability in your code. Write clear and descriptive comments, use meaningful variable and function names, and structure the code in a way that is easy others to understand and modify, Follow established coding standards and best practices.
3.3 BRANCH SCOUTING
Inspired by optimization techniques like Ant Colony Optimization and Particle Swarm Optimiza- tion, we improve solutions by leveraging insights from effective improvement directions. After generating
solution 8-1 using improvement directions d 8-2, we provide feedback f-1 to the LLM to assess its effectiveness and derive general insights. These insights are stored in global memory and included in future prompts, enabling shared knowledge of effective improvements across branches. This enhances feedback exploitation and strengthens our SCATTERING technique.
Example SCOUTING Insights
Insight 1: Modify the return statement to return min-k and max-k k instead of (min-x[0], max-k [01. min-k I-21. max X. 1.) This will ensure the function returns the entire lists of minimum maximum k elements.
Update the lunction hamdle the case when greater tham the length the tuple. In this case, return the entire surted tuple both the minimum and maximum elements..
Insight 2:
use insights to gener- ate directions
see if the direction
update insights based on feedback
worked or not
3.4 A THEORETICAL PERSPECTIVE
The proposed techniques- STATERNG and FORESTING can be analyzed via the Markov chain theory. particularly focusing on the concepts of diverse transition kernels, conductance, and mixing times (Levin & Peres, 2020). We can define the search strategy Markov transition kernel P(s, s') which denotes the probability of generating a new solution s' given the current solution 8. A chain of self-refined solutions 80; 81, 82, are generated following the transition kernel P.
In previous methods including line search and tree search, the transition is realized by an LLM π that conditioned on the previous solution s and the feedback f F((s), denoted by aTss (, f). The transition kernel is
Pprevious (8, 8') Te(8'1x F(x)).
where we use Te to emphasize that the LLM я is prompted to output code. We know T(c) can be extremely concentrated and outputs highly similar solutions.
With SCATTERING, we first sample an improvement direction generated by the LLM with prompt (+|8, F())). And then prompt L.MM to generate the next solution s' given the current solution
5

---

Published as a conference paper at ICLR 2025
the feedback f = F(s), and the improvement direction d. The transition kernel is PscAtteRiNa (s, s')sss)==)))
Σ (d F( ((s))T=(ss)l) F(s).d),
where we is still an extremely concentrated policy and outputs highly similar solutions. However, we have text- based "reflection" Te (dlss, F()) that can generate highly diverse improvement directions. In practice, we can observe that indeed the directions are highly diverse.
In Markov chain theory, diverse transition kernel increases the probability of moving between different regions of the state space (denoted by S), enhancing the conductance & the chain:
+ p ExEs, ( P(8,
((S)
where S' is subset and is the stationary distribution. More details in Appendix M.
Higher conductance improves the spectral gap 7, which is inversely related to the mixing time of the Markov chain (see Cheeger's inequality) (Levin & Peres, 2020), reducing the likelihood of the chain getting trapped in local regions. More formally speaking, for a local region S, the previous methods (equation 3) rely on directly generating new responses that can easily stuck in the local region S (P previous (s, s') = 0 when s E S and s' é S, thus the conductance T is near O). While our SCATTERING search (equation 4) can generate highly diverse directions d and lead new solutions s' out of the local region S (P (PSCATTERIN
> 0 if some d gives correct direction).
3.5 EMPIRICAL VALIDATION
Pass@k rate for different seed themes
We varied the types of seed instructions used to generate seed code during BoN sampling to validate the effects of increasing solution diver- sity with SCATTERING. In the Jabberwocky setting, the model was prompted with differ- ent lines from the humorous nonsense poem "Jabberwocky" before generating seed code. In the Style setting the model was prompted with different coding style instructions such as writ- ing code in "highly modular way' or 'fo- cus on brevity and clarity'. In the Role set- ting, the model was prompted with different software engineer personalities such as 'You innovator.'
Role
0.85
Style
Jabberwocky
None
0.80
Pass0
0.70
2
10
Number submissions
Figure 11: Pass rate for repeated sampling with different initialization seed types Hu- manEval using creasing seed variety with SCATTERING signifi- cantly improves both Pass @k k rate and scaling.
'You are perfection- ist'. All input prompts were LLM generated by gpt-3. 5urbo around common theme.
In-
We present the pass@k k performance of these seed generation styles in Figure 11, with detailed performance metrics in Tables and 19. This includes: I) the pass @ any rate, which measures the proportion of problems where the correct solution was found at any point during the search, 2) the mean validation score, averaged across all candidate solutions generated (Eq. 12), and 3) the mean BERT cosine similarity between embeddings of candidate solution pairs, averaged over all problems. Embeddings were taken using CodeBERT, pretrained model for understanding code semantically (Feng et al., 2020).
embed( ()) embed (s')
Mean BERT cosine similarity
Σ (p.
X
Sp1( 1)
lembed $) embedd |
8.8 ES
In addition to the metrics discussed previously, also include other similarity metrics such tf- idf similarity, which measures the average cosine similarity between tf-idf vectors, the Levenshtein similarity, and the token sequence similarity. See App. for more details, including examples.
As shown in Table 1, "Role" and "Style" performed best discovering the correct solution. Surpris- ingly, even unrelated prompts, like lines from nonsense poems, boosted performance. Overall, all SCATTERING themes reduced solution similarity while maintaining comparable validation scores, demonstrating the effectiveness of using varied inputs during the search process.

---

Published as a conference paper at ICLR 2025
Table 1: Effects of different seed instruction SCATTERING themes. 10 seed solutions were generated using gpt-3. 100-3.5tttu 5-turbo for each theme, and we filtered the seeds using 6 generated validation tests select the best one submit for evaluation on the HumanEval benchmark.
Seed theme
pass
pass @ any
tf-idf sim.
BERT sim.
lev. sim.
seq. sim.
val. score
None
72.5
75.0
0.9013
0.9976
0.8971
0,9361
0.7786
Jabberwocky
74.4
81.9
0.7559
0.9944
0.7749
0.8444
0.7658
Style Role
79.4
88.1
0.6826
0.9929
0.7119
0.7504
0.7548
81.9
87.5
0.7734
0.9957
0.7907
0.8323
0.7649
EXPERIMENTS
We demonstrate that our search method outperforms prior methods by showing that it 1) achieves higher accuracy, 2) finds correct solutions faster and scales better, and 3) explores more diverse solutions without sacrificing exploitation of good ones.
4.1 EVALUATION BENCHMARKS
We evaluate our method on several popular code generation benchmarks. HumanEval consists of 164 human- genaa-geeerraed Python questions (Chen al., 2021), and MBPP includes 399 problems (Austin et al., 2021). The original sets included only 3 to 8 hidden tests H. which researchers found inadequate for thoroughly evaluating correctness in edge cases. Additional hidden tests were added, resulting in the HumanEval+ and MBPP+ sets (Liu et al., 2024a).
Both APPS (Hendrycks et al., 2021) and CodeContests (Li al., 2022) feature challenging code competition problems. From the 10,000 problems in APPS, randomly sample 200 for evaluation due to budget constraints. We adapt the competition format both datasets to resemble the HumanEval format for Python evaluation. Leetcode (Guo et al., 2024) includes recent problems scraped from the website, ensuring that LLMs released before July 2023 have not been trained on these data.
4.2 ACCURACY
We conduct experiments on a variety of code generation benchmarks as shown in Table 2, where we that our method achieves higher pass@1 rate than other search methods and the base accuracy (i.e., evaluating the first solution that the L.M model generates). Methods were given the same search budget (10 solutions), they used 6 self-generated validation tests.
Table 2: Performance of our method compared to prior search methods. Pass reported here. Both solutions and validation tests were generated using
performance
Method Benchmark
HumanEval+
MBPP+
Leetcode
APPS
CodeContests
Base
58.5%
64.9%
30.0%
16.0%
1.82%
Line
53.0%
61.2%
28.9%
14.5%
1.21%
Tree (MCTS)
59.8%
65.4%
31.7%
18.0%
2.42%
Best of N
65.2%
64.4%
33.3%
19.5%
1.82%
Ours (SFS)
67.1% %
65.7%
36.7%
20.5%
4.24% %
We also measure the proportion of problems where the correct solution was found (pass@ @ any) any point during the search process, as shown in Table We evaluate on HumanEval and MBPP rather than their plus versions due to computational constraints. HumanEval+ and MBPP+ contain 80x and 35x more tests, respectively, which makes it challenging to verify each generated solution. The pass @ any rate is higher than pass@1 @1 because, even if the correct solution is found, inaccurate validation tests may lead the algorithm to submit an alternative solution. Our method achieves significantly higher pass @ any rates and demonstrates greater improvements from pass @ to pass
@ay @ any. indicating that it can better leverage a more accurate verifier to filter for the correct solution. We further explore the impact of noisy validation tests in detail in Sec. 4.6.
7

---

Published as a conference paper at ICLR 2025
Table Pass@ any aceuracy of our method compared to prior search methods, Both solutions and validation tests were generated using gpt-3. 5-turbo. We run each method for 10 iterations.
Method Benchmark
HvmanEval
MBPP
Leetcode
APPS
CodeContests
Line
83.1% %
82.9%
33.3%
22.0%
2.99%
Tree (MCTS)
76.9%
79.6%
33.9%
21.5%
2.42%
Best of N
75.6%
77.3%
33.9%
23.0%
3.03%
Ours (SFS)
89.0%
86.1 %
39.4%
32.5%
6.06
We also compare existing state-of-the-art works shown in Table and 5. In Table setting, validation tests are self self- geffeeeeerad, and cap our solution budget at 40 generations max, same as in prior literature (Zhou al., 2024). In Table 5, subset the ground truth hidden tests are given (3 for HumanFval, 1 for MBPP) (Zhong et al., 2024), and we compare against similar methods under this setting. We see that our method achieves higher performance both settings.
Table 4: Comparison to prior works when ground truth tests are not given. We report Pass@1 performance with GPT-3.5.
Table 5:
Comparison to prior works when subset of ground truth tests are given. We report Pass@) I performance with GPT-3.5.
Benchmark
HvmanEval
MBPP
Benchmark Tests given
HumanEval
MBPP
3
1
CoT (Wei al, 2022)
46.9
54.9
ReAct (Yao 2022)
56.9
67.0
SD (+Expl.)
81.1
74.4
Reflexion (Shia al. 2023)
68.1
70.0
(Chen al., 2023)
ToT (Yao al., 2023)
54.4
65.8
SD (+Tracce)
80.5
72.6
RAP (Tan et al., 2023)
63.1
71.4
(Chen et al., 2023)
LATS" (Zhou al., 2024)
75.6
79.6
LDB
82.9
76.0
(Zhong et al., 2024)
Ours (SFS)
82.5
81.7
Ours (SFS)
87.2
91.3
"ran under our setup. see App. for similar setup
4.3
SCALABILITY
Scaling curve with solutions
Scaling curve with output tokens
Ours
0.90
0.8
Tee (MCTS)
Propartion cornec
0.85
Proportion
0.6
Ours
0.75
00000000
0.5
Line
Tre
0.70
0.4
BoN
0
10
15
20
25
30
35
1000
1500
2000
2500
Number solutions generated
Number of output tokens used
Figure 12: Scaling curves for different search methods. Left: Proportion of problems solved vs. number of solutions generated. Right: Proportion of problems solved vs. number of tokens used. Results are from gpt-3. 1...5550. 5-turbo on HumanEyal. Our method shows consistent improvement up to 20 solutions. Other methods plateau and do not catch up to SFS even with additional scaling. Additional curves can be found in Sec. D, including curves for other datasets.
We report the average number of iterations (solutions generated) takes before the search algorithm discovers the correct solution in Table 6. Iters. (incl) is the average number of iterations it takes including problems where algorithm succeeds on the first try. Iters. (exel) the average number of iterations it takes excluding first successes, where the search algorithm is actually used to find the correct solution. On both metries, our method demonstrates the ability to discover the correct solution much more quickly than the other methods. Moreover, method also scales better than the other methods on all datasets. Our method scales efficiently with higher budgets, improving up 20 solutions while others plateau as shown in Figure 18.
in Figure 2 and 12 that our
8

---

Published as a conference paper at ICLR 2025
Table 6: Metries for different search methods. We run search methods for 10 iters. each using gpt-3.- 5-turbo on HumanEval. Our method generates more diverse solutions and discovers the correct solution faster. We also compare against genetic algorithm (Romera- Paredes al., 2024)
Method
pass@1
pass @ any
BERT sim.
val. score
iters. (inel)
iters. (exel)
Line
68.1%
83.1%
0,9992
0.795
2.09
7.13
Tree (MCTS)
75.6%
76.9%
0.9998
0.827
2.38
8.09
Best of N
73.8%
75.6%
0.9983
0.774
2.59
9.00
Genetic
74.4%
75.6%
0.9994
0.815
3.04
10.36
Ours (SFS)
82.5%
89.0%
0.9945
0.813
1.67
5.06
4.4 SOLUTION DIVERSITY
We see in Table that our proposed search method able to propose more diverse candidate solutions with lower semantic similarity score, while maintaining high quality search with by generating solutions with high validation scores. This shows that our methods help both exploration and exploitation without sacrificing much of one for the other. Detailed stats shown in App. G.
4.5 ABLATION ON TECHNIQUES
We performed ablation study the three introduced techniques shown in Table 7 (and App. H), all of which enhanced performance and efficiency, with SCATTERING yielding the highest gains.
Table 7:
Ablation metries for techniques used in our method. We rum search methods for 10 iterations each using gpt 1ppt-3.. 3. 5-turbo on HumanEval.
Ablation
pass @ 1
pass aan
BERT sim.
val. score
iters. (incl)
iters. (excl)
Everything
82.5%
89.0%
0.9945
0.813
1.68
5.06
No SCATTERING
75.6%
78.1%
0,9982
0.802
2.43
8.82
No FORESTING
79.4%
86.3%
0.9982
0.817
2.05
6.56
No SCOUTING 81.9%
86.3%
0.9942
0.792
2.12
6.05
Table 8: Performance on benchmarks when the ground truth tests are given. We run 10 iterations with our method using gpt 5-turro---o-- 0613 HvmanEval. When the tests accurate, can achieve even higher performance, even if only subset is given.
Tests given
pass@1 1
pass@any
BERT sim.
val. score
iters. (incl)
iters. (exel)
No tests given
82.5%
89.0%
0.9945
0.813
1.68
5.06
3 tests given
87.2%
90.2%
0.9952
0.862
2.34
6.86
All tests given 89.0%
90.2%
0.9949
0.864
2.04
5.88
4.6 VERIFIER (VALIDATION TEST) ACCURACY
Confusion Matrix
Previous work emphasized the importance of reliable verifier (Liu et al., 2024a; Chen et al., 2022; Zhang et al., 2023a). In our case, we use self-generated validation tests noisy as a black-box verifer. Figure 13 shows the fusion matrix for whether self-generated validation tests accurately predict solution correctness. The false negative rate of 27.5% highlights misalignment between validation and ground truth tests. We performed an ablation study comparing performance when given different numbers of ground-trutte tests as validation (Table 8). While finding the best verifier is not our focus, the results show a sig- nificant impact of verifier accuracy on pass@1 There are strong interactions between the search method and evaluation metric-just one ground-truth validation test dramatically improves performance in Table 5. However, the 33. 75% inaccuracy validation tests do not affect the pass any rate much shown in Table 8, which demon- strates the robustness of our method to validation noise. Detailed metrics shown in App. I.
Negative
Positive
0.6
Negative
0.5
True correctress Positive
11.25%
6.25%
0.4
0.3
27.50%
55.00%
0.2
0.1
Predicted correctness
0.0
Figure 13: Confusion matrix for celf-generated validation tests with gpt-3 5-turbo-0613 using our method.

---

Published as a conference paper at ICLR 2025
4.7 ABLATION ON MODEL
Scaling curves for different models
Fig. 14 shows weaker models scale better with our method, highlighting trade-off: better- trained models scale worse with inference com- pute. This suggests inference-time scaling com- pensates for limited training quality, benefiting weaker models. Detailed stats in App. F.
0.80
0.75
1lama-3.1-8b
ADDITIONAL RELATED WORK
0.70
gpt-3.5
0.65
Code generation with large language models. Some works focus on either training their own model (Guo al., 2024) fine tuning existing models to adapt them towards code related tasks (Roziere al., 2023: Jain et al., 2023; Roziere et al., 2023). Recent literature has shown a flora of methods to improve LLM code generation performance during inference time, including agentic approaches (Qian et al., 2023; Liu et al., 2024b), multi-agent approaches (Tao et al., 2024; Hong et al., 2023; Islam et al., 2024), tool usage (Zhang et al., 2024), and self-repair (I.e et al., 2023; Olausson er al., 2023a). There trade-off between scaling inference and training compute, with an optimal balance between them (Wu et al., 2024; Sardana et al., 2024). Our work complements this by demonstrating the impact of enhanced solution diversity and exploration on scaling. While this work focuses MCTS, our method can seamlessly integrate with advanced solution sampling methods during refinement (Tang et al., 2024).
0.60
10
Number of submissions k
Figure 14:
Scaling curve for different LLM- models. We run our method on each model for 10 iterations on HumanEval and report the propor- tion of problems where the correct solution has been discovered at each iteration.
Solution validation and feedback. Prior work has demonstrated that effective and accurate validation methods significantly boost performance in code generation (Chen et al., 2022; 2024b) and related tasks like math theorem proving (Cobbe et al., 2021; Uesato et al., 2022). The importance of reliable evaluation metric is critical (Liu et al., 2024a), and incorporating natural language feedhack and reflection on execution results further enhances performance (Zhang et al., 2023c; Bai al., 2022). Our work complements this by introducing new search methods that more effectively discover solutions meeting these validation and evaluation criteria. Combining a strong search method with a robust validation approach leads to improved solution generation performance.
Black box optimization. While many of these methods are domain specific, we adapt many of the insights behind these methods into using L.MSs to search over language and code space. Our textual optimization steps can be thought of as 'textual gradients', though we not use them to conduct backpropogation (Yuksekgonul et al., 2024). There have been some recent works exploring the usage of LLMS as optimizers for different problems (Zhang et al., 2023b; Liu et al., 2024c), including using evolutionary optimization algorithms (Lange et al., 2024; Liu et al., 2024b).
Tree search. Tree search has proven effective decision-making domains. Previous works have applied tree search multi-step tasks, such determining the next reasoning step (Silver et al., 2017; Zhou et al., 2024; Yao et al., 2023; Besta et al., 2024) or generating the next code token (Zhang al., 2023c). While prior work primarily uses tree search for planning (Jiang al., 2023; Feng et al., 2023; Bairi et al., 2024), we show that tree search can also be used for optimization, functioning as a black-box method for exploring a region rather than line.
6 CONCLUSION
We have shown that framing code generation as an optimization task over the code space and applying SCATTERED FOREST SEARCH is highly effective. The simple yet powerful SCATTERING technique, which encourages the LLM to produce more diverse outputs, underscores the importance of exploration in optimization and search processes. This framework and these techniques can offer valuable insights for other code or language generation tasks.
The integration of search-based methods could significantly reduce computational costs while en- hancing performance, making them attractive for large-scale deployments, especially in real-time applications those requiring resource efficiency. This framework also lays the groundwork for future research into optimization strategies for language models, potentially leading to more advanced search algorithms, hybrid models, and novel techniques that push the limits of generative models.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe Le, al. Program synthesis with large language models. arXiv preprint arXiv:2108.077 07732, 2021.
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint arXiv:2212.08073, 2022.
Ramakrishna Bairi, Athary Sonwane, Aditya Kanade, Arun Iyer, Suresh Parthasarathy, Sriram Rajamani, Ashok, and Shashank Shet. Codeplan: Repository-level coding using Ilms and planning. FSE, 1:675- 698, 2024.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. In AAAI, volume 38, pp. 17682-17690, 2024.
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. arXiv preprint arXiv:2407.21788 2024.
Cameron B Browne, Edward Powley, Daniel Whitchouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and in games, 4(1):1-43, 2012.
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.10397 2022.
Guoxin Chen, Minpeng Liao, Chengxi Li, and Kai Fan. Alphamath almost zero: process supervision without process. arXiv preprint arxiv:2405.03553, 2024a.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint 1xXiv:2107.03374 2021.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint arXiv:2304.05/22 2023.
Ziru Chen, Michael White, Raymond Mooney, Ali Payani, Yu Su, and Huan Sun. When is tree search useful for Ilm planning? it depends on the discriminator, arXiv preprint arXiv:2402. 10890, 2024b.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 14168, 2021.
Xidong Feng, Ziyu Wan, Muning Wen, Stephen Mareus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero- like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.1711 2023.
Zhangyin Feng Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al. Codebert: A pre-trained model for programming and natural languages. arXiv preprint arXiv:2002.08155 2020.
Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman. Stream of search (sos): Learning to search in language. arXiv preprint arXiv:2404.03662 03668, 2024.
Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and David Sculley. Google vizier: A service for black-box optimization. In SIGKDD, pp. 1487-1495. 2017.
11

---

Published as a conference paper at ICLR 2025
Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Yu Wu, YK Li, et al. Deepseek-coder coder: When the large language model meets programming- the rise of code intelligence. arXiv preprint arXiv:2401.
2024.
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. arXiv preprini arXiv:2305. 2309. 2023.
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al. Measuring coding challenge competence with apps. arXiv preprint arXiv:2105.09933 2021.
Sirui Hong, Xiawu Zheng. Jonathan Chen, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, et al. Metagpt: Meta programming for multi-agent collaborative framework. arXiv preprint arXiv:2308.00033
2023.
Md Ashraful Islam, Mohammed Eunus Ali, and Md Rizwan Parvez. Mapcoder: Multi-agent code generation for competitive problem solving. arXiv preprint mrXiv:2405.11403, 2024.
Naman Jain, Tianjun Zhang, Wei-Lin Chiang, Joseph E Gonzalez, Koushik Sen, and Ion Stoica. LIm-assisted code cleaning for training accurate code generators. arXiv preprint arXiv:2311. 144904, 2023.
Xue Jiang, Yihong Dong, Lecheng Wang, Fang Zheng, Qiwei Shang, Ge Li, Zhi Jin, and Wenpin Jiao. Self-planning code generation with large language models. ACM Transactions Software Engineering and Methodology, 2023.
Robert Lange, Yingtao Tian, and Yujin Tang. Large language models as evolution strategies. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 579-582, 2024.
Hung Le, Hailin Chen, Amrita Saha, Akash Gokul, Doyen Sahoo, and Shafiq Joty. Codechain: Towards modular code generation through chain of self-revisions with representative sub-modules. arXiv preprint (Xiv:2310.0899)) 2023.
David A. Levin and Yuval Peres. http://pagee..oooooncco wwtp://wwwwc.eeiiaaa///oaaoooooa
Markov chains and mixing times. 2020.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schritwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, (18866624)1092-1000 2022.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint arXiv:2305.200500 2023.
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. NeurIPS, 36, 2024a.
Shengcai Liu, Caishun Chen, Xinghua Qu, Ke Tang, and Yew-Soon Ong. Large language models as evolutionary optimizers. In 2024 IEEE Congress on Evolutionary Computation (CEC), pp. 1-8. IEEE, 2024b.
Shihong Liu, Samuel Yu, Zhiqiu Lin, Deepak Pathak, and Deva Ramanan. Language models as black-box optimizers for vision-language models. In CVPR, pp. 12687-12697, 2024c.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. NeurlPS, 36, 2023.
Theo X Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar- Demystifying gpt self-repair for code generation. CORR, 2023a.
12

---

Published as a conference paper at ICLR 2025
Theo X Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar- Is self-repair a silver bullet for code generation? In The Twelfth International Conference on Learning Representations, 2023b.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feed- Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Ad-
back. In S. Koyejo, vances in Neural Information Processing Systems, volume 35, pp. 27730-27744, Curran Asso- ciates, Inc., 2022. URL 2022 http://ttttee//rreeeessssseese wttp::/ewwwrppppepppeeeeeeeeeeee ct pctpppppeppeeriie/pppppee Papell-aap---aee Conference pdf.
Chen Qian, Xin Cong, Cheng Yang. Weize Chen, Yusheng Su, Juyuan Xu, Zhiyuan Liu, and Maosong Sun. Communicative agents for software development. arXiv preprint (vXiv:2307.07994, 6, 2023.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. In Thirty-seventh Conference Neural Information Processing Systems, 2023. URL https:
/ //openreview.....//m//e/ee.eeevr net. forum? id=HPuSTXJaas
Bernardino Nomera-Paredes. Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468 475, 2024.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et al. Code llama: Open foundation models for code. arXiv preprint arXiv:2308. /2900, 2023.
Nikhil Sardana, Jacob Portes, Sasha Doubov, and Jonathan Frankle. Beyond chinchilla-opiimal: Accounting for inference in language model scaling laws, 2024. URL /ttpsttt://aaiii..com 2bcs/2401.. 00 8.
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. NeurIPS, 36, 2023.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint urXiv:1712.01811 2017.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314 2024.
Hao Tang, Keya Hu, Jin Peng Zhou, Sicheng Zhong, Wei-Long Zheng, Xujie Si, and Kevin Ellis. Code repair with Iims gives an sxploration-exploiaaiie tradeoff. arXiv preprint arXiv:2405. 2024.
Wei Tao, Yucheng Zhou, Wenqiang Zhang, and Yu Cheng. Magis: Llm- multi-agent framework for github issue resolution. arXiv preprint arXiv:2403.17922 2024.
Ye Tian, Baolin Peng, I Linfeng Song, Lifeng Jin, Dian Yu, Haitao Mi, and Dong Yu. Toward self- improvement of llms via imagination, searching, and criticizing. arXiv preprint arXiv:2404. 12253, 2024.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint 2rXiv:2211.14222 2022.
Evan Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, Will Song, Vaskar Nath, Ziwen Han, Sean Hendryx, Summer Yue, and Hugh Zhang. Planning in natural language improves 1lm search for code generation. arXiv preprint arX 2024.
13

---

Published as a conference paper at ICLR 2025
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. Chain-of- -f-tuughht prompting elicits reasoning in large language models. NeurIPS, 35: 2022.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models, 2024. URL https: /tl:://azxxe aarxiv.v. org/ abs/ 2208/240... 00724.
Ya xiang Yuan. Recent advances in trust region algorithms. Mathematical Programming, 2015.
Chengrun Yang. Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc Le, Denny Zhou, and Xinyun Chen. Large language models optimizers. In ICLR, 2024. URL https: /owpnr/eeww/.e.eee.ee/ net/
Eorum??ddBBb-vGoWk
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting language models, arXiv preprint arXiv:2210.03629, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliherate problem solving with large language models. NeurIPS, 36, 2023.
Mert Yuksekgonul, Federico Bianchi, Joseph Boen, Sheng Liu, Zhi Huang, Carlos Guestrin, and James Zou. Textgrad: Automatic" differentiation" via text. arXiv preprint arXi::200.007496 2024.
Kechi Zhang, Jia Li, Ge Li, Xianjie Shi, and Zhi Jin. Codeagent: Enhancing code generation with tool-integrated agent systems for real-world repo-level coding challenges. arXiv preprint arXiv:2401.07339, 2024.
Kexun Zhang, Danqing Wang, Jingtao Xia, William Yang Wang, and Lei Li. Algo: synthesizing algorithmic programs with Ilm-generated oracle verifiers. arXiv preprint arXiv:2305. 145911, 2023a.
Michael Zhang, Nishkrit Desai, Juhan Bae, Jonathan Lorraine, and Jimmy Ba. Using large language models for hyperparameter optimization. In NeurlPS 2023 Foundation Models for Decision Making Workshop, 2023b.
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B Tenenbaum, and Chuang Gan. Planning with large language models for code generation. arXiv preprint arXiv:2303.0551 2023c.
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua Tenenbaum, and Chuang Gan. Plamning with large language models for code generation, 2023d. URLhttpst htt.tps://axxiv.rrgg abs/ abss2303 2203. 05510.
Li Zhong, Zilong Wang, and Jingbo Shang. Ldb: A large language model debugger via verifying runtime execution step-by-step. arXiv preprint arXiv:2402.16900 16906, 2024.
Andy Zhou, Kai Yan, Michal Shlapentokh-Rothnee Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. ICML, 2024.
14

---

Published as a conference paper at ICLR 2025
APPENDIX: SMARTER CODE SPACE EXPLORATION WITH LLMs
A ETHICS STATEMENT
All contributing authors of this paper confirm that they have read and pledged to uphold the ICLR Code of Ethics. Our proposed method is specifically designed for code generation using LLMs. We acknowledge the potential for LLMs generate code that may inadvertently introduce vulnerabilities or ethical concerns. Our research prioritizes the development of methodologies that emphasize responsible usage, ensuring that generated code adheres best practices in security and ethics. We recognize that LLMs can perpetuate and amplify biases present in training data. We aim to contribute positively to the field of code generation while addressing the potential challenges and responsibilities that arise from the use of advanced AI technologies.
B PROBLEM SETTING AND CODING PROBLEM EXAMPLE
In the program synthesis task æ (p, H), the solver is provided with problem prompt p, described in natural language, which requests the generation of code to implement a specific functionality or object The objective is to generate solution s' that passes all the hidden tests H designed to evaluate its correctness. These hidden tests H are not visible to the solver under any circumstances. In some cases, the solver may also have to verify their solution before submitting for evaluation against the hidden tests. Alternatively, the solver may generate their own validation tests V test the functional correctness of s'. Both hidden and validation tests are typically structured as a set of assert statements validating specific functionalities of A representative example of this problem setup is provided below.
of validation tests V, which they can
Example code generation prompt, solution, and tests
Prompt: Write function greatest_common_diiee (a, b) that returns the GCD of two integers and
Validation tests:
assert (greatest_ccmooo__ivvvsorr (3,5) assert (greatest_.commoo_ddvllooll (25, == 5)
assert (greateet_ccomorccvvvieee
3)
Proposed solution 1:
def ceaatest_commot divisor (a, b)
for i in range (min (a, b) 0, -1) if == 0 and b 0: return i
Test feedback:
assert (gweateettcoomoennee correct
(3, 1) #output 1 is
assert heattt/grraees_cooo_diiieee (25, 15) 5) #output 5 is correct assert (ggeattet_.como.ddivlsooo incorrect
#output None is
A solution s' is deemed correct if and only if it passes all hidden tests H. Solvers are permitted up to & attempts [s]; to submit their solutions for evaluation. at least one submission s* satisfies all hidden tests, the task is considered solved. Given of tasks X. the proportion of tasks (p, H) X successfully solved by the agent within & submissions is referred to as the pass@ @k k rate (Chen et al., 2021).
15

---

Published as a conference paper at ICLR 2025
B.1 JUSTIFICATION FOR PROBLEM SETUP
In our problem setting, the solver is explicitly not allowed to access the hidden tests H. This constraint ensures that the task closely mirrors real-world applications of program synthesis, where the solver must produce solutions based solely on the problem prompt p. Such a setup aligns with platforms like LeetCode or conventional coding assessments, where cases remain hidden to preserve the integrity of the evaluation process and discourage overfitting to known test sets.
This restriction is not only practical but also reflects the needs of end users real-world scenarios. Writing comprehensive and correct unit tests is time-consuming process, requiring substantial domain knowledge and effort. practice, users would prefer tools that can autonomously generate correct implementations from prompt without requiring additional test specifications guidance. By requiring solvers to rely on self-generated validation tests or implicit reasoning to produce correct solutions, this setup encourages the development of tools capable of robust and generalized problem-solving.
By prioritizing correctness under these constraints, our framework evaluates agent's ability to understand the problem and synthesize accurate solutions a realistic and user-centric manner, making it an ideal benchmark for program synthesis tasks.
C METHODOLOGY DETAILS
C.I TRADITIONAL MONTE CARLO TREE SEARCH (MCTS)
Monte Carlo Tree Search (MCTS) is widely used algorithm for decision-making in environments with large, complex state spaces, such games and optimization problems. The algorithm incre- mentally builds a search tree by simulating possible outcomes and leveraging these simulations to balance exploration (visiting new states) and exploitation (refining knowledge about promising states). The MCTS process consists of four main stages: selection, expansion, simulation, and backpropagation.
C.I.1 SELECTION
The algorithm begins the root node, corresponding the current state 8, and iteratively selects child nodes using selection policy designed to balance exploration and exploitation. The most commonly used selection policy is the Upper Confidence Bound for Trees (UCT), which evaluates each child state s' and corresponding action (or direction) d according to the formula:
In (Eo n(s, b))
UCT(s, d) = (s, + +oV n(ss d)
where (s, d) is the estimated value of taking action d from state s, ((s, d) is the number of times this action has been visited, and is hyperparameter controlling the exploration-explee trade-off. This equation encourages actions that either have high value (exploitation) or have been visited less frequently (exploration).
C.1.2 EXPANSION
After a leaf node is reached during selection, one or more child nodes representing potential future states s' are added to the search tree. These states typically generated by sampling actions improvement directions d from a predefined set or policy. The added nodes represent unexplored areas of the search space.
C.1.3 SIMULATION
Once new node is expanded, the algorithm performs simulation or rollout from that state s'. In this step, a playout policy is used to sample a trajectory of states and actions until a terminal state evaluation horizon is reached. The outcome of this simulation, denoted as v(s'), provides an estimate the quality of the state s'. This value could represent a game outcome (e.g., win/loss), a performance metric (e.g., number of test cases passed), another problem-specifie objective.
16

---

Published as a conference paper at ICLR 2025
C.1.4 BACKPROPAGATION
The results of the simulation are then propagated back up the search tree update the value estimates ((s, d) for the nodes along the trajectory = [80, d1, 82, 8-1]. The value update is performed iteratively using a weighted average, which incorporates the new simulation result while retaining information from prior simulations:
(s; di+1) (1+1)) (1 a., (( (0) an max (Q(s,, "0+1) Q(s++1 (++2) (7)
where O₂ is a weighting parameter that depends on the visit count n(s, d), and max ensures that only the best-performing solutions along the trajectory are prioritized.
17

---

Published as a conference paper at ICLR 2025
C.2 SCATTERED FOREST SEARCH
Algorithm 1: Scattered Forest Search (SFS) with SCOUTING
Input: Language Model C. Prompt p. Number of iterations N, Branching factor Exploration parameter
Output: Best solution
Function Scattering (nade)
Generate diverse directions (d1, d2....,, ] using & conditioned on feedback for node;
Save directions (d1, d2...... d dereeeniesssooss, with (ode.qua/uc((d)) 0;
return direeddiectiinn:;
Function F Foresting ing (Su)
Initialize forest with random seed solutions ($1, ,,,..,, Sn sampled by C; foreach seed E Su do
Scat tering (seed) Gencrate directions for each seed
end
return forest So:
Function Scout ing (porent, direction, child, f feedback, I):
Update global insights 7 using feedback from applying direction to parent, resulting in child;
Function Select Seed (S)
Select the promising seed from using UCT formula (Eq. 1);
return s:
Function SelectDi rect fectioon (node):
Select the most promising direction d from node.directions using UCT formula;
return d;
Function Simulate (seed)
parent seed, 0:
while parent is not a leaf node
direction +- Sel ectDi recti on (parent); child + Child node corresponding to direction;
(pappend((parent, direction, child)): parent child;
end
return lcaf node and trajectory
Function Expand (porent, direction):
Generate new solution s' using &. conditioned on direction, and foodback:
Create new child node child with solution s' and feedback from validation tests on parend; return child;
Function Backpropaçate (r, leo..a.faraaoo reward):
leaf qvaluee (iirectiidiettion) f- reward:
foreach (parent, direction, child) E r (in reverse order) do
Update parent. ceattt.quuuueeeeee (direccti))) using Eq. 2;
marent.visite |direction] careent.iisita + 1;
end
begin
Initialize global insights I 0:
Initialize forest Sg +- Forestii boresting ();
Generate validation tests V if not given;
for +- 1 to N do
seed (Sleetteeeeddd
leaf, + Simulate (seed);
direction + reccciircttionnn (leaf);
child - Expand (leaf, direction);
feedback, reward Execution feedback and validation score of child;
Backpropagate (r, leaf, reward);
Scout (leaf, direction, child, feedback, I); Scattering nn (child); ; / Generate di rect i ins for the new node
end
Best solution across all trees;
end
18

---

Published as a conference paper at ICLR 2025
Python Pscudocode for SFS with SCOUTING
(andeering(node) vaa
Cenerate diverse directions for given node using the language model (120
di rect long = [d), d2, dk] ione cirrctione Generate vaiig 1M condi on node feedback
node.qualue (d: for directions; i initialize gevalues For each direction recurn of rections
def Ingesting():: van
Instialize a focest with multiple random seed solutions and generate directions for each seed. van
forest [al, a2, sn] # Generate Initial seeds usiing TM
for seed Forest:
berinn Generate dorectioons for each seed recurn forest
del Lngut (parent, direction, child, Teedback, insights):
global insights using feedback applying directioo the parent to produce the child.
vinn
Update insights with the feedback and inceraction details
insights. updotec (parent, di roctioon) feedsock))
Select the most premising seed from the focest using the UCT forula.
recurn max (forest, key=lamoda at (st_vallues)1 Replace with actual UCT calculation
del diiect_
premising direction from node/ directions using forula.
**n
seturn max (oodd.diiieene diremiion, key=lumbda di uet_rolue d)) Replace with actual ucr caleulation
def similate (seed)
Similate path starting from seed, selecting the best direction each step. wan
parent
Lra Jectozy - []
while not te_ (sarent)))
direction sel.ot__direeteee diw.etiiietnnnnoooooooooo (porent)
child = get child rode mode (parent, donection)
trajectocy.appet
(parent, direction, child)
parent child
zecurn parenty trajectory
del expendiparent, dic)ction): by applying direction parent generating solution.
with
new solution generate conerate_polutionn solution (porent .ollutiioo direction) Use LM feedback val idate aaltt_asslll soluu on now soluttonn # Valitationn feedback
create_ncce tnew sccuution [eedback) Create child
recurn child
dež wttp:rpppaatetttaooooooooo laaf, roward):
Packpropagate revard along trajectory.
eeaf.gvaloediiee rect ion] zeward
for parent, direction, child in reversedttrejectory/.
parant.qva luw (di rection]] reward parent. wualuueedlleeeeeeeeeeeee parent.visite [direction] i- Increment visis count
Main algerithm
def peaatterdd_forstt...eo foresttaearrrrroeeette wewrch (model, prompe, fterations, pranchingg_fctton exploratioon, on_peram) wen
Perform the Seatt Pores: Search (SF8) algocithm.
van
Insights
Initialive global insights
foresting() unstinlize
seed
val idation_tests gemerate_eee yol ion Generate testa if not given
For in tange((teratloon))
selest_peedd(fozes)
lasf, trafectory = simolate/sood)
direction se ecte det_eettddrrectineeee ion expand(leaf, dizection)
foodback, reward execute(child imlidattio_tests) Run validetion tests and get reward hackpropagateite ra lest, reward)
ingleef,, directicn, child feedack, insightst
scat innteeincchhioo Id) Generate dore for the new node
beat solution got_bbst__e_eeeoeeee best__oo.veiennffores)) best_solution
19

---

Published as a conference paper at ICLR 2025
SFS integrates three key components: scattering, foresting, and scouting, with tree search performed using Monte Carlo Tree Search (MCTS). Below, we detail the main components and steps of the algorithm.
C.3 ALGORITHM OVERVIEW
SFS operates over multiple iterations, progressively refining the solution space using a search tree initialized with diverse seed solutions. For each iteration, SFS balances exploration and exploitation using the Upper Confidence Bound for Trees (UCT) formula to guide the search. The algorithm begins by initializing global insights forest of seed solutions Sp, and validation tests V. It then performs the following steps over N iterations.
Initialization
Global Insights: A global memory I is initialized to store feedback and general insights gained during the search process, enabling knowledge sharing across branches.
Forest Creation: The algorithm generates set of initial seed solutions So
{s1, .2,...., by sampling diverse solutions using the language model L. For each seed:
Diverse directions (d1, seed solution by prompting & with feedback from the seed.
Direction Initialization:
dx} are generated for each
Q-Values: Q-values for each direction are initialized to 0, i.e. mode.qualue (d:) <- 0. These values are updated dynamically based on feedback during backpropagation.
Seed Selection the UCT formula:
The algorithm selects the most promising seed solution from the forest S using
UCT(s, ((..d) + + In (
(8)
n(s, d)
where e the exploration parameter, nss, s, d) the visit count for direction (or seed) d at state
and Q(s,, d) is the estimated reward for that direction. This balances exploration of under-explored solutions and exploitation of high-reward solutions. Unvisited seeds/directions always have infinite UCT values, which means that we will always explore unvisited seeds or directions first.
Simulation Starting from the selected seed 8, the algorithm simulates trajectory [(8;, di, {1]1 by iteratively selecting the most promising direction d, using the UCT formula. The simulation proceeds until leaf node reached.
Expansion At the leaf node, the algorithm expands the search tree by generating a new child node:
= L(s, d, feedback).
where C generates a new solution s' by incorporating the parent solution 8, the improvement direction d, and validation feedback. The newly generated solution s' is validated, and the proportion of validation tests passed serves as the reward:
Reward Number of tests passed
(10)
Total number of tests
Backpropagation
The reward is backpropagated along the trajectory T:
Q(s,, (1+1) - (1-,,,)) d++1) +a, max(e(s;, ()) (( d442) (11)
where on is a weighting parameter dependent on visit counts. The visit count ni d) for each direction incremented by during backpropagation.
Scouting The feedback from applying direction d to a parent node is analyzed to extract general insights. These insights are stored in global memory and reused to guide future direction generation. Scouting improves the search's 's efficiency by leveraging knowledge gained from past iterations.
Scattering For every expanded node, diverse new improvement directions {d1, de..... dd are generated using L. This encourages exploration of orthogonal regions of the solution space, reducing the likelihood of stagnation in local optima.
20

---

Published as a conference paper at ICLR 2025
Final Selection After N iterations, the best solution s* across all trees in the forest is selected. The best solution is determined based on the highest reward, i.e., the proportion of validation tests passed.
C.4 KEY FEATURES OF SFS
Q- D-Vuue Initialization: For every new direction, Q-values are initialized to and dynami- cally updated during backpropagation.
Reward Definition: The reward is explicitly defined as the proportion of validation tests passed, providing a consistent measure of solution quality.
Diversity: By incorporating scattering and foresting, the algorithm ensures diversity in both initial seed solutions and branching directions, reducing the risk of stagnation in local optima.
Global Insights: The scouting mechanism enables the sharing of effective improvement strategies across the search space, enhancing the algorithm's 's exploitation capabilities.
The SFS algorithm's 's integration of scattering, foresting, and scouting represents powerful approach to systematically navigate and optimize large solution spaces.
C.5 ALGORITHM COMPLEXITY
The time complexity of the Scattered Forest Search (SFS) algorithm is primarily determined by the number of iterations N and the traversal steps involved in each iteration.
Time Complexity: At each iteration, the algorithm performs several steps: selecting seeds, simulating a trajectory, expanding nodes, and backpropagating rewards. In the worst-case scenario, the depth of the solution tree proportional to N, resulting O(N) steps for traversal. Over N iterations, this results in total time complexity of O(N2). Additionally:
Scouting and Scattering: The scouting and scattering steps at each iteration involve generating new directions and updating global insights, which have constant time complexity per iteration.
Comparison to Other Methods:
Line Search: Line search explores solutions sequentially without tree traversal, yielding time complexity of O(N).
Beam of Nodes (BoN): Similar to line search, BoN has time complexity of O(N) due to its focus on maintaining and updating a fixed number of candidate solutions.
-Tree Search (MCTS): Traditional Monte Carlo Tree Search also has a time complexity of O(N2), as involves tree traversal similar to SFS.
Thus, the SFS algorithm shares the same O time complexity tree search but differs signifi- cantly in its use of global insights and scattering to improve solution diversity and efficiency.
Space Complexity:
SFS: The algorithm stores all generated solutions, resulting in space complexity of O(N). In addition, global insights require constant space O(1) since only the most recent updated insights need to be kept, and insights are kept within a fixed length.
Line Search: solution.
Line search has space complexity of O(1), as it retains only the most recent
BoN and Tree Search: Both methods, like SFS, require O(N) space store all candidate solutions.
While the memory overhead for SFS comparable to other tree- based methods, the efficient use of global insights enhances the algorithm's 's performance without additional memory costs.
Practical Considerations: Although SFS involves tree traversal, which contributes to the O complexity, the computational bottleneck in practice is the solution generation process, typically
21

---

Published as a conference paper at ICLR 2025
dominated by LLM API calls. Thus, the tree traversal cost has negligible impact runtime in practical settings.
C.6 LLM REQUEST COST
Our algorithm requires two LLM-API calls (requests) per solution generated. One API call is used for code generation based on SCATTERING improvement directions. One API call is used for reflection after the code is generated and executed. The reflection step involves (1) updating the global insights based on the execution feedback (2) generating new SCATTERING directions based on the global insights and execution feedback. In practice, the two components of the reflection step can be separated into two API calls run in parallel to increase computational efficiency and code cleanness, which is how we implemented
22

---

Published as a conference paper at ICLR 2025
D SCALING
Our method scales well with increased iterations. We show scaling curves for each dataset as shown in Figures 15, 16, 17. We also display scaling curves higher budgets as shown Figure 18. We see that performance mostly plateaus after the 20 solutions are generated. Moreover, other methods do catch up our method each with higher search budgets, suggesting how our method is able to fundamentally better explore the solution spaces, including solutions that other methods will not consider.
Scaling curves for APPS
Scaling curves CodeContests
0.325
Ours
0.06
Ours
BoN
Proportion correct
Unn
Proportion correct
0.05
Line
Tree (MCTS)
0.250
0.225
0.03
0.200
0.02
10
10
Number solutions generated
generated
Figure 15: Scaling curves for different search methods APPS (left) and CodeContests (right). We run each method for 10 iterations using gpt-3. 1ppt-3.5-tuue 5-turbo, reporting the proportion problems where the correct solution is discovered each iteration.
Scaling curves for HumanEval
Scaling curves for MBPP
0.90
0.86
Line
Line
Proportion correct
Tree (MCTS)
Proportion correct
(MCTS)
BoN
0.82
0.80
0.80
0.75
0.76
0.70
0.74
10
Number of solutions generated
Number of solutions generated
Figure 16: Scaling curves for different search methods on HumanEval (left) and MBPP (right). We run each method for 10 iterations using gpt-3 5-turbo, reporting the proportion of problems where the correct solution is discovered at each iteration.
Scaling curves for Leetcode
0.40
0.38
Proportion correct
0.36
0.34
0.32
Ours
0.30
(MCTS)
BoN
0.28
Line
10
Number of solutions generated
Figure 17: Scaling curves for different search methods on LeetCode. We run each method for 10 iterations using gpt-3. 5-turbo, reporting the proportion problems where the correct solution is discovered at each iteration.
23

---

Published as a conference paper at ICLR 2025
High budget scaling curves
Ours
0.90
Line
Proportion correct
(MCTS)
0.85
BoN
00llo0 300000
0.80
#0000000
10
15
20
30
35
Number of solutions generated
Figure 18: High budget scaling performance for our method. Proportion of problems where the correct solution was discovered by our method HumanEval with gpt-3. 3ptt-3.5-turbo06 5-turbo0611 with 40 iterations. Our method continues to show great improvement up until 20 solutions generated while the performance other methods plateau. Other methods do not catch up with SFS in terms of performance even with more inference scaling.
PRIOR WORKS BENCHMARK
In the LATS experimental setup, each iteration after a solution is generated, the algorithm is allowed to check if the new solution is correct on the ground truth tests before proceeding (Zhou et al., 2024). show the performance our method in the same setup here, with the same solution budget. The performance Pass@1 numbers are adapted from the LATS paper (Zhou et al., 2024). We see Table 9 that given the same setup, our method still achieves higher performance.
Table 9: Comparison prior works. We report Pass performance with GPT-3.5.
Method Benchmark
HumanEval
MBPP
CoT (Wei et al., 2022)
46.9
54.9
ReAct (Yao et al., 2022)
56.9
67.0
Reflexion (Shinn et al., 2023)
68.1
70.0
ToT (Yao al., 2023)
54.4
65.8
RAP (Hao et al., 2023)
63.1
71.4
LATS (Zhou et al., 2024)
83.8
81.1
Self-repair (Olausson et al., 2023b)
90.5
79.1
Ours (SFS)
93.3
91.2
24

---

Published as a conference paper at ICLR 2025
F ABLATION ON MODELS
In this section, we provide detailed ablation study on the performance of different base language models, focusing metrics relevant to the HumanEval benchmark. Table 10 displays the results of applying various search methods across three models: gpt-3.. 5, gpt- For each model, we report key performance indicators such as pass @ 1, pass @ any, BERT similarity, and validation score, along with the number of iterations (inclusive and exclusive). Furthermore, Table II provides an extended comparison of metrics, including similarity measures like TF-IDF and Levenshtein, alongside error rates (false positives/negativs)) and true classification rates, helping to evaluate model behavior in more detail across different performance aspects.
ni, and gpt-4o.
Table 10: Ablation models. We run search methods for 10 iterations each HumanEval
Model
pass@]
pass@any
BERT sim.
val. iters. (incl)
iters. (excl)
gpt-3.5
82.5%
89.0%
0.9945
0.813
1.68
5.06
gpt-4o-mini gp
89.4%
93.8%
0.9876
0.845
0.84
5.83
90.6%
95.6%
0.9915
0.894
0.68
4.95
Table 11: Performance metrics for different base LLM models HumanEval. gpt 3.t-3.5-m t-rbbrr 0613 for 10 iterations for each model.
We ran
Metric
gpt-3.5
gpt-4o-min -inin
gpt-4o
Pass @ai@@AAnr Any
89.0%
93.8%
95.6%
Pass
82.5%
89.4%
90.6%
Validation score
0.813
0.845
0.894
BERT sim.
0.9945
0.9876
0.9915
TF-IDF sim.
0.743
0.643
0.691
Levenshtein sim.
0.721
0.631
0.665
Token seq. sim.
0.765
0.719
0.705
False positive rate
6.25%
4.38%
4.38%
False negative
27.50%
33.13%
17.50%
True positive rate
55.00%
56.25%
73.13%
True negative rate
11.25%
6.25%
5.00%
Iters. (incl)
1.68
0.84
0.68
Iters. (excl)
5.06
5.83
4.95
F.1 INFERENCE VS TRAINING TRADEOFF
The debate between investing resources in training stronger models versus developing effective inference-time methods reflects fundamental tradeoff in the field of machine learning. Training- based improvements often involve scaling up model size, enhancing training datasets, or incorporating comain-specitfe fine-tuning, While these approaches can lead substantial performance gains, they come with high computational costs and limited adaptability post-training. Conversely, test-time methods like Scattered Forest Search (SFS) focus on maximizing utility of pre-trained models, enabling efficient exploration and improved accuracy without additional training.
Our experiments vividly illustrate this tradeoff. For example, as shown in 14, stronger models such GPT-4o consistently outperform weaker models like GPT-3.5. However, also observe that weaker models benefit disproportionately more from inference scaling, highlighting that test- time optimization be particularly valuable for models that not extensively trained. This suggests that test-time methods can serve as a complement to training improvements, especially in eeourcc-constrained settings.
While training stronger models remains a cornerstone progress, inference time techniques like SFS address challenges that training alone cannot solve. For instance:
25

---

Published as a conference paper at ICLR 2025
Adaptability: Test-time methods allow for domain-specifer optimizations without requiring expensive retraining.
Exploration vs. Exploitation: Techniques like SFS improve solution diversity and robust- ness, addressing issues such as overfitting or lack of generalization in pre-trained models.
Many real-world applications rely on off-the-shelf LLMs where retraining infeasible. In such cases, enhancing inference-tine time performance becomes the primary lever for improvement.
Practical Use Cases:
Our work also reveals intriguing interaction effects between training and inference scaling. For example:
Better Models, Marginal Gains; While stronger models perform better overall, the
marginal benefits of inference scaling decrease training quality improves. This is because well-trained models already exhibit diverse and high-quality outputs, reducing the need for additional exploration.
Weaker Models, Larger Gains: Conversely, weaker models benefit substantially from techniques like SFS, which compensate for their limited training by expanding the search space and leveraging execution feedback refine solutions.
These findings highlight that the importance of inference scaling is inversely proportional to the strength of the underlying model, creating an interesting trade-off that could guide future research in balancing the two approaches.
26

---

Published as a conference paper at ICLR 2025
G PERFORMANCE METRICS FOR DIFFERENT DATASETS
We display detailed performance metrics for MBPP (Table 13), HumanEval (Table 12), CodeContests (Table 16), Leetcode (Table 14), and APPS (Table 15).
The performance metrics across various datasets, including MBPP, HvmanEval, CodeContests, Leetcode, and APPS, offer comprehensive comparison of different search methods used to evaluate large language model (LLM) performance. Each table highlights the results of different strategies, such Line, Tree-based search (MCTS). Best of N, and our proposed method. Key metries, such as Pass @ 1, Pass @ Any. validation score, and various similarity metrics (e.g., BERT, TF-IDF, and Levenshtein), illustrate the effectiveness of each search method in terms of accuracy and relevance.
Additionally. false positive and false negative rates provide insight into the errors made by each approach. while true positive and negative rates reflect the precision and recall of each method. These metrics give holistic view of model performance, especially in scenarios involving iterative search, with the number of iterations (both inclusive and exclusive) further contextualzznng the computational complexity of each method.
Table 12:
Performance metrics for different search methods HumanEval.
We ran
3ot-3.5-turbon for 10 iterations for each method.
Metric
Line
Tree (MCTS)
Best of N
Ours
Pass @ Any
83.1 %
76.9%
75.6%
89.0%
Pass
68. %
75.6%
73.8%
82.5%
Validation score
0.795
0.827
0.774
0.813
BERT sim.
0.9992
0.9998
0.9983
0.9945
TF-IDF sim.
0.495
0.502
0.936
0.743
Levenshtein sim.
0.480
0.496
0.925
0.721
Token seq. sim.
0,476
0.500
0.962
0.765
False positive rate
8.1%
5.0%
3,8%
6.3%
False negative rate
16.9%
23.1%
28.1%
27.5%
True positive rate
51.3%
52.5%
45.6%
55.0%
True negative rate
23.8%
19.4%
22.5%
11.3%
Iters. (incl)
2.09
2.61
2.59
1.68
Iters. (excl)
7.13
8.87
9.00
5.06
Table 13: Performance metrics for different search
methods
on MBPP. We
ran
10t--35--turb-O00 for 10 iterations for each method.
Metric
Line
Tree (MCTS)
Best of N
Ours
Pass @ Any
82.9%
79.6%
77.3%
86.1%
Pass @
73.6%
76.1 %
76.6%
78.3%
Validation
0.784
0.774
0.729
0.729
BERT sim.
0.9991
0,9998
0.9993
0.9956
TF-IDF sim.
0.473
0.521
0.960
0.747
Levenshtein sim.
0.455
0.519
0.956
0.759
Token seq. sim.
0.450
0.520
0.974
0.785
False positive rate
7.6%
5.8%
6.0%
6.5%
False negative rate
18.9%
26.2%
33.0%
21.7%
True positive rate
54.7%
49.9%
43.6%
56.7%
True negative rate
18.9%
18.1%
17.4%
15.1%
Iters. (incl)
1.91
2.29
2.36
1.91
Iters. (excl)
7.35
9.20
9.20
6.85
27

---

Published as a conference paper at ICLR 2025
Table 14:
Performance metrics for different search methods on Lectcode.
We ran
1pt-3.5-turbo-O0 for 10 iterations for each method.
Metric
Line
Tree (MCTS)
Best of N
Ours
Pass @ Any
33.3%
33.9%
33.9%
39,4%
Pass
28.9%
33.3%
33.3%
36.7%
Validation
0.352
0.354
0.372
0.387
BERT sim.
0.9933
0,9998
0.9936
0.9961
TF-IDF sim.
0.840
0,934
0.889
0,589
Levenshtein sim.
0.813
0,926
0.902
0.694
Token seq. sim.
0.818
0,925
0.897
0.652
False positive rate
1.1%
0.6%
0.6%
5.0%
False negative rate
12.2%
27.2%
26.7%
24.4%
True positive rate
8.3%
6.1%
6.7%
9.4%
True negative rate
78.3%
66.1%
66.1%
61.1%
Iters. (incl)
6.78
7.31
6.74
6.42
Iters. (excl)
9.54
10.44
9.63
8.75
Table 15: Performance metrics for different search 3pt-3.5-tuzbo-O0 for 10 iterations for each method.
methods
on APPS. We
ran
Metric
Line
Tree (MCTS)
Best of N
Ours
Pass Any
22.0%
21.5%
23.0%
32.5%
Pass@
14.5%
18.0%
19.5%
20.5%
Validation score
0,232
0.211
0.205
0.232
BERT sim.
0.9886
0.9997
0.9984
0.9946
TE-IDF sim.
0.837
0.943
0.825
0.523
Levenshtein sim.
0.817
0.936
0.843
0.626
Token seq. sim.
0,813
0,933
0.840
0.567
False positive rate
6.5%
3.0%
3.0%
7.0%
False negative rate
7.5%
17.5%
18.5%
16.0%
True positive rate
2.0%
1.5%
2.0%
2.5%
True negative rate
84.0%
78.0%
76.5%
74.5%
Iters. (incl)
7.93
8.66
7.82
7.30
Iters. (excl)
9.61
10.75
9.65
9.18
H TECHNIQUE ABLATION
In this section, present the results of ablation study to assess the impact of different com- ponents of our method on performance, as shown in Table 17. We evaluate four variations: the full method with all components enabled ("Everything"), and three ablations where we remove key FORESTING, and SCOUTING one at time.
The ablation results highlight how critical each technique is for achieving high performance. Re- moving SCATTERING leads to a noticeable drop in Pass @ Any, decreasing from 89.0% to 78.1%. while removing FORESTING has a milder effect, with Pass@ Any only falling to 86.3%. Notably, FORESTING removal significantly affects similarity scores, with a drop in TF-IDF similarity from 0.743 0.419. Similarly, removing SCOUTING results in slight reduction performance metries, but Pass @ remains comparable to the full method, indicating its robustness.
28

---

Published as a conference paper at ICLR 2025
Table 16: Performance metries for different search methods on Codecontests. 1pt--3.5-urbo--e for 10 iterations for each method.
We ran
Metric
Line
Tree (MCTS)
Best of N
Ours
Pass @ Any
3.0%
2.4%
3.0%
6.1%
Pass
1.21% %
2.42%
1.82%
4.24%
Validation
0.091
0.078
0.051
0.086
BERT sim.
0.9838
0.9997
0.9980
0.9950
TF-IDF sim.
0.871
0,980
0.770
0.502
Levenshtein sim.
0.856
0.981
0.800
0.603
Token seq. sim.
0.846
0,982
0.766
0,502
False positive rate
2.2%
1.2%
0.6%
1.2%
False negative rate
0.7%
2.4%
1.8%
1.2%
True positive rate
0.0%
0.0%
0.0%
0.0%
True negative rate
97.0%
96.4%
97.6%
97.6%
Iters. (incl)
9.74
10.73
9.75
9.53
Iters. (excl)
9.89
11.00
9.93
9.83
Table 17: Performance metrics for different ablations on techniques for our method. We ran ppt-3.55 3.5--uurb--063 for 10 iterations for each ablation HumanEval.
Metric
Everything
No SCATTERING
No FORESTING
No SCOUTING
Pass @ Any
89.0%
78.1%
86.3%
86.3%
Pass
82.5%
75.6%
79.4%
81.9%
Validation score
0.813
0.802
0.817
0.792
BERT sim.
0.9945
0.9982
0.9982
0.9942
TF-IDF sim.
0.743
0.926
0.419
0.740
Levenshtein sim.
0.721
0.911
0,427
0.729
Token seq. sim.
0.765
0.945
0.409
0.756
False positive rate
0.063
0.063
0.050
0,063
False negative rate
0.275
0.244
0.244
0,281
True positive rate
0.550
0.513
0.550
0.538
True negative rate
0.113
0.181
0.156
0.119
Iters. (inel)
1.68
2.43
2,05
2.12
Iters. (excl)
5.06
8.82
6.56
6.05
I VERIFIER ACCURACY AND GROUND-TRUTH VALIDATION TESTS
1.1 VALIDATION TEST GENERATION
In our methodology, validation tests are automatically generated to evaluate the correctness of code solutions. The I.LM is instructed create Python unit tests in the form of assert statements. This process involves prompting the model with high-level description of the function module and specifying that the tests should be concise, diverse, and verifiable. By leveraging the LLM's capability to understand code semantics, the generated tests help guide the search for correct solutions and provide immediate feedback during the refinement process.
To illustrate, consider the task of generating validation tests for function greatest. cotmoo_como___mmm common_divisoo (a, b). The LLM receives a prompt to write the func- tion and is instructed produce unit tests in the form of assert statements:
29

---

Published as a conference paper at ICLR 2025
Example Code Generation Prompt, Solution, and Tests
Prompt: Write function
(a, b) that returns the GCD
of two integers and b.
Generated validation tests:
assert (greatest_ cititess__commor_ddiiloooo (3, 5) == 1) assert (greatest_coomoo_____ooe__ httprt_ccooooonnno_ee assert
15) 5)
(0, 3) = 3)
The LLM follows a specific prompt instruction to generate these tests, ensuring comprehensive validation of the function's behavior. The prompt structured follows:
Test Generation Prompt
You are an AI coding assistant that can write unique, diverse, and comprehensive unit tests for Python objects given the description of the object. The format of test cases should be: "'yython
assert function_nand (input_1) expected_outputt_]] "Test
case 1 description"
assert function name (input_2) expected_outtut._ "Test
case 2 description" "
DO NOT use pytest or unittest frameworks for this task. Stick to small inputs that you can easily verify the output for.
This approach ensures the generation of validation tests that are both human-readable and executable, enabling robust evaluation of proposed solutions. By iterating through test generation, feedback, and solution refinement, the process aligns closely with real-world software development practices and ensures that the generated solutions correct and efficient.
1.2 TEST ACCURACY EXPERIMENTS
In this section, we assess the impact of incorporating ground-truth validation tests on verifier accuracy, as shown in Table 18. We compare three configurations: no ground-truu tests ("None"), using ground-truth truth tests, and utilizing all available tests. These variations allow us to explore how different amounts of external validation influence the performance of our verifier.
The results demonstrate clear improvement in Pass@1 and validation scores when ground-truth tests are introduced. With no external tests, the Pass@1 rate 82.5%, which increases to 87.2% when 3 tests are used and further to 89.0% with all tests. Similarly, the validation score improves from 0.8 to 0.862 and 0.864, respectively. These enhancements reflect verifier's increased accuracy when more reliable validation signals are available.
30

---

Published as a conference paper at ICLR 2025
Table 18: Performance metrics when given different amounts of ground truth tests. self-generated tests were used for validation in 'None'. We ran gpt-3. 1est-3.5-turboe. 5-turbo-0611 for 10 iterations for each setting.
Metric
None
tests
All tests
Pass @ Any
89.0%
90.2%
90.2%
Pass
82.5%
87.2%
89.0%
Validation score
0.813
0.862
0.864
BERT sim.
0.9945
0.9952
0.9949
TF-IDF sim.
0.743
0.767
0.762
Levenshtein sim.
0.721
0.739
0.729
Token seq. sim.
0.765
0.758
0.757
False positive rate
6.3%
9.8%
1.8%
False negative rate
27.5%
2.4%
3.7%
True positive rate
55.0%
78.0%
85.4%
True negative rate
11.3%
9.8%
9.1%
Iters. (incl)
1.68
2.34
2.04
Iters. (excl)
5.06
6.86
5.88
J SEED SCATTERING THEME
We calculate the validation score as shown below:
Mean validation score
Σ
Σ sESp
proportion of validation tests passed
(12)
X
Spl
We explore four themes: "None", "Jabberwocky". "Style", and "Role" to assess their impact various evaluation metries, including Pass@1 1, validation score, and similarity measures (BERT, TF-ID, Levenshtein, and token sequence). Additionally, provide false positive and negative rates, as well as true positive and negative rates, to further analyze the effects of the seed themes on performance in Table 19.
We also present examples of the SCATTERING seed instructions used for each theme and the metaprompt used generate those instructions.
Table 19: Performance Metrics for varies seed instruction themes.
Seed instruction theme
None
Jabberwocky
Style
Role
Pass@1
72.50%
74.38%
79.38%
81.88%
Validation score
0.7786
0.7658
0.7548
0.7649
BERT similarity
0.9976
0.9944
0.9929
0.9957
TF-IDF similarity
0.9013
0.7559
0.6826
0.7734
Levenshtein similarity
0.8971
0.7749
0.7119
0.7907
Token sequence similarity
0.9361
0.8444
0.7504
0.8323
False positive rate
0.0500
0.0438
0.0500
0,0438
False negative rate
0.3000
0.3063
0.3500
0.3438
True positive rate
0.4250
0.4375
0.4438
0.4750
True negative rate
0.2250
0.2125
0.1563
0.1375
Pass Any
75.00%
81.88%
88.13%
87.50%
Metaprompt: Roles of Software Engineer
What are different possible roles that software engineer can have, and what are the charac- teristics of each role?
31

---

Published as a conference paper at ICLR 2025
You problem solver. You are analytical, logical, detail-oriented. You thrive tackling complex problems and finding efficient solutions, enjoy the challenge of debugging and often issues as puzzles be solved, and methodical in your approach and persistent your efforts to overcome obstacles.
You are innovator. You are creative, visionary, adaptable. You are always looking for new ways to apply technology. You are not just interested in how things work but also in how they can be improved or transformed. You enjoy pioneering new techniques and technologies and are comfortable with experimentation and risk-taking.
You are communicator. You are interpersonal, collaborative, empathetic. You excel in environments where teamwork and collaboration are key. You are skilled at explaining complex technical details in simpler terms and bridging the gap between technical teams and non-technical stakeholders. You value relationships and work well in roles that require negotiation and coordination.
Metaprompt: Instructions for Writing Code Different Styles
What are ten different possible instructions you can give software engineer before they write code, instructing them to write code in three different styles.
Write the code in highly modular way, breaking down functionality into small, reusable components. Each function or class should have single responsibility, and avoid large monolithic structures.
Use an object-oriented approach where each concept is modeled as class. Leverage inheritance, encapsulation, and polymorphism to create flexible, scalable design.
Write the code in functional programming style, avoiding mutable state and side effects. Use pure functions, higher-order functions, and recursion where appropriate.
Metaprompt:
Jabberwocky Poem by Lewis Carroll
Recite the poem "Jabberwocky" by Lewis Carroll.
'Twas brillig, and the slithy toves. Did gyre and gimble in the wabe:
All mimsy were the borogoves, And the mome raths outgrabe.
Beware the Jabberwock, my son! The jaws that bite, the claws that catch!
32

---

Published as a conference paper at ICLR 2025
K
WHY SCATTERING IS USEFUL FOR SOLUTION-LEVEL TREE SEARCH
Monte Carlo Tree Search (MCTS) is a powerful algorithm used to navigate large decision spaces by balancing exploration and exploitation. At each step, MCTS selects actions based on a combination of their estimated value (exploitation) and their potential for uncovering better outcomes (exploration), typically guided by metrics such as the Upper Confidence Bound for Trees (UCT). The algorithm works by iteratively expanding the most promising nodes in the search tree, simulating outcomes, and backpropagating the results to refine its decision-making process. This iterative cycle helps MCTS focus on regions of the search space that are likely to yield optimal solutions while still dedicating some effort to exploring unvisited nodes.
The main challenge with using MCTS in our setting arises from the mechanism through which new solutions are proposed by the Large Language Model (LLM), While MCTS encourages exploration by prioritizing less-visited nodes, the diversity of exploration is fundamentally constrained by the similarity of the proposed solutions. Even if MCTS efficiently navigates the tree, if the solutions generated by the LLM are inherently similar, the result is limited exploration of the broader solution space.
This issue becomes even more pronounced in scenarios with large action spaces, such where the action space encompasses all possible code solutions within a given length. Traditional MCTS struggles in such settings because effective exploration and exploitation require the expansion of numerous unvisited actions. Since it is computationally infeasible to exhaustively explore all possible actions, selective expansion becomes critical. Without mechanisms enhance the diversity of these selected actions, the exploration remains suboptimal.
setting,
K.1 TOKEN-LEVEL VS. KOLUTION-LEVER TREE SEARCH
significant distinction between our approach and prior works lies the level at which MCTS operates. In traditional applications, MCTS is often employed at the token level, where it explores possible next tokens during the generation of a single solution. At this level, the LLM's log- probabilities can be used select the top k tokens, which are typically diverse enough to lead to varied outcomes. Token-level MCTS effectively balances exploration and exploitation due to the inherent variability in token selection.
In contrast, our method applies MCTS at the solution level, where each action corresponds to a complete code solution rather than individual tokens. While this approach enables broader exploration of high-level solutions, it introduces new challenges. Simply selecting the first k: responses generated by the LLM often results in highly similar solutions, as the LLM tends produce consistent outputs given the same prompt. Consequently, the lack of diversity in the selected actions undermines the effectiveness of MCTS in exploring the solution space, even when prioritizes less-visited nodes.
K.2 ROLE OF SCATTERING FOR SOLUTION-LEVEL TREE SEARCH
To address these limitations, we introduce the Scattering technique, which explicitly diversifies the prompts used for solution generation. By incorporating varied seed themes or directions into the prompts, Scattering ensures that the L.M generates broader range of candidate solutions. This increased diversity enhances the exploratory capabilities of MCTS, enabling it to better navigate the solution space.
Experimental results in Section 3.5 demonstrate the effectiveness of Scattering. As shown in Table 1, solutions generated without Scattering (seed theme=None) exhibit high similarity across all metrics. leading to poorer performance. In contrast, using Scattering significantly reduces the similarity of generated solutions and improves performance metrics, depicted in Figure 11. This improvement highlights the critical role of Scattering in enabling MCTS to effectively explore large and complex action spaces.
These results underline the importance of fostering diversity in proposed actions to unlock the full potential of MCTS large and complex action spaces, further validating the utility of the Scattering technique.
33

---

Published as a conference paper at ICLR 2025
L ADDITIONAL EXPERIMENTS ON APPS COMPETITION-LVEL PROBLEMS
To further evaluate the performance of our method, we conducted additional experiments on the APPS competition-leve problems using ground-truth test cases. We report classic pass@K metrics as well as additional metrics designed to highlight performance variations under different resource budgets. Specifically, we measure:
Pass@ 10Req: The proportion of problems solved within a budget of 10 LLM requests per method.
Pass@ntok: The proportion of problems solved under specified output token budget (n).
Pass@5 and @ 10: Standard metrics measuring the success rate when is the number of submissions allowed.
Table 20 compares the performance of different methods under these constraints using GPT-3.5-turbo. Our approach outperforms the baselines across all evaluation criteria, demonstrating its robustness and efficiency constrained settings.
Table 20: Comparison of Methods on APPS Competition-Leve Problems (Ground-Truth Test Cases, GPT-3.5-turbo)
Method
Pass 10Req
Pass@5
Pass @ 10
Pass@ 1000tok
Pass 2000tok
Ours
16.1%
14.9%
19.7%
14.4%
16.7%
No Scattering
10.2%
9.2%
10.5%
9.1%
10.4%
No Foresting
12.9%
12.6%
13.0%
12.2%
12.7%
No Scouting
14.9%
14.7%
16.8%
12.1%
15.2%
Line (Reflexion)
(Shinn et al., 2023)
7,5%
7.2%
7.3%
7.5%
Best N (BoN) (Li et al., 2022)
11.0%
10.8%
11.0%
10.8%
11.0%
FunSearch
(Romera- PRomera-Paredes et al., 2024)
9.9%
9.2%
9.9%
9.0%
9.9%
REx
(Tang et al., 2024)
13.5%
12.1 %
13.5%
12.2%
13.5%
Self-repair
(Olausson et al., 2023b)
9.3%
8.6%
10.7%
7.6%
10.1%
Tree (LATS)
(Zhou et al., 2024)
9.0%
8.5%
9.0%
8.2%
8.9%
Tree with PUCT
9.0%
8.9%
9.0%
8.8%
9.0%
Our method achieves superior performance across all metrics, demonstrating robustness and scala- bility under constrained settings. The removal of each core Sumponent-Scattering. Foresting, and Scouting results significant performance degradation, underscoring their necessity in achieving strong results. Among baseline methods, the REx approach performs best, followed by Best-of-N (BoN), showing the effectiveness strong baseline search methods.
34

---

Published as a conference paper at ICLR 2025
M THEORY ILLUSTRATION
We can imagine each code generation is a node the search graph, and generating a new code solution given the current code and the feedback (lest cases) can be seen as a transition from one node to another stochastically. The problem with direct generation of code is that they are highly similar, so the search process can "trapped" in local cluster where all nodes within have similar performance. The concentrated nature of the generated solutions might arise from the limited diversity inherent in post-training objectives (Ouyang et al., 2022; Rafailov al., 2023) commonly employed train chatbots. These objectives often prioritize
large language models (LLMs) as instruction-followe optimizing the model to produce single, correct answer. Consequently, repeated sampling from the model tends to yield highly similar outputs, offering minimal benefit from additional inference-ting computation. Specifically, the whole solution space can be imagined to consist of several such node clusters. The text-based improvement direction, based on what observed, highly different solutions the improvement direction is different. This can be seen as a direct edge connecting different node clusters. Such edges do not exist without text-based improvement direction. This is what Equations and 4 try to establish.
help prompt
Figure 19: Illustration of Diverse Code Generation. Left: Direct code generation explores
solutions in local cluster, leading limited diversity. Right: Text-based improvement directions create transitions between clusters, enabling diverse solution exploration.
Direct code generation
Text guidance (from point)
Small probobiiitt
Direct code generation trapped within single cluster of similar solutions.
Text-based improvement introduces cross- cluster transitions, increasing solution diver- sity and escaping local optima.
35

---

Published as a conference paper at ICLR 2025
N MCTS SELECTION POLICY
We evaluate two Monte Carlo Tree Search (MCTS) selection policies: PUCT (Predictor Upper Confidence Bounds for Trees) and UCT (Upper Confidence Bounds for Trees). Both policies aim to balance exploration and exploitation during search, dynamically selecting promising directions for exploration.
N.1 SELECTION POLICIES: PUCT
PUCT extends UCT (eq. 1) by incorporating policy prediction term IT d), which biases explo- ration based on prior probability distribution:
log (n(#))
P-UCT(s, d) = =Q(s,d) B(s)- Prranstommrr (d)
V
1+ ++nnssd
(13)
where:
((s, d) is the estimated g-value for state and direction d,
Pransformer( (dls) is the probability of taking direction d given the partial program 8, as predicted by the LLM,
n(s) = E. n(s, , b) is the total number of visits to state s, n(s, d) the number of visits to direction in state s, (s) is the weight for exploration, defined as:
((()) Chase +
1
((s) log
+ C,
(14)
Opase
where Obase and are hyperparameters that control the exploration--xxploitatio balance.
The performance PUCT heavily relies on the quality of ((s, d), which in our case derived from the cumulative token probabilities of the underlying language model (LLM). We use the same formula as in (Zhang et al., 2023d).
N.2 WHY PUCT AND UCT PERFORM SIMILARLY IN OUR SETTING
Our experiments reveal that PUCT and UCT achieve similar performance levels when applied to MCTS with self-feeding search (SFS). As shown in Fig. 22 and Table 21, PUCT depends on the quality of the policy predictor, which based on the cumulative token probabilities output by the LLM. However, in our specific setting, these probabilities do not provide strong guidance for policy-basee exploration. This limitation arises because:
Token-level predictions are not aligned with global solution quality: The cumulative proba- bilities from the LLM optimized for next-token prediction, rather than for evaluating the overall quality of solutions at different nodes in the search tree.
2. Sparse alignment between token probabilities and decision-making: For many problems in HumanEval, the token-level likelihoods fail to correlate well with successful code comple- tions, leading to suboptimal guidance for PUCT.
3. Robustness of UCT the absence strong priors: UCT relies purely on the empirical q-value estimates and visit counts, which are updated during the MCTS process. This allows UCT to perform well even without high-quality priors.
Overall, while PUCT offers theoretical advantages when high-quality priors are available, its depen- dency the LLM's 's token probabilities limits its effectiveness in our setting, leading comparable performance with UCT.
36

---

Published as a conference paper at ICLR 2025
PUCT vs UCT comparison
0.85
0.80
Proportion
0.75
0.70
Ours (PUCT)
Tree (UCT)
0.65
Tree (PUCT)
2
10
Number of solutions generated
Figure 22: PUCT vs UCT scaling performance for both SFS and tree search. Propor- tion of problems where the correct solution was discovered by method on HumanEval with gpt-3. 5-turbo0613 with 10 iterations. PUCT depends on the quality of policy predictor pre- dictions, which are based the cumulative token probabilities from the LLM in our case.
Table 21: Metrics for different MCTS selection policies. We run search methods for 10 iters, each using gpt-3. 5-turbo on HumanEval. PUCT and UCT achieve similar performance with SFS
Method
pass@1
pass @ any
BERT sim.
val. score
iters. (inel)
iters. (excl)
Tree (PUCT)
73.8%
75.0%
0.9996
0.799
2.84
9.46
Tree (UCT)
75.6%
76.9%
0.9998
0.827
2.61
8.87
Ours (PUCT)
78.8%
86.3%
0.9943
0.788
2.13
5.88
Ours (UCT)
82.5%
89.4%
0.9945
0.813
1.68
5.06
37


Reviews:
[{"review_id": "VWbsu3rPuH", "reviewer": "Reviewer_DZCq", "summary": "This paper frames code generation as a black box optimization problem within the code space, and employ optimization-inspired techniques to enhance exploration of the space. They introduce SCATTERED FOREST SEARCH to enhance solution diversity while searching for solutions. Their method improves performance by 4-8% on HumanEval+ and HumanEval", "questions": "What is the actual cost of the tree-search base inference per instance in comparison to other prior search methods, for the same budget\nWould be interesting to see whether such tree-search techniques prove helpful in popular challenging benchmarks like SWEBench", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- A timely and appropriate direct of exploration for competitive programming tasks \n- Extensive experiments and ablations on different benchmarks\n- Their proposed search mechanism provides a good boost in performance, also in comparison to other search methods", "weaknesses": "- All experiments are only based on gpt-3.5. Showing the performance on at least some SoTA open source llm is helpful to understand the generality of usage of this method.", "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": "GOFyK5CEbR", "reviewer": "Reviewer_Jy4v", "summary": "This paper focuses on scaling inference computing of language models for code generation. The paper proposes Scattered Forest Search (SFS), which involves the following steps: 1) scattering: choosing different search directions given a solution; 2) foresting: starting searching from different initial solutions; 3) scouting: sharing insights across search branches.\n\nEmpirically, SFS outperforms some well-accepted baseline algorithms: Best of N (BoN) and tree search, on HumanEval, MBPP, and other coding benchmarks.", "questions": "See my questions in the weakness section above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is well-written and easy to follow. The illustrations and examples are beneficial for understanding the paper.\n\nThe SFS algorithm is overall presented clearly. Although it’s similar to most search-based algorithms in the literature, it has a novel design and outperforms BoN and tree search empiriically. Ablation studies are done to understand the contributions of each component (Sec. E).", "weaknesses": "## Primary Concerns\n\nThe paper can be stronger with more thorough empirical evaluations and clearer justification on why it’s better than tree search. Specifically:\n\n**Empirical results.** The number of solutions generated is small (up to 10). How does the algorithm perform with larger numbers of solutions (k)? In our words, do MCTS and BoN catch up with SFS with larger k’s?\n\nI’m not sure if the authors have considered the strongest baselines. The authors seem to use the standard MCTS algorithm (Eq. (1)). Have the authors considered P-UCT, which considers the probability of direction $d$ prescribed by the language model? See Eq. (3) in [2].\n\n**Comparison with tree search.** Can authors clarify why tree search algorithms produce similar results (caption of Fig. 3)? Tree search algorithms like MCTS should do explicit exploration, so they inherently perform the scattering step in SFS?\n\n## Other Comments\n\n**Presentation.**\nIt would be clearer to have an algorithm block to clarify how the three components work together. Specifically, how does the global memory work? Do you only keep the global memory for the last few steps (otherwise it may not fit in the prompt)?\n\n**Related work.**\nFunSearch [1] has a similar idea of exploring the search space which is not mentioned in the paper.\n\n**Miscellaneous:**\n\nLine 208: si, di -> s_i, d_i.\n\nLine 241-242: The insights will then be store[d] in the global memory.\n\n**References:**\n\n[1] Romera-Paredes, Bernardino, et al. \"Mathematical discoveries from program search with large language models.\" Nature 625.7995 (2024): 468-475.\n\n[2] Zhang, Shun, et al. \"Planning with large language models for code generation.\" arXiv preprint arXiv:2303.05510 (2023).", "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": "vKDntMuX8v", "reviewer": "Reviewer_zwDf", "summary": "This paper discusses the search strategy with LLM-based operators for code generation. It has an interesting prompting method to increase the diversity of LLM generations: first ask LLM to generate a list of chain-of-thoughts (COTs) and then ask LLM to generate code given each chain of thought. The generated COTs tend to be more diverse due to the itemized prompting and then the codes get more diverse. It also caches the chain of thoughts to reuse on other codes. One more claimed contribution is using a forest of search trees to \"encourage exploration\". It compares with simple baselines and reports improved performance in a customized setting.", "questions": "See the weakness for details. \n\n* Are there clearer descriptions of the method, from the overall pipeline to each component such as the reward/value design? \n* Are there results without the self-generated test cases which are neither this paper's contribution nor part of standard benchmarks? \n* Are there results of more popular baselines than simple line-search? \n* Are there more detailed descriptions of the experimental settings, including how many LLM requests are used? \n* Are there ablation studies in a cleaner or more standard setting?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The itemized chain-of-thought generation prompting method is interesting. It seems to be a general, intuitive, and easy-to-implement prompting method that could potentially be applied in many other reasoning-based domains where the diversity of LLM generations is important. It also unleashed the most significant improvement in the ablation study. I would recommend the authors to test this prompting technique in more domains such as generating math proofs. It would be an interesting addition to our toolbox for LLM-based reasoning. \n\nCode generation is an important domain to study.", "weaknesses": "* **Non-standard and vague experimental setting**s: This paper claims to use 6 self-generated test cases for each problem to solve. However, I couldn't find any related descriptions or details about how they generate them. The self-generated test cases are neither the contribution of this paper nor part of some public datasets/benchmarks. It is thus hard to reproduce and compare results from this paper with other methods in this domain. It is also unclear how many LLM requests/tokens they use in these experiments. \n* **Missing baselines; only simplest baselines**: There are many more papers discussing the search strategy with LLM-based code refinements/generation (exploration v.s. exploitation), such as Fun-Search [1] based on evolution search and REx[2] based on bandits algorithms. There are many more popular hard-coded tree expansion policies in the field such as [3,4].\n* **Missing details of the method**: There are many confusing or missing descriptions of the method such as (1) the definition of rewards/values for each action/code; (2) how to initialize Q in UCB/MCTS; (3) how to generate test cases; (4) what is the overall pipeline? how many LLM requests for each \"submission\"? \n* **Complicated method; Unclear contributions of each component**: This paper includes many components in its method including (1) self-generated test cases, (2) itemized COT prompting, (3) UCB-based tree-expansion policy, (4) reusing COTs, (5) \"foresting\", and so on. It is unclear how each component contributes to the performance. I would suggest the authors perform ablation studies in a more common/standard setting, removing influences of components that are not part of this paper's contributions. \n\n\n[1] Romera-Paredes, Bernardino, et al. \"Mathematical discoveries from program search with large language models.\" Nature 625.7995 (2024): 468-475.\n\n[2] Tang, Hao, et al. \"Code Repair with LLMs gives an Exploration-Exploitation Tradeoff.\" arXiv preprint arXiv:2405.17503 (2024).\n\n[3] Olausson, Theo X., et al. \"Is Self-Repair a Silver Bullet for Code Generation?.\" The Twelfth International Conference on Learning Representations. 2023.\n\n[4] Wang, Ruocheng, et al. \"Hypothesis search: Inductive reasoning with language models.\" arXiv preprint arXiv:2309.05660 (2023).", "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": "iJgoEV3LAy", "reviewer": "Reviewer_hhUS", "summary": "This paper propose a novel in-context learning workflow, which iteratively prompts a PLM to address diverse code generation tasks. Concretely, the authors proposes a reinforced tree search paradigm, termed 'scarttered forest search',  which first initializes multiple seed solutions through promping the PLM with diverse coding requirements, then proceeds the expansion of the forest search by selecting  the improvement direction with maximum UCT score. During the optimization, a global experience pool is maintained to help the exploitation. The results of the proposed searching paradigm show superiority to existing baselines, with certain diversity improvement.", "questions": "See weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Overall, the motivation of this paper is clear. The related works are properly elaborated. The experimental results are solid.", "weaknesses": "Although the motivation of this paper is quite clear, there are stll several issues on the rejection side:\n\n1) The elaboration of the methodology is still far from sufficient clarity. In particular, what is the overall workflow of this paper? Can you provide a pesudocode?  \n\n2) Besides, in Section 3.1, what is the 'b' in Eq. (1)? In Section 3.3, how do you utilize the collected insights exactly? In Section 3.4, I am confused about the improvement direction 'd', which is also generated by PLM, why it is rather diverse than concentrated?\n\n3) For me, the importance of studying how to train a LM for accurate code generation outweights the importance of studying how to prompt a PLM. This is why I denote this paper as a 'fair contribution' one.  Could the authors provide an in-depth discussion on this point to at least reveal for future readers that there is a tradeoff between the above two research direction?\n\n4)  The experimental analysis lacks a visualization or demonstration that the proposed method really escapes the local optimal, from the results in the shown tables, I can only say that the proposed method escapes the local optima found by previous method and falls into a nes local optima now. Can the authors give a clear demonstration of what they promised in the abstract: 'Our theoretical analysis illustrates how these methods avoid local optima during optimization.'", "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": "YafaKN5PW0", "reviewer": "Reviewer_4VU2", "summary": "This paper proposes SCATTERED FOREST SEARCH to encourage LLMs to produce diverse outputs. The approach incorporates scattering, foresting, and scouting techniques to strike a balance between exploration and exploitation. Extensive experiments on code generation benchmarks demonstrate its effectiveness.", "questions": "* Has the time or space complexity been considered for the code generation task studied in this paper?\n* How do you ensure that the textual directions are orthogonal, as mentioned in line 182?\n* I'm curious about the performance of the proposed framework when applied to solve combinatorial optimization problems, such as TSP.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* This paper is well-organized and clearly structured.\n* The proposed method is sound and novel.\n* The author provides a theoretical foundation for the approach.\n* The experiments are thorough, and the method demonstrates strong empirical performance.", "weaknesses": "* The notations in Section 3 are unclear and could benefit from clarification.\n  * What does $b$ represent in Eq. (1)? \n  * The subscripts in lines 208-209 are incorrect.\n  * In line 161, the specific direction is denoted as $d_i$, but $d_{0i}$ is used in line 206. \n  * How to initialize $\\hat{Q}(s,d)$? \n  * How is $UCT(s,d)$ used to select directions? \n  * $s$ denotes the solution in Section 3.1, but $d$ is used in line 240.\n  * It would be better to add a preliminary section to introduce MCTS.\n* The proposed framework introduces several layers of complexity but lacks a discussion on time complexity. How does its efficiency compare to the baseline methods?\n* Minor: The figures are not clear. Please use PDF format for better readability.", "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 (Poster)