We thank the reviewer for their detailed review. We are glad that they found our method novel, the paper logically organized, and the experiments and ablations comprehensive. We are pleased that they recognized the effectiveness of our proposed tree search approach, and the findings reproducible and credible. We address specific questions below and will incorporate all feedback.

On innovation/novelty of the approach

However, as tree search techniques are commonly used in other systems, this approach exhibits limited innovation.

While it is true that tree search is commonly used in other systems (from as early as the 1950s, as we highlighted in Sec 2.3), we respectfully disagree that this limits the innovation of our approach. The primary contribution of our paper is to show the viability of such a search algorithm on complex, highly realistic websites, such as those in (Visual)WebArena. Adapting search for this domain: implementing backtracking, building an effective value function, is non-trivial. Here we show, for the first time, through extensive ablations and analysis, what is needed to make search effective in these complex and realistic web environments (for which the value function is not clear-cut, unlike in previous applications in math and games). Please also see our top-level response to all reviewers for further discussion.

Execution time compared to other approaches

In Sec A.2.2 and Figure 6 in the appendix, we compared the search approach (c=5) against a re-ranking approach adapted from [1] that generates and re-ranks multiple trajectories (up to 7). The n=5 case of the re-rank approach uses comparable compute to our search procedure, as c=5 expands 5 nodes at each search step (similar to generating 5 trajectories). Our results highlight that our approach scales more effectively than this generate-and-re-rank method, which suggests that our search approach uses computation more efficiently

Moreover, as the cost of LLM inference continues to improve (due to hardware and ML systems innovations), we believe that cost of search will decrease and it is likely to become even more practical over time. Exploring ways to improve the efficiency and computational cost of search (as well as the inference cost of base LLM agents) is an exciting direction for future work.

References

[1] Pan, Jiayi, et al. "Autonomous evaluation and refinement of digital agents." arXiv preprint arXiv:2404.06474 (2024).

Results for larger c

In Figure 2, it can be observed that there is a noticeable improvement as the search budget c increases from 15 to 20. Have the authors attempted to experiment with a larger c? This might yield better results.

Due to compute and budget limitations, we were unfortunately unable to run full experiments with larger $c$ values, but our scaling curve (Figure 2) suggests that our search algorithm is not yet saturated at $c=20$. In future work with access to more resources, it will be valuable to expand this beyond $20$, and develop more comprehensive "scaling laws" for the search budget, breadth and width hyperparameters, and the baseline agent model.

Max search budget and performance

We detailed the performance with increasing $c$ in Figure 2, as well as the performance when we increase the depth and breadth of the search tree (Table 3). We find that the results align with intuition: as more search is conducted, success rate generally improves. We also find that aside from scaling $c$, we also need to scale the depth and the breadth of the search tree to achieve the best results (see Sec 5.1 of the main paper for more detailed discussions).

We thank the reviewer for their helpful comments. We are glad that they recognized that our approach addresses several critical challenges faced by LLM web agents, and that they appreciated the clarity of the approach and the structure of our paper. We address specific questions below and will incorporate all feedback.

Novelty

We thank the reviewer for the references: we had discussed [1,2] in the related work, and have now updated the manuscript to cite and discuss [3,4] as well. While using tree search for LLMs is not new, we respectfully disagree that our approach is incremental. Previous work, including the provided references, primarily focused on quantitative tasks (such as math, science, coding) which have more clearly defined value functions, such as execution tests, or highly simplified web environments (such as MiniWoB or WebShop as in [1]). In contrast, our approach shows viability for the first time on complex, highly realistic websites, such as those in (Visual)WebArena. For example, the shopping environment in (V)WA is far more complex than that of WebShop, with advanced search mechanisms, an account creation system, and end-to-end shopping cart checkout. Developing a search algorithm -- implementing backtracking accurately, experimenting and developing a value function that is good enough -- is non-trivial, and here we show this viability for the first time, achieving substantial gains over a baseline without search.

Moreover, as also highlighted by the reviewer, one of the highlights of our approach is that it is simple, straightforward, and effective. The value of our paper is not in coming up with a convoluted solution, but showcasing for the first time how we can build a general search algorithm for realistic web tasks. We also refer the reviewer to the comments in our top-level response for further details.

Evaluating the value function

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

We agree that it could be beneficial to have a value function specific evaluation. At the moment, we do not believe there exists a good benchmark to measure the effectiveness of value functions for web tasks, but we agree that developing such a benchmark (similar to RewardBench [5] but for web agents) would be a very valuable contribution.

Since our work has shown that value functions can substantially improve web agents, future work that evaluates and improves value functions is complementary to our findings, and should improve agents further. We see this not as a limitation of our work, but an opportunity for future work.

References

[5] Lambert, Nathan, et al. "Rewardbench: Evaluating reward models for language modeling." arXiv preprint arXiv:2403.13787 (2024).

Performance vs. SOTA

As the main contribution of our work is to introduce a general tree search algorithm for LLM web agents, we aim to reduce domain specific knowledge in the base agents, which many SOTA methods employ (as also highlighted by reviewer fowi and discussed in our response above). Our experimental results in Table 6 and 7 also demonstrate that our approach doesn’t overfit to a specific type of website, and shows consistent effectiveness over all websites in both WA and VWA.

Due to our compute and budget limitations, we were also unable to run it for extended horizons (all our experiments were limited to a maximum of 5 steps), which also negatively affected performance compared to other SOTA baselines (which typically run for around 30 steps). We also believe that our method is complementary to advances in efficiency and ML systems research, and is likely to benefit from these improvements in the near future. For these reasons, we believe that the efficiency and time consumption problems are not significant hurdles to practical deployment.

We thank the reviewer for their comprehensive review, and for these detailed suggestions that will make the paper more readable! We are glad that they found the paper to be of high quality, the results strong and clear, and recognized the significance of our approach in introducing test-time compute for LM web agents.

Other SOTA WebArena results

We agree that many state-of-the-art approaches include domain specific biases that are tailored for WebArena, and we indeed opted to develop a more general tree search methodology that can be applied to any baseline agent. In practical deployment scenarios, it will likely be useful to still include some of these domain specific tweaks (including to our value function and our search algorithm) but we will leave these for practitioners to explore and experiment with.

Backtracking feasibility and implementation

We agree that in many real world web settings it is difficult to backtrack. However, search is likely still useful for many economically valuable web tasks which can be trivially parallelized (and for which destructive actions are not a concern). For example, the same Google Sheets document can be copied n times and we can run search over the n tabs in parallel.

Other web tasks can also be parallelized similarly if we have an effective way to avoid destructive actions (e.g., by implementing a denylist for pages such as checkout), such as exploring multiple categories in parallel on a shopping site to find the best item. Of course, significant work will need to be done to make this viable in production, but there are already many existing real world scenarios where search can be both practical and effective.

For our backtracking implementation, we have added section A.4.1 to the appendix of the manuscript with more implementation details, and will include code pointers once the code is publicly released. Please also see our top-level response to all reviewers for further discussion.

More inference time compute required

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

We believe that this is a feature rather than a weakness: our approach indeed expends more computation at inference, but achieves better results as more search is performed (Figure 2 and Table 3). While at present it may be impractical to apply the full search algorithm on all tasks, we believe that search unlocks a valuable "knob" that can be used to tradeoff performance and inference compute for web agents. For example, we can perform less (or no) search for easy tasks, while expending more compute on harder or more consequential tasks to get better results. Please also see our top-level response to all reviewers for more details.

Tie-breaking

In the event of ties we keep the original node (the one that was explored first, which had a higher value than other options at that point in time). We ran an ablation where we broke ties by preferring the most shallow node, and on the 200 example ablation subset this achieved a score of 34.5%. Breaking ties by preferring deeper trajectories achieved a score of 35.0%. Both of these are slightly worse compared to the success rate of 37.0% when we keep the original path. Breaking ties by the number of "votes" would definitely be interesting to explore in future extensions but would likely require taking even more samples during search to reduce noise.

Table 2 results vs. ablation subset

Indeed, this is likely because the sampled set of the first 100/50/50 tasks of VWA shopping/reddit/classifieds have easier difficulty levels than the full set (perhaps due to how VWA was originally constructed). The full dataset compared to the ablation subset has the following statistics:

MSE of value function

This would be an interesting metric, but for the (V)WA tasks, MSE would likely be less interpretable than the success rate numbers in Table 4, as most nodes have a groundtruth value of 0. Early termination (when the groundtruth is 0) is as detrimental as failure to correctly terminate (when the groundtruth is 1), which also makes it harder to interpret MSE in some of these cases.

Other suggestions

Thank you for the detailed suggestions! We have incorporated most of the feedback in the revised draft. However, as we do not have sufficient space within the ICLR page limit, we opted to leave the algorithm in the appendix, as we felt that the high level overview of the approach in Figure 1 provided a better introduction for new readers. We added a reference in Figure 1's caption to point to the location of the algorithm details.

We thank the reviewer for their helpful comments. We are pleased that the reviewer found the experimental results practical, and our proposed method effective. We are glad that the reviewer recognized the generality of our search algorithm. We address specific queries below, and have incorporated all feedback into the revised manuscript.

Requiring increased computational resources

The search algorithm demands significant computational resources due to the increased number of environment interactions. This may limit its practical applicability in real-time or resource-constrained environments.

We believe that this is a feature rather than a weakness: our approach indeed expends more computation at inference, but achieves better results as more search is performed (Figure 2 and Table 3). While at present it may be impractical to apply the full search algorithm on all tasks, we believe that search unlocks a valuable "knob" that can be used to tradeoff performance and inference compute for web agents. For example, we can perform less (or no) search for easy tasks, while expending more compute on harder or more consequential tasks to get better results. Please also see our top-level response to all reviewers for further discussion.

Quality of the value function

success of the best-first search depends heavily on the quality of the value function

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

We agree, and this is true for almost all approaches that use search. For some domains (e.g., chess or Go) the value function is 100% deterministic and accurate — but for general web domains, this is not the case. For these reasons, it’s difficult to build a perfect value function. We chose self-consistency for this paper primarily because it performed well empirically (see Table 4), but we believe that there is a lot that future work can do.

In particular, we believe that finetuning reward models specifically for web tasks will be a very promising future direction, and is likely to improve our approach significantly (but this may require much more compute resources and labeled data than is available to us at present).

Destructive actions

The primary goal of our paper is to demonstrate the viability of a tree search algorithm (for the first time) in complex and realistic web environments. One existing practical deployment scenario that we discussed in Sec 5.4 is to run the algorithm in environments where actions are always reversible, e.g., Google Docs or Google Sheets.

However, we agree that deployment of such algorithms in general real world web environments requires more engineering work (and briefly discuss what might be required for this in our Ethics Statement). We believe that this is a very important direction for future work to explore, but also believe that it is out of the scope of this paper.

Performance on more complex or longer tasks

How does the search algorithm perform on tasks with very high action complexity or longer required sequences? Are there any indications that increasing the search budget might lead to diminishing returns in such cases?

Our results actually suggest the opposite: that search is likely to be more effective on more complex or longer tasks. Sec 5.2 of the paper includes a breakdown of tasks according to their. In the VWA benchmark, easy tasks are defined as those that require a human 3 or fewer actions to complete, medium tasks require 4-9, and hard tasks require 10 or more. Our results show that search actually results in larger relative improvements on medium (+75%) and hard tasks (+47%) compared to easy tasks (+24%), which likely do not benefit from as much exploration and planning. For the hard tasks, we believe that this is also because our compute limitations did not allow us to run search over trees deeper than 5 nodes (see Sec. 5.2), which is why many hard tasks (which are defined in VWA to require more than 10 actions) did not benefit as much from search as medium tasks.

Environment resets

We have added section A.4.1 to the appendix of the manuscript with more implementation details, and will include code pointers once the code is publicly released. Please also see our top-level response to all reviewers for more discussion.

Safeguards or heuristics for repetition

Are there any safeguards or heuristics incorporated to prevent the agent from becoming stuck in specific repetitive or irrelevant actions during search?

In our current implementation, we did not introduce such mechanisms, as we opted to develop a general approach that can be deployed to a variety of web environments. For specific use cases, this would make a lot of sense (e.g., we might stop the shopping agent from ever going to the pages with the "/checkout" suffix in their URL).