"Scattered Forest Search: Smarter Code Space Exploration with LLMs"

Scattered Forest Search (SFS) makes code generation smarter by exploring multiple solution paths simultaneously

It turns code generation into a treasure hunt with multiple search parties.

https://arxiv.org/abs/2411.05010

🎯 Original Problem:

Code generation using LLMs often gets stuck in local optima due to similar solutions being generated repeatedly, leading to inefficient exploration of the solution space.

-----

🔍 Solution in this Paper:

→ Introduces Scattered Forest Search (SFS) which frames code generation as a black-box optimization problem

→ Uses Scattering to generate diverse solution directions by dynamically varying input prompts

→ Implements Foresting to create multiple seed solutions and perform tree search from each one

→ Employs Scouting to share feedback across search branches, enhancing exploration efficiency

→ Utilizes Monte Carlo Tree Search (MCTS) with UCT formula to balance exploration and exploitation

-----

💡 Key Insights:

→ Traditional methods like tree search and line search produce highly similar solutions

→ Diverse initialization seeds significantly improve exploration of solution space

→ Knowledge sharing across search branches enhances solution quality

→ Higher conductance in Markov chain theory explains why SFS escapes local optima better

-----

📊 Results:

→ Achieves 67.1% pass@1 on HumanEval+ (8.6% improvement over SOTA)

→ 87.2% pass@1 on HumanEval (4.3% improvement over SOTA)

→ Halves iterations needed to find correct solutions

→ Shows better scaling efficiency than tree search, line search and repeated sampling