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

arXiv:2603.05294v3 Announce Type: replace Abstract: Existing LLM-based web agents struggle on complex, long-horizon tasks due to limited in-context memory, weak planning abilities, and greedy behaviors that lead to premature termination. To address these challenges, we propose SA{}, a hierarchical planning framework that interleaves planning and execution via dynamic ANDOR trees. The framework separates structural planning from LLM-based reasoning, enabling principled error recovery through node repair, systematic exploration of alternatives via OR nodes, and modular plans that can facilitate human intervention. On WebArena (630 tasks), SA{} achieves a sim53% success rate vs. sim46% for AgentOccam, and on complex multi-constraint Amazon shopping tasks, gains reach 10% over the strongest baseline.

Source: arXiv cs.AI | 2026-09-23