🤖 AI

On the Ability of Transformers to Verify Plans

Cette étude introduit C*-RASP pour démontrer théoriquement et valider empiriquement que les transformers peuvent apprendre à vérifier des plans longs dans de nombreux domaines de planification classique, même lorsque la taille du vocabulaire et la longueur des séquences augmentent simultanément.

Auteurs originaux : Yash Sarrof, Yupei Du, Katharina Stein, Alexander Koller, Sylvie Thiébaux, Michael Hahn

Publié 2026-03-23

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yash Sarrof, Yupei Du, Katharina Stein, Alexander Koller, Sylvie Thiébaux, Michael Hahn

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 (un "Transformer", le cerveau derrière les IA comme moi) comment vérifier si un itinéraire de voyage est correct.

Le robot a lu des millions de livres de voyages. Il connaît très bien les routes, les villes et les règles de circulation. Mais il y a un problème : il a tendance à se perdre quand le voyage devient trop long ou quand on lui présente de nouvelles villes qu'il n'a jamais vues.

C'est exactement ce que cette recherche tente de comprendre et de résoudre. Voici l'explication simple, avec quelques images pour aider à visualiser.

1. Le Problème : Le Robot qui s'égare

Dans le monde de l'IA, on demande souvent à ces modèles de créer ou de vérifier des "plans" (des séquences d'actions pour atteindre un but, comme déplacer des objets ou résoudre un puzzle).

La situation actuelle : Si on entraîne le robot sur des voyages courts (5 étapes), il est excellent. Mais si on lui demande de vérifier un voyage de 200 étapes, il commence à halluciner. Il oublie où il est, propose des actions impossibles ou s'arrête avant la fin.
Le mystère : Pourquoi ? Est-ce qu'il manque de mémoire ? Est-ce qu'il est trop bête ? Les chercheurs ne savaient pas vraiment pourquoi il échouait, jusqu'à présent.

2. La Solution : Une nouvelle "Règle du Jeu" (C*-RASP)

Les chercheurs ont créé un nouveau langage théorique, qu'ils appellent C-RASP*. C'est un peu comme un manuel de règles pour dire : "Voici les types de problèmes que ton cerveau de robot peut vraiment résoudre, et voici ceux où il va inévitablement échouer."

Ils ont découvert que tout dépend de la structure du problème, pas seulement de sa taille.

Analogie de la "Boîte à Outils"

Imaginez que le robot doit ranger des jouets dans des boîtes.

Cas 1 : Les boîtes "Intelligentes" (Well-Formed / Delete-Free)
Imaginez des boîtes qui ont un mécanisme spécial : si vous mettez un jouet rouge dedans, il reste rouge. Si vous le retirez, il disparaît définitivement. Il n'y a pas de magie, pas de surprises.
- Résultat : Le robot apprend très vite. Même si vous lui donnez 1000 jouets au lieu de 10, il comprend la logique. Il peut vérifier des listes de 200 étapes sans problème. C'est comme apprendre à faire du vélo : une fois qu'on a compris l'équilibre, on peut rouler aussi loin qu'on veut.
Cas 2 : Les boîtes "Magiques" (STRIPS standard / Effets conditionnels)
Imaginez maintenant des boîtes magiques. Si vous mettez un jouet rouge dedans, il devient bleu seulement si la boîte était ouverte, mais il reste rouge si elle était fermée. De plus, si vous essayez de retirer un jouet, il peut se multiplier ou changer de forme selon l'humeur du jour.
- Résultat : Le robot est perdu. Pour savoir si le jouet est rouge à la fin, il doit se souvenir de chaque détail de l'histoire, de chaque état antérieur. C'est comme essayer de retenir une conversation de 200 personnes en se souvenant de qui a dit quoi à qui, dans quel ordre exact. Le cerveau du robot explose. Il ne peut pas généraliser.

3. La Grande Découverte : La Structure compte plus que la Taille

Le résultat le plus surprenant de l'article est que ce n'est pas la longueur du plan qui tue le robot, c'est la complexité de ses règles.

Si les règles sont simples et logiques (comme dans les cas "Well-Formed"), le robot peut vérifier des plans infinis.
Si les règles sont complexes et dépendent de conditions changeantes (comme dans les jeux de type "Lights Out" ou certains puzzles), le robot échouera, même si le plan est court.

C'est comme si vous appreniez à quelqu'un à cuisiner :

Si vous lui donnez une recette simple (ajouter du sel, cuire, servir), il pourra cuisiner un festin pour 1000 personnes.
Si vous lui donnez une recette où "le sel change de goût selon l'heure de la journée", il ne pourra jamais cuisiner, même pour une seule personne.

4. Pourquoi est-ce important ?

Cette recherche est cruciale pour deux raisons :

Comprendre l'échec : Elle explique pourquoi les IA actuelles échouent souvent dans des tâches de planification complexes. Ce n'est pas parce qu'elles sont "bêtes", c'est parce que la structure du problème dépasse leurs capacités de généralisation.
Comment les aider : Elle nous dit comment reformuler les problèmes. Si nous prenons un problème complexe (comme un jeu de puzzle) et que nous le réécrivons avec des règles plus simples et plus logiques (en "compilant" le problème), nous pouvons permettre à l'IA de le résoudre parfaitement, même avec de nouveaux objets ou des scénarios plus longs.

En résumé

Cette étude dit aux développeurs d'IA : "Ne blâmez pas le robot pour sa mémoire courte. Regardez plutôt vos règles de jeu. Si vos règles sont trop 'magiques' et imprévisibles, aucun robot ne pourra les comprendre sur le long terme. Mais si vous les rendez logiques et structurées, l'IA pourra devenir un expert infatigable."

C'est une avancée majeure pour rendre les IA plus fiables dans le monde réel, où les situations sont souvent longues et complexes.

1. Problématique et Contexte

Les modèles de langage (LLM) basés sur l'architecture Transformer ont montré des résultats mitigés dans le domaine de la planification automatique (AI Planning). Bien qu'ils puissent générer des plans pour des instances de taille similaire à celles vues lors de l'entraînement, ils échouent souvent à généraliser à des plans plus longs ou à des instances impliquant un nombre d'objets différent (vocabulaire variable).

Le problème central abordé par les auteurs est l'incapacité théorique et empirique des Transformers à vérifier la validité d'un plan (Plan Verification) lorsque la longueur du plan et le nombre d'objets (la taille de l'alphabet d'entrée) augmentent simultanément au moment du test. La littérature actuelle manque d'une analyse théorique claire expliquant pourquoi certains domaines de planification sont appris avec succès par les Transformers tandis que d'autres ne le sont pas.

2. Méthodologie et Cadre Théorique

Pour combler ce vide, les auteurs adoptent une approche basée sur la théorie des langages formels et la complexité computationnelle, en étendant le cadre existant C-RASP (Counting RASP).

A. Le Cadre C-RASP et ses Limites

Le cadre C-RASP permet de caractériser la capacité d'un Transformer à généraliser en longueur. Il a été établi que si un problème peut être exprimé en C-RASP[Pos], un Transformer peut le généraliser. Cependant, C-RASP suppose un alphabet de tokens fixe et fini. Cela ne couvre pas les scénarios de planification où le nombre d'objets (et donc le vocabulaire) varie entre l'entraînement et le test.

B. Introduction de C*-RASP

Les auteurs introduisent C-RASP*, une extension de C-RASP conçue pour gérer la croissance simultanée de la longueur de la séquence et de la taille du vocabulaire (alphabet).

Alphabet Split : L'alphabet d'entrée est divisé en deux parties : un alphabet fixe $\Sigma$ (noms d'actions, prédicats) et un alphabet croissant $C$ (identifiants d'objets).
Prédicat de Correspondance (Match Predicate) : C*-RASP introduit un nouveau prédicat logique $\chi(i, j)$ qui permet de vérifier si deux tokens à des positions différentes correspondent aux mêmes objets, sans dépendre de leurs identités absolues. Cela force le modèle à apprendre des règles basées sur la structure et la correspondance locale plutôt que sur la mémorisation d'identifiants spécifiques.
Symbolic Limit Transformer : Les auteurs définissent un objet théorique, le "Symbolic Limit Transformer", qui représente l'algorithme sous-jacent appris par une séquence de Transformers entraînés sur des longueurs et des vocabulaires croissants. Ils prouvent que l'expressibilité par ce modèle est une condition nécessaire et suffisante pour la généralisation en longueur et en vocabulaire.

C. Classes de Planification Analysées

L'étude se concentre sur la vérification de plans dans plusieurs sous-classes de domaines de planification :

Delete-Free : Les actions n'ont que des effets positifs (pas de suppression de faits).
Well-Formed : Chaque effet d'une action change nécessairement l'état du monde (pas d'actions redondantes ou "no-op").
STRIPS standard : Pas d'effets conditionnels, mais peut inclure des suppressions.
Conditional Effects : Les effets dépendent de l'état actuel (ex: basculer un interrupteur).

3. Contributions Clés

Cadre Théorique Unifié (C-RASP) :* Développement d'un nouveau cadre formel permettant d'analyser la généralisation des Transformers lorsque le nombre d'objets n'est pas borné, dépassant les limites de C-RASP.
Résultats de Positivité et Négativité :
- Positif : La vérification de plans dans les domaines Delete-Free et Well-Formed est exprimable en C*-RASP. Les auteurs prouvent que les Transformers peuvent apprendre à vérifier ces plans avec une généralisation parfaite, même avec un nombre croissant d'objets.
- Négatif : La vérification de plans dans les domaines STRIPS généraux (avec suppression de faits) et ceux avec effets conditionnels n'est pas exprimable en C*-RASP. Ces problèmes sont réduits à des langages connus pour être difficiles pour les Transformers (comme le langage FlipFlop ou PARITY), impliquant qu'ils ne généraliseront pas.
Validation Empirique : Conception de trois domaines de planification synthétiques (Heavy Grippers, Colors, Lights Out) avec des variantes "Well-Formed", "Delete-Free", "STRIPS" et "Conditional Effects" pour tester ces hypothèses.

4. Résultats Expérimentaux

Les expériences ont été menées sur une architecture GPT-2 entraînée pour prédire la validité d'un plan (token "correct" ou "incorrect").

Généralisation en Longueur et Vocabulaire :
- Les modèles entraînés sur des plans courts (11-100 actions) et avec un nombre d'objets limité réussissent à généraliser à des plans longs (101-200 actions) et à un nombre d'objets plus élevé pour les variantes Well-Formed et Delete-Free. La précision reste élevée (proche de 100%).
- En revanche, pour les variantes STRIPS (ex: Colors) et Conditional Effects (ex: Lights Out), la précision chute drastiquement dès que la longueur du plan dépasse la taille de l'entraînement, tombant au niveau du hasard (chance level) pour les effets conditionnels.
Impact de la Structure :
- Le domaine Lights Out avec effets conditionnels échoue même avec un nombre d'objets fixe, confirmant que la difficulté provient de la structure logique (non-expressibilité en C*-RASP) et non seulement de la complexité du vocabulaire.
- La reformulation d'un problème complexe (comme Lights Out) en une version Well-Formed (en décomposant les effets conditionnels en multiples actions distinctes) permet une généralisation parfaite, démontrant que la structure du problème est le facteur déterminant.

5. Signification et Implications

Explication Théorique des Échecs : L'article fournit une explication fondamentale à l'inconstance des LLMs dans la planification : ce n'est pas une question de capacité brute, mais de la structure formelle du problème. Les Transformers échouent là où le problème nécessite de suivre des dépendances complexes (comme le dernier état modifié d'un fait supprimé) qui ne peuvent pas être résolues par un comptage local ou une correspondance simple.
Guide pour la Conception de Problèmes : Pour rendre les tâches de planification accessibles aux Transformers, il est crucial de reformuler les problèmes pour qu'ils soient Well-Formed ou Delete-Free. Cela suggère que le prétraitement des problèmes de planification (compilation) est une étape essentielle pour l'application des LLMs.
Avancée en Théorie des Transformers : L'introduction de C*-RASP et du "Symbolic Limit Transformer" ouvre de nouvelles voies pour analyser la capacité des modèles à raisonner sur des structures symboliques infinies ou variables, au-delà de la simple généralisation en longueur.

En conclusion, cette étude démontre que la capacité des Transformers à vérifier des plans dépend intrinsèquement de la propriété structurelle du domaine de planification. Les domaines bien structurés (Well-Formed/Delete-Free) sont apprenables et généralisables, tandis que les domaines non contraints (STRIPS standard, effets conditionnels) posent des limites théoriques insurmontables pour l'architecture Transformer actuelle sans mécanismes de raisonnement externes (comme le Chain-of-Thought, non couvert ici).