PaperlayerView exact revision on arXiv

Source-linked AI summary

Branch-and-Browse: Efficient and Controllable Web Exploration with Tree-Structured Reasoning and Action Memory

Shiqi He, Yue Cui, Xinyu Ma, Yaliang Li, Bolin Ding, Mosharaf Chowdhury

arXiv:2510.19838v2cs.AIcs.CLcs.LG

TL;DR

Web agents face limited reasoning depth and efficiency: linear methods lack effective backtracking, while tree search can be coarse-grained and costly. Branch-and-Browse combines subtask-aware tree exploration, replay with background reasoning, and page action memory. On WebArena, it reports a 35.8% task success rate and up to a 40.4% reduction in execution time relative to existing methods.

  • Problem

    Linear web-agent methods lack effective backtracking, while search methods can be coarse-grained and computationally costly.

    Source: §1 · p. 1, §2 · p. 3

  • Method

    Branch-and-Browse combines subtask-aware tree exploration, web-state replay with background reasoning, and page action memory shared across branches.

    Source: §1 · p. 2

  • Results

    35.8% task success rate and up to a 40.4% reduction in execution time relative to existing methods are reported on WebArena.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The authors present Branch-and-Browse as a framework combining structured exploration, memory, and acceleration for efficient and reliable LLM-based web agents.

    Source: §6 · p. 9

    The framework operates in a single-browser session and does not parallelize exploration across branches, limiting scalability for highly complex or time-sensitive tasks.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Autonomous web agents powered by large language models (LLMs) show strong potential for performing goal-oriented tasks such as information retrieval, report generation, and online transactions. These agents mark a key step toward practical embodied reasoning in open web environments. However, existing approaches remain limited in reasoning depth and efficiency: vanilla linear methods fail at multi-step reasoning and lack effective backtracking, while other search strategies are coarse-grained and computationally costly. We introduce Branch-and-Browse, a fine-grained web agent framework that unifies structured reasoning-acting, contextual memory, and efficient execution. It (i) employs explicit subtask management with tree-structured exploration for controllable multi-branch reasoning, (ii) bootstraps exploration through efficient web state replay with background reasoning, and (iii) leverages a page action memory to share explored actions within and across sessions. On the WebArena benchmark, Branch-and-Browse achieves a task success rate of 35.8\% and reduces execution time by up to 40.4\% relative to state-of-the-art methods. These results demonstrate that Branch-and-Browse is a reliable and efficient framework for LLM-based web agents.

1 Introduction

Web agents must manage long-horizon reasoning and backtracking in dynamic, partially observable interfaces, but linear prompting and coarse tree search each have limitations. Branch-and-Browse combines subtask-aware tree exploration, replay, and page action memory; on WebArena it reports a 35.8% task success rate and up to a 40.4% reduction in execution time.

1 Introduction

  • Linear prompting lacks effective backtracking, while tree search explores branches independently and incurs redundant exploration and high computational costs.Web tasks also involve diverse context-dependent actions and partial observability, requiring long-horizon reasoning and efficient backtracking.Source: §1 · pp. 1–2
  • Branch-and-Browse combines subtask-managed tree exploration, web-state replay with background reasoning, and page action memory shared across branches.The framework uses subtask control for multi-branch reasoning, replay and evaluation to prioritize branches, and action records to reduce redundancy.Source: §1 · p. 2
  • 35.8% task success rate and up to a 40.4% reduction in execution time relative to existing methods are reported for Branch-and-Browse on WebArena.The authors frame these results as balancing reasoning depth and multi-branch exploration efficiency in dynamic web environments.Source: §1 · p. 2

2 Background

Web agents interact with websites through sequential decisions based on observations, actions, and task intent. Prior approaches offer pieces of structured planning, but the background section identifies a need to integrate subtask awareness, structured exploration, and contextual reasoning while managing branching, inefficiency, and fragmented history.

2 Background

  • Web interaction is framed as sequential decision-making: an agent observes a page and acts toward a natural-language task goal.The action space includes operations such as click, type, URL navigation, and tab management.Source: §2 · pp. 2–3
  • ReAct follows a single reasoning–action trajectory, while Tree Search branches but remains coarse-grained and computationally costly.Other frameworks add structured subtasks, reflection, or predictive reasoning, but the section identifies no unified fine-grained framework integrating these strengths.Source: §2 · p. 3
  • The paper distinguishes branching uncertainty, redundant branch expansion, and lost interaction histories as challenges addressed by tree planning, replay with background reasoning, and page action memory.These mechanisms are respectively associated with controlled exploration and backtracking, reduced redundant exploration, and shared context across branches.Source: §2 · p. 3

3 Design

Branch-and-Browse treats long-horizon web interaction as structured search guided by task planning, subtask control, and page-level memory. It decomposes goals, explores and updates subtasks through page-state feedback, accelerates recovery and branch evaluation, and preserves per-page interaction context for reuse.

3 Design

  • The agent formulates long-horizon web interaction as structured search over a dynamic environment, aiming to reach an observation that satisfies the task goal.A trajectory alternates between selecting actions from the current observation and applying environment transitions.Source: §3 · p. 3

3.1 Fine-Grained Structured Planning

  • Subtask-aware tree exploration decomposes a global instruction, selects promising frontier nodes, and uses page context to adapt subtasks when initial objectives do not match the site.Reason–Act–Evaluation cycles expand candidate actions; successful subtasks advance the workflow, while replay links reuse visited contexts and low-value branches can be pruned.Source: §3.1 · p. 4

3.2 Exploration Acceleration

  • Nearest-URL replay restores the closest cached URL and replays only the remaining actions; background reasoning pre-expands valid linked clicks but defers interactions requiring live context.These mechanisms target recovery from failed trajectories and reduce redundant execution without exhaustively expanding every branch.Source: §3.2 · pp. 4–5

3.3 Page Action Memory

  • Page action memory stores per-page objectives, progress summaries, reason–action histories, snapshots, and attempted actions with relevance and success metadata.When a URL is revisited, cached summaries and actions reconstruct local context; recorded actions also inform later task decomposition and branch pruning.Source: §3.3 · pp. 5–6

4 Evaluation

The evaluation compares Branch-and-Browse with web-agent baselines on WebArena and VisualWebArena, then examines efficiency mechanisms and search hyperparameters. Results cover task success and runtime, including how replay, background reasoning, depth, and branching factor relate to performance.

4.1 Experimental Setup

  • WebArena contains 812 long-horizon tasks across multiple website domains; the evaluation also includes VisualWebArena, a multimodal dataset built on the same WebArena-style stacks.Baselines include single-loop ReAct agents, policy-based strategies, and search-based methods; success rate measures the percentage of tasks reaching the goal state.Source: §4.1 · pp. 6–7

4.2 Main Results

  • 35.8% vs. 19.2% success rate on WebArena: Branch-and-Browse outperforms the Tree Search baseline across 812 tasks.The reported gain is particularly strong on Reddit and GitLab, while Multisite gains are smaller.Source: §4.2 · p. 7, Table 2 · p. 7
  • 39.8% vs. 35.8% overall success rate: adding SteP improves Branch-and-Browse performance, with gains on five domains and unchanged Multisite performance.The hybrid uses SteP to select one action per tree expansion while retaining Branch-and-Browse search, replay, pruning, and page action memory.Source: §4.2 · p. 8
  • 32.7% vs. 26.4% overall success rate on VisualWebArena: Branch-and-Browse improves over Tree Search on every reported site slice.VisualWebArena shifts observations toward rendered pages and visual layout.Source: §4.2 · p. 8, Table 3 · p. 8

4.3 Ablation Studies

  • 40.4% reduction in average task time versus Tree Search: Branch-and-Browse reduces time from 20.8 to 12.4 minutes on successful tasks.Disabling Replay increases time slightly, while removing Background Reasoning produces a larger increase; the authors attribute the latter contribution to overlapping offline inference with exploration and early pruning.Source: Figure 4 · p. 7, §4.3 · p. 8

4.4 Sensitivity Studies

  • 33.7% success rate with only a 3.4-minute increase in average task time at b = 5 and d = 2; increasing either branching factor or search depth improves performance.At d = 0 and b = 1, the framework becomes ReAct augmented with page action memory and achieves 23.9% success; experiments use the same overall search budget.Source: §4.4 · pp. 8–9

5 Related Work

Related work covers web-agent perception and memory, alongside approaches for integrating multimodal inputs and prior interaction histories.

Perception and Web Environmental Understanding

  • Web-agent perception uses text and accessibility trees, screenshots interpreted by vision-language models, or multimodal combinations of visual and other inputs.Examples include SeeClick, which uses screenshots, and MMAC-Copilot, which integrates GPT-4V.Source: §5 · p. 9

Memory and Knowledge Integration

  • Web agents integrate short- and long-term memory, including histories of webpage states and actions or summaries of successful and unsuccessful trajectories.AutoWebGLM uses state-action history, while Agent S combines external web searches with narrative memory.Source: §5 · p. 9

6 Conclusion

Branch-and-Browse combines subtask-aware tree exploration, page action memory, and acceleration mechanisms for LLM-based web agents.

6 Conclusion

  • On WebArena, Branch-and-Browse achieves a 35.8% success rate and reduces execution time by 40.4%.The conclusion presents these results as evidence of a scalable path toward practical, high-performing web agents.Source: §6 · p. 9

Limitations

Branch-and-Browse is limited to a single-browser session and does not explore branches in parallel. It also focuses on search-based control and is not fully integrated with policy-based approaches.

Limitations

  • Exploration is confined to a single-browser session, without parallel execution across branches.The authors identify this as a scalability constraint for highly complex or time-sensitive tasks.Source: Limitations · p. 9
  • The framework focuses on search-based control and has not been fully integrated with policy-based approaches.The authors describe policy-based approaches as potentially complementary.Source: Limitations · p. 9
  • The authors propose multi-session and hybrid policy–search integration as future work to improve scalability and adaptability in dynamic web environments.Source: Limitations · p. 9

Ethical Considerations

The experiments use simulated WebArena environments to avoid real-world data access or unintended interactions. The authors flag privacy, consent, and site-policy concerns for live deployment and recommend safeguards.

Ethical Considerations

Related papers

Loading 2510.19838v2…