Résumé technique : Recherche Arbre de Pensée basée sur la nouveauté pour le raisonnement et la planification des LLM

Énoncé du problème

Bien que les modèles de langage de grande taille (LLM) aient démontré des capacités significatives dans les tâches basées sur le langage, ils restent fragiles face au raisonnement complexe et à la planification à long terme. Le prompting naïf échoue souvent, et les approches structurées comme l'Arbre de Pensée (ToT) souffrent d'une complexité temporelle et de coûts en tokens exponentiels dus à une recherche arborescente non élaguée. À l'inverse, les algorithmes de planification classiques, en particulier les planificateurs basés sur la largeur comme Iterative Width (IW), atteignent une efficacité en élaguant les états selon une mesure de « nouveauté », mais ils nécessitent des structures de problèmes rigides et formalisées (par exemple, PDDL) qui ne se traduisent pas bien dans des contextes de langage naturel. Le défi central abordé par ce travail consiste à définir une notion analogue de nouveauté au sein du domaine linguistique non structuré afin de permettre un élagage efficace dans ToT sans sacrifier la flexibilité des LLM.

Méthodologie

Les auteurs proposent un algorithme de planification qui intègre un élagage basé sur la nouveauté dans le cadre ToT. L'approche décompose le processus de planification en quatre sous-tâches :

1. Génération d'actions : Le LLM propose les prochaines actions possibles à partir d'un état courant.
2. Cartographie des états successeurs : Le LLM mappe les actions vers les états résultants.
3. Vérification du plan : Le modèle détermine si une séquence d'états satisfait l'objectif.
4. Estimation de la nouveauté : La contribution novatrice, où le LLM agit comme estimateur de nouveauté.

Estimation de la nouveauté et élagage

Contrairement aux planificateurs classiques qui calculent la nouveauté comme un entier basé sur des sous-ensembles de caractéristiques booléennes, cette méthode adapte la nouveauté au langage naturel. Le LLM est interrogé par une question binaire « oui/non » pour déterminer si un nouvel état est nouveau par rapport à une liste d'états précédemment visités. Cela exploite les connaissances générales pré-entraînées et la compréhension sémantique du modèle pour identifier des états uniques sans nécessiter de définitions explicites d'atomes ni d'exemples few-shot.

L'arbre de recherche peut être parcouru soit par recherche en largeur d'abord (BFS), soit par recherche en profondeur d'abord (DFS). Bien que l'IW classique utilise généralement la BFS, les auteurs notent que dans les contextes de LLM, la BFS peut entraîner une croissance exponentielle des coûts ; ainsi, les compromis entre BFS et DFS sont évalués. La méthode est conçue pour être agnostique au domaine, reposant uniquement sur un prompt de contexte conçu à la main expliquant les règles du domaine, évitant ainsi l'ingénierie de prompts spécifique au domaine pour l'estimateur de nouveauté lui-même.

Contributions clés

1. Adaptation de la nouveauté pour les LLM : L'article propose un concept mesurable de nouveauté pour les domaines linguistiques, utilisant les connaissances sémantiques internalisées du LLM pour élaguer les branches de recherche basées sur l'unicité de l'état plutôt que sur un appariement rigide de caractéristiques.
2. Cadre agnostique au domaine : Une implémentation générale est développée permettant des expérimentations flexibles à travers différents domaines (planification et raisonnement) avec un effort manuel minimal, ne nécessitant qu'un changement du prompt de contexte pour les règles du domaine.
3. Évaluation des sous-tâches : Les auteurs introduisent un cadre d'évaluation dédié inspiré de Plan-Bench pour tester les quatre sous-tâches (génération d'actions, cartographie des états, vérification et estimation de la nouveauté) indépendamment par rapport à des vérités terrain générées par des planificateurs classiques.
4. Analyse empirique du prompting : Le travail met en évidence la sensibilité de la planification par LLM à la conception du prompt, identifiant spécifiquement des points d'échec récurrents (par exemple, distinguer entre « pick-up » et « unstack » dans Blocksworld) et démontrant comment des extensions ciblées de prompts peuvent améliorer considérablement les performances.

Résultats expérimentaux

L'approche a été évaluée sur les domaines de planification Blocksworld et Logistics, ainsi que sur le benchmark MATH (niveau de difficulté 5).

• Performance des sous-tâches : En utilisant le modèle Qwen3 14B, le « Mode Réflexion » (tokens de raisonnement) et le prompting en langage naturel ont généralement produit les meilleurs résultats. Le modèle a réussi à effectuer un élagage par nouveauté dans des scénarios standards mais a eu des difficultés avec une variante plus difficile impliquant des états non dupliqués nécessitant un raisonnement strict basé sur la largeur.
• Efficacité des tokens : Dans des configurations bien réglées (spécifiquement en utilisant le « Mode Réflexion » et la cartographie d'actions/états « Directe »), le ToT élagué par nouveauté a réduit les coûts en tokens jusqu'à 20 fois par rapport au ToT standard tout en maintenant des taux de réussite similaires. Par exemple, dans Blocksworld avec DFS et le Mode Réflexion, le ToT de base a généré en moyenne 330k tokens, tandis que la version élaguée par nouveauté en a généré en moyenne 18k.
• Généralisabilité : La méthode s'est transférée efficacement vers le domaine Logistics et le benchmark MATH sans réajuster les prompts d'estimation de nouveauté, bien que l'efficacité optimale des tokens dans des domaines de raisonnement distincts (comme MATH) semble nécessiter un réglage spécifique au domaine des prompts.
• Limites : Dans des configurations mal réglées, les performances se sont dégradées de manière significative, avec des taux de résolution proches de zéro et des coûts en tokens augmentant de plus de 100 % en raison de la surcharge des requêtes de nouveauté. La méthode repose fortement sur les performances de base de la configuration ToT sous-jacente.

Importance et affirmations

L'article affirme que l'élagage basé sur la nouveauté peut améliorer avec succès l'efficacité du raisonnement Arbre de Pensée, le rendant viable pour des tâches de planification complexes en réduisant drastiquement l'espace de recherche et la consommation de tokens. Les auteurs soulignent que, bien que la méthode s'écarte de la planification classique basée sur la largeur en l'absence de garanties formelles sur la qualité de la solution ou le calcul précis de la nouveauté, elle offre une alternative pratique et flexible qui exploite l'adaptabilité des LLM.

Cependant, les auteurs restent modestes quant à la robustesse de l'approche. Ils notent que l'instabilité du prompting récursif des LLM reste un défi fondamental, rendant la configuration laborieuse et imprévisible. Le comportement d'élagage est observé comme étant principalement piloté par la détection de doublons plutôt que par un véritable raisonnement de « nouveauté » dans des scénarios complexes. Par conséquent, ce travail est présenté comme une étape vers une planification LLM plus efficace, suggérant des orientations futures telles que la sérialisation des objectifs, des estimateurs de nouveauté alternatifs, ou l'utilisation de modèles de base plus grands pour améliorer la compréhension des états.