Beyond Completion: Charting a Path for Intelligent Web Agents

by

Author: Denis Avetisyan

A new framework analyzes how AI agents navigate the web, moving beyond simple task success to understand the quality of their decision-making.

The evaluation of two agent architectures-Step-by-Step and Full-Plan-in-Advance-across the WebArena benchmark demonstrates performance averages across multiple domains, highlighting a comparative analysis of planning strategies in complex web-based tasks.
The evaluation of two agent architectures-Step-by-Step and Full-Plan-in-Advance-across the WebArena benchmark demonstrates performance averages across multiple domains, highlighting a comparative analysis of planning strategies in complex web-based tasks.

This review introduces a planning-based approach to evaluating autonomous web agents and proposes novel metrics for trajectory analysis and performance assessment.

While large language models demonstrate promise in automating web-based tasks, their internal reasoning remains largely opaque, hindering systematic diagnosis of failures. This limitation motivates the work presented in ‘AI Planning Framework for LLM-Based Web Agents’, which formally connects modern LLM agent architectures-including step-by-step, tree search, and full-plan-in-advance approaches-to established AI planning paradigms like breadth-first, best-first, and depth-first search. By introducing a taxonomy and five novel evaluation metrics beyond simple success rates, this framework allows for nuanced trajectory analysis and reveals trade-offs between human alignment and technical accuracy. Can this principled approach to agent evaluation ultimately guide the development of more robust and interpretable autonomous web agents tailored to specific application needs?

The Web’s Unforgiving Nature: A Challenge for Automation

The development of genuinely autonomous web agents faces considerable hurdles stemming from the intricate and ever-shifting nature of online spaces. Unlike static, predictable environments, the web is characterized by a vast, loosely structured collection of interconnected documents, constantly updated and presenting information in diverse, often ambiguous formats. An agent must not only locate relevant information, but also interpret its meaning within context, adapt to changing website layouts, and handle unpredictable user interfaces – tasks that demand robust perception, reasoning, and learning capabilities. This dynamism necessitates agents that can move beyond pre-programmed responses and exhibit genuine adaptability, continually refining their strategies to navigate the web’s inherent complexity and achieve their objectives effectively.

Conventional techniques in artificial intelligence often falter when applied to the web due to its fundamentally unstructured and ambiguous nature. Unlike curated databases, web content lacks consistent formatting, relies heavily on natural language – rife with nuance and context-dependency – and is in a constant state of flux. This presents a significant hurdle for agents attempting to interpret information, identify relevant data, or complete tasks; simple keyword matching or pre-programmed rules prove inadequate when confronted with the variability of online text and the lack of explicit semantic tagging. Consequently, researchers are actively exploring novel approaches – including advanced natural language processing, machine learning models capable of understanding context, and reinforcement learning strategies that allow agents to adapt to dynamic environments – to enable robust and effective web navigation and task completion.

The Step-by-Step agent demonstrates consistent success rates across WebArena domains, outperforming the Full-Plan-in-Advance agent, which exhibits more variable performance.
The Step-by-Step agent demonstrates consistent success rates across WebArena domains, outperforming the Full-Plan-in-Advance agent, which exhibits more variable performance.

Breadth-First Exploration: A Systematic Approach

The StepByStepAgent utilizes a Breadth-First Search (BFS) strategy for web exploration, systematically examining webpages in a level-by-level order. This means the agent first identifies all immediately accessible links on an initial page, then explores those links before moving to links found on those pages, and so on. This deliberate, layered approach contrasts with depth-first methods and ensures comprehensive, though potentially slower, coverage of the web space. By prioritizing breadth over depth, the agent aims to discover a wide range of available options at each stage of exploration before committing to a specific path, mirroring the systematic nature of the BFS algorithm.

The ‘StepByStepAgent’ utilizes an ‘AccessibilityTree’ to represent the underlying structure and content of webpages, enabling more informed action selection. This tree, generated from web page elements and their relationships, provides a navigable representation of the page beyond the raw HTML. By parsing the AccessibilityTree, the agent can identify interactive elements like buttons and links, as well as textual content and headings, allowing it to reason about the page’s functionality and purpose. This structured understanding facilitates targeted actions, as the agent can directly address specific elements within the tree rather than relying on potentially unreliable heuristics or visual cues.

The WebArena benchmark offers a controlled and reproducible environment for assessing the efficacy of step-by-step web agents. It facilitates performance evaluation through a series of defined web-based tasks. To enable comprehensive comparative analysis, WebArena includes a dataset consisting of 794 annotated human trajectories. These trajectories represent human solutions to the benchmark tasks, providing a baseline for measuring agent performance and identifying areas for improvement. The dataset allows for quantitative comparisons between agent behavior and human strategies, utilizing metrics such as task completion rate, path length, and action efficiency.

The Full-Plan-in-Advance agent incorrectly predicted a scrolling action instead of posting a comment for the merge request in task 392, resulting in a 'null' action being executed.
The Full-Plan-in-Advance agent incorrectly predicted a scrolling action instead of posting a comment for the merge request in task 392, resulting in a ‘null’ action being executed.

Depth-First Planning: The Illusion of Foresight

The FullPlanInAdvanceAgent diverges from reactive approaches by constructing a complete sequence of actions prior to initiating execution. This methodology mirrors the Depth-First Search (DFS) algorithm utilized in computer science, where the agent explores a single branch of possible actions as deeply as possible before backtracking. Rather than responding to immediate states, the agent simulates potential action sequences to identify a comprehensive plan for achieving the designated goal. This pre-planning phase allows the agent to anticipate future states and select actions based on the projected outcome of the entire plan, rather than solely on the current environment.

Robust StateSpaceSearch capabilities are central to the FullPlanInAdvanceAgent’s operation, requiring the systematic exploration of potential action sequences to determine viable paths toward goal completion. This involves evaluating the projected outcomes of each action, considering environmental constraints and object states, to construct a complete plan before execution. The agent utilizes algorithms to assess the feasibility and optimality of these sequences, often employing heuristics to prioritize exploration and manage computational complexity. Effective StateSpaceSearch necessitates data structures for representing states, actions, and transitions, as well as mechanisms for backtracking and pruning suboptimal paths to efficiently identify a solution or determine that no solution exists within the defined search space.

The Full-Plan-in-Advance agent exhibited a Step Success Rate of 58% and an Element Accuracy Rate of 89.89% during evaluation. These metrics indicate the agent’s ability to successfully complete individual steps within a task and accurately identify and manipulate relevant elements, respectively. Performance benchmarks demonstrate that these rates represent an improvement over existing agents operating in the same environment, suggesting the efficacy of the complete, pre-execution planning strategy employed by this agent.

Despite correctly reasoning that scrolling is needed to locate submissions by PatientBuilder499 in the videos subreddit, the Full-Plan-in-Advance agent failed to execute the action, instead performing a ‘null’ operation.
Despite correctly reasoning that scrolling is needed to locate submissions by PatientBuilder499 in the videos subreddit, the Full-Plan-in-Advance agent failed to execute the action, instead performing a ‘null’ operation.

Beyond Completion: Measuring True Intelligence

Traditional task completion metrics offer a limited view of agent performance; assessing how closely an agent replicates human problem-solving strategies requires supplementary metrics. Specifically, the ‘Step Success Rate’ quantifies the percentage of individual actions that align with optimal or typical human behavior, providing insight into the agent’s procedural correctness. Complementing this, the ‘RecoveryRate’ measures the agent’s ability to correct errors and return to a successful trajectory after a suboptimal step, mirroring a key aspect of human adaptability and resilience. These metrics, in conjunction with task completion rates, offer a more nuanced evaluation of an agent’s intelligence and behavioral fidelity.

The Full-Plan-in-Advance agent exhibited a Repetitiveness Rate of 19%, signifying a relatively low incidence of redundant actions during task execution. This metric quantifies the proportion of actions that duplicate previous steps within a given plan. Complementing this, the agent achieved a Recovery Rate of 31%, representing the frequency with which it successfully continued task completion after encountering an initial failure. The Recovery Rate demonstrated a standard deviation of 0.19, indicating moderate variability in its ability to recover across different task instances or environmental conditions.

The evaluation of the Full-Plan-in-Advance agent utilizes a framework comprising five distinct metrics designed to assess performance beyond simple task completion. Within this framework, the agent achieved a Partial Success Rate of 0.12, indicating the frequency with which it partially completed the assigned task. The observed Partial Success Rate is accompanied by a standard deviation of 0.27, representing the variability in performance across multiple trials and providing a measure of the reliability of this result.

The agent’s decision-making process involves reasoning about the previous action (A), generating a rationale (B), incorporating metadata (C), and selecting the next action (D) as demonstrated in this example step.
The agent’s decision-making process involves reasoning about the previous action (A), generating a rationale (B), incorporating metadata (C), and selecting the next action (D) as demonstrated in this example step.

The pursuit of elegant AI planning for LLM-based web agents, as detailed in this framework, feels predictably optimistic. It’s a well-structured attempt to move beyond simple task completion and assess trajectory quality – a noble goal. However, one suspects that even the most sophisticated evaluation metrics will inevitably be circumvented by the sheer creativity of production environments. As Brian Kernighan observed, “Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not going to be able to debug it.” This holds true; the framework meticulously charts a course for agent behavior, but the reality of autonomous web agents will invariably involve unforeseen interactions and edge cases, turning meticulous planning into damage control. It’s a beautiful system, destined to be stressed, broken, and ultimately, patched with pragmatic solutions.

What’s Next?

This framework, while offering a vocabulary for dissecting LLM-based agent behavior, inevitably highlights what it cannot measure. Trajectory analysis, even with novel metrics, remains a rear-view mirror assessment. The true cost of autonomy – the subtle degradations of information quality, the amplification of biases embedded in the LLM, the sheer waste of computational resources chasing ill-defined goals – will not yield to simple success/failure ratios. Each layer of abstraction, each attempt to ‘simplify’ web interaction, simply introduces new failure modes, new vectors for unexpected behavior.

The inevitable proliferation of these agents necessitates a shift in focus. Evaluation will move beyond demonstrating capability and towards quantifying risk. How does an agent’s ‘planning’ impact the information ecosystem? How readily does it succumb to adversarial prompts, or simply hallucinate plausible-sounding falsehoods? These are not questions of improved algorithms, but of fundamentally recalibrating expectations.

Ultimately, this work is a temporary reprieve. It defines a problem space that will, within the next cycle, become a maintenance burden. CI is the temple – and the prayers for unbroken pipelines will only grow louder. Documentation, of course, remains a myth invented by managers.

Original article: https://arxiv.org/pdf/2603.12710.pdf

Contact the author: https://www.linkedin.com/in/avetisyan/

See also:

2026-03-16 22:22