Technisch Overzicht: Counterexample Guided Learning in the Large met Reasoning Agents

Probleemstelling

Het artikel adresseert de uitdaging om Large Language Models (LLMs) en agents effectief te laten leren en te laten adapteren op basis van feedback. Hoewel feedback cruciaal is voor coding agents, tool-gebruikers en gepersonaliseerde assistenten, is het meten en verbeteren van het vermogen van een model om feedback te benutten moeilijk vanwege de heterogeniteit, domeinspecificiteit en het gebrek aan controleerbaarheid in typische feedbackmechanismen.

Om een controleerbaar testbed voor deze capaciteit te creëren, richten de auteurs zich op regular-expression (regex) inductie. Dit is een klassiek symbolisch leerprobleem waarbij het doel is om een reguliere expressie (de doeltaal $L^\star$) af te leiden uit een verzameling gelabelde strings (positieve en negatieve voorbeelden). De taak is inherent uitdagend omdat veel kandidaat-expressies een kleine set voorbeelden kunnen passen, wat leidt tot overfitting op oppervlakkige patronen. De auteurs formuleren dit als een oracle-guided symbolic generation problem, waarbij een LLM (de leerling) zijn hypothese iteratief verfijnt op basis van feedback van een verifieerder (de leraar) in de vorm van tegenvoorbeelden (counterexamples).

Methodologie

Het voorgestelde framework integreert LLMs met een teacher-learner loop, versterkt door agentic workflows. Het systeem werkt via de volgende componenten:

1. Teacher-Learner Iteratief Framework

• Learner: Een LLM stelt een kandidaat reguliere expressie voor op basis van de huidige verzameling gelabelde voorbeelden.
• Teacher: Een verifieerder controleert de kandidaat tegen de doeltaal. Omdat de equivalentie van reguliere talen beslisbaar is, construeert de teacher de symmetrische differentie $L(\hat{r}) \triangle L^\star$ tussen de kandidaat en de doeltaal.
• Feedback: Als de kandidaat onjuist is, geeft de teacher tegenvoorbeelden (strings die in de doeltaal zouden moeten zitten maar dat niet doen, of andersom). Deze worden toegevoegd aan de trainingsset voor de volgende ronde.

2. Synthese en Clustering van Tegenvoorbeelden

Om de potentieel oneindige hoeveelheid tegenvoorbeelden te beheren (vooral die voortkomen uit Kleene-sterren/loops), introduceren de auteurs Clustered Counterexamples:

• In plaats van individuele strings terug te geven, analyseert de teacher de geminimaliseerde verschil-automaat.
• Het groepeert uitgaande symbolen vanuit een staat die naar dezelfde bestemmingsstaat leiden in "super-karakters" (bijvoorbeeld het representeren van $\{A, \dots, Z, a, \dots, z\}$ als $[A-Za-z]$).
• Een geclusterd tegenvoorbeeld is een pad in deze automaat met behulp van deze super-karakters, wat een verzameling concrete strings representeert die dezelfde foutmodus delen. Dit biedt een meer systematisch en minder redundant overzicht van de foutregio.

3. Agentic Workflow

Het framework tilt de standaard teacher-learner loop naar een agentic workflow bestaande uit twee loops:

• Outer Loop (Reflection): De LLM wordt geprompt om te reflecteren op eerdere pogingen. Het ontvangt de vorige hypothese, de reasoning trace en nieuwe tegenvoorbeelden. Het model krijgt de instructie om uit te leggen wat er misging en hoe de hypothese te herzien.
• Inner Loop (Repair): Om consistentie te waarborgen, gebruikt het systeem een repair loop. Het bevraagt de LLM herhaaldelijk om kandidaten te genereren die voldoen aan:
  1. Syntax Check: De regex moet syntactisch geldig zijn.
  2. Satisfaction Check: De regex moet alle geaccumuleerde tegenvoorbeelden correct labelen.
  • Een RepairScore functie evalueert kandidaten op basis van compilatiesucces en het fractie van foutief geclassificeerde voorbeelden, waarbij de beste kandidaat uit meerdere pogingen wordt geselecteerd.

4. Regularisatie

Om te voorkomen dat de LLM overly specifieke of complexe expressies genereert die passen bij de huidige sample set maar niet algemeen generaliseren, maakt het systeem gebruik van prompt-level regularisatie. Dit omvat beperkingen op de maximale expressie lengte, de nesting diepte van operatoren en een bias naar simpelere hypothesen.

Belangrijkste Bijdragen

1. Oracle-Guided Formulering: Het artikel formuleert LLM-gebaseerde regex inductie als een iteratief symbolisch leerprobleem waarbij hypothesen worden verfijnd via tegenvoorbeeld-feedback, waardoor de kloof tussen traditionele programmasynthese (CEGIS) en moderne LLM-inferentie wordt overbrugd.
2. Active Learning Methodologie: Het introduceert technieken voor het bouwen van effectieve LLM-gebaseerde active learners, specifiek symbolic counterexample clustering en regularisatie om simpelere, meer plausibele hypothesen te prioriteren.
3. Agentic Workflow: De auteurs ontwikkelen een nieuw agentic framework dat gebruikmaakt van reflection (om structurele implicaties van fouten te extraheren) en iteratieve repair loops om mislukte hypothesen te herzien, waarmee ze verder gaan dan eenvoudige prompt-gestuurde generatie.
4. Strikte Evaluatie: De studie biedt een uitgebreide evaluatie over twee datasets (Simple en Extended Regex) en meerdere backbone modellen, waarbij de prestatiedynamiek, sample efficiëntie en de impact van specifieke componenten worden geanalyseerd.

Resultaten

De auteurs evalueerden hun framework op twee datasets: Simple Regex (standaard operatoren over $\{a, b, c\}$) en Extended Regex (ondersteunt intersectie, negatie en complexe kwantificatoren).

• Prestatiewinst: Op de moeilijkste taken (hoge StarDepth) presteerde het tegenvoorbeeld-gestuurde framework aanzienlijk beter dan standaard prompting.
  • Op Simple Regex (StarDepth 4) verbeterde het succespercentage van 3.2% (Standaard) naar 38.1% (Agentic).
  • Op Extended Regex (StarDepth 2) verbeterde het succespercentage van 38.9% (Standaard) naar 74.1% (Agentic).
• Sample Efficiëntie: Tegenvoorbeeld-gestuurd leren verminderde het aantal benodigde gelabelde voorbeelden om een doel nauwkeurigheid te bereiken aanzienlijk vergeleken met methoden die willekeurig gesamplede voorbeelden gebruiken.
• Component Analyse:
  • Clustered Counterexamples: Presteerde consequent beter dan niet-geclusterde (individuele string) tegenvoorbeelden, wat aangeeft dat de kwaliteit en systematische dekking van feedback belangrijker zijn dan alleen het volume.
  • Agentic vs. Single: De volledige agentic workflow (met reflection en repair) presteerde consequent beter dan single-inference benaderingen die dezelfde tegenvoorbeelden gebruikten, hoewel dit een hogere token cost met zich meebracht.
  • Model Agnosticisme: De verbeteringen werden waargenomen bij diverse backbone modellen (Qwen3, GPT-5.4 varianten, GPT-oss), wat suggereert dat het framework robuust is tegen modelkeuze.
  • Ablatie: Hoewel regularisatie hielp om vroege overfitting te voorkomen, leverde de repair loop de grootste prestatiewinst op. Reflection droeg bij aan succes, maar was minder kritiek dan het repair mechanisme.

Betekenis en Claims

Het artikel claimt dat LLMs kunnen profiteren van rijke feedback die verder gaat dan het behandelen van feedback als aanvullende data. Door feedback te behandelen als een gestructureerd, iteratief signaal (tegenvoorbeelden) in plaats van statische trainingsdata, kunnen LLM's deelnemen aan robuuste, verifieerder-gestuurde verfijning.

De auteurs positioneren dit werk als een stap naar robuuste verifieerder-gestuurde methoden voor LLM-gebaseerde programmasynthese en formeel redeneren. Ze stellen dat in domeinen waar informatieve fouten kunnen worden gesynthetiseerd (verifieerbare domeinen), agents verder kunnen gaan dan louter het fitten van voorbeelden naar het uitvoeren van betrouwbare iteratieve verfijning. De studie suggereert dat de combinatie van symbolische verificatie (tegenvoorbeelden) en agentic reasoning (reflection/repair) een synergie creëert die het mogelijk maakt voor LLM's om complexe symbolische inductietaken op te lossen waar standaard prompting faalt.