LATS : Language Agent Tree Search — Raisonnement, Action et Planification dans un Cadre Unique

J'ai réfléchi à ce qui succède à Tree of Thoughts — si l'on peut effectuer une recherche sur les étapes de raisonnement, pourquoi ne pas aussi le faire sur les actions ? C'est exactement ce que propose LATS (Language Agent Tree Search), et c'est pourquoi je l'étudie actuellement. L'article d'Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang et Yu-Xiong Wang (ICML 2024, arXiv:2310.04406) est la synthèse la plus claire à ce jour du raisonnement, de l'action et de la planification au sein d'un cadre d'agent unique, et les résultats sont véritablement difficiles à ignorer.

L'article

Le problème central abordé par LATS est une lacune structurelle dans les travaux antérieurs sur les agents. ReAct entrelace raisonnement et action, mais ne dispose d'aucun mécanisme pour revenir en arrière et essayer un chemin différent lorsqu'une trajectoire échoue. Tree of Thoughts permet des branchements sur les étapes de raisonnement mais opère sur les connaissances internes du modèle de langage (LM) — il ne peut pas appeler d'outils ni recevoir de retours externes au cours de la recherche. Reflexion ajoute une auto-correction verbale, mais sa boucle de répétition linéaire signifie qu'il s'engage dans une nouvelle trajectoire sans explorer d'alternatives. LATS fusionne ces trois idées avec une structure de recherche arborescente de Monte Carlo (MCTS) robuste, permettant aux agents LLM d'explorer plusieurs branches, de recevoir des retours réels de l'environnement et de revenir en arrière (backtracking) lorsqu'un chemin échoue.

Le mécanisme technique repose sur une boucle MCTS en six étapes : Sélection (choix du prochain nœud à explorer via la formule UCT), Expansion (échantillonnage de n actions candidates à partir du LM), Évaluation (notation de chaque nœud avec une fonction de valeur hybride), Simulation (déroulement jusqu'à un état terminal), Rétropropagation (mise à jour des valeurs des ancêtres) et Réflexion (en cas d'échec, génération d'un résumé verbal de ce qui n'a pas fonctionné pour le stocker comme contexte). La fonction de valeur mérite une attention particulière : V(s) = λ·LM(s) + (1−λ)·SC(s), où LM(s) est l'estimation propre du LM sur la qualité de la trajectoire après avoir reçu un retour de l'environnement, et SC(s) est un score d'auto-cohérence (self-consistency) basé sur la fréquence d'échantillonnage de cette action parmi les nœuds frères. Il ne s'agit pas d'un modèle de récompense entraîné — la fonction de valeur est entièrement pilotée par les prompts.

Idées clés

• Sur HumanEval, GPT-4 + LATS atteint 92,7 % de pass@1, contre 91,0 % pour GPT-4 + Reflexion et 56,9 % pour GPT-3.5 + ReAct seul. GPT-3.5 + LATS grimpe à 83,8 %.
• Sur HotPotQA, LATS (CoT + ReAct) atteint 0,71 en correspondance exacte (exact match) contre 0,32 pour la référence ReAct — doublant plus que l'exactitude sur le raisonnement à sauts multiples (multi-hop).
• Sur WebShop (navigation web + achat), LATS obtient un score de 75,9 (taux de réussite de 38,0 %) contre 64,2 (35,0 %) pour Reflexion — un écart significatif sur une tâche nécessitant la gestion de l'état sur plusieurs pages.
• Sur le "Game of 24" (un puzzle de raisonnement pur), LATS atteint un taux de réussite de 0,44 contre 0,20 pour ToT, malgré l'utilisation du même moteur GPT-4.
• Étonnamment, LATS développe moins de nœuds pour trouver une solution que ToT (66,65 contre 84,05 nœuds en moyenne sur HotPotQA à k=50), et utilise moins de tokens (173 290 contre 210 215), même s'il semble plus coûteux en théorie.

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

Les chiffres des benchmarks sont réels et le cadre est conceptuellement propre. La formulation UCT offre un compromis exploration-exploitation fondé, ce qui manque aux approches ad-hoc BFS/DFS de ToT. L'intégration des retours environnementaux externes dans la fonction de valeur — plutôt que la pure introspection du LM — est la bonne approche, et les résultats le prouvent.

Cela dit, une hypothèse critique est enfouie dans l'article, que les auteurs reconnaissent mais ne testent pas pleinement : LATS nécessite la capacité de ramener l'environnement à un état antérieur. Sans points de sauvegarde (checkpointing), vous ne pouvez pas créer de branches dans l'arbre — une fois qu'une action est entreprise, vous êtes engagé. Les auteurs notent que pour les tâches de LM, cela est souvent gérable en « copiant-collant l'historique du texte d'entrée », mais pour les environnements d'action réels (bases de données, systèmes de fichiers, API avec effets de bord), c'est une exigence stricte que de nombreux systèmes de production ne peuvent pas satisfaire. Les résultats de WebShop, bien que meilleurs que les bases de référence, montrent que dans des environnements complexes, les auto-réflexions ont tendance à devenir génériques plutôt que ciblées — les agents peuvent rester bloqués à répéter des erreurs superficiellement différentes mais structurellement identiques. L'article le note mais ne propose pas de solution.

Il n'y a pas non plus d'étude d'ablation isolant la contribution de la structure MCTS par rapport à la conception de la fonction de valeur. Il est plausible qu'une approche de branchement plus simple avec la même fonction de valeur hybride comblerait une grande partie de l'écart, et les auteurs ne testent pas cela directement.

Pourquoi cela compte pour l'IA financière

Les grands livres Beancount constituent un environnement presque idéal pour une recherche arborescente de style LATS, pour une raison clé : chaque journal est adossé à un dépôt git. La réversion d'état — l'exigence stricte qui rend LATS peu pratique dans de nombreux contextes réels — est trivialement satisfaite par un git checkout ou un git stash. Un agent d'écriture pourrait proposer des écritures comptables candidates sur plusieurs branches, les évaluer par rapport aux contraintes du bilan (la fonction de valeur) et ne valider que le chemin ayant le score le plus élevé. Les branches ayant échoué bénéficient d'une réflexion verbale : « l'écriture saisie a violé l'invariant actif = passif + capitaux propres car le type de compte a été mal classé. »

La conception de la fonction de valeur hybride est également directement applicable. Pour un agent de comptabilité, LM(s) noterait une écriture proposée en fonction de la pertinence sémantique (cela ressemble-t-il à la bonne catégorie ?), tandis que SC(s) suivrait la cohérence avec laquelle l'agent classe les transactions passées similaires — un contrôle d'auto-cohérence naturel ancré dans l'historique même du grand livre.

L'hypothèse de réversion d'état est le seul point où je nuancerais l'analogie financière. Les grands livres réels ont souvent des effets en aval : une écriture enregistrée déclenche une facture, qui déclenche un flux de paiement. Dans ces cas, l'hypothèse de LATS s'effondre. Pour Beancount spécifiquement, où le journal est un fichier texte brut sous contrôle git et où les modifications sont locales avant tout déclencheur en aval, l'hypothèse tient — mais c'est une contrainte de conception qu'il convient de garder explicite.

Que lire ensuite

• Planification basée sur MCTS sans modèles d'environnement : "Reasoning with Language Model is Planning with World Model" (Hao et al., 2023, arXiv:2305.14992) — RAP, sur lequel LATS s'appuie directement et qu'il surpasse.
• Dans quelle mesure la fonction de valeur du LM se généralise-t-elle ? "Let's Verify Step by Step" (Lightman et al., 2023, arXiv:2305.20050) — les modèles de récompense de processus comme alternative aux fonctions de valeur basées sur les prompts.
• Planification multi-étapes sécurisée sous irréversibilité : "Decision-Making with Language Models via Successive Prompting" (Creswell et al., 2023) — une approche de planification plus simple qui évite l'exigence de réversion d'état.