Scattered Forest Search: Smarter Code Space Exploration with LLMs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910843005829120 |
|---|---|
| author | Light, Jonathan Wu, Yue Sun, Yiyou Yu, Wenchao liu, Yanchi Zhao, Xujiang Hu, Ziniu Chen, Haifeng Cheng, Wei |
| author_facet | Light, Jonathan Wu, Yue Sun, Yiyou Yu, Wenchao liu, Yanchi Zhao, Xujiang Hu, Ziniu Chen, Haifeng Cheng, Wei |
| contents | We frame code generation as a black-box optimization problem within the code space and demonstrate how optimization-inspired techniques can enhance inference scaling. Based on this perspective, we propose SCATTERED FOREST SEARCH (SFS), a novel approach that improves solution diversity and better exploits feedback during evolutionary search. Our theoretical analysis illustrates how these methods help avoid local optima during optimization, leading to more efficient exploration. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_05010 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Scattered Forest Search: Smarter Code Space Exploration with LLMs Light, Jonathan Wu, Yue Sun, Yiyou Yu, Wenchao liu, Yanchi Zhao, Xujiang Hu, Ziniu Chen, Haifeng Cheng, Wei Software Engineering Artificial Intelligence Machine Learning I.2.2; I.2.6; I.2.8; D.2.3; D.2.5; D.1.2; F.2.2; G.1.6 We frame code generation as a black-box optimization problem within the code space and demonstrate how optimization-inspired techniques can enhance inference scaling. Based on this perspective, we propose SCATTERED FOREST SEARCH (SFS), a novel approach that improves solution diversity and better exploits feedback during evolutionary search. Our theoretical analysis illustrates how these methods help avoid local optima during optimization, leading to more efficient exploration. 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. |
| title | Scattered Forest Search: Smarter Code Space Exploration with LLMs |
| topic | Software Engineering Artificial Intelligence Machine Learning I.2.2; I.2.6; I.2.8; D.2.3; D.2.5; D.1.2; F.2.2; G.1.6 |
| url | https://arxiv.org/abs/2411.05010 |