Planning to Explore: Curiosity-Driven Planning for LLM Test Generation

Probleemstelling

Het gebruik van Large Language Models (LLMs) voor het genereren van code is uitgebreid naar het genereren van tests. Echter, bestaande methoden voor LLM-gebaseerde testgeneratie kampen met een fundamenteel probleem: ze zijn gierig (greedy).

• De beperking: Deze methoden maximaliseren de onmiddellijke winst in code-dekking (coverage). Ze genereren tests onafhankelijk van elkaar en leren niet van eerdere uitvoeringen.
• Het "Corridor"-probleem: In complexe codebases zijn er vaak diepe takken (branches) die alleen bereikbaar zijn via een reeks opzetstappen (bijv. initialisatie, validatie-gates, import-chains). Elke individuele stap in deze reeks levert geen nieuwe code-dekking op. Omdat gierige strategieën alleen kijken naar directe winst, blijven ze steken in oppervlakkige code en missen ze deze diepere logica. Ze bereiken een plateau waar ze niet verder komen.

Methodologie: CovQValue

De auteurs formuleren testgeneratie als een Bayessche exploratie van een onbekende omgeving, geïnspireerd door theorieën over kunstmatige nieuwsgierigheid (curiosity) en optimal exploration (Sun et al., 2011). De kern van hun methode, CovQValue, is als volgt opgebouwd:

1. Bayessch Raamwerk:

   • De onbekende parameter ($\Theta$) is de volledige structuur van de bereikbaarheid van takken in het programma.
   • De dekkingkaart (coverage map) fungeert als een voldoende statistiek (sufficient statistic) die de exploratiestatus samenvat. Deze kaart wordt na elke uitvoering bijgewerkt en teruggekoppeld naar de LLM.
   • In plaats van alleen te kijken naar wat er nu wordt ontdekt, probeert de agent de toekomstige bereikbaarheid te voorspellen.

2. Nieuwsgierigheids-Q-waarde (Curiosity Q-value):
   De methode selecteert testplannen niet op basis van directe dekking, maar op basis van een geschatte Q-waarde die twee componenten combineert:
   $$Q = \hat{g} + \gamma \cdot \hat{v}$$

   • $\hat{g}$: De verwachte onmiddellijke winst (hoeveel nieuwe takken worden direct bedekt?).
   • $\hat{v}$: De toekomstige bereikbaarheid (hoeveel extra takken worden toegankelijk gemaakt door deze stap, zelfs als ze niet direct worden bedekt? Bijvoorbeeld het passeren van een validatie-gate).
   • $\gamma$: Een disconteringsfactor die het gewicht van de toekomstige waarde bepaalt.

3. Implementatie:

   • De LLM genereert $K$ diverse kandidaat-plannen (elk bestaand uit een reeks van $S$ scripts) met verschillende exploratie-instructies (bijv. focus op foutafhandeling, hoofdfunctionaliteit).
   • De LLM schat voor elk plan de Q-waarde door de dekkingkaart te analyseren.
   • Het plan met de hoogste Q-waarde wordt uitgevoerd.
   • De resulterende dekking update de kaart voor de volgende ronde.

Belangrijkste Bijdragen

1. Formalisatie van Testgeneratie: De auteurs formuleren testgeneratie als Bayessche exploratie, waarbij de dekkingkaart de kern vormt van de feedbacklus. Dit biedt een theoretisch onderbouwd alternatief voor gierige dekking-gerichte benaderingen.
2. RepoExploreBench: Ze introduceren een nieuwe benchmark specifiek voor iteratieve, exploratie-gebaseerde testgeneratie. Deze bestaat uit 93 modules van 9 populaire Python-pakketten (zoals Flask, Requests, Pydantic) die gekenmerkt worden door "corridor-structuren" (complex opzetwerk). Bestaande benchmarks testen vaak slechts één-shot generatie.
3. CovQValue Methode: Een werkend systeem dat dekking-kaart feedback, diverse plan-generatie en Q-waarde selectie combineert om maximale tak-ontdekking te bereiken.

Resultaten

De methoden zijn getest op drie populaire LLMs (Gemini 3 Flash, GPT-5.4 Mini, Mistral Large 3) op twee benchmarks: TestGenEval Lite en het nieuwe RepoExploreBench.

• Prestatieverbetering: CovQValue presteert aanzienlijk beter dan gierige selectie en willekeurige baselines.
  • Op RepoExploreBench: 40% tot 74% meer tak-dekking.
  • Op TestGenEval Lite: 51% tot 77% meer tak-dekking.
  • De methode wint in 77% tot 84% van de individuele doelen.
• Corridor Navigatie: De resultaten tonen aan dat CovQValue succesvol door "corridors" (opzetreeksen met nul directe winst) navigeert, terwijl gierige methoden hier vastlopen.
• Ablatie-studies:
  • Zonder dekking-kaart feedback presteert de LLM-selectie niet beter dan willekeur.
  • Het toevoegen van Q-waarde scoring (toekomstige waarde) is cruciaal; een disconteringsfactor ($\gamma$) van 0.5 bleek het meest effectief.
  • Langere plannen (meerdere stappen vooruit kijken) leiden tot betere dekking, wat de waarde van multi-step planning bevestigt.
• Trade-off: CovQValue genereert tests met een iets lagere "pass rate" (meer tests falen), maar dit komt omdat de LLM durft om ambitieuzere tests te schrijven die onbekende codepaden targeten, in plaats van veilige, herhalende tests.

Betekenis en Toekomst

Dit paper toont aan dat planning-bewuste exploratie essentieel is voor LLM-agents die werken in onbekende omgevingen met complexe afhankelijkheden.

• Theoretische impact: Het verbindt theorieën over kunstmatige nieuwsgierigheid en Bayessche optimalisatie succesvol toe met praktische software-engineering taken.
• Praktische impact: Het lost het probleem op waarbij LLMs vastlopen in complexe codebases die veel opzetwerk vereisen.
• Toepassingsgebied: Hoewel gericht op testgeneratie, is het raamwerk breed toepasbaar op andere agent-systemen die sequentieel interageren met een onbekende omgeving, zoals API-discovery, wetenschappelijke experimenten of het verkennen van complexe systemen.

Samenvattend bewijst CovQValue dat het integreren van een "nieuwsgierige" blik op de toekomst (via Q-waarden) en het gebruik van een gestructureerde feedback-loop (dekkingkaart) de beperkingen van huidige gierige LLM-testgenerators effectief doorbreekt.