💻 computer science

Beyond Localization: Recoverable Headroom and Residual Frontier in Repository-Level RAG-APR

This paper investigates the recoverable performance gains and remaining limitations of repository-level RAG-APR systems beyond localization by evaluating Oracle Localization, candidate diversity, context injection, and interface design on SWE-bench Lite, revealing that while stronger localization and specific post-localization levers improve repair rates, a significant residual frontier persists due to inherent system and prompt-level constraints.

Original authors: Pengtao Zhao, Boyang Yang, Bach Le, Feng Liu, Haoye Tian

Published 2026-04-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pengtao Zhao, Boyang Yang, Bach Le, Feng Liu, Haoye Tian

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to fix a massive, ancient library (a software repository) where a specific book has a typo that breaks the whole story. You have a team of three very smart, but slightly different, librarians (the AI repair systems: Agentless, KGCompass, and ExpeRepair).

For a long time, everyone thought the only way to fix the library was to get the librarians better at finding the exact page with the typo. This is called "Localization."

This paper asks a new, crucial question: "Okay, let's pretend we magically give the librarians the exact page number where the typo is. Now that they know where to look, what stops them from actually fixing it?"

The authors ran a series of experiments to find out what happens after the location is found. Here is what they discovered, using some simple analogies:

1. The "Magic Map" Experiment (Oracle Localization)

The researchers gave the librarians a "Magic Map" that pointed directly to the typo.

The Result: The librarians got much better at fixing the books, but they still failed more than half the time.
The Analogy: Imagine you are told exactly which brick in a wall is broken. You can now see the problem clearly, but you might still fail to fix it because you don't have the right tools, you don't know the right mortar recipe, or you just can't reach the spot.
Key Finding: Knowing where the problem is helps, but it doesn't solve the whole puzzle. The real struggle happens after you find the spot.

2. The "Lottery Ticket" Experiment (Search Headroom)

The researchers asked: "If we ask the librarians to try 10 different ways to fix the typo (instead of just one), will they get better?"

The Result: Yes, but only a little bit. The first few attempts were the most helpful. By the 5th attempt, they had already found almost all the "good" ideas they could. Trying 10 times instead of 5 didn't help much more.
The Analogy: It's like buying lottery tickets. The first few tickets you buy give you a decent chance of winning. Buying 10 tickets instead of 5 doesn't double your luck; you just run out of "winning" tickets pretty quickly. The librarians ran out of good ideas very fast.

3. The "Extra Clues" Experiment (Added Context)

The researchers tried giving the librarians extra notes from the other librarians. For example, they gave Agentless a note from KGCompass saying, "Hey, I saw a similar problem in a different book."

The Result: This helped! The librarians fixed more books when they had these extra, relevant clues.
The Catch: It wasn't just about having more paper to read. If they gave them extra paper with useless junk on it, the librarians got confused and fixed fewer books.
The Analogy: It's like cooking. If you give a chef the exact recipe (the right clue), they make a great meal. If you give them the recipe plus a 50-page manual on how to grow wheat (too much context), they get overwhelmed. But if you give them a tip from a master chef on how to chop onions (relevant extra context), the meal gets even better.

4. The "Unsolvable Frontier" (The Residual Problem)

Finally, the researchers asked: "If we combine all the librarians' best attempts, the Magic Maps, and the extra clues, how many books are still broken?"

The Result: A surprisingly large number. Even after doing everything right, there was a "Frontier" of problems that no one could fix.
The Analogy: Imagine a group of detectives solving crimes. Even if they have the perfect crime scene photo, the best forensic tools, and all the witness statements, there are still some cases where the culprit is just too clever, or the evidence is too messy.
The Reality: The remaining broken books usually had very specific, tricky errors (like a missing ingredient in a recipe or a confusing instruction). The current AI tools just aren't smart enough to handle those specific, messy details yet.

The Big Takeaway

For a long time, the AI repair community thought: "If we just get better at finding the bug, we will fix everything."

This paper says: "Nope. Finding the bug is only step one. Once we find it, the real hard work begins."

To fix software in the future, we need to stop just focusing on "finding" and start focusing on:

How to use the evidence once we find it.
How to design better tools for the AI to use.
Accepting that some problems are currently too hard for our AI to solve, no matter how much we tweak the search.

In short: We found the needle in the haystack. Now we need to figure out how to actually sew the hole in the haystack.

1. Problem Statement

Repository-level Automated Program Repair (APR) systems, particularly those using Retrieval-Augmented Generation (RAG), have increasingly focused on localization (identifying the correct files and code spans) as the primary driver of success. However, current evaluations often conflate gains from better localization with gains from context construction, patch generation, and validation.

The authors ask a targeted question: Once localization is strengthened (even to an "Oracle" level), what recoverable gains remain? Specifically, they investigate:

How much "headroom" exists within the system's search space after localization is fixed?
Does adding cross-paradigm evidence (e.g., mixing knowledge graphs with memory) help under controlled interfaces?
What is the "residual frontier" of cases that remain unsolved even after optimizing localization, search, and context?

2. Methodology

The study is conducted on the SWE-bench Lite benchmark (300 instances) using three representative RAG-APR paradigms:

Agentless: A phase-structured pipeline using hierarchical localization and compressed repository views.
KGCompass: A structure-aware system using repository knowledge graphs and graph proximity.
ExpeRepair: A memory-augmented system using dual memory for past demonstrations and semantic insights.

The authors designed a controlled intervention protocol involving four main components:

Oracle Localization: Instead of relying on the system's own retrieval, the authors inject ground-truth fault spans (file paths and line ranges derived from the gold patch) into each system's candidate set. Crucially, they preserve each system's unique prompt construction and patch generation logic to isolate the effect of localization from interface design.
Within-Pool Best-of- $K$ : To measure search headroom, they sample $K=10$ independent patch candidates per instance under Oracle Localization. They evaluate $Solved@K$ (if any of the $K$ patches solves the issue) and analyze how quickly gains saturate.
Fixed-Interface Added Context Probes: To test evidence attribution, they inject extra context from other paradigms (e.g., injecting KGCompass evidence into Agentless) into a fixed native interface.
- Controls: They use same-token filler controls (non-informative text matching the token count) and same-repository hard negatives (irrelevant evidence from the same repo) to ensure gains are due to information quality, not just prompt length.
Common-Wrapper Check: A subset of experiments uses a shared repair wrapper and prompt builder to determine if gains are dependent on specific system architectures.

3. Key Contributions

Controlled Post-Localization Study: The first study to decouple localization from context construction and patch generation across multiple RAG-APR paradigms using a unified protocol.
Bounded Headroom Characterization: Quantifies that while stronger localization helps, the remaining recoverable gains from within-system search are bounded and saturate quickly.
Evidence Attribution: Demonstrates that informative added context outperforms token-matched controls, but simple prompt fusion (combining all evidence) does not always yield additive gains and can sometimes dilute performance.
Residual Frontier Analysis: Identifies a large, jointly-unsolved frontier that persists even after optimizing localization, search, and context fusion.

4. Key Results

RQ1: Oracle Gain and Failure Concentration

Localization helps but isn't a silver bullet: Oracle Localization improved success rates for all three systems (e.g., Agentless rose from 28.0% to 40.3%), but success remained below 50% for all.
Shift in Failure Modes: Oracle localization primarily reduced "no patch submitted" failures. The remaining failures were mostly "completed but unresolved" (the model generated a patch, but it failed tests).
Wrapper Dependence: Under a shared wrapper, Agentless showed a massive performance drop compared to its native wrapper, whereas KGCompass and ExpeRepair retained most of their gains. This suggests Agentless is highly sensitive to how the prompt is constructed.

RQ2: Selection Headroom and Saturation

Rapid Saturation: Increasing the candidate pool from $K=1$ to $K=5$ captured 86.2%–87.5% of the total possible gain available in a $K=10$ pool.
Selector Sensitivity: While the pool contains solutions, default system ordering often misses them. However, even the best rerankers leave a gap of 1.3–2.0 points compared to the theoretical greedy upper bound.
Insight: The bottleneck is not just generating more samples, but reaching the right "patch family" early and ranking the correct variant within that family.

RQ3: Fixed-Interface Evidence Attribution

Informative Context Wins: Added context (e.g., KG evidence in Agentless) significantly outperformed same-token filler and hard-negative controls.
Non-Monotonic Fusion: Simply concatenating all evidence sources (UnionContext) did not always yield the best results.
- On Agentless, the best single-source probe (KG-augmented) outperformed the UnionContext.
- On ExpeRepair, UnionContext improved early coverage but offered only marginal final gains.
Dilution Effect: Adding too much context or wrong evidence (hard negatives) can dilute strong single-source trajectories, reducing stable solves.

RQ4: Residual Cross-System Frontier

Limited Frontier Recovery: Even with Oracle Localization, Best-of- $K$ $K$ , and cross-paradigm probes, a large frontier remains.
- The native union of the three systems solved 199/300 instances.
- The best fixed probes recovered only 6 additional instances beyond this native union.
- Even under a favorable "post-hoc ceiling" (best possible combination of all probes), only 14 of the 101 remaining frontier cases were recovered.
Failure Modes: The residual frontier is concentrated in specific failure patterns: Wrong API/Runtime exceptions, Incomplete fixes, and Missing imports/NameErrors. These are hard to resolve with current prompt-level improvements alone.

5. Significance

This paper fundamentally shifts the research agenda for Repository-Level APR:

Beyond Localization: While localization is necessary, it is no longer the sole bottleneck. The field must address post-localization challenges.
Interface Design Matters: The way evidence is packaged and the prompt wrapper is constructed (especially for systems like Agentless) significantly impacts performance, sometimes more than the retrieval itself.
Search vs. Generation: The "headroom" for finding the right patch is bounded; future gains likely require better patch generation strategies and validation logic rather than just better retrieval or more context.
Hard Frontiers: A significant portion of repository-level repair failures stems from deep semantic issues (API usage, logic completeness) that current LLM prompting and RAG strategies struggle to resolve, suggesting a need for new architectural approaches beyond simple context augmentation.