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∗ , and formats the selected record as destination memory for an unchanged GUI agent. The figure writes ri for the formal record rh,n with i=(h,n) and uses st only as schematic exploration-state notation; the formal online/evaluation trajectory uses screenshots xt .
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 → 58.3
63.3 → 71.3
66.7 → 76.7
p
0.383
0.073
0.508
Qwen-VL-Max
59.5 → 71.4
66.0 → 70.7 §
76.7 → 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 → +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.
Graph
Success
Gain (pp)
95% CI (pp)
p
UI-TARS-1.5-7B
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.
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 .
System
Success
SR (%)
Prior memory-format adaptations
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
∙
Calendar
Productivity
∙
Clock
Utility
∙
Google Maps
Travel
∙
Settings
Utility
∙
YouTube
Entertainment
∙
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 κ (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 ).
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
Δ
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.
Figure 4: Class A Failure (Wrong retrieval) Task: “Visit the user’s saved cards” (Amazon). Memory: Shopping Cart → Lists Tab → 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.”
Figure 5: Class B Failure (Near miss) Task: “View the user’s contribution profile” (Google Maps). Memory: Google Maps Home → Contribute hub → 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.
Figure 6: Class C Failure (Execution failure) Task: “Toggle Use device time zone” (Calendar). Memory: Calendar Day View → Side Navigation Menu → 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 organizes an agent’s experiences, facts, and procedures as linked structures for persistent, evidence-aware retrieval and reuse.
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.
Yuxiang Chai, Han Xiao, Xinyu Fu +3
1CUHK MMLab · 2Huawei Research · 3Shenzhen Loop Area Institute +1
Graphical User Interface (GUI) Agents autonomously interact with software to fulfill user requests, where GUI navigation stands out as the most critical and challenging capability. Mastering this capability demands a complex synergy of step-wise decision-making, state-action alignment, and long-horizon planning. While directly mixing these corresponding navigation tasks seems intuitive to simultaneously acquire these skills, such a direct combination is severely bottlenecked by inconsistent optimization objectives and profound data heterogeneity. To overcome these barriers, we propose the MaP (stands for ``Masked Trajectory Prediction''), a unified framework that seamlessly harmonizes divergent GUI navigation tasks. By modeling multi-turn GUI interactions as a trajectory and defining training objectives through component masking and prediction, MaP shifts the optimization from task-specific marginal distributions to a consistent objective. Furthermore, to handle the data heterogeneity across multiple navigation tasks, we design a role-aware adapter learning module that dynamically routes each token to a specialized representation space. Extensive experiments on five representative GUI navigation benchmarks demonstrate that MaP effectively mitigates gradient conflicts and significantly outperforms the direct mixture training, establishing a robust paradigm for multi-task GUI navigation.
Yan Zhang, Pei Fu, Daiqing Wu +8
Institute of Information Engineering, Chinese Academy of Sciences · MiLM Plus, Xiaomi Inc. · School of Cyber Security, University of Chinese Academy of Sciences +1
Mobile GUI agents increasingly face long-horizon tasks that require reading, updating, and reusing task-relevant data across pages and applications. Existing methods treat memory largely as passive storage, where past observations are accumulated and retrieved when needed. Yet retrieving a value does not reveal its current role in the workflow. The agent must still infer from accumulated records whether the value should be used now, has already been used, or must wait for a later dependency. This implicit reconstruction becomes unreliable in long trajectories with repeated values, distractors, and outdated states, causing repeated or missed operations. To address this, we propose Active Task Driving Memory (ATMem), which shifts GUI-agent memory from passive storage to an actively maintained execution state. ATMem maintains task-relevant information as a continually updated execution state that links each value to its role and current status, enabling action selection based on the current workflow state. While supervised fine-tuning enables the agent to construct ATMem, it does not teach when ATMem is beneficial. We therefore introduce STR-GRPO, an online reinforcement learning method that encourages selective use of ATMem based on its contribution to task completion. STR-GRPO contrasts memory-on and memory-off rollouts to estimate when memory use improves execution, while memory-cost-aware reward discourages costly memory usage that does not improve execution. To evaluate whether agents can complete all in-scope work while avoiding out-of-scope actions, we build a challenging mobile benchmark. From a list of near identical entries, agents must act on every entry that satisfies the instruction and reject entries that violate its constraints. We further introduce App-Level Progress and Scope-Aware F1 to measure these two dimensions separately.
Chen Liu, Ling Chen, Hanzhang Zhou +7
University of Technology Sydney · Tongyi Lab, Alibaba Group · Adelaide University