Technische Samenvatting: EvoOtter

Probleemstelling

De generatie van Bug Reproduction Tests (BRTs) is een cruciale stap in software engineering, die dient om de aanwezigheid van een bug te bevestigen voordat een fix wordt toegepast. In tegenstelling tot traditionele testgeneratie, die streeft naar passerende tests, moet een BRT "fail-to-pass" (F2P) zijn: het moet falen op de huidige buggy code ($c_{old}$) maar slagen op de toekomstige opgeloste code ($c_{new}$).

De primaire uitdaging bij BRT-generatie is het gebrek aan betrouwbare feedback. Omdat de opgeloste code ($c_{new}$) niet beschikbaar is tijdens de generatie, is het moeilijk om te bepalen of een kandidaat-test faalt om de juiste reden of om de beste kandidaat te selecteren tussen vele opties. Eerdere benaderingen vertrouwden op "inference scaling"—het genereren van veel kandidaten en het gebruik van Large Language Models (LLMs) of executie-feedback om deze te selecteren en te verbeteren. Deze methoden zijn echter vaak duur vanwege het hoge aantal LLM-aanroepen en lijden onder onbetrouwbare feedback of test-overfitting.

Methodologie: EvoOtter

EvoOtter pakt deze uitdagingen aan door evolutionaire programmering te combineren met LLMs, specifiek afgestemd op het verminderen van kosten en het aanscherpen van feedbacksignalen. De workflow werkt op een populatie van kandidaat-tests en een populatie van code-mutanten.

1. Kern van de Evolutionaire Loop

Het systeem onderhoudt twee populaties:

• Predators (Roofdieren): Kandidaat BRTs.
• Prey (Prooi): Buggy varianten van de code (mutanten).

De evolutionaire loop verloopt als volgt:

1. Initialisatie: Een basisgenerator creëert $n$ initiële diverse tests (meestal 8) met behulp van heterogene prompting om variatie aan te brengen in issuebeschrijvingen en context.
2. Mutant Generatie: Een regelgebaseerde generator creëert $m$ code-mutanten door specifieke mutatie-operators toe te passen (bijv. rekenkundige wissels, vervanging van constanten, geforceerde fouten) op gelokaliseerde focusfuncties waarvan wordt vermoed dat ze de bug bevatten. Er wordt geen LLM gebruikt voor deze stap.
3. Fitness Evaluatie: Elke test wordt uitgevoerd tegen de huidige populatie van mutanten. De fitnessscore wordt gedefinieerd als het aantal mutanten dat door de test wordt "gedood" (killed).
   • Nieuwigheid in de definitie van 'Killing': Omdat de originele code al buggy is, wordt het doden van een mutant door een test niet simpelweg gedefinieerd als een testfout. In plaats daarvan analyseert het systeem de executielogs. Een mutant wordt beschouwd als "gedood" als de test op de mutant faalt om een andere reden dan hij faalde op de originele code (geïndiceerd door een verandering in de logoutput).
4. Selectie (Successive Halving): Tests worden gesorteerd op fitness, waarbij de onderste helft wordt weggegooid. Om een sterk feedbacksignaal te behouden terwijl de executiekosten constant blijven, verdubbelt het systeem het aantal mutanten in de volgende generatie (door te samplen uit een vooraf gegenereerde pool) terwijl de testpopulatie wordt gehalveerd. Dit proces herhaalt zich totdat er één test overblijft.
5. Crossover (Batched Repair): De overlevende tests worden gebruikt als ouders. Er wordt één enkele LLM-aanroep gebruikt om de gehele volgende generatie nakomelingen te genereren. De LLM wordt geprompt om statements tussen de ouder-tests en hun executielogs uit te wisselen, toe te voegen of te verwijderen om ze te verbeteren. Deze "gebatchte crossover" voorkomt de hoge kosten van individuele LLM-aanroepen per test.

2. Mechanismen voor Kostenbeheersing

• Successive Halving: Vermindert de testpopulatie elke generatie met de helft, terwijl het aantal mutanten wordt verdubbeld, waardoor het totale aantal test-executies per iteratie constant blijft ($2m$).
• Batched Crossover: Genereert alle nakomelingen voor een generatie in één enkele LLM-aanroep in plaats van één aanroep per kandidaat.
• Regelgebaseerde Mutanten: Gebruikt deterministische code-rewrite regels voor mutanten in plaats van LLMs, waardoor LLMs strikt worden gereserveerd voor testgeneratie en evolutie.
• Single-Prompting Optie: Hoewel het standaardproces heterogene prompting gebruikt voor initiële diversiteit, ondersteunt het systeem een "single-prompt" modus waarbij één LLM-aanroep alle initiële kandidaten genereert. Dit vermindert de kosten aanzienlijk en maakt het gebruik van krachtigere (maar duurdere) reasoning-modellen zoals Claude-Opus-4.7 mogelijk.

Belangrijkste Bijdragen

1. EvoOtter Workflow: De eerste BRT-generatieworkflow gebaseerd op evolutionaire programmering, die mutatietesten en successive halving integreert.
2. Mutation-Based Fitness Score: Een nieuwe fitnessmetriek die het aantal regelgebaseerde code-mutanten telt die door een test worden gedood, waarbij gebruik wordt gemaakt van logverschillen om de "buggy originele code"-scenario's af te handelen.
3. Batched Crossover: Een techniek die moderne LLM-capaciteiten benut om een volledige generatie tests in één enkele aanroep te evolueren, waarbij een balans wordt gevonden tussen prestaties en kosten.

Experimentele Resultaten

De auteurs evalueerden EvoOtter op drie benchmarks: TDD-Bench-Verified, SWE-Rebench, en SWT-Bench-Verified.

• Prestaties: Met gebruik van Claude-Sonnet-4.5 met heterogene prompting bereikte EvoOtter een F2P-rate van 65,9% op TDD-Bench-Verified en 51,9% op SWE-Rebench, waarmee het eerdere baselines versloeg die uitsluitend vertrouwen op selectie of reparatie (zoals e-Otter).
• State-of-the-Art: Door gebruik te maken van single prompting met het sterkere reasoning model Claude-Opus-4.7, bereikte EvoOtter 75,3% op TDD-Bench-Verified en 66,3% op SWE-Rebench. Op de SWT-Bench-Verified leaderboard bereikte het 77,8%.
• Kostenefficiëntie: EvoOtter behaalt deze resultaten tegen een fractie van de kosten van eerdere inference-scaling benaderingen. De gemiddelde kosten per instantie zijn ongeveer $0,17 (exclusief initiële generatie) voor de standaard workflow, en $0,88 voor de high-performance single-prompt variant, vergeleken met aanzienlijk hogere kosten voor methoden die individuele repair-loops vereisen.
• Componentanalyse:
  • Selectie: Mutatie-gebaseerde selectie presteerde beter dan LLM-gebaseerde en willekeurige selectie in latere evolutionaire fasen, hoewel LLMs goed presteerden in de initiële fase.
  • Crossover: Het verwijderen van crossover veroorzaakte een prestatiedaling van meer dan 10%, wat de cruciale rol ervan benadrukt.
  • Diversiteit: Single prompting verminderde de diversiteit licht, maar voorkwam niet dat de evolutionaire operators effectief tests konden selecteren en verbeteren.

Betekenis en Claims

Het artikel claimt dat EvoOtter aantoont hoe men efficiënt en effectief evolutionaire programmering met LLMs kan combineren voor software engineering taken. De primaire betekenis ligt in:

• Robuustheid: Het bieden van betrouwbaardere feedbacksignalen via mutatietesten in plaats van enkel te vertrouwen op potentieel ruisende LLM-oordelen of executie op de buggy code alleen.
• Efficiëntie: Het drastisch verminderen van de kosten van BRT-generatie door LLM-aanroepen te minimaliseren via gebatchte operaties en successive halving, wat de aanpak schaalbaar maakt.
• Practicaliteit: Het behalen van state-of-the-art resultaten op geverifieerde benchmarks terwijl de inferentiekosten laag blijven, wat suggereert dat evolutionaire strategieën een levensvatbaar alternatief kunnen zijn voor pure inference scaling voor complexe software engineering taken.

De auteurs merken op dat hun bevindingen momenteel beperkt zijn tot Python-repositories en dat de ontwerpkeuzes (zoals single-prompting) zijn afgestemd op de capaciteiten van recente frontier-modellen.