Tree of Thoughts (ToT) (FR)

Tree of Thoughts (ToT) (Arbre de Pensées) est un framework innovant pour la gestion du raisonnement des grands modèles de langage (LLM), leur permettant de résoudre des problèmes de manière délibérée en explorant systématiquement de multiples chaînes de raisonnement. Le concept a été présenté en 2023 par des chercheurs de l'Université de Princeton et de Google DeepMind.

ToT est une extension et une généralisation de la technique populaire de la « chaîne de pensée » (Chain of Thought, CoT). Contrairement à la CoT, où le raisonnement est une séquence linéaire unique d'étapes, ToT organise le processus de pensée sous la forme d'un arbre, où chaque nœud est un état intermédiaire (une « pensée ») et les branches représentent les chemins de raisonnement possibles. Cela permet au modèle d'explorer plusieurs options en parallèle, d'évaluer leur potentiel, de revenir sur ses pas en cas d'impasse (backtracking) et de faire un choix délibéré.

Principe de fonctionnement

Le framework ToT organise le processus de résolution de problèmes comme une recherche dans un arbre d'états. Son fonctionnement repose sur l'interaction cyclique de quatre composants clés :

1. Décomposition du problème en « pensées » : Le problème initial est décomposé en sous-tâches ou étapes plus petites, appelées « pensées ». Contrairement à la CoT, où une « pensée » n'est que le token suivant, dans ToT, une « pensée » est une unité sémantiquement significative (par exemple, une équation dans un problème mathématique ou un paragraphe dans le plan d'un texte) qui rapproche de la solution.

1. Génération de pensées : À chaque étape, pour l'état actuel (nœud de l'arbre), le modèle génère plusieurs « pensées » potentielles suivantes (branches). Deux stratégies sont utilisées à cette fin :

• Échantillonnage (sample) : Le modèle génère plusieurs continuations de manière indépendante. Cette approche convient aux tâches créatives où un large éventail d'idées est bénéfique.
• Proposition (propose) : Le modèle génère des options de manière séquentielle, ce qui est plus efficace pour les problèmes avec un espace de solutions restreint.

1. Évaluation des états : Les « pensées » générées sont évaluées par le LLM lui-même pour déterminer leur potentiel. L'évaluation peut être numérique (par exemple, sur une échelle de 0 à 1) ou catégorique (« certain », « possible », « impossible »). Il s'agit d'une fonction heuristique qui guide la recherche vers les branches les plus prometteuses.

1. Algorithme de recherche : Pour explorer systématiquement l'arbre de pensées, des algorithmes de recherche classiques sont utilisés :

• Parcours en largeur (BFS) : Explore tous les nœuds d'un même niveau avant de passer au niveau suivant. Il garantit de trouver le chemin le plus court, mais nécessite plus de mémoire.
• Parcours en profondeur (DFS) : Explore une branche jusqu'à son terme avant de revenir en arrière pour en essayer une autre. Il est plus économe en mémoire et convient aux problèmes avec un espace de recherche profond mais pas trop large.

Ce framework imite la pensée humaine lors de la résolution de problèmes, en combinant la génération intuitive d'idées (via le LLM) avec une planification systématique et délibérée et une exploration des options.

Comparaison avec d'autres méthodes de raisonnement

ToT par rapport à Chain of Thought (CoT)

ToT est une généralisation directe de la CoT. Si la CoT peut être vue comme un arbre avec un facteur de branchement de 1, ToT permet d'explorer un arbre avec un facteur de branchement arbitraire. Cela offre des avantages clés :

• Exploration d'alternatives : ToT peut envisager plusieurs chemins de solution, tandis que la CoT est limitée à un seul chemin linéaire.
• Possibilité de retour en arrière (backtracking) : ToT permet au modèle de « revenir en arrière » si une branche de raisonnement mène à une impasse, ce qui est impossible avec la CoT.
• Planification globale : ToT permet de faire des choix stratégiques basés sur l'évaluation de plusieurs étapes futures.

ToT par rapport à Self-Consistency

La Self-Consistency (auto-cohérence) génère de multiples « chaînes de pensée » indépendantes et sélectionne la réponse la plus fréquente par un vote majoritaire. Cette méthode améliore la fiabilité de la CoT, mais, tout comme elle, ne permet pas d'explorer une structure de solution ramifiée. ToT, en revanche, peut montrer des améliorations plus significatives sur des tâches de planification complexes où non seulement les tentatives indépendantes, mais aussi leur interconnexion, sont importantes.

Résultats expérimentaux

Les auteurs de ToT ont démontré son efficacité sur trois tâches nécessitant une planification ou une recherche non triviale.

• Jeu des 24 : Un puzzle mathématique où il faut obtenir le nombre 24 à partir de quatre nombres donnés en utilisant des opérations arithmétiques de base. Le prompting standard avec GPT-4 a montré un taux de réussite de 7,3 %, tandis que la Chain of Thought a atteint 4 %. ToT avec un parcours en largeur (b=5) a atteint un taux de réussite de 74 %, soit une amélioration de 18,5 fois par rapport à la CoT.
• Écriture créative : Dans une tâche de génération d'un texte cohérent de quatre paragraphes avec des phrases de fin imposées, les textes créés avec ToT ont obtenu un score de cohérence moyen de 7,56 sur 10, contre 6,15 pour la CoT. Dans 41 comparaisons sur 100, les humains ont préféré le texte généré par ToT, contre 21 pour celui de la CoT.
• Mots croisés miniatures (5x5) : ToT a correctement rempli 60 % des mots, alors que la CoT n'en a rempli que 1 %.

Limites et perspectives futures

Malgré ses résultats impressionnants, le framework ToT présente plusieurs limites :

• Complexité computationnelle : ToT nécessite beaucoup plus de ressources de calcul (de 5 à 100 fois plus de tokens) que les méthodes standards, en raison de la nécessité de générer et d'évaluer de nombreuses « pensées ».
• Complexité de mise en œuvre : L'implémentation de ToT demande un effort d'ingénierie considérable pour créer et configurer tous les composants : le générateur de pensées, l'évaluateur d'états et l'algorithme de recherche.
• Dépendance à la qualité de l'évaluation : L'efficacité de l'ensemble du framework dépend fortement de la capacité du LLM à évaluer adéquatement les états intermédiaires, ce qui n'est pas toujours garanti.

Les recherches futures visent à améliorer l'efficacité, à automatiser l'optimisation et à intégrer ToT avec d'autres méthodes, telles que l'apprentissage par renforcement, pour créer des agents plus intelligents et autonomes.

Liens

• Dépôt officiel de Tree of Thoughts sur GitHub.
• Tree of Thoughts (ToT) - un guide sur Prompt Engineering Guide.

Bibliographie

• Yao, S. et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. arXiv:2305.10601.
• Wei, J. et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. arXiv:2201.11903.
• Wang, X. et al. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models. arXiv:2203.11171.
• Kojima, T. et al. (2022). Large Language Models are Zero-Shot Reasoners. arXiv:2205.11916.
• Zhang, Z. et al. (2022). Automatic Chain of Thought Prompting in Large Language Models. arXiv:2210.03493.
• Lyu, Q. et al. (2023). Faithful Chain-of-Thought Reasoning. arXiv:2301.13379.
• Ling, Z. et al. (2023). Deductive Verification of Chain of Thought Reasoning. arXiv:2306.03872.
• Yao, S. et al. (2022). ReAct: Synergizing Reasoning and Acting in Language Models. arXiv:2210.03629.
• Besta, M. et al. (2023). Graph of Thoughts: Solving Elaborate Problems with Large Language Models. arXiv:2308.09687.
• Lightman, H. et al. (2023). Let’s Verify Step by Step. arXiv:2305.20050.
• Lanham, T. et al. (2023). Measuring Faithfulness in Chain-of-Thought Reasoning. arXiv:2307.13702.
• Yang, B. et al. (2025). Hallucination Detection in Large Language Models with Metamorphic Relations. arXiv:2502.15844.