C5 · Recherche arborescente

Principe

Plutôt qu’un seul fil, l’agent développe plusieurs branches. Chacune est évaluée, les plus prometteuses sont prolongées et les autres abandonnées. Cela suppose un évaluateur fiable et un environnement que l’on peut remettre à zéro : l’usage reste de niche.

Le problème qu'il résout

Sur un problème combinatoire, un fil de raisonnement unique peut s’enfermer dans une impasse sans moyen de faire marche arrière.

Quand l'utiliser

• Le problème relève de la recherche combinatoire et l’on dispose d’un évaluateur de branches fiable.
• L’environnement peut être remis à zéro pour explorer plusieurs pistes depuis le même point de départ.

Quand l'éviter

• Dans la plupart des cas : une simple relance ou un vote (B4), ou une boucle de réflexion (C3), atteint une précision voisine pour bien moins cher.
• Le budget ou la latence sont contraints : le coût et le temps d’exécution sont les plus élevés du catalogue d’agent unique.

Synonymes par éditeur

• Tree of Thoughts (ToT) (Yao et al. (NeurIPS 2023))
• Graph of Thoughts (Besta et al. (AAAI 2024))
• Language Agent Tree Search (LATS) (Zhou et al. (ICML 2024))
• Multi-path plan generator (CSIRO Data61)

Patterns voisins

• B4 · Échantillonnage et vote
• C1 · Boucle agentique (ReAct)
• C3 · Réflexion

Sources

• Tree of Thoughts: Deliberate Problem Solving with Large Language Models — S. Yao et al. (NeurIPS 2023), 2023
• Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models — A. Zhou et al. (ICML 2024), 2024
• AI Agents That Matter — S. Kapoor, B. Stroebl, Z. Siegel, N. Nadgir, A. Narayanan (Princeton), 2024