🤖 AI

Goedel-Code-Prover: Hierarchical Proof Search for Open State-of-the-Art Code Verification

Le papier présente Goedel-Code-Prover, un cadre de recherche de preuves hiérarchique pour Lean 4 qui utilise une décomposition structurée et un apprentissage par renforcement hybride pour atteindre un taux de succès de 62 % sur des tâches de vérification de code, surpassant ainsi les modèles neuronaux existants, y compris ceux beaucoup plus grands.

Auteurs originaux : Zenan Li (Mike), Ziran Yang (Mike), Deyuan (Mike), He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin

Publié 2026-03-23

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Zenan Li (Mike), Ziran Yang (Mike), Deyuan (Mike), He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin

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 Problème : Construire un château de cartes parfait

Imaginez que vous demandez à un grand expert en construction (une Intelligence Artificielle, ou IA) de construire un château de cartes. L'IA est très douée : elle peut empiler les cartes rapidement et créer des formes impressionnantes. C'est ce qu'elle fait aujourd'hui pour écrire du code informatique : elle génère des programmes qui semblent fonctionner.

Mais il y a un gros problème : si le vent souffle un tout petit peu (une erreur logique, un cas limite), tout s'effondre. Dans le monde du logiciel, surtout pour des choses vitales comme les freins d'une voiture ou le système bancaire, "ça semble marcher" ne suffit pas. Il faut une garantie absolue que le château ne s'effondrera jamais.

C'est là qu'intervient la vérification formelle. C'est comme demander à un architecte de prouver mathématiquement, carte par carte, que la structure est indestructible. Mais écrire ces preuves à la main est un cauchemar : c'est long, difficile et réservé à quelques experts.

🚀 La Solution : Gödel-Code-Prover (Le Chef de Chantier Intelligent)

Les chercheurs ont créé un nouvel IA, Gödel-Code-Prover, capable de faire ce travail de vérification toute seule. Mais au lieu d'essayer de résoudre le problème d'un seul coup (ce qui est trop dur), ils ont inventé une méthode en deux étapes, comme un chef de chantier qui décompose un projet géant en petites tâches gérables.

1. L'Analogie du "Démantèlement" (La Décomposition)

Imaginez que vous devez démonter un énorme robot complexe. Si vous essayez de le casser d'un seul coup, vous risquez de le briser ou de vous blesser.

L'approche classique (les autres IA) : Elles essaient de trouver la solution finale directement. C'est comme essayer de sauter d'un immeuble de 10 étages : souvent, ça rate.
L'approche de Gödel-Code-Prover : Elle agit comme un démantèlement intelligent. Avant même de toucher au robot, elle dit : "Attends, ce robot est trop gros. Découpons-le d'abord en 3 sous-robots. Ensuite, découpons ces sous-robots en pièces détachées."

Elle transforme un problème impossible en une liste de petits problèmes simples, comme si elle transformait un labyrinthe géant en une série de petits couloirs droits.

2. Le "Score de Confiance" (Le Critère de Décision)

Comment l'IA sait-elle si une façon de découper le problème est bonne ? C'est là que réside l'ingéniosité du papier. Ils ont créé un score magique (le "Decomposition Score").

Ce score vérifie deux choses, comme un inspecteur de chantier :

La logique (Est-ce que ça tient ?) : Si je découpe le problème ainsi, est-ce que les petites pièces, une fois assemblées, prouvent bien que le robot entier fonctionne ? (C'est la justification constructive).
La simplicité (Est-ce que c'est plus facile ?) : Est-ce que ces petites pièces sont vraiment plus simples à résoudre que le robot entier ? (C'est l'efficacité structurelle).

Si une proposition de découpe ne passe pas ce test, l'IA la rejette immédiatement et en essaie une autre. C'est comme un filtre qui ne laisse passer que les meilleures idées.

🎓 Comment l'IA a-t-elle appris ? (L'Entraînement Hybride)

Pour entraîner ce robot, les chercheurs ont utilisé une méthode très astucieuse, un peu comme un jeu vidéo avec deux modes :

Mode Apprentissage (Supervisé) : D'abord, on lui montre des milliers d'exemples de bons découpages et de bonnes preuves, faits par des humains ou d'autres IA très puissantes. C'est comme lui donner un manuel de cuisine.
Mode Exploration (Renforcement) : Ensuite, on le laisse jouer. Il essaie de découper des problèmes.
- S'il trouve une bonne découpe, il reçoit une récompense continue (un petit point de plus, comme un score dans un jeu).
- S'il réussit à prouver le petit problème final, il reçoit une récompense binaire (Gagné ! ou Perdu !).

Le défi était que les récompenses pour "découper" sont fines et continues, tandis que celles pour "prouver" sont brutales (tout ou rien). Les chercheurs ont créé un système hybride pour que l'IA n'oublie pas comment prouver pendant qu'elle apprend à découper.

🏆 Les Résultats : Un Petit Géant

Le résultat est bluffant.

Ils ont testé leur modèle (qui est "petit", avec 8 milliards de paramètres) sur 427 tâches de vérification de code.
Il a réussi 62 % des tâches.
Pour comparaison, les plus gros modèles du marché (qui sont 84 fois plus gros !) n'arrivaient pas à faire aussi bien.

C'est comme si un petit chien de berger, bien dressé, réussissait à gérer un troupeau de moutons mieux qu'un lion géant mais mal entraîné.

💡 En Résumé

Ce papier nous dit que pour vérifier que le code est sûr, il ne faut pas essayer de tout résoudre d'un coup. Il faut :

Décomposer le problème géant en petits morceaux gérables.
Utiliser un score intelligent pour s'assurer que chaque découpe est logique et utile.
Entraîner l'IA à faire les deux choses (découper et prouver) en même temps.

Grâce à cette méthode, nous nous rapprochons de l'objectif ultime : un monde où le logiciel est non seulement fonctionnel, mais mathématiquement prouvé comme sûr, sans avoir besoin d'une armée d'experts humains pour le vérifier.

1. Problématique : Le fossé entre génération de code et vérification formelle

Les modèles de langage (LLM) ont considérablement progressé dans la génération de code, mais ils peinent à garantir la correction formelle de leurs sorties. Bien que les agents de codage basés sur les LLM puissent générer des tests unitaires, ceux-ci ne suffisent pas à certifier l'absence d'erreurs logiques subtiles ou de violations de spécifications, en particulier dans des environnements critiques.

La vérification formelle, via des prouveurs de théorèmes interactifs (ITP) comme Lean 4, offre une solution rigoureuse en exigeant la construction de preuves vérifiables par machine. Cependant, l'automatisation de cette tâche pour la vérification de code (par opposition aux mathématiques pures) se heurte à trois défis majeurs que les méthodes actuelles ne parviennent pas à surmonter :

Décomposition non ancrée (Ungrounded decomposition) : Contrairement aux mathématiques, où les LLMs ont absorbé une vaste littérature de raisonnements informels, il n'existe pas de corpus naturel équivalent pour la correction des programmes. Les LLMs génèrent donc souvent des sous-objectifs (lemmes) sémantiquement invalides ou aussi complexes que l'objectif initial.
Prolifération conceptuelle (Concept proliferation) : Chaque programme introduit un univers conceptuel unique (nouveaux comportements de calcul, invariants de structures de données) qui ne peut pas être résolu par des bibliothèques de lemmes réutilisables (comme Mathlib en mathématiques).
Décalage de distribution des tactiques (Tactic distribution shift) : La vérification de code nécessite des tactiques spécifiques (réflexion computationnelle, solveurs SMT, induction sur des listes) très différentes des tactiques algébriques dominantes dans les preuves mathématiques. Les modèles entraînés sur des corpus mathématiques échouent souvent à utiliser ces outils correctement.

2. Méthodologie : Une recherche de preuve hiérarchique

L'article propose un cadre de recherche de preuve hiérarchique pour Lean 4, implémenté via un modèle unique nommé Goedel-Code-Prover-8B. L'approche repose sur une boucle « planification-preuve » divisée en deux étapes :

A. Décomposition Hiérarchique (Planification)

Au lieu d'essayer de prouver un théorème complexe en une seule passe, le modèle décompose récursivement l'objectif de vérification en une série de lemmes intermédiaires plus simples.

Objectif : Transformer un théorème global en sous-objectifs qui, une fois prouvés, entraînent la validité du théorème parent.
Critère de scoring (Décomposition Score) : C'est le cœur de la méthode. Une fonction de score $S$ $S$ évalue chaque proposition de décomposition selon deux axes :
1. Justification constructive : Les lemmes proposés doivent logiquement entraîner le théorème parent (vérifié par reconstruction de preuve) et survivre à une recherche de contre-exemples automatisée via Quickcheck.
2. Efficacité structurelle : La décomposition doit réduire la complexité. La complexité est mesurée par l'empreinte d'opérateurs (nombre d'opérateurs logiques et de programme dans l'arbre de syntaxe abstraite). Le score favorise les décompositions qui réduisent significativement cette empreinte.

B. Complétion de Lemmes (Preuve)

Une fois les lemmes décomposés (les « feuilles » de l'arbre), le même modèle tente de les prouver individuellement en générant des tactiques Lean 4.

Ce processus est itératif : le modèle génère une tactique, reçoit les erreurs de compilation du noyau Lean, et affine sa preuve jusqu'à succès ou épuisement du budget.

C. Apprentissage Hybride (Entraînement)

Pour entraîner un modèle unique capable à la fois de décomposer et de prouver, les auteurs utilisent une approche de Reinforcement Learning (RL) hybride après une initialisation supervisée (SFT) :

Décomposition : Optimisée via GRPO (Group Relative Policy Optimization) utilisant le score de décomposition continu comme récompense dense. Cela permet d'explorer efficacement l'espace de recherche.
Complétion : Stabilisée par un rejeu supervisé (supervised replay) de trajectoires de preuve de haute qualité. Cela évite le problème de la récompense binaire et sparse (succès/échec) qui bloquerait l'apprentissage de la complétion si elle était optimisée uniquement par RL.

3. Contributions Clés

Cadre de recherche hiérarchique : Une architecture qui sépare la planification (décomposition de lemmes) de l'exécution (génération de tactiques), adaptée spécifiquement aux défis de la vérification de code.
Score de décomposition unifié : Une métrique combinant justification logique et réduction structurelle, utilisée de manière cohérente comme récompense d'entraînement et critère de classement lors de l'inférence, assurant une alignement strict entre l'optimisation et le déploiement.
Pipeline d'apprentissage hybride : Une méthode novatrice pour entraîner un seul modèle à gérer deux tâches aux signaux de récompense hétérogènes (continu pour la décomposition, binaire pour la preuve).
Performance à petite échelle : Démonstration qu'un modèle de 8 milliards de paramètres (Goedel-Code-Prover-8B), spécifiquement entraîné, surpasse des modèles de pointe beaucoup plus grands (jusqu'à 84 fois plus volumineux, comme DeepSeek-Prover-671B).

4. Résultats Expérimentaux

Les auteurs ont évalué leur approche sur trois benchmarks Lean 4 totalisant 427 tâches : Verina, Clever et AlgoVeri.

Taux de réussite global : Le modèle atteint un taux de réussite de 62,0 % sur l'ensemble des tâches.
Comparaison avec l'état de l'art :
- C'est une amélioration de 2,6 fois par rapport à la meilleure base de référence (neural prover ou modèle de raisonnement frontalier).
- Il surpasse des prouveurs neuronaux jusqu'à 84 fois plus grands (ex: DeepSeek-Prover-V2-671B).
- Les modèles de raisonnement frontaliers (GPT-5.3, Claude-Opus) obtiennent des taux bien inférieurs (< 24 %), confirmant que la génération en une seule passe est insuffisante.
Évolutivité à l'inférence (Scaling) : Les performances augmentent de manière monotone avec le nombre d'itérations de recherche et le budget d'échantillonnage parallèle (pass@k), indiquant un potentiel de mise à l'échelle non saturé.
Complexité des preuves : Les preuves validées comportent en moyenne 8 à 17 lemmes décomposés et plus de 130 lignes de code, prouvant la capacité du système à maintenir un raisonnement structuré profond.

5. Signification et Impact

Ce travail marque une avancée significative dans l'automatisation de la vérification formelle du code. Il démontre que :

La décomposition hiérarchique est essentielle pour combler le fossé entre les mathématiques formelles et la vérification de logiciels, où les bibliothèques de lemmes préexistantes font défaut.
Un score de décomposition principiel peut guider efficacement la recherche d'arbre, servant de pont entre l'apprentissage par renforcement et la recherche heuristique.
Il n'est pas nécessaire d'avoir des modèles massifs pour réussir la vérification formelle ; une spécialisation ciblée (entraînement sur la décomposition et la complétion de code) d'un modèle de taille moyenne (8B) est plus efficace que des modèles génériques géants.

En conclusion, Goedel-Code-Prover établit un nouvel état de l'art pour la vérification de code assistée par IA, offrant une voie prometteuse pour rendre les logiciels critiques plus sûrs et vérifiables de manière automatisée.