🤖 machine learning

Counterexample Guided Learning in the Large using Reasoning Agents

Diese Arbeit zeigt, dass die Ausstattung von LLM-Agenten mit Strategien des gegenbeispielgestützten Lernens, bei denen ein Verifizierer spezifisches Feedback zu fehlerhaften regulären Ausdruckskandidaten gibt, die Stichprobeneffizienz und Erfolgsraten bei komplexen symbolischen Induktionsaufgaben im Vergleich zu Standard-Prompting signifikant verbessert.

Ursprüngliche Autoren: Hongyi Liu, Frederic Sala, Thomas Reps, Adithya Murali

Veröffentlicht 2026-06-11

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Hongyi Liu, Frederic Sala, Thomas Reps, Adithya Murali

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, einem sehr intelligenten, aber leicht verwirrten Roboter beizubringen, einen Haufen durcheinandergewürfelter Spielzeuge zu sortieren. Sie möchten dem Roboter eine bestimmte Regel beibringen, wie zum Beispiel: „Behalte alle roten Blöcke und die blauen Autos, aber wirf alles andere weg.“

Früher hätten Sie dem Roboter einfach ein paar Beispiele gezeigt: „Hier ist ein roter Block (behalten), hier ist ein blaues Auto (behalten), hier ist ein grüner Ball (wegwerfen).“ Der Roboter würde eine Regel erraten. Wenn er falsch lag, hätten Sie ihm einfach mehr Beispiele gezeigt. Das ist wie Standard-Prompting: Man füttert den Roboter immer wieder mit Daten, in der Hoffnung, dass er die Regel schließlich selbst herausfindet.

Dieses Paper stellt eine intelligentere Methode vor, um den Roboter zu lehren, genannt Counterexample-Guided Learning (Lernen durch Gegenbeispiele). Anstatt dem Roboter einfach nur mehr zufällige Beispiele zu zeigen, bekommt er einen „Lehrer“, der wie ein strenger Korrektor agiert.

Die Kernidee: Der „Korrektor“-Lehrer

So funktioniert die neue Methode unter Verwendung einer einfachen Analogie:

Die Vermutung: Der Roboter (der „Lerner“) betrachtet die Beispiele, die Sie ihm gegeben haben, und schreibt eine Regel auf (einen „Regulären Ausdruck“, was nur eine schicke Art ist, eine Musterbeschreibung zu sagen).
Die Prüfung: Ein „Lehrer“ (ein Computerprogramm, das die tatsächliche korrekte Regel kennt) überprüft die Regel des Roboters.
Das Gegenbeispiel (Das „Erwischt!“-Moment): Wenn die Regel des Roboters falsch ist, sagt der Lehrer nicht einfach nur „Nein“. Er findet ein spezifisches Spielzeug, bei dem der Roboter einen Fehler gemacht hat.
- Beispiel: Die Regel des Roboters lautet „Behalte alles Rote“. Der Lehrer findet einen roten Ball, der laut der wahren Regel eigentlich weggeworfen werden sollte. Der Lehrer reicht dem Roboter diesen roten Ball und sagt: „Schau mal! Diesen hast du behalten, aber das solltest du nicht. Korrigiere deine Regel.“
- Dieser spezifische Fehler wird als Gegenbeispiel bezeichnet. Es ist ein direkter Beweis dafür, warum die aktuelle Vermutung fehlgeschlagen ist.

Das Geheimrezept: „Geklumpte“ Fehler

Das Paper fand heraus, dass der Roboter manchmal immer wieder die gleiche Art von Fehler macht. Wenn die Regel „Behalte alle Buchstaben“ lautet und der Roboter den Buchstaben „Z“ vergisst, könnte der Lehrer dem Roboter „Z“, „A“, „B“, „C“... alle auf einmal zeigen. Das wäre zu viel Rauschen.

Deshalb haben die Autoren Clustered Counterexamples (geklumpte Gegenbeispiele) erfunden. Anstatt dem Roboter 26 verschiedene Buchstaben zu zeigen, die falsch sind, sagt der Lehrer: „Dir fehlt die ganze Kategorie der Buchstaben.“ Er gruppiert ähnliche Fehler zu einem einzigen, aussagekräftigen Hinweis. Dies hilft dem Roboter, das Muster seines Fehlers zu verstehen, anstatt nur eine Liste schlechter Beispiele auswendig zu lernen.

Der „Agent“-Workflow: Reflexion und Reparatur

Das Paper gibt dem Roboter auch ein „Gehirn“, das über sein eigenes Denken nachdenken kann. Dies wird als Agentic Workflow bezeichnet. Es läuft in zwei Schleifen ab:

Reflexion (Das „Anhalten und Nachdenken“): Nachdem der Lehrer auf einen Fehler hingewiesen hat, wird der Roboter aufgefordert, anzuhalten und zu erklären, warum er diesen Fehler gemacht hat. „Oh, ich dachte, ‚rot‘ bedeutete ‚alle roten Dinge‘, aber die Regel meinte eigentlich nur ‚rote Blöcke‘.“ Dies hilft dem Roboter, die Logik zu lernen, nicht nur die Antwort.
Reparatur-Schleife (Der „Neustart“): Wenn die neue Regel des Roboters immer noch einen Syntaxfehler (wie einen Tippfehler) aufweist oder immer noch ein Beispiel falsch bearbeitet, gibt das System nicht auf. Es schickt den Roboter zurück an den Zeichentisch mit einem spezifischen Hinweis: „Deine Regel hat hier einen Tippfehler, und du hast diesen roten Ball immer noch falsch behandelt. Versuche es erneut.“ Der Roboter probiert es so lange, bis er es richtig macht.

Was sie herausgefunden haben

Die Forscher testeten dies bei zwei Arten von „Spielzeug-Sortieraufgaben“:

Einfache Regeln: Basismuster (wie „rote Blöcke“).
Komplexe Regeln: Knifflige Muster mit vielen verschachtelten Bedingungen (wie „rote Blöcke, die auch quadratisch sind, aber nicht, wenn sie glänzend sind“).

Die Ergebnisse:

Standardmäßiges Lehren (nur Beispiele zeigen) scheiterte kläglich an den komplexen Regeln. Der Roboter blieb bei der Vermutung falscher Muster stecken.
Counterexample-Lehren (Verwendung des „Erwischt!“-Feedbacks) machte den Roboter viel besser. Er benötigte weit weniger Beispiele, um die komplexen Regeln zu lernen.
Die „Agent“-Meth Methode (Reflexion + Reparatur) war der Gewinner. Bei den schwierigsten Aufgaben sprang die Erfolgsquote von winzigen 3,2 % (mit Standard-Lehren) auf 38,1 %. Bei einem anderen Satz schwieriger Aufgaben sprang sie von 38,9 % auf 74,1 %.

Das Fazit

Das Paper behauptet, dass Large Language Models (LLMs) großartig darin sind, zu raten, aber Schwierigkeiten bekommen, wenn sie einfach nur mehr Daten erhalten. Sie benötigen reichhaltiges, strukturiertes Feedback, das ihnen genau sagt, wo und warum sie falsch liegen.

Indem man den Lernprozess wie ein Spiel „Heiß oder Kalt“ mit einem strengen Lehrer gestaltet, der auf spezifische Fehler hinweist (und diese Fehler gruppiert), und indem man dem Modell die Chance gibt, über sich selbst zu reflektieren und seine Arbeit zu reparieren, können wir es lehren, komplexe symbolische Rätsel zu lösen, die es zuvor nicht bewältigen konnte.

Kurz gesagt: Gib dem Schüler nicht einfach nur mehr Hausaufgaben; gib ihm einen Lehrer, der seine spezifischen Fehler markiert, die Logik erklärt und ihn immer wieder versuchen lässt, bis er es richtig gemacht hat.

Technisches Resümee: Counterexample Guided Learning in the Large durch Reasoning Agents

Problemstellung

Die Arbeit befasst sich mit der Herausforderung, Large Language Models (LLMs) und Agenten zu befähigen, effektiv aus Feedback zu lernen und sich von diesem anpassen zu können. Während Feedback entscheidend für Coding-Agenten, Tool-Nutzer und personalisierte Assistenten ist, gestaltet sich die Messung und Verbesserung der Fähigkeit eines Modells, Feedback zu nutzen, aufgrund der Heterogenität, Domänenspezifität und mangelnden Kontrollierbarkeit typischer Feedback-Mechanismen als schwierig.

Um ein kontrollierbares Testfeld für diese Fähigkeit zu schaffen, konzentrieren sich die Autoren auf die Reguläre-Ausdrücke-Induktion (regex induction). Dies ist ein klassisches symbolisches Lernproblem, bei dem das Ziel darin besteht, einen regulären Ausdruck (die Zielsprache $L^\star$ ) aus einer Menge gelabelter Strings (positiver und negativer Beispiele) abzuleiten. Die Aufgabe ist inhärent anspruchsvoll, da viele Kandidaten-Ausdrücke eine kleine Menge an Beispielen passen können, was zu einem Overfitting auf oberflächliche Muster führt. Die Autoren rahmen dies als ein Oracle-geführtes symbolisches Generierungsproblem ein, bei dem ein LLM (der Lernende) seinen Hypothesen-Entwurf iterativ basierend auf Feedback von einem Verifizierer (dem Lehrer) in Form von Gegenbeispielen (Counterexamples) verfeinert.

Methodik

Das vorgeschlagene Framework integriert LLMs in einen Lehrer-Lerner-Zyklus, der durch agentische Workflows verstärkt wird. Das System operiert durch die folgenden Komponenten:

1. Iteratives Lehrer-Lerner-Framework

Lerner: Ein LLM schlägt einen Kandidaten-Regulären-Ausdruck basierend auf der aktuellen Menge gelabelter Beispiele vor.
Lehrer: Ein Verifizierer prüft den Kandidaten gegen die Zielsprache. Da die Äquivalenz regulärer Sprachen entscheidbar ist, konstruiert der Lehrer die symmetrische Differenz $L(\hat{r}) \triangle L^\star$ zwischen dem Kandidaten und der Zielsprache.
Feedback: Wenn der Kandidat inkorrekt ist, gibt der Lehrer Gegenbeispiele (Strings, die in der Zielsprache sein sollten, aber nicht enthalten sind, oder umgekehrt) zurück. Diese werden für die nächste Runde zum Trainingssatz hinzugefügt.

2. Synthese und Clustering von Gegenbeispielen

Um die potenziell unendliche Anzahl an Gegenbeispielen zu bewältigen (insbesondere jene, die aus Kleene-Sternen/Schleifen resultieren), führen die Autoren Clustered Counterexamples ein:

Anstatt einzelne Strings zurückzugeben, analysiert der Lehrer den minimierten Differenz-Automaten.
Er gruppiert ausgehende Symbole von einem Zustand, die zum selben Zielzustand führen, zu "Super-Zeichen" (z. B. die Repräsentation von $\{A, \dots, Z, a, \dots, z\}$ als $[A-Za-z]$).
Ein Clustered Counterexample ist ein Pfad in diesem Automaten unter Verwendung dieser Super-Zeichen, der eine Menge konkreter Strings repräsentiert, die dieselbe Fehlermode teilen. Dies bietet eine systematischere und weniger redundante Sicht auf die Fehlerregion.

3. Agentischer Workflow

Das Framework hebt den Standard-Lehrer-Lerner-Zyklus in einen agentischen Workflow mit zwei Schleifen:

Äußere Schleife (Reflexion): Das LLM wird angewiesen, über frühere Versuche zu reflektieren. Es erhält die vorherige Hypothese, seinen Reasoning-Trace und neue Gegenbeispiele. Das Modell wird instruiert, zu erklären, was fehlgeschlagen ist und wie die Hypothese zu revidieren ist.
Innere Schleife (Reparatur): Um Konsistenz zu gewährleisten, nutzt das System eine Reparatur-Schleife. Es fragt das LLM wiederholt ab, um Kandidaten zu generieren, die folgendes erfüllen:
1. Syntax-Check: Der reguläre Ausdruck muss syntaktisch valide sein.
2. Satisfaktions-Check: Der reguläre Ausdruck muss alle akkumulierten Gegenbeispiele korrekt labeln.
- Eine RepairScore-Funktion evaluiert Kandidaten basierend auf dem Kompilierungserfolg und dem Anteil der falsch klassifizierten Beispiele, wobei der beste Kandidat aus mehreren Versuchen ausgewählt wird.

4. Regularisierung

Um zu verhindern, dass das LLM zu spezifische oder komplexe Ausdrücke generiert, die zwar den aktuellen Stichproben-Satz passen, aber generalisiert scheitern, setzt das System Prompt-basierte Regularisierung ein. Dies beinhaltet Beschränkungen bezüglich der maximalen Ausdruckslänge, der Verschachtelungstiefe von Operatoren und eines Bias hin zu einfacheren Hypothesen.

Zentrale Beiträge

Oracle-Guided Formulation: Die Arbeit formuliert die LLM-basierte Regex-Induktion als iteratives symbolisches Lernproblem, bei dem Hypothesen durch Gegenbeispiel-Feedback verfeinert werden, wodurch die Lücke zwischen traditioneller Programmsynthese (CEGIS) und moderner LLM-Inferenz geschlossen wird.
Aktive Lernmethodik: Sie führt Techniken für den Aufbau effektiver LLM-basierter aktiver Lerner ein, insbesondere das symbolische Clustering von Gegenbeispielen und die Regularisierung, um einfachere, plausiblere Hypothesen zu priorisieren.
Agentischer Workflow: Die Autoren entwickeln einen neuartigen agentischen Workflow, der Reflexion (zur Extraktion struktureller Implikationen von Fehlern) und iterative Reparatur-Schleifen nutzt, um fehlgeschlagene Hypothesen zu revidieren, und damit über die einfache promptgesteuerte Generierung hinausgeht.
Strenge Evaluierung: Die Studie liefert eine umfassende Evaluierung über zwei Datensätze (Simple und Extended Regex) sowie über mehrere Backbone-Modelle hinweg und analysiert die Leistungsdynamik, die Stichprobeneffizienz und die Auswirkungen spezifischer Komponenten.

Ergebnisse

Die Autoren evaluierten ihr Framework auf zwei Datensätzen: Simple Regex (Standard-Operatoren über $\{a, b, c\}$ ) und Extended Regex (unterstützt Schnittmenge, Negation und komplexe Quantifikatoren).

Leistungssteigerungen: Bei den schwierigsten Aufgaben (hohe StarDepth) übertraf das Gegenbeispiel-gesteuerte Framework das Standard-Prompting signifikant.
- Bei Simple Regex (StarDepth 4) verbesserte sich die Erfolgsrate von 3,2 % (Standard) auf 38,1 % (Agentic).
- Bei Extended Regex (StarDepth 2) verbesserte sich die Erfolgsrate von 38,9 % (Standard) auf 74,1 % (Agentic).
Stichprobeneffizienz: Das Gegenbeispiel-gesteuerte Lernen reduzierte die Anzahl der benötigten gelabelten Beispiele, um eine Zielgenauigkeit zu erreichen, im Vergleich zu Methoden, die zufällig gezogene Beispiele verwenden, erheblich.
Komponenten-Analyse:
- Clustered Counterexamples: Übertrafen konsistent die nicht-geclusterten (einzelne Strings) Gegenbeispiele, was darauf hindeutet, dass die Qualität und die systematische Abdeckung des Feedbacks wichtiger sind als das reine Volumen.
- Agentic vs. Single: Der vollständige agentische Workflow (mit Reflexion und Reparatur) übertraf konsistent Single-Inference-Ansätze, die dieselben Gegenbeispiele nutzten, wenngleich zu höheren Token-Kosten.
- Modell-Agnostik: Die Verbesserungen wurden über verschiedene Backbone-Modelle hinweg beobachtet (Qwen3, GPT-5.4 Varianten, GPT-oss), was darauf hindeutet, dass das Framework robust gegenüber der Modellwahl ist.
- Ablation: Während die Regularisierung half, frühes Overfitting zu verhindern, lieferte die Reparatur-Schleife die größten Leistungsgewinne. Die Reflexion trug zum Erfolg bei, war jedoch weniger kritisch als der Reparatur-Mechanismus.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass LLMs von reichhaltigem Feedback profitieren können, das über die bloße Behandlung als zusätzliche Daten hinausgeht. Indem Feedback als strukturiertes, iteratives Signal (Gegenbeispiele) statt als statische Trainingsdaten behandelt wird, können LLMs eine robuste, Verifizierer-gesteuerte Verfeinerung durchführen.

Die Autoren positionieren diese Arbeit als einen Schritt hin zu robusten Verifizierer-gesteuerten Methoden für die LLM-basierte Programmsynthese und das formale Reasoning. Sie argumentieren, dass Agenten in Domänen, in denen informative Fehler synthetisierbar sind (verifizierbare Domänen), über das bloße Anpassen an Beispiele hinausgehen und eine zuverlässige iterative Verfeinerung leisten können. Die Studie legt nahe, dass die Kombination aus symbolischer Verifizierung (Gegenbeispiele) und agentischem Reasoning (Reflexion/Reparatur) eine Synergie schafft, die es LLMs ermöglicht, komplexe symbolische Induktionstests zu lösen, an denen Standard-Prompting scheitert.