The Problem: Topological Blindness
Current web agents navigate like tourists without a map — they can only see the current page and must guess where to click next. We call this Topological Blindness: agents lack access to the global structure of websites, forcing inefficient trial-and-error exploration.
Figure 1: WebNavigator’s two-phase paradigm. Offline: build an Interaction Graph via zero-token heuristic exploration. Online: Retrieve-Reason-Teleport workflow for global navigation.
Our Solution: WebNavigator
WebNavigator transforms web navigation from probabilistic exploration into deterministic retrieval and pathfinding.
Phase 1: Offline Interaction Graph Construction
Before any task, we build a complete map of the website:
- Heuristic auto-exploration discovers all reachable pages via BFS — no LLM needed, zero token cost
- Each page is captured with screenshots, DOM trees, and accessibility trees
- All pages are embedded and indexed into a vector database
Phase 2: Online Retrieval-Augmented Navigation
During task execution, the agent uses a Retrieve-Reason-Teleport workflow:
- Retrieve: Given a navigation query, find top-k relevant pages from the pre-built graph
- Reason: A multimodal LLM selects the best target from candidates
- Teleport: Compute shortest path and execute — zero token cost
Figure 2: On a multi-site task requiring cross-domain knowledge (CMS → Map), WebNavigator achieves human-level planning in 2 actions, while ReAct fails due to Topological Blindness.
Key Results
| Benchmark | WebNavigator | Previous SOTA | Improvement |
|---|---|---|---|
| WebArena (overall) | 63.3% | 45.7% | +38% |
| WebArena (multi-site) | 72.9% | 35.4% | +106% |
| Online-Mind2Web | 52.7% | 41.0% | +29% |
Why It Works
- Complete environmental knowledge — The Interaction Graph captures the full observation space
- Compact action space — Only 6 actions needed (vs. 15+ in prior work)
- Task simplification — Transforms trajectory generation into candidate selection