💬 NLP

Scaling Agentic Verifier for Competitive Coding

L'article présente l'Agentic Verifier, un agent basé sur l'exécution qui génère activement des entrées de test discriminantes par le biais d'un raisonnement multi-tours et de l'apprentissage par renforcement afin d'améliorer significativement la précision des grands modèles de langage en programmation compétitive en identifiant et en filtrant efficacement les solutions candidates incorrectes.

Auteurs originaux : Zeyao Ma, Jing Zhang, Xiaokang Zhang, Jiaxi Yang, Zongmeng Zhang, Jiajun Zhang, Yuheng Jing, Lei Zhang, Hao Zheng, Wenting Zhao, Junyang Lin, Binyuan Hui

Publié 2026-02-05

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Zeyao Ma, Jing Zhang, Xiaokang Zhang, Jiaxi Yang, Zongmeng Zhang, Jiajun Zhang, Yuheng Jing, Lei Zhang, Hao Zheng, Wenting Zhao, Junyang Lin, Binyuan Hui

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

Le gros problème : Le jeu de devinettes du « coup unique »

Imaginez que vous êtes un chef génie (un Grand Modèle de Langage) essayant de recréer un plat complexe à partir d'une description de recette. Parfois, vous réussissez parfaitement du premier coup. Mais souvent, vous pouvez manquer un détail subtil, comme utiliser du sel au lieu du sucre, ou oublier une étape.

Dans le monde de la programmation compétitive (résoudre des énigmes logiques complexes avec du code), même les chefs IA les plus intelligents peinent à obtenir la bonne réponse à 100 % en une seule tentative.

Pour corriger cela, les chercheurs demandent généralement à l'IA de cuisiner le plat 64 fois (en générant 64 solutions différentes) puis de choisir la meilleure. Mais comment savoir laquelle est réellement bonne si vous n'avez pas le « corrigé officiel » sous la main ?

L'ancienne méthode : Jeter des fléchettes à l'aveugle

La méthode traditionnelle pour vérifier ces 64 solutions s'appelle la Vérification par Exécution (Execution-Based Verification). Vous prenez les 64 recettes de code et vous les testez contre des ingrédients de test (entrées).

Le défaut : L'ancienne méthode consistait à lancer des fléchettes sur un immense mur d'ingrédients possibles pour voir lesquels révèlent une erreur. Elle choisissait simplement des ingrédients au hasard (par exemple : « Et si le nombre est 5 ? », « Et si c'est 100 ? »).
Le résultat : La plupart de ces ingrédients aléatoires sont trop faciles. Ils ne détectent pas les erreurs subtiles. Vous pourriez exécuter 64 tests, et les 64 mauvaises solutions pourraient encore paraître parfaites parce qu'aucun des tests n'était assez difficile pour exposer leurs erreurs. C'est comme essayer de trouver une fissure dans un diamant en tapotant avec une plume ; il vous faut un marteau.

La nouvelle solution : Le « Chef Détective » (Vérificateur Agentique)

Les auteurs de ce papier ont construit un nouvel outil appelé le Vérificateur Agentique (Agentic Verifier). Ne voyez pas cela comme un lanceur de fléchettes aléatoire, mais comme un détective super intelligent ou un critique culinaire exigeant.

Au lieu de deviner des ingrédients au hasard, ce détective :

Examine deux solutions différentes côte à côte.
Réfléchit profondément à leur fonctionnement.
Traque activement l'ingrédient spécifique qui fera que les deux solutions se comporteront différemment.

Si la Solution A dit « La réponse est 10 » et la Solution B dit « La réponse est 12 », le détective ne choisit pas un nombre au hasard. Il demande : « Quel est l'input spécifique qui forcera la Solution A à planter ou à donner une mauvaise réponse alors que la Solution B reste correcte ? » Il continue de poser des questions et de tester jusqu'à ce qu'il trouve cet « élément de preuve » (smoking gun).

Comment ils ont entraîné le détective

On ne peut pas simplement dire à un ordinateur d'être « intelligent ». Il faut l'entraîner. Les auteurs ont utilisé un camp d'entraînement en trois étapes :

Synthèse de données (La cuisine d'entraînement) : Ils ont créé des milliers de faux problèmes de cuisine et des paires de solutions « bonnes » et « mauvaises ».
Affinage par rejet (Le tour d'élimination) : Ils ont laissé l'IA essayer de trouver les ingrédients difficiles. Si elle échouait à trouver une différence, cette tentative était jetée à la poubelle. Seules les tentatives réussies ont été conservées pour enseigner à l'IA ce qu'est un « bon travail de détective ».
Apprentissage par renforcement agentique (Le championnat) : Ils ont donné un système de récompense à l'IA. Si elle trouvait un input qui exposait une différence entre deux solutions, elle gagnait un point. Si elle échouait, elle recevait une pénalité. Au fil du temps, l'IA a appris à devenir incroyablement efficace pour trouver ces « éléments de preuve ».

Les résultats : Des tests plus intelligents, de meilleurs gagnants

Lorsqu'ils ont testé ce nouveau « Chef Détective » contre l'ancien « Lanceur de fléchettes aléatoire » :

Efficacité : Le détective a trouvé les erreurs beaucoup plus rapidement. Il n'avait pas besoin d'exécuter des centaines de tests ; il a trouvé le bon test à exécuter.
Précision : Sur les énigmes difficiles (comme celles des compétitions USACO ou ICPC), la nouvelle méthode a amélioré le taux de réussite de l'IA de 10 à 15 %. C'est un bond massif dans ce domaine.
Passage à l'échelle (Scaling) : Plus on donnait de « temps de réflexion » et d'inputs de test au détective, meilleur il devenait. Il n'a pas atteint de limite comme les anciennes méthodes.

Une découverte bonus : L'« arbitre imparfait »

Le papier a également découvert quelque chose d'intéressant sur les compétitions elles-mêmes. Les cas de test officiels utilisés par ces compétitions sont en réalité imparfaits.

Parfois, une solution est techniquement « fausse » (elle échoue sur des inputs que la compétition n'a pas testés), mais elle réussit les tests officiels et obtient une médaille d'or. Le Vérificateur Agentique agit comme un porteur de vérité capable de trouver ces « faux gagnants » en générant de nouveaux tests difficiles que les juges officiels ont manqués. Cela montre que même les « corrigés » de ces compétitions ne sont pas parfaits, et que ce nouvel outil peut aider à trouver le code réellement correct.

Résumé

En bref, le papier dit : « Arrêtez de deviner des cas de test aléatoires pour vérifier le code de l'IA. À la place, entraînez un détective IA à traquer activement les tests spécifiques et difficiles qui révèlent la vérité. Cela rend la recherche du meilleur code beaucoup plus rapide et beaucoup plus précise. »

Résumé Technique : Mise à l'échelle d'un Vérificateur Agentique pour la Programmation Compétitive

Énoncé du Problème

Bien que les grands modèles de langage (LLM) aient démontré de fortes capacités en synthèse de programmes, ils peinent fréquemment à résoudre correctement des problèmes de programmation compétitive en une seule tentative. Une stratégie courante pour améliorer la précision est le scaling au moment de l'inférence (test-time scaling), où plusieurs solutions candidates sont échantillonnées et un vérificateur sélectionne la meilleure.

Les méthodes de vérification existantes font face à des limitations significatives dans le contexte de la programmation compétitive :

Génération de cas de test complets : Générer des cas de test complets (entrées + sorties de vérité terrain) est souvent aussi difficile que de résoudre le problème original, ce qui est coûteux en termes de calcul et peu fiable.
Exécution par entrées uniquement : Les approches récentes génèrent uniquement des entrées valides et sélectionnent les solutions sur la base de l'accord des sorties (vote). Cependant, ces méthodes reposent généralement sur un échantillonnage d'entrées aléatoires.
Inefficacité de l'échantillonnage aléatoire : L'espace des entrées valides en programmation compétitive est vaste, mais seule une petite fraction est « discriminante » (c'est-à-dire capable d'exposer les différences de comportement entre les solutions correctes et incorrectes). Les expériences préliminaires de l'article démontrent que l'augmentation du nombre d'entrées aléatoires produit des rendements décroissants et ne parvient pas à combler l'écart de performance par rapport aux cas de test de vérité terrain.

Méthodologie : Vérificateur Agentique

Les auteurs proposent un Vérificateur Agentique, un agent basé sur un LLM conçu pour raisonner activement sur les comportements des programmes et rechercher des entrées de test hautement discriminantes qui exposent les divergences parmi les solutions candidates.

Mécanisme Central

Au lieu d'un échantillonnage aléatoire aveugle, le vérificateur s'engage dans une interaction multi-tours avec un environnement d'exécution de code :

Formulation de la tâche : Étant donné un problème $Q$ et une paire de solutions candidates $(C_a, C_b)$ , l'objectif de l'agent est de générer un programme générateur d'entrées $G$ qui produit une entrée $x$ telle que $Exec(C_a, x) \neq Exec(C_b, x)$ .
Boucle d'interaction : L'agent propose de manière itérative des entrées, exécute les solutions candidates, inspecte les retours (erreurs d'exécution, sorties) et affine ses hypothèses pour découvrir des contre-exemples.
Stratégie de sélection : Lors de l'inférence, le vérificateur entraîné génère des entrées de test ciblées pour des paires de solutions candidates. Ces entrées sont utilisées dans une stratégie de vote basée sur l'exécution pour sélectionner la solution finale.

Pipeline d'Entraînement

Le vérificateur est entraîné via un pipeline évolutif en trois étapes :

Synthèse de données à grande échelle : Les auteurs construisent un ensemble de données de problèmes de programmation compétitive avec des solutions étiquetées. Pour les problèmes dépourvus de cas de test de vérité terrain, ils synthétisent des suites de tests de haute qualité en utilisant un mécanisme de vote majoritaire fondé sur le consensus à travers plusieurs solutions de référence pour garantir la fiabilité.
Affinage par rejet (Rejection Fine-Tuning) : En utilisant un modèle enseignant puissant (Qwen3-235B), ils collectent des trajectoires d'interaction multi-tours réussies où l'agent génère avec succès des entrées distinctives. Le modèle de base est affiné sur ces trajectoires de haute qualité, en masquant les prompts initiaux et les retours pour apprendre des schémas d'interaction efficaces.
Apprentissage par Renforcement Agentique (RL) : Le vérificateur est optimisé davantage via GRPO (Group Relative Policy Optimization). La fonction de récompense est parcimonieuse et basée sur le résultat :
- $+1$ : Entrée valide qui distingue les deux solutions.
- $0$ : Entrée valide qui ne distingue pas (les solutions sont d'accord).
- $-1$ : Entrée invalide ou générateur vide.
  Le curriculum d'entraînement donne la priorité aux paires de « faux négatifs difficiles » où les entrées distinctives sont rares, encourageant l'agent à apprendre des comportements de génération ciblés.

Contributions Clés

Analyse Empirique : L'article démontre empiriquement que la génération d'entrées aléatoires est hautement inefficace pour la vérification basée sur l'exécution par entrées uniquement, révélant un écart de performance substantiel par rapport aux entrées de test discriminantes.
Vérificateur Agentique : Introduction d'un agent qui génère activement des entrées de test hautement discriminantes via une interaction multi-tours, dépassant le simple échantillonnage statique ou aléatoire.
Pipeline d'Entraînement Évolutif : Un nouveau pipeline combinant la synthèse de données, l'affinage par rejet et l'apprentissage par renforcement agentique pour entraîner le vérificateur.
Scaling au Moment de l'Inférence : Démonstration que la méthode proposée bénéficie continuellement de l'augmentation du calcul au moment de l'inférence, se mettant à l'échelle efficacement tant avec le nombre de solutions candidates qu'avec le nombre d'entrées générées.

Résultats Expérimentaux

L'approche a été évaluée sur cinq benchmarks de programmation compétitive (USACO, LiveCodeBench, OJBench, ICPC-Eval, et un nouveau benchmark CodeForces) en utilisant deux modèles de politique (Qwen3-30B et Qwen3-235B).

Gains de Performance : L'Agentic Verifier a systématiquement surpassé les bases solides, y compris la génération d'entrées aléatoires, les cas de test générés par modèle (CodeT, CodeRM) et la sélection basée sur un modèle de récompense.
- A obtenu des gains absolus de +10–15 % en précision Best@k par rapport aux bases solides basées sur l'exécution.
- Sur le sous-ensemble "Hard" d'OJBench, le vérificateur entraîné de 30B a amélioré les performances de +34,1 % par rapport à la base, surpassant de manière significative un modèle zero-shot de 235B.
Comportement de Mise à l'Échelle : Contrairement aux bases qui montraient une saturation précoce, l'Agentic Verifier a présenté un comportement clair de mise à l'échelle au moment de l'inférence, la performance s'améliorant régulièrement à mesure que le nombre d'entrées de test augmentait.
Zero-Shot vs Entraîné : Les LLM zero-shot ont apporté une certaine amélioration, mais le vérificateur entraîné spécifiquement pour la tâche a nettement mieux performé, même lorsque le modèle entraîné était 7 fois plus petit que son homologue zero-shot.

Signification et Revendications

L'article affirme que l'efficacité du vote basé sur l'exécution est déterminée principalement par la qualité discriminante des entrées de test plutôt que par leur simple quantité.

Au-delà de l'amélioration de la sélection Best-of-N, les auteurs soulignent une implication plus large : les suites de tests des benchmarks sont des vérificateurs imparfaits. Les suites de tests fixes ne couvrent qu'une partie limitée de l'espace des entrées valides, ce qui conduit à des faux positifs où des solutions incorrectes passent tous les tests du benchmark. L'Agentic Verifier peut exposer activement ces échecs en découvrant des contre-exemples ciblés. Ainsi, les auteurs positionnent le vérificateur non pas simplement comme un outil de réordonnancement, mais comme un mécanisme complémentaire de vérification de la correction qui peut étendre la couverture des entrées et atténuer le bruit induit par les benchmarks dans l'évaluation à grande échelle.