CoChat
Sign Up
PreprintCited by 14Software Engineering ResearchSoftware Testing and Debugging TechniquesEvolutionary Algorithms and Applications

Code Repair with LLMs gives an Exploration-Exploitation Tradeoff

Open access
Tang, Hao, Hu, Keya, Zhou, Jin Peng, Zhong, Sicheng, Zheng, Wei-Long, Si, Xujie, Ellis, Kevin·2024·arXiv
DOI 10.48550/arxiv.2405.17503arXiv 2405.17503
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2405.17503

Cites

0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Tang et al. (2024) points out that the process of iteratively refining code exposes an explore-exploit tradeoff, which can be framed as a multi-armed bandit problem and solved using Thompson Sampling.

    “Tang et al. (2024) points out that the process exposes an explore-exploit tradeoff, which can be framed as a multi-armed bandit problem, and solved using Thompson Sampling.”

    From When LLMs meet cybersecurity: a systematic literature review (2025) · cites this paper as Tang et al. (2024)

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 35

  1. Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint arXiv:2304.05128, 2023. · arXiv
  2. Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. arXiv preprint arXiv:2211.00053, 2022. · arXiv
  3. Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion: an autonomous agent with dynamic memory and self-reflection. arXiv preprint arXiv:2303.11366, 2023. · arXiv
  4. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024.
  5. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/ forum?id=WaGvb7OzySA.
  6. Peter Whittle. Arm-acquiring bandits. The Annals of Probability, 9(2):284-292, 1981.
  7. Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends® in Machine Learning, 11(1):1-96, 2018.
  8. Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Ad- vances in Neural Information Processing Systems, volume 24.
  9. Curran Associates, Inc., 2011. URL https://proceedings.neurips.cc/paper_files/paper/2011/file/ e53a0a2978c28872a4505bdb51db06dc-Paper.pdf.
  10. Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer-Verlag New York, Inc., 2006.
  11. Hao Tang, Darren Key, and Kevin Ellis. Worldcoder, a model-based llm agent: Building world models by writing code and interacting with the environment. NeurIPS, 2024.
  12. Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al. Measuring coding challenge competence with apps. arXiv preprint arXiv:2105.09938, 2021. · arXiv
  13. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021. · arXiv
  14. Aysja Johnson, Wai Keen Vong, Brenden M Lake, and Todd M Gureckis. Fast and flexible: Human program induction in abstract reasoning tasks. arXiv preprint arXiv:2103.05823, 2021. · arXiv
  15. Enric Rodríguez-Carbonell and Deepak Kapur. Generating all polynomial invariants in simple loops. J. Symb. Comput., 42(4):443-476, 2007. doi: 10.1016/J.JSC.2007.01.002. URL https://doi.org/10.1016/j.jsc.2007.01.002. · DOI
  16. Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient smt solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 337-340. Springer, 2008.
  17. Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah D. Goodman. Hypothesis search: Inductive reasoning with language models. ICLR, 2024.
  18. Linlu Qiu, Liwei Jiang, Ximing Lu, Melanie Sclar, Valentina Pyatkin, Chandra Bhagavatula, Bailin Wang, Yoon Kim, Yejin Choi, Nouha Dziri, and Xiang Ren. Phenomenal yet puzzling: Testing inductive reasoning capabilities of language models with hypothesis refinement. ICLR, 2024.
  19. Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D Goodman, and Nick Haber. Parsel: Algorithmic reasoning with language models by composing decompositions. NeurIPS 2023, 2023.
  20. Hari Govind Vediramana Krishnan, YuTing Chen, Sharon Shoham, and Arie Gurfinkel. Global guidance for local generalization in model checking. In Shuvendu K. Lahiri and Chao Wang, editors, Computer Aided Verification, pages 101-125, Cham, 2020. Springer International Publishing. ISBN 978-3-030-53291-8.
  21. Yangruibo Ding, Marcus J Min, Gail Kaiser, and Baishakhi Ray. Cycle: Learning to self-refine the code generation. Proceedings of the ACM on Programming Languages, 8(OOPSLA1): 392-418, 2024.
  22. Westley Weimer, ThanhVu Nguyen, Claire Le Goues, and Stephanie Forrest. Automatically finding patches using genetic programming. In 2009 IEEE 31st International Conference on Software Engineering, pages 364-374. IEEE, 2009.
  23. Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. Semfix: Program repair via semantic analysis. In 2013 35th International Conference on Software Engineering (ICSE), pages 772-781. IEEE, 2013.
  24. Claire Le Goues, Michael Pradel, and Abhik Roychoudhury. Automated program repair. Communications of the ACM, 62(12):56-65, 2019.
  25. Rishabh Singh, Sumit Gulwani, and Armando Solar-Lezama. Automated feedback genera- tion for introductory programming assignments. In Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation, pages 15-26, 2013.
  26. Zhiyu Fan, Xiang Gao, Martin Mirchev, Abhik Roychoudhury, and Shin Hwei Tan. Auto- mated repair of programs from large language models. In 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE), pages 1469-1481. IEEE, 2023.
  27. Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pages 72-83. Springer, 2006.
  28. Timothy Yee, Viliam Lisỳ, Michael H Bowling, and S Kambhampati. Monte carlo tree search in continuous action spaces with execution uncertainty. In IJCAI, pages 690-697, 2016.
  29. Guillaume M Jb Chaslot, Mark HM Winands, H Jaap van den Herik, Jos WHM Uiterwijk, and Bruno Bouzy. Progressive strategies for monte-carlo tree search. New Mathematics and Natural Computation, 4(03):343-357, 2008.
  30. David Silver and Joel Veness. Monte-carlo planning in large pomdps. Advances in neural information processing systems, 23, 2010.
  31. Dezhi Ran, Hao Wang, Wenyu Wang, and Tao Xie. Badge: prioritizing ui events with hierar- chical multi-armed bandits for automated ui testing. In 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE), pages 894-905. IEEE, 2023.
  32. Chenyuan Yang, Yinlin Deng, Runyu Lu, Jiayi Yao, Jiawei Liu, Reyhaneh Jabbarvand, and Lingming Zhang. Whitefox: White-box compiler fuzzing empowered by large language models. arXiv preprint arXiv:2310.15991, 2023. · arXiv
  33. Xujie Si, Hanjun Dai, Mukund Raghothaman, Mayur Naik, and Le Song. Learning loop invariants for program verification. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural In- formation Processing Systems, volume 31.
  34. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper_files/paper/2018/file/ 65b1e92c585fd4c2159d5f33b5030ff2-Paper.pdf.
  35. E. Rodríguez-Carbonell and D. Kapur. Generating all polynomial invariants in simple loops. Journal of Symbolic Computation, 42(4):443-476, 2007. ISSN 0747-7171. doi: https://doi. org/10.1016/j.jsc.2007.01.002. URL https://www.sciencedirect.com/science/ article/pii/S0747717107000107. 0, 0, 0, 8, 8, 8, 8, 8], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]] Correct Output: [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 8, 8, 8, 8, 8, 0, 0], [0, 0, 8, 0, 0, 0, 0, 8, 0], [0, 0, 0, 8, 0, 0, 0, 0, 8], [0, 0, 0, 0, 8, 0, 0, 0, 8], [0, 0, 0, 0, 8, 8, 8, 8, 8], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]] Output: [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 8, 8, 8, 8, 8, 0, 0], [0, 0, 8, 0, 0, 0, 0, 8, 0], [0, 0, 0, 8, 0, 0, 0, 0, 8], [0, 0, 0, 0, 8, 0, 0, 0, 0], [0, 0, 0, 0, 8, 8, 8, 8, 8], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0 · DOI

Cited by

Sorted by citations

Related

Authors
Tang, H., Hu, K., Zhou, J. P., Zhong, S., Zheng, W.-L., Si, X., & Ellis, K.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2024
Pages
117954-117996
ISSN
1049-5258 (ISSN-L)
DOI
10.48550/arxiv.2405.17503
arXiv
2405.17503
OpenAlex
W4415795471
Cited by
11
References
0
Citations by year
2026: 8 · 2025: 3
FWCI
4.19
Type
conference paper
Language
en
Open access
Licence
Locations
  • neural information processing systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion, cc-by-nc-sa)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (2310350)
  • Cisco Systems
  • Canadian Institute for Advanced Research
  • Natural Sciences and Engineering Research Council of Canada
Topics
  • Physical Sciences › Computer Science › Information Systems › Software Engineering Research
  • Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
Keywords
code repair, large language models, exploration-exploitation balance, program repair

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review