Tree Search for Language Model Agents
Authors: Jing Yu Koh
Stephen Marcus McAleer
Daniel Fried
Ruslan Salakhutdinov
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (09/2025)
Tree Search for Language Model Agents
Jing Yu Koh Cornegie Mellon University
jingyukiccs. crnu. edu
Stephen McAleer
smcaleer@cs.comee edu
Cornegie Mellon University
Daniel Fried Carnegie Mellon University
dfried@ess. craa, edu
Ruslan Salakhutdinov Carnegie Mellon University
rsalaklu@cs.cmm www.aecccccccccmmmmmmmommm.m...m edu
Reviewed on OpenReview:
Abstract
Autonomous agents powered by language models (LMs) have demonstrated promise in their ability perform decision-making tasks such as web automation. However, key limitation remains: LMs, primarily optimized for natural language understanding and generation, struggle with multi-step reasoning, planning, and using kenvironmental feedback when atlempting to solve realistic computer tasks. Towards addressing this, propose an inference-time search algorithm for LM agents to explicitly perform exploration and multi-step plamning 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 the first tree search algorithm for LM agents that shows effectiveness on realistic web tasks. On the challenging VisualWeb benchmark, applying our search algorithm top of a GPT-40 agent yields 39.7% relative increase in success rate compared to the same baseline without search, setting state-of-the- success rate of 26.4%. On WebArena, scarch also yiclds 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.
1 Introduction
Building agents that can perceive, plan, and act autonomously has been a long standing goal of artificial intelligence research (Russell & Norvig 1995 Franklin & Graesser 1996). 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. 2024b) and VisualWeb 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 lext-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 stratogy for leveraging test-compute to improve results search: iteratively constructing, exploring, and pruning a graph of intermediate states and possible solutions (Newell et. al. 1959 Silver et. al. 2016 Laird 2019). The
(Koh et al. 2024),

---

Published in Transactions on Machine Learning Research (09/2023)
GPT-4o Agent
AROY-D
AROV-D
3
Fallure
GPT-4o Agent Search
Task Instruction (7): "Can you add this and the other canned fruit (af the same brand) that looks like this, but red instead of brown the comparison page?"
V 0.5
0.46
Starting State
0:48
0.85
Legend
Stop sequence
9
10
Backtracking
State values
V5
Success
Our proposed search algorithu. At each iteration, we pick the next state Up to expand from frontier F and compute a score v for it using the value function. Then, we add the possible states that the agent can get to from Sp to the frontier and repeat the scarch procodure. Faded nodes indicate explored and pruned states. Blue dashed arrows indicate backtracking.
Figure 1:
effectiveness of search algorithms has been shown time and time again, enabling models to achieve or surpass human-level performance on variety of games, including Go (Silver et al. 2016 2017 poker (Brown & Sandholm 2018 2019 and Diplomacy (Gray et al. 2020).
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 mothod 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 enunerate a much larger mumber of potentially promising trajectorics 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 model-based value function to guide best-first search. The value function is computed by marginalizing over reasoning chains of a multimodal L.M conditioned on the agent's '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 VibualWebArena (Koh et al. 2024), scarch improves the performance of a bascline GPT-4o (OpenAī 2024) agent by 39.7% relative to the bascline without search, setting a new state-of-the-art (SOTA) success rale of 26.4%. On WebArena [Zhou et al., 2024b), search also highly effective, contributing a 28.0% relative improvement (yielding a competitive success rate of 19.2%). We also demonstrate that our scarch procedure benefits from scale: achieving improved performance as the agent is allotted greater amounts of test-time computation. Our code and models are publicly released at
2

---

Published in Transactions on Machine Learning Research (09/2025)
2 Background
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.) 2023) is an evaluation benchmark that measures the ability of frontier models in predicting actions taken on static Internet pages. VebleeWe (Liu et al.) 2024b) 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. 2017 Liu et al. 2018 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. 2022a) simulates a simplified e-commerce site with real world data. WebLINX (Lü et al. 2024) proposes a benchmark for tackling conversational web navigation, which involves communication between the agent and a human instructor. MMI1A (Zhang et al. 2024c) and OSWorld (Xie et al., 2024a) propose benchmarks to measure the ability of agents to accomplish tasks by navigating across multiple computer applications. WorkArena (Drouin et al.) 2024) is simulated environment for tasks on the ServiceNow platform. Outside of the web, environments such AndroidWorld (Rawles et al. 2024) is a dynamic environment for measuring the performance of agents on mobile applications. Several other work build comprehensive, highly realistic, fully-featured web simulators. WebArena (WA) (Zhou el al. 2024b) is a benchmark of 812 tasks across realistic self- hosted re- re-implenentations of popular websites (Shopping, Reddit, CMS, GitLab, Maps), each populated with real world data. VisualWebArena (VWA) (Koh et al., 2024) 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 realistic and challenging test for multimodal agents.
visual grounding and understand image inputs
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. (2024b) for additional context. The environment & AS, 12, T) consists of a set of states S, actions A (Tab. 1 and a deterministic transition function T S x A + S that defines transitions between states conditioned on actions. Each task in the benchmark consists of a goal specified with a natural language instruction (e.g., "Find me the cheapest red Toyota car below $2000."). Fach task has a predefined reward function R S x A {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.
Action Type
Description
click [elem] hover [elem]
Click on elem.
Hover on elem.
type [elem] [text]
Type text on elem. Press key combo. Open new tab. Focus on the i-th tab. Close current tab.
press [key_comb]
new_tab
tab_focus [index]
tab_close
goto [url]
Open url.
go_back
Click back.
go_ forward
Click forward.
scroll [dwn]
Scroll up or down.
stop [answer]
End with an output.
Table 1: Possible actions A in the (Vi- sual) WebArena environments.
2.2 Language- Guided Autonomous Agents
Autonomous web agents, powered by frontier (multimodal) language models (Google 2023
OpenAT
2024
Anthropic 2024), are the SOTA approaches for many of the above benchmarks. Kim et al. (2024) showed
that large language models can be prompted to execute computer tasks on MiniWoB++ (Liu et al.
2018
requiring far fewer demonstrations than reinforcement learning methods. AutoWebGLM (Lai et al. 2024
collects web browsing data for curriculum training and develops web navigation agent based off a 6B parameter language model that outperforms GPT-4 on WebArena. Patel et al. (2024) showed that a language model agent can improve its performance through finetuning on its own synthetically generated data. Pan ct al. (2024) 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. (2024) agent. Fu et al.] (2024) extracts domain knowledge from oflline data and provides this to the language agent during inference, to enable it to leverage
3

---

Published in Transactions on Machine Learning Research (09/2025)
helpful domain knowledge. SteP (Sodhi et al. 2024) and AWM (Wang et al. 2024b) propose methods to enable agents to dynamically compose policies to solve web tasks.
In the multimodal setting, WebGUM (Furuta et al. 2024] finetuned a 3B parameter multimodal language model on a large corpus of demonstrations, achieving strong performance on MiniWoB and WebShop. Koh et al. (2024) showed that prompting multimodal language models with a Set-of-Marks (Yang al.) 2023 representation enables the model to navigate complex webpages more effectively than text-only agents. SceAct (Zheng et al., 2024) demonstrated that frontier multimodal models can be grounded and prompted to solve web tasks. ICAL (Sarch et al. 2024 builds a memory of multimodal insights from demonstrations and human feedback. Our procodure 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. 1968) have long been used in artificial intelligence systems. Newell et al. (1559) and Laird (2019) cast goal-oriented behavior as search through a space of possible states. Dean et al. (1993) and Tash & Russell 1994 proposed planning algorithms over a limited search horizon, and employed an expansion strategy to improve plans based off hcuristics. Tash & Russell (1994) showed that this allowed agents to provide appropriate responses to time pressure and randomness in the world. Deep Blue (Campbell et al.) 20022,, the chess engine which defeated world champion Kasparov in chess 1997, was based on massive parallel tree search. Pluribus (Brown & Sandholm 2019) 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 in many games. Monte-Carlo Tree Search (MCTS) (Browne et al. 2012) was used to provide lookahead search in the AlphaGo Siilerr et al. 2016
2017) systems that achieved superhuman performance in the game of Go. Gray et al. 2020) performs one-step lookahead search to achieve SOTA on no-press Diplomacy. More recently, several papers Yao et al.
2024 Besta et al.,
2024) showed the potential
of applying search to large language models to introduce exploration, enhancing performance on text basod
tasks that require non-trivial planning. Others have applied MCTS (Hao al.
Zhou el. al. 2024a] Xie 2024a Zhang et al.) 2024b Wang et al. 2024a] Zhang et al 2024a] to improve the
2023
et al. 2024b Chen et al.
performance of LMs on math and science benchmarks (Cobbe et al. 202 Wang et al. 2023a or simplified
environments (Ya et al.
2022a Valmeekam et al. 2023 Zhou et al. 2024a
In contrast to prior work, we search over the actual environment space of realistic, complex websites. This means that search mechanics need to incorporate not just the text outputs of the agent, but also external environmental feedback.
3 Method
In this section, we describe the search procodure (Fig. [ in detail. Successfully solving a task in a web environment such as (V)WA can be interpreted as navigating to a goal state 8, which gives a positive reward R(s.) The agent starts at state so (c.g., the homepage). Given a natural language instruction I, the agent's goal is to navigate 8. by executing actions (ao,..., a.) A. Each action produces new state $t+1 S and observation 0t+1 Ω from the environment. The transition s; $1+1 is governed by deterministic transition function T S x A
Most approaches treat this as a partially observable Markov decision process, and only condition on the current observation o, when predicting the next action o, to take. This has significant limitations: the error of the agent compounds with each stop, and if an crroncous action taken at time t, cannot be casily rectified if this leads to a bad state. Our approach aims to alleviate this by explicitly conducting search and backtracking to identify better trajectories.
4

---

Published in Transactions on Machine Learning Research (09/2025)
3.1 Agent Backbone
Most SOTA web agents are built through prompling large (multimodal) language models Zhou et al. 2024b Pan et al. 2024 Fu et al., 2024 Zheng et al. 2024 Koh et al., 2024). A pretrained language model or multimodal model f& is prompted with the current webpage observation or and instructed to predict the next action a, to be executed. is common to leverage prompting techniques, such as ReAct (Yao et al., 2022b), RCT (Kim et al.) (0244), or Chain-of-Thought (CoT) prompting (Wei et al., 2022), 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. 2020)), 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 scarch improves inference-time performance on a range of models without retraining finetuning fa-
3.2 Value Function
We implement a best-first search heuristic using a value function fo which estimates the expected reward E [s:]] of the current state &t, where the ground truth goal state would provide perfect reward of 1. As the state 9t of the simulator is not always accessible to the agent (s, may include private information such as site database entrics), the value function computes the value i using the current and previous obsorvations, as well the natural language lask instruction I:
1z = [o, fo....., 0, E [0,
the value function is implemented by prompting a multimodal language model with the task instruction and observation screenshots.
In our experiments (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. 1968). 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 which determine the maximum size of the search tree and termination threshold 0. The search procedure is summarized in Fig. [ We describe it in detail in the following paragraphs and provide the formal algorithm in Appendix A.4
At time l in the execution trajectory, the agent has previously executed a sequence of actions to arrive at the current state 8t- We begin the search algorithm from 8, by initializing the frontier F < O (implemented as a max priority queue) which holds the set of states that we plan to evaluate, the best state found so far 8, < St, the score of the best sequence é, + 0, and the scarch counter
0.
At each iteration of the search process, extract the next state from the frontier, 8p + pop(F). We the value function to compute the score for state 8p (with observation op and previous observations o1,..., Op-1):
Up = foll, fo.....,,,p). o,,))
Then, we increment 8, and up is higher than the current best score i, we update and our best state accordingly:
t- 8 +
8, x- 8p
if up > 6r otherwise
0, f- max (z, Up)
If up > 0 (i.e., the agent is likely to have found a goal state) or 2 c (the search budget has been exceeded), we will terminate the search and navigate to the best state & found thus far. Otherwise, if the current branch
In Sec.
5.1 we show that increasing the of the search tree improves results by leveraging increased compute.
5

---

Published in Transactions on Machine Learning Research (09/2025)
does not exceed the maximum depth (i.e., [ss (8.......sp) sp)) d), we will generate plausible next actions for branching by obtaining b candidate actions {a (app....,9) Og) from the language model agent fs. For each i, we execute d and add the resulting state s to the fronticr with the score of the current state
F ((p
for I....,b
This concludes one iteration of search. both termination conditions have not been reached, we backtrack and repeat this for the next best state from the updated frontier F.
4
Experiments
We run experiments the full set of 910 VisualWebArena (VWA) and 812 WebArena (WA) tasks. The tasks are distributed across set of diverse and realistic websites.
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 el. al. 2024 Sodhi et al. 2024 for future work. We run several prompt-based agent baselines:
Multimodal SoM: For multimodal models that accept multiple image-text inputs, such as GPT- 4o (OpenAl 2024) (6pt-40-2824-05-13) we run the multimodal agent from Koh et al. (024) with the same prompt We similarly apply a preprocessing step to assign a Set-of- Marks (SoM) Yang (et al.) 2023) reprosentation to the webpage. This highlights every intoractable element on the webpage with a bounding box and a unique ID. The inpul to the agent a screenshot of the SoM-annotated webpage, and a text description of the elements on the page with their assigned IDs.
Caption-augmented: For base models that are not multimodal (e.g., Mlama-3-70B-Instreee Dubey cet al., 2024)), we rum the apttion-augmented agent with the same prompt from Koh al. (2024). We generate captions for each image the webpage using off-the-shelf captioning model (in our case, BLIP-2; 2: Li et al. 2023). The accessibility tre representation of the webpage is used as the input observation.
Text-only: On WebArena (which does not require visual grounding), run text-only agents using the prompt from Zhou et al. (2024b), for both GPT-4o and Llama-3-700 1aama-3-70B--- Instruct. This model uses an accessibility tree (w/o captions) of the current page as input.
Search parameters Our search parameters are set to d = 5, b 5, = 20, and we stop execution after a maximum of 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 maximun 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 scarch 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. 2020 with 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. 2022 We aggregate the count of the actions and use the top-b actions for branching.
We opt for this approach instead of immediately computing the value for resulting states sf as immediate evaluation requires more backtracking calls, which would incur much more overhead in the (V)WA simulators. hhttps://devell mozilla.oo //t////r/////e//ooaar//ccesssss

---

Published in Transactions on Machine Learning Research (09/2025)
Agent Model
Max Steps
Search
+ Search
1aamaa3-77O-Insttaae captions Kohh et al.
2024
9.8%
GPT-4o + SoM (Koh et al. 2024
30
19.8%
VWA
ICAL (Sarch al.
2024
23.4%
Mamm--3-70B-Isttrucc + captions
7.6%
16.7%
-19.77
5
GPT-40 SoM
18.9%
26.4%
+39.7%
GPT-4o (Zhou et al. 2024b
13.1%
GPT-4 + Reflexion Pan et al.
2024
15.6%
AutoWebGLM Lai
2024
18.2%
AutoEval [Pan el al. 2024
20.2%
BrowserGym Drouin al. 2024
30
23.5%
WA
SteP (odhi et al. 2024
33.5%
GUT-APT Hybrid Agent
Song et al.
2024
35.8%
AgentOccam Yang et 2024b
43.1%
AgentOccam- Judge Yang et al.
2024b
45.7%
-lama-3-70B-Lnsttee
7.6%
10.1%
+2.33%
GPPT-40
15.0%
19.2%
+28.0%
Table 2: Success rales (SR) and relative change (A) for baseline models and models that employ search on
the VisualWebArena (VWA) (Koh et al.] 2024) and WebArena (WA) Zhou et al.) 2024b) benchmarks. We also show other published approaches. Search substantially improves our bascline models, setting new state-of the-art on VWA.
Value function As detailed in Sec. 3.2
require value function which scores the likelihood that the current state 8t is goal state. We implement the value function by prompting a multimodal language model with the task instruction J, screenshots of the agent's ' trajectory, previous actions the agent took, and the current page URL. The full prompt is provided in Appendix A..322] The multimodal LM is instructed to output whether the current state is a success, a failure, and it's a failure, whether it is on a trajectory towards success. These put are assigned values of 1, O, and 0.5 respectively (and for invalid oulput). order to get more finegrained and reliable scores, we leverage ideas from self-consistency prompting (Wang) et al. 2023b), and sample multiple reasoning paths by prompting the multimodal LM with CoT (Wei et al., 2022 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 8t, 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.
4.2 Results
Our results are summarized in Tab. Introducing search increases success rate substantially across the board. Search improves the success rate of the baseline GPT-40 + SoM agent on VWA by 39.7% relatively (increasing from 18.9% 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% 19.2%) While other baseline agents obtain higher performance than our GPT-4o baseline through domsin-specific techniques such as introducing website specific guidelines (Sodhi et al. 2024 Fu el. al. 2024 engineering improved input spaces (Song et al. 2024 Yang et al. 2024b), these techniques are orthogonal to and potentially complementary with - our scarch-baser approach.
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 scarch, Llama-3-70B-Instin multimodal models that do not use search. On WebArena, we also see a substantial relative improvement of
achieves success rates that are close to the best frontier
We estimate the API of the GPT-4o SoM agent for action prediction to approximately that computing the value.
7

---

Published in Transactions on Machine Learning Research (09/2025)
Success Rate vs. Search Budget
Depth d Branch b
SR (t)
A
0.4
24.5%
0%
Success Rate (t)
0.3
26.0%
+6%
32.0%
+31%
0.2
3
31.5%
+29%
2
35.0% 5
+-43%
0.1
3
5
35.5%
+45%
37.0%
+-11%
0.0
20 Max Search Budget (# of node expansions)
Table 3: Success rate (SR) and relative change (A) over the baseline without search on a subset of 200 VWA tasks with varying search depth (d) and branching factor (b). d = 0 indicates no scarch is performed. All methods use max search budget e = 20.
Figure 2: Success rate on a subset of 200 VWA tasks with search budget c. c 0 indicates no scarch is performed. Success rate generally in- creases as increases.
32.2% for the text-based Llama-3 agent (7.6% to 10.1%). The strong performance of the Baenaa---7---nnstuun agent with search can prove to be a cost effective agent model for iteration in future work that requires access 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
We conduct several ablations a subset of 200 VWA tasks.
Search budget We plot the success rate of the GPT-4o agent with search limited to varying budgets E (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 10 indicates that at most 10 nodes will be expanded, after which the agent. will commit 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 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 scarch budget.
Search depth and breadth We run an ablation experiment. varying the search branching factor b and maximum depth d. The results are summarized Tab. g We observe that in general, success rate increases as the size of search tree increases (along both b and d dimensions), and scaling both b and d is necessary to achieve strong performance.
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. 2024ah multimodal model prompted zero-shot (with only the current observation, as LLaVA only supports a single image input) and (2) the groundtruth reward from VWA (which is a sparse reward signal that returns either or 1, and does not track partial progress), and (3) GPT-4o without self-consistency. The results are summarized in Tab. 4 We find that the GPT-4o value function significant outperforms
Value Function
SR (t)
None (no search)
24.5%
LLaVA (w/ SC, 20)
30.0%
GPT-4o (no SC)
28.5%
GPT--o (w/ SC, = 5)
32.5%
GPT-4o (w/ SC, 20)
37.0%
Groundtruth
43.5%
Table 4: Success rale of the GPT- 4o agent with different value func- tions.
8

---

Published in Transactions on Machine Learning Research (09/2025)
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 with better value functions. We also observe that sell-consistency is essential for good performance (28.5% + 007, which we altribute it enabling marginalization over multiple reasoning chains, reducing noise during state evaluation. While we do not finetune custom value function models in this paper, believe that this is promising direction for future work, and may result in value function models that can outperform our current version.

---

Published in Transactions on Machine Learning Research (09/2025)
Comparison to Trajectory-Level Reranking 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 mothods proposed in Chen et al. (2024b) and Pan el al. (2024)
Success Rate vs. Number of Trajectories
Success Rate (t)
without their Reflexion Shinn et al., 2024] component.
This is less practical method, 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 more limited form of search, as it only considers entire trajectories and cannot backtrack to prune bad branches. Nevertheless, we perform an ablation where sample n trajectories from the GPT-4o agent (with nucleus sampling (Holtzman et al. 2020) 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.
Trajectory Reranking
Tree Search (c = 5)
Tree Search 20)
2
3
5
6
Number of Trajectories
Figure 3: Success rate of trajectory re-ranking approach compared to our approach.
We observe that this re-ranking baseline starts to plateau around runs, which achieves success rate of 30%. This underperforms our approach with search budget 2 5 (Fig. 2). For and n = 5, the agent from these two approaches spend approximately equal inference compute. Tt also substantially worse than approach with 20, which achieves success rate of 37.0% the ablation subset.
5.2 Success Rate Breakdown
Success rate by task difficulty The VWA benchmark includes labels for the action difficulty of cach 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, there may exist more optimal solutions in practice. The increase in success rate from introducing search is summarized in Tab. Introducing search improves performance across all difficulty levels, but introduces much greater gains medium difficulty tasks, with a relative increase of 75% in success rate (from 12.7% to 22.2%). We hypothesizo that this is because our search parameters (max depth = 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 do not benefit much from scarch, they generally involve less planning (some can be solved with or 2 actions), and baselines already have higher success rates.
Difficulty
No Search
Scarch
A
easy
34.2%
42.3%
+24%
medium hard
12.7%
22.2%
+75%
10.2%
14.9%
+477
Table 5: Success rates and relative change (A) of the GPT-4o agent on VWA tasks of different. action difficulty levels.
Success rates by website Tables 0 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, ratinn 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%, and the CMS site in the WA benchmark (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.
10

---

Published in Transactions on Machine Learning Research (09/2025)
Task Instruction (7): "I recall seeing this exact item on the site, help me find the most recent post of it. recall seeing it in either the Collectibles or Antiques section."
GPT-4o Agent + Search
2
=
= 0.45
Starting State
3
v
==
0.2
5
6
Success
0.63
1.0
Legend:
Search sequence
Backtracking
1.0
State values
Figure 4: Search can improve robustness by backtracking from bad actions. Shown above is trajectory for VWA classifieds task #48 where groodily picking the first sampled actions would have led to a failure (the path the first row).
Website
No Search
Search
Website
No Search
Search
A
CMS
11.0%
16.5%
+50%
Classifieds
18.4%
26.5%
+44%
Map
21.1%
25.8%
+22%
Reddit
17.1%
20.5%
+ +00%
Shopping
24.0%
28.1%
+17%
Shopping 20.0%
29.0%
+ +45%
Reddit 7.9%
10.5%
+33%
Gitlab 10.2%
13.3%
+300%
Overall 18.9%
26.4%
+40%
Overall 15.0%
19.2%
+288%
Table 6: Success rales and relative change (A) of the GPT-4o agent on VWA websites.
Table 7: Success rates and relative change (A) of the GPT-4o agent on WA websites.
More robust multi-step planning Many tasks in VWA and WA require agent to keep persistent. memory of multiple previous actions and observations. A common failure mode amongst agents without scarch is that they tend to undo previous actions, or get stuck in loops (sce Appendix C.4 of Koh et al. 2024). An example for VWA shopping lask #256 is shown in Fig. [ where the agent. is tasked to add two dilferent. 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 step 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 backtracks when those eventually result in failure: the same GPT-4o agent with search is able to find successful multi-step trajectory for the samne lask, which involves adding the first item (action #1 in Fig. typing in search query (#6), and adding the correct second item to the comparison list (#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 take in the environment. Search allows us to evaluate each generated action concrctely by executing it the simulator, and use the received environmental foedback make better decisions. One example is VWA classifieds task #48 (Fig. 4b, which is to find post containing particular image. Tf the agent executes the
11

---

Published in Transactions on Machine Learning Research (09/2025)
first sampled action at every step (i..,, the sequence in the top row), it results in failure. Search allows the agent to explore and enumerate multiple possibilities.
5.4 Limitations
While we have shown that introducing search to language model agents achieves promising results on web tasks, our approach does come with some practical considcrations.
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, 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 20x more LM calls than an agent without search. Research on improving the efficiency and throughput of machine learming systems (Leviahhan et al. 2023 Dao et al., 2022: Dao, 2023) will likely help with optimizing this, but for practical deployment one may neod to carefully set the search parameters b, d, and e to balance between achieving better results and overall time spent completing a task.
In our approach, implemented scarch by koeping track of the sequence of actions required to get to state. During backtracking, we reset the enviromment and apply the same sequence after resetting the environment. This is necessary, as naively executing the go_back action (Tab. I may discard important information on the page, such as the scroll offset and already entered text.
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 difficult to 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 ream 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 2018 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. 2023 Yang ct al. 2024a) or Microsoft Excel [Li et al., 2024).
Domain Specific Value Functions In this work, we only consider tree search in the context of agents operating in dynamic web environments, and our value function is tailored to capture the nuances of web navigation, incorporating features such as page content and navigation history (in the form of previously seen screenshots). This is likely to be less effective for other agentic domains, such as software engineering (SWE) agents Yang et al. (2024a). Although our overall tree search approach is generalizable, the value function may require adaptation to effectively incorporate domain-specifee context: for example, code execution traces for SWE tasks. We leave detailed explorations for future work.
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 trajectorics to achieve superior performance on web tasks. This is the first time search has been shown lo siguificantly improve the success rales of LM agents on realistic web environments, as demonstrated on the (Visual)Webe WebArena benchmarks. Our search procedure is general, and it will be valuable to apply to other domains future work, or incorporate more sophisticatod search algorithms such as MCTS. We believe that inferenco-time search will be a key component for building capable agents that can plan, reason, and act autonomously to perform computer tasks.
12

---

Published in Transactions on Machine Learning Research (09/2025)
Statement of Broader Impact
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 acknowlodge several considerations of broader impact:
Intended uses. Our work is 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.
Privacy: More capable web agents could potentially be used to scrape personal information or navigate private areas websites more effectively. We emphasize the importance of respecting user privacy and website terms of service in any real-world deployment of these technologies.
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, rescarchers and developers should proactively consider how to manage this transition and support affected workers.
Fairness and bias. As with any modern Al 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 casily be applied to any off-tho-shelf language model, and will likely benefit from upstream efforts on language model safety and aligument.
Our approach also potentially provides 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 guidelines and best practices for the responsible deployment of web agents.
References
AI Anthropic.
The claude 3 model family: Opus, sonnet, haiku. Claude-9 Model Card, 2024.
Macicj Besta, Nils Blach, Ales Kubicck, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. In AAAI, 2024.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365 888-890 2019.
Cameron Browne, Edward Powley, Daniel Whitchouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfsha- gen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEFE Transactions Computational Intelligence and AT in games, 2012.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Murray Campbell, A Joseph Hoane Jr, and
Hsu. Deep blue. Artificial intelligence, 2002.
Guoxin Chen, Minpeng Liao, Chengxi Li, and Kai Fan. Alphamath almost zero: process supervision without process. orXiv preprint arXiv:2405.03555 03553, 2024a.
Ziru Chen, Michael White, Raymond Mooney, Ali Payani, Yu Su, and Huan Sun. When is tree search useful for Ilm planning? depends on the discriminator. ACL, 2024b.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint Xrx:::2110 10. 14168, 2021.
Tri Dao. Flashattention Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691 2023.
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattennion: Fast and memory-effiiint exact attention with io-awareness. NewrIPS, 2022.
Thomas Dean, Leslie Pack Kaelbling, Jak Kirman, Ann Nicholson, et al. Planning with deadlines in stochastic domains. In AAAI, 1993.
Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Samuel Stevens, Boshi Wang, Huan Sun, and Yu Su. Mind2web: Towards a generalist agent for the web. NeurIPS, 2023.
Alexandre Drouin, Maxime Gasse, Massimo Caccia, Issamn H Laradji, Manuel Del Verme, Tom Marty, Léo Boisvert, Megh Thakkar, Quentin Cappart, David Vazquez, et al. Workarena: How capable are web agents at solving common knowledge work tasks? arXiv preprint arXiv:2409.077 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprint WxXiv:247.21178, 2024.
Stan Franklin and Art Graesser. Is it an agent, just program?: A taxonomy for autonomous agents. In International workshop agent theories, architectures, and languages, pp. 21-35. Springer, 1996.
Yao Fu, Dong-Ki Ki Kim, Jackyeom Kim, Sungryull Sohn, Lajanugen Logeswaran, Kyunghoon Bac, and Honglak Lee. Autoguide: Automated generation and selection of state-aware guidelines for large language model agents. Xiv preprint "xXi:2403.08972 2024.
Hiroki Furuta, Kuang- Huei Lee, Ofir Nachum, Yutaka Matsuo, Aleksandra Faust, Shixiang Shane Gu, and Izzoddin Gur. Multimodal web navigation with instruction-finctuned foundation models. ICLR, 2024.
Gemini Team Google. Gemini: a family of highly capable multimodal models. arXiv preprint 2rX.w:2312.11805, 2023.
Jonathan Gray, Adam Lerer, Anton Bakhtin, and Noam Brown. Human-level performance in no-press diplomacy via equilibrium search. arXiv preprint Xrx: 020223 2020.
David Ha and Jürgen Schmidluber. World models. arXio preprint arxiv 10122, 2018.
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. EMNLP, 2023.
Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the houristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernelics, 4(2):100 107, 1968.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. ICL,R 2020.
Carlos Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. Swe-bench: Can language models resolve real-world github issues? arXiv preprint arXix2330.00 0.00000, 2023.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Geunwoo Kim, Pierre Baldi, and Stephen McAleer. Language models can solve computer tasks, Advances in Neural Information Processing Systems, 36, 2024.
Jing Yu Koh, Robert Lo, Lawrence Jang, Vikram Duvvur, Ming Chong Lim, Yu-Yu Huang, Graham Neubig, Shuyan Zhou, Ruslan Salakhutdinov, and Daniel Fried. Visualwebarena: Evaluating multimodal agents on realistic visual web tasks. ACL, 2024.
Hanyu Lai, Xiao Liu, Iat Long Iong, Shuntian Yao, Yuxuan Chen, Pengbo Shen, Hao Yu, Hanchen Zhang, Xiaohan Zhang, Yuxiao Dong, et al. Autowebglm: Bootstrap and reinforce large language model-basee web navigating agent. arXiv preprint Xrxin:2404.00 2404.006448 2024.
John E Laird. The Soor cognitice archileclure. MIT press, 2019.
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In ICML, 2023.
Hongxin Li, Jingran Su, Yuntao Chen, Qing Li, and ZHAO-XIANG ZHANG. Sheetcopilot: Bringing software productivity to the next level through large language models. NewrIPS, 2024.
Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi. Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models. In ICML, 2023.
Evan Zheran Liu, Kelvin Guu, Panupong Pasupat, Tianlin Shi, and Percy Liang. Reinforcement learning on web interfaces using workflow-guided exploration. ICLR, 2018.
Haotian Liu, Chunyuan Li, Yuheng Li, Bo Li, Yuanhan Zhang, Sheng Shen, and Yong Jae Lee. Lexta-next: Improved reasoning, ocr, and world knowledge, January 2024a. URL https://1lawa-vl.. www.ll.ggtt........ h
Junpeng Liu, Yifan Song, Bill Yuchen Lin, Wai Lam, Graham Neubig, Yuanzhi Li, and Xiang Yue. Visu- alwebbench: How far have multimodal Ilms evolved in web page understanding and grounding? arXiv preprinl ar Xiv: 05955, 2024b.
Xing Han Lü, Zdeněk Kasner, and Siva Reddy. Weblinx: Real-world website navigation with multi-turn dialogue. Xrxiv preprint arXiv:2402.05930 2024.
Allen Newell, John C Shaw, and Herbert A Simon. Report on general problem solving program. In IFIP congress, volume 256, pp. 64, 1959.
OpenAL. Hello GPT-4o. https://oopnai..cc//ndd/////l/l
2024.
Jiayi Pan, Yichi Zhang, Nicholas Tomlin, Yifei Zhou, Sergey Levine, and Alane Suhr. Autonomous evaluation and refinement digital agents. arXiv preprint arXiv:2404.06474, 2024.
Ajay Patel, Markus Hofmarcher, Claudiu Gooveanu-Condee and Sepp Hochreiter. Large language models can self-improve at web agent tasks. arXiv preprint 2XXi::405.20909 2024.
Dinu, Chris Callison-Bureh
Christopher Rawles, Sarah Clinckemaillie, Yifan Chang, Jonathan Waltz, Gabrielle Lau, Marybeth Fair, Alice Ti, William Bishop, Wei Li, Folawiyo Campbell-Ajala, et al. Androidworld: A dynamic benchmarking environment for autonomous agents. arXiv preprint arv: 14573, 2024.
Stuart Russell and Peter Norvig. Artificial intelligence: a modern approach, 1995.
Gabriel Sarch, Lawrence Jang, Michael J Tarr, William W Cohen, Kenneth Marino, and Katerina Fragkiadaki. Ical: Continual lcarning of multimodal agents by transforming trajectorics into actionable insights. arXiv preprint XrXe::2406. 14596, 2024.
Tianlin Shi, Andrej Karpathy, Linxi Fan, Jonathan Hernandez, and Percy Liang. World of bits: An open-domain platform for web-based agents. In TCML, 2017.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyn Yao. Reflexion: Language agents with verbal reinforcement learning. NewrIPS, 2024.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7567):484-48) 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, loamnis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthow Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 359, 2017.
Paloma Sodhi, SRK Branavan, Yoav Artzi, and Ryan McDonald. Step: Stacked Ilm policies for web actions. arXiv preprint arXtt:2300.03770e: 2024.
Yueqi Song, Frank Xu, Shuyan Zhou, and Graham Neubig. Beyond browsing: Api-based web agents. 2024.
Jonathan Tash and Stuart Russell. Control strategies for a stochastic planner. In AAAI, 1994.
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilitics of large language models-a critical investigation. NewrIPS, 2023.
Ante Wang, Linfeng Song, Ye Tian, Baolin Peng, Dian Yu, Haitao Mi, Jinsong Su, and Dong Yu. Litescarch: Efficacious tree search for Ilm. arXiv preprint 2rXiv2247.00032 2024a.
Xiaoxuan Wang, Ziniu Hu, Pan Lu, Yanqiao Zhu, Jieyu Zhang, Satyen Subramaniam, Arjun Loomba, Shichang Zhang, Yizhou Sun, and Wei Wang. Seibench: Evaluating college-level scientific problem-solving abilities of large language models. arXiv preprint ar (XXt:2307710633 2023a.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. ICLR, 2023b.
Zora Zhiruo Wang, Jiayuan Mao, Daniel Fried, and Graham Neubig, Agent workflow memory. arXie preprint 2rXiv:2409.74422 2024b.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarlen Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Shain-of-thoughe prompting elicits reasoning in large language models. NeurIPS, 2022.
Tianbao Xie, Danyang Zhang, Jixuan Chen, Xiaochuan Li, Siheng Zhao, Ruisheng Cao, Toh Jing Hua, Zhoujun Cheng, Dongchan Shin, Fangyu Lei, et al. Osworld: Benchmarking multimodal agents for open-ended tasks in real computer environments. arXiv preprint arXiv:2404.070 079997 2024a.
Yuxi Xie, Anirudh Goyal, Wenyue Zheng, Min-Yen Kan, Timothy P Lillicrap, Kenji Kawaguchi, and Michael Shieh. Monte carlo tree search boosts reasoning via ilerative preference learning, arXiv preprint arXiv:2405.00441, 2024b.
Jianwei Yang, Hao Zhang, Feng Li, Xueyan Zou, Chunyuan Li, and Jianfeng Gao. Set-of-mark prompling unleashes extraordinary visual grounding in gpt-4v. arXiv preprint arXiv:2310.11441, 2023.
John Yang, Carlos E Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofi Press. Swe-agent: Agent-computer interfaces enable automated software engineering. arXiv preprint ar arXiv:2405.15793, 2024a.
Ke Yang, Yao Liu, Sapana Chaudhary, Rasool Fakoor, Pratik Chaudhari, George Karypis, and Huzefa Rang- wala. Agentoccam: A simple yet strong baseline for llmebased web agents. arXiv preprint arXiv:2410.138.. 2024b.
Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. NewrIPS, 2022a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. ICLR, 2022b.
16

---

Published in Transactions on Machine Learning Research (09/2025)
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan, Tree of thoughts: Deliberate problem solving with large language models. NewrIPS, 2024.
Dan Zhang, Sining Zhoubian, Zimiu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. Rest-mets"; Lim self training via process reward guided tree search. ar preprint Skk:2446600810 2024a.
Di Zhang, Jiatong Li, Xiaoshui Huang. Dongzhan Zhou, Yuqiang Li, and Wanli Ouyang. Accessing gpt-4 level mathematical olympiad solutions via monte carlo tree self-refine with llama-3 8b. arXiv preprint arXiv:2406.07394 2024b.
Ziniu Zhang, Shulin Tian, Liangyu Chen, and Ziwei Liu. Mmina: Benchmarking multihop multimodal internet agents. Xiviv preprint 009992244.09992 2024c.
Boyuan Zheng, Boyu Gou, Jihyung Kil, Huan Sun, and Yu Su. Gpt-4v (ision) is generalist web agent, if grounded. arXiv preprint arXi::240100161, 2024.
Andy Zhou, Kai Yan, Michal Shlapentokt-Rollmmnn, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. ICML, 2024a.
Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Yonatan Bisk, Daniel Fried, Uri Alon, et al. Webarena: A realistic web environment for building autonomous agents. ICLR, 2024b.
17

---

Published in Transactions on Machine Learning Research (09/2025)
A
Appendix
In the appendix 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.
Task Instruction (/): "Tell me the the number reviews that our store received by far that mention term 'not useful""
GPT-4o Agent
2
3
4
X
Failure
GPT-4o Agent + Search
0.05
2
8
0.4
V-43
5
6
0.5
V 0.43
v 0.48
V 0.45
10
Success
0.05
0.68
Legend:
Search sequence
Backtracking
State values
Figure 5: 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.
Enabling exploration A significant advantage of models with search is their ability to explore larger parts of the environment compared models without search. Fig. 5 part of the search tree for WebArena task #14 (in the CMS environment), where the model is able take multiple plausible actions the first step (actions 2, and 4 in the graph), and expand the search tree to find the best trajectory (3 - 5 + 10, which achieves the highest value of 0.68). In this case, the model terminates after hitting the search budget (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.
Improving robustness As discussed in Sec. 5.3 the bascline agent can be prone to selecting bad samples from the language model due to randommess from nucleus sampling. Search allows the agent to explore each possibility and identify the best trajectories. VWA shopping task #96 (shown Fig, ( is another example. The baseline agent fails on this task, but the agent with search avoids the first two trajectories (cnding actions and 4) due low values assigned after exploring the subsequent states. It able to prune these and identify successful trajectory (highlighted in Fig.
18

---

Published in Transactions on Machine Learning Research (09/2025)
Task Instruction (7): "I need something like this for my apartment. Can you add one to my wishlist?"
GPT-4o Agent + Search
2
3
V = 0.5
0.98
0.55
Starting State
4
= 0.9
0.45
5
6
Success
= 0.9
1.0
Legend:
Search sequence
Backtracking
v= 1.0
State values
Figure 6: 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 trajectorics (faded nodes the figure) to identify the successful one.
Agent Model
Value Function
Max Steps
Search + Search A
Llama-3-70B-Inssiee (Koh et al.
2024
9.8%
30
GPT-4o + SoM (Khh al. 2024
19.8%
Llama-3-70B-Instte Instruutttt + captions
L.aVA-166-3B
7.6%
13.5%
+77.6%
VWA
Jlama-3-70B--nstruee + captions
GPT-4o
7.6%
16.7%
+119.7%
1Jama-3.--70---nnst + captions
GPT-4o
5
9.1%
16.2%
+78.0%
GPT-4o-mini + SoM
GPT--o--mini
9.1%
14.4%
+58.2%
GPTT-40 + SoM
GPT-44
18.9%
26.4%
+39.7%
GPT-4o Zhou et al.
2024b
13.1%
GPT-4 Rellexion
Pan al.
2024
15.6%
AutoWebGIMM [Lai
2024
18.2%
30
AutoEval [aan et al.
20.2%
BrowserGym (Drouin cl a
2024
23.5%
WA
SteP (Sodhi al. 2024
35.8%
Llama-3-70B-Instree
GPT-4o
7.6%
10.1%
+32.3%
5
GPT-4o
GPT-4o
15.0%
19.2%
+28.0%
Table 8: Success rates (SR) and relative change
(A) for baseline models and models that employ search on the VisualWebArena (VWA) (Koh et al. (2024) and WebArena (WA) (Zhou et al. (024b) benchmarks. We also show other published approaches. Search substantially improves our baseline models, setting new the on VWA.
A.2 Additional Ablations
A.2.1 Value Function Ablations
In Sec. of the main paper, we experimented with using gpt-4o as our value function. In Tab. S we present results using different language models as the agent models and the value functions. We observe that our search algorithm is effective across a range of different model sizes and capabilities. In particular, our approach applied to the Mamm--370B-Tnstrueee and 1VVA-116-34B value function yields 77.6% relative
19

---

Published in Transactions on Machine Learning Research (09/2025)
improvement over the baseline Llama-3-70B 7-0ts---e agent VWA (7.6% to 13.5%), and is fully open sourced and reproducible baseline. For the GPT-40-mini model (a relatively weaker model compared to GPT-40) 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-scarch baseline on VWA (9.1% to 14.4%).
A.3
Implementation Details
A.3.1 Language Model Agents
For all experiments, observations to 3840 tokens. We sample from models using nucleus sampling with 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.
webpage viewport width of 1280, viewport height of 2048, and truncate text
For the GPT-4o agent on VWA, we use the same prompt with SoM prompting from Koh et al. (0244). reproduced in Fig- The model provided with 3 in-context examples. A similar prompt (without the image screenshots) is used for the caption-augmenteed Mama-3-70B-Immg
agent which takes the caption-augmentter 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. 2024b that includes in-context examples (reproduced in Fig. 10
A.3.2 Value Function
As described in Sec. 3.2 we implement the value function So by prompting a multimodal language model with all current and previously seen observations fo1...., Op]. We use a prompt similar to the one from Pan ct al. (2024), 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 failure for tasks that involve multi-step reasoning (c.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 failure a success crtieria. This is necessary as our search occurs over a denser graph (compared to generating and re-ranking trajectorics), and requires a more accurate value function. We refor readers to Chen et al. (024bb 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 lo success. This allows us to collect scores '(0, 0.5, 1}, enabling more finegrained value outputs (in addition 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. I1 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 accossibility tree representations cach page, may further improve its performance (at greater compute and API cost).
A.4
Search Algorithm
Our search procedure described in Sec. 3.3 is summarized in Algorithm. |
A.4.1
Environment Reset
In this section, describe the implementation details of the backtracking used in search procedure:
20

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm 1 Our proposed search algorithm at step /
Require: depth d, branching factor b, search budget c, start state 8,
1: Initialize frontier F t {} as max priority queue
2: Initialize best state & 6 8t
3: Initialize the best score 0 +- -00 Initialize the search counter while do
Sp, Uprev + pop(F)
Backlrack and execute new actions to gel to state 8p
8: Compute the score Up = (L, fo........ ,p3) from current and previous observations
9:
8 s 8
10:
if Up 2 & then
11:
0r 4- Up
12:
8, f Sp end if
13:
14: if up 2 0 then
15:
break (Found a likely successful state) end if
16:
17: if s #26 e then
18:
break (Search budget exceeded)
19: end if
20: if 18: -o.,.., 8pl < then
21: Sample b candidates for the next action from the LM: ab. ~ folop)
22: for i +- 1 to b do
23:
Execute o to get to state o
24: Add new candidate state and the current value to the frontier: F F (s).
25: end for
26: end
27: end while
28: Reset f and s +
29: Go to the best state &,
30: Set + (#actions to get from 8 to 8e)
1. We maintain
priority queue that contains sequences of actions and their score (from the value function). Each element is a sequence of actions that the agent has to sequentially execute starting from the init state (lask dependent, but often the website homepage) to get to state 8 that has the corresponding score v.
2. After execute and add the new sequence to the priority queue with its corresponding score
action (L23 of Algorithm. I append this action to the sequence of actions
3. In order reset the environment get clean slate for the next node to explore, we reset to the initial state again, and repeat the execution of the next sequence of actions starting from step 1.
We implemented backtracking in this fashion, as we found that this was substantially more complete way of resetting the state, opposed to simply clicking the "back" button on the browser for example, as this does not persist certain web states such as the scroll offset, or retain text in text inputs. While our implementation does improve fidelity of backtracking and resets, however does add significant overhead terms of time (see Sec. 5.4 for more discussion).
The exact code implementation details can be found within the available code at seroved_for_reviiie
file of our publicly
21

---

Published in Transactions on Machine Learning Research (09/2025)
You are an autonomous intelligent agent tasked with navigating a web browser. You will be given web-based lasks. These tasks will be accomplished through the use of specific actions you can issue.
Here's the information you'll have:
The user's objective: This is the task you're trying to complete.
The current web page screenshot: This a screenshot of the webpage, with each interactable element assigned unique numerical id. Each bounding box and its respective id shares the same color.
The observation, which lists IDs of interactable elements on the current web page with their text content any, in the format [id] [tagType] [text content). tagType is the type of the element, such as button, link, textbox. text content the text content the element. For example, [1234] [button] ('Add to Cart') means that there is a button with id 1234 and text content 'Add to Cart' the current web page. [ [StalicTeext] [text] means that the element is of some text that is not interactable.
The current web page's URL: This is the page you're currently navigating. The open tabs: These are the tabs you have open. The previous action:
This the action you just performed. It may be helpful track your progress.
The actions you can perform fall into several categories:
Page Operation Actions:
"'click [id]""" This action clicks an element with specific id on the webpage.
"type [id] [content]" " Use this to type the content into the field with id. By default, the "Enter" key pressed after typing unless press_ _ress_enter______ after is set to D, i.e., "typ [id] [content) [0]**
..
''over [id] "": Hover over an element with id.
..
"press [key _o_b) ":; Simulates the pressing of key combination on the keyboard (e.g., Ctrl+v).
"scroll [down]" ... or scroll [up] "" Scroll the page up or down.
Tab Management Actions:
'new tab"";; Open a new, empty browser tab. focus (tab ____ndex]"" "*x Switch the browser's focus to a specific tab using its index.
"close tab" " Close the currently active tab.
URL Navigation Actions:
goto jurl'"" Navigate to specific URL.
go back '; Navigate to the previously viewed page.
go forward" ':; Navigate to the next page (if previous 'go back' action was performed).
Completion Action:
.. ''stop [answer]''; Issue this action when you believe the task is complete. If the objective to find a text-based answer, provide the answer the bracket.
Homepage:
If you want to visit other websites, check out the homepage at http://hoomepage.com It has a list of websites can visit.
http://hooaage.co///eeeeeeee wowoom//pswwwr..iiii html lists all the account name and password for the websites. You can use them to log in the websites.
To be successful, is very important follow following rules:
1. You should only issue action that is valid given the current observation
2. You should only issue one action at a time.
3. You should follow the examples to reason step by step and then issue the next action.
4. Generate the action in the correct format. Start with a "In summary, the next action I will perform is" phrase,
followed by action inside ...... For example, "In summary, the next action will perform is "click [1234]*** "*"
5. Issue stop action when you think you have achieved the objective. Don't generate anything after stop.
Figure 7: System message from Koh et al. (2024) in our SoM agent.
22

---

Published in Transactions on Machine Learning Research (09/2025)
example user:
IMAGES: (1) current page screemshot
OBSERVATION:
[31
[MG] [Image, description: hp fx-7010dn fax machine, url: B08GKZ3ZKD.0.pg
[32]
[HP ABBA 640 Inkjet Fax Machine (Renewed))
[] [ [$279.49]
[33]
BUTTON] [Add to Cart]
334
A [Add to Wish List]
35]
[A] [Add to Compare]
URL: http://oneee http:///onesoopmaket.cooo
OBJECTIVE: What is the price HP Inkjet Fax Machine?
PREVIOUS ACTION: None
example assistant: Let's think step-by-step. This page list the information of HP Inkjet Fax Machine, which is the product identified in the objective. Its price is $279.49. I think I have achieved the objective. I will issue the stop action with the answer. In summary, the next action will perform is .* 'sstop [8279.49] example user:
IMAGES: (1) current page screenshot
OBSERVATION:
Text [/f/food]
[] (extt [homemade]] Obligatory Halloween Pumpkin Loaf!
Submitted by kneechalice t3 yid9lu year ago]
[9] [MMG] []
[] [StaticText]] [Submitted by kneechalice t3 yid9lu year ago]
[10] [A] [kneechalice]
[11] [A] [45 comments]
[] [Static[Text]] [[1 ate] Maple Pecan Croissant Submitted by Accordingto.JP y3hrpn 1 year ago]
[14] [IMG] []
[StaticText]] [Submitted by AccordingtoJP t3 y3hrpn year ago]
[15] [A] [AccordingtoJP]
[16] [ 1204 comments]
URL: http://reddit.com
OBJECTIVE: Tell me what the top comment on the croissant post says.
PREVIOUS ACTION; None
example saample__ssistantt assistant: Let's think step-by-step. This page has a post titled '[T ate] Maple Pecan Croissant', which is the post mentioned in the objective. In order to find the top comment, I will navigate into the comments section of the post. In summary, the next action will perform "* "click [11] example user:
IMAGES: (1) current page screenshot
OBSERVATION:
[]
[ext [What are you looking for today?]
INPUT]
[6] [SLECCT] [Select a category]
[UTTTON
[Search]
[Sttt [Latest Listings]
[StaticTText] [Atlas Powered Audio System w/ Tripod 150.00 $ Music instruments
Borough of Red Lion
(Pennsylvania
2023/11/16]
[IMG] [Atlas Powered Audio System w/ Tripod]
[A] [Atlas Powered Audio System w/ Tripod]
(StaticText]] [150.00 $)
[StaticTText] [Neptune Gaming Console 350.00 $ Video gaming Pennwyn (Pennsylvania) 2023/11/16
URL: http:/ htpp://cllassee cclasssiiiedsssco com
OBJECTIVE: Help find the cheapest dark colored guitar.
PREVIOUS ACTION: None
example assistant: _annptt_ssssttnt:: Let's think step-by-step. The objective is find the cheapest dark colored guitar on the site. The site has search box whose ID is [5]. I can search for guitars by entering "guitar". I can submit this by pressing the Enter afterwards. In summary, the next action will perform is " ""type [guitar] [1]
Figure 8: In-context examples and prompt adopted from Koh et al. (2024) for our SoM agents. The webpage
screenshots with SoM are added to the end of cach round of the example user dialogue.
23

---

Published in Transactions on Machine Learning Research (09/2025)
example user:
OBSERVATION:
[1744]
[ink] [HP CB782A#ABA 640 Inkjet Fax Machine (Renewed)]
[1499
StaticTeext [$279.49]
[1757]
[utton] [Addd to Cart']
[1760] [button] ['Add to Wish List"]
[1761] [button] ['Add to Compare']
URL: http:///onestommakkt.coom httpraarrettooofffieeeeeeeee ceticc-produtss/offceeeeeeee
OBJECTIVE: What the price of HP Inkjet Fax Machine?
PREVIOUS ACTION; None
example assistant: Let's think step-by-step. This page list the information of HP Inkjet Fax Machine, which is the product identified in the objective. Its price is $279.49. I think I have achieved the objective. I will issue the stop action with the answer. In summarry, the next action will perform " "stop [$279.49] " example user:
IMAGES: (1) current page screenshot
OBSERVATION:
[204] [heading] [/fffoodd]
[593] [heading] ['homemade] Obligatory Halloween Pumpkin Loaf!"]
[942] [link] ['[homemade] Obligatory Halloween Pumpkin Loaf!']
[945] [StaticText]] ['Submitted by ']
[30] [link] ["kneechalice" expanded: False]
[1484] [StaticTTexi] [13__id9luu
[949] [time] ['October 31, 2022 10:10:03 AM EDT"
[1488] [StaticTextt] ('1 year ago")
[1489] [link] ['45 comments]]
[605] [eading]] ['[] ate] Maple Pecan Croissant"]
[963] [link] ['[ ate] Maple Pecan Croissant]]
[966] (StaticText]] ['Submitted by ']
[37] [link] ['AcoordingtoJP" expanded: False]
[1494] [StaticText]] _3__hhrpn']
[970] (time) ['October 13, 2022 at 10:41:09 PM EDT"
[1498] [StaticTeext] ['1 year ago']
[1499] [link] [2204 comments"]
URL: http://reddit.com
OBJECTIVE: Tell me what the top comment on the croissant post says.
PREVIOUS ACTION: None
example _ssistann:: Let's think step-by-step. This page has a post titled '[I ate) Maple Pecan Croissant', which is the post mentioned the objective. order find the top comment. will navigate into comments section of the post. In summary, the next action I will perform is "celick [1499] example user:
IMAGES: (1) current page screenshot
OBSERVATION:
[42]
[ink]] [My account:]
43
link] ['Logou']]
44
link] ['Publish Ad']
25
heading] ['What you looking for today?']
143
StttiiTeext] [[Keyword]]
[81]
[extbox] ['e.g., blue used car' required: False]
146]
[StaticTText] ['Category"]
[28]
heading] [TLatest Listings"]
URL: http://classifieds com
OBJECTIVE: Help me find the cheapest dark colored guitar.
PREVIOUS ACTION: None
ecample_assistant: Let's think step-by-step. The objective is find cheapest dark colored guitar on the site. The site has search box whose ID is [5]. I can search for guitars by entering "guitar". I can submit this by pressing the Enter afterwards. In summary, the next action will perform is ""type [81] [guitar] []]-..
assistant:
Figure In-context examples and prompt used for the caption- Llama-3 agent. The webpage accessibility tree is added to the end of each round of the example user dialogue.
24

---

Published in Transactions on Machine Learning Research (09/202))
example. user: user::
OBSERVATION:
17444 [ink] [HH ABBA 640 Inkjet Fax Machine (Renewed))
[1749
StaticTText] [$279.49]
[1757]
button] ['Add to Cart']
[1760] [button] ['Add Wish List"]
[1761]
[button] ['Add to Compare"]
URL: http:///onesoopmrrket
/offcce-rrduucs//offfoooo OBJECTIVE: What is the price of HP Inkjet Fax Machine?
PREVIOUS ACTION: None
example assistant: Let's think step-by-step. This page list the information of HP Inkjet Fax Machine, which is the product identified in the objective. Its price is $279.49. 1 think I have achieved the objective. will issue the stop action with the answer. In summary, the next action will perform is " "stop [$279.19] example_ user:
IMAGES: (1) current. page screenshot
OBSERVATION:
[164] [textbox] I'Search' focused: True required: False]
[171] [button] ['Go']
[174] [lnk]] ['Find directions between two points"]
[212] [heading] ('Search Results]]
[216] [button] ['Close"]
URL: http:///ppnstreeetmap..
OBJECTIVE: Show me the restaurants near CMU
PREVIOUS ACTION: None
example assistant: Let's think step-by-step. This page has search box whose ID is [164]. According the nominatim rule of openstreetmap, can search for the restaurants near a location by "restaurants near". can submit my lyping pressing the Enter afterwards. In summary, the next action will perform type [e6s[[rstassaans CMU][1]'*
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.
25

---

Published in Transactions on Machine Learning Research (09/2025)
system message:
You are an expert evaluating the performance of web navigation agent. The agent designed to help human navigate a website to complete task. Given the user's intent, the agent's action history, the final state of the webpage, and the agent's response to the user, your goal is to decide whether the agent's execution is successful or not. If the current state is failure but it looks like the agent on the right track towards success, you should also output as such.
There are three types of tasks:
1. Information seeking: The user wants to obtain certain information from the webpage, such as the information of product, reviews, the text in comment post, the date of submission, elc. This may be formulated in the intent as "tell me", "what is", or "list out", The agent's response must contain the information the user wants, or explicitly state that the information is not available. Otherwise, e-g. the agent encounters an exception and respond with the error content, the task is considered to a failure. It. is VERY IMPORTANT that the bot response is the stop action with the correct output. If the bot response is not stop (e.g., it is click, type, goto), it is considered failure for information seeking tasks.
2. Site navigation: The user wants to navigate to specific page (which may also be specified in the intent "find", "show me", "navigate Lo"). Carefully examine the agent's action history and the final state of the webpage (shown in the LAST IMAGE) to determine whether the agent successfully completes the lask. It is VERY IMPORTANT that the agent actually navigates to the specified page (reflected by the final state of the webpage, in the LAST IMAGE) and NOT just output the name of the item or post. Make sure that the final url is compatible with the task. For example, if you are tasked to navigate to comment an item, the final page and url should be that of the specific comment /item and not the overall post or search page. If asked to navigate to a page with a similar image, make sure that an image on the page is semantically SIMILAR to the intent image. If asked to look for a particular post or item, make sure that the image on the page is EXACTLY the intent image. For this type task to be considered successful, the LAST IMAGE and current URL should reflect the correct content. No need to consider the agent's 's response. 3. Content modification: The user wants to modify the content agent actually commits to the modification. For example, if the agent writes review click post, the task is considered to be a failure. Carefully examine the agent's 's action history and the final state of the webpage determine whether the agent successfully completes the task. No need to consider the agent's response.
webpage or configuration. Ensure that the
comment but does not
*IMPORTANT*
Format your response into two lines as shown below:
Thoughts: <your thoughts and reasoning process>
Status: "success" or "failure"
On the right track to success: "yes" or "no"
user:
<intent screenshots>
User Intent: intent
<obs sc_seereeehot. 1> ... <obs screenshot d>
Action History: last, actions str
Bot response to the user: mest_response
Current URL: current. url The images corresponding to the user intent are shown in the FIRST [leniinent__imagee images (before the User Intent).
The last (len(ccrensshots) snapshots of the agent's trajectory are shown in the LAST {len (Iensscreenshooss) images. The
LAST IMAGE represents the current state of the webpage.
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.
Figure 11:
26


Reviews:
[{"review_id": "6uKtULe1tW", "reviewer": "Reviewer_UxGu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n1. Conducting better reasoning by combining LLMs and search is an important open problem in the field. To that end, the proposed approach (using best-first search on top of LLMs using an LLM-based value function) is simple and effective, which increases the likelihood of broader adoption in the field.\n\n2. The paper is clear, well-written, and self-contained, with earlier sections clearly explaining the problem, its importance, and the relevant background & related work.\n\n3. The improvements from the proposed best-first search approach works for both GPT-4o and LLaMa-3-70B, with strong improvements observed for both models, which allude to the generality of the proposed approach (rather than just working for one particular LLM).\n\n# Weaknesses\n\n1. I am not convinced regarding the primary comparison in Table 2, which is conducted against the baseline with no search. While I find the findings in Section 5.1 (**Comparison to Trajectory-Level Reranking**) to be informative (i.e. if we just sample multiple times with chain-of-thought prompting from different random seeds, and then pick the best trajectory according to the value function at the end, could this work just as well?), I do not know if the **inference FLOPs comparison** in Figure 3 is comparable across both methods, as the comparison in Figure 3 is primarily against best-first search with a particular tree search budget (c=5 & c=20). For example, if we spend the exact same inference FLOPs, could this simpler \"trajectory-level reranking\" approach work as well as the proposed best-first search approach? In my view, comparing the methods based on the inference FLOPs is a much fairer way to compare the different approaches: Concretely, we would like to find the best approach for a given inference FLOPs budget, so we would need to translate different hyper-parameter choices (e.g. best-first search with c=20, or trajectory-level reranking with 10 trajectories) across different methods to FLOPs to compare them properly.\n\n2. As mentioned in Section 2.3, there has been a lot of prior work on applying MCTS for LLM + search, although not necessarily for building LLM-based agents for realistic web domains (Web Arena & Visual Web Arena). Given the prevalence of prior work on MCTS and LLM-based search, how does the proposed best-first search approach compare with using MCTS with the same LLMs for this benchmark.\n\n3. Some aspects are still unclear or could be improved, as detailed by the questions / suggestions / comments below.\n\n# Questions / Suggestions / Comments\n1. It looks like the best value function is also based on GPT-4o, which comes from the same model family as the LLM that generates the actions & trajectories, although the value function LLM uses a different prompt, and also applies self-consistency across multiple reasoning paths. Have the authors tried using a different LLM for the value function? This might further reduce the correlation between the LLM generator and the LLM value function, and make them more complementary.\n\n2. In Section 4.2, it is mentioned that \"...  increasing from 18.6% to 26.4% ...\". The number on the Table is 18.9% rather than 18.6%. Is one of these a typo?\n\n3. I would suggest adding the trajectory reranking approach as an entry in Table 2, as it is also a (more rudimentary) form of search. Also, I would strongly recommend comparing the entries on Table 2 based on the inference FLOPs, to contextualize how much extra FLOPs are spent on search (whether the proposed best-first search or trajectory reranking or MCTS-based search) vs no search.\n\n4. In Section 5.1, **Varying the value function**, how is partial progress / credit scored when using the Ground-truth value function? It seems like using the LLM-based value function allows a partial score of 0.5, rather than just 0 or 1.\n\n5. Section 5.4 lists the possibility of the LLM agent taking destructive actions. Did the authors encounter examples of this?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to improve the performance of LLM-based agents in interactive web environment benchmarks. To that end, it proposes a best-first search approach to search over the best sequences of actions that would yield the highest value, which is provided by a model-based value function (in this case, provided also by an LLM, albeit one with a different prompt and scoring mechanism than for the LLM used to generate the actions). This best-first search mechanism allows the model to prune parts of the explored search space that are not promising, backtrack to the most promising earlier state, and explore that part of the search space. This exploration terminates when the agent is likely to have found a goal state, or if the exploration budget has been exhausted, in which case the highest-value state found thus far is returned as the output.\n\nExperiments on the WebArena & Visual WebArena benchmarks demonstrate that the proposed approach outperforms the baseline without search, with up to ~40% relative improvement over the baseline, where the largest improvements are observed for problems that are of medium difficulty. Further ablation studies suggest that the model performance increases with a higher search budget, and that using a stronger model (GPT-4o) with self-consistency / marginalizing over different reasoning paths for the value function yields the best result.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. **Critical**: Compare the different search methods, including the proposed best-first search method and also the trajectory reranking method, in addition to the no search baseline, in terms of the inference FLOPs. This will allow us to do a proper & fair comparison across the different methods (Weakness 1).\n\n2. **Strongly Recommended**: Compare with an MCTS baseline on this task, using the same base LLMs (i.e. only varying the search method from best-first search & trajectory reranking to MCTS) (Weakness 2).\n\n3. **Strongly Recommended**: Clarify the questions & incorporate the suggestions above (Weakness 3).", "broader_impact_concerns": "No broader impact concerns come to mind; I find the **Limitations** section satisfactory for addressing the potential risks of the approach & LLM agents more broadly.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "D5AdkqAg3P", "reviewer": "Reviewer_mNMw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Quality\n#### Strengths\n- Approach is intuitive and seems correct\n- Value function design and other adaptations are \n- Experiments are well-designed and extensive \n- Results speak for themselves - the improvement when adding inference-time tree search is clear. \n#### Weaknesses\n- I want to know more about the value function, how it was designed, and how it fits into the particular problem space\n- We aren't grounded into why it's significant to do this for web agents specifically, aside from potential product-type impact (which is genuine value, but not explored in this paper) \n- Though experiments are well-designed and exhaustive, it would be good to have additional domains in some way, or a discussion of what that would require \n\n### Clarity\n#### Strengths\n- Well-written and clear!\n- Results are presented clearly, which is less common than it should be \n#### Weaknesses \n- Fig. 1 is hard to understand - lots of images, little annotation and guidance \n\n### Originality and significance\nI think it is technically true that this is the first work to try this approach specifically on realistic web agent benchmarks. However, it's otherwise a very standard approach. The paper does spend some time discussing problems that are unique to the space and require novel ways of applying the approach, but limited time, and mainly in the limitations section. So we don't get a sense of the breakthrough, even at the task level. So while this is technically original, I wouldn't consider it very original or significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper applies existing best-first tree search at inference time to LLM-based web agents. At each decision step, the agent does a tree search of possible action sequences using a novel value function for this domain. The paper motivates this method with the large search space and lack of supervision and validation signal inherently. Results are then presented on WebArena and VisualWebArena, testing on multiple underlying models and comparing to the same model-based agent without inference-time tree search. Results show 20-40% increase in performance when using inference-time tree search.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Limited. Mainly about significance and adding new domains of experiments.", "broader_impact_concerns": "Great broader impacts section! Unusually well-thought out.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "446cpagHcp", "reviewer": "Reviewer_pBdQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The framework is simple and modular, relying entirely on prompting without any fine-tuning. It uses pretrained VLMs for both action generation and state evaluation, making it broadly applicable across domains.\n- The value function scores the current state based on the full history of the trajectory. This design allows the agent to incorporate long-term context, which is important for tasks with delayed or sparse feedback.\n- The method consistently outperforms prompting-only variants of the same models, demonstrating that structured search brings clear benefits even without additional training.\n\n**Weaknesses**\n* The method underperforms compared to some existing baselines on WebArena, including models that do not incorporate search. Additionally, the paper does not compare with other tree-based or planning-based agents on WebArena, despite their similar motivations and methodologies. This omission weakens the paper’s positioning and raises concerns about the practical competitiveness and novelty of the proposed approach. Furthermore, the lack of in-depth analysis fails to clarify why this direction remains promising despite the weaker empirical results.\n- The value function is implemented solely via prompting a pretrained VLM, without any task-specific tuning or learning. While this keeps the system lightweight, it limits the ability to accurately assess intermediate states—particularly in complex or ambiguous environments—potentially reducing the effectiveness of the search process.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a tree search framework for vision-language model (VLM) agents that performs best-first search over natural language action sequences. At each step, a VLM generates candidate actions, and a value function—implemented via prompting a pretrained VLM—estimates the quality of the resulting state based on the full trajectory. The method is entirely prompt-based and requires no fine-tuning. Experiments on WebArena and VisualWebArena show consistent improvements over prompting-only variants of the same models, though performance lags behind several stronger baseline agents on WebArena.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* To better contextualize the proposed approach, future work should include comparisons with prior tree-based or planning-oriented agents on shared benchmarks like WebArena. In addition, deeper empirical analysis—such as case studies, ablation of search components, or diagnostics of failure modes—would help clarify the method’s strengths and limitations, especially in light of its underperformance against many baselines.\n* Figures illustrating tree search (e.g., Figures 1, 4, 5, 6) lack clear definitions of the actions, resulting states, and value scores, making it difficult to follow the decision-making process. Improving the interpretability of these examples—through explicit annotations and clearer descriptions—would help readers better understand how the model performs search and makes choices.", "broader_impact_concerns": "No broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)