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
Primary area: applications to computer vision, audio, language, and other modalities
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

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

Decision: accept (poster)
Reviewer scores: 8, 6, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1729574446264

thread_type:
official_review

<thread_object>
creator: reviewer_4vu2

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

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729695094044

thread_type:
official_review

<thread_object>
creator: reviewer_hhus

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

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:

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

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730569295331

thread_type:
official_review

<thread_object>
creator: reviewer_zwdf

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

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.

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

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730682687168

thread_type:
official_review

<thread_object>
creator: reviewer_jy4v

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

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

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

questions:
See my questions in the weakness section above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730684509067

thread_type:
official_review

<thread_object>
creator: reviewer_dzcq

<content>
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

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

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.

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
</content>
</thread_object>

</thread>
<thread>
creation date:
1732400111732

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of revisions

comment:
We would like to thank all the reviewers for their insightful comments and for helping us improve our paper. Your feedback has been instrumental in refining the presentation, bolstering the experimental analysis, and providing a clearer explanation of our methodology. Below, we highlight the major revisions we’ve made in response to your feedback:

1. **Improved Clarity and Method Presentation**:
   - We have added detailed explanations of our methodology in **Appendix C**, including pseudocode and descriptions of how the core components—Scattering, Foresting, and Scouting—work together. This addresses concerns raised by reviewers (e.g., **hhUS** and **4VU2**) regarding the need for a clearer overall workflow and additional details on implementation.
   - A preliminary section on Monte Carlo Tree Search (MCTS) has been added in **Appendix C.1**, as suggested by **4VU2**, to help readers unfamiliar with MCTS understand its role in our framework.
   - A space-time complexity analysis of our algorithm has been added to **Appendix C.5**, as suggested by **4VU2**.

2. **Experimental Settings**:
   - As per **zwDf**'s feedback, we clarified our experimental setup in **Appendix B**, explaining the rationale for using self-generated test cases and how these align with real-world scenarios where ground-truth tests may not be accessible.
   - We also conducted experiments with ground-truth validation tests, as shown in **Table 8** and detailed in **Appendix I**. This provides a direct comparison of performance with and without self-generated test cases.

3. **Additional Baselines**:
   - In response to **zwDf**'s and **Jy4v**'s suggestions, we compared our method against additional baselines, including **FunSearch**, **REx**, and other state-of-the-art methods like **Self-repair** and **LDB**. These results are summarized in **Tables 5, 6, and 9**. We find that SFS consistently outperforms these baselines across multiple metrics, further demonstrating the robustness of our approach.

4. **Ablation Studies**:
   - We conducted extensive ablation studies to evaluate the contributions of our method's key components, including Scattering, Foresting, and Scouting.(e.g., **Table 7** and **Appendix H**). These studies show that each component contributes significantly to performance improvements.
   - Additionally, following **Jy4v**'s suggestion, we performed new ablations to compare **PUCT** and **UCT** tree-expansion policies, as detailed in **Appendix M**, highlighting why UCT performs better in our specific setting.
   - Per reviewer **DZCq**'s suggestion, we have included a comparison against open-source models such as LLama-3.1


5. **Scaling Experiments**:
   - We included a scaling chart (**Figure 12, right**) to analyze how our method performs under different token budgets, addressing **DZCq**'s request for a cost analysis of tree-search-based inference. These results demonstrate that SFS scales more effectively than baselines given the same token budget.

6. **Visualization of Local Optima Escape**:
   - To respond to **hhUS**'s request for a clearer demonstration of how our method avoids local optima, we added a new illustration (**Figure 19**) and theoretical insights in **Appendix L**. This visualization shows how text-based improvement directions enable transitions between clusters in the solution space, facilitating the escape from local optima.

7. **Improved Presentation**:
   - We have addressed **4VU2**'s comments on notation inconsistencies and improved the clarity of equations, including fixing typos in Eq. (1) and standardizing subscripts throughout the text.
   - Figures have been updated to PDF format for better readability, as suggested by **4VU2**.

8. **Tradeoff Discussion**:
   - Inspired by **hhUS**'s insightful comments, we added a discussion in the **Related Works** section and **Appendix F** on the tradeoff between training stronger models and optimizing inference-time performance. This contextualizes our work and highlights its complementary role to model training.

We believe these revisions comprehensively address the reviewers’ feedback and significantly improve the quality of the paper. Thank you again for your invaluable suggestions and for helping us make this work stronger and more impactful.
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.