PaperlayerView exact revision on arXiv

Source-linked AI summary

Tree Search for Language Model Agents

Jing Yu Koh, Stephen McAleer, Daniel Fried, Ruslan Salakhutdinov

arXiv:2407.01476v4cs.AIcs.CLcs.LG

TL;DR

LM agents struggle with multi-step reasoning, planning, and environmental feedback on realistic computer tasks. The paper adds inference-time best-first tree search in the actual web environment, improving success on VisualWebArena and WebArena while benefiting from greater test-time computation.

  • Problem

    LM agents struggle with multi-step reasoning, planning, and using environmental feedback when solving realistic computer tasks.

  • Method

    The paper uses inference-time best-first tree search over interactive web-environment states, guided by a multimodal language-model value function.

  • Results

    39.7% relative improvement raises GPT-4o success on VisualWebArena from 18.9% to 26.4%, while WebArena improves by 28.0% to 19.2%.

  • Takeaways & Limitations

    Search is complementary with existing LM agents and enables better performance on harder and longer-horizon web tasks as test-time computation increases.

  • Takeaways & Limitations

    Search can substantially increase execution time and language-model calls, requiring deployment-specific tuning of search parameters.

Abstract

from arXiv · show

Autonomous agents powered by language models (LMs) have demonstrated promise in their ability to perform decision-making tasks such as web automation. However, a key limitation remains: LMs, primarily optimized for natural language understanding and generation, struggle with multi-step reasoning, planning, and using environmental feedback when attempting to solve realistic computer tasks. Towards addressing this, we propose an inference-time search algorithm for LM agents to explicitly perform exploration and multi-step planning in interactive web environments. Our approach is a form of best-first tree search that operates within the actual environment space, and is complementary with most existing state-of-the-art agents. It is the first tree search algorithm for LM agents that shows effectiveness on realistic web tasks. On the challenging VisualWebArena benchmark, applying our search algorithm on top of a GPT-4o agent yields a 39.7% relative increase in success rate compared to the same baseline without search, setting a state-of-the-art success rate of 26.4%. On WebArena, search also yields a 28.0% relative improvement over a baseline agent, setting a competitive success rate of 19.2%. Our experiments highlight the effectiveness of search for web agents, and we demonstrate that performance scales with increased test-time compute. We conduct a thorough analysis of our results to highlight improvements from search, limitations, and promising directions for future work. Our code and models are publicly released at https://jykoh.com/search-agents.

1 Introduction

LM agents remain substantially behind humans on realistic web tasks, where large action spaces and long action sequences demand search and planning. The paper introduces inference-time tree search for web agents and reports substantial gains on VisualWebArena and WebArena.

  • Search addresses web tasks' large action spaces, multiple plausible action sequences, and need for efficient trajectory exploration and pruning.
  • The proposed method searches an iteratively constructed graph within the actual web environment, using environmental feedback to explore and prune trajectories.A model-based value function guides best-first search when environments lack clear rewards and win conditions.
  • The approach is presented as the first inference-time tree search algorithm shown to improve autonomous-agent success rates in realistic web environments.
  • 39.7% relative improvement raises GPT-4o success on VisualWebArena from 18.9% to 26.4%, setting a new state-of-the-art.On WebArena, search yields a 28.0% relative improvement and a 19.2% success rate.

2 Background

The paper situates its method among realistic interactive web benchmarks, language-guided agents, and classical search algorithms. Unlike prior work focused on static pages or simplified simulators, it searches the actual environment space and incorporates external feedback.

  • 2.1 Realistic Simulated Web Environments: Prior web-agent benchmarks span static-page action prediction, multimodal web understanding, simplified simulators, e-commerce simulation, conversational navigation, and multi-application computer tasks.
  • 2.1 Realistic Simulated Web Environments: Realistic web benchmarks evaluate agents in interactive environments, including tasks specified by natural-language goals and transitions governed by environment dynamics.The (Visual)WebArena environments define states, actions, observations, transitions, and task rewards for successful execution.
  • 2.2 Language-Guided Autonomous Agents: Language-guided agents commonly prompt pretrained language or multimodal models to predict actions from webpage observations, with multimodal grounding improving navigation on complex webpages.
  • 2.3 Search and Planning: Classical and neural search methods, including breadth-first, depth-first, A*, and Monte-Carlo Tree Search, have supported planning and strong performance in games.
  • 2.3 Search and Planning: The method differs from prior search work by operating over realistic website states and incorporating external environmental feedback alongside agent text outputs.

3 Method

The method treats web-task execution as navigation through an interactive state space and uses best-first search with backtracking to counteract compounding action errors. A value function scores states from task instructions and observation histories, while branching and budget parameters control exploration.

  • 3.1 Problem Formulation: Best-first search explicitly explores and backtracks among web trajectories, addressing errors that compound when agents condition only on the current observation.The search operates over the actual environment, where actions produce new states and observations.
  • 3.2 Value Function: The value function estimates expected reward for a state from the task instruction and current and previous observations because simulator state may be inaccessible.In experiments, it is implemented by prompting a multimodal language model with instructions and observation screenshots.
  • 3.3 Search Algorithm: The search uses a language model to propose candidate branches and a value function to rank states in a best-first frontier.Its depth, branching factor, search budget, and termination threshold determine the maximum search and stopping behavior.
  • 3.3 Search Algorithm: At each iteration, the algorithm expands the highest-priority frontier state, scores it, updates the best state, and terminates when the score threshold or search budget is reached.Otherwise, it generates candidate actions up to the maximum depth, executes them, adds resulting states to the frontier, and backtracks.
  • 3.3 Search Algorithm: Increasing the search tree size improves results by leveraging greater test-time computation.

4 Experiments

Experiments evaluate search across realistic web benchmarks, agent variants, and search configurations. Search substantially improves baseline success rates, with gains across models and evidence that additional search budget generally helps.

  • Results: 39.7% relative improvement raises GPT-4o + SoM success on VWA from 18.9% to 26.4%, setting a new state-of-the-art.
  • Results: 28.0% relative improvement raises GPT-4o success on WA from 15.0% to 19.2%.
  • Results: 119.7% relative improvement raises the Llama-3 caption-augmented agent’s VWA success rate from 7.6% to 16.7%.
  • Search configuration: Success rate generally increases with search budget, while the search setup uses depth d = 5, branching factor b = 5, and maximum budget c = 20.The implementation also limits execution to five actions because of compute and budget constraints.
  • Results: 32.2% relative improvement raises the text-based Llama-3 agent’s WA success rate from 7.6% to 10.1%.The results report improvements across models with different scales and capabilities.

5 Analysis

Search performance improves with larger search budgets and trees, stronger value functions, and backtracking, while analysis also exposes deployment costs and domain limitations.

  • 5.1 Ablations: 51.0% relative improvement results from increasing the search budget to c = 20, raising success from 24.5% to 37.0%.The experiments use depth d = 5 and branching factor b = 5.
  • 5.2 Success Rate Breakdown: Success generally increases as branching factor and depth enlarge the search tree, while search benefits harder tasks more than easy tasks.Easy tasks involve less planning and often already have higher baseline success rates.
  • 5.1 Ablations: GPT-4o value evaluation reaches 37.0% versus 30.0% with LLaVA, while groundtruth reward reaches 43.5% and self-consistency improves results from 28.5% to 37.0%.These results indicate remaining headroom for better value functions.
  • 5.1 Ablations: Trajectory-level reranking plateaus at 30% around seven runs, underperforming search with c ≥5 and the c = 20 result of 37.0%.At c = 5 and n = 5, the two approaches use approximately equal inference compute.
  • 5.2 Success Rate Breakdown: Search improves success across websites, with relative gains of 44% on VWA Classifieds, 45% on VWA Shopping, and 50% on the WA CMS site.The reported improvements demonstrate generalization across sites.
  • 5.3 Qualitative Results: Search supports robust multi-step planning and recovery by exploring alternatives, backtracking from failed actions, and avoiding compounding errors.Qualitative examples show successful trajectories where baseline agents loop, undo actions, or become confused.

6 Conclusion

The paper introduces inference-time search for language model agents on realistic web tasks. It reports significant success-rate improvements on the (Visual)WebArena benchmarks and identifies broader future directions.

  • Inference-time search integrates best-first tree search with language model agents to explore and evaluate multiple action trajectories on realistic web tasks.The approach is presented as general and potentially applicable to other domains or more sophisticated search algorithms.

Statement of Broader Impact

The paper discusses potential benefits and risks of more capable web agents, including accessibility, automation, misuse, privacy, economic, and fairness concerns. It also notes that inference-time value functions could encode safety constraints.

  • More capable web agents could improve accessibility and automate repetitive tasks, but the current system is not intended for practical deployment.The authors frame the work as research intended to advance agents that augment humans.
  • Deployment may enable malicious uses such as sophisticated phishing or automated attacks, requiring safeguards for misuse scenarios.
  • Web agents may scrape personal information, displace web-based roles, or amplify biases, motivating attention to privacy, worker transition, fairness, and mitigation.
  • The tree-search value function could incorporate classifiers that prevent destructive actions or violations of privacy and security policies.

A Appendix

The appendix provides additional qualitative analysis and implementation details, including the prompts used in the experiments.

  • The appendix contains further qualitative analysis, implementation details, and experimental prompts.

A.1 Qualitative Examples

Qualitative examples show search helping agents explore plausible trajectories, prune low-value paths, and recover from poor sampled actions. These examples illustrate improved robustness and successful task completion under a search budget.

  • The qualitative examples examine additional agent-with-search behavior and include a shopping wishlist task instruction.
  • Enabling exploration: A WebArena example reaches a successful trajectory with value 0.68 after exploring multiple plausible first actions.The model commits to the best trajectory found when the search budget is exhausted, without requiring a perfect value function.
  • Improving robustness: Search improves robustness by exploring alternatives and pruning trajectories with low values after poor sampled actions.In the VWA shopping example, the baseline fails while search avoids two low-value trajectories and identifies the successful one.

A.2.1 Value Function Ablations

The search procedure remains effective across different agent and value-function model choices, including weaker and open-source configurations.

  • A.2.1 Value Function Ablations: The tree search algorithm is effective across a range of model sizes and capabilities.The reported configurations include Llama-3-70B-Instruct, LLaVA-1.6-34B, and GPT-4o-mini.
  • A.2.1 Value Function Ablations: 77.6% relative improvement raises the Llama-3-70B-Instruct agent from 7.6% to 13.5% on VWA with Llama-3-70B-Instruct and LLaVA-1.6-34B value functions.This configuration provides a fully open-sourced and reproducible baseline.
  • A.2.1 Value Function Ablations: 58.2% improvement raises GPT-4o-mini performance from 9.1% to 14.4% on VWA when GPT-4o-mini serves as both agent and value function.

A.3 Implementation Details

The implementation combines model prompts, multimodal trajectory evaluation, and best-first backtracking search to explore web states under explicit depth, branching, and compute limits.

  • A.3 Implementation Details: The value function evaluates current and previous observations, using recent screenshots and finer-grained success scores to assess multi-step trajectories.It outputs scores in {0, 0.5, 1} and includes instructions for success, failure, and being on track.
  • A.3 Implementation Details: The multimodal value function may explain stronger performance on VWA than WA, while adding accessibility-tree information could improve evaluation at greater compute and API cost.
  • A.3 Implementation Details: Algorithm 1 expands up to b candidate actions to depth d within search budget c, stopping when a state reaches threshold θ or the budget is exhausted.
  • A.3 Implementation Details: The search maintains a max-priority queue of action sequences scored by the value function, then backtracks from the initial state to explore promising states.Each newly executed action extends a sequence and adds a candidate state to the frontier.
  • A.3 Implementation Details: Backtracking resets the environment to the initial state and replays actions for fidelity, preserving web state that browser back navigation may lose.This more complete reset procedure adds significant time overhead.
  • A.3 Implementation Details: Agents receive task objectives, screenshots, and accessibility-tree observations, with prompts and examples varying across text-only, caption-augmented, and screenshot-based settings.
Loading 2407.01476v4…