SFS: Smarter Code Space Search improves LLM Inference Scaling
Jonathan Light Yue Wu Yiyou Sun Wenchao Yu Yanchi Liu Xujiang Zhao Ziniu Hu Haifeng Chen Wei Cheng
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)**.
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
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.