Scattered Forest Search: Smarter Code Space Exploration with LLMs

## Abstract

Abstract We propose a novel approach to scaling LLM inference for code generation. We frame code generation as a black box optimization problem within the code space, and employ optimization-inspired techniques to enhance exploration.
Specifically, we introduce \method to enhance solution diversity while searching for solutions.
Our theoretical analysis illustrates how these methods avoid local optima during optimization. Extensive experiments on HumanEval, MBPP, APPS, CodeContests, and Leetcode reveal significant performance improvements.
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 method scales more efficiently than existing search techniques, including tree search, line search, and repeated sampling.

## 1 Introduction

Figure: 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.
Refer to caption: extracted/5943404/graphics/neurips_quarter-02.png

Recent work highlights the effectiveness of scaling inference compute over training compute  (Snell et al., ; Brown et al., ; Gandhi et al., ). The most common approach by far is to repeatedly sample from the LLM with the same prompt and filter out the best response using a verifier, also known as best-of-N sampling  (Cobbe et al., ; Lightman et al., ). Methods that leverage feedback from the verifier to revise previous solutions in a line or tree-like fashion have also been explored  (Feng et al., ; Chen et al., ). Code generation is one such setting where scaling LLM inference through repeated sampling has also been effective  (Wang et al., ; Chen et al., ).

Inference scaling is effective because, given enough attempts, the LLM is likely to sample the correct solution eventually (Snell et al., ; Brown et al., ). Therefore, 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.11). Hence, a sampling and testing approach that balances exploration and exploitation can greatly improve inference scaling.

To tackle this issue, we propose framing solution generation as a black-box optimization problem  (Golovin et al., ) (as illustrated in Figure 1), in which validation tests serve as the black box and the LLM functions as the optimizer (Yang et al., ).
Drawing from optimization theory, we develop \method(SFS) to efficiently search for code solutions that successfully pass the maximum number of validation tests.
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 to 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 containing syntax errors.

Figure: Figure 2: Scaling curve for different search methods. We run each method for 10 iterations total using gpt-3.5-turbo on APPS and report the proportion of problems where the correct solution has been discovered at each iteration.
Refer to caption: extracted/5943404/graphics/scaling_tease.png

Additionally, drawing inspiration from ant colony optimization and particle swarm optimization, we introduce Scouting to enhance Scattering by sharing feedback and experiences across search branches. When one branch discovers positive (or negative) results by following a specific textual direction, this information 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 local search regions when sampling from LLMs.

Our parameter-free method is simple yet effective.
It does not require additional training or labelled data, yet achieves great performance. As illustrated in Figure 2, our method is able to discover the correct solution significantly faster than the other approaches.
We evaluate our method on five different code generation benchmarks, HumanEval  (Chen et al., ), MBPP  (Austin et al., ), 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-art 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 analyze the lack of diversity in current LLM code search processes and frame code generation as a black-box optimization problem within the language space, emphasizing the need for a balance between exploration and exploitation.
- •
We introduce \method(SFS), composed of techniques Scattering and Foresting that enhance the search process by encouraging broader exploration of the code space through textual optimization and seed initialization. We also provide a theoretical explanation for their effectiveness. Additionally, we present Scouting, which further improves SFS by exploiting promising search directions.
- •
We demonstrate that our method significantly enhances the accuracy, scalability, and solution diversity of the search process across widely used code generation benchmarks, including HumanEval, MBPP, Leetcode, APPS, and CodeContests.

## 2 Background

Figure: 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.
Refer to caption: extracted/5943404/graphics/neurips_quarter-07.png

### 2.1 Problem description

In the task $\bm{x}=\langle\bm{p},\bm{H}\rangle$ of program synthesis, the solver is given a prompt $\bm{p}$ in natural language, which asks the solver to write code for some object $\bm{s}$. The goal is to complete the code implementation of $\bm{s}$ such that it passes all the hidden tests $\bm{H}$. The solver is not allowed to see the hidden tests. Sometimes, the solver is also given validation (visible) tests $\bm{V}$ that they can test their solution $\bm{s}$ on before they submit it for evaluation on the hidden tests $\bm{H}$. They can also generate their own validation tests $\bm{V}$. Usually both hidden and validation tests are in the form of a set of assert statements that test the functionalities of $\bm{s}$. An example of one such code generation task is shown in Appendix B.

A solution $\bm{s}^{\prime}$ is said to be correct if it passes all the hidden tests $\bm{H}$. The solver is allowed $k$ submissions $[\bm{s}]_{k}$ to the hidden tests. If at least one submission $\bm{s}^{*}$ passes all the hidden tests, then the task is considered to be solved. Given a set of tasks $\mathcal{X}$, the proportion of tasks $\langle\bm{p},\bm{H}\rangle\in\mathcal{X}$ that are solved by the agent is called the pass@k rate  (Chen et al., ).

### 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 LLM, which are shown in Figure 6. We elaborate more on the pros and cons of each method under a code space optimization framework below:

Best of N (BoN), or repeated sampling, involves sampling multiple independent solutions $[\bm{s}]_{n},\bm{s}\sim\texttt{LLM}(\bm{p})$ from a language model using the same prompt $\bm{p}$. The best solution $\bm{s}^{*}$ is then selected based on a verifier, commonly the number of validation tests passed (Li et al., ; Chen et al., ).

Line search begins by sampling an initial seed code $\bm{s}_{0}\sim\texttt{LLM}(\bm{p})$. It then iteratively refines the previous solution $s_{i-1}$ based on its test feedback $\bm{f}_{i-1}$  (Shinn et al., ; Madaan et al., ). This iterative self-refinement leverages test execution feedback to guide the model toward sampling successful solutions, i.e. $\bm{s}_{i}\sim\texttt{LLM}(\bm{p}|\bm{s}_{i-1},\bm{f}_{i-1})$. However, line search is limited by its rigidity – requiring improvements on the most recent solution, even if the latest edits are incorrect. Thus, it struggles to effectively explore the search space and is more likely to get stuck in local optima.

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 et al., ; Chen et al., ; Hao et al., ; Yao et al., ; Zhou et al., ; Tian et al., ). Given a parent solution $\bm{s}_{i}$ and its feedback $\bm{f}_{i}$, the LLM produces $k$ child solutions $\bm{s}_{i0},\bm{s}_{i1},...,\bm{s}_{ik}$. Although higher temperatures can produce diverse solutions, in practice, these solutions often resemble each other because they originate from the same prompt (refer to Sec. 11). Consequently, tree search still faces challenges in fully exploring the search space.

## 3 Methodology

Our method incorporates three optimization inspired techniques to enhance both exploration and exploitation of tree search (MCTS) using LLMs.

Figure: Figure 7: Core techniques used by SFS. Points represent solutions. Hexagons represent initial solutions. Star represents the final selected solution.
Refer to caption: extracted/5943404/graphics/neurips_quarter-04.png

### 3.1 Tree branch Scattering

In tree search, children solutions of the same parent solution tend to be highly similar to one another since the LLM is given the same prompt to generate the children. We encourage more exploration when generating children solutions by querying the LLM to generate possible improvement directions $[\bm{d}]_{n}$ first.
The LLM is then instructed to implement a specific direction $\bm{d}_{j}$ for each child $\bm{s}_{ij}$ that it generates from parent $\bm{s}_{i}$. This helps us explore different, often orthogonal, improvement directions that help us explore a wider region of the search space, similar to trust-region methods in numerical optimization (xiang Yuan, ). We refer to this technique as Scattering the tree branches.

$$ $\text{\parbox{85.35826pt}{\centering feedback from validation tests \@add@centering}}\quad\rightarrow\quad\text{\parbox{85.35826pt}{\centering propose new textual directions using LLM\@add@centering}}\quad\rightarrow\quad\text{ \parbox{113.81102pt}{\centering choose 1 direction to implement when branching \@add@centering}}$ $$

Furthermore, we employ MCTS and utilize the UCT formula (Eq. 1) to dynamically select directions for exploration, as illustrated below

$$ $UCT(\bm{s},\bm{d})=\widehat{Q}(\bm{s},\bm{d})+c\sqrt{\frac{\ln\left(\sum_{\bm{ b}}n(\bm{s},\bm{d})\right)}{n(\bm{s},\bm{d})}},$ (1) $$

where $c$ is the exploration parameter, $n(\bm{s},\bm{d})$ is the number of visits of direction $\bm{d}$ at solution $\bm{s}$, and $\widehat{Q}(\bm{s},\bm{d})$ is the estimated $q$-value which is updated via backpropogation as follows:

$$ $\widehat{Q}(\bm{s}_{i},\bm{d}_{i})^{(t+1)}\leftarrow(1-\alpha(n))\widehat{Q}( \bm{s}_{i},\bm{d}_{i})^{(t)}+\alpha(n)\mathop{max}\{\widehat{Q}(\bm{s}_{i},\bm {d}_{i})^{(t)},\widehat{Q}(\bm{s}_{ij},\bm{d}_{ij})^{(t+1)}\},$ (2) $$

where $\alpha(n)$ is the weighted average parameter that depends on $n(\bm{s},\bm{d})$.
The backpropogation occurs along the entire MCTS simulated trajectory $\tau=[\bm{s}_{0},\bm{d}_{0i},\bm{s}_{0i},...,\bm{s}_{-2},\bm{d}_{-1},\bm{s}_{-
1}]$, where the $q$-value for the penultimate state $\bm{s}_{-1}$ is updated using the evaluation value of the final state $\widehat{Q}(\bm{s}_{-2},\bm{d}_{-1})^{(t+1)}\leftarrow v(\bm{s}_{-1})$ instead. We take the max of $\widehat{Q}(\bm{s}_{i},\bm{d}_{i})^{(t)}$ and the next state’s $q$-value $\widehat{Q}(\bm{s}_{ij},\bm{d}_{ij})$ 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 $\bm{s}_{j}$ over exploring all directions of a parent solution $\bm{s}_{i}$. Using UCT to select distinct actions has been effective in balancing exploration and exploitation in other settings (Browne et al., ).

### 3.2 Forest search and forest Scattering

Iterative refinement faces the challenge that a 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. We refer to this technique as Foresting, in which we generate $n$ seed solutions $[\bm{s}]_{n}$ and dynamically select which seed function to evolve from using the UCT formula (Eq. 1). Specifically, for each MCTS simulation, we select seed function $\bm{s}_{i}$ 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, we can also promote more diverse seed solution generation through 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. 11.

### 3.3 Branch Scouting

Inspired by traditional optimization techniques like Ant Colony Optimization and Particle Swarm optimization, we utilize insights from other branches—specifically, which improvement directions are effective—to enhance the current solution. Specifically, after generating a new solution $\bm{d}_{-1}$ by applying improvement $\bm{d}_{-1}$ to solution $\bm{d}_{-2}$, we provide feedback on the new solution $\bm{f}_{-1}$ to the LLM, inquiring whether the improvement was effective and what general insights it can derive from this. The insights will then be store in global memory, and in future iterations when the LLM is prompted to generate improvement directions, the global insights will be included in the prompt. This approach enables knowledge about effective and ineffective improvement directions to be shared across branches, facilitating more efficient exploitation of the search feedback and thereby enhancing our Scattering technique.

$$ $\text{\parbox{85.35826pt}{use insights to generate directions}}\quad \rightarrow\quad\text{\parbox{85.35826pt}{see if the direction worked or not}} \quad\rightarrow\quad\text{\parbox{85.35826pt}{update insights based on feedback}}$ $$

### 3.4 A Theoretical Perspective

The proposed techniques—Scattering 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, ).
We can define the search strategy as a Markov transition kernel $P(\bm{s},\bm{s}^{\prime})$ which denotes the probability of generating a new solution $\bm{s}^{\prime}$ given the current solution $\bm{s}$.
A chain of self-refined solutions $\bm{s}_{0},\bm{s}_{1},\bm{s}_{2},\dots$ are generated following the transition kernel $P$.

In previous methods including line search and tree search, the transition is realized by an LLM $\pi$ that is conditioned on the previous solution $\bm{s}$ and the feedback $\bm{f}=F(\bm{s})$, denoted by $\pi(\bm{s}^{\prime}|\bm{s},\bm{f})$. The transition kernel is

$$ $\displaystyle P_{\text{previous}}(\bm{s},\bm{s}^{\prime})$ $\displaystyle=\pi_{c}(\bm{s}^{\prime}|\bm{s},F(\bm{s})),$ (3) $$

where we use $\pi_{c}$ to emphasize that the LLM $\pi$ is prompted to output code. We know $\pi(c)$ can be extremely concentrated and outputs highly similar solutions.

With Scattering, we first sample an improvement direction $\bm{d}$ generated by the LLM with prompt $\pi(\cdot|\bm{s},F(\bm{s}))$. And then prompt LLM $\pi$ to generate the next solution $\bm{s}^{\prime}$ given the current solution $\bm{s}$, the feedback $\bm{f}=F(\bm{s})$, and the improvement direction $\bm{d}$. The transition kernel is

$$ $\displaystyle P_{\textsc{Scattering}}(\bm{s},\bm{s}^{\prime})$ $\displaystyle=\sum_{\bm{d}}\pi_{t}(\bm{d}|\bm{s},F(\bm{s}))\pi_{c}(\bm{s}^{ \prime}|\bm{s},F(\bm{s}),\bm{d}),$ (4) $$

where $\pi_{c}$ is still an extremely concentrated policy and outputs highly similar solutions. However, we have a text-based “reflection” $\pi_{t}(\bm{d}|\bm{s},F(\bm{s}))$ that can generate highly diverse improvement directions. In practice, we can observe that indeed the directions are highly diverse.

In Markov chain theory, a diverse transition kernel increases the probability of moving between different regions of the state space (denoted by $\mathcal{S}$), thereby enhancing the conductance $\Phi$ of the chain:

$$ $\displaystyle\Phi_{P}(S)=\frac{\sum_{\bm{s}\in S,\bm{s}^{\prime}\not\in S}\mu( \bm{s})P(\bm{s},\bm{s}^{\prime})}{\mu(S)},$ (5) $$

where $S$ is a subset and $\mu$ is the stationary distribution.

Higher conductance improves the spectral gap $\gamma$, which is inversely related to the mixing time of the Markov chain (see Cheeger’s inequality) (Levin & Peres, ), 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_{\text{previous}}(\bm{s},\bm{s}^{\prime})\approx 0$ when $\bm{s}\in S$ and $\bm{s}^{\prime}\not\in S$, thus the conductance $\Phi$ is near 0 0). While our Scattering search (equation 4) can generate highly diverse directions $\bm{d}$ and lead to new solutions $\bm{s}^{\prime}$ out of the local region $S$ ($P_{\textsc{Scattering}}(\bm{s},\bm{s}^{\prime})>0$ if some $\bm{d}$ gives correct direction).

### 3.5 Empirical validation

Figure: Figure 11: Pass@k rate for repeated sampling with different initialization seed types on HumanEval using gpt-3.5-turbo-0613. Increasing seed variety with Scattering significantly improves both Pass@k rate and scaling.
Refer to caption: extracted/5943404/graphics/random_passk.png

We varied the types of seed instructions used to generate seed code during BoN sampling to validate the effects of increasing solution diversity with Scattering.
In the Jabberwocky setting, the model was prompted with different 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 writing code in a ‘highly modular way’ or ‘focus on brevity and clarity’.
In the Role setting, the model was prompted with different software engineer personalities such as ‘You are an innovator.’ or ‘You are a perfectionist’.
All input prompts were LLM generated by gpt-3.5-turbo around a common theme.

We present the pass@k performance of these seed generation styles in Figure 11, with detailed performance metrics in Tables 1 and 19.
This includes: 1) 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. 6), and 3) the mean BERT cosine similarity between embeddings of candidate solution pairs, averaged over all problems. Embeddings were taken using CodeBERT, a pretrained model for understanding code semantically  (Feng et al., ).

$$ $\displaystyle\text{ Mean BERT cosine similarity}=\frac{1}{|\mathcal{X}|}\sum_{ \langle\bm{p},\bm{H}\rangle\in\mathcal{X}}\frac{1}{|\mathcal{S}_{\bm{p}}|(| \mathcal{S}_{\bm{p}}|-1)}\sum_{\begin{subarray}{c}\bm{s},\bm{s}^{\prime}\in \mathcal{S}_{\bm{p}}\\ \bm{s}\neq\bm{s}^{\prime}\end{subarray}}\frac{\text{embed}(\bm{s})\cdot\text{ embed}(\bm{s}^{\prime})}{\|\text{embed}(\bm{s})\|\|\text{embed}(\bm{s}^{\prime })\|}$ $$

In addition to the metrics we discussed previously, we also include other similarity metrics such as tf-idf similarity, which measures the average cosine similarity between tf-idf vectors, the Levenshtein similarity, and the token sequence similarity. See App. I for more details, including examples.

As shown in Table 1, “Role” and “Style” performed best in discovering the correct solution.
Surprisingly, 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.

**Table 1: Effects of different seed instruction Scattering themes. 10 seed solutions were generated using gpt-3.5-turbo for each theme, and we filtered the seeds using 6 generated validation tests to select the best one to submit for evaluation on the HumanEval benchmark.**
| Seed theme | pass@1 | 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 | 79.4 | 88.1 | 0.6826 | 0.9929 | 0.7119 | 0.7504 | 0.7548 |
| Role | 81.9 | 87.5 | 0.7734 | 0.9957 | 0.7907 | 0.8323 | 0.7649 |

## 4 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-generated Python questions  (Chen et al., ), and MBPP includes 399 problems (Austin et al., ). The original sets included only 3 to 8 hidden tests $\mathcal{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., ).

Both APPS  (Hendrycks et al., ) and CodeContests  (Li et al., ) feature challenging code competition problems. From the 10,000 problems in APPS, we randomly sample 200 for evaluation due to budget constraints. We adapt the competition format of both datasets to resemble the HumanEval format for Python evaluation. Leetcode  (Guo et al., ) 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 see that our method achieves a higher pass@1 rate than other search methods and the base accuracy (i.e., evaluating the first solution that the LLM 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@1 performance reported here. Both solutions and validation tests were generated using gpt-3.5-turbo.**
| 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) at any point during the search process, as shown in Table 3. 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 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@1 to pass@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.

**Table 3: Pass@any accuracy 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 | HumanEval | 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 to existing state-of-the-art works as shown in Table 5 and 5. In Table 5 setting, validation tests are self-generated, and cap our solution budget at 40 generations max, same as in prior literature  (Zhou et al., ). In Table 5, a subset of the ground truth hidden tests are given (3 for HumanEval, 1 for MBPP)  (Zhong et al., ), and we compare against similar methods under this setting. We see that our method achieves higher performance in both settings.

**Table 4: Comparison to prior works when ground truth tests are not given. We report Pass@1 performance with GPT-3.5.**
| Benchmark | HumanEval | MBPP |
| --- | --- | --- |
| CoT  (Wei et al., ) | 46.9 | 54.9 |
| ReAct  (Yao et al., ) | 56.9 | 67.0 |
| Reflexion  (Shinn et al., ) | 68.1 | 70.0 |
| ToT  (Yao et al., ) | 54.4 | 65.8 |
| RAP  (Hao et al., ) | 63.1 | 71.4 |
| LATS(^1^11ran under our setup, see App. D for similar setup)  (Zhou et al., ) | $75.6$ | $79.6$ |
| Ours (SFS) | 82.5 | 81.7 |

### 4.3 Scalability

Figure: Figure 12: Scaling curves for different search methods on CodeContests (left) and Leetcode (right). We run each method for 10 iterations using gpt-3.5, reporting the proportion of problems where the correct solution is discovered at each iteration. Additional curves can be found in Sec. C
Refer to caption: extracted/5943404/graphics/scaling_codecontests.png

We report the average number of iterations (solutions generated) it 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 the algorithm succeeds on the first try. Iters. (excl) is the average number of iterations it takes excluding first try successes, where the search algorithm is actually used to find the correct solution. On both metrics, our method demonstrates the ability to *discover the correct solution much more quickly than the other methods*. Moreover, we see in Figure 2 and 12 that our method also *scales better than the other methods* on all datasets.

**Table 6: Metrics for different search methods. We run different search methods for 10 iterations each using gpt-3.5-turbo on HumanEval. Our method generates more diverse solutions and discovers the correct solution faster.**
| Method | pass@1 | pass@any | BERT sim. | val. score | iters. (incl) | iters. (excl) |
| --- | --- | --- | --- | --- | --- | --- |
| 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 |
| Ours (SFS) | 82.5% | 89.0% | 0.9945 | 0.813 | 1.67 | 5.06 |

### 4.4 Solution diversity

We see in Table 6 that our proposed search method is able to propose more diverse candidate solutions with a 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 too much of one for the other*. Detailed stats shown in App. F.

### 4.5 Ablation on techniques

We performed an ablation study on the three introduced techniques as shown in Table 7 (and App. G), all of which enhanced performance and efficiency, with Scattering yielding the highest gains.

**Table 7: Ablation metrics for techniques used in our method. We run search methods for 10 iterations each using gpt-3.5-turbo on HumanEval.**
| Ablation | pass@1 | pass@any | 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-3.5-turbo-0613 on HumanEval. When the tests are accurate, we can achieve even higher performance, even if only a subset is given.**
| Tests given | pass@1 | pass@any | BERT sim. | val. score | iters. (incl) | iters. (excl) |
| --- | --- | --- | --- | --- | --- | --- |
| 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% | 89.0% | 0.9949 | 0.864 | 2.04 | 5.88 |

### 4.6 Verifier (Validation test) accuracy

Figure: Figure 13: Confusion matrix for self-generated validation tests with gpt-3.5-turbo-0613 using our method.
Refer to caption: extracted/5943404/graphics/confusion.png

Previous work emphasized the importance of a reliable verifier  (Liu et al., ; Chen et al., ; Zhang et al., ). In our case, we use self-generated validation tests noisy as a black-box verifer. Figure 13 shows the confusion 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-truth tests as validation (Table 8).
While finding the best verifier is not our focus, the results show a significant impact of verifier accuracy on performance. There are strong interactions between the search method and evaluation metric—just one ground-truth validation test dramatically improves performance. This demonstrates how well our methods *exploit accurate evaluation signals* and perform even better when the black-box evaluation is more accurate. Detailed metrics shown in App. H.

### 4.7 Ablation on model

Figure: Figure 14: Scaling curve for different LLM-models. We run our method on each model for 10 iterations on HumanEval and report the proportion of problems where the correct solution has been discovered at each iteration.
Refer to caption: extracted/5943404/graphics/scaling_model.png

As shown in Figure 14, weaker models scale better with our method. This supports the trade-off between training and inference compute: better-trained models scale worse with inference compute, and vice versa. Detailed stats in App. E.

## 5 Additional Related work

Code generation with large language models. Some works focus on either training their own model  (Guo et al., ) or fine tuning existing models to adapt them towards code related tasks  (Roziere et al., ; Jain et al., ; Roziere et al., ).
Recent literature has shown a flora of methods to improve LLM code generation performance during inference time, including agentic approaches  (Qian et al., ; Liu et al., ), multi-agent approaches  (Tao et al., ; Hong et al., ; Islam et al., ), tool usage  (Zhang et al., ), and self-revision  (Le et al., ).
Our work compliments these works by showing that increasing solution diversity and exploration can have a large impact on inference scaling.

Solution validation and feedback. Prior work has demonstrated that effective and accurate validation methods significantly boost performance in code generation  (Chen et al., ; ) and related tasks like math theorem proving  (Cobbe et al., ; Uesato et al., ). The importance of a reliable evaluation metric is critical  (Liu et al., ), and incorporating natural language feedback and reflection on execution results further enhances performance  (Zhang et al., ; Bai et al., ). 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 LLMs to search over language and code space.
Our textual optimization steps can be thought of as ‘textual gradients’, though we do not use them to conduct backpropogation  (Yuksekgonul et al., ). There have been some recent works exploring the usage of LLMs as optimizers for different problems  (Zhang et al., ; Liu et al., ), including using evolutionary optimization algorithms  (Lange et al., ; Liu et al., ).

Tree search.
Tree search has proven effective in decision-making domains. Previous works have applied tree search to multi-step tasks, such as determining the next reasoning step  (Silver et al., ; Zhou et al., ; Yao et al., ; Besta et al., ) or generating the next code token  (Zhang et al., ). While prior work primarily uses tree search for planning  (Jiang et al., ; Feng et al., ; Bairi et al., ), we show that *tree search can also be used for optimization*, functioning as a black-box method for exploring a region rather than a line.

## 6 Conclusion

We have shown that framing code generation as an optimization task over the code space and applying \methodis 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 maintaining or enhancing performance, making them attractive for large-scale deployments, especially in real-time applications or 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.

## Appendix: Smarter Code Space Exploration with LLMs

## Appendix 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 to 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 to 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.

## Appendix B Coding problem example

## Appendix C Scaling

Our method scales well with increased iterations. We show scaling curves for each dataset as shown in Figures 15, 16, 17.

Figure: Figure 15: Scaling curves for different search methods on APPS (left) and CodeContests (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.
Refer to caption: extracted/5943404/graphics/scaling_apps.png

Figure: 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.
Refer to caption: extracted/5943404/graphics/scaling_humaneval.png

Figure: 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 of problems where the correct solution is discovered at each iteration.
Refer to caption: extracted/5943404/graphics/scaling_leetcode.png

Figure: Figure 18: High budget scaling performance for our method. Proportion of problems where the correct solution was discovered by our method on HumanEval with gpt-3.5-turbo0613 with 20 iterations.
Refer to caption: extracted/5943404/graphics/scaling.png

## Appendix D Prior works benchmark

In the LATS experimental setup, in 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., ).
We show the performance of our method in the same setup here, with the same solution budget.
We see that given the same setup, our method still achieves higher performance.

**Table 9: Comparison to prior works. We report Pass@1 performance with GPT-3.5.**
| Method / Benchmark | HumanEval | MBPP |
| --- | --- | --- |
| CoT  (Wei et al., ) | 46.9 | 54.9 |
| ReAct  (Yao et al., ) | 56.9 | 67.0 |
| Reflexion  (Shinn et al., ) | 68.1 | 70.0 |
| ToT  (Yao et al., ) | 54.4 | 65.8 |
| RAP  (Hao et al., ) | 63.1 | 71.4 |
| LATS  (Zhou et al., ) | 83.8 | 81.1 |
| Ours (Forest Scouting) | 93.3 | 91.2 |

## Appendix E Ablation on models

In this section, we provide a detailed ablation study on the performance of different base language models, focusing on metrics relevant to the HumanEval benchmark. Table
10 displays the results of applying various search methods across three models: gpt-3.5, gpt-4o-mini, and gpt-4o. 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 11 provides an extended comparison of metrics, including similarity measures like TF-IDF and Levenshtein, alongside error rates (false positives/negatives) and true classification rates, helping to evaluate model behavior in more detail across different performance aspects.

**Table 10: Ablation on models. We run search methods for 10 iterations each on HumanEval**
| Model | pass@1 | pass@any | BERT sim. | val. score | iters. (incl) | iters. (excl) |
| --- | --- | --- | --- | --- | --- | --- |
| gpt-3.5 | 82.5% | 89.0% | 0.9945 | 0.813 | 1.68 | 5.06 |
| gpt-4o-mini | 89.4% | 93.8% | 0.9876 | 0.845 | 0.84 | 5.83 |
| gpt-4o | 90.6% | 95.6% | 0.9915 | 0.894 | 0.68 | 4.95 |

**Table 11: Performance metrics for different base LLM models on HumanEval. We ran gpt-3.5-turbo-0613 for 10 iterations for each model.**
| Metric | gpt-3.5 | gpt-4o-mini | gpt-4o |
| --- | --- | --- | --- |
| Pass@Any | 89.0% | 93.8% | 95.6% |
| Pass@1 | 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 rate | 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 |

## Appendix F 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, HumanEval, CodeContests, Leetcode, and APPS, offer a comprehensive comparison of different search methods used to evaluate large language model (LLM) performance. Each table highlights the results of different strategies, such as Line, Tree-based search (MCTS), Best of N, and our proposed method. Key metrics, 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 a holistic view of model performance, especially in scenarios involving iterative search, with the number of iterations (both inclusive and exclusive) further contextualizing the computational complexity of each method.

**Table 12: Performance metrics for different search methods on HumanEval. We ran gpt-3.5-turbo-0613 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@1 | 68.1% | 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 gpt-3.5-turbo-0613 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@1 | 73.6% | 76.1% | 76.6% | 78.3% |
| Validation score | 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 |

**Table 14: Performance metrics for different search methods on Leetcode. We ran gpt-3.5-turbo-0613 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@1 | 28.9% | 33.3% | 33.3% | 36.7% |
| Validation score | 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 methods on APPS. We ran gpt-3.5-turbo-0613 for 10 iterations for each method.**
| Metric | Line | Tree (MCTS) | Best of N | Ours |
| --- | --- | --- | --- | --- |
| Pass@Any | 22.0% | 21.5% | 23.0% | 32.5% |
| Pass@1 | 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 |
| TF-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 |

**Table 16: Performance metrics for different search methods on Codecontests. We ran gpt-3.5-turbo-0613 for 10 iterations for each method.**
| Metric | Line | Tree (MCTS) | Best of N | Ours |
| --- | --- | --- | --- | --- |
| Pass@Any | 3.0% | 2.4% | 3.0% | 6.1% |
| Pass@1 | 1.21% | 2.42% | 1.82% | 4.24% |
| Validation score | 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 |

## Appendix G Technique ablation

In this section, we present the results of an ablation study to assess the impact of different components 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 techniques—Scattering, Foresting, and Scouting —one at a time.

The ablation results highlight how critical each technique is for achieving high performance. Removing 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 to 0.419. Similarly, removing Scouting results in a slight reduction in performance metrics, but Pass@1 remains comparable to the full method, indicating its robustness.

**Table 17: Performance metrics for different ablations on techniques for our method. We ran gpt-3.5-turbo-0613 for 10 iterations for each ablation on HumanEval.**
| Metric | Everything | No Scattering | No Foresting | No Scouting |
| --- | --- | --- | --- | --- |
| Pass@Any | 89.0% | 78.1% | 86.3% | 86.3% |
| Pass@1 | 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. (incl) | 1.68 | 2.43 | 2.05 | 2.12 |
| Iters. (excl) | 5.06 | 8.82 | 6.56 | 6.05 |

## Appendix H Verifier accuracy and ground-truth validation tests

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-truth tests (“None”), using 3 ground-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 a clear improvement in Pass@1 and validation scores when ground-truth tests are introduced. With no external tests, the Pass@1 rate is 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.813 to 0.862 and 0.864, respectively. These enhancements reflect the verifier’s increased accuracy when more reliable validation signals are available.

**Table 18: Performance metrics when given different amounts of ground truth tests. 6 self-generated tests were used for validation in ‘None’. We ran gpt-3.5-turbo-0613 for 10 iterations for each setting.**
| Metric | None | 3 tests | All tests |
| --- | --- | --- | --- |
| Pass@Any | 89.0% | 90.2% | 89.0% |
| Pass@1 | 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 |

## Appendix I Seed Scattering theme

We calculate the validation score as shown below:

$$ $\displaystyle\text{Mean validation score}=\frac{1}{|\mathcal{X}|}\sum_{\langle \bm{p},\bm{H}\rangle\in\mathcal{X}}\frac{1}{|\mathcal{S}_{\bm{p}}|}\sum_{\bm{s }\in\mathcal{S}_{\bm{p}}}\text{proportion of validation tests passed}(\bm{s})$ (6) $$

We explore four themes: “None”, “Jabberwocky”, “Style”, and “Role” to assess their impact on various evaluation metrics, including Pass@1, validation score, and similarity measures (BERT, TF-IDF, Levenshtein, and token sequence). Additionally, we 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 to 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% |

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
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
Would be interesting to see whether such tree-search techniques prove helpful in popular challenging benchmarks like SWEBench
soundness: 3
strengths: - A timely and appropriate direct of exploration for competitive programming tasks 
- Extensive experiments and ablations on different benchmarks
- Their proposed search mechanism provides a good boost in performance, also in comparison to other search methods
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
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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 4
questions: See my questions in the weakness section above.
soundness: 4
strengths: This paper is well-written and easy to follow. The illustrations and examples are beneficial for understanding the paper.

The 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).
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.

Empirically, SFS outperforms some well-accepted baseline algorithms: Best of N (BoN) and tree search, on HumanEval, MBPP, and other coding benchmarks.
weaknesses: ## Primary Concerns

The paper can be stronger with more thorough empirical evaluations and clearer justification on why it’s better than tree search. Specifically:

**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?

I’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].

**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?

## Other Comments

**Presentation.**
It 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)?

**Related work.**
FunSearch [1] has a similar idea of exploring the search space which is not mentioned in the paper.

**Miscellaneous:**

Line 208: si, di -> s_i, d_i.

Line 241-242: The insights will then be store[d] in the global memory.

**References:**

[1] Romera-Paredes, Bernardino, et al. "Mathematical discoveries from program search with large language models." Nature 625.7995 (2024): 468-475.

[2] Zhang, Shun, et al. "Planning with large language models for code generation." arXiv preprint arXiv:2303.05510 (2023).

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 2
questions: See the weakness for details. 

* Are there clearer descriptions of the method, from the overall pipeline to each component such as the reward/value design? 
* Are there results without the self-generated test cases which are neither this paper's contribution nor part of standard benchmarks? 
* Are there results of more popular baselines than simple line-search? 
* Are there more detailed descriptions of the experimental settings, including how many LLM requests are used? 
* Are there ablation studies in a cleaner or more standard setting?
soundness: 2
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. 

Code generation is an important domain to study.
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.
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. 
* **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].
* **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"? 
* **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. 


[1] Romera-Paredes, Bernardino, et al. "Mathematical discoveries from program search with large language models." Nature 625.7995 (2024): 468-475.

[2] Tang, Hao, et al. "Code Repair with LLMs gives an Exploration-Exploitation Tradeoff." arXiv preprint arXiv:2405.17503 (2024).

[3] Olausson, Theo X., et al. "Is Self-Repair a Silver Bullet for Code Generation?." The Twelfth International Conference on Learning Representations. 2023.

[4] Wang, Ruocheng, et al. "Hypothesis search: Inductive reasoning with language models." arXiv preprint arXiv:2309.05660 (2023).

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: See weaknesses.
soundness: 3
strengths: Overall, the motivation of this paper is clear. The related works are properly elaborated. The experimental results are solid.
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.
weaknesses: Although the motivation of this paper is quite clear, there are stll several issues on the rejection side:

1) 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?  

2) 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?

3) 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?

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

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: * Has the time or space complexity been considered for the code generation task studied in this paper?
* How do you ensure that the textual directions are orthogonal, as mentioned in line 182?
* I'm curious about the performance of the proposed framework when applied to solve combinatorial optimization problems, such as TSP.
soundness: 3
strengths: * This paper is well-organized and clearly structured.
* The proposed method is sound and novel.
* The author provides a theoretical foundation for the approach.
* The experiments are thorough, and the method demonstrates strong empirical performance.
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.
weaknesses: * The notations in Section 3 are unclear and could benefit from clarification.
  * What does $b$ represent in Eq. (1)? 
  * The subscripts in lines 208-209 are incorrect.
  * In line 161, the specific direction is denoted as $d_i$, but $d_{0i}$ is used in line 206. 
  * How to initialize $\hat{Q}(s,d)$? 
  * How is $UCT(s,d)$ used to select directions? 
  * $s$ denotes the solution in Section 3.1, but $d$ is used in line 240.
  * It would be better to add a preliminary section to introduce MCTS.
* The proposed framework introduces several layers of complexity but lacks a discussion on time complexity. How does its efficiency compare to the baseline methods?
* Minor: The figures are not clear. Please use PDF format for better readability.

Meta-review: Summary: 
This paper presents a novel search strategy employing LLM-based operators for code generation. It introduces an innovative prompting method to enhance the diversity of LLM outputs. Specifically, the approach first prompts the LLM to generate a list of chain-of-thoughts (CoTs) and subsequently uses each CoT to guide the generation of corresponding code. The itemized prompting results in more diverse CoTs, which in turn lead to greater diversity in the generated code. Additionally, the method caches CoTs for reuse across different code generation tasks. Another key contribution is the use of a forest of search trees to "encourage exploration" during the search process. The proposed approach is compared against simple baselines, demonstrating improved performance in a customized evaluation setting.

Strengths:
(1) The proposed method looks sound and novel. (2) The author provides a theoretical foundation for the approach. (3) The experiments are thorough, and the method demonstrates strong empirical performance.

Weakness:
This work does not touch much on the design of training dataset, training paradigm and training objective.

Decision:
While the above-mentioned weakness is a notable concern, I believe the novelty and contributions of this paper outweigh it. I recommend acceptance; however, I strongly encourage the authors to consider how their work could contribute to improvements in the training dataset, training paradigm, and training objectives in future iterations.

Decision: Accept (Poster)