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 proposeSCATTERED 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 experimentsonHumanEval, MBPP, APPS, CodeContests,andLeetcodereveal significantperformance gains. For instance, our method achieves apass@1 rate of 67.1% onHumanEval+and87.2% on HumanEval with GPT-3.5, marking improvements of8.6%and4.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, includingtree search, line search,andrepeatedsampling (Best of N).