Research map / Large language models / Agents, code and math
Code Repair with LLMs gives an Exploration-Exploitation Tradeoff
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes REx, a Thompson-sampling bandit policy for LLM code refinement that trades off exploiting high-pass-rate programs against exploring less-refined ones, reducing LLM calls on loop invariant, ARC, and APPS tasks.
Problem
Iterative LLM code refinement needs a search policy over the infinite tree of refined programs; prior work uses greedy or breadth-first expansion, which yields marginal gains over i.i.d. sampling.
Approach
Frame refinement as an arm-acquiring bandit where each program is an arm, and apply Thompson Sampling with Beta priors biased by the pass-rate heuristic and penalized by the number of prior refinements (REx), avoiding MCTS rollouts and tree traversal.
Key results
- On loop invariant synthesis, REx solves 73.7% of tasks versus 60.5% for the specialized prior solver, with no special tuning.
- REx uses roughly 2x fewer LLM calls than the best baseline on APPS-Competition and 2-5x fewer on loop invariants, and 1.1-1.6x fewer on ARC.
- REx is more robust to hyperparameter choice than Greedy, BFS, and Fixed-Width, with C=20 performing well across difficult benchmarks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use REx instead of G-CLN | NLA loop invariant synthesis · NLA loop invariant benchmark | total correct: 24 -> 28 | Helped |
| Use REx instead of Loopy-GPT4 | NLA loop invariant synthesis · NLA loop invariant benchmark | total correct: 11 -> 28 | Helped |
| Use REx instead of GSpacer | NLA loop invariant synthesis · NLA loop invariant benchmark | total correct: 5 -> 28 | Helped |
| Use REx instead of the specialized solver | Nonlinear loop invariant synthesis · Nonlinear loop invariants | success rate: 60.5% -> 73.7% | Helped |
| Use REx rather than the alternatives | Code refinement across APPS-Competition · APPS-Competition | LLM calls: 2× | Helped |
| Use REx rather than the alternatives | Code refinement for loop invariants · Loop invariants | LLM calls: 2-5× | Helped |
| Use REx rather than the alternatives | Visual reasoning code refinement · ARC | LLM calls: 1.1-1.6× | Helped |
| Use REx rather than the alternatives | Code refinement · APPS-Introductory | LLM calls | No clear effect |
| Use REx instead of Fixed-Width | Code refinement · APPS-Competition and ARC | problems solved | No clear effect |
Surprising findings
- On APPS Introductory there is no speedup from REx, and Greedy is competitive on easier benchmarks.
- Prior refinement policies yield only marginal gains over repeatedly sampling i.i.d. programs from the initial prompt.
Limitations
- Gains in the large-compute limit are modest; final solve counts are only slightly higher than baselines.
- Uses only pass-rate heuristic; richer feedback and contextual bandits are not explored.
- Hardest problems depend mainly on base model improvements rather than search policy.
Experimental setup
Datasets: APPS ARC NLA loop invariant benchmark
Benchmarks: APPS Competition APPS Interview APPS Introductory ARC (40-problem subset) NLA loop invariant benchmark
Metrics: problems solved vs. LLM calls AUC final success rate LLM calls speedup
Baselines: Greedy refinement Breadth-First Search Fixed-Width Hypothesis Search Parsel AlphaCode G-CLN GSpacer Loopy-GPT4
Builds on: Thompson Sampling Monte Carlo Tree Search Hypothesis Search Fixed-Width refinement
Closest papers by meaning
- Let's Revise Step-by-Step: A Unified Local Search Framework for Code Generation with LLMs (NeurIPS 2025 · similarity 0.88)
- Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization (AAAI 2025 · similarity 0.88)
- LeDex: Training LLMs to Better Self-Debug and Explain Code (NeurIPS 2024 · similarity 0.87)
- AuPair: Golden Example Pairs for Code Repair (ICML 2025 · similarity 0.87)
- Property-Guided LLM Program Synthesis for Planning (NeurIPS 2026 · similarity 0.87)
- Rethinking Verification for LLM Code Generation: From Generation to Testing (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.