SFS: Smarter Code Space Search improves LLM Inference Scaling

摘要

We frame code generation as a black-box optimization problem within the codespace and demonstrate how optimization-inspired techniques can enhance inferencescaling over text. Based on this perspective, we propose **SCATTERED FORESTSEARCH (SFS)**, a novel approach that improves solution diversity during evolutionary search,thereby avoiding local optima. Our theoretical analysis illustrates how thesemethods improve exploration and enhance efficiency. Extensive experimentson *HumanEval, MBPP, APPS, CodeContests,* and *Leetcode* reveal significantperformance gains. For instance, our method achieves a **pass@1 rate of 67.1% onHumanEval+** 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 neededto find the correct solution. Furthermore, our approach scales more efficientlythan existing search techniques, including **tree search, line search,** and **repeatedsampling (Best of N)**.