Code Repair with LLMs gives an Exploration-Exploitation Tradeoff
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914997087502336 |
|---|---|
| author | Tang, Hao Hu, Keya Zhou, Jin Peng Zhong, Sicheng Zheng, Wei-Long Si, Xujie Ellis, Kevin |
| author_facet | Tang, Hao Hu, Keya Zhou, Jin Peng Zhong, Sicheng Zheng, Wei-Long Si, Xujie Ellis, Kevin |
| contents | Iteratively improving and repairing source code with large language models (LLMs), known as refinement, has emerged as a popular way of generating programs that would be too complex to construct in one shot. Given a bank of test cases, together with a candidate program, an LLM can improve that program by being prompted with failed test cases. But it remains an open question how to best iteratively refine code, with prior work employing simple greedy or breadth-first strategies. We show here that refinement exposes an explore-exploit tradeoff: exploit by refining the program that passes the most test cases, or explore by refining a lesser considered program. We frame this as an arm-acquiring bandit problem, which we solve with Thompson Sampling. The resulting LLM-based program synthesis algorithm is broadly applicable: Across loop invariant synthesis, visual reasoning puzzles, and competition programming problems, we find that our new method can solve more problems using fewer language model calls. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_17503 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Code Repair with LLMs gives an Exploration-Exploitation Tradeoff Tang, Hao Hu, Keya Zhou, Jin Peng Zhong, Sicheng Zheng, Wei-Long Si, Xujie Ellis, Kevin Software Engineering Artificial Intelligence Computation and Language Programming Languages Iteratively improving and repairing source code with large language models (LLMs), known as refinement, has emerged as a popular way of generating programs that would be too complex to construct in one shot. Given a bank of test cases, together with a candidate program, an LLM can improve that program by being prompted with failed test cases. But it remains an open question how to best iteratively refine code, with prior work employing simple greedy or breadth-first strategies. We show here that refinement exposes an explore-exploit tradeoff: exploit by refining the program that passes the most test cases, or explore by refining a lesser considered program. We frame this as an arm-acquiring bandit problem, which we solve with Thompson Sampling. The resulting LLM-based program synthesis algorithm is broadly applicable: Across loop invariant synthesis, visual reasoning puzzles, and competition programming problems, we find that our new method can solve more problems using fewer language model calls. |
| title | Code Repair with LLMs gives an Exploration-Exploitation Tradeoff |
| topic | Software Engineering Artificial Intelligence Computation and Language Programming Languages |
| url | https://arxiv.org/abs/2405.17503 |