STRUCTUREDAGENT: Planning with AND/OR Trees for Long-Horizon Web Tasks

The paper introduces STRUCTUREDAGENT, a hierarchical planning framework that leverages dynamic AND/OR trees and a structured memory module to overcome the limitations of existing LLM-based agents in executing complex, long-horizon web tasks.

The Gist

The Big Problem: The "Impulsive Browser"

Imagine you hire a very smart, well-read intern (an AI) to go on a complex shopping trip for you. Your request is specific: "Find me three different standing desks under $350 that have a cable tray, and make sure they are all different brands."

Most current AI web agents are like impulsive browsers. They see a desk, think, "Hey, that looks okay," and immediately click "Add to Cart." If they realize later they picked the wrong brand or the price is wrong, they get confused. They often forget what they saw five minutes ago, get stuck in loops, or give up entirely because they can't remember the whole list of rules they need to follow. They are "greedy"—they want to finish the task quickly, even if it means doing it wrong.

The Solution: The "Architect with a Blueprint"

The authors propose STRUCTUREDAGENT. Instead of just browsing, this agent acts like a master architect who draws a blueprint before laying a single brick.

Here is how it works, broken down into three simple concepts:

1. The AND/OR Tree: The "Decision Map"

Imagine the task is a giant tree.

• The Root is your main goal (e.g., "Buy 3 desks").
• AND Nodes are like a checklist. To finish this step, you must do A, B, and C. (e.g., You must find a desk, check the price, and check the brand).
• OR Nodes are like forks in the road. You can take Path A or Path B. (e.g., "Should I search by brand name first, or by price first?").

Most AIs just walk down one path blindly. STRUCTUREDAGENT draws the whole map. If it hits a dead end (a broken link or a wrong price), it doesn't panic. It looks at the map, sees the "OR" fork, and says, "Okay, Path A failed. Let's try Path B." It can backtrack and try a different strategy without losing its mind.

2. The "Backpack of Notes" (Structured Memory)

Imagine you are looking for those desks, but you find 50 of them. A normal AI has a short memory; it might forget the first 20 desks by the time it finds the 21st.

STRUCTUREDAGENT carries a specialized backpack (Structured Memory). Every time it finds a potential desk, it writes down the details in a neat table:

• Desk Name: ErgoRise
• Price: $340
• Brand: Ergo
• Status: Good candidate

If it finds a second desk, it updates the table. If it finds a third, it checks the table to make sure it's not a duplicate. This prevents the AI from wasting time looking at the same desk twice or forgetting the one it found earlier that was perfect. It keeps the "candidates" organized so it can pick the best ones at the end.

3. The "Safety Net" (Error Recovery)

When a normal AI makes a mistake, it often keeps going, hoping for the best, or it crashes.

STRUCTUREDAGENT has a Safety Net. If it tries to click a button and nothing happens (a failure), the system doesn't just say "Oops." It pauses, looks at the "Decision Map," and asks:

• "Did I pick the wrong strategy?" (Try a different search term).
• "Did I miss a step?" (Go back and scroll down).
• "Is this path impossible?" (Cut this branch off the tree so we don't waste time).

It can even ask a human for help if it gets truly stuck, showing the human exactly where the plan went wrong on the map.

The Real-World Result

The researchers tested this on three different "arenas":

1. Amazon Shopping: Finding complex items with many rules.
2. WebVoyager: Navigating real websites to find specific info.
3. WebArena: A simulated world of web tasks.

The Verdict:
The "Architect" (STRUCTUREDAGENT) was much better at the long, hard tasks than the "Impulsive Browser" (standard AIs).

• It didn't give up when things got complicated.
• It remembered the rules better.
• It found the right answers even when it had to try multiple strategies.

Summary Analogy

Think of the old way of AI browsing as driving a car with no GPS, just guessing turns until you get there. If you miss a turn, you might drive in circles.

STRUCTUREDAGENT is like driving with a GPS that also has a co-pilot.

1. The GPS (The Tree) plans the route and shows you all the alternative roads if traffic blocks your way.
2. The Co-pilot (The Memory) keeps a notepad of every gas station and hotel you passed, so you don't forget the one that was perfect.
3. If you hit a roadblock, the Co-pilot doesn't panic; they just look at the map, say "Detour," and keep moving forward.

This paper shows that giving AI a structure (a plan) and a memory (a notepad) makes it a much more reliable helper for complex, real-world jobs.

Technical Summary

1. Problem Statement

The paper addresses the limitations of current Large Language Model (LLM) based web agents when tackling complex, long-horizon tasks (e.g., multi-step shopping, information retrieval across multiple sites). Existing agents struggle due to four primary challenges:

• Limited In-Context Memory: Agents fail to track alternative solution paths or history, especially when web pages exceed token limits (often >20k tokens), leading to the loss of critical context.
• Weak Planning Abilities: Agents lack the capacity to construct and execute complex, hierarchical plans over extended time horizons.
• Lack of Robust Error Handling: Existing agents often fail to recover from mistakes or explore alternative solutions, leading to premature task termination.
• Greedy Decision-Making: Agents tend to make locally optimal choices that satisfy immediate constraints but fail to meet the global user objective, often stopping before all constraints are satisfied.

2. Methodology: STRUCTUREDAGENT

The authors propose STRUCTUREDAGENT, a hierarchical planning framework that interleaves planning and execution. Unlike standard agents that rely on the LLM to generate entire plans, STRUCTUREDAGENT separates responsibilities: the framework manages the global structure and state, while the LLM is invoked only for specific, localized operations.

Core Components

1. Dynamic AND/OR Tree Planner:

   • Structure: The agent constructs a planning tree dynamically during execution.
     • AND Nodes: Represent conjunctive subgoals (all children must succeed).
     • OR Nodes: Represent alternative strategies (any child succeeding satisfies the parent).
     • ACTION Nodes: Leaf nodes corresponding to atomic browser operations (click, type, scroll, note).
   • Traversal Algorithm: The framework uses a Modified Greedy Depth-First Search (DFS).
     • State Management: Nodes track three states: ENTERING (processing), EXITING (evaluation), and FAILED.
     • Dynamic Revision: If an action fails, the agent can backtrack, repair the node (via LLM), or prune the branch.
     • Error Propagation: Failures in child nodes propagate upward, triggering repairs or pruning of the parent node to maintain global plan coherence.
   • Interpretability: The tree structure provides a transparent view of the agent's decision-making, allowing for human intervention (e.g., correcting subgoal decomposition) at any layer.

2. Structured Memory Module:

   • Designed specifically for information-seeking tasks (e.g., finding products with specific constraints).
   • Instead of unstructured notes, the agent maintains a dynamic table of candidate entities.
   • Function: It extracts constraints from the task, tracks candidate items, and updates their status (satisfied/unsatisfied constraints) as new information is gathered.
   • Benefit: This prevents the agent from revisiting rejected pages or losing track of items that partially satisfy constraints, significantly improving performance on multi-constraint shopping tasks.

3. Tree Operations (LLM-Driven):
   The framework prompts the LLM for specific, well-defined tasks:

   • Node Expansion: Determines node type (AND/OR/Action) and generates children.
   • Node Repair: Modifies failed nodes by adding new strategies or pruning infeasible paths.
   • Node Completion Check: Verifies if an AND node's objective is met based on child outcomes.
   • Observation Summarizer: Condenses raw HTML and interaction history into concise summaries to manage context limits.

3. Key Contributions

• Hierarchical Planning Framework: Introduces a system that uses ordered AND/OR trees to enable compositional reasoning, dynamic plan revision, and error back-propagation, moving beyond simple sequential planning.
• Structured Memory for Constraint Satisfaction: Develops a novel memory module that tracks candidate entities and their constraint satisfaction states, addressing the "forgetting" problem in long-horizon tasks.
• Interpretability and Human-in-the-Loop: The explicit tree structure allows for easy debugging and human intervention, enabling operators to correct subgoal decompositions mid-execution.
• Robustness: The system decouples the global planning logic from the LLM, making the agent more robust to LLM hallucinations and failures by confining LLM queries to local tree operations.

4. Experimental Results

The framework was evaluated on three benchmarks: WebVoyager, WebArena, and a custom Complex Shopping benchmark (Amazon tasks).

• Performance Gains:
  • Amazon Shopping: STRUCTUREDAGENT achieved the highest success rates (83.3% on Easy, 35.6% on Hard tasks using human evaluation), outperforming strong baselines like AgentOccam by ~14% on Easy tasks and ~7% on Hard tasks.
  • WebArena: Achieved an overall success rate of 52.6%, outperforming AgentOccam (~46.4%) and other baselines by significant margins, particularly in Shopping and Reddit categories.
  • Model Generalization: The framework performed well with different backbone models (Claude 3.5, Claude 3.7, Kimi-k2), demonstrating that the planning architecture provides benefits independent of the base LLM's raw capability.
• Efficiency vs. Exploration:
  • On harder tasks, STRUCTUREDAGENT takes more actions and time than baselines. The authors argue this is a trade-off for systematic exploration and error recovery, which leads to higher success rates where greedy agents fail prematurely.
• Structured Memory Impact:
  • The Structured Memory module provided a 5% boost on complex Amazon Hard tasks but slightly degraded performance on simpler tasks, confirming its utility is specific to multi-constraint, information-seeking scenarios.

5. Significance

This work represents a significant step forward in agentic AI by shifting the paradigm from "LLM as a planner" to "LLM as a local executor within a structured framework."

• Solving Long-Horizon Tasks: It demonstrates that explicit, hierarchical planning is essential for tasks requiring deep reasoning and memory retention over many steps.
• Reliability: By managing the search space and error recovery explicitly, the system reduces the "greedy" behavior common in LLMs, leading to more reliable task completion.
• Human-AI Collaboration: The interpretable nature of the AND/OR tree bridges the gap between autonomous agents and human oversight, allowing for corrective intervention when the agent's logic diverges from the user's intent.

In conclusion, STRUCTUREDAGENT proves that combining dynamic hierarchical search with structured memory creates a robust, interpretable, and high-performing agent capable of navigating the complexities of the modern web.