Not All Graphs Are Maps: A Task-Agnostic Exploration Framework for Mobile GUI Navigation

Adamo Orsini; Seyed Mehdi Ayyoubzadeh; Sadman Rakib Pinon; Hannuo Zhang; Koosha Gholipour Baradari; Yuanhao Yu; Xinxin Zuo; Yang Wang

cs.AIOct 15, 2026

Not All Graphs Are Maps: A Task-Agnostic Exploration Framework for Mobile GUI Navigation

Authors: Adamo Orsini, Seyed Mehdi Ayyoubzadeh, Sadman Rakib Pinon, Hannuo Zhang, Koosha Gholipour Baradari, Yuanhao Yu, Xinxin Zuo, Yang Wang

Organizations: Concordia University · Mila – Quebec AI Institute · McMaster University

Abstract

Modern mobile GUI agents can perceive visible screens and execute local actions, but they still lack persistent app-specific navigation knowledge: where functions live, which pages contain them, and which screens are equivalent across repeated visits. We introduce TAG-Nav, a Task-Agnostic Graph Navigation framework that wraps existing GUI-agent backbones with reusable destination memory. Offline exploration is distilled into compact records of app functions, target pages, and waypoint routes before any evaluated instruction is seen. When a future task's destination is covered, TAG-Nav retrieves the destination and provides route guidance without task-specific demonstrations. This separates mobile GUI destination navigation from full task completion: many tasks share the prefix of reaching the right page, while final actions may enter content, send data, make purchases, delete information, or change sensitive settings. To evaluate route finding without downstream execution confounds, we introduce DestBench, a navigation-only protocol that asks whether an agent reaches the correct pre-action destination screen. DestBench enables a controlled graph-memory study comparing no-memory agents with random, automated BFS, and clean graph memory. Graph-derived memory improves strict navigation success rate of UI-TARS-1.5-7B from 52.4% without graph memory to 58.3% with automated BFS memory, and improves Qwen-VL-Max success rate from 59.5% to 71.4% on the same conditions. Together, TAG-Nav and DestBench show that destination coverage and route cleanliness strongly shape graph-memory value, making graph quality a measured variable rather than an assumed benefit of exploration.

Figures & tables

Systems	What is retrieved online	Actor
AutoDroid, AppAgent ( Wen et al., 2024 ; Zhang et al., 2025a )	Per-element hints or app docs	No
KG-RAG, GUI-explorer ( Guan et al., 2025 ; Xie et al., 2025 )	Trajectory pairs or current-screen cues	No
PG-Agent, GraphPilot ( Chen et al., 2025b ; Yu et al., 2026 )	Page-graph guidelines or one-shot plans	No
TAG-Nav	Destination page + waypoint route	Yes

Table 1: Positioning of TAG-Nav against representative graph- and memory-augmented GUI agents. Two axes capture the main difference: the unit of memory retrieved online, and whether that memory wraps an unmodified stepwise visual actor. Detailed per-system positioning (exploration mode, graph structure, actor pipeline) is deferred to Appendix G .

Figure 1: Overview of TAG-Nav on an Amazon instruction . Offline exploration builds a hypernode app graph, post-processing distills indexed states into destination records, and online navigation retrieves candidate records, selects $r^{\ast}$ , and formats the selected record as destination memory for an unchanged GUI agent. The figure writes $r_{i}$ for the formal record $r_{h,n}$ with $i=(h,n)$ and uses $s_{t}$ only as schematic exploration-state notation; the formal online/evaluation trajectory uses screenshots $x_{t}$ .

Figure 2: Memory units retrieved at inference by representative graph- and memory-augmented GUI agents. AutoDroid and AppAgent retrieve a per-element hint anchored to a specific UI control; KG-RAG retrieves an intent-trajectory pair (a flat replay of how a similar past task was completed); PG-Agent and GraphPilot retrieve page-level guideline text. TAG-Nav instead retrieves a structured destination record with a named target, page summary, route, and transition hints, and injects it into an unmodified visual actor (UI-TARS, Qwen-VL). The categorical difference between TAG-Nav and prior work is the shape of the retrieved memory unit, not the presence of memory.

App	Tasks	Records	Hypernodes	Edges	Covered
Google Maps	24	415	364	1,192	20
Amazon	17	287	257	652	8
YouTube	15	229	196	483	9
Settings	9	94	84	128	7
Clock	9	93	91	322	6
Calendar	10	50	40	182	5

Table 2: Per-app task distribution and core graphs in DestBench. The controlled graph-memory experiments use the six-app core cohort shown here. Graph columns describe the Auto-BFS graphs (one record per stored screen state; directed hypernode edges); Covered counts tasks whose strict target is in the graph (human-audited).

Backbone	DestBench	DroidTask-Nav	SPA-Bench-Nav
	SR (%)	SR (%)	SR (%)
UI-TARS-1.5-7B	52.4 $\rightarrow$ 58.3	63.3 $\rightarrow$ 71.3	66.7 $\rightarrow$ 76.7
$p$	0.383	0.073	0.508
Qwen-VL-Max	59.5 $\rightarrow$ 71.4	66.0 $\rightarrow$ 70.7 §	76.7 $\rightarrow$ 93.3
$p$	0.076	0.265	0.125
Avg. gain	+8.9	+6.4	+13.3

Table 3: Cross-backbone, cross-benchmark navigation. Cells report no-memory

\rightarrow

+TAG-Nav in success rate (SR). DroidTask and SPA-Bench are converted to page-reaching tasks; only within-column deltas are comparable. All cells use human-annotated strict success.

p

: exact McNemar test; 95% confidence intervals (CIs) are in Appendix D.2 . § The no-memory arm resized screenshots to a 1,280-pixel longest side; the +TAG-Nav arm used full resolution.

UI-TARS-1.5-7B
Graph	Success	Gain (pp)	95% CI (pp)	$p$
No memory	44/84	–	–	–
Random	54/84	+11.9	[0.0, 23.8]	0.087
Auto-BFS	49/84	+6.0	[ $-4.8$ , 16.7]	0.383
Manual	59/84	+17.9	[8.3, 27.4]	0.0007
Qwen-VL-Max

Table 4: Paired graph-condition comparisons on DestBench. Success is the human-judged destination match count. Gains and 95% CIs are in percentage points (pp) relative to no memory for the same backbone;

p

: exact McNemar test (Appendix D.2 ). Some random- and manual-arm cells used the same app’s memory from a different graph condition (Appendix D.3 ); without those cells, every gain remains positive.

Panel of Figure 3 — Figure 3: Per-app navigation success rate with and without TAG-Nav. Gains are largest when navigation is the bottleneck (Clock, Amazon, Google Maps) and smaller when the baseline is already strong or execution dominates (Settings, Calendar).

	No memory		+ TAG-Nav
App	UI-TARS- 1.5-7B	Qwen-VL- Max	UI-TARS- 1.5-7B	Qwen-VL- Max
DroidTask-Nav (12 apps, 150 tasks)
AppLauncher	2/5	4/5	5/5	2/5
Calendar	11/17	9/17	12/17	12/17
Camera	5/15	5/15	4/15	5/15
Clock	7/12	9/12	11/12	11/12

Table 5: DroidTask-Nav and SPA-Bench-Nav per-app drilldowns. Tasks converted from task-completion to navigation-only goals. Human-annotated strict destination success for both benchmarks.

Condition	Targets	Routes	SR (%)
(a) No memory	–	–	59.5
(b) Random exploration	auto	noisy	64.3
(c) TAG-Nav (Auto-BFS)	auto	auto	71.4
(d) Manual targets + auto routes	manual	auto	70.2
(e) Auto targets + manual routes	auto	manual	79.8
(f) Manual exploration	manual	manual	66.7

Table 6: Graph-quality controlled decomposition on DestBench (Qwen-VL-Max). Human-annotated strict success on the 84-task core. Row (d) ran at full input resolution on a separate host. Rows (d) and (e) replace one memory field at a time with manual ground truth. Rows (b) and (f) include app cells that used the same app’s memory from a different graph condition (Appendix D.3 ). The UI-TARS counterpart is in Appendix D.4 .

Prior memory-format adaptations
System	Success	SR (%)
PG-Agent †	36/84	42.9
GUI-Explorer	47/84	56.0
Backbone agents without / with TAG-Nav
AgentCPM-GUI	28/84	33.3
+ TAG-Nav	33/84	39.3 (+6.0)

Table 7: Prior memory formats and wrapped backbones on DestBench. TAG-Nav adds one-time unsupervised exploration and one retrieval call per task. All rows use human-annotated strict success. † PG-Agent additionally requires human-labeled task demonstrations.

App	No memory	+ TAG-Nav
Airbnb	7/13	10/13
Chrome	4/13	6/13
eBay	11/16	13/16
Instagram	4/13	2/13
TikTok	2/13	4/13
Total	28/68 (41.2%)	35/68 (51.5%)

Table 8: Transfer to five additional apps. UI-TARS-1.5-7B, human-judged strict destination match; separate from the 84-task core.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

App	Category	Core 6
Amazon	Shopping	$\bullet$
Calendar	Productivity	$\bullet$
Clock	Utility	$\bullet$
Google Maps	Travel	$\bullet$
Settings	Utility	$\bullet$
YouTube	Entertainment	$\bullet$

Appendix

Table 9: Full DestBench app inventory. 20 Android apps spanning Shopping, Productivity, Utility, Travel, Entertainment, Social Media, Food & Drink, Communication, and Local Services categories. The 6-app core cohort is the subset used for the controlled graph-condition study (no-memory, random, automated Local-BFS, clean manual).

App	User instruction $q$	Target page (destination)	Stopping boundary
Amazon	“View past orders.”	“Your Orders” history page	Before opening any order detail
Calendar	“Change the default reminder time for events to 15 minutes.”	“Default notification time” settings row	Before tapping the time picker
TikTok	“Open the privacy settings for who can comment on my videos.”	“Who can comment” configuration page	Before selecting a permission
Chrome	“Clear browsing history from the last hour.”	“Clear browsing data” time-range dialog	Before tapping “Clear data”
Google Maps	“Switch the map style to satellite.”	Map-style selector with satellite option	Before confirming the style change
WhatsApp	“Turn off read receipts.”	“Read receipts” toggle row	Before flipping the toggle

Appendix

Table 10: Representative DestBench task examples. Each task specifies a natural-language instruction

q

, a pre-action destination screen the agent must reach, and a safe stopping boundary that excludes the irreversible final operation. Success is judged by visual equivalence between the agent’s final screenshot and the destination annotation; the stopping-boundary action is never executed in scoring.

Metric	Value
Total calibration tasks	530
Binary agreement	517 / 530 (97.5%)
False pass	10
False fail	3
Cohen’s $\kappa$ (binary)	0.95

Appendix

Table 11: GPT-4o judge calibration against human annotators. Calibration set: 530 (task, agent-final-screenshot) pairs spanning all 20 apps. Binary agreement represents matching judge and human results. False pass represents a reported success from the judge, and failure from the human annotator, while false fail represents a reported failure from the judge, and success from the human annotator. Binary success label uses scores 4–5 = success.

Setting	UI-TARS-1.5-7B	Qwen-VL-Max
Image resolution	native (1080p portrait)	native
Max input tokens	8192	API-controlled
Max output tokens	512	API-controlled
Temperature	0.0	0.0
Top- $p$	1.0	1.0
Action space	mobile-ops	mobile-ops

Appendix

Table 12: Backbone configurations. Same prompting and decoding hyperparameters across both backbones; only the model weights and tokenizer differ. mobile-ops is the shared action vocabulary ( click , type , scroll , back , home , wait , finished ).

	No memory		+ TAG-Nav
App	UI-TARS-1.5-7B	Qwen-VL-Max	UI-TARS-1.5-7B	Qwen-VL-Max
Amazon	9/17	8/17	10/17	11/17
Calendar	5/10	7/10	4/10	7/10
Clock	1/9	4/9	3/9	7/9
Google Maps	12/24	12/24	15/24	17/24
Settings	8/9	7/9	7/9	7/9

Appendix

Table 13: DestBench per-app drilldown (6 apps, 84 tasks). Human-annotated strict SR.

App	Graph condition	Success	No memory	$\Delta$ pp	95% CI pp	Exact $p$
Amazon	Random	11/17	9/17	+11.8	[+0.0, +29.4]	0.500
Calendar	Random	7/10	5/10	+20.0	[-30.0, +60.0]	0.688
Clock	Random	4/9	1/9	+33.3	[+0.0, +66.7]	0.250
Google Maps	Random	16/24	12/24	+16.7	[-8.3, +41.7]	0.344
Settings	Random	7/9	8/9	-11.1	[-33.3, +0.0]	1.000
YouTube	Random	9/15	9/15	+0.0	[-33.3, +33.3]	1.000

Appendix

Table 14: UI-TARS-1.5-7B per-app comparisons against no memory on DestBench (human strict labels; intervals and tests as in Appendix D.2 ).

App	Graph condition	Success	No memory	$\Delta$ pp	95% CI pp	Exact $p$
Amazon	Random	9/17	8/17	+5.9	[-17.6, +29.4]	1.000
Calendar	Random	8/10	7/10	+10.0	[-20.0, +40.0]	1.000
Clock	Random	7/9	4/9	+33.3	[+0.0, +66.7]	0.250
Google Maps	Random	12/24	12/24	+0.0	[-25.0, +25.0]	1.000
Settings	Random	6/9	7/9	-11.1	[-44.4, +22.2]	1.000
YouTube	Random	12/15	12/15	+0.0	[-26.7, +26.7]	1.000

Appendix

Table 15: Qwen-VL-Max per-app comparisons against no memory on DestBench (human strict labels; intervals and tests as in Appendix D.2 ).

Benchmark	Backbone	Success	No memory	$\Delta$ pp	95% CI pp	Exact $p$
DroidTask-Nav	UI-TARS-1.5-7B	107/150	95/150	+8.0	[+0.0, +16.0]	0.073
DroidTask-Nav	Qwen-VL-Max	106/150	99/150	+4.7	[-2.0, +12.0]	0.265
SPA-Bench-Nav	UI-TARS-1.5-7B	23/30	20/30	+10.0	[-10.0, +30.0]	0.508
SPA-Bench-Nav	Qwen-VL-Max	28/30	23/30	+16.7	[+0.0, +33.3]	0.125

Appendix

Table 16: Converted-benchmark comparisons against no memory (human strict labels; intervals and tests as in Appendix D.2 ).

Arm (excluded apps: memory received)	$n$	No mem.	Arm	$\Delta$ pp [95% CI]	$p$
UI-TARS-1.5-7B random (YouTube, Settings: Auto-BFS)	60	27	38	+18.3 [5.0, 31.7]	0.027
UI-TARS-1.5-7B manual (Clock: random-graph targets)	75	43	56	+17.3 [8.0, 28.0]	0.002
Qwen-VL-Max random (Settings: Auto-BFS)	75	43	48	+6.7 [ $-6.7$ , 20.0]	0.424
Qwen-VL-Max manual (Clock: random-graph targets)	75	46	50	+5.3 [ $-8.0$ , 18.7]	0.557

Appendix

Table 17: Graph conditions without the affected apps. Each row names the excluded apps and the memory they received. Human strict success; intervals and tests as in Appendix D.2 .

App	No memory	Random	Auto-BFS	Manual
Amazon	9/17	11/17	10/17	12/17
Calendar	5/10	7/10	4/10	6/10
Clock	1/9	4/9	3/9	3/9
Google Maps	12/24	16/24	15/24	20/24
Settings	8/9	7/9	7/9	8/9
YouTube	9/15	9/15	10/15	10/15

Appendix

Table 18: Per-app graph-quality breakdown on DestBench using UI-TARS-1.5-7B. Cells are successes / attempts under the strict human-scoring rule; all cells are human-labeled (Appendix D.2 ).

Injected-route measure	$n$	Point-biserial $r$	$p$
Route length (waypoints)	313	$-0.16$	0.006
Transition-hint count	313	$-0.19$	0.001
Loop count	313	$-0.03$	0.652
Backtrack count	313	$+0.04$	0.467
Detour count	313	$+0.02$	0.783

Appendix

Table 19: Route-cleanliness associations. GPT-4o-judged runs of Section 5.3 . Route length and hint count correlate negatively with success; this observational analysis does not establish causality.

Core app	Walks	Forward actions
Maps	869	3,166
Amazon	804	2,440
YouTube	638	2,174
Clock	994	3,990
Settings	148	510
Calendar	209	655

Appendix

Table 20: Exploration effort per core app. Walks and forward actions recorded during graph construction (Appendix D.8 ).

Record condition	Instagram	eBay	Total
Transition hints	4/11	13/16	17/27
Full record	2/11	12/16	14/27
No memory	4/11	10/16	14/27
Route only	2/11	11/16	13/27
Goal only	2/11	10/16	12/27

Appendix

Table 21: Version-matched record-content ablation. Human-judged Instagram/eBay tasks at matched graph versions. The small sample is suggestive.

Condition	Success	$\Delta$	$p$
No memory	35/80	–	–
Goal-only record	39/80	+4	0.388
Hand-written app manual	41/80	+6	0.109
Full record	39/80	+4	0.541
Route-only record	42/80	+7	0.167
Transition-hints record	44/80	+9	0.108

Appendix

Table 22: Informed no-memory baseline. UI-TARS-1.5-7B, human-judged strict success on 80 core-app tasks. The app manual gives fixed app-level guidance without task-specific destinations or routes.

p

: exact two-sided McNemar against no memory.

System	Backbone	Protocol adaptation
GUI-Explorer	GPT-4o	Used their published interaction-triple KB, retrieval, and guideline-generation pipeline on our emulator/app versions; exploration was not rerun.
PG-Agent	Qwen2.5-VL-72B	Built a page graph from DestBench task episodes with their construction pipeline, retrieved page guidelines by screen embedding, and replaced the multi-agent planner with a single Qwen2.5-VL-72B navigator.

Appendix

Table 23: Evaluation protocol for prior systems on DestBench. Each row keeps the system’s memory abstraction but uses our tasks and human-annotated strict-SR judge.

Class	N	%	Addressed by
A: wrong retrieval	22	46	embeddings, coverage
B: near miss	15	31	target selection
C: execution failure	11	23	step budget, replanning

Appendix

Table 24: Failure taxonomy. Labeled open-loop DestBench failures.

Panel of Figure 4 — Figure 4: Class A Failure (Wrong retrieval) Task: “Visit the user’s saved cards” (Amazon). Memory: Shopping Cart $\rightarrow$ Lists Tab $\rightarrow$ Lists and Registries . The retrieval system incorrectly matched the task to the Lists node. The agent then followed the memory faithfully: (1) Started at Amazon home page, (2) Navigated to Shopping Cart page and tapped the Lists tab, (3) Arrived at the Lists and Registries page showing a Shopping List. The embedding confused “saved cards” from the task with “saved items/lists.”

Panel of Figure 5 — Figure 5: Class B Failure (Near miss) Task: “View the user’s contribution profile” (Google Maps). Memory: Google Maps Home $\rightarrow$ Contribute hub $\rightarrow$ Profile details . The agent followed the memory: (1) Started on the Maps home page, (2) Tapped the Contribute tab, (3) Arrived at the Contribute page showing the “View profile” link. It then declared success without clicking it. The retrieval selected the Contribute hub node, which is the parent node to the correct Profile details node.

Panel of Figure 6 — Figure 6: Class C Failure (Execution failure) Task: “Toggle Use device time zone” (Calendar). Memory: Calendar Day View $\rightarrow$ Side Navigation Menu $\rightarrow$ Settings Page (correct). The agent followed the memory: (1) Started on the Calendar day view, (5) Remained on the same Calendar view after 4 wasted steps, and (15) Finally reached the Settings page but exhausted the step budget ( $T{=}15$ ) before locating the specific toggle. The memory was correct but the agent could not efficiently navigate the multi-level settings hierarchy. Account identifiers in the final screenshot are redacted.

System	Stored memory	Retrieved unit	Coupling
AutoDroid / AppAgent	UI graph + element notes	Element hint / note	Own LLM
KG-RAG	UTG distilled into KG store	Intent–trajectory pair	Own agent loop
GUI-explorer	Interaction-triple store	Current-screen cue	Own MLLM
GUI-Xplore	Video transition graph	App-level prior	Own VLM
PG-Agent / GraphPilot	Page / app knowledge graph	Guideline or action rule	Planner + validator
TAG-Nav	Nav. graph + dest. records	Target page + compact route	Unmodified actor

Appendix

Table 25: Detailed positioning of TAG-Nav. Prior systems retrieve hints, trajectories, guidelines, or action rules and are coupled to their own actors; TAG-Nav retrieves a structured destination record for an unchanged stepwise actor.

App	Condition	Matched	Updated
Instagram	No memory	4/11	1/11
	Full record	2/11	2/11
	Transition hints	4/11	4/11
eBay	No memory	10/16	10/16
	Full record	12/16	9/16
	Transition hints	13/16	11/16

Appendix

Table 26: Limited stale-graph probe. Human-judged paired tasks using the original graph at matched and updated app versions. Instagram: 416.0.0.47.66 to 437.0.0.33.78; eBay: 6.242.0.2 to 6.251.0.1. Full-record memory matched no memory in aggregate at both versions, with differing per-app outcomes; this small study does not establish general cross-version robustness.

Graph-Based Agent Memory

Graph-based agent memory organizes an agent’s experiences, facts, and procedures as linked structures for persistent, evidence-aware retrieval and reuse.

See all 133 papers

UI-KOBE: Knowledge-Oriented Behavior Exploration for Lightweight Graph-Guided GUI Agents
May 28, 2026Yuxiang Chai, Han Xiao, Xinyu Fu +3Mobile GUI Automation GUI Agents
1CUHK MMLab · 2Huawei Research · 3Shenzhen Loop Area Institute +1
Towards Omni-dimensional GUI Agent Navigation with Masked Trajectory Prediction
Sep 22, 2026Yan Zhang, Pei Fu, Daiqing Wu +8GUI Agents Multi-Task Learning
Institute of Information Engineering, Chinese Academy of Sciences · MiLM Plus, Xiaomi Inc. · School of Cyber Security, University of Chinese Academy of Sciences +1
What Memory Do GUI Agents Really Need? From Passive Records to Active Task-Driving States
Jun 30, 2026Chen Liu, Ling Chen, Hanzhang Zhou +7RL for GUI Agents GUI Agents
University of Technology Sydney · Tongyi Lab, Alibaba Group · Adelaide University

May 28, 2026J/K move · Enter open · S save

UI-KOBE: Knowledge-Oriented Behavior Exploration for Lightweight Graph-Guided GUI Agents

Yuxiang Chai, Han Xiao, Xinyu Fu, Jinpeng Chen+2

1CUHK MMLab · 2Huawei Research · 3Shenzhen Loop Area Institute+1

Mobile GUI Automation GUI Agents Mobile GUI Agents Graph-Based Planning GUI Automation

Open paper AskPDF arXiv

Recent advances in mobile GUI agents have shown strong potential for automating mobile tasks, but most effective systems still depend on large vision-language models for screenshot understanding and long-horizon planning. Small GUI agents that can be deployed directly on mobile devices are more attractive for practical use, offering lower inference cost and better protection of sensitive on-device information. However, due to limited model capacity, such lightweight agents remain unreliable when planning and executing GUI tasks end-to-end from screenshots alone. We propose Knowledge-Oriented Behavior Exploration (UI-KOBE), a framework that improves lightweight mobile GUI agents with reusable app-specific graph knowledge. UI-KOBE first autonomously explores a mobile application and constructs an app knowledge graph, where nodes represent distinct UI states and edges represent executable transitions. At runtime, a lightweight GUI agent uses the graph as external guidance: given a user task and the current screenshot, it identifies the current graph node and selects among self-loop actions, neighboring transitions, task completion, or fallback free actions associated with that node. By supporting runtime decisions with app-specific graph guidance, UI-KOBE reduces the burden of end-to-end GUI planning and helps lightweight models perform mobile GUI tasks more effectively, offering a practical step toward efficient, interpretable, and privacy-conscious on-device GUI agents.

Abstract

Graph-Based Agent Memory

Explore similar work

UI-KOBE: Knowledge-Oriented Behavior Exploration for Lightweight Graph-Guided GUI Agents

Towards Omni-dimensional GUI Agent Navigation with Masked Trajectory Prediction

What Memory Do GUI Agents Really Need? From Passive Records to Active Task-Driving States