Source-linked AI summary
Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models
Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, Yu-Xiong Wang
TL;DR
LM agents often rely on simple, reflexive acting processes that limit deliberate decision-making across environments. LATS integrates MCTS with LM reasoning, acting, planning, value functions, self-reflection, and external feedback, achieving strong results across programming, QA, web navigation, and math while retaining competitive reasoning performance. The method nevertheless has higher computational cost, assumes reversible environments, and may introduce safety and security risks.
Problem
Existing LM agent methods rely on reflexive acting, lack deliberate exploration and planning, and provide limited support for broad autonomous decision-making.
Method
LATS adapts MCTS to language agents, combining reasoning, acting, planning, external feedback, LM-powered value functions, and self-reflection without additional training.
Results
LATS improves decision-making across programming, interactive QA, web navigation, and math while maintaining or improving reasoning performance, including 92.7 Pass@1 on HumanEval with GPT-4.
Takeaways & Limitations
The combined use of search, interaction, and reflection provides a versatile approach to autonomous decision-making with language models.
Takeaways & Limitations
LATS has higher computational cost, assumes environments allow reverting to earlier states, and may facilitate harmful uses or create security risks.
Abstract
from arXiv · showhide
While language models (LMs) have shown potential across a range of decision-making tasks, their reliance on simple acting processes limits their broad deployment as autonomous agents. In this paper, we introduce Language Agent Tree Search (LATS) -- the first general framework that synergizes the capabilities of LMs in reasoning, acting, and planning. By leveraging the in-context learning ability of LMs, we integrate Monte Carlo Tree Search into LATS to enable LMs as agents, along with LM-powered value functions and self-reflections for proficient exploration and enhanced decision-making. A key feature of our approach is the incorporation of an environment for external feedback, which offers a more deliberate and adaptive problem-solving mechanism that surpasses the constraints of existing techniques. Our experimental evaluation across diverse domains, including programming, interactive question-answering (QA), web navigation, and math, validates the effectiveness and generality of LATS in decision-making while maintaining competitive or improved reasoning performance. Notably, LATS achieves state-of-the-art pass@1 accuracy (92.7%) for programming on HumanEval with GPT-4 and demonstrates gradient-free performance (average score of 75.9) comparable to gradient-based fine-tuning for web navigation on WebShop with GPT-3.5. Code can be found at https://github.com/lapisrocks/LanguageAgentTreeSearch
1. Introduction
Existing LM agents improve reasoning through environmental feedback but often act reflexively, without exploring alternatives or planning ahead. LATS unifies reasoning, acting, and planning through search, external feedback, and LM-based heuristics.
- Motivation: LM prompting methods can use external observations to improve reasoning and acting, but they remain reflexive and do not plan across multiple reasoning paths.Search-guided methods address planning but may lack external feedback.
- LATS: LATS expands ReAct into a search over possible reasoning and acting steps, integrating external feedback into nodes, prompts, and value heuristics.The authors report that simply combining existing methods is inadequate on HotPotQA.
- LATS: LATS adapts Monte Carlo Tree Search for language agents and uses LM-powered value functions and self-reflections to guide exploration without additional training.Language serves as the interface between framework components.
- Contributions: LATS combines search, external feedback, self-reflection, and experience-based learning across programming, interactive QA, web navigation, and math.The framework is presented as broadly applicable to autonomous reasoning and decision-making.
2. Related Work
Prior work separately develops LM reasoning, acting, and tree-based planning. LATS is positioned as combining these dimensions for broader task applicability.
- Reasoning: LM reasoning methods decompose complex inputs into intermediate language steps, but autoregressive chains can suffer from compound error propagation.This motivates methods that explore or revise reasoning paths.
- Acting: LMs have been adapted as high-level policy models for robotics, games, and text-based interactive environments.These approaches emphasize acting in external environments.
- Tree-based search: Tree-based search explores multiple outcome branches and offers an exploration-exploitation trade-off in planning and reinforcement learning.For many LM tasks, states can be revisited by resetting or restoring prior text context.
- Unified view: Table 1 defines reasoning as internal LM reasoning, acting as external decision-making, planning as search, self-reflection as LM-generated feedback, and external memory as stored text context.LATS is described as the first work incorporating designs from all three core domains.
3. Preliminaries
The preliminaries describe LM prompting, reasoning, acting, and tree search, then identify limitations motivating LATS. MCTS supplies a search mechanism based on node values, exploration, and backpropagated returns.
- Problem setting: LMs generate language sequences autoregressively from natural-language inputs and prompts, with prompting used to improve reasoning or task completion.The model maps an input prompt to an output sequence.
- Reasoning: Chain-of-thought prompting inserts sequential intermediate thoughts between an input and final answer, while Tree-of-thought explores multiple reasoning paths.Tree-of-thought uses search procedures and LM state evaluations.
- Acting: ReAct interleaves reasoning traces and permissible actions, using environment observations to improve subsequent decisions; the setup assumes reverting between iterations is feasible.The action space combines environment actions with reasoning traces.
- Limitations: Existing prompting and planning methods lack flexibility, sensibility, and adaptability because they neglect alternatives, environmental feedback, or reusable experience.These shortcomings motivate LATS as a general problem-solving agent framework.
- MCTS: MCTS repeatedly expands sampled child states, selects high-UCT children, and backpropagates episode returns to update node values.UCT combines a node value with an exploration term based on visits and the parent node.
- MCTS: MCTS normally requires an environment model that can undo prior steps, but many LM tasks permit resetting by copying historical text input.This reversibility motivates adapting MCTS to language-agent tasks.
4. Unifying Reasoning, Acting, and Planning
LATS unifies language-model reasoning and acting with planning by adapting Monte Carlo Tree Search to interactive language-agent trajectories. It combines environmental feedback, LM-based evaluation, self-consistency, and reflection to explore alternatives and refine subsequent trials.
- Adaptability: LATS supports both sequential reasoning and interactive decision-making while adapting planning to environmental conditions without additional training.The framework repurposes the pretrained LM as an agent, state evaluator, and feedback generator.
- Unified framework: LATS represents decision-making as a tree search over reasoning and acting trajectories, with each node storing the input, action sequence, and observation sequence.The framework adapts ReAct into a search over possible reasoning and acting steps and uses environment interaction rather than a world model.
- Search operations: The search performs selection, expansion, evaluation, simulation, backpropagation, and reflection until success or a computational limit.Selection uses UCT; expansion samples n actions, simulation reaches a terminal state, and trajectory outcomes update tree values.
- Value evaluation: LATS evaluates child nodes with a value function combining a self-generated LM score and a self-consistency score.The LM assigns a scalar correctness-oriented score after environmental feedback, while repeated action sampling supplies the self-consistency heuristic.
- Reflection: Failed trajectories trigger verbal self-reflection, whose stored summaries become additional context for later agent and value-function decisions.Reflections summarize reasoning or acting errors and propose alternatives for subsequent iterations.
5. Experiments
LATS is evaluated across question answering, programming, web navigation, and ablations, combining tree search with external feedback and self-reflection. It generally improves performance over prompting and related search methods, while search size increases computational cost.
- HotPotQA: LATS achieves the highest acting exact match on HotPotQA and performs best when combining CoT and ReAct prompting.The evaluation uses n = 5 nodes and k = 50 trajectories; LATS also outperforms ToT and RAP with ReAct prompting.
- HotPotQA: Combining internal and external reasoning in LATS produces the highest HotPotQA performance, showing the value of external feedback even when the language model can already answer.
- Programming: LATS achieves the highest Pass@1 accuracy on both HumanEval and MBPP, with GPT-4 HumanEval performance reaching the reported state of the art.Programming actions are complete solutions, while compiler and test-suite feedback provide observations used during search.
- WebShop: On WebShop, LATS improves both score and success rate for the same number of iterations and surpasses reinforcement-learning-based training.ReAct and Reflexion benefit less from additional semantic feedback in this complex environment, where generated reflections are often generic.
- Ablation Study and Additional Analysis: Removing self-reflection causes a 0.05 performance drop, while replacing MCTS operations with DFS causes a 0.21 drop under comparable sampling.LM scoring, the main component of LATS’s value function, is also reported as crucial for leveraging external feedback.
- Ablation Study and Additional Analysis: LATS has the same sample complexity as other tree-search methods but expands fewer nodes and uses fewer overall tokens and states upon successful search.With fewer sampled trajectories, LATS requires 3.55 fewer nodes than RAP and 12.12 fewer nodes than ToT on average.
6. Conclusion
LATS unifies reasoning, acting, and planning through deliberate search, external feedback, and self-reflection. The evaluation supports its versatility for LM decision-making without additional training, while its practicality is constrained by computational cost and state-reversion requirements.
- LATS unifies reasoning, acting, and planning by deliberately constructing trajectories with search algorithms, external feedback, and learning from experience.The framework is presented as a general approach to LM problem-solving across decision-making tasks.
- LATS maintains LM reasoning ability without additional training while harnessing LM capabilities across various decision-making tasks.
- LATS has higher computational cost than simpler prompting methods, which may limit its practicality in some situations.
- LATS assumes environments support reverting to earlier states, a capability that is not universally applicable.The paper notes that reversion is feasible in many real-world applications.
Impact Statement
LATS strengthens LM performance through environmental interaction and several rounds of linguistic reasoning, action, and reflection. These capabilities may facilitate harmful uses and raise security risks, although they may also improve interpretability and alignment potential.
- LATS enhances LM performance through interactions with an environment.
- LATS may facilitate harmful uses of LMs by improving autonomous decision-making.
- High-level linguistic reasoning and actions across repeated reflection rounds may improve interpretability and alignment potential.
- More capable LM agents may raise security risks, including executing malware.
B. More Discussion on Limitations
LATS trades additional computation for improved problem-solving and offers a tunable performance-efficiency balance. Its applicability is bounded by the need for environment reversion and by benchmarks simpler than real-world interactive environments.
- Computational cost: LATS incurs higher computational cost than ReAct or Reflexion, although it can achieve better performance and efficiency than similar methods.
- Computational cost: LATS has the same asymptotic sample complexity as ToT and RAP while expanding fewer nodes and using fewer tokens on average upon success.
- Computational cost: The number of nodes expanded at each step controls a trade-off between performance and efficiency; n = 1 matches the efficiency of ReAct with multiple trials or CoT-SC.
- Computational cost: LATS is recommended for difficult tasks such as programming or settings where performance is prioritized over efficiency.
- Assumption of environment reversion in decision-making: LATS requires environments to support reverting to earlier states because its model-free MCTS operates across prior decision states.
- Assumption of environment reversion in decision-making: The evaluated benchmarks are relatively simple compared with real-world interactive environments, and some environments may not support rollbacks easily.
C. Additional Ablations
Ablations examine exploration, depth, value evaluation, and search scaling in LATS. Results indicate that value evaluation and exploration settings materially affect performance, while reduced depth causes only a slight decline and more iterations benefit LATS relative to Reflexion.
- The ablation studies use sampling size n = 5, with maximum k = 50 trajectories for HotPotQA and k = 8 for HumanEval.
- Exploration weight: Reducing the exploration weight to 0.5 lowers HotPotQA performance, while increasing it to 2.0 does not improve performance but often accelerates convergence.The optimal exploration setting depends on the environment and state-space complexity.
- Depth: Reducing HotPotQA maximum depth from d = 7 to d = 4 produces only a slight performance drop.Most questions can be answered within four steps.
- LM value function: Removing the LM evaluation operation causes a 0.26 drop in performance.The value function supplies expected-future-reward guidance when completed-trajectory rewards are scarce and often binary.
- Performance over time: LATS scales better with more sampled trajectories than Reflexion on HumanEval.The difference is more noticeable when fewer trajectories are sampled.
D.1. HotPotQA
HotPotQA evaluates multi-hop retrieval over Wikipedia using an interactive action space, while LATS uses search-guided state evaluation to explore promising trajectories.
- Action Space: The environment supports search[entity], lookup[string], and finish[answer] actions, combined with free-form thoughts.
D.3. WebShop
WebShop tests grounded decision-making in a large simulated e-commerce environment, using reward-based task score and success rate metrics.
- Benchmark: WebShop contains over 1 million Amazon products across 5 categories and 113 subcategories, with rich product descriptions and options.
- Metrics: Task Score equals 100 × average reward, while Success Rate measures the portion of instructions receiving reward r = 1.
- Action Space: Table 12 presents the WebShop action space used for interactive shopping decisions.
D.4. Game of 24
The supplied passages describe Game of 24 evaluation and several prompting examples for question answering and code correction, including self-consistency and reflection mechanisms.
- D.4. Game of 24: Game of 24 measures whether an agent constructs 24 from four numbers using each number once, reporting success over 50 games.
- D.4. Game of 24: λ = 0.5 outperforms λ = 1 in Game of 24, indicating that the self-consistency score improves LATS performance.
- Prompting Examples: Question-answering prompts interleave Thoughts, Actions, and environmental Observations, with search, lookup, and finish as the available action types.
- Trajectory Evaluation: A correctness evaluator scores trajectories from 1 to 10 while judging the latest thought, action, and observation without extending incomplete trajectories.
- Code Reflection: Reflection-based code repair changes a subtraction operator to addition after unit-test feedback identifies the failed input case.
F.1. HumanEval function implementation example
The examples illustrate iterative correction in programming and web shopping: implementations are revised from test feedback, while shopping trajectories use search, clicks, observations, and reflection.
- Function Implementation: The programming example defines minSubArraySum as the minimum sum of any non-empty subarray and shows a nested-loop implementation.
- WebShop Trajectories: WebShop trajectories combine searches, option clicks, and observations to identify products matching requested attributes and sizes.
- WebShop Reflection: A failed shopping attempt records a score of 5 after selecting a $100 product despite a $30 budget, then proposes refining the search.
- WebShop Reflection: Reflection revises the search strategy after recognizing that the selected product exceeded the budget and did not satisfy the requested item constraints.