WebOperator: Action-Aware Tree Search for Autonomous Agents in Web Environment

1 INTRODUCTION

• Web agents’ greedy decisions are fragile because a single incorrect action can make a goal unreachable, while partial observability limits agents to browser-visible state.Without explicit backtracking, agents struggle to correct mistakes or systematically explore alternatives.Source: §1 · pp. 1–2
• WebOperator uses action-aware best-first search and verified backtracking to explore alternative paths while avoiding unreliable replay and unsafe execution.It classifies actions as safe or destructive and prioritizes safe, reversible actions before deferring destructive ones.Source: §1 · pp. 2–3
• WebOperator addresses invalid and redundant candidates, unreliable state reversal, destructive actions, and the high computational cost of exhaustive tree search.It adapts and validates actions, generates candidates from varied contexts, merges equivalent actions, uses speculative execution with snapshot validation, and applies pre- and post-execution heuristics to identify destructive actions.Source: §1 · pp. 2–3
• Experiments on WebArena and WebVoyager, together with ablations and analyses, are presented to assess WebOperator’s effectiveness, capabilities, and limitations.The introduction says Table 1 compares prior methods by features and Figure 1 provides an operational overview, but does not report benchmark results.Source: §1 · p. 3

2.1 PROBLEM DEFINITION: TREE SEARCH IN WEB ENVIRONMENTS

• Web environments are modeled as E = (S, A, T, O), with persistent and temporary states and potentially stochastic action-driven transitions.Actions include clicking, filling forms, navigating, and terminating; observations expose snapshots such as the DOM, page content, and URL.Source: §2.1 · p. 3
• Tree search represents reachable states as nodes and actions as edges, seeking a path from the initial state to a goal state.The observation function maps environment states to agent-visible snapshots, including DOM, page content, and URL.Source: §2.1 · p. 3

2.2 ACTION CLASSIFICATION

• Safe actions modify only reversible temporary state, while navigational actions change the URL and reset temporary state without changing persistent state.These actions comprise most exploratory tree-search steps.Source: §2.2 · p. 3
• Destructive actions alter persistent state and may be irreversible, so WebOperator applies them only when necessary and uses safety checks.Examples include server-side changes, form submissions, and updates to browser storage or cookies.Source: §2.2 · p. 4
• Terminating actions signal a stopping point without changing the environment, whereas invalid actions would cause execution errors.Invalid actions include using an invalid URL, interacting with disabled or nonexistent elements, filling a read-only field, or going back from the initial page.Source: §2.2 · p. 4

3.1 ACTIONS GENERATION

• WebOperator varies action-generation context, adapts action types to feasible options, rejects invalid or ineffective actions before execution, and merges semantically equivalent candidates.These mechanisms aim to produce high-quality, diverse candidates while reducing irrelevant exploration and redundant expansions.Source: §3.1 · p. 4

3.2 THE CHALLENGE OF DESTRUCTIVE ACTIONS

• Pre-execution action and element heuristics and post-execution HTTP-request checks detect destructive actions; confirmed changes invalidate prior states and restart search from the current state.GET requests are typically treated as non-destructive, while POST, PUT, DELETE, and PATCH requests indicate possible server-side changes.Source: §3.2 · pp. 5–6

3.3 BACKTRACKING

• Backtracking jumps to the nearest refresh-stable URL checkpoint and replays only minimal UI actions, while parallel-tab snapshot validation aborts mismatches before changing the main environment.Successful replay is committed to the main environment only when all stored snapshots match.Source: §3.3 · pp. 6–7

3.4 ACTION SELECTION

• Frontier priorities are recomputed using action type and search context, favoring safe reversible actions early and deferring destructive actions until strategically justified.A fixed frontier budget prunes actions that cannot be reliably backtracked to and limits destructive actions to the highest-rewarded candidate.Source: §3.4 · p. 7

4.1 EXPERIMENTAL SETUP

• WebArena comprises 812 evaluator-verified tasks across four domains; experiments use BrowserGym with gpt-4o-2025-01-01 and compare LMTS, WebPilot, and Branch-and-Browse.The task set comes from 241 parameterized templates.Source: §4.1 · p. 7

4.2 MAIN RESULTS

• On WebArena, WebOperator with gpt-4o achieves 54.6% overall success, outperforming all existing methods, with 76.4% on Reddit, 52.8% on GitLab, and 55.0% on CMS.The comparison covers both tree-search and non-tree-search web agents.Source: Table 2 · p. 8, §4.2 · p. 8
• With a 20-step budget, WebOperator reaches 54.6% SR versus 35.8% for Branch-n-Browse and 37.2% for WebPilot under matched gpt-4o conditions.SR rises from 24.4% at budget 5 to 54.6% at budget 20; at budget 10, WebOperator reaches 42.7%, surpassing prior tree-search methods using larger budgets.Source: Table 3 · p. 8, §4.2 · p. 8

4.3 BACKTRACKING ANALYSIS

• Approximately 40% of successful tasks require at least one backtrack, while fewer than 3% require five or more.The distribution is reported across WebArena task domains.Source: §4.3 · p. 8, Figure 4 · p. 9

4.4 DESTRUCTIVE ACTION HEURISTICS

• Only about 37% of actions flagged pre-execution are confirmed as destructive, while post-execution checks verify persistent-state changes and support re-rooting after irreversible changes.The lightweight pre-check conservatively flags potentially state-altering actions, trading precision for efficient node expansion.Source: Figure 5 · p. 9, §4.4 · p. 9

4.5 ABLATION STUDIES

• On WebArena-lite, action validation raises single-action success from 49.03% with a dynamic action space to 53.55%, versus 47.74% for the base ReAct agent.Action validation also yields the lowest average action count, 8.67.Source: §4.5 · p. 9, Table 4 · p. 10
• Action merging and context variation raise multi-action success to 54.84% after multi-action generation expands exploration to 24.06 average actions.The improvement comes with a slight increase of 1.24 in average action count.Source: §4.5 · p. 9, Table 4 · p. 10
• On WebArena-lite, naive tree search falls to 51.61% from 54.84%, while destructive-action handling plus context-aware selection reaches 58.71% and speculative execution reaches 60.00%.The full approach generates 31.34 actions versus 24.79 for naive tree search, a 6.55-action increase accompanying an 8.39-percentage-point success gain.Source: §4.5 · pp. 9–10, Table 4 · p. 10

5 RELATED WORK

• LMTS (Koh et al., 2024), LATS (Zhou et al., 2024), Branch-and-Browse (He et al., 2025), WebPilot (Zhang et al., 2025b), and WebRollback (Zhang et al., 2025c) expand and evaluate candidate actions with backtracking.These systems improve robustness on long-horizon tasks but rely on replay-based restoration, limited action validation, and heuristic handling of dynamic or irreversible transitions.Source: §5 · p. 10
• WebOperator integrates destructive-action detection and speculative backtracking into tree search, with recovery mechanisms designed for partially observable, non-deterministic web environments.It also aims to improve destructive-action handling and action generation quality and diversity.Source: §5 · p. 10
• WebGuard (Zheng et al., 2025) classifies action risk, while InferAct simulates candidate effects; both generally keep safety checks outside the core planning loop.WebGuard blocks or flags potentially harmful interactions, and InferAct warns users before risky commands.Source: §5 · p. 10

• WebOperator achieves state-of-the-art performance on WebArena and demonstrates strong, superior generalization on WebVoyager.Source: §6 · p. 11
• Its integrated approach combines high-quality action generation, reliable speculative backtracking, and strategic handling of destructive operations.Source: §6 · p. 11
• The framework addresses partial observability, non-determinism, and irreversible actions through robust, efficient exploration that balances safety with long-term foresight.Source: §6 · p. 11

REPRODUCIBILITY STATEMENT

• The repository provides BrowserGym-based code, benchmark configurations for WebArena, WebArena-lite, and WebVoyager under official protocols, hyperparameters, experiment logs, and scripts to reproduce all experiments with minimal setup.The hyperparameter settings include search and frontier budgets and thresholds for destructive or terminating actions.Source: REPRODUCIBILITY STATEMENT · p. 11

LIMITATIONS

• Speculative backtracking may fail in highly dynamic websites, while destructive-action heuristics can miss unconventional interactions and permit irreversible changes.Speculative backtracking remains a safety backup when heuristic detection fails.Source: LIMITATIONS · p. 11
• Reward-model accuracy, limited frontier size, and mistaken early termination constrain evaluation, exploration, and search duration.The authors propose stronger destructive-action detection, dynamic-page handling, improved process reward models, and multi-user or collaborative environments as future work.Source: LIMITATIONS · p. 11

A.1.1 REPHRASED INSTRUCTION

• A.1.1 reformulates instructions to clarify ambiguities, emphasize important details, and highlight edge cases for the agent.The rephrased goal is intended to make the input more reliably interpretable.Source: §A.1.1 · p. 14

A.1.2 ADAPTIVE OBSERVATION SPACE

• A.1.2 adapts observations to tree size: small trees are fully provided with scrolling disabled, while large trees show viewport elements with scrolling enabled.This balances context completeness with tractability under model input limits.Source: §A.1.2 · p. 14

A.1.3 INCORPORATING ALERTS INTO THE ACCESSIBILITY TREE

• A.1.3 detects JavaScript alerts and adds them to the accessibility tree so the agent can reason about their content and respond.Alerts are not normally part of that tree but can contain task-relevant errors or confirmation prompts.Source: §A.1.3 · p. 14

A.1.4 CONCISE HISTORY REPRESENTATION

• Because full trajectories can exceed context windows, A.1.4 summarizes observations and provides only the last N steps’ summaries, thoughts, and actions.This preserves a meaningful trajectory history while keeping context size manageable.Source: §A.1.4 · p. 14

A.1.5 INTEGRATING PAST EXPERIENCE

• A.1.5 retrieves the k most similar prior observation-thought-action tuples from a static trajectory database, as in Go-Browse (Gandhi et al., 2025).The retrieved examples provide experience with repetitive interaction patterns, aiming to improve efficiency and robustness to minor UI variations.Source: §A.1.5 · pp. 14–15

A.1.6 DYNAMIC ACTION SPACE

• WebOperator enables actions conditionally based on the current state, preventing impossible or meaningless operations and reducing irrelevant exploration and uninformative errors.Examples include enabling scrolling when scrollable elements are visible and tab controls only when multiple tabs are open.Source: §A.1.6 · p. 15

A.2 OUTPUT PROCESSING

• Each decision output separates the agent’s reasoning, concrete action, and concise observation summary to provide an interpretable trace reusable in subsequent steps.The observation summary highlights relevant elements and changes for future reasoning.Source: §A.2 · pp. 15–16

A.2.1 ACTION VALIDATION LOOP

• A hybrid validation loop checks most actions against the DOM or simple heuristics and tests complex cases in a temporary tab before execution.Only actions predicted to succeed run in the working environment; failed validation prompts feedback and an internal retry, which is omitted from the trajectory.Source: §A.2.1 · p. 16

A.2.2 AUTO CORRECTION

• WebOperator automatically corrects minor output mistakes, such as selecting the first of multiple generated actions or capitalizing a Boolean parameter to valid syntax.The example converts false to False in a fill action.Source: §A.2.2 · p. 16

A.2.3 RECOVERY ASSISTANCE

• When errors occur despite validation, WebOperator provides detailed feedback and can use context-dependent recovery actions; it also permits human intervention for captchas.For an invalid page such as a 404, it may go back or close the tab, depending on context.Source: §A.2.3 · p. 16

A.2.4 GENERATING MULTIPLE CANDIDATE ACTIONS

• Multiple candidate actions are generated by varying context, including navigation-history length, retrieved past experiences, and task-goal phrasing, to improve diversity and robustness.The method addresses the low diversity often produced by repeated sampling from an identical prompt.Source: §A.2.4 · p. 16

A.2.5 PROCESS REWARD MODEL FOR CANDIDATE ACTIONS

• The process reward model scores candidate actions without executing them, using a checklist of task sub-goals to estimate their expected productivity.Following WebShepherd (Chae et al., 2025), the checklist is generated from the task instruction and initial observation, and supports ranking and selection.Source: §A.2.5 · p. 17

A.2.6 ACTION MERGING FOR EFFICIENT EXPLORATION

• Equivalent actions are merged by combining their predicted rewards, prioritizing stronger collective options and reducing redundant exploration.The stated criteria include identical function names and parameters, multiple stop actions, and fill actions whose text matches after normalization.Source: §A.2.6 · p. 17

B.1 MODEL

• Experiments use GPT-4o with temperature 0.7 for action generation.Source: §B.1 · p. 17

B.2 RETRIEVAL

• Retrieval uses Go-Browse data (Gandhi et al., 2025), URL preprocessing for the WebArena setup, and all-MiniLM-L6-v2 embeddings.Queries contain the goal and observation; retrieved examples provide the goal, thought, and action as agent context.Source: §B.2 · p. 18

B.3 ACTION GENERATION

• Three prompt variations generate up to three actions per step; invalid actions receive feedback and up to five retries, while other agents or tree backtracking can provide alternatives.If all agents succeed, the system gets three valid actions; otherwise, it gets fewer, and five unsuccessful retries lead to failure.Source: §B.3 · p. 18

B.4 PROCESS REWARD MODEL

• A GPT-4o-generated checklist of natural-language subgoals tracks progress toward the user’s goal and provides the basis for reward prediction.The paper follows WebShepherd for checklist generation.Source: §B.4 · p. 18
• Each checklist-item reward combines the probability of “Yes” with half the probability of “In Progress,” and the final reward averages item scores.The same model generates checklists and rewards in the experiments, though the paper says these models can differ.Source: §B.4 · p. 18

C SEARCH ALGORITHM

• Search expands observations into candidate actions, scores and merges them, then prioritizes reward and action type while checking speculative backtracking feasibility before browser execution.Tree nodes store accessible observations rather than full states.Source: C SEARCH ALGORITHM · pp. 18–19

D BACKTRACKING

• WebOperator defines backtracking as restoring an ancestor state and executing the actions needed to reach a previously visited state where a promising action was proposed.The ideal procedure finds the lowest common ancestor, undoes actions to it, then replays the path to the target.Source: D BACKTRACKING · p. 19
• Safe actions can typically be reversed, but destructive actions may lack inverses and nondeterministic actions make reversal unreliable, so ideal backtracking in the main environment is infeasible.These challenges include clicks, form submissions, and dynamic content changes.Source: D BACKTRACKING · p. 19
• WebOperator reduces replay overhead by jumping to the target’s closest checkpoint, defined by refresh-stable observation and a URL distinct from its parent, then replaying only necessary UI interactions.URL navigation reconstructs the checkpoint state before incremental interactions recover the exact target state.Source: D BACKTRACKING · p. 20
• WebOperator validates backtracking in a parallel tab against stored snapshots, aborting on mismatches without changing the main environment and committing only after successful replay.It dynamically remaps tab-focus indices to account for differences between actual and speculative tab configurations.Source: D BACKTRACKING · p. 20

E ACCESSIBILITY TREE-BASED OBSERVATION COMPARISON.

• For backtracking verification, WebOperator records each action’s pivotal accessibility-tree node and snapshot, and uses semantic flexibility rather than requiring exact tree structure.The pivotal node corresponds to the UI element involved in the action, such as a button or text field.Source: E ACCESSIBILITY TREE-BASED OBSERVATION… · p. 20
• WebOperator checks whether the pivotal node’s ID exists and its role, label, value, and enabled state remain equivalent in the current accessibility tree.A missing node or non-equivalent semantic attributes indicates a backtracking mismatch.Source: E ACCESSIBILITY TREE-BASED OBSERVATION… · p. 21
• WebOperator also compares the pivotal node’s ancestors, descendants, and the children of its ancestors; matching local context makes observations equivalent.This localized check tests whether the UI around the action-critical element has changed enough to invalidate the action.Source: E ACCESSIBILITY TREE-BASED OBSERVATION… · p. 21

F GENERALIZATION TO REAL-WORLD WEBSITES.

• WebOperator’s largest gains occur on knowledge-intensive or structurally complex sites, including ArXiv (+31.25%) and HuggingFace (+17.65%).The results indicate robustness to deep navigation and multi-step decision-making.Source: F GENERALIZATION TO REAL-WORLD WEBSITES · p. 21
• On ambiguous sites, WebOperator avoids catastrophic failures seen with AgentOccam, including BBC News improving from 0.00% to 50.00%.The paper characterizes this as more reliable behavior under ambiguity.Source: F GENERALIZATION TO REAL-WORLD WEBSITES · p. 21
• On straightforward transactional sites such as Amazon and Booking, both methods achieve near-perfect accuracy.Source: F GENERALIZATION TO REAL-WORLD WEBSITES · p. 21
• On direct retrieval sites such as Google Search, AgentOccam performs slightly better, while WebOperator may incur overhead when the optimal path is trivial.The passage describes this as a trade-off with WebOperator’s strength in decision-heavy environments.Source: F GENERALIZATION TO REAL-WORLD WEBSITES · p. 21
• 63.57% accuracy on the WebVoyager subset lets WebOperator surpass AgentOccam’s 48.84%.The comparison is reported for the WebVoyager subset.Source: Table 6 · p. 21, F GENERALIZATION TO REAL-WORLD WEBSITES · p. 21

G QUALITATIVE EXAMPLE

• Figure 8 presents a step-by-step tree-search walkthrough for task webarena.421, corresponding to the overview in Figure 1.Source: G QUALITATIVE EXAMPLE · p. 21, Figure 8 · p. 22

H ERROR ANALYSIS

• Incorrect termination can end tasks prematurely, while destructive actions can invalidate needed states despite safety thresholds.Termination may fail because of incorrect reward assignment or a lack of productive actions; destructive actions can create dead ends.Source: H ERROR ANALYSIS · p. 23
• Ambiguous instructions, limited domain knowledge, non-intuitive interfaces, and delayed or generic error feedback can hinder task execution and recovery.The Reddit example shows a delayed “500 Internal Server Error” after several form fields are filled, making the cause difficult to diagnose.Source: H ERROR ANALYSIS · p. 23, Figure 9 · p. 23

I PROMPT

• The action-generation prompt asks the agent to describe relevant page information, reason cautiously about alternatives, and issue one formatted action.It also instructs the agent to use only the supplied action commands and avoid repeating actions in a loop.Source: I PROMPT · p. 28
• The rephraser prompt requires a meaning-preserving task paraphrase, subgoals, ambiguities or assumptions, and cautions, without relying on domain-specific knowledge.Its example for a GitLab status change calls for verifying the account, locating the status interface, saving the text, and confirming the result.Source: I PROMPT · pp. 28–29
• The checklist prompt asks for key milestones and assumes an authenticated session, while the evaluator rates checklist progress as Yes, In Progress, or No.The evaluator also assesses whether the agent’s reasoning is appropriate and its action advances the task.Source: I PROMPT · pp. 29–30
• The prompt defines browser controls for selecting options, filling fields, scrolling, navigating to URLs, managing tabs, and moving through page history.It recommends using discovered URLs rather than random ones and notes that scrolling can reveal hidden page elements.Source: I PROMPT · p. 32
• For content-writing fields and final answers, the prompt requires exact goal-matching text because evaluation uses an exact string matcher.The fill instruction says to reproduce the goal text exactly for posts, messages, and similar content; the stop instruction likewise requires the answer to match the goal and observations for Q&A tasks.Source: I PROMPT · p. 32
• The prompt requires a single strictly formatted action after separate Observation Description, Reason, and Action sections.The observation should extract goal-relevant information and identify useful interactive elements; the reasoning should assess ambiguity, alternatives, and prior actions without looping.Source: I PROMPT · p. 32