PatchRecall: Patch-Driven Retrieval for Automated Program Repair

Probleemstelling

Automatische Programmatuurherstel (Automated Program Repair - APR) staat voor een fundamentele uitdaging bij het werken met grote codebases: het vinden van het juiste bestand dat moet worden aangepast op basis van een probleemomschrijving (issue).

• Het Dilemma: Er bestaat een afweging tussen recall (het vinden van alle relevante bestanden) en efficiëntie/concisie. Als te weinig bestanden worden opgehaald, wordt het juiste bestand gemist. Als er te veel bestanden worden opgehaald, introduceert dit "ruis" (noise) die de Large Language Models (LLMs) afleidt en de prestaties verslechtert.
• Huidige Beperkingen: Bestaande benchmarks zoals SWE-bench tonen aan dat zelfs geavanceerde modellen (zoals Claude-2) minder dan 2% van de taken oplossen. Traditionele zoekmethoden (zoals BM25) halen vaak veel irrelevante bestanden op, terwijl empirische analyses tonen dat in meer dan 80% van de gevallen slechts één bestand daadwerkelijk moet worden gewijzigd.
• Empirische Bevindingen: Een studie op de SWE-bench-dataset toonde aan dat falen vaak samenhangt met de complexiteit van de taak en de onbekendheid van het systeem met de specifieke codebase-structuur. Veel agents falen omdat ze de locatie van de wijziging niet kunnen lokaliseren, niet omdat ze de code niet kunnen genereren.

Methodologie: PatchRecall

De auteurs stellen PatchRecall voor, een hybride zoekstrategie die recall maximaliseert zonder de hoeveelheid opgehaalde bestanden onnodig te vergroten. De methode combineert twee complementaire strategieën:

1. Codebase Retrieval (Directe Zoeking):

   • De probleemomschrijving wordt direct vergeleken met de inhoud van de doel-repository.
   • Hiervoor wordt BM25 (een traditionele, sparse retrieval methode) gebruikt om bestanden te scoren op basis van tekstuele overeenkomst.

2. History-Based Retrieval (Patch-Driven Zoeking):

   • Deze strategie benut de geschiedenis van het SWE-bench-dataset.
   • Voor een nieuwe issue worden de 10 meest vergelijkbare eerdere issues opgehaald uit het unverified deel van de dataset (gebruikmakend van een Sentence Transformer model, specifiek all-mpnet-base-v2).
   • Van deze vergelijkbare eerdere issues worden de bijbehorende patches geanalyseerd om te zien welke bestanden er toen zijn gewijzigd.
   • Bestanden die vaak voorkomen in deze historische patches krijgen een hogere score.

3. Hybride Score Fusion & Her-ranking:

   • De resultaten van beide strategieën worden samengevoegd.
   • De scores van beide methoden worden genormaliseerd (min-max normalisatie) om ze vergelijkbaar te maken.
   • Een hybride score $H(f)$ wordt berekend met een gewogen som:
     $$H(f) = \alpha \cdot s'_{ST}(f) + (1 - \alpha) \cdot s'_{BM25}(f)$$
     Waarbij $s'_{ST}$ de score is van de Sentence Transformer (gebaseerd op patch-gebruik) en $s'_{BM25}$ de score van de directe codebase-zoekopdracht.
   • De parameter $\alpha$ (tussen 0 en 1) bepaalt de balans. Experimenten tonen aan dat een waarde tussen 0,4 en 0,6 de beste resultaten oplevert.
   • De bestanden worden opnieuw gerangschikt op basis van deze hybride score, en de top-$k$ bestanden worden als context naar de LLM gestuurd voor het genereren van de patch.

Belangrijkste Bijdragen

• Hybride Framework: Een nieuw framework dat semantische zoekopdrachten (via embeddings) combineert met historische patch-data om de precisie van bestandslokalizatie te verbeteren.
• Empirische Validatie: Een grondige analyse van de SWE-bench-dataset die aantoont dat traditionele methoden te veel ruis introduceren en dat een hybride aanpak nodig is om de "single-file" aard van de meeste reparaties te benutten.
• Efficiëntie: Het bewijs dat het mogelijk is om de recall te verhogen zonder de lijst met kandidaat-bestanden onbeperkt uit te breiden, wat cruciaal is voor de prestaties van downstream LLM's.

Resultaten

De experimenten zijn uitgevoerd op de SWE-bench-verified dataset (500 menselijk gevalideerde issue-patch paren).

• Baseline Vergelijking: De Sentence Transformer (dense retrieval) presteerde consistent beter dan zowel BM25 als TF-IDF op alle dieptes van $k$ (aantal opgehaalde bestanden). Dit benadrukt het belang van semantisch begrip boven puur tekstuele matching.
• Hybride Prestaties: De hybride aanpak met score fusion ($\alpha \approx 0,4$) behaalde de hoogste recall in vergelijking met alleen BM25 of alleen de Sentence Transformer.
  • Bijvoorbeeld: Bij het ophalen van een beperkt aantal bestanden (lage $k$), behaalde de hybride methode een significant hogere recall dan de BM25-baseline die in andere frameworks (zoals MAGIS) wordt gebruikt.
• Vergelijking met MAGIS: Hoewel frameworks zoals MAGIS gebruikmaken van multi-agent samenwerking, blijft de zoekfase een knelpunt. PatchRecall verbetert deze specifieke fase en levert een hogere recall op dan de BM25-baseline van MAGIS, wat aantoont dat een lichte, modulaire zoekverbetering complementair kan werken aan complexere agent-systemen.

Betekenis en Conclusie

PatchRecall adresseert een kritieke bottleneck in het veld van APR: het lokaliseren van de juiste bestanden.

• Praktische Impact: Door de ruis te verminderen en de context voor de LLM te verfijnen, maakt deze methode repository-level automatische reparatie praktischer en schaalbaarder.
• Toekomstperspectief: De auteurs suggereren dat adaptieve weging (dynamisch aanpassen van $\alpha$ op basis van taakcomplexiteit) en het integreren van structurele signalen (zoals Abstract Syntax Trees of dependency graphs) de prestaties verder kunnen verbeteren.
• Conclusie: Het paper bewijst dat het combineren van directe codezoekopdrachten met historische patch-informatie een krachtige, kosteneffectieve manier is om de prestaties van APR-systemen te verhogen, zonder afhankelijk te zijn van zware multi-agent architecturen.