Abstract
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.
Introduction: The Challenges of Web Navigation
Building autonomous web agents is a complex challenge due to the inherent messiness and high branching factor of web environments. Current Large Language Model (LLM) agents typically follow one of two flawed strategies. Linear prompting methods, such as ReAct, take steps sequentially; if the agent makes a mistake—such as clicking an incorrect filter—it lacks an effective mechanism to backtrack, often resulting in total task failure. Conversely, coarse tree search strategies explore multiple paths but often do so "blindly," ignoring previous attempts and leading to redundant actions and high computational costs.
Researchers have identified three primary hurdles: branching uncertainty (deciding which link to click), exploration inefficiency (repeating work), and contextual fragmentation (losing insights gained on previous branches).
Methodology: The Branch-and-Browse Framework
Branch-and-Browse introduces a fine-grained architecture designed to unify reasoning and execution through three core components:
- Subtask Manager: Instead of attempting a complex goal in one go, the framework decomposes the user's intent into a hierarchy of manageable subtasks. This allows the agent to track progress and maintain grounding throughout long-horizon tasks.
- Tree-Structured Exploration: Navigation is treated as a search problem. The agent maintains a "frontier" of potential states and utilizes Background Reasoning to evaluate branches before execution, pruning irrelevant paths early.
- Page Action Memory: This global cache records the outcomes of actions at the URL level. By sharing "aha moments" across different reasoning paths, the agent avoids redundant exploration. If one branch discovers a dead end, other branches are immediately aware.
To optimize execution, the framework employs Nearest-URL State Replay. Rather than re-executing every click to backtrack, the agent jumps to the nearest cached URL and replays only the essential intermediate actions (like typing or tab switching) to reconstruct the necessary state.
Experimental Results
The framework was evaluated on WebArena, a high-fidelity benchmark featuring 812 long-horizon tasks across diverse platforms including GitLab, Reddit, and e-commerce sites. Branch-and-Browse achieved a 35.8% success rate, a significant improvement over the standard Tree Search baseline of 19.2%.
Beyond success rates, the framework demonstrated massive efficiency gains. Average execution time dropped from 20.8 minutes to 12.4 minutes—a 40.4% reduction. These gains were most pronounced in complex, interactive environments like Reddit and GitLab, where structured backtracking is essential for technical workflows.
Conclusion and Future Work
Branch-and-Browse demonstrates that fine-grained, memory-augmented search is superior to both linear and coarse search methods for web agents. While the framework currently operates within a single browser session, future work may explore parallelizing exploration across multiple instances and extending the "Action Memory" across different tasks to allow agents to gain experience over time. By unifying structured reasoning with efficient execution, Branch-and-Browse provides a robust foundation for the next generation of autonomous web assistants.
Summary updated