🤖 machine learning

Synthesis and Verification of Transformer Programs (Technical Report)

Ce papier présente de nouvelles techniques algorithmiques pour vérifier et apprendre automatiquement des programmes C-RASP — des constructions linguistiques qui capturent l'expressivité des transformateurs — en exploitant des liens avec la vérification de modèles Lustre et la recherche locale, permettant ainsi des applications dans l'optimisation de programmes de transformateurs et l'apprentissage contraint.

Auteurs originaux : Hongjian Jiang, Matthew Hague, Philipp Rümmer, Anthony Widjaja Lin

Publié 2026-05-19

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Hongjian Jiang, Matthew Hague, Philipp Rümmer, Anthony Widjaja Lin

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 possédiez un robot très intelligent et puissant (un « Transformer ») capable de lire des histoires, d'écrire des e-mails et de résoudre des énigmes. Ce robot est incroyablement compétent dans son travail, mais il est aussi un peu une « boîte noire ». Vous pouvez voir ce qu'il fait, mais vous ne pouvez pas facilement voir comment il pense ni prouver qu'il ne commettra jamais une erreur spécifique.

Ce papier présente une nouvelle méthode pour construire un plan pour ces robots. Au lieu d'essayer de comprendre directement le cerveau désordonné et complexe du robot, les auteurs ont créé un langage plus simple et plus clair appelé C-RASP. Considérez C-RASP comme un « manuel d'instructions simplifié » que le robot suit. Il est suffisamment simple pour que nous puissions le lire, le comprendre et vérifier ses erreurs, mais suffisamment puissant pour décrire exactement ce que fait le robot.

Voici la décomposition de leurs deux principales réalisations, expliquées avec des analogies du quotidien :

1. L'« Inspecteur de Sécurité » (Vérification)

Le Problème : Vous avez un manuel d'instructions C-RASP (un programme) et vous voulez savoir : « Ce programme fait-il toujours la bonne chose ? Accepte-t-il jamais un mauvais mot ou rejette-t-il un bon mot ? » Vérifier cela manuellement revient à essayer de lire un livre d'un million de pages pour trouver une seule faute de frappe : c'est presque impossible et parfois mathématiquement impossible d'être sûr à 100 %.

La Solution : Les auteurs ont construit un « Inspecteur de Sécurité ». Ils ont trouvé comment traduire ces manuels d'instructions C-RASP dans un langage différent et très strict appelé Lustre.

L'Analogie : Imaginez que vous avez une recette complexe écrite dans un cahier manuscrit et désordonné (C-RASP). Vous ne pouvez pas facilement vérifier si les calculs sont justes. Alors, vous traduisez cette recette désordonnée dans un format rigide et lisible par ordinateur (Lustre) qu'un robot ultra-rapide (un « Vérificateur de Modèle ») peut lire instantanément.
Le Résultat : Ce robot peut scanner instantanément la recette et dire : « Oui, c'est sûr », ou « Non, voici l'étape exacte où cela tourne mal ». Le papier montre que cela fonctionne incroyablement vite (en quelques secondes) par rapport à l'entraînement d'un nouveau robot IA, qui peut prendre des heures.

2. L'« Éditeur Automatique » (Synthèse)

Le Problème : Supposons que vous ayez une liste d'exemples (par exemple : « Ce sont de bonnes phrases, ce sont de mauvaises ») et que vous vouliez écrire un manuel d'instructions C-RASP qui les respecte. Vous n'avez pas encore le manuel ; vous devez l'inventer à partir de zéro.

La Solution : Les auteurs ont créé un « Éditeur Automatique » qui utilise une technique appelée Recuit Simulé.

L'Analogie : Imaginez que vous essayez de trouver la combinaison parfaite d'ingrédients pour un gâteau, mais que vous ne pouvez pas le goûter avant de l'avoir cuit.
1. Vous commencez avec une recette aléatoire et désordonnée.
2. Vous la cuisez et voyez si elle correspond à vos exemples.
3. Si elle est proche, vous apportez un tout petit changement (remplacez le sucre par du miel, ajoutez une pincée de sel).
4. Si le nouveau gâteau est meilleur, vous le gardez. S'il est pire, vous pourriez quand même le garder (au cas où cela mènerait à un meilleur gâteau plus tard), mais vous arrêtez progressivement de prendre des risques à mesure que vous vous rapprochez de la recette parfaite.
Le Résultat : Ce processus écrit automatiquement un programme C-RASP qui correspond parfaitement à vos exemples. C'est comme avoir un chef qui peut reconstituer une recette simplement en goûtant le plat final.

Pourquoi cela compte (selon le papier)

Les auteurs ont testé leurs outils sur diverses « énigmes » (comme vérifier si les parenthèses sont équilibrées ou compter des lettres).

Vitesse : Leurs outils ont résolu ces énigmes en quelques secondes.
Comparaison : Ils ont noté que si vous essayiez d'entraîner une IA standard (comme GPT-2) à apprendre ces mêmes énigmes à partir de zéro, cela pourrait prendre des heures et pourrait quand même ne pas aboutir au résultat correct.
Deux utilisations intéressantes :
1. Minimisation : Si vous avez un manuel d'instructions énorme et gonflé, leur outil peut le réduire à la version la plus petite et la plus simple qui fonctionne toujours.
2. Apprentissage Contraint : Si vous avez une idée partielle de ce que le programme devrait faire (une « spécification »), leur outil peut combler les lacunes pour s'assurer que le programme final respecte à la fois vos exemples et vos règles.

En résumé : Le papier nous offre un moyen de transformer la mystérieuse « boîte noire » de l'IA en un manuel d'instructions clair, vérifiable et modifiable, nous permettant de vérifier sa sécurité et d'en construire de nouveaux beaucoup plus rapidement qu'auparavant.

Résumé technique : Synthèse et vérification de programmes Transformer

Énoncé du problème

Les Transformers, l'architecture fondamentale des grands modèles de langage (LLM), sont notoirement difficiles à analyser formellement. Bien qu'ils soient expressifs et parallélisables, la vérification de leurs propriétés est indécidable, et leur extension avec les chaînes de pensée (Chain of Thoughts) les rend Turing-complets. Pour y remédier, des chercheurs ont développé des langages déclaratifs comme RASP (Restricted Access Sequence Processing Language) et sa variante C-RASP (Counting RASP) afin de capturer le comportement des transformers avec une sémantique précise.

Cependant, malgré le lien théorique entre C-RASP et les transformers, deux lacunes critiques subsistent :

Vérification : Il n'existe aucune méthode automatique pour vérifier les programmes C-RASP. Vérifier si un C-RASP reconnaît un langage trivial est indécidable dans le cas général, et aucun outil pratique n'existe pour analyser des propriétés telles que l'équivalence ou l'inclusion de langages.
Synthèse : Aucune méthode connue ne permet d'apprendre ou de synthétiser automatiquement un programme C-RASP à partir d'exemples. Les approches existantes reposent sur l'entraînement de réseaux de neurones et l'extraction de règles, qui échouent souvent à produire des traductions implémentables ou nécessitent des hypothèses idéalisées.

Cet article répond à ces défis en développant les premières techniques automatiques pour la vérification et la synthèse de programmes C-RASP.

Méthodologie

1. Vérification par réduction vers Lustre

Les auteurs établissent un lien formel entre C-RASP et Lustre, un langage de flux de données synchrone utilisé pour les systèmes embarqués.

Traduction : Un programme C-RASP est traduit en un nœud Lustre. Cette traduction mappe les règles C-RASP vers des variables Lustre (flux booléens et entiers).
- Opérateurs de comptage : L'opérateur de comptage C-RASP #φ (comptant les positions où φ est vrai) est simulé dans Lustre à l'aide de variables entières auxiliaires qui accumulent des valeurs sur un flux infini.
- Finis vs infinis : Puisque C-RASP opère sur des mots finis et Lustre sur des flux infinis, l'entrée est encodée comme un flux infini avec un marqueur spécifique de fin de flux (#) et un marqueur d'éternité (Ω).
Model Checking : Une fois traduits, des propriétés telles que l'équivalence, l'inclusion et la vacuité des langages sont vérifiées à l'aide de model checkers de pointe (spécifiquement Kind2) couplés à des solveurs SMT optimisés (CVC5, Z3).
Complexité : La traduction est polynomiale en taille, à condition que les paramètres de plage dans l'opérateur #rs,re soient encodés en unaire.

2. Synthèse par recuit simulé

L'article propose un algorithme de recherche locale basé sur le recuit simulé pour synthétiser des programmes C-RASP à partir d'exemples positifs et négatifs.

Espace d'états : La recherche est contrainte à une "forme de programme" fixe définie par le nombre de règles booléennes ( $N_b$ ), de règles de comptage ( $N_c$ ) et une borne sur les constantes numériques ( $K$ ).
Opérateurs de mutation : L'algorithme explore l'espace d'états en appliquant des mutations syntaxiques au programme courant. Cela inclut :
- Resampling : Remplacement complet du côté droit d'une règle.
- Micro-mutations : Modifications locales telles que l'échange de connecteurs logiques, le basculement de la négation, ou l'inversion de la strictesse des comparaisons.
- Contraintes : Les mutations sont restreintes à des fragments syntaxiques peu profonds (par exemple, profondeur 2 pour les expressions de comptage) pour orienter la recherche vers des modèles simples et interprétables.
Fonction objectif : La fonction de notation $E(P)$ priorise la minimisation des mauvaises classifications ( $\lambda_{mis}$ ), suivie de la pénalisation des règles inaccessibles ( $\lambda_U$ ) et de la taille totale de l'arbre de syntaxe abstraite ( $\lambda_S$ ).
Dynamique de recuit : L'algorithme accepte des solutions pires avec une probabilité dépendante d'un calendrier de refroidissement de température, lui permettant d'échapper aux optima locaux.

3. Applications intégrées

Les auteurs intègrent ces deux composants dans un cadre unifié supportant deux applications :

Minimisation de programmes Transformer : Étant donné un programme C-RASP, le système synthétise un programme équivalent structurellement plus petit. Il alterne entre recherche locale et vérification d'équivalence ; les contre-exemples fournis par le vérificateur guident la recherche.
Apprentissage contraint : Étant donné une spécification partielle (un programme C-RASP $P_{spec}$ ) et des exemples étiquetés, le système synthétise un programme qui correspond aux exemples et qui est inclus dans le langage de $P_{spec}$ ( $L(P) \subseteq L(P_{spec})$ ).

Contributions clés

Première méthode de vérification automatique : L'article présente la première technique pour vérifier automatiquement les programmes C-RASP en les réduisant à Lustre et en utilisant le model checking. Cela permet la vérification de l'équivalence, de l'inclusion et de la vacuité des langages.
Première méthode de synthèse automatique : Les auteurs introduisent un algorithme de recherche locale (recuit simulé) capable de synthétiser directement des programmes C-RASP à partir d'exemples, évitant ainsi le besoin d'un entraînement intermédiaire de réseaux de neurones.
Implémentation et évaluation comparative : Une chaîne d'outils Scala unifiée a été implémentée et évaluée face à une suite de benchmarks issus de la littérature, incluant des langages réguliers, basés sur le comptage et de style contextuel.

Résultats expérimentaux

Les auteurs ont évalué leur outil sur une suite de benchmarks incluant des langages comme Dyck-1, Majority et divers automates de Tomita.

Efficacité : L'outil a synthétisé avec succès des programmes C-RASP corrects pour la plupart des benchmarks dans un délai de 300 secondes. Par exemple, la synthèse d'un programme pour Dyck-1 a pris environ 3,92 secondes, tandis que AnBnCn a pris 80,05 secondes.
Précision : La synthèse a atteint une précision élevée en entraînement et en évaluation (souvent 100 %) sur des langages relevant du pouvoir expressif de C-RASP.
Comparaison avec les Transformers : L'article note que pour certains benchmarks, l'entraînement d'un transformer (par exemple GPT-2 via HuggingFace) pour obtenir le langage correct pouvait prendre plusieurs heures, alors que l'outil de synthèse C-RASP a accompli la tâche en quelques secondes.
Limites : Comme attendu par la théorie de l'expressivité, les langages dépassant le pouvoir de C-RASP (par exemple Parity, Tomita 3, Tomita 5) n'ont pas pu être appris avec une haute précision, les meilleures précisions d'entraînement restant inférieures à 80 %.

Importance et affirmations

L'article positionne C-RASP non pas seulement comme un outil théorique pour comprendre l'expressivité des transformers, mais comme un modèle substitut interprétable. En fournissant des méthodes automatiques pour la vérification et la synthèse, les auteurs soutiennent que C-RASP peut être analysé à l'aide de méthodes formelles (FXAI), comblant le fossé entre la nature "boîte noire" des réseaux de neurones et le besoin d'explicabilité.

L'importance réside dans :

Décidabilité en pratique : Bien que la vérification générale soit indécidable, la réduction vers Lustre offre une voie pratique et automatisée pour vérifier des comportements spécifiques et réels des transformers.
Synthèse directe : La méthode de synthèse offre une voie directe pour générer des programmes interprétables sans l'instabilité ou l'opacité de l'entraînement de réseaux de neurones profonds.
Optimisation : La capacité à minimiser les programmes transformers existants et à les apprendre sous contraintes démontre l'utilité de C-RASP pour l'affinement de programmes et les applications critiques pour la sécurité.

Les auteurs concluent que leur travail jette les bases de l'analyse formelle des transformers, avec des orientations futures incluant la vérification de robustesse et l'intégration de mécanismes de chaînes de pensée (CoT).