WebNavigator: Global Web Navigation via Interaction Graph Retrieval

Xuanwang Zhang; Yuteng Han; Jinnan Qi; Xinyu Liu; Kunze Meng; Mulong Xie; Zhen Wu; Xinyu Dai

cs.IRMar 20, 2026

WebNavigator: Global Web Navigation via Interaction Graph Retrieval

Authors: Xuanwang Zhang, Yuteng Han, Jinnan Qi, Xinyu Liu, Kunze Meng, Mulong Xie, Zhen Wu, Xinyu Dai

Organizations: National Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · Fellou AI

Abstract

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.

Figures & tables

Figure 1: Overview of WebNavigator. WebNavigator resolves Topological Blindness via a two-phase paradigm. (1) Offline Interaction Graph Construction . A heuristic auto-exploration engine discovers dynamic page observations at zero-token cost and indexes all observations into a vector database. (2) Online Retrieval-Augmented Navigation . The Global-View Navigator implements a three-stage workflow: Retrieve top- $k$ candidates from the Interaction Graph via multimodal retrieval; Reason to identify the optimal target page; and Teleport by computing and executing the shortest path within the Interaction Graph, achieving globally optimal navigation.

Figure 2: Trajectory comparison on a multi-site task (WebArena 760), which requires retrieving a specific customer address from the CMS to plan a route on the Map. WebNavigator achieves human-level planning via navigate(domain, query) actions, whereas the ReAct baseline prematurely terminates due to Topological Blindness. The human expert trajectory is the gold standard.

Panel of Table 1 — Table 1: Main results on WebArena and Online-Mind2Web. Act # denotes the action space size. Success rate (SR) for different website domains. Bold and underlined values indicate the best and second-best performance among non-enterprise agents. Methods and scores marked with $*$ are our reproduced results. Models marked with $\dagger$ are finetuned.

Table 4

Panel of Figure 3 — Figure 3: Ablation study on depth, top- $k$ , selector model, and retriever on the Reddit domain in WebArena. Unless otherwise specified, the default configuration uses depth=3, top- $k$ =30, Gemini-2.5-Flash as the selector, and Jina-embedding-v4 as the retriever. The Selector group compares GPT-4o, Gemini-2.5-Flash, and Qwen3-VL-8B. The Retriever group compares Jina-embedding-v4, Jina-embedding-v4 (dense), and Jina-clip-v2. $*$ denotes dense embedding mode.

Figure 4: Failure analysis on WebArena (Gemini-2.5-Pro).

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Value
Observation	Acc. Tree + Image
Selector	Gemini-2.5-Flash
Selector Input	Intent $i$ + top- $k$ candidate screenshots
Retriever	Jina-embedding-v4
Top- $k$	30
Temperature	0.5

Appendix

Table 4: Global hyperparameters for WebNavigator.

Parameter	Map	CMS	Shopping	GitLab	Reddit
Exploration Depth	1	2	2	2	3
Graph Nodes	16	122	570	838	225
Graph Edges	19	138	627	1,659	295
Branching Factor	1.19	1.13	1.10	1.98	1.31
Construction Time (min)	2.1	23.1	122.1	316.8	31.1

Appendix

Table 5: Per-domain graph construction statistics on WebArena.

Symbol	Description
$\mathcal{Q}$	BFS queue organized by exploration depth
$\mathcal{L}_{d}$	Set of nodes at depth $d$
$\mathcal{R}$	Set of interested accessibility roles (e.g., link , button )
$\mathcal{I}_{v}$	Interactive elements extracted from node $v$
$H_{v}$	Structural hash set $\{h_{e}\mid e\in\text{Elements}(v)\}$
$\Delta H_{v}$	Structural hash difference $H_{v}\setminus H_{v_{\text{parent}}}$

Appendix

Table 6: Additional notation for Algorithm 1

Function	Description
Snapshot	Captures a comprehensive observation of a specific page state, including both visual and structural representations, and returns an interaction graph node representing this page.
ShortestPath	Computes the shortest action sequence from the start node $v_{0}$ to target node $v$ through the partially constructed graph $\mathcal{G}$ . If no path from $v_{0}$ to $v$ exists in the graph, it performs a reverse search from $v$ to find the nearest reachable node that is directly accessible via URL, and then derives the path in the forward direction. Returns an ordered action sequence $\tau=(a_{1},\ldots,a_{m})$ .
ExecutePath	Executes a navigation trajectory $\tau$ in the browser. Navigates to the starting node, then sequentially performs each action to reach the target node.
GetInteractiveElements	Extracts all interactive elements matching the specified accessibility roles $\mathcal{R}$ from the structural observation $o_{v}^{\text{str}}$ .
CreateAction	Constructs an action to trigger the given interactive element $e$ .
ExecuteAndSnapshot	Executes action $a$ on the web page represented by $v$ and returns the Snapshot of the resulting page state.

Appendix

Table 7: Function descriptions for Algorithm 1

Action Type	Description	WebArena	BG	AO	SteP	WebNavigator
click(elem)	Click at an element	✓	✓	✓	✓	✓
type(elem, text)	Type to an element	✓	✓	✓	✓	✓
go_back	Visit the last URL	✓	✓	✓	✓	✓
note(content)	Take notes	-	-	✓	✓	✓
stop(answer)	Stop with an answer	-	-	✓	✓	✓
navigate(domain,query)	Teleport via multimodal retrieval	-	-	-	-	✓

Appendix

Table 8: Comprehensive Comparison of Action Spaces across WebArena, BrowserGym (BG), AgentOccam (AO), SteP and WebNavigator.

Method	Model	Avg. Steps		Avg. Time
Method	Model	All	Multi-site	Avg. Time
WebArena	Claude-Sonnet-4	12.27	13.62	191.6s
WebArena	Gemini-2.5-Pro	9.15	10.98	128.8s
AgentOccam	Claude-Sonnet-4	10.14	14.56	643.3s
AgentOccam	Gemini-2.5-Pro	10.10	14.96	773.6s
WebNavigator	Claude-Sonnet-4	8.93	11.75	635.1s

Appendix

Table 9: Average number of steps and average end-to-end execution time per task on WebArena.

Model	None Rate	Fallback SR
Qwen3-VL-32B	6.8%	43.6%
GPT-4o	3.6%	51.7%
Claude-Sonnet-4	5.3%	58.1%
Gemini-2.5-Pro	9.1%	62.2%

Appendix

Table 10: None return frequency and task success rate on None-triggered tasks across all WebArena tasks.

Method	Qwen3-VL-32B-Instruct	Claude-Sonnet-4	Gemini-2.5-Pro
WebArena	19.1	19.8	15.9
AgentOccam	34.2	49.3	50.4
WebNavigator (Ours)	47.8	57.1	63.3

Appendix

Table 11: WebArena success rate (%) across additional models.

Method	Allrecipes	Apple	Arxiv	BBC News	Cambridge Dictionary
WebVoyager	44.4	51.2	34.9	47.6	69.8
WebNavigator	77.8	51.2	62.8	66.7	90.7

Appendix

Table 12: Success rate (%) on five WebVoyager domains using GPT-4o.

Backbone	Queries	Valid / No Target
GPT-4o	91	74 / 17
Claude-Sonnet-4	61	49 / 12
Gemini-2.5-Pro	50	47 / 3

Appendix

Table 13: Query annotation statistics.

Method	Depth	Total Nodes	Coverage
Heuristic Auto-Exploration Engine	2	48	8/16
Heuristic Auto-Exploration Engine	3	225	16/16
LLM-based Exploration Engine	2	55	8/16
LLM-based Exploration Engine	3	241	16/16

Appendix

Table 14: Comparison of Heuristic Auto-Exploration Engine and LLM-based Exploration Engine on the WebArena Reddit domain. Coverage reports functional entry point discovery out of 16 human-annotated ground-truth points.

Panel of Figure 5 — Figure 5: Representative page states discovered exclusively by the LLM-based Exploration Engine via type-based interactions at depth 3 on the WebArena Reddit domain, including search result pages and form-filling interfaces.

Domain	Depth	Exploration (min)	Embedding & Indexing (min)	Index Size (MB)	API Cost (USD)
Map	1	2.1	0.31	16.18	$0.01
CMS	2	23.1	1.99	103.28	$0.17
Shopping	2	122.1	12.96	470.02	$1.26
GitLab	2	316.8	21.75	677.67	$1.13
Reddit	3	31.1	3.82	164.62	$0.38

Appendix

Table 15: Offline graph construction and indexing cost across WebArena domains.

Component	Avg. Time / Task	Avg. Tokens / Task
Retrieve	2.2 s	83 input
Reason	11.1 s	6,169 input $+$ 1,800 output
Teleport	2.3 s	—
navigate workflow	15.6 s	8,052 total

Appendix

Table 16: Online cost breakdown of navigate .

Method	Model	Avg. Time / Task	Avg. Tokens / Task	SR
AgentOccam	Gemini-2.5-Pro	773.6 s	67,351	50.40%
WebNavigator	Gemini-2.5-Pro	753.5 s	123,684	63.30%

Appendix

Table 17: End-to-end online cost and performance on the WebArena benchmark.

Failure Type	Definition	Count	Share
Topological Blindness	Target page never located during online exploration	37	38.90%
Execution Error	Target page reached but local execution failed	39	41.10%
Step Limit Exhaustion	Step budget exhausted	18	18.90%
Annotation Error	Incorrect ground truth	1	1.10%

Appendix

Table 18: Empty-graph error analysis and classification of regressed tasks.

Web Agents

Web agents use language and vision models to navigate websites, gather information, and complete tasks through interactive interfaces.

See all 174 papers

Mango: Multi-Agent Web Navigation via Global-View Optimization
Apr 20, 2026Weixi Tong, Yifeng Di, Tianyi ZhangMulti-Agent Systems Web Agents
Purdue University
See and Remember: A Multimodal Agent for Web Traversal
Mar 3, 2026Xinjun Wang, Shengyao Wang, Aimin Zhou +1Web Agents Memory-Augmented Language Model Agents
Shanghai Institute of AI for Education, East China Normal University · Shanghai Innovation Institute
WebChallenger: A Reliable and Efficient Generalist Web Agent
Jun 9, 2026Jayoo Hwang, Xiaowen Zhang, Vedant PadwalLLM Agent Memory Web Agents
ML Collective · Independent

Apr 20, 2026J/K move · Enter open · S save

Mango: Multi-Agent Web Navigation via Global-View Optimization

Weixi Tong, Yifeng Di, Tianyi Zhang

Purdue University

Multi-Agent Systems Web Agents

Open paper AskPDF arXiv

Existing web agents typically initiate exploration from the root URL, which is inefficient for complex websites with deep hierarchical structures. Without a global view of the website's structure, agents frequently fall into navigation traps, explore irrelevant branches, or fail to reach target information within a limited budget. We propose Mango, a multi-agent web navigation method that leverages the website structure to dynamically determine optimal starting points. We formulate URL selection as a multi-armed bandit problem and employ Thompson Sampling to adaptively allocate the navigation budget across candidate URLs. Furthermore, we introduce an episodic memory component to store navigation history, enabling the agent to learn from previous attempts. Experiments on WebVoyager demonstrate that Mango achieves a success rate of 63.6% when using GPT-5-mini, outperforming the best baseline by 7.3%. Furthermore, on WebWalkerQA, Mango attains a 52.5% success rate, surpassing the best baseline by 26.8%. We also demonstrate the generalizability of Mango using both open-source and closed-source models as backbones. Our data and code are open-source and available at https://github.com/VichyTong/Mango.

Abstract

Web Agents

Explore similar work

Mango: Multi-Agent Web Navigation via Global-View Optimization

See and Remember: A Multimodal Agent for Web Traversal

WebChallenger: A Reliable and Efficient Generalist Web Agent