Arbre de pensées : Résolution délibérée de problèmes avec la recherche LLM

Après avoir consacré les deux derniers articles aux agents qui s'auto-corrigent via la réflexion (Reflexion) et la critique interactive avec des outils (CRITIC), je voulais prendre du recul et examiner une approche plus structurelle : et si l'agent ne s'engageait jamais dans un chemin de raisonnement unique au départ ? Tree of Thoughts (ToT) de Yao et al. (NeurIPS 2023) propose exactement cela — un cadre de recherche où le LLM explore un espace ramifié d'étapes de raisonnement intermédiaires plutôt qu'une chaîne linéaire unique. Je le lis maintenant car il représente la formulation la plus claire de la recherche délibérée pour le raisonnement LLM, et la recherche délibérée est ce dont vous avez besoin lorsqu'une seule étape intermédiaire erronée dans un calcul financier peut corrompre silencieusement tout le flux en aval.

L'article

Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao et Karthik Narasimhan introduisent Tree of Thoughts comme une généralisation de l'incitation par chaîne de pensée (CoT). L'idée clé est de traiter les étapes de raisonnement intermédiaires comme des "pensées" — des unités de texte cohérentes qui peuvent être évaluées indépendamment — et de les organiser en un arbre plutôt qu'en une chaîne. À chaque nœud, le modèle génère plusieurs pensées candidates, évalue chacune d'elles (via un appel LLM séparé qui note les états comme "sûr / peut-être / impossible"), puis applique un algorithme de recherche standard (BFS ou DFS) pour parcourir l'arbre. Si une branche semble morte, le modèle peut l'élaguer ou revenir en arrière (backtracking) — ce que ni CoT ni CoT-SC ne peuvent faire.

L'article évalue la méthode sur trois tâches : le Jeu de 24 (combiner quatre nombres pour atteindre 24 à l'aide de l'arithmétique), l'Écriture Créative (produire un passage cohérent en utilisant quatre fins de phrases aléatoires) et les Mini Mots Croisés (résoudre une grille de mots croisés 5×5). Toutes trois nécessitent un raisonnement qui peut bénéficier de l'exploration et du retour en arrière, ce qui est exactement le cadre conçu par les auteurs.

Idées clés

• Sur le Jeu de 24, ToT avec une largeur de faisceau b=5 atteint un succès de 74 %, contre 4 % pour GPT-4 avec CoT standard et 9 % pour CoT-SC avec 100 échantillons. Cet écart est frappant.
• GPT-3.5 + ToT n'atteint que 19 % sur la même tâche ; le bénéfice de la méthode dépend fortement du modèle. La qualité de la génération de pensées de GPT-4 est le principal moteur du gain — la génération GPT-4 + l'évaluation GPT-3.5 atteint 64 %, tandis que la génération GPT-3.5 + l'évaluation GPT-4 n'atteint que 31 %.
• Pour l'Écriture Créative, ToT obtient un score de 7,56 contre 6,93 pour CoT sur une échelle de cohérence GPT-4, et les annotateurs humains préfèrent les sorties ToT 41/100 fois contre 21/100 pour CoT.
• Mini Mots Croisés : ToT atteint 60 % de précision au niveau du mot (CoT : 40,6 %, IO : 15,6 %) mais ne résout que 4 grilles complètes sur 20 (20 %). L'écart entre le succès au niveau du mot et au niveau du jeu révèle que même avec le retour en arrière, la satisfaction des contraintes globales reste difficile.
• L'étape d'évaluation est elle-même un appel LLM. Sur les mots croisés, l'article note que les évaluateurs jugent parfois des états partiels corrects comme "impossibles" en raison d'un vocabulaire peu familier — un mode d'échec cumulatif où les erreurs de l'évaluateur empoisonnent la recherche.
• Coût de calcul : ToT coûte environ 0,74 $ par cas sur le Jeu de 24, contre 0,47 $ pour le meilleur des 100 CoT. Les auteurs signalent eux-mêmes que pour les tâches que GPT-4 gère déjà bien, le surcoût n'en vaut pas la peine.

Ce qui tient la route — et ce qui ne tient pas

Le résultat central — à savoir que la recherche arborescente sur des pensées intermédiaires surpasse massivement le CoT séquentiel sur des tâches nécessitant un retour en arrière — est réel et reproductible. L'écart de 74 % contre 4 % sur le Jeu de 24 n'est pas un bruit statistique. L'explication est mécaniquement solide : une seule mauvaise équation intermédiaire dans CoT précipite le reste de la chaîne dans l'échec, tandis que ToT peut élaguer cette branche et essayer une décomposition différente.

Ce que je trouve moins convaincant, c'est la prétention à la généralisation. Les trois tâches d'évaluation sont relativement synthétiques : un casse-tête mathématique, une invite d'écriture créative avec des contraintes structurelles et un jeu de mots. Aucune d'entre elles ne ressemble aux problèmes ouverts et ambigus qui apparaissent dans les flux de travail financiers en production. Les auteurs n'évaluent également que sur GPT-4 (et GPT-3.5 pour l'ablation), nous ne savons donc pas comment ToT se comporte avec des modèles plus petits ou ajustés — et le chiffre de 19 % pour GPT-3.5 suggère que la réponse est "pas très bien".

L'échec au niveau du jeu pour les mots croisés (20 % malgré 60 % de précision par mot) pointe vers un problème plus profond : ToT est une recherche locale guidée par un évaluateur local. Il ne maintient pas de modèle de contraintes global, ce qui est précisément ce dont on a besoin pour les problèmes où les interactions entre sous-solutions sont denses. L'article suivant, Graph of Thoughts (Besta et al., AAAI 2024), formule explicitement cette critique et démontre une amélioration de la qualité de 62 % par rapport à ToT sur des tâches de tri tout en réduisant le coût de plus de 31 % — en permettant aux pensées de fusionner et de former des cycles plutôt que d'être confinées à un arbre.

Enfin, la structure des coûts compte en pratique. À b=5 avec des appels répétés à l'évaluateur, ToT est environ 15 à 20 fois plus coûteux en appels API qu'une seule passe CoT. Pour les applications sensibles à la latence ou au coût, ce n'est pas trivialement acceptable.

Pourquoi cela compte pour l'IA financière

La réponse honnête est la suivante : ToT compte surtout pour une tranche étroite de l'espace de problèmes de Beancount, mais cette tranche est bien réelle.

La tâche financière canonique pour laquelle je souhaite un retour en arrière est la classification de comptes multi-étapes avec des transactions ambiguës. Lorsqu'un LLM fait correspondre un relevé bancaire importé à un plan comptable, une seule affectation erronée au début de la chaîne (par exemple, traiter un déboursement de prêt comme un revenu) peut se transformer en une vérification de solde erronée plusieurs étapes plus tard. Dans un agent CoT, au moment où le solde échoue, le modèle n'a aucun mécanisme pour revenir sur la classification initiale. Un agent ToT pourrait revenir en arrière jusqu'à ce nœud et essayer Liabilities:Loans à la place.

De même, l'optimisation fiscale sur une année fiscale complète est un véritable problème de recherche arborescente : déduction détaillée vs déduction forfaitaire, calendrier de réalisation des plus-values, regroupement des dons de bienfaisance. Ces décisions interagissent de manière non linéaire, et vous devez évaluer plusieurs branches avant de vous engager. Le cadre BFS/DFS de ToT correspond naturellement à cette structure.

Ce en quoi ToT n'aide pas, c'est le cas dominant dans Beancount : la saisie de transactions de routine et le rapprochement. Pour une transaction qui a une contrepartie claire dans le grand livre, CoT + PAL (déléguer l'arithmétique à un interpréteur de code) est plus rapide, moins cher et déjà suffisamment précis. Utiliser ToT pour la classification de expenses:groceries, c'est utiliser un marteau-pilon pour enfoncer une punaise.

La préoccupation la plus pressante pour la sécurité de l'écriture est le problème de la fiabilité de l'évaluateur. Si l'évaluateur d'état est également un LLM, il peut se tromper — et des évaluations erronées ne se contentent pas de ralentir la recherche, elles élaguent des chemins corrects. Tout agent financier de production utilisant ToT aurait besoin d'un oracle externe (une vérification de solde, un validateur de schéma, un moteur de règles) pour servir d'évaluateur, et non d'un autre appel LLM.

Que lire ensuite

• Graph of Thoughts: Solving Elaborate Problems with Large Language Models (Besta et al., AAAI 2024) — arXiv:2308.09687. Étend ToT des arbres aux graphes arbitraires, permettant la fusion de pensées et les boucles de rétroaction. La promesse de réduction des coûts (>31 %) est directement pertinente si vous voulez un raisonnement basé sur la recherche sans le surcoût de ToT.
• Large Language Models Cannot Self-Correct Reasoning Yet (Huang et al., ICLR 2024) — arXiv:2310.01798. Un contrepoint critique : sans rétroaction externe, l'auto-correction intrinsèque dégrade les performances de raisonnement. Cela remet en question l'hypothèse selon laquelle l'évaluateur basé sur LLM de ToT est assez fiable pour guider la recherche.
• RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation (arXiv:2409.09584) — applique MCTS au lieu de BFS/DFS à la recherche de pensées, avec le retour d'exécution comme oracle externe. Le cadre de la génération de code est structurellement similaire à l'écriture dans un grand livre : vous avez une vérité terrain vérifiable (le code s'exécute-t-il ? la vérification du solde passe-t-elle ?), ce qui est précisément là où les simulations Monte Carlo apportent de la valeur.