Tree Search for Language Model Agents

## Abstract

Abstract 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 showcase 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 jykoh.com/search-agents .

## 1 Introduction

Building agents that can perceive, plan, and act autonomously has been a long standing goal of artificial intelligence research (Russell & Norvig, ; Franklin & Graesser, ). In recent years, the advent of large language models (LMs) with strong general capabilities has paved the way towards building language-guided agents that can automate computer tasks. However, the best LM agents today are still far worse than humans. On the realistic web benchmarks WebArena (Zhou et al., ) and VisualWebArena (Koh et al., ), humans succeed on 78% and 89% of tasks respectively, but agents — even those powered by the latest frontier models — are far worse, typically achieving success rates below 20%.
One significant bottleneck in existing agents arises from their inability to leverage test-time computation for exploration and multi-step planning. Search and planning is especially important in open ended web environments, as the potential action space (i.e., all possible actions one can take on a webpage) is much larger than in most video games or text-based simulators. There are often multiple plausible actions that must be sequenced to reach a goal, and being able to efficiently explore and prune trajectories is essential.

In artificial intelligence systems, one effective strategy for leveraging test-compute to improve results is search: iteratively constructing, exploring, and pruning a graph of intermediate states and possible solutions (Newell et al., ; Laird, ; Silver et al., ). The effectiveness of search algorithms has been shown time and time again, enabling models to achieve or surpass human-level performance on a variety of games, including Go (Silver et al., ; ), poker (Brown & Sandholm, ; ), and Diplomacy (Gray et al., ).

How might we apply search in the context of automating computer tasks, where the search space is large and — unlike games — there do not exist clear cut rewards and win conditions? Towards this goal, we propose a method to enable autonomous web agents to search over a graph that is iteratively constructed through exploration of an interactive web environment. This search procedure is grounded within the actual environment space, and is guided with environmental feedback. Our approach allows agents to enumerate a much larger number of potentially promising trajectories at test time, reducing uncertainty through explicit exploration and multi-step planning. To the best of our knowledge, this is the first time that inference-time search has been shown to improve the success rate of autonomous agents in realistic web environments. In order to handle the lack of clear cut rewards in these diverse environments, we propose a model-based value function to guide best-first search. The value function is computed by marginalizing over reasoning chains of a multimodal LM conditioned on the agent’s observations, producing finegrained scores to effectively guide search.

Our experiments show that this search procedure is complementary with existing LM agents, and enables these models to perform better on harder and longer horizon tasks. On VisualWebArena (Koh et al., ), search improves the performance of a baseline GPT-4o (OpenAI, ) agent by 39.7% relative to the baseline without search, setting a new state-of-the-art (SOTA) success rate of 26.4%. On WebArena (Zhou et al., ), search is also highly effective, contributing a 28.0% relative improvement (yielding a competitive success rate of 19.2%). We also demonstrate that our search procedure benefits from scale: achieving improved performance as the agent is alloted greater amounts of test-time computation. Our code and models are publicly released at [jykoh.com/search-agents](https://jykoh.com/search-agents).

## 2 Background

Figure: Figure 1: Our proposed search algorithm. At each iteration, we pick the next state $s_{p}$ to expand from frontier $\mathcal{F}$ and compute a score $v$ for it using the value function. Then, we add the possible next states that the agent can get to from $s_{p}$ to the frontier, and repeat the search procedure. Faded nodes indicate explored and pruned states. Blue dashed arrows indicate backtracking.
Refer to caption: x1.png

### 2.1 Realistic Simulated Web Environments

Towards the goal of developing autonomous web agents powered by large language models, several prior works focused on building evaluation benchmarks for measuring the progress of models on web tasks.
Mind2Web (Deng et al., ) is an evaluation benchmark that measures the ability of frontier models in predicting actions taken on static Internet pages. VisualWebBench (Liu et al., ) introduced a multimodal benchmark for assessing the ability of models to understand web content.
Others have looked towards simulators (as opposed to static HTML content): MiniWoB (Shi et al., ; Liu et al., ) was one of the first interactive simulators for web tasks, but consisted of simplified environments that do not directly translate into real world performance. WebShop (Yao et al., ) simulates a simplified e-commerce site with real world data. WebLINX (Lù et al., ) proposes a benchmark for tackling conversational web navigation, which involves communication between the agent and a human instructor. MMInA (Zhang et al., ) and OSWorld (Xie et al., ) propose benchmarks to measure the ability of agents to accomplish tasks by navigating across multiple computer applications. WorkArena (Drouin et al., ) is a simulated environment for tasks on the ServiceNow platform.
WebArena (WA) (Zhou et al., ) is a benchmark of 812 tasks across 5 realistic self-hosted re-implementations of popular websites (Shopping, Reddit, CMS, GitLab, Maps), each populated with real world data. VisualWebArena (VWA) (Koh et al., ) is a multimodal extension to WebArena, consisting of 910 new tasks across realistic re-implementations of 3 popular real world sites (Classifieds, Reddit, Shopping). To solve tasks in VWA, agents must leverage visual grounding and understand image inputs, providing a realistic and challenging test for multimodal agents.

**Table 1: Possible actions $A$ in the (Visual)WebArena environments. Reproduced with permission from Koh et al. ().**
| Action Type $a$ | Description |
| --- | --- |
| click [elem] | Click on elem. |
| hover [elem] | Hover on elem. |
| type [elem] [text] | Type text on elem. |
| press [key_comb] | Press a key combo. |
| new_tab | Open a new tab. |
| tab_focus [index] | Focus on the i-th tab. |
| tab_close | Close current tab. |
| goto [url] | Open url. |
| go_back | Click back. |
| go_forward | Click forward. |
| scroll [up|down] | Scroll up or down. |
| stop [answer] | End with an output. |

As the (V)WA environments are one of the most realistic and comprehensive evaluation suites for web tasks, we primarily benchmark our method on (V)WA.
We briefly describe the setting here but refer readers to Zhou et al. () for additional context. The environment $\mathcal{E}=(\mathcal{S},\mathcal{A},\Omega,T)$ consists of a set of states $S$, actions $A$ (Tab. 1), and a deterministic transition function $T:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$ that defines transitions between states conditioned on actions. Each task in the benchmark consists of a goal specified with a natural language instruction $I$ (e.g., “Find me the cheapest red Toyota car below $2000.”). Each task has a predefined reward function $R:\mathcal{S}\times\mathcal{A}\rightarrow\{0,1\}$ which measures whether an agent’s execution is successful. We implement our search algorithm on the (V)WA web simulators, but our method is fully general and can be applied to any setting with an interactive environment.

### 2.2 Language-Guided Autonomous Agents

Autonomous web agents, powered by frontier (multimodal) language models (Google, ; OpenAI, ; Anthropic, ), are the SOTA approaches for many of the above benchmarks. Kim et al. () showed that large language models can be prompted to execute computer tasks on MiniWoB++ (Liu et al., ), requiring far fewer demonstrations than reinforcement learning methods. AutoWebGLM (Lai et al., ) collects web browsing data for curriculum training and develops a web navigation agent based off a 6B parameter language model that outperforms GPT-4 on WebArena. Patel et al. () showed that a language model agent can improve its performance through finetuning on its own synthetically generated data. Pan et al. () show that introducing an automatic evaluator to provide guidance on task failure or success can improve the performance of a baseline Reflexion (Shinn et al., ) agent. Fu et al. () extracts domain knowledge from offline data and provides this to the language agent during inference, to enable it to leverage helpful domain knowledge. SteP (Sodhi et al., ) and AWM (Wang et al., ) propose methods to enable agents to dynamically compose policies to solve web tasks.

In the multimodal setting, WebGUM (Furuta et al., ) finetuned a 3B parameter multimodal language model on a large corpus of demonstrations, achieving strong performance on MiniWoB and WebShop.
Koh et al. () showed that prompting multimodal language models with a Set-of-Marks (Yang et al., ) representation enables the model to navigate complex webpages more effectively than text-only agents.
SeeAct (Zheng et al., ) demonstrated that frontier multimodal models such as GPT-4V (Yang et al., ) and Gemini (Google, ) can be grounded and prompted to solve web tasks. ICAL (Sarch et al., ) builds a memory of multimodal insights from demonstrations and human feedback, improving performance on VisualWebArena.

Our procedure is an inference-time approach that is compatible with many of these past approaches that focus on developing better base agents.

### 2.3 Search and Planning

Our method also draws inspiration from a rich history of search and planning algorithms in computer science.
Search algorithms such as breadth first search, depth first search, and A* search (Hart et al., ) have long been used in artificial intelligence systems. Newell et al. () and Laird () cast goal-oriented behavior as search through a space of possible states.
Dean et al. () and Tash & Russell () proposed planning algorithms over a limited search horizon, and employed an expansion strategy to improve plans based off heuristics about the value of information. Tash & Russell () showed that this allowed agents to provide appropriate responses to time pressure and randomness in the world. Deep Blue (Campbell et al., ), the chess engine which defeated world champion Kasparov in chess in 1997, was based on massive parallel tree search. Pluribus (Brown & Sandholm, ) leverages search to find better multiplayer poker strategies for dynamic situations.

In deep learning, search algorithms with neural network components have been instrumental in achieving superhuman performance on many games: Monte-Carlo Tree Search (MCTS) (Browne et al., ) was used to provide lookahead search, and was pivotal in the AlphaGo (Silver et al., ) and AlphaGo Zero Silver et al. () systems that achieved superhuman performance in the game of Go.
Gray et al. () performs one-step lookahead search to achieve SOTA on no-press Diplomacy.
More recently, several papers (Yao et al., ; Besta et al., ) showed the potential of applying search to large language models to introduce exploration over multiple reasoning paths, enhancing performance on text based tasks that require non-trivial planning. Others have applied MCTS (Xie et al., ; Chen et al., ; Zhang et al., ; Zhou et al., ; Hao et al., ) to improve the performance of LMs on math benchmarks (Cobbe et al., ) or simplified environments (Yao et al., ; Valmeekam et al., ).

In contrast to prior work, our setting is grounded in realistic web environments, and we search over the actual environment space (i.e., the web). This means that the search mechanics need to incorporate not just the text outputs of the agent, but also external environmental feedback from a highly complex environment.

## 3 Method

In this section, we describe the search procedure (Fig. 1) in detail.
Successfully solving a task in a web environment such as (V)WA can be interpreted as navigating to some goal state $s_{*}$ which gives a positive reward $R(s_{*})=1$. The agent starts at state $s_{0}$ (e.g., the homepage). Given a natural language task instruction $I$, the agent’s goal is to navigate to the goal state by executing a set of actions $(a_{0},\ldots,a_{t})\in\mathcal{A}$. Each action produces a new state $s_{t+1}\in\mathcal{S}$ and observation $o_{t+1}\in\Omega$ from the environment. The transition $s_{t}\rightarrow s_{t+1}$ is governed by a deterministic transition function $T:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$.

Most approaches treat this as a partially observable Markov decision process, and only condition on the current observation $o_{t}$ when predicting the next action $a_{t}$ to take. This has significant limitations: the error of the agent compounds with each step, and if an erroneous action is taken at time $t$, it cannot be easily rectified if this leads to a bad state in the future. Our approach aims to alleviate this by explicitly conducting search and backtracking to identify better trajectories. There are several components involved which we describe in the following sections: the baseline agent model (Sec. 3.1), the value function (Sec. 3.2), and the search algorithm (Sec. 3.3)

### 3.1 Agent Backbone

Most SOTA web agents are built through prompting large (multimodal) language models (Zhou et al., ; Pan et al., ; Fu et al., ; Zheng et al., ; Koh et al., ).
A pretrained language model or multimodal model $f_{\phi}$ is prompted with the current webpage observation $o_{t}$ and instructed to predict the next action $a_{t}$ to be executed. It is common to leverage prompting techniques, such as ReAct (Yao et al., ), RCI (Kim et al., ), or Chain-of-Thought (CoT) prompting (Wei et al., ), to improve the performance of the agent.
Language model agents also allow us to sample a diverse set of actions (e.g., with nucleus sampling (Holtzman et al., )), which is essential for creating plausible branches to explore during search (see Sec. 3.3).
Our proposed search algorithm can in principle be applied to any base agent. We show in Sec. 4 that search improves inference-time performance on a range of models without retraining or finetuning $f_{\phi}$.

### 3.2 Value Function

We implement a best-first search heuristic using a value function $f_{v}$ which estimates the expected reward $\mathbb{E}[R(s_{t})]$ of the current state $s_{t}$, where the ground truth goal state would provide perfect reward of 1. As the state $s_{t}$ of the simulator is not always accessible to the agent ($s_{t}$ may include private information such as database entries of the site), the value function computes the value $v_{t}$ using the current and previous observations, as well as the natural language task instruction $I$:

$$ $\displaystyle v_{t}=f_{v}(I,\{o_{1},\ldots,o_{t}\})\in[0,1]$ $$

In our experiments, the value function is implemented by prompting a multimodal language model with the natural language instruction and observations as screenshots (Sec. 4.1).

### 3.3 Search Algorithm

Our proposed search algorithm is a best-first search method loosely inspired by A* search (Hart et al., ), a classic graph traversal algorithm used widely in computer science.
We use a language model agent to propose candidate branches of the search tree. The search has hyperparameters depth $d$, branching factor $b$, and search budget $c$ which determine the maximum size of the search tree,(^1^11In Sec. 5.1 we show that increasing the size of the search tree improves results at the expense of using increased compute for exploration.) and termination threshold $\theta$.
The search procedure is summarized in Fig. 1. We describe it in detail in the following paragraphs and provide the formal algorithm in Appendix A.4.

At time $t$ in the execution trajectory, the agent has previously executed a sequence of actions to arrive at the current state $s_{t}$. We begin the search algorithm from $s_{t}$ by initializing the frontier $\mathcal{F}\leftarrow\{\}$ (implemented as a max priority queue) which holds the set of states that we plan to evaluate, the best state found so far $\hat{s}_{t}\leftarrow s_{t}$, the score of the best sequence $\hat{v}_{t}\leftarrow 0$, and the search counter $s\leftarrow 0$.

At each iteration of the search process, we extract the next state from the frontier, $s_{p}\leftarrow\text{pop}(\mathcal{F})$.
We use the value function to compute the score for state $s_{p}$ (with observation $o_{p}$ and previous observations $o_{1},\ldots,o_{p-1}$):

$$ $\displaystyle v_{p}=f_{v}(I,\{o_{1},\ldots,o_{p}\})$ $$

Then, we increment the search counter $s$, and if $v_{p}$ is higher than the current best score $\hat{v}_{t}$, we update it and our best state accordingly:

$$ $\displaystyle s$ $\displaystyle\leftarrow s+1$ $\displaystyle\hat{s}_{t}$ $\displaystyle\leftarrow\begin{cases}s_{p}&\text{if }v_{p}>\hat{v}_{t}\\ \hat{s}_{t}&\text{otherwise}\end{cases}$ $\displaystyle\hat{v}_{t}$ $\displaystyle\leftarrow\max(\hat{v}_{t},v_{p})$ $$

If $v_{p}\geq\theta$ (i.e., the agent is likely to have found a goal state) or $s\geq c$ (the search budget has been exceeded), we will terminate the search and navigate to the best state $\hat{s}_{t}$ found thus far.
Otherwise, if the current branch does not exceed the maximum depth (i.e., $|(s_{0},\ldots,s_{p})|<d$), we will generate plausible next actions for branching by obtaining $b$ candidate actions $\{a_{p}^{1},\ldots,a_{p}^{b}\}$ from the language model agent $f_{\phi}$.
For each $i$, we execute $a_{p}^{i}$ and add the resulting state $s_{p}^{i}$ to the frontier with the score of the current state(^2^22We opt for this approach instead of immediately computing the value for resulting states $s_{p}^{i}$ as immediate evaluation requires more backtracking calls, which would incur much more overhead in the (V)WA simulators.):

$$ $\displaystyle\mathcal{F}$ $\displaystyle\leftarrow\mathcal{F}\cup(v_{p},s_{p}^{i})\qquad\text{ for }i=1, \ldots,b$ $$

This concludes one iteration of search. If both of the termination conditions have not been reached, we backtrack and repeat this process for the next best state from the updated frontier $\mathcal{F}$.

## 4 Experiments

We run experiments on the full set of 910 VisualWebArena (VWA) and 812 WebArena (WA) tasks. These tasks are distributed across a set of diverse and realistic web environments: a Classifieds, Reddit, and Shopping environment for VWA, and a Shopping, CMS, Reddit, GitLab and Maps environment for WA.

### 4.1 Implementation Details

##### Baseline agent models

Our search algorithm is compatible with most off-the-shelf language model agents. In this work, we test it with simpler, more general, prompt-based agents, and leave incorporation of our method with more performant methods that incorporate domain-specific techniques (Fu et al., ; Sodhi et al., ) for future work. We run several prompt-based agent baselines with different input formats (full prompts provided in the appendix):

- •
Multimodal SoM: For multimodal models that accept multiple image-text inputs, such as GPT-4o (OpenAI, ) (gpt-4o-2024-05-13), we run the multimodal agent from Koh et al. () with the same prompt. We similarly apply a preprocessing step to assign a Set-of-Marks (SoM) (Yang et al., ) representation to the webpage. This highlights every interactable element on the webpage with a bounding box and a unique ID. The input to the agent is a screenshot of the SoM-annotated webpage, and a text description of the elements on the page with their corresponding SoM IDs.
- •
Caption-augmented: For base models that are not multimodal (e.g., Llama-3-70B-Instruct (Dubey et al., )), we run the caption-augmented agent with the same prompt from Koh et al. (). We generate captions for each image on the webpage using an off-the-shelf captioning model (in our case, BLIP-2; Li et al. ). The accessibility tree(^3^33[https://developer.mozilla.org/en-US/docs/Glossary/Accessibility_tree](https://developer.mozilla.org/en-US/docs/Glossary/Accessibility_tree)) representation of the webpage observation is extracted and provided to the language model as its input observation at each step.
- •
Text-only: On WebArena (which does not require visual grounding), we run text-only agents using the prompt from Zhou et al. (), for both GPT-4o and Llama-3-70B-Instruct. Similar to the caption-augmented baseline, this model uses an accessibility tree representation of the current webpage as its input observation (but this text-only baseline does not include image captions).

##### Search parameters

We run these agents with and without search. Our search parameters are set to $d=5,b=5,c=20$, and we stop execution after a maximum of 5 actions. We enforce these constraints due to compute and budget limitations, though we expect that increasing these parameters is likely to further improve results (see Sec. 5.1 for results on scaling search parameters). We note that the fairly strict limitations on maximum actions imply that there are certain tasks that are intractable (e.g., VWA tasks with “hard” action difficulty usually require humans to execute 10 or more actions to complete). Despite this, our results show that GPT-4o with search capped at 5 max actions still substantially outperforms the GPT-4o baseline (without search) with 30 max actions.

##### Obtaining actions

We sample actions using nucleus sampling (Holtzman et al., ) with a temperature of 1.0 and top-$p$ of 0.95 for all experiments. At each step of execution, we generate 20 outputs from the model by prompting it with CoT reasoning (Wei et al., ), and aggregate the count of the action candidates. We use the top-$b$ actions with the highest counts for branching.

##### Value function

As detailed in Sec. 3.2, we require a value function which scores the likelihood that the current state $s_{t}$ is a goal state. We implement the value function by prompting a multimodal language model
with the task instruction $I$, screenshots of the agent’s trajectory, previous actions the agent took, and the current page URL. The full prompt is provided in Appendix A.3.2. The multimodal LM is instructed to output whether the current state is a success, a failure, and if it’s a failure, whether it is on a trajectory towards success. These outputs are assigned values of 1, 0, and 0.5 respectively (and 0 for invalid output).
In order to get more finegrained and reliable scores, we leverage ideas from self-consistency prompting (Wang et al., ), and sample multiple reasoning paths by prompting the multimodal LM with CoT (Wei et al., ). We sample 20 different paths from the GPT-4o model using ancestral sampling (temperature of 1.0 and top-$p$ of 1.0).
The final value assigned to state $s_{t}$, used in the best-first search heuristic, is computed by averaging the values from each of the 20 reasoning paths.
In our implementation, calling the value function is significantly cheaper than predicting the next action, as action prediction consumes more input tokens for few-shot examples and the representation of the page.
We estimate the API cost of the GPT-4o SoM agent for action prediction to be approximately $2\times$ that of computing the value.

### 4.2 Results

**Table 2: Success rates (SR) and relative change ($\Delta$) for baseline models and models that employ search on the VisualWebArena (VWA) (Koh et al., ) and WebArena (WA) (Zhou et al., ) benchmarks. We also show other published approaches. Search substantially improves our baseline models, setting a new state-of-the-art on VWA.**
|  | Agent Model | Max Steps | No Search | + Search | $\Delta$ |
| --- | --- | --- | --- | --- | --- |
| VWA | Llama-3-70B-Instruct + captions (Koh et al., ) | 30 | 9.8% | - | - |
| GPT-4o + SoM (Koh et al., ) | 19.8% | - | - |  |  |
| ICAL (Sarch et al., ) | 23.4% | - | - |  |  |
| Llama-3-70B-Instruct + captions | 5 | 7.6% | 16.7% | +119.7% |  |
| GPT-4o + SoM | 18.9% | 26.4% | +39.7% |  |  |
| WA | GPT-4o (Zhou et al., ) | 30 | 13.1% | - | - |
| GPT-4 + Reflexion (Pan et al., ) | 15.6% | - | - |  |  |
| AutoWebGLM (Lai et al., ) | 18.2% | - | - |  |  |
| AutoEval (Pan et al., ) | 20.2% | - | - |  |  |
| BrowserGym (Drouin et al., ) | 23.5% | - | - |  |  |
| SteP (Sodhi et al., ) | 35.8% | - | - |  |  |
| Llama-3-70B-Instruct | 5 | 7.6% | 10.1% | +32.3% |  |
| GPT-4o | 15.0% | 19.2% | +28.0% |  |  |

Our results are summarized in Tab. 2. Introducing search increases success rate substantially across the board. Search improves the success rate of the baseline GPT-4o + SoM agent on VWA by 39.7% relatively (increasing from 18.6% to 26.4%), setting a new state-of-the-art on the benchmark. On WA, introducing search to the GPT-4o agent improves the success rate substantially as well, increasing it by 28.0% relatively (15.0% to 19.2%). This is competitive with other prompt-based agents on WA, but in future work it will be interesting to explore introducing search to stronger baseline agents that incorporate domain-specific techniques, such as SteP (Sodhi et al., ) or AutoGuide (Fu et al., ).

With weaker base models, we also observe substantial improvements.
For the Llama-3 caption-augmented agent on VWA, introducing search improves the success rate on VWA by 119.7% relative to the baseline (7.6% to 16.7%). With search, Llama-3-70B-Instruct achieves success rates that are close to the best frontier multimodal models that do not use search.
On WebArena, we also see a substantial relative improvement of 32.2% for the text-based Llama-3 agent (7.6% to 10.1%).
The strong performance of the Llama-3-70B-Instruct agent with search can prove to be a cost effective agent model for iteration in future work that requires access to model internals. These results over a variety of model scales and capabilities demonstrate the generality and effectiveness of our approach.

## 5 Analysis

### 5.1 Ablations

Figure: Figure 2: Success rate on a subset of 200 VWA tasks with search budget $c$. $c=0$ indicates no search is performed. Success rate generally increases as $c$ increases.
Refer to caption: x2.png

We conduct several ablation experiments on a subset of 200 tasks from VWA (100 Shopping tasks, 50 Reddit task, and 50 Classifieds tasks).

##### Search budget

We plot the success rate of the GPT-4o agent with search limited to varying budgets $c\in\{0,5,10,15,20\}$ in Fig. 2. All experiments are conducted with search parameters of depth $d=5$ and branching factor $b=5$. The search budget specifies the maximum number of node expansions performed at each step. For example, a search budget of 10 indicates that at most 10 nodes will be expanded, after which the agent will commit to and execute the trajectory with the highest value.
We observe that success rate generally increases as search budget increases. Notably, performing even very small amounts of search ($c=5$) substantially improves success rate by 30.6% relative to not doing search (24.5% to 32.0%). When the budget is increased to $c=20$, this improves success rate by 51.0% relative to not doing search (from 24.5% to 37.0%), highlighting the benefit of scaling the search budget. Running experiments with an even greater search budget to evaluate scaling trends would be a promising future direction to explore.

##### Search depth and breadth

We run an ablation experiment varying the search branching factor $b$ and maximum depth $d$. The results are summarized in Tab. 3. We observe that in general, success rate increases as the size of search tree increases (along both $b$ and $d$ dimensions). In particular, scaling both $b$ and $d$ is necessary to achieve strong performance.

**Table 4: Success rate of the GPT-4o agent with different value functions.**
| Value Function | SR ($\uparrow$) |
| --- | --- |
| None (no search) | 24.5% |
| LLaVA (w/ SC, $n=20$) | 30.0% |
| GPT-4o (no SC) | 28.5% |
| GPT-4o (w/ SC, $n=5$) | 32.5% |
| GPT-4o (w/ SC, $n=20$) | 37.0% |
| Groundtruth | 43.5% |

##### Varying the value function

We ablate the multimodal model used for the value function, swapping out GPT-4o for (1) the LLaVA-v1.6-34B (Liu et al., ) multimodal model prompted zero-shot (with just the current observation) and (2) the groundtruth reward from VWA (which is a sparse reward signal that returns either 0 or 1), and (3) GPT-4o without self-consistency. The results are summarized in Tab. 4. We find that the GPT-4o value function significant outperforms the LLaVA model, improving the result of the agent from 30.0% to 37.0%. The groundtruth reward function achieves a success rate of 43.5%. These results suggest that there is still significant headroom in improving the search algorithm by training better value functions. We also observe that self-consistency is essential for the performance of search ($28.5\%\rightarrow 37.0\%$), which we attribute to it enabling marginalization over multiple reasoning chains, reducing noise during state evaluation.

### 5.2 Success Rate Breakdown

**Table 5: Success rates and relative change ($\Delta$) of the GPT-4o agent on VWA tasks of different action difficulty levels.**
| Difficulty | No Search | Search | $\Delta$ |
| --- | --- | --- | --- |
| easy | 34.2% | 42.3% | +24% |
| medium | 12.7% | 22.2% | +75% |
| hard | 10.2% | 14.9% | +47% |

##### Success rate by task difficulty

The VWA benchmark includes labels for the action difficulty of each task. These labels are human annotated, and roughly indicate the number of actions a human would need to take to solve the tasks: easy tasks require 3 or fewer actions, medium tasks require 4–9 actions, and hard tasks demand 10 or more. These guidelines are approximate and devised by the human annotators of VWA, so there may exist more optimal solutions in practice. The increase in success rate from introducing search is summarized in Tab. 5. Introducing search improves performance across all difficulty levels, but it introduces much larger gains on tasks of medium action difficulty, with a relative increase of 75% in success rate (from 12.7% to 22.2%). We hypothesize that this is because our search parameters (max depth $d=5$) are beneficial for a large proportion of medium difficulty tasks. Conversely, achieving even better performance on hard tasks may require search over deeper trees. Easy tasks likely do not benefit as much from search, as they generally involve less multi-step planning (some can be solved with 1 or 2 actions), and baselines already have higher success rates.

Figure: Figure 3: Search can improve the robustness of agents by filtering out bad actions. Shown above is a trajectory for VWA classifieds task #48 where greedily picking the first sampled actions would have led to a failure (by taking the path in the first row). Search avoids this failure mode by exploring and pruning less promising paths, ultimately committing to the highlighted trajectory.
Refer to caption: x3.png

**Table 6: Success rates and relative change ($\Delta$) of the GPT-4o agent on VWA websites.**
| Website | No Search | Search | $\Delta$ |
| --- | --- | --- | --- |
| Classifieds | 18.4% | 26.5% | +44% |
| Reddit | 17.1% | 20.5% | +20% |
| Shopping | 20.0% | 29.0% | +45% |
| Overall | 18.9% | 26.4% | +40% |

##### Success rates by website

Tables 7 and 7 summarize the success rates across the various websites in the VWA and WA benchmarks. We observe an improvement in success rates across the board, demonstrating that our method generalizes across sites.
Specifically, the increase is most substantial on the Classifieds and Shopping sites in VWA, with relative increases of 44% and 45%, respectively. Similarly, the CMS site in the WA benchmark shows a significant relative improvement of 50%.

### 5.3 Qualitative Results

In this section, we discuss some qualitative examples of agent trajectories, and identify various failure modes that are solved when incorporating search.

##### More robust multi-step planning

Many tasks in VWA and WA require an agent to keep a persistent memory of multiple previous actions and observations. A common failure mode amongst agents without search is that they tend to undo previous actions, or get stuck in loops (see Appendix C.4 of Koh et al. ). An example for VWA shopping task #256 is shown in Fig. 1, where the agent is tasked to add two different types of canned fruit from the same brand to the comparison list. The baseline agent successfully adds the first item, but fails to navigate to the second item, as it returns to the homepage in step 3 and gets confused. This is an example of compounding error leading to overall task failure, which is fairly common in existing baseline agents without search.

When search is introduced, the agent explores other plausible trajectories and backtrack when those eventually result in failure:
the same GPT-4o agent with search is able to find a successful multi-step trajectory for the same task, which involves adding the first item (action #1 in Fig. 1), typing in a search query (action #6), and adding the correct second item to the comparison list (action #9).

##### Resolving uncertainty

An inherent issue with sampling actions from language models is that we are sampling from a distribution over text, and the first sample we generate may not always be the best action to take in the environment. Search allows us to evaluate each generated action concretely by executing it in the simulator, and use the received environmental feedback to make better decisions. One example is VWA classifieds task #48 (Fig. 3), which is to find a post containing a particular image. If the agent executes the first sampled action at every step (i.e., the sequence in the top row), it results in failure. Search allows the agent to enumerate all possibilities by executing plausible actions and receiving environment feedback, which allows it to select the best (and in this case, successful) trajectory.

### 5.4 Limitations

While we have shown that introducing search to language model agents achieves promising results on web tasks, it does come with some practical limitations:

##### Search can be slow

Introducing search allows us to expend more compute at inference time to extract stronger results from the baseline LM agent. However, this results in trajectories taking significantly longer to execute, as the agent has to perform more exploration and hence more inference calls to the LM.
For example, a search budget of $c=20$ implies that an agent with search could potentially expand up to 20 states in each search iteration, which would use up to $20\times$ more LM calls than an agent without search. Research on improving the efficiency and throughput of machine learning systems (Leviathan et al., ; Dao et al., ; Dao, ) will likely help with optimizing this, but for practical deployment one may need to carefully set the search parameters $b$, $d$, and $c$ to balance between achieving better results and overall time spent completing a task.

In our approach, we implemented search by keeping track of the sequence of actions required to get to a state. During backtracking, we reset the environment and apply the same sequence after resetting the environment. This is necessary, as naively executing the go_back action (Tab. 1) may discard important information on the page, such as the scroll offset and already entered text.
However, these environment calls for backtracking introduce additional overhead, which may be restrictive for deployment if calls to the environment are expensive.

##### Destructive actions

For real world deployment, we will need to restrict the search space to actions that are not destructive. Destructive actions are defined as actions that will irreversibly change the state of the website and are difficult to backtrack from. For example, placing an order on an e-commerce site is typically very difficult to automatically undo.
One way to address this is to introduce a classifier that predicts when certain actions are destructive, and prevent node expansion for those states. If we have specific domain knowledge about the downstream application (e.g., we know certain pages should be off limits), such rules can be manually enforced with high accuracy.
One advantage of tree search is that it is easier to incorporate such a constraint: it can be directly integrated into the value function to prevent execution of dangerous actions.
Another direction to handle this would be to train a world model (Ha & Schmidhuber, ) that we can use for simulations during search. Search may also be more easily implemented in offline settings where actions are non-destructive as they can always be undone or reset, such as programming (Jimenez et al., ; Yang et al., ) or Microsoft Excel (Li et al., ).

## 6 Conclusion

In this paper, we introduced an inference-time search algorithm designed to enhance the capabilities of language model agents on realistic web tasks. Our approach integrates best-first tree search with LM agents, enabling them to explore and evaluate multiple action trajectories to achieve superior performance on web tasks. This is the first time search has been shown to significantly improve the success rates of LM agents on realistic web environments, as demonstrated on the (Visual)WebArena benchmarks. Our search procedure is general, and it will be valuable to apply it to other domains in future work. We believe that inference-time search will be a key component for building capable agents that can plan, reason, and act autonomously to perform computer tasks.

#### Acknowledgments

We thank Andy Liu, Saujas Vaduguru, Zhiruo Wang, Alex Xie, Shuyan Zhou, and many others for helpful feedback and discussions on previous versions of this paper, and Santiago Cortes-Gomez for infrastructure support. We thank Wendy Kua for helping with the figures.

## Ethics Statement

As an active area of machine learning research, language model web agents present both opportunities and potential ethical considerations. Improved web agents could improve accessibility for users with disabilities, automate repetitive or tedious tasks, and potentially democratize access to complex web platforms. Our search method contributes towards making such benefits more reliable and widely available by improving the robustness and success rate of language model agents. However, we acknowledge several potential ethical considerations:

- •
Intended uses. Our work is a research product that aims to advance the development of web agents that can help augment humans by automating computer tasks. It is not in its current state intended for deployment in practical scenarios. However, we acknowledge that as they get better, enhanced web agents might be leveraged for malicious purposes, such as more sophisticated phishing attempts or automated attacks on web services. As with all emerging technologies, developers deploying these technologies should incorporate consider potential misuse scenarios and implement the appropriate safeguards.
- •
Economic impact. As web agents become more capable, there may be concerns about job displacement for roles that involve web-based tasks. We believe that web agents will augment human capability, and will be able to improve the overall quality of work by automating tedious computer tasks. However, as this technology starts being deployed more broadly, researchers and developers should proactively consider how to manage this transition and support affected workers.
- •
Fairness and bias. As with any modern AI system, web agents may inherit or amplify biases present in their training data or underlying language models. Care must be taken to assess and mitigate unfair treatment or representation of different user groups. As an inference time algorithm, our approach can easily be applied to any off-the-shelf language model, and will likely benefit from upstream efforts on language model safety and alignment.

Our approach also potentially provides a framework that could help address some of these concerns. The value function in our tree search algorithm offers a natural way to encode safety constraints at inference time. For example, classifiers can be integrated with our proposed value function to prevent destructive actions or violations of privacy and security policies. We encourage further research into the ethical implications of web agents, and the development of guidelines and best practices for the responsible deployment of web agents.

## Reproducibility Statement

To ensure reproducibility of our results, we provide details of the tree search algorithm within this paper (Sec. 3.3) as well as more formally in Appendix. A.4. The details of the models used are also provided in Sec. 4.1. All other prompts and implementation details necessary to reproduce our results are provided in Appendix A.3. In order to ensure long term reproducibility, we also provide results for a setting with open model weights for longer term reproducibility, the Llama-3 agent with the LLaVA value function (Appendix. A.2.1), in addition to the API-based agents (which at present achieve higher performance than open sourced alternatives). All of our code and experiment launch scripts are open sourced and made publicly available on GitHub at [jykoh.com/search-agents](https://jykoh.com/search-agents).

## Appendix A Appendix

In the appendix we provide further qualitative analysis and implementation details, including the prompts used in our experiments.

### A.1 Qualitative Examples

We discuss several other qualitative examples from the agent with search.

Figure: Figure 4: WA task #14 is an example where performing more exploration helps the model to identify a trajectory that is likely to be more successful than others.
Refer to caption: x4.png

##### Enabling exploration

A significant advantage of models with search is their ability to explore larger parts of the environment compared to models without search. Fig. 4 part of the search tree for WebArena task #14 (in the CMS environment), where the model is able to take multiple plausible actions at the first step (actions 1, 2, 3, and 4 in the graph), and expand the search tree to find the best trajectory ($3\rightarrow 5\rightarrow 6\rightarrow 10$, which achieves the highest value of 0.68). In this case, the model terminates after hitting the search budget $c$ (rather than finding a state with value of 1.0), committing to the best found trajectory thus far, which is successful. This also highlights that our value function does not need to be perfect for search to be helpful.

Figure: Figure 5: VWA shopping task #96 is another example where search allows the model to be more robust to sampling bad actions. On this task, the baseline agent without search failed, but the agent with search is able to prune less promising trajectories (faded nodes in the figure) to identify the successful one.
Refer to caption: x5.png

##### Improving robustness

As discussed in Sec. 5.3, the baseline agent can be prone to selecting bad samples from the language model due to randomness from nucleus sampling. Search allows the agent to explore each possibility and identify the best trajectories. VWA shopping task #96 (shown in Fig. 5) is another example. The baseline agent fails on this task, but the agent with search avoids the first two trajectories (ending at actions 3 and 4) due to low values assigned after exploring the subsequent states. It is able to prune these and identify a successful trajectory (highlighted in Fig. 5).

### A.2 Additional Ablations

#### A.2.1 Value Function Ablations

**Table 8: Success rates (SR) and relative change ($\Delta$) for baseline models and models that employ search on the VisualWebArena (VWA) (Koh et al., ) and WebArena (WA) (Zhou et al., ) benchmarks. We also show other published approaches. Search substantially improves our baseline models, setting a new state-of-the-art on VWA.**
|  | Agent Model | Value Function | Max Steps | No Search | + Search | $\Delta$ |
| --- | --- | --- | --- | --- | --- | --- |
| VWA | Llama-3-70B-Instruct (Koh et al., ) | - | 30 | 9.8% | - | - |
| GPT-4o + SoM (Koh et al., ) | - | 19.8% | - | - |  |  |
| Llama-3-70B-Instruct + captions | LLaVA-1.6-34B | 5 | 7.6% | 13.5% | +77.6% |  |
| Llama-3-70B-Instruct + captions | GPT-4o | 7.6% | 16.7% | +119.7% |  |  |
| Llama-3.1-70B-Instruct + captions | GPT-4o | 9.1% | 16.2% | +78.0% |  |  |
| GPT-4o-mini + SoM | GPT-4o-mini | 9.1% | 14.4% | +58.2% |  |  |
| GPT-4o + SoM | GPT-4o | 18.9% | 26.4% | +39.7% |  |  |
| WA | GPT-4o (Zhou et al., ) | - | 30 | 13.1% | - | - |
| GPT-4 + Reflexion (Pan et al., ) | - | 15.6% | - | - |  |  |
| AutoWebGLM (Lai et al., ) | - | 18.2% | - | - |  |  |
| AutoEval (Pan et al., ) | - | 20.2% | - | - |  |  |
| BrowserGym (Drouin et al., ) | - | 23.5% | - | - |  |  |
| SteP (Sodhi et al., ) | - | 35.8% | - | - |  |  |
| Llama-3-70B-Instruct | GPT-4o | 5 | 7.6% | 10.1% | +32.3% |  |
| GPT-4o | GPT-4o | 15.0% | 19.2% | +28.0% |  |  |

In Sec. 4.2 of the main paper, we experimented with using gpt-4o as our value function. In Tab. 8, we present results using different language models as the agent models and the value functions. We observe that our tree search algorithm is effective across a range of different model sizes and capabilities. In particular, our approach applied to the Llama-3-70B-Instruct and LLaVA-1.6-34B value function yields a 77.6% relative improvement over the baseline Llama-3-70B-Instruct agent on VWA (7.6% to 13.5%), and is a fully open sourced and reproducible baseline. For the GPT-4o-mini model (a relatively weaker model compared to GPT-4o) we also observed improvements when it is used as both the agent model and the value function, improving performance by 58.2% over the no-search baseline on VWA (9.1% to 14.4%).

#### A.2.2 Comparison to Trajectory-Level Reranking

Figure: Figure 6: Success rate of a trajectory re-ranking approach compared to our approach.
Refer to caption: x6.png

An alternative to tree search would be to generate multiple trajectories, re-rank, and commit to the best one as scored by the value function, similar to the methods proposed in Chen et al. () and Pan et al. () without their Reflexion (Shinn et al., ) component. This is a less practical method, as it is harder to prevent destructive actions from being executed (see Sec. 5.4 for more discussion) as the agent is required to take the trajectory to completion before it can be evaluated. It is also a more limited form of search, as it only considers entire trajectories and cannot backtrack to prune bad branches. Nevertheless, we perform an ablation where we sample $n$ trajectories from the GPT-4o agent (with nucleus sampling (Holtzman et al., ) at each step using a temperature of 1.0 and top-$p$ of 0.95) and use the same value function to re-rank the trajectories, picking the best one out of $n$.

We observe that this re-ranking baseline starts to plateau around 7 runs, which achieves a success rate of 30%. This underperforms our approach with search budget $c\geq 5$ (Fig. 2).
It is also substantially worse than our approach with $c=20$, which achieves a success rate of 37.0% on the ablation subset.

### A.3 Implementation Details

#### A.3.1 Language Model Agents

Figure: Figure 7: System message from Koh et al. () in our SoM agent.

Figure: Figure 8: In-context examples and prompt adopted from Koh et al. () for our SoM agents. The webpage screenshots with SoM are added to the end of each round of the example_user dialogue.

Figure: Figure 9: In-context examples and prompt used for the caption-augmented Llama-3 agent. The webpage accessibility tree is added to the end of each round of the example_user dialogue.

Figure: Figure 10: In-context examples and prompt used for the text-only GPT-4o agent on WebArena. The webpage accessibility tree is added to the end of each round of the example_user dialogue.

For all experiments, we use a webpage viewport width of 1280, a viewport height of 2048, and truncate text observations to 3840 tokens. We sample from models using nucleus sampling with a temperature of 1.0 and a temperature of 1.0 and a top-p of 0.95. The system message used in all our experiments is provided in Fig. 7. This instructs the agent with the guidelines for the web navigation task, and list out all the possible actions that it can perform.

For the GPT-4o agent on VWA, we use the same prompt with SoM prompting from Koh et al. (), reproduced in Fig. 8. The model is provided with 3 in-context examples. A similar prompt (without the image screenshots) is used for the caption-augmented Llama-3-70B-Instruct agent which takes the caption-augmented accessibility tree as input (shown in Fig. 9).
On WA, the agents take the accessibility tree as input, and we use the same prompt from Zhou et al. () that includes 2 in-context examples (reproduced in Fig. 10).

#### A.3.2 Value Function

Figure: Figure 11: System message and prompt used for the value function. Blue text indicates items that will be replaced by image content during the call to the value function.

As described in Sec. 3.2, we implement the value function $f_{v}$ by prompting a multimodal language model with all current and previously seen observations $\{o_{1},\ldots,o_{p}\}$. We use a prompt similar to the one from Pan et al. (), but make several modifications:

- •
Instead of just the current screenshot, we include the last-$d$ screenshots of the evaluated trajectory, to enable the value function to more accurately compute success or failure for tasks that involve multi-step reasoning (e.g., whether the final observation corresponds to the second item in the second row of the second last observation).
- •
We modify the instructions to include more detailed instructions about what constitutes a failure or a success crtieria. This is necessary as our search occurs over a denser graph (compared to generating and re-ranking trajectories), and requires a more accurate value function. We refer readers to Chen et al. () for more discussion.
- •
Rather than a binary output, we instruct the model to produce whether the given observations have succeeded at the task or failed. If it fails, we further prompt the model to output if it is possibly on the right track to success. This allows us to collect scores in $`\{0,0.5,1\}$, enabling more finegrained value outputs (in addition to the averaging of multiple reasoning paths described in Sec. 4.1).

The full system message and prompt for the value function is provided in Tab. 11. We also note that our value function is heavily visual, which may be one explanation for why our method is more effective on the multimodal VWA benchmark than on WA (Sec. 4). Including more finegrained textual information about the trajectory on top of the screenshots, such as the accessibility tree representations of each page, may further improve its performance (at greater compute and API cost).

### A.4 Search Algorithm

Figure: Algorithm 1 Our proposed search algorithm at step $t$

Our search procedure described in Sec. 3.3 is summarized in Algorithm 1.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. How does the search algorithm perform on tasks with very high action complexity or longer required sequences? Are there any indications that increasing the search budget might lead to diminishing returns in such cases?

2. Can the authors provide more details on how the environment resets are managed during backtracking? Specifically, what challenges arise, and how might these affect the agent’s efficiency?

3. What were the key considerations in selecting the self-consistency technique for the value function? How does this compare to alternative approaches like reinforcement learning-based value functions?

4. Are there any safeguards or heuristics incorporated to prevent the agent from becoming stuck in specific repetitive or irrelevant actions during search?
soundness: 3
strengths: 1. Experiments are conducted on several practical benchmark datasets such as VisualWebArena and WebArena, showcasing its effectiveness in web-based tasks.

2. The search algorithm is compatible with a variety of LM agents and does not require fine-tuning or retraining.

3. Extensive hyper-parameter analysis is provided.
summary: This paper introduces a tree search algorithm for improving the performance of language model agents. By implementing a best-first search approach that operates in the environment's actual state space, the authors enable LM agents to achieve multi-step planning and exploration during inference. Experiments are conducted on VisualWebArena and WebArena benchmarks with improved performance, showing that introducing search allows agents to perform better on complex tasks.
weaknesses: 1. The search algorithm demands significant computational resources due to the increased number of environment interactions. This may limit its practical applicability in real-time or resource-constrained environments.

2. The success of the best-first search depends heavily on the quality of the value function. Although self-consistency techniques were used, further improvements in the value function are needed for optimal performance.

3. The paper briefly addresses the issue of destructive actions in search trajectories but lacks a comprehensive solution. This is a critical consideration for deployment in real-world web environments where irreversible actions are possible.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 2
questions: 1)
Algorithm 1 has “Backtrack and execute new actions to get to state s_p”
- How is this done in your implementation?

2)
Algorithm 1 has “””
for i ← 1 to b 
do: 
	Execute a_ip to get to state s_ip
”””
- How do you execute multiple actions from the same state in a web environment? This is similar to the above question. Essentially, how is backtracking done?

3)
Tab 2 shows GPT-4o gets 18.9% across the whole VWA benchmark. On the 200 question subset, the results without search are 24.5%. And with b=5, d=5 the results are 37% compared to 26.4% in table 2. This seems like a large discrepancy. Can this be attributed to the sampled questions? 

4)
Line 405: “(which is a sparse reward signal that returns either 0 or 1)”
- What about just showing the accuracy of the value function when the ground truth is available? I.e. Something like mean square error of the value function in cases when ground truth is available. 

5) 
How is tie-breaking done? Seems like it would make sense to break ties by depth and/or by the number of "votes" during generation. 

Suggestions:

Algorithm 1 should be in main section of paper. It is easier to be able to refer to it in the method section. 

“For example, a search budget of 10 indicates that at most 10 nodes will be expanded, after which the agent will commit to and execute the trajectory with the highest value” - This needs to be part of the algorithm. 
The reader needs a place to be able to refer to and understand how the algorithm works. They should not need to comb through ablation results to know how the method works. 

Line 404: “prompted zero-shot (with just the current observation)”
- Maybe note this is because LLaVa only accepts one screenshot

This is maybe nit-picky but wouldn't all the children of a state have the same value? In figure 1, (7) and (9) have different values. 

“Alloted” -> “allotted”

Line 483: backtrack -> backtracks

Figure 1 should be referred to in the text.
soundness: 3
strengths: Originality: This paper proposes an original tree search algorithm for LLM based web agents. The paper also claims to be the first such algorithm.

Quality: The paper is of high quality. The results are pretty strong and clear. 

Clarity: The paper is generally clear and easy to follow. However, there could be some improvement here. 

Significance: There has been a trend of applying tree search and test time compute across many applications LLMs can be applied to. So it is not surprising to see a tree search algorithm for LLM web agents. However, in a first to the flag sense, it is significant. 

The results show that this is a meaningful route to improved performance and seems likely to inspire other works. It clearly clears the bar for publication significance. 

Value function approach seems smart: Multi-modal, Last d screenshots. Scores in 0, 0.5, 1 and averaging over multiple reasoning. This could be a source of a lot of noise but this seems to be a way of reducing that. The trade-off is more compute so the further balance is by only evaluating states when expanded, not when generated. 

“we generate 20 outputs from the model by prompting it with CoT reasoning (Wei et al., 2022), and aggregate the count of the action candidates. We use the top-b actions with the highest counts for branching.”  - This is a good way to generate distinct action candidates
summary: This paper proposes a tree search algorithm for web agents.

The search algorithm expands states using best first search where the value of the state comes from LLM self-evaluation. Specifically, the value comes from self-evaluation of the parent state. This proceeds up to a max depth and search budget after which the algorithm linearly rolls out to complete the task. 

Their results show that tree search can significantly improve LLM-based web agents. 

They claim to be the first tree-search algorithm for web agents.
weaknesses: WebArena results do not look strong relative to other modern works. However, some of those works seem to be a bit over-optimized for the benchmark, whereas this work is more general. 

There are some clarity issues to work out with the writing. 

The section on destructive actions, seems highly speculative. This is a major weakness of the approach in that in real world settings it is difficult to conduct search with lots of back tracking required. It is not even clear to me how backtracking could be conducted in these situations even excluding destructive actions. 

Another weakness of this method is that it involves more inference time compute.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 3
questions: Please refer to the 'Weaknesses' section.
soundness: 2
strengths: 1. The paper adeptly addresses several critical challenges faced by LLM agents in real-world web environments: the difficulty in obtaining clear rewards, the accumulation of errors, and the complexity of multimodal interactive web environments. The motivation for this research is both meaningful and reasonable.
2. The study introduces a tree search algorithm specifically tailored for LLM-based multi-step planning in web environments. This framework is both clear and straightforward.
3. The authors provide qualitative examples of agent trajectories in Section 5.3, which significantly aids in understanding the operational principles and effectiveness of the proposed method.
4. The paper is well-written, with clear and readable presentation of formulas, visualizations of figures and tables, and experimental results.
summary: The paper addresses a critical limitation of language models (LMs) used in autonomous Web agents, particularly their difficulty in performing multi-step reasoning, planning, and utilizing environmental feedback in decision-making tasks. The authors propose an inference-time search algorithm that enhances the decision-making capabilities of LM agents by incorporating a best-first tree search method. To handle the challenge of lacking clear cut rewards in the diverse environments of Web, they propose a model-based value function to guide best-first search. The proposed approach allows the agents to effectively explore and evaluate multiple action paths within interactive web environments, thereby improving their performance.
weaknesses: 1. Lack of technical contribution. The integration of tree search techniques with LLM planning is not entirely novel, as there is existing research in this area, e.g., [1, 2, 3, 4]. Thus, the contribution of this paper in terms of technique novelty may need to be reconsidered, as it incrementally applies existing tree search-based LLM planning frameworks to the web agent domain.

[1] Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models (Released in 6 Oct 2023)

[2] When is Tree Search Useful for LLM Planning? It Depends on the Discriminator (Released in 16 Feb 2024)

[3] LLM Self-Training via Process Reward Guided Tree Search (Released in 6 Jun 2024)

[4] LiteSearch: Efficacious Tree Search for LLM (Released in 29 Jun 2024)


2. Lack a specially designed evaluation method for value function. The authors evaluate the impact of different value functions on the success rate of the entire framework in order to select a best value function, as mentioned between lines 401 and 412. However, assessing value functions based solely on the overall framework's outcome might be indirectly influenced by various potential factors. It would be beneficial for the authors to propose a dedicated evaluation method for value functions, essentially allowing for a more stable and accurate selection process.


3. The performance and credibility of the proposed framework seems limited, as observed in Table 2 (lines 324-341):
- The use of different baselines across two different datasets raises questions about the credibility of the experiments.
- On the WebArena benchmark, the authors only report the performance of two base LLMs augmented by their method, without the performance of the SOTA baselines augmented by their method, suggesting that the method may not universally integrate with diverse models or scenarios as claimed.
- Since the base LLMs already perform sub-optimally, the observed improvements after involving the proposed method are not surprising.
- The highest success rate achieved by the framework is 19.2% on the WebArena benchmark, which is considerably lower than multiple baselines, raising doubts about its efficacy.


4. Some mentioned future works should have been addressed in this paper:
- Integrating proposed search strategies into domain-specific SOTA baselines (mentioned as future work on lines 274 and 349).
- Experiments with larger search budgets (mentioned as future work on line 377).
- Mitigating the time cost of tree search-based LLM planning (mentioned as future work on line 502).

For instance, the study should report the performance of the domain-specific SOTA baselines augmented by the proposed method under the maximum step constraint setting used in the reported baselines, instead of just using the base LLMs and a small step constraint. Furthermore, addressing the time consumption of tree search for LLM planning is crucial for the feasibility of practical applications, making this an essential consideration.

Simply involving these crucial issues into future work may lead to skepticisms about the credibility and robustness of this study.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. In Figure 2, it can be observed that there is a noticeable improvement as the search budget c increases from 15 to 20. Have the authors attempted to experiment with a larger c? This might yield better results.
2. The parameter c is set as the maximum search budget. Have the authors tested the average number of searches conducted for both successful and unsuccessful cases? It might be beneficial to use a larger search budget during testing and observe how the training performance improves as c increases.
soundness: 3
strengths: 1. The methodology presented in this paper is robust, as the application of tree search methods within a network environment proves to be an effective solution.
2. The structure of the paper is logically organized, beginning with an examination of existing issues and specifically addressing the challenge of implementing multi-step reasoning in network environments.
3. The authors propose a novel method, conduct rigorous testing, and perform comprehensive ablation studies.
4. The explanations are articulated clearly and are easily comprehensible; the combination of diagrams and text effectively illustrates the improvements achieved by the proposed method.
5. The experimental section is meticulously detailed, ensuring the reproducibility of the experiments, which enhances the credibility of the findings.
summary: This paper proposes a search-based approach to improve the performance of language model (LM) agents on realistic web automation tasks. Existing LM agents struggle with multi-step reasoning, planning, and using environmental feedback, which is crucial for success on open-ended web tasks. The authors introduce a best-first tree search algorithm that operates within the actual environment space and is complementary to existing state-of-the-art LM agents. The search procedure allows agents to explore a larger number of potentially promising trajectories at test time, reducing uncertainty through explicit exploration and multi-step planning. The authors evaluate their approach on the challenging VisualWebArena and WebArena benchmarks, demonstrating significant improvements over baseline LM agents and setting new state-of-the-art success rates.
weaknesses: 1. The authors' central concept is to apply tree search methods within a network environment to achieve enhanced performance. However, as tree search techniques are commonly used in other systems, this approach exhibits limited innovation. 
2. In Section 5.4, the authors acknowledge that this method may result in slow execution, a significant drawback often associated with tree search. Nevertheless, the paper does not present a comparison of execution times between this method and other approaches, nor does it provide an in-depth discussion of the temporal challenges involved. The discussion primarily revolves around the search budget c, yet c does not accurately reflect the time expenditure. Readers are more concerned with the issue of temporal efficiency rather than the selection of hyperparameters.

Meta-review: In this paper, the authors propose an inference-time tree search algorithm for LLM agents to perform web exploration and planning tasks. Reviewers noted that the experiments demonstrate the effectiveness of the approach and its compatibility with various LLM models. However, they also expressed concerns about the computational costs, the novelty of the approach, and its overall completeness. In summary, reviewers acknowledged the contributions of this work but suggested that further development is needed to make it a solid publication.

Decision: Reject