Tree of Thoughts (ToT)

Tree of Thoughts (ToT) est un cadre d’ingénierie de prompt dans lequel un grand modèle de langage (LLM) résout un problème en explorant un arbre de solutions partielles. À chaque étape, le modèle propose plusieurs étapes suivantes possibles, appelées pensées, évalue le potentiel de chaque état obtenu, puis un algorithme de recherche décide quelles branches développer, conserver ou abandonner. Alors que le prompting par chaîne de pensée s’engage sur une seule piste de raisonnement dès le premier jeton, ToT peut anticiper et revenir en arrière. Shunyu Yao et ses collègues de l’université de Princeton et de Google DeepMind l’ont présenté dans Tree of Thoughts: Deliberate Problem Solving with Large Language Models, à NeurIPS 2023. Le même mois, Jieyi Long a proposé un système similaire d’exploration arborescente pour résoudre des sudokus avec un LLM. Pour le jeu du 24, ToT a fait passer le taux de réussite de GPT-4 de 4 % avec le prompting par chaîne de pensée à 74 %.

Fonctionnement de Tree of Thoughts#

Yao et ses collègues définissent ToT à l’aide de quatre choix de conception :

• Décomposition des pensées : Détermine ce qu’est une étape. Dans le jeu du 24, une pensée est une équation ; en génération de texte créative, un plan pour le passage ; dans une grille de mots croisés, un mot à placer.
• Générateur de pensées : Détermine comment produire les candidats. Le modèle échantillonne plusieurs pensées indépendamment, ce qui convient aux étapes ouvertes, ou propose une liste de choix distincts dans un seul prompt, ce qui évite les doublons lorsque les options sont limitées.
• Évaluateur d’état : Détermine comment juger la progression. Le modèle évalue chaque état isolément, par exemple en indiquant « certain », « possible » ou « impossible » d’atteindre l’objectif, ou en votant pour le meilleur de plusieurs états. Ces évaluations servent d’heuristique de recherche, rôle assuré par une fonction de score écrite à la main dans les méthodes classiques.
• Algorithme de recherche : Détermine comment explorer l’arbre. La recherche en largeur conserve les b meilleurs états à chaque niveau, tandis que la recherche en profondeur suit la branche la plus prometteuse, écarte les états rejetés par l’évaluateur et revient en arrière.

Exemple : le jeu du 24#

Le jeu du 24 donne quatre nombres à combiner avec +, -, x et / pour obtenir 24, en utilisant chaque nombre une fois. ToT divise la solution en trois étapes, chacune correspondant à une équation qui fusionne deux nombres. Pour l’entrée 4 9 10 13, un prompt de proposition énumère des candidats tels que :

13 - 9 = 4 (left: 4 4 10)
10 - 4 = 6 (left: 6 9 13)
4 + 9 = 13 (left: 10 13 13)
4 x 13 = 52 (left: 9 10 52)

Le prompt d’évaluation demande ensuite si chaque ensemble restant peut encore permettre d’obtenir 24. « 4 4 10 » est certain, car (10 - 4) x 4 = 24, tout comme « 6 9 13 », car (13 - 9) x 6 = 24. En revanche, « 10 13 13 » et « 9 10 52 » sont impossibles ; la recherche ne développe donc que les deux premières branches. En suivant la première, on obtient ensuite 10 - 4 = 6 (reste : 4 6), puis 4 x 6 = 24.

Dans les expériences de l’article sur 100 parties difficiles, la recherche en largeur conservait les 5 meilleurs états à chaque étape, et chaque état était évalué trois fois. Avec GPT-4, ToT a résolu 74 % des parties, contre 7,3 % avec un prompt direct, 4,0 % avec une chaîne de pensée et 9,0 % avec une chaîne de pensée assortie de cohérence interne. Même la meilleure de 100 chaînes de pensée échantillonnées n’atteignait que 49 %, et ToT ne conservant qu’un seul état par étape atteignait 45 %.

Place de Tree of Thoughts#

ToT est utile pour les problèmes où les premiers choix contraignent les suivants et où il est difficile de corriger un mauvais premier pas : les casse-têtes, la planification et les problèmes de mathématiques à plusieurs étapes. Dans les mini-mots croisés de 5x5, ToT en profondeur avec élagage a rempli correctement 60 % des mots et résolu 4 grilles sur 20. Le coût est computationnel : chaque niveau de l’arbre nécessite plusieurs appels de génération et d’évaluation. Une seule réponse peut donc demander des dizaines d’appels au modèle, voire davantage, et beaucoup plus de jetons qu’une chaîne, avec une latence d’inférence comparable.

La même boucle de génération, d’évaluation et d’expansion intervient à une échelle beaucoup plus large dans la recherche automatisée d’expériences, comme le réglage des hyperparamètres. Dans AutoTrain sur la plateforme Ultralytics, Ask AI peut entraîner plusieurs modèles Ultralytics YOLO qui ne diffèrent que par un réglage, comme des tailles d’image de 640, 800 et 960, comparer les entraînements terminés selon leur mAP50-95 de validation, puis proposer la prochaine expérience à partir du meilleur résultat.

Tree of Thoughts et méthodes apparentées#

• Prompting par chaîne de pensée : Une seule piste de raisonnement, équivalente à un arbre ne comportant qu’une branche par niveau.
• Prompting ReAct : Entrelace le raisonnement avec des actions dans un environnement externe, comme des recherches ou des appels d’outils, et avance en fonction de leurs résultats. ToT explore les pensées candidates du modèle lui-même.
• Cohérence interne : Échantillonne plusieurs chaînes complètes et choisit les réponses finales à la majorité, sans évaluer les étapes intermédiaires.
• Graph of Thoughts : généralise l’arbre en un graphe où les pensées peuvent également être fusionnées et affinées, et a rapporté une qualité de tri supérieure de 62 % à celle de ToT, pour un coût inférieur de plus de 31 %.
• Recherche arborescente Monte-Carlo (MCTS) : l’algorithme de recherche utilisé par AlphaGo, qui équilibre l’exploration de nouvelles branches et l’exploitation des branches prometteuses, et peut remplacer la recherche en largeur ou en profondeur parmi les pensées.
• Modèles de raisonnement : entraînés par apprentissage par renforcement pour produire de longues traces de raisonnement en une seule génération, tandis que ToT s’appuie sur un programme de recherche externe autour d’un modèle ordinaire pour créer des embranchements et revenir en arrière.