# Code Repair with LLMs gives an Exploration-Exploitation Tradeoff

arXiv: https://arxiv.org/abs/2405.17503 · HTML: https://mlsanity.com/paper/2405.17503/

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 26 May 2024.

## Builds on (most cited first, 22 of 22)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01780/) (2022)
- [Generating Sequences by Learning to Self-Correct](https://mlsanity.com/paper/2211.00053/) (2022)
- [Is Self-Repair a Silver Bullet for Code Generation?](https://mlsanity.com/paper/2306.09896/) (2023)
- [Practical Program Repair in the Era of Large Pre-trained Language Models](https://mlsanity.com/paper/2210.14179/) (2022)
- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement](https://mlsanity.com/paper/2310.08559/) (2023)
- [Automated Repair of Programs from Large Language Models](https://mlsanity.com/paper/2205.10583/) (2022)
- [Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions](https://mlsanity.com/paper/2212.10561/) (2022)
- [CYCLE: Learning to Self-Refine the Code Generation](https://mlsanity.com/paper/2403.18746/) (2024)
- [WhiteFox: White-Box Compiler Fuzzing Empowered by Large Language Models](https://mlsanity.com/paper/2310.15991/) (2023)
- [Finding Inductive Loop Invariants using Large Language Models](https://mlsanity.com/paper/2311.07948/) (2023)
- [Fast and flexible: Human program induction in abstract reasoning tasks](https://mlsanity.com/paper/2103.05823/) (2021)
- [Learning Nonlinear Loop Invariants with Gated Continuous Logic Networks (Extended Version)](https://mlsanity.com/paper/2003.07959/) (2020)
- [Global Guidance for Local Generalization in Model Checking](https://mlsanity.com/paper/2005.13301/) (2020)

## Built on by (most cited first, 30 of 51)

- [AutoHarness: improving LLM agents by automatically synthesizing a code harness](https://mlsanity.com/paper/2603.03329/) (2026)
- [ReasonFlux: Hierarchical LLM Reasoning via Scaling Thought Templates](https://mlsanity.com/paper/2502.06772/) (2025)
- [Combining Induction and Transduction for Abstract Reasoning](https://mlsanity.com/paper/2411.02272/) (2024)
- [Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search](https://mlsanity.com/paper/2503.04412/) (2025)
- [Self-Improving Language Models for Evolutionary Program Synthesis: A Case Study on ARC-AGI](https://mlsanity.com/paper/2507.14172/) (2025)
- [CodeJudgeBench: Benchmarking LLM-as-a-Judge for Coding Tasks](https://mlsanity.com/paper/2507.10535/) (2025)
- [What Makes Large Language Models Reason in (Multi-Turn) Code Generation?](https://mlsanity.com/paper/2410.08105/) (2024)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [PoE-World: Compositional World Modeling with Products of Programmatic Experts](https://mlsanity.com/paper/2505.10819/) (2025)
- [SELA: Tree-Search Enhanced LLM Agents for Automated Machine Learning](https://mlsanity.com/paper/2410.17238/) (2024)
- [Reasoning Through Execution: Unifying Process and Outcome Rewards for Code Generation](https://mlsanity.com/paper/2412.15118/) (2024)
- [Calibrate-Then-Act: Cost-Aware Exploration in LLM Agents](https://mlsanity.com/paper/2602.16699/) (2026)
- [LoopViT: Scaling Visual ARC with Looped Transformers](https://mlsanity.com/paper/2602.02156/) (2026)
- [M2F: Automated Formalization of Mathematical Literature at Scale](https://mlsanity.com/paper/2602.17016/) (2026)
- [LLM-Guided Probabilistic Program Induction for POMDP Model Estimation](https://mlsanity.com/paper/2505.02216/) (2025)
- [Scattered Forest Search: Smarter Code Space Exploration with LLMs](https://mlsanity.com/paper/2411.05010/) (2024)
- [Token Hidden Reward: Steering Exploration-Exploitation in Group Relative Deep Reinforcement Learning](https://mlsanity.com/paper/2510.03669/) (2025)
- [ARC-GEN: A Mimetic Procedural Benchmark Generator for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2511.00162/) (2025)
- [Improved Generalized Planning with LLMs through Strategy Refinement and Reflection](https://mlsanity.com/paper/2508.13876/) (2025)
- [InfCode: Adversarial Iterative Refinement of Tests and Patches for Reliable Software Issue Resolution](https://mlsanity.com/paper/2511.16004/) (2025)
- [Relational decomposition for program synthesis](https://mlsanity.com/paper/2408.12212/) (2024)
- [Generating Diverse Hypotheses for Inductive Reasoning](https://mlsanity.com/paper/2412.13422/) (2024)
- [Multi-Agent Code-Orchestrated Generation for Reliable Infrastructure-as-Code](https://mlsanity.com/paper/2510.03902/) (2025)
- [How Many Tries Does It Take? Iterative Self-Repair in LLM Code Generation Across Model Scales and Benchmarks](https://mlsanity.com/paper/2604.10508/) (2026)
- [Distilling Game Code World Model Generation into Lightweight Large Language Models](https://mlsanity.com/paper/2605.24375/) (2026)
- [Program Synthesis via Test-Time Transduction](https://mlsanity.com/paper/2509.17393/) (2025)
- [Automating Computational Reproducibility in Social Science: Comparing Prompt-Based and Agent-Based Approaches](https://mlsanity.com/paper/2602.08561/) (2026)
- [Compute Allocation for Self-Evolving LLMs: From Depth-Breadth to Multi-Armed Bandits](https://mlsanity.com/paper/2605.29268/) (2026)
- [Twin: Playing an Unknown Game with a Test-Time Digital Twin](https://mlsanity.com/paper/2608.14490/) (2026)
- [Cog-Rethinker: Hierarchical Metacognitive Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2510.15979/) (2025)

## Abstract (arXiv)

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.