# WebNavigator: Global Web Navigation via Interaction Graph Retrieval

arXiv: https://arxiv.org/abs/2603.20366 · HTML: https://mlsanity.com/paper/2603.20366/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 36 references that are in the map.
- First posted on arXiv 20 Mar 2026.

## Builds on (most cited first, 30 of 30)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [OpenHands: An Open Platform for AI Software Developers as Generalist Agents](https://mlsanity.com/paper/2407.16741/) (2024)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [WebVoyager: Building an End-to-End Web Agent with Large Multimodal Models](https://mlsanity.com/paper/2401.13919/) (2024)
- [Agent Workflow Memory](https://mlsanity.com/paper/2409.07429/) (2024)
- [WorkArena: How Capable Are Web Agents at Solving Common Knowledge Work Tasks?](https://mlsanity.com/paper/2403.07718/) (2024)
- [ReasoningBank: Scaling Agent Self-Evolving with Reasoning Memory](https://mlsanity.com/paper/2509.25140/) (2025)
- [Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks](https://mlsanity.com/paper/2503.09572/) (2025)
- [DeepSeek-OCR: Contexts Optical Compression](https://mlsanity.com/paper/2510.18234/) (2025)
- [WebWalker: Benchmarking LLMs in Web Traversal](https://mlsanity.com/paper/2501.07572/) (2025)
- [An Illusion of Progress? Assessing the Current State of Web Agents](https://mlsanity.com/paper/2504.01382/) (2025)
- [The BrowserGym Ecosystem for Web Agent Research](https://mlsanity.com/paper/2412.05467/) (2024)
- [Is Your LLM Secretly a World Model of the Internet? Model-Based Planning for Web Agents](https://mlsanity.com/paper/2411.06559/) (2024)
- [Tree Search for Language Model Agents](https://mlsanity.com/paper/2407.01476/) (2024)
- [Autonomous Evaluation and Refinement of Digital Agents](https://mlsanity.com/paper/2404.06474/) (2024)
- [Web Agents with World Models: Learning and Leveraging Environment Dynamics in Web Navigation](https://mlsanity.com/paper/2410.13232/) (2024)
- [AgentOccam: A Simple Yet Strong Baseline for LLM-Based Web Agents](https://mlsanity.com/paper/2410.13825/) (2024)
- [WebPilot: A Versatile and Autonomous Multi-Agent System for Web Task Execution with Strategic Exploration](https://mlsanity.com/paper/2408.15978/) (2024)
- [AutoGLM: Autonomous Foundation Agents for GUIs](https://mlsanity.com/paper/2411.00820/) (2024)
- [Agent-E: From Autonomous Web Navigation to Foundational Design Principles in Agentic Systems](https://mlsanity.com/paper/2407.13032/) (2024)
- [jina-embeddings-v4: Universal Embeddings for Multimodal Multilingual Retrieval](https://mlsanity.com/paper/2506.18902/) (2025)
- [SteP: Stacked LLM Policies for Web Actions](https://mlsanity.com/paper/2310.03720/) (2023)
- [ExACT: Teaching AI Agents to Explore with Reflective-MCTS and Exploratory Learning](https://mlsanity.com/paper/2410.02052/) (2024)
- [Glyph: Scaling Context Windows via Visual-Text Compression](https://mlsanity.com/paper/2510.17800/) (2025)
- [jina-clip-v2: Multilingual Multimodal Embeddings for Text and Images](https://mlsanity.com/paper/2412.08802/) (2024)
- [Towards Enterprise-Ready Computer Using Generalist Agent](https://mlsanity.com/paper/2503.01861/) (2025)
- [Branch-and-Browse: Efficient and Controllable Web Exploration with Tree-Structured Reasoning and Action Memory](https://mlsanity.com/paper/2510.19838/) (2025)

## Built on by (most cited first, 3 of 3)

- [WebUncertainty: Dual-Level Uncertainty Driven Planning and Reasoning For Autonomous Web Agent](https://mlsanity.com/paper/2604.17821/) (2026)
- [Clearing the Fog: Towards Installing and Refining Proactive Exploration Capabilities in LLM Agents](https://mlsanity.com/paper/2608.14339/) (2026)
- [SynWeaver: Website-Prior Task and Trajectory Co-Synthesis for Web Agents](https://mlsanity.com/paper/2608.12429/) (2026)

## Abstract (arXiv)

Despite significant advances in autonomous web navigation, current methods remain far from human-level performance in complex web environments. We argue that this limitation stems from Topological Blindness, where agents are forced to explore via trial-and-error without access to the global topological structure of the environment. To overcome this limitation, we introduce WebNavigator, which reframes web navigation from probabilistic exploration into deterministic retrieval and pathfinding. WebNavigator constructs Interaction Graphs via zero-token cost heuristic exploration offline and implements a Retrieve-Reason-Teleport workflow for global navigation online. WebNavigator achieves state-of-the-art performance on WebArena and OnlineMind2Web. On WebArena multi-site tasks, WebNavigator achieves a 72.9% success rate, more than doubling the performance of enterprise-level agents. This work reveals that Topological Blindness, rather than model reasoning capabilities alone, is an underestimated bottleneck in autonomous web navigation.