AprMcts : Improving LLM-based Automated Program Repair with Iterative Tree Search
Haichuan Hu, Congqing He, Hao Zhang, Xiaochen Xie, Quanjun Zhang · 2025
Read AprMcts : Improving LLM-based Automated Program Repair with Iterative Tree Search by Haichuan Hu, Congqing He, Hao Zhang, Xiaochen Xie, Quanjun Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01827.txt.
Introduction
Haichuan Hu and co-authors present in 2025 PSearch, a search based way to make code patches with large language models. The head text gives that name and frame for the work. Most patch tools just sample tries at random, with no plan for which path to fund next.
PSearch keeps a clear state over half built patches and scores each path as it grows. Weak paths are dropped early, while strong paths get more work and polish. Tests span five bug and flaw test sets. The tool fixed two hundred one of eight hundred thirty five bugs in one set, ahead of twelve rival tools.
Catalog record
| CREATOR | Haichuan Hu, Congqing He, Hao Zhang, Xiaochen Xie, Quanjun Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-01827
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
AprMcts : Improving LLM-based Automated Program Repair with Iterative Tree Search Haichuan Hu, Congqing He, Hao Zhang, Xiaochen Xie, Quanjun Zhang 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. I Introduction Automated Program Repair (APR) attempts to fix buggy programs by automatically generating patches. A typical APR process involves two main steps: (1) generating plausible patches that pass all test cases, and (2) verifying the correctness of these patches through manual inspection. Traditional APR techniques can be generally classified into three categories: template-based [ 1 , 2 ] , heuristic-based [ 3 , 4 ] , and constraint-based [ 5 , 6 ] ones. Among them, template-based APR leverages well-designed templates to match buggy code patterns, and is widely regarded as state-of-the-art. Despite its effectiveness, template-based APR is inherently constrained by its dependency on predefined templates, which limits its ability to handle previously unseen software bugs. Over the past few years, researchers have introduced a mass of learning-based approaches [ 7 ] , which utilize deep learning to enhance repair capabilities by extracting bug-fixing patterns from existing code repositories. Compared to traditional APR, learning-based APR demonstrates superior generalization, enabling it to address bugs that are not present in the training data. Recently, with the rapid advancements in Large Language Models (LLMs), numerous LLM-based APR techniques have emerged. Hossain et al. [ 8 ] comprehensively discuss the impact of various prompts and contexts on the effectiveness of LLM-based APR. ChatRepair [ 9 ] uses GPT-3.5 to fix a total of 162 bugs on Defects4J [ 10 ] , marking one of the most representative LLM-based methods. Other studies [ 11 , 12 ] further demonstrate the effectiveness of LLMs in different repair scenarios, such as programming problems. However, existing state-of-the-art LLM-based APR techniques typically follow a serial, single-path trial-and-error strategy, where a candidate patch is generated, validated against test cases, and then refined based on the test outcomes. While straightforward, this strategy may suffer from two key limitations: local optima in effectiveness and redundant exploration in efficiency. First, it lacks the ability to leverage historical search information, making the repair process prone to getting trapped in local optima. Second, it generates patches in an unstructured and memoryless manner, often resulting in redundant or near-duplicate patches and inefficient use of computational resources. These limitations hinder the model’s capacity to explore promising regions of the search space and adapt its repair strategy based on prior attempts. As a result, current methods often struggle to efficiently discover high-quality patches, especially for complex bugs. To address these issues, we propose AprMcts , which helps improve LLM-based APR by utilizing a multi-round iterative tree search method combined with CoT and self-evaluation to generate patches. Unlike the trial-and-error repair paradigm, we adopt an evaluate-and-improve approach to guide the model toward the correct repair path. Through effective global patch evaluation, AprMcts can quickly discover mistakes and backtrack from incorrect repair paths, step by step approaching the correct patch by restarting from the most promising candidate. For AprMcts , each iteration of patch search can be divided into four stages: Patch Selection , Patch Generation , Patch Evaluation , Patch Tree Updating . In the patch selection stage, AprMcts first selects an explored patch from the patch tree according to the UCT (Upper Confidence Bounds Applied to Trees) value. Then in the patch generation stage, AprMcts inspires LLMs to perform repairs on selected patch through CoT, and further conducts self-reflection on the generated patches. In the patch evaluation stage, the generated patches are validated for correctness on test cases. For those patches that fail the tests, AprMcts assesses their quality and then add them to the patch tree. Specifically, we adopt LLM-as-Judge and Test-as-Judge strategies adaptively for evaluation based on whether the test cases are sufficient. In the patch tree updating stage, back propagation is performed from the selected patch upwards to the root node of the patch tree. After a certain number of iterations (16 and 32 in our work), AprMcts outputs all the plausible patches found for patch validation. Compared with prior LLM-based APR techniques, AprMcts has the following advantages. (1) Global optimum. During each iteration of repair, AprMcts selects the highest-scoring patch from the patch search space as the starting point for the next search. Compared with approaches that focus solely on a single patch, AprMcts ensures the global optimum of the search algorithm. In terms of results, AprMcts can fix 201 out of 835 bugs on Defects4J, surpassing all 9 state-of-the-art baselines. (2) Flexibility and generality. AprMcts is flexible as it works seamlessly with any LLMs. AprMcts is also generalizable to different search algorithms. Although we adopt the representative Monte Carlo Tree Search (MCTS) to demonstrate the effectiveness of AprMcts , it can be replaced by any other search algorithm (e.g., genetic algorithms). (3) High search efficiency, larger search space with fewer search iterations. Compared with serial single-path methods, AprMcts employs a multi-path search strategy to generate more diverse patches. By pruning low-quality search paths, AprMcts avoids straying too far down incorrect trajectories, thereby reducing the number of search iterations. For example, AprMcts adopts a smaller patch size (16 and 32) than that used in previous studies (10000 [ 13 ] , 500 [ 14 ] ). This paper makes the following contributions: • We propose AprMcts , which utilizes tree search to optimize the LLM-based APR process, representing a new technological endeavor in the field of APR. AprMcts offers multiple advantages, such as flexible architecture, preferable effectiveness, and efficiency. • We evaluate AprMcts against 9 state-of-the-art baselines (including learning-based, template-based and LLM-based APR techniques) and 13 representative LLMs. Experimental results show that AprMcts outperforms existing baselines, fixing 108 and 93 bugs on Defects4J-v1.2 and Defects4J-v2,