APRMCTS: Improving LLM-based Automated Program Repair with Iterative Tree Search

• URL: http://arxiv.org/abs/2507.01827v1
• Date: Wed, 02 Jul 2025 15:44:12 GMT
• Title: APRMCTS: Improving LLM-based Automated Program Repair with Iterative Tree Search
• Authors: Haichuan Hu, Congqing He, Hao Zhang, Xiaochen Xie, Quanjun Zhang,
• Abstract summary: APRMCTS incorporates Monte Carlo Tree Search (MCTS) into patch searching by performing a global evaluation of the explored patches and selecting the most promising one for subsequent refinement and generation.<n>Our experiments on 835 bugs from Defects4J demonstrate that, when integrated with GPT-3.5, APRMCTS can fix a total of 201 bugs, which outperforms all state-of-the-art baselines.
• Score: 6.314858275160081
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Automated Program Repair (APR) attempts to fix software bugs without human intervention, which plays a crucial role in software development and maintenance. Recently, with the advances in Large Language Models (LLMs), a rapidly increasing number of APR techniques have been proposed with remarkable performance. However, existing LLM-based APR techniques typically adopt trial-and-error strategies, which suffer from two major drawbacks: (1) inherently limited patch effectiveness due to local exploration, and (2) low search efficiency due to redundant exploration. In this paper, we propose APRMCTS, which uses iterative tree search to improve LLM-based APR. APRMCTS incorporates Monte Carlo Tree Search (MCTS) into patch searching by performing a global evaluation of the explored patches and selecting the most promising one for subsequent refinement and generation. APRMCTS effectively resolves the problems of falling into local optima and thus helps improve the efficiency of patch searching. Our experiments on 835 bugs from Defects4J demonstrate that, when integrated with GPT-3.5, APRMCTS can fix a total of 201 bugs, which outperforms all state-of-the-art baselines. Besides, APRMCTS helps GPT-4o-mini, GPT-3.5, Yi-Coder-9B, and Qwen2.5-Coder-7B to fix 30, 27, 37, and 28 more bugs, respectively. More importantly, APRMCTS boasts a significant performance advantage while employing small patch size (16 and 32), notably fewer than the 500 and 10,000 patches adopted in previous studies. In terms of cost, compared to existing state-of-the-art LLM-based APR methods, APRMCTS has time and monetary costs of less than 20% and 50%, respectively. Our extensive study demonstrates that APRMCTS exhibits good effectiveness and efficiency, with particular advantages in addressing complex bugs.

Related papers

• From Empirical Evaluation to Context-Aware Enhancement: Repairing Regression Errors with LLMs [1.078085076551721]
  We conduct an empirical study of APR techniques on Java regression bugs.<n>RegMiner4APR is a benchmark of Java regression bugs collected from 32 widely used real-world Java GitHub repositories.<n>Our results show that classical APR tools fail to repair any bugs, while LLM-based APR approaches exhibit promising potential.
  arXiv  Detail & Related papers  (2025-06-16T07:49:18Z)
• Fixing 7,400 Bugs for 1$: Cheap Crash-Site Program Repair [26.981770213053004]
  We propose crash-site repair to simplify the repair task while still mitigating the risk of exploitation.<n>We introduce a template-guided patch generation approach that significantly reduces the token cost of Large Language Models (LLMs)<n>Our results show that, when combined with the top-performing agent CodeRover-S, WILLIAMT reduces token cost by 45.9% and increases the bug-fixing rate to 73.5% (+29.6%) on ARVO.
  arXiv  Detail & Related papers  (2025-05-19T13:32:51Z)
• The Art of Repair: Optimizing Iterative Program Repair with Instruction-Tuned Models [48.073219761367184]
  We investigate an APR pipeline that balances the generation of multiple outputs and multiple rounds of iteration.<n>We fine-tune each model on an APR dataset with three sizes (1K, 30K, 65K) and two techniques (Full Fine-Tuning and LoRA)<n>Our results show that by using only a fraction (1%) of the fine-tuning dataset, we can achieve improvements of up to 78% in the number of plausible patches generated.
  arXiv  Detail & Related papers  (2025-05-05T18:06:51Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Tree Search for Language Model Agents [69.43007235771383]
  We propose an inference-time search algorithm for LM agents to perform exploration and multi-step planning in interactive web environments. Our approach is a form of best-first tree search that operates within the actual environment space. It is the first tree search algorithm for LM agents that shows effectiveness on realistic web tasks.
  arXiv  Detail & Related papers  (2024-07-01T17:07:55Z)
• Hybrid Automated Program Repair by Combining Large Language Models and Program Analysis [12.7034916462208]
  Automated Program Repair (APR) has garnered significant attention due to its potential to streamline the bug repair process for human developers. This paper introduces an innovative APR approach called GIANTREPAIR. Based on this insight, GIANTREPAIR first constructs patch skeletons from LLM-generated patches to confine the patch space, and then generates high-quality patches tailored to specific programs.
  arXiv  Detail & Related papers  (2024-06-03T05:05:12Z)
• Practical Program Repair via Preference-based Ensemble Strategy [28.176710503313895]
  We propose a Preference-based Ensemble Program Repair framework (P-EPR) to rank APR tools for repairing different bugs. P-EPR is the first non-learning-based APR ensemble method that is novel in its exploitation of repair patterns. Experimental results show that P-EPR outperforms existing strategies significantly both in flexibility and effectiveness.
  arXiv  Detail & Related papers  (2023-09-15T07:23:04Z)
• RAP-Gen: Retrieval-Augmented Patch Generation with CodeT5 for Automatic Program Repair [75.40584530380589]
  We propose a novel Retrieval-Augmented Patch Generation framework (RAP-Gen) RAP-Gen explicitly leveraging relevant fix patterns retrieved from a list of previous bug-fix pairs. We evaluate RAP-Gen on three benchmarks in two programming languages, including the TFix benchmark in JavaScript, and Code Refinement and Defects4J benchmarks in Java.
  arXiv  Detail & Related papers  (2023-09-12T08:52:56Z)
• Optimizing Two-way Partial AUC with an End-to-end Framework [154.47590401735323]
  Area Under the ROC Curve (AUC) is a crucial metric for machine learning. Recent work shows that the TPAUC is essentially inconsistent with the existing Partial AUC metrics. We present the first trial in this paper to optimize this new metric.
  arXiv  Detail & Related papers  (2022-06-23T12:21:30Z)
• The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [67.47961797770249]
  Multi-Agent PPO (MAPPO) is a multi-agent PPO variant which adopts a centralized value function. We show that MAPPO achieves performance comparable to the state-of-the-art in three popular multi-agent testbeds.
  arXiv  Detail & Related papers  (2021-03-02T18:59:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.