Research map / Multi-agent systems and games / LLM agents
WebNavigator: Global Web Navigation via Interaction Graph Retrieval
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes WebNavigator, which builds offline Interaction Graphs of websites with zero-token heuristic BFS exploration and, online, uses a Retrieve-Reason-Teleport Global-View Navigator to jump to target pages, reaching SOTA on WebArena and Online-Mind2Web.
Problem
Web navigation agents perform trial-and-error exploration without access to the global topological structure of websites ("Topological Blindness"), limiting performance especially on cross-site multi-site tasks.
Approach
Pre-explore each website into a directed Interaction Graph with a zero-LLM-cost adaptive BFS, index node screenshots with late-interaction multimodal retrieval, and let the agent call a single navigate(domain, query) action that retrieves candidates, selects one with a multimodal LLM, and teleports along the shortest path.
Key results
- On WebArena multi-site tasks, WebNavigator with Gemini-2.5-Pro reaches 72.9% success, versus 37.5% for CUGA's 35.4%... (CUGA reported 35.4% multisite) and 25.0% for AgentOccam with GPT-4o.
- Overall WebArena success is 63.3% with Gemini-2.5-Pro and 49.9% with GPT-4o; Online-Mind2Web success is 52.7% with Gemini-2.5-Pro.
- Adding the selector raises Reddit-domain task success for Gemini-2.5-Pro from 54.2% (top-1) to 72.9%.
Surprising findings
- Qwen3-VL-8B as selector matches GPT-4o and Gemini-2.5-Flash (75.5% on Reddit), suggesting the reasoning step is offloaded to retrieval.
- Reducing top-k to 10 still yields 71.7% on Reddit, indicating graph completeness matters more than retrieval bandwidth.
Limitations
- Requires an upfront Interaction Graph construction per website before deployment.
- Relies on accessibility trees, so it is ineffective on HTML canvas-based sites.
- Exploration depth is set manually per site.
Experimental setup
Datasets: WebArena Online-Mind2Web WebVoyager
Benchmarks: WebArena Online-Mind2Web WebVoyager
Metrics: success rate Recall@30 top-1 accuracy selector accuracy average steps execution time
Baselines: WebArena BrowserGym Tree search Exact Branch and browse WebPilot Auto-Eval WebDreamer WMA SteP Plan-and-Act Agent-e
Builds on: ReAct AgentOccam WebArena
Closest papers by meaning
- WebLINX: Real-World Website Navigation with Multi-Turn Dialogue (ICML 2024 · similarity 0.87)
- REAL: Benchmarking Autonomous Agents on Deterministic Simulations of Real Websites (NeurIPS 2025 · similarity 0.86)
- WARC-Bench: Web Archive based Benchmark for GUI Subtask Executions (ICLR 2026 · similarity 0.86)
- WebVLN: Vision-and-Language Navigation on Websites (AAAI 2024 · similarity 0.86)
- AutoWebWorld: Synthesizing Infinite Verifiable Web Environments via Finite State Machines (ICML 2026 · similarity 0.86)
- Multimodal Web Navigation with Instruction-Finetuned Foundation Models (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.