Single Agent Patterns: Search over Actions
Intent
When single-path generation is unreliable, explore a tree or graph of candidate reasoning/action sequences and select among them.
Introduction
For complex reasoning tasks, software engineering, or mathematical problem solving, a single linear completion path (whether standard ReAct or static Plan-Then-Execute) is highly vulnerable to early mistakes. If an AI agent commits to an incorrect assumption or selects a suboptimal tool at step one, it can wander far off course, wasting tokens and time. The Search over Actions pattern addresses this by transforming the agent's execution path from a linear sequence into a state search tree. This allows the system to systematically explore, evaluate, and backtrack over alternative action paths.
Structure of the Pattern
The Search over Actions architecture leverages classical tree and graph search algorithms, mapping them onto generative language model calls and evaluations:
- Generator (Proposer): For any given state, the model is prompted to propose multiple possible next steps (branches) rather than just one. This forms a set of candidate reasoning steps or actions.
- Evaluator (Value Function): A critic evaluates the proposed branches. This evaluation can be driven by a separate prompt (self-assessment), an external verifier (such as a unit test runner or compiler), or concrete environment feedback (e.g. HTTP status codes).
- Search Policy: An algorithm (such as Breadth-First Search (BFS), Monte Carlo Tree Search (MCTS), or Depth-First Search (DFS)) orchestrates which nodes/branches to expand next based on evaluation scores. Suboptimal paths are pruned, and promising paths are prioritized.
Two primary frameworks have defined this pattern in LLM systems: **Tree of Thoughts (ToT)** [1], which introduced structured tree searching over reasoning traces, and **Language Agent Tree Search (LATS)** [2], which unified tree-search architectures with tool execution, state tracking, and external environment feedback.
Trade-offs
Searching over action graphs provides massive resilience on complex, algorithmic tasks, but introduces significant design and operating trade-offs:
High Algorithmic Accuracy
Enables the agent to recover from reasoning dead-ends, syntax errors, or environmental failures through deterministic backtracking.
Pruning & Safety Guardrails
Allows safety and quality verifiers to veto hazardous or incorrect candidate actions before they are executed in production systems.
Multiplied Resource Costs
Exploring both breadth and depth in a search tree causes token consumption and inference latency to grow exponentially with the branching factor.
Evaluator as a Bottleneck
The entire search policy depends heavily on the critic's accuracy. A faulty value function will guide the agent down hallucinated paths.
Known Uses
Search over Actions is typically utilized in advanced problem-solving wrappers and validation harnesses:
- Tree of Thoughts: Algorithms utilizing BFS/DFS to solve complex puzzles (e.g. Game of 24, Creative Writing) that require planning ahead and backtracking [1].
- Language Agent Tree Search (LATS): Frameworks leveraging MCTS for decision-making tasks, merging deliberate search with tool-call execution and external feedback [2].
- Best-of-N Sampling: A degenerate depth-one case of this pattern, where a verifier ranks $N$ complete model completions and selects the highest scoring sequence.
References
-
[1]
Yao, S., Yu, D., Zhao, J., Shafran, I., Narasimhan, K., Yuan, Y., & Cao, Y. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. Neural Information Processing Systems (NeurIPS).
https://arxiv.org/abs/2305.10601 -
[2]
Zhou, A., Lei, K., & Wang, H. (2024). Language Agent Tree Search: Unifying Reasoning, Acting, and Planning in Language Agents. International Conference on Learning Representations (ICLR).
https://arxiv.org/abs/2310.04406