AI
Search algorithm boosts LLM patch generation, cuts repair costs in half
A new framework called PSearch uses structured search to improve how AI models fix code bugs, achieving better results while dramatically lowering computational expenses.
Researchers have proposed a new approach to automated program repair that makes large language models (LLMs) significantly more efficient at fixing code bugs. Unlike current methods that generate patches through trial-and-error sampling, the new framework treats repair as a guided exploration problem.
The Problem with Current Methods#
Today's LLM-based approaches to automated program repair (APR) generate candidate patches by repeatedly sampling from the model without a coherent plan. This unstructured exploration wastes computational resources on unpromising directions and makes it hard to know which search paths deserve more attention. The result: higher costs and lower success rates than theoretically possible.
How PSearch Works#
The new framework, called PSearch, maintains a structured search state as it evaluates intermediate patches. Rather than treating each patch generation as an isolated attempt, the system continuously assesses which repair directions show the most promise and focuses effort on refining those paths. This allows it to abandon weak approaches early and zero in on correct solutions through long-horizon search strategies.
The implementation uses Monte Carlo Tree Search as its core algorithm, though the architecture can accommodate other search methods. This design ensures that the LLM explores the repair space more deliberately, allocating compute where it's most likely to succeed.
Measured Results#
Testing on five standard benchmarks showed clear improvements:
- Defects4J: Fixed 201 of 835 bugs, outperforming 12 competing baselines
- VUL4J: Resolved 27 of 79 vulnerabilities
- SWE-Bench-Lite: Fixed 164 of 300 issues
Beyond raw repair counts, the efficiency gains are striking. With a batch size of 16 patches, PSearch cut API and computational costs to roughly half those of strong baseline methods while maintaining superior repair effectiveness—a major advantage for organizations running APR systems at scale.
Why It Matters#
As LLMs become central to software maintenance pipelines, improving their patch-generation efficiency directly impacts development velocity and operational budgets. By treating repair as a structured search problem rather than brute-force sampling, this work demonstrates how algorithmic thinking can amplify LLM capabilities.
