AI Planning Framework for LLM-Based Web Agents

This paper proposes an AI planning framework that maps LLM-based web agent architectures to traditional search paradigms (BFS, DFS, Best-First) to enable principled failure diagnosis, introducing new evaluation metrics and a human-labeled dataset to demonstrate that different agent strategies excel in distinct aspects of task execution, such as human-like trajectory alignment versus technical element accuracy.

The Gist

Imagine you are trying to teach a very smart, but slightly confused, robot how to do your chores on the internet. You tell it, "Go to the store, buy milk, and then check the weather."

In the past, these robots were like rigid robots following a script: "Click here, then click there." If the website changed slightly (like moving the "Buy" button), the robot would crash.

Now, we have AI Agents powered by Large Language Models (LLMs). These are like super-smart interns who can read and understand your request. But there's a problem: they often act like a black box. You see them click things, but you don't know why they clicked them, or why they suddenly forgot they were supposed to buy milk and started looking at cat videos instead.

This paper is like a diagnostic manual for these AI interns. It gives us a new way to understand how they think, how to spot when they are going wrong, and how to measure if they are actually doing a good job.

Here is the breakdown of their ideas using simple analogies:

1. The Three Ways to Plan a Trip

The authors say that all these AI agents are essentially trying to solve a maze. They categorize them into three distinct "planning styles," comparing them to classic search methods:

• The "Step-by-Step" Agent (The Breadth-First Explorer):

  • Analogy: Imagine you are walking through a forest. At every single step, you stop, look at the three paths right in front of you, pick the best one, take a step, and then stop again to look at the new three paths.
  • How it works: The AI looks at the current webpage, decides on one action (like "click the login button"), does it, sees what happens, and then decides the next move.
  • Pros: It's very flexible. If the website changes, it adapts immediately.
  • Cons: It can get "lost" easily. It might forget the big picture (buying milk) because it's too focused on the immediate next step.

• The "Tree Search" Agent (The Branching Detective):

  • Analogy: This agent is like a detective who draws a map of every possible path before moving. It imagines "If I click here, then what? If I click there, then what?" It explores many branches of the future at once to find the best route.
  • How it works: It keeps a mental tree of possibilities and picks the most promising branch to follow.

• The "Full-Plan-in-Advance" Agent (The Depth-First Planner):

  • Analogy: This is the ultimate planner. Before leaving the house, it writes down the entire itinerary: "1. Open browser. 2. Go to Amazon. 3. Search milk. 4. Click buy. 5. Go to weather site." It commits to this entire list before taking a single step.
  • How it works: The AI generates a full list of steps first, then tries to execute them one by one.
  • Pros: It has a clear goal and is less likely to wander off.
  • Cons: If the website is slightly different than expected (e.g., the "Buy" button is in a different spot), the whole plan falls apart, and the agent might get stuck or give up.

2. The Problem with "Pass or Fail"

Currently, we judge these agents like a teacher grading a test with only two options: Pass or Fail.

• The Flaw: If the agent was supposed to find 5 reviews and it found 4, it gets a "Fail." But that's unfair! It did 80% of the work.
• The Old Way: We only looked at the final result.
• The New Way: The authors say we need to grade the process, not just the result. Did the agent take a weird detour? Did it repeat the same mistake 10 times? Did it recover when it made a mistake?

3. The New Report Card (5 New Metrics)

To fix the "Pass/Fail" problem, they created a new report card with five specific grades:

1. Recovery Rate: If the agent takes a wrong turn, how quickly does it realize its mistake and get back on the right path? (Like a GPS recalculating your route).
2. Repetitiveness Rate: Does the agent keep clicking the same button over and over because it's confused? (Like a dog chasing its tail).
3. Step Success Rate: How many of the steps the agent took actually matched what a human would have done?
4. Partial Success Rate: If the task was "list 3 movies," did it list 1, 2, or all 3?
5. Element Accuracy: Did the agent say it was going to click "Submit," but actually clicked "Cancel"? This measures if the agent's intent matches its action.

4. The Experiment: The Human vs. The Robot

The authors built a new dataset of 794 tasks where humans actually solved the problems step-by-step. This became the "Gold Standard" (the perfect answer key).

They then tested two agents:

1. The Step-by-Step Agent (The WebArena Agent): The standard, flexible one.
2. The Full-Plan-in-Advance Agent (Their new creation): The rigid planner.

The Results:

• The Step-by-Step Agent was better at following the human path. It was more flexible, recovered from mistakes better, and finished more tasks overall (38% success vs 36%).
• The Full-Plan-in-Advance Agent was actually more precise when it did click things. It rarely clicked the wrong button (90% accuracy), but it was too rigid. If the plan didn't match the reality perfectly, it got stuck or gave up.

The Big Takeaway

There is no "one size fits all" AI agent.

• If you are navigating a chaotic, changing website (like a social media feed or a live dashboard), you want the Step-by-Step agent. It's like a hiker who looks at the terrain as they go.
• If you are navigating a strict, predictable system (like a bank portal or an e-commerce checkout), the Full-Plan-in-Advance agent might be better. It's like a train on a track; it's fast and efficient, but it can't handle a broken bridge.

In short: This paper gives us the vocabulary to stop treating AI agents like magic black boxes. It helps us understand how they think, why they fail, and which type of "thinking style" is best for the specific job we need them to do.

Technical Summary

1. Problem Statement

The development of autonomous Large Language Model (LLM) agents for web-based tasks faces a critical transparency and evaluation gap. While LLM agents can interpret complex user requests, they often operate as "black boxes," making it difficult to diagnose why they fail or how they plan.

• The Planning Gap: Current LLM agents lack a unified framework connecting their architectures to traditional AI planning paradigms. This obscures the root causes of failures, such as context drift (losing the original goal over time) and incoherent task decomposition.
• The Evaluation Gap: Existing benchmarks (e.g., WebArena, MiniWoB) rely almost exclusively on binary success/failure metrics. These coarse metrics fail to capture the quality of the execution trajectory, such as the agent's ability to recover from mistakes, avoid redundant actions, or maintain semantic alignment with human reasoning.

2. Methodology

The authors propose a comprehensive framework that treats web browsing as a sequential decision-making process (specifically a Partially Observable Markov Decision Process, or POMDP). The methodology consists of three main pillars:

A. Planning Taxonomy

The paper maps modern LLM agent architectures to three classical search paradigms:

1. Step-by-Step Agents (Breadth-First Search - BFS): The agent observes the current state, generates immediate candidate actions, selects one, and repeats. It prioritizes immediate feedback over long-term planning (e.g., standard WebArena agents).
2. Tree Search Agents (Best-First Search): The agent maintains a search tree of explored states, using a value function to prioritize the most promising branches for multi-step planning.
3. Full-Plan-in-Advance Agents (Depth-First Search - DFS): The agent generates a complete trajectory (sequence of actions) from the initial state to the goal before execution begins. The paper introduces a novel implementation of this paradigm where the plan serves as a persistent "external memory" to prevent context drift.

B. Novel Evaluation Metrics

To move beyond binary success rates, the authors introduce five metrics to assess trajectory quality:

1. Recovery Rate: Measures the agent's ability to return to the human-gold trajectory after deviating.
2. Repetitiveness Rate: Quantifies the proportion of redundant actions (lower is better; inverted for scoring).
3. Step Success Rate: The proportion of human gold-standard steps successfully fulfilled by the agent.
4. Partial Success Rate: Evaluates tasks with multiple required elements (e.g., listing 5 items) to measure how many were completed.
5. Element Accuracy Rate: Compares the agent's intended action (planning phase) with the actual executed action to detect execution failures.

Note: These metrics utilize an LLM-as-a-Judge framework to perform semantic equivalence checks between agent actions and human gold-standard traces.

C. Dataset Construction

The authors created a new ground-truth dataset by manually annotating 794 human-labeled execution traces from the WebArena benchmark. This dataset provides the "gold standard" trajectories required to calculate the reference-based metrics (Recovery and Step Success).

3. Key Contributions

1. Formal Taxonomy: Established a nomenclature mapping LLM web agents to traditional planning strategies (BFS, Best-First, DFS), providing a common vocabulary for analysis.
2. Novel Agent Implementation: Developed and implemented a Full-Plan-in-Advance agent that generates a complete roadmap before execution, serving as a proof-of-concept for DFS-based web agents.
3. Comprehensive Dataset: Created a high-quality dataset of 794 human-annotated trajectories to support fine-grained evaluation.
4. Evaluation Framework: Introduced five new metrics that evaluate the process of task execution (coherence, efficiency, stability) rather than just the final outcome.
5. Empirical Validation: Conducted a comparative study between a baseline Step-by-Step agent and the new Full-Plan-in-Advance agent using the proposed metrics.

4. Results and Analysis

The authors compared the WebArena (Step-by-Step/BFS) agent against their Full-Plan-in-Advance (DFS) agent across 812 tasks.

• Overall Success Rate: The Step-by-Step agent achieved a higher overall success rate (38.41%) compared to the Full-Plan-in-Advance agent (36.29%).
• Alignment with Human Trajectories:
  • Step Success Rate: Step-by-Step (82%) significantly outperformed Full-Plan-in-Advance (58%), indicating the latter struggles to align with human reasoning sequences.
  • Recovery Rate: Step-by-Step (36%) recovered from deviations better than Full-Plan-in-Advance (31%).
• Technical Execution:
  • Element Accuracy: Full-Plan-in-Advance excelled here (89% vs. 82%), suggesting that when it does plan an action, it is highly accurate in identifying the correct target element.
  • Repetitiveness: Full-Plan-in-Advance was slightly better (19% repetitive actions vs. 21%), indicating fewer loops of the same failed action.
• Trajectory Length: Both agents produced significantly longer trajectories than humans (approx. 15–20 steps vs. 8 human steps), but the Full-Plan-in-Advance agent was the longest, often including unnecessary steps due to rigid planning.
• Domain Specificity: Full-Plan-in-Advance performed better in structured domains (Reddit, E-commerce) where UI elements are predictable, while Step-by-Step performed better in dynamic/complex domains (CMS, GitLab).

5. Significance and Implications

• Diagnosis over Outcome: The paper demonstrates that a "failed" task does not necessarily mean a "bad" agent. An agent might fail the final outcome but possess high element accuracy or efficient recovery, which is crucial for debugging and iterative improvement.
• Architectural Selection: The findings suggest that no single planning paradigm is universally superior.
  • Step-by-Step (BFS) is superior for dynamic, partially observable environments (e.g., DevOps dashboards, social media) where the state changes unpredictably.
  • Full-Plan-in-Advance (DFS) is superior for structured, rigid environments (e.g., e-commerce, enterprise portals) where a pre-calculated roadmap prevents context drift.
• Future Directions: The proposed metrics and taxonomy provide a foundation for developing hybrid agents that can switch between planning paradigms based on environmental constraints, moving the field toward more robust and interpretable autonomous agents.