Accueil › Glossaire › Tree-of-Thought

Tree-of-Thought (ToT)

Le tree-of-thought (ToT), ou « arbre de pensées », est un framework d’inférence pour les modèles de langage qui généralise le chain-of-thought en permettant au modèle d’explorer simultanément plusieurs chemins de raisonnement, d’évaluer chacun d’entre eux, et de revenir en arrière (backtracking) quand une branche mène à une impasse.

Qu’est-ce que le tree-of-thought ?

Les LLM génèrent du texte de manière autoregressive : token par token, de gauche à droite, sans possibilité de revenir en arrière. Le chain-of-thought (CoT) améliore le raisonnement en ajoutant des étapes intermédiaires, mais reste fondamentalement linéaire : le modèle suit un seul chemin de pensée et ne peut pas explorer d’alternatives si ce chemin s’avère infructueux.

Le tree-of-thought résout cette limitation en structurant le raisonnement comme un arbre. Chaque nœud de l’arbre représente une « pensée » (thought), c’est-à-dire une unité cohérente de texte correspondant à une étape intermédiaire vers la résolution du problème. Depuis chaque nœud, le modèle peut générer plusieurs pensées candidates, évaluer leur pertinence, et choisir la branche la plus prometteuse. Si une branche mène à une impasse, le modèle peut remonter dans l’arbre (backtracking) et explorer une alternative.

Cette approche est directement inspirée des recherches en intelligence artificielle classique des années 1950-1960, notamment les travaux de Newell et Simon sur la résolution de problèmes formulée comme une recherche dans un espace combinatoire. L’innovation du ToT est d’appliquer ce paradigme de planification délibérée aux LLM modernes, en utilisant le modèle lui-même à la fois comme générateur de pensées et comme évaluateur de leur qualité.

Comment fonctionne le ToT

Les quatre composants fondamentaux

Le framework ToT repose sur quatre opérations qui se combinent pour explorer l’espace des solutions :

La combinaison de ces quatre composants est configurable selon la tâche. Pour un puzzle comme le « Game of 24 » (trouver une expression arithmétique qui donne 24 à partir de 4 nombres), le ToT utilise une décomposition en 3 étapes, la méthode propose pour la génération, value pour l’évaluation, et BFS comme algorithme de recherche. Pour de l’écriture créative, la décomposition pourrait être en paragraphes, avec sample pour la génération et vote pour l’évaluation.

L’analogie Système 1 / Système 2

Les auteurs du ToT s’appuient sur la distinction de Daniel Kahneman entre pensée rapide (Système 1) et pensée lente (Système 2). Un LLM standard qui génère des tokens séquentiellement fonctionne comme le Système 1 : des décisions rapides et associatives, sans planification délibérée. Le CoT ajoute une couche de raisonnement séquentiel, mais reste fondamentalement réactif. Le ToT implémente le Système 2 : une résolution de problèmes délibérée, avec exploration, évaluation et capacité de remise en question des choix antérieurs.

Cette analogie n’est pas parfaite (le ToT n’a pas de véritable « conscience » de ses choix), mais elle capture bien l’intuition : le ToT permet au modèle de « prendre du recul », d’examiner plusieurs options et de choisir la meilleure, plutôt que de s’engager aveuglément dans la première solution qui lui vient.

Algorithmes de recherche en détail

Le choix de l’algorithme de recherche détermine comment l’arbre est exploré :

Résultats expérimentaux

L’article original de Yao et al. (2023) évalue le ToT sur trois tâches représentatives :

Game of 24

Le problème : combiner 4 nombres avec des opérations arithmétiques (+, -, ×, ÷) pour obtenir 24. C’est un problème de planification pure qui nécessite d’explorer plusieurs combinaisons. Résultats : le CoT standard (avec GPT-4) résout environ 4% des cas. Le CoT avec self-consistency atteint 9%. Le ToT avec BFS atteint 74%. L’amélioration est massive parce que le problème exige précisément ce que le ToT offre : exploration de multiples chemins et backtracking quand une combinaison ne fonctionne pas.

Écriture créative

Le problème : écrire un passage cohérent de 4 paragraphes où chaque paragraphe se termine par un des 4 mots imposés. Résultats : le ToT produit des textes jugés plus cohérents par GPT-4 (évaluateur) que le CoT standard, avec un taux de satisfaction de 7,56/10 contre 6,19/10 pour le CoT. Le DFS est l’algorithme de choix ici car la tâche est séquentielle.

Mini mots croisés (5×5)

Le problème : remplir une grille de mots croisés de 5×5. Résultats : le ToT résout 60% des jeux (mots complets) contre 15,6% pour le CoT et 16% pour le CoT avec self-consistency. La capacité de backtracking est décisive : quand un mot ne fonctionne pas avec les lettres croisées, le modèle peut revenir en arrière et essayer un autre mot.

Chain-of-Thought vs Tree-of-Thought

Le CoT reste le choix par défaut pour la majorité des tâches. Le ToT ne se justifie que lorsque le problème exige explicitement de l’exploration (plusieurs solutions possibles à évaluer), du backtracking (certains chemins mènent à des impasses) et de la planification stratégique (les décisions initiales conditionnent la suite).

Implémentation pratique

Via l’implémentation officielle

L’équipe de Princeton NLP fournit une implémentation open-source sur GitHub. L’installation est directe :

L’utilisation requiert une clé API OpenAI (le framework utilise GPT-4 par défaut) et permet de configurer les paramètres de recherche : nombre d’échantillons de génération (--n_generate_sample), nombre d’évaluations (--n_evaluate_sample), et nombre de branches conservées à chaque étape (--n_select_sample).

Via du prompting pur (version simplifiée)

Pour les cas où l’implémentation complète est disproportionnée, une version simplifiée du ToT peut être approximée par du prompting. Le principe : demander au modèle de générer plusieurs stratégies de résolution, de voter pour la meilleure, puis de développer la solution basée sur la stratégie gagnante.

Cette approche « ToT-lite » capture une partie des bénéfices (exploration, évaluation) sans la complexité de l’orchestration multi-appels. Les gains sont inférieurs au ToT complet mais le rapport effort/bénéfice est souvent plus favorable en production.

Variantes et extensions

Le ToT a inspiré plusieurs extensions qui enrichissent le framework original :

ToT face aux modèles de raisonnement modernes

Le ToT a été conçu avant l’émergence des modèles de raisonnement natifs (OpenAI o1/o3, Claude avec extended thinking, DeepSeek R1). Ces modèles intègrent des mécanismes de raisonnement approfondi directement dans leur architecture, ce qui pose la question de la pertinence du ToT en tant que technique externe.

L’extended thinking de Claude, par exemple, permet au modèle de raisonner longuement avant de répondre, d’explorer implicitement plusieurs approches et de s’auto-corriger. En mode adaptive avec interleaved thinking, Claude peut même « réfléchir » entre les étapes d’un workflow agentique, ce qui couvre une partie des cas d’usage du ToT.

Cependant, le ToT conserve des avantages spécifiques. La transparence du processus de recherche (chaque branche, chaque évaluation est traçable) est supérieure au thinking résumé des modèles de raisonnement. Le contrôle explicite de l’algorithme de recherche (BFS vs DFS, largeur de l’arbre, profondeur maximale) n’a pas d’équivalent dans les modèles natifs. Pour les tâches de planification pure nécessitant une exploration exhaustive, le ToT reste la méthode de référence.

Limites et défis

Le ToT présente plusieurs contraintes significatives qui limitent son adoption en production.

Le coût computationnel est la limite la plus évidente. Une seule résolution ToT peut nécessiter des dizaines, voire des centaines d’appels API. Sur le Game of 24, chaque problème peut consommer l’équivalent de 50 à 100 appels au modèle, ce qui est prohibitif pour des applications à fort volume. Le coût est au minimum 10 à 50 fois supérieur à un simple CoT.

La latence est proportionnelle au nombre d’appels. Une résolution qui prend 500 ms avec un CoT peut prendre 30 à 60 secondes avec un ToT complet, ce qui est inacceptable pour les applications interactives.

La complexité d’implémentation est non triviale. Orchestrer les appels API, parser les réponses du modèle pour la phase d’évaluation, gérer la structure arborescente et les algorithmes de recherche nécessite un code substantiel. L’implémentation officielle de Princeton est un bon point de départ, mais l’adapter à une nouvelle tâche demande une compréhension approfondie du framework.

La dépendance à la qualité de l’évaluation est un point subtil. Le ToT utilise le modèle lui-même pour évaluer ses propres pensées. Si le modèle est un mauvais juge de la qualité de ses raisonnements (ce qui arrive régulièrement sur les domaines spécialisés), l’exploration sera mal guidée et le backtracking ne sera pas déclenché au bon moment.

Enfin, le ToT nécessite des modèles de grande taille. Les petits modèles (moins de 70 milliards de paramètres) ne produisent pas des évaluations suffisamment fiables pour guider la recherche arborescente. Le framework est conçu pour les modèles frontier (GPT-4, Claude Opus, etc.).

Cas d’usage en production

Malgré ses limites, le ToT trouve des applications dans plusieurs domaines. La planification de projets complexes, où les décisions initiales conditionnent fortement la suite, bénéficie de l’exploration multi-branches. La résolution de problèmes de design (architecture logicielle, UX, stratégie produit) où plusieurs approches doivent être évaluées avant d’en choisir une peut exploiter le ToT en version simplifiée. Les jeux et puzzles combinatoires restent le terrain de prédilection du framework. L’écriture créative avec contraintes structurelles (construire un récit qui respecte des points de passage imposés) profite du backtracking.

En pratique, la version « ToT-lite » par prompting est la plus utilisée en production. L’implémentation complète avec orchestration multi-appels est réservée aux cas d’usage de recherche ou aux applications à très forte valeur ajoutée où le coût computationnel est justifié.