C5 · Tree search

Principle

Rather than a single thread, the agent grows several branches. Each is evaluated, the most promising are extended and the others dropped. This requires a reliable evaluator and an environment that can be reset: it remains a niche use.

The problem it solves

On a combinatorial problem, a single line of reasoning can get stuck in a dead end with no way back.

When to use it

• The problem is a combinatorial search and a reliable branch evaluator is available.
• The environment can be reset to explore several leads from the same starting point.

When to avoid it

• In most cases: a plain retry or a vote (B4), or a reflection loop (C3), reaches similar accuracy for far less.
• Budget or latency is constrained: cost and run time are the highest of the single-agent catalogue.

Synonyms by vendor

• 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)

Neighbouring patterns

• B4 · Sampling and voting
• C1 · Agent loop (ReAct)
• C3 · Reflection

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