PSearch: Search-based Patch Generation in the Era of LLM-based Automated Program Repair
For researchers and practitioners in automated program repair, PSearch provides a more structured and cost-effective approach to patch generation, achieving state-of-the-art results on multiple benchmarks.
PSearch introduces a search-based patch generation framework for LLM-based automated program repair that uses iterative evaluation and refinement with Monte Carlo Tree Search. It correctly repairs 201/835 bugs in Defects4J, outperforming 12 baselines, and reduces monetary cost to ~50% of strong baselines with a patch size of 16.
Large Language Models (LLMs) have substantially advanced Automated Program Repair (APR), yet most existing LLM-based APR methods still rely on trial-and-error to generate patches. Such a strategy explores candidate patches in a weakly structured manner, making it difficult to assess the future potential of search directions and allocate search budget effectively. To address this limitation, we propose Psearch, a search-based patch generation framework for LLM-based APR centered on iterative patch evaluation and refinement. Instead of treating patch generation as repeated independent sampling, Psearch maintains a structured search state over intermediate patches, continuously evaluates the promise of explored search paths, and prioritizes the most promising ones for further refinement. This design enables Psearch to abandon weak directions early and progressively approach correct fixes through long-horizon search. Importantly, Psearch can be integrated with different search algorithms, while our current implementation adopts Monte Carlo Tree Search as one effective instantiation. We evaluate Psearch on five widely used bug and vulnerability benchmarks. Experimental results show that Psearch correctly repairs 201 out of 835 bugs in Defects4J, outperforming all 12 state-of-the-art baselines. Psearch also fixes 27 of 79 vulnerabilities in VUL4J and resolves 164 of 300 issues in SWE-Bench-Lite. Moreover, with a patch size of 16, Psearch reduces monetary cost to roughly 50% of strong baselines while maintaining superior repair effectiveness. These results highlight the effectiveness of Psearch for improving LLM-based APR. The code and results can be found at https://github.com/Tomsawyerhu/Psearch