🤖 machine learning

Counterexample Guided Learning in the Large using Reasoning Agents

Cet article démontre que doter les agents de LLM de stratégies d'apprentissage guidées par des contre-exemples, où un vérificateur fournit un retour spécifique sur les candidats d'expressions régulières incorrects, améliore considérablement l'efficacité de l'échantillonnage et les taux de réussite dans les tâches complexes d'induction symbolique par rapport au prompting standard.

Auteurs originaux : Hongyi Liu, Frederic Sala, Thomas Reps, Adithya Murali

Publié 2026-06-11

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Hongyi Liu, Frederic Sala, Thomas Reps, Adithya Murali

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'enseigner à un robot très intelligent, mais légèrement confus, comment trier un tas de jouets mélangés. Vous voulez que le robot apprenne une règle spécifique, comme : « Garde tous les blocs rouges et les voitures bleues, mais jette tout le reste. »

Par le passé, vous auriez simplement montré au robot quelques exemples : « Voici un bloc rouge (garde-le), voici une voiture bleue (garde-la), voici une balle verte (jette-la). » Le robot devinerait une règle. S'il se trompait, vous lui montriez simplement plus d'exemples. C'est ce qu'on appelle le prompting standard : vous fournissez des données en continu, en espérant que le robot finira par comprendre.

Ce document présente une façon plus intelligente d'enseigner au robot, appelée Apprentissage Guidé par Contre-exemple (Counterexample-Guided Learning). Au lieu de simplement lui montrer plus d'exemples aléatoires, le robot reçoit un « enseignant » qui agit comme un correcteur rigoureux.

L'idée centrale : l'enseignant « Correcteur »

Voici comment fonctionne la nouvelle méthode, en utilisant une analogie simple :

La supposition : Le robot (l'« Apprenant ») examine les exemples que vous lui avez donnés et rédige une règle (une « Expression Régulière », qui est juste une façon sophistiquée de dire « description de motif »).
La vérification : Un « Enseignant » (un programme informatique qui connaît la règle réelle correcte) vérifie la règle du robot.
Le contre-exemple (le « Piège ! ») : Si la règle du robot est fausse, l'Enseignant ne se contente pas de dire « Non ». Il trouve un jouet spécifique que le robot a mal traité.
- Exemple : La règle du robot dit « Garde tout ce qui est rouge ». L'Enseignant trouve une balle rouge qui devrait être jetée selon la vraie règle. L'Enseignant tend cette balle rouge au robot et lui dit : « Regarde ! Tu as gardé ceci, mais tu ne devrais pas. Corrige ta règle. »
- Cette erreur spécifique est appelée un Contre-exemple. C'est une preuve directe de la raison pour laquelle cette supposition a échoué.

Le secret : les erreurs « Groupées »

Les auteurs ont découvert que parfois, le robot fait le même type d'erreur de manière répétée. Si la règle est « Garder toutes les lettres », et que le robot oublie la lettre « Z », l'Enseignant pourrait lui montrer « Z », « A », « B », « C »... tout cela en même temps. C'est trop de bruit.

Ainsi, ils ont inventé les Contre-exemples Groupés (Clustered Counterexamples). Au lieu de montrer au robot 26 lettres différentes qui sont fausses, l'Enseignant dit : « Tu as oublié toute la catégorie des Lettres ». Il regroupe les erreurs similaires en un seul indice puissant. Cela aide le robot à comprendre la logique de son erreur plutôt que de simplement mémoriser une liste de mauvais exemples.

Le flux de travail de l'« Agent » : Réflexion et Réparation

Le document donne également au robot un « cerveau » capable de réfléchir à sa propre pensée. C'est ce qu'on appelle un Flux de Travail Agentique (Agentic Workflow). Cela se déroule en deux boucles :

Réflexion (La « Pause et Réflexion ») : Après que l'Enseignant a signalé une erreur, on demande au robot de s'arrêter et d'expliquer pourquoi il a fait cette erreur. « Oh, je pensais que "rouge" signifiait "tout ce qui est rouge", mais la règle était en fait "blocs rouges uniquement". » Cela aide le robot à apprendre la logique, pas seulement la réponse.
Boucle de Réparation (Le « Nouveau essai ») : Si la nouvelle règle du robot contient toujours une erreur de syntaxe (comme une faute de frappe) ou si elle se trompe encore sur un exemple, le système n'abandonne pas. Il renvoie le robot à la planche à dessin avec une note spécifique : « Ta règle contient une faute de frappe ici, et tu as encore raté cette balle rouge. Réessaie. » Le robot continue d'essayer jusqu'à ce qu'il réussisse.

Ce qu'ils ont trouvé

Les chercheurs ont testé cela sur deux types de tâches de « tri de jouets » :

Règles simples : Motifs basiques (comme « blocs rouges »).
Règles complexes : Motifs délicats avec beaucoup de conditions imbriquées (comme « blocs rouges qui sont aussi carrés, mais pas s'ils sont brillants »).

Les résultats :

L'enseignement standard (montrer simplement des exemples) a échoué lamentablement sur les règles complexes. Le robot restait bloqué sur de mauvaises suppositions de motifs.
L'enseignement par contre-exemple (utiliser le feedback du type « Piège ! ») a rendu le robot bien meilleur. Il a eu besoin de beaucoup moins d'exemples pour apprendre les règles complexes.
La méthode « Agent » (Réflexion + Réparation) a été la grande gagnante. Sur les tâches les plus difficiles, le taux de réussite est passé d'un minuscule 3,2 % (avec l'enseignement standard) à 38,1 %. Sur un autre ensemble de tâches difficiles, il est passé de 38,9 % à 74,1 %.

L'essentiel

Le document affirme que les Grands Modèles de Langage (LLM) sont excellents pour deviner, mais qu'ils ont du mal lorsqu'ils reçoivent simplement plus de données. Ils ont besoin d'un feedback riche et structuré qui leur indique précisément où et pourquoi ils se trompent.

En traitant le processus d'apprentissage comme un jeu de « Chaud ou Froid » avec un enseignant strict qui pointe des erreurs spécifiques (et qui regroupe ces erreurs ensemble), et en donnant au modèle la possibilité de réfléchir et de réparer son propre travail, nous pouvons lui apprendre à résoudre des puzzles symboliques complexes qu'il ne pouvait pas gérer auparavant.

En bref : Ne donnez pas seulement plus de devoirs à l'élève ; donnez-lui un enseignant qui marque ses erreurs spécifiques, explique la logique et lui permet de réessayer jusqu'à ce qu'il réussisse.

Résumé Technique : Apprentissage guidé par contre-exemple à grande échelle via des agents de raisonnement

Énoncé du Problème

Le papier traite du défi consistant à permettre aux grands modèles de langage (LLM) et aux agents d'apprendre et de s'adapter efficacement à partir de retours (feedback). Bien que le feedback soit crucial pour les agents de codage, les utilisateurs d'outils et les assistants personnalisés, mesurer et améliorer la capacité d'un modèle à utiliser le feedback est difficile en raison de l'hétérogénéité, de la spécificité des domaines et du manque de contrôlabilité des mécanismes de feedback typiques.

Pour créer un banc d'essai contrôlable pour cette capacité, les auteurs se concentrent sur l'induction d'expressions régulières (regex). Il s'agit d'un problème classique d'apprentissage symbolique où l'objectif est d'inférer une expression régulière (le langage cible $L^\star$ ) à partir d'un ensemble de chaînes étiquetées (exemples positifs et négatifs). La tâche est intrinsèquement difficile car de nombreuses expressions candidates peuvent correspondre à un petit ensemble d'exemples, ce qui conduit au surapprentissage (overfitting) de motifs superficiels. Les auteurs cadrent cela comme un problème de génération symbolique guidé par un oracle, où un LLM (l'apprenant) affine de manière itérative son hypothèse sur la base du feedback d'un vérificateur (l'enseignant) sous la forme de contre-exemples.

Méthodologie

Le cadre proposé intègre les LLM dans une boucle enseignant-apprenant, améliorée par des flux de travail agentiques. Le système fonctionne via les composants suivants :

1. Cadre itératif Enseignant-Apprenant

Apprenant : Un LLM propose une expression régulière candidate basée sur l'ensemble actuel d'exemples étiquetés.
Enseignant : Un vérificateur vérifie la candidate par rapport au langage cible. Puisque l'équivalence des langages réguliers est décidable, l'enseignant construit la différence symétrique $L(\hat{r}) \triangle L^\star$ entre la candidate et la cible.
Feedback : Si la candidate est incorrecte, l'enseignant renvoie des contre-exemples (chaînes qui devraient être dans la cible mais ne le sont pas, ou inversement). Ceux-ci sont ajoutés à l'ensemble d'entraînement pour le tour suivant.

2. Synthèse et Regroupement de Contre-exemples

Pour gérer le nombre potentiellement infini de contre-exemples (notamment ceux provenant des étoiles de Kleene/boucles), les auteurs introduisent des Contre-exemples Regroupés (Clustered Counterexamples) :

Au lieu de renvoyer des chaînes individuelles, l'enseignant analyse l'automate de différence minimisé.
Il regroupe les symboles sortants d'un état menant au même état de destination en "super-caractères" (par exemple, représentant $\{A, \dots, Z, a, \dots, z\}$ comme $[A-Za-z]$).
Un contre-exemple regroupé est un chemin dans cet automate utilisant ces super-caractères, représentant un ensemble de chaînes concrètes partageant le même mode de défaillance. Cela fournit une vue plus systématique et moins redondante de la région d'erreur.

3. Flux de Travail Agentique (Agentic Workflow)

Le cadre élève la boucle enseignant-apprenant standard en un flux de travail agentique comprenant deux boucles :

Boucle Extérieure (Réflexion) : Le LLM est incité à réfléchir sur les tentatives précédentes. Il reçoit l'hypothèse précédente, sa trace de raisonnement et les nouveaux contre- exemples. Le modèle est instruit d'expliquer ce qui a échoué et comment réviser l'hypothèse.
Boucle Intérieure (Réparation) : Pour garantir la cohérence, le système emploie une boucle de réparation. Il interroge de manière répétée le LLM pour générer des candidates qui satisfont :
1. Vérification de Syntaxe : La regex doit être syntaxiquement valide.
2. Vérification de Satisfaction : La regex doit étiqueter correctement tous les contre-exemples accumulés.
- Une fonction RepairScore évalue les candidates basées sur le succès de la compilation et la fraction d'exemples mal classés, sélectionnant la meilleure candidate parmi plusieurs tentatives.

4. Régularisation

Pour empêcher le LLM de générer des expressions trop spécifiques ou complexes qui s'adaptent à l'ensemble d'exemples actuel mais échouent de manière générale, le système emploie une régularisation au niveau du prompt. Cela inclut des contraintes sur la longueur maximale de l'expression, la profondeur d'imbrication des opérateurs et un biais vers des hypothèses plus simples.

Contributions Clés

Formulation Guidée par Oracle : Le papier formule l'induction de regex basée sur les LLM comme un problème d'apprentissage symbolique itératif où les hypothèses sont affinées via un feedback de contre-exemples, comblant le fossé entre la synthèse de programme traditionnelle (CEGIS) et l'inférence moderne des LLM.
Méthodologie d'Apprentissage Actif : Il introduit des techniques pour construire des apprenants actifs efficaces basés sur les LLM, spécifiquement le regroupement symbolique de contre-exemples et la régularisation pour prioriser des hypothèses plus simples et plus plausibles.
Flux de Travail Agentique : Les auteurs développent un nouveau cadre agentique utilisant la réflexion (pour extraire les implications structurelles des erreurs) et des boucles de réparation itératives pour réviser les hypothèses échouées, allant au-delà de la simple génération pilotée par prompt.
Évaluation Rigoureuse : L'étude fournit une évaluation complète à travers deux jeux de données (Simple Regex et Extended Regex) et plusieurs modèles de base, analysant la dynamique de performance, l'efficacité de l'échantillonnage et l'impact de composants spécifiques.

Résultats

Les auteurs ont évalué leur cadre sur deux jeux de données : Simple Regex (opérateurs standards sur $\{a, b, c\}$ ) et Extended Regex (supportant l'intersection, la négation et les quantificateurs complexes).

Gains de Performance : Sur les tâches les plus difficiles (StarDepth élevé), le cadre guidé par contre-exemples surpasse significativement le prompting standard.
- Sur Simple Regex (StarDepth 4), les taux de réussite sont passés de 3,2 % (Standard) à 38,1 % (Agentic).
- Sur Extended Regex (StarDepth 2), les taux de réussite sont passés de 38,9 % (Standard) à 74,1 % (Agentic).
Efficacité de l'Échantillonnage : L'apprentissage guidé par contre-exemples réduit considérablement le nombre d'exemples étiquetés nécessaires pour atteindre une précision cible par rapport aux méthodes utilisant des exemples échantillonnés aléatoirement.
Analyse des Composants :
- Contre-exemples Regroupés : Ont systématiquement surpassé les contre-exemples non regroupés (chaînes individuelles), indiquant que la qualité et la couverture systématique du feedback comptent plus que le simple volume.
- Agentic vs Single : Le flux de travail agentique complet (avec réflexion et réparation) surpasse systématiquement les approches d'inférence unique utilisant les mêmes contre-exemples, bien qu'au coût de jetons (tokens) plus élevé.
- Agnosticisme du Modèle : Les améliorations ont été observées sur divers modèles de base (variantes de Qwen3, GPT-5.4, GPT-oss), suggérant que le cadre est robuste au choix du modèle.
- Ablation : Bien que la régularisation aide à prévenir le surapprentissage précoce, la boucle de réparation a fourni les gains de performance les plus importants. La réflexion a contribué au succès mais était moins critique que le mécanisme de réparation. L'analyse montre que la réflexion contribue au succès mais est moins critique que le mécanisme de réparation.

Signification et Revendications

Le papier affirme que les LLM peuvent bénéficier d'un feedback riche au-delà du simple traitement du feedback comme donnée supplémentaire. En traitant le feedback comme un signal structuré et itératif (contre-exemples) plutôt que comme des données d'entraînement statiques, les LLM peuvent s'engager dans un raffinement robuste guidé par un vérificateur.

Les auteurs positionnent ce travail comme une étape vers des méthodes de synthèse de programmes et de raisonnement formel basées sur les LLM et guidées par des vérificateurs robustes. Ils soutiennent que dans les domaines où les écheurs informatifs peuvent être synthétisés (domaines vérifiables), les agents peuvent aller au-delà de la simple adaptation d'exemples pour effectuer un raffinement itératif fiable. L'étude suggère que la combinaison de la vérification symbolique (contre-exemples) et du raisonnement agentique (réflexion/réparation) crée une synergie qui permet aux LLM de résoudre des tâches d'induction symbolique complexes là où le prompting standard échoue.