并非所有图都是地图:面向移动 GUI 导航的任务无关探索框架
摘要
本文提出 TAG-Nav 框架,通过任务无关的图导航记忆为移动 GUI 代理提供可复用的导航知识,并引入 DestBench 导航评测协议,实验表明图记忆可显著提升 UI-TARS-1.5-7B 和 Qwen-VL-Max 的导航成功率。
arXiv:2610.22672v1 Announce Type: new
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.
查看缓存全文
缓存时间: 2026/10/19 07:03
# Not All Graphs Are Maps: A Task-Agnostic Exploration Framework for Mobile GUI Navigation
Source: [https://arxiv.org/html/2610.22672](https://arxiv.org/html/2610.22672)
###### 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 DestBench111[https://tag\-nav\-authors\.github\.io/tag\_nav/](https://tag-nav-authors.github.io/tag_nav/)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\.
## 1Introduction
Modern multimodal GUI agents perceive screens and execute visible actions well, but they lack a persistent map of the apps they operate\([Zhang et al\., 2025a](https://arxiv.org/html/2610.22672#bib.bib34);[Wen et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib29);[Qin et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib18)\)\. When asked to reach a deep setting, account\-management page, privacy control, or app\-specific tool, the agent must re\-infer where the function lives and how to navigate there from the current screen on every task\. Many user requests share the prefix of arriving at a destination before any task\-specific \(and often sensitive or irreversible\) final action: reaching an account\-privacy screen is reusable navigation, while toggling the control itself is task\-specific execution\.
We study mobile GUI*destination navigation*as a problem distinct from full task completion, focused on whether the agent reaches the correct pre\-action destination screen\.
The standard response is to explore the app offline and retrieve from the resulting graph\([Wen et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib29);[Guan et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib8);[Xie et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib30);[Chen et al\., 2025b](https://arxiv.org/html/2610.22672#bib.bib4)\), but exploration does not automatically yield a useful map: a large random graph can have low target coverage and noisy routes, while a small clean graph can be highly navigable\. Two graph\-construction properties decide whether explored memory actually helps:*target coverage*of the destinations users request, and*route cleanliness*from the app root to those destinations\. We argue that graphs satisfying both, built by task\-agnostic breadth\-oriented exploration and post\-processed into destination\-anchored deduplicated routes, are the design that turns offline exploration into navigation memory that wraps any visual GUI actor\.
We instantiate this design in TAG\-Nav, aTask\-AgnosticGraphNavigation framework that wraps existing visual GUI agents with destination memory without retraining\. TAG\-Nav explores apps with task\-agnostic local breadth\-first search \(Local\-BFS\) and post\-processes the result into compact destination records \(target page summary, intents, waypoint route, transition hints\); at inference time the matching record is injected as plain text into an unmodified backbone such as UI\-TARS\([Qin et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib18)\)\. The retrieved unit is a destination plus its route, not a per\-task trajectory replay, so TAG\-Nav can be evaluated under different graph\-construction conditions while holding the actor and task set fixed\.
To evaluate this design on real apps, we introduce DestBench, a navigation\-only protocol on real Android apps that judges whether the agent reaches the correct pre\-action destination screen, with graph\-aware target coverage and route cleanliness diagnostics\. End\-to\-end task benchmarks would otherwise conflate memory quality with downstream execution, blurring the properties we want to measure\. On 84 DestBench tasks spanning six apps, TAG\-Nav achieves higher observed navigation success than a no\-memory baseline across two GUI backbones \(Table[3](https://arxiv.org/html/2610.22672#S5.T3)\)\. Controlled comparisons against random\-exploration and clean manual\-graph conditions examine the roles of target coverage and route cleanliness \(Table[6](https://arxiv.org/html/2610.22672#S5.T6)\)\.
Our contributions are:
- •TAG\-Nav, a task\-agnostic destination\-memory module that wraps an unmodified visual GUI actor: offline exploration becomes compact destination records \(target page, waypoint route, transition hints\) injected as plain text at inference\.
- •DestBench, a navigation\-only page\-reaching protocol on real Android apps with graph\-aware diagnostics for target coverage and route cleanliness\.
## 2Related Work
#### Mobile GUI Agents and Visual Grounding\.
Mobile GUI agents translate natural language instructions and visual observations into interface actions\. Smartphone agents and Android automation systems showed that language models can operate mobile apps through screenshots, UI trees, and action histories\([Zhang et al\., 2025a](https://arxiv.org/html/2610.22672#bib.bib34);[Wen et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib29);[Wang et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib27);[Wang et al\., 2025b](https://arxiv.org/html/2610.22672#bib.bib28)\)\. More recent general\-purpose GUI backbones such as CogAgent and UI\-TARS improve perception, grounding, and multi\-step action generation across GUI tasks\([Hong et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib9);[Qin et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib18);[Wang et al\., 2025a](https://arxiv.org/html/2610.22672#bib.bib26)\)\. Parallel work on visual grounding and screen parsing, including SeeClick, UGround, and OmniParser, shows that locating the correct on\-screen element is itself a central bottleneck for visual GUI agents\([Cheng et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib5);[Gou et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib7);[Lu et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib17)\)\. TAG\-Nav is complementary to these efforts: it does not replace the actor or the grounding model, but supplies app\-specific destination memory that tells an existing actor where to go\. Table[1](https://arxiv.org/html/2610.22672#S2.T1)summarizes how TAG\-Nav differs from prior graph\- and retrieval\-based systems on two axes that anchor the rest of this section:*what is retrieved online*and*whether the memory wraps an unmodified actor*; a per\-system breakdown \(stored memory, retrieved unit, coupling\) is given in Appendix[G](https://arxiv.org/html/2610.22672#A7)\.
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](https://arxiv.org/html/2610.22672#A7)\.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, selectsr∗r^\{\\ast\}, and formats the selected record as destination memory for an unchanged GUI agent\. The figure writesrir\_\{i\}for the formal recordrh,nr\_\{h,n\}withi=\(h,n\)i=\(h,n\)and usessts\_\{t\}only as schematic exploration\-state notation; the formal online/evaluation trajectory uses screenshotsxtx\_\{t\}\.
#### Mobile\-Agent Benchmarks\.
Mobile\-agent benchmarks have expanded from UI\-control datasets to interactive task\-completion environments\. Android in the Wild and AndroidControl study large\-scale supervised UI\-control data with high\- and low\-level instructions\([Rawles et al\., 2023](https://arxiv.org/html/2610.22672#bib.bib23);[Li et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib13)\), while AndroidLab provides a reproducible Android training and evaluation framework\([Xu et al\., 2025b](https://arxiv.org/html/2610.22672#bib.bib32)\)\. AndroidWorld, SPA\-Bench, Mobile\-Bench, and MobileWorld evaluate increasingly realistic mobile\-agent task completion, including dynamic environments, multi\-step planning, API/tool use, and user interaction\([Rawles et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib22);[Chen et al\., 2025a](https://arxiv.org/html/2610.22672#bib.bib3);[Deng et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib6);[Kong et al\., 2026](https://arxiv.org/html/2610.22672#bib.bib12)\)\. Other recent benchmarks stress cross\-app navigation, multiple valid paths, noisy apps, and online procedural judging\([Lu et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib16);[Xu et al\., 2025a](https://arxiv.org/html/2610.22672#bib.bib31);[Im et al\., 2026](https://arxiv.org/html/2610.22672#bib.bib11);[Chai et al\., 2026](https://arxiv.org/html/2610.22672#bib.bib2)\)\. These benchmarks are valuable, but their success criteria usually mix navigation with downstream execution: typing user\-specific content, changing app state, sending information, selecting items, or satisfying procedural completion checks\. Because they sample task completion across many apps, they also provide limited visibility into how well app\-specific memory covers the functional regions of a single target app\. DestBench instead isolates page\-reaching navigation by asking whether the agent reaches the pre\-action destination screen for a given task\. This makes it possible to evaluate graph\-derived navigation memory through target coverage, target retrieval, path existence, route cleanliness, and strict page matching rather than only final task success\.
#### App Exploration and App\-Specific Memory\.
Several systems build app\-specific knowledge before task execution\. Earlier UI\-guided testing tools such as DroidBot built app state\-transition models through device interaction, providing an important predecessor to app exploration for automation\([Li et al\., 2017](https://arxiv.org/html/2610.22672#bib.bib15)\)\. AutoDroid explores Android apps, builds a UI transition graph, and turns view\-hierarchy/accessibility states into simplified HTML prompts and simulated\-task app memory\([Wen et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib29)\)\. Its memory is structured around explored UI trees, elements, and actions rather than visual screen perception, making it a strong early example of exploration\-based app memory\. AppAgent and AppAgent\-v2 use autonomous or manual exploration to build app documents for later task execution\([Zhang et al\., 2025a](https://arxiv.org/html/2610.22672#bib.bib34);[Li et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib14)\)\. Their memory is element\- and document\-centered: per\-element notes consulted on the current screen, not destination memory keyed to a target page\. GUI\-Xplore uses pre\-recorded exploration videos and converts them into GUI transition graphs\([Sun et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib25)\)\. GUI\-Xplore is primarily evaluated as an offline app\-understanding setup over those videos, whereas TAG\-Nav studies graph memory under live device interaction with a stepwise actor\. GUI\-explorer autonomously explores apps and mines transition\-aware knowledge for dynamic guidance\([Xie et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib30)\)\. Across this family, exploration\-derived memory is largely treated as an assumed benefit; what varies between systems is the exploration policy and the memory format, not a controlled comparison of when the explored graph yields useful navigation memory\. Our narrower question is when exploration becomes reusable navigation memory: whether the graph contains destination pages, whether retrieval selects the right target, and whether the recovered route is clean enough to guide a future page\-reaching task\.
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\.
#### Graph and Retrieval\-Augmented GUI Agents\.
Graph and retrieval memories are increasingly common in GUI\-agent systems\. KG\-RAG transforms UI transition graphs into a vector database of intent\-trajectory pairs and retrieves relevant trajectories at inference time\([Guan et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib8)\)\. PG\-Agent reconstructs page graphs from episodes and retrieves page\-graph guidelines for multi\-agent planning\([Chen et al\., 2025b](https://arxiv.org/html/2610.22672#bib.bib4)\)\. GraphPilot constructs app\-specific knowledge graphs and uses them for low\-latency action\-sequence generation\([Yu et al\., 2026](https://arxiv.org/html/2610.22672#bib.bib33)\)\. HyMEM studies graph\-structured self\-evolving memory for GUI agents\([Zhu et al\., 2026](https://arxiv.org/html/2610.22672#bib.bib38)\), while AndroTMem focuses on anchored within\-task memory in long\-horizon Android tasks\([Shi et al\., 2026](https://arxiv.org/html/2610.22672#bib.bib24)\)\. The closest systems differ in what memory they retrieve and how it is consumed: KG\-RAG retrieves intent\-trajectory pairs for action decisions, GUI\-explorer retrieves transition\-aware current\-screen knowledge for dynamic guidance, PG\-Agent retrieves screen\-conditioned page\-graph guidelines for multi\-agent planning, and GraphPilot uses a knowledge graph to plan near one\-shot action sequences with a validator\. TAG\-Nav differs along two axes that prior work does not exercise together \(see Fig\.[2](https://arxiv.org/html/2610.22672#S2.F2)\): the online unit is a destination page with a compact waypoint route consumed by an unmodified stepwise visual actor, and graph quality is measured by comparing no\-memory, random, automated\-BFS, and clean\-graph conditions under the same actor and tasks\.
## 3TAG\-Nav
### 3\.1Overview
TAG\-Nav is a navigation\-memory module for mobile GUI agents that separates app\-specific discovery from online task execution\. Offline exploration builds an app graph over hypernode\-clustered observations, then post\-processing turns each indexed graph state into a compact destination record describing what the page is for and how it can be reached\. At inference time, TAG\-Nav retrieves the destination record for the user instruction, formats it as a plain\-text destination\-memory block, and injects it into an existing GUI\-agent backbone without training a new actor or replacing the actor’s visual grounding module\. Figure[1](https://arxiv.org/html/2610.22672#S2.F1)summarizes the full pipeline: the offline input is an app/device configuration and the offline output is an app graph plus target\-indexed records; the online input is a natural\-language instruction and the online output is the executed trajectory together with the evaluator’s terminal status\.
### 3\.2Offline App Exploration
TAG\-Nav represents an app as a directed graphG=\(ℋ,E\)G=\(\\mathcal\{H\},E\)\. A hypernodeh∈ℋh\\in\\mathcal\{H\}groups observed UI states that the matcher judges to be the same screen or screen family using visual or layout evidence\. Each member observation stores its screenshot, parsed UI or layout evidence when available, and metadata collected during exploration\. An edgee=\(hi,a,hj\)e=\(h\_\{i\},a,h\_\{j\}\)records an executable transition from source hypernodehih\_\{i\}to destination hypernodehjh\_\{j\}, whereaaincludes the action type, an action description, and available element evidence\. The graph is therefore a state abstraction over repeated screenshots rather than a literal log of every frame\.
Auto\-BFS is our automated graph\-construction condition, which builds the app graph through repeated walks from the app’s initial screen\. It combines walks using the local breadth\-first search exploration policy \(Local\-BFS\) with random\-action walks\. Local\-BFS walks probe unexplored actions and verify return to the current screen before probing another action, skipping actions already explored on matched sibling nodes within the same hypernode\. Observed states are matched to existing hypernodes or assigned to new ones, and transitions are recorded as edges\. We treat Auto\-BFS as an autonomous graph\-construction condition rather than a novel graph\-search algorithm\. Appendix[B\.2](https://arxiv.org/html/2610.22672#A2.SS2)gives the walk schedule and measured exploration counts, and Appendix[B\.1](https://arxiv.org/html/2610.22672#A2.SS1)describes how observed states are matched to hypernodes\.
Algorithm 1Offline Graph Memory Construction1:app
AA, device
DD, exploration configuration
π\\pi, maximum walks
NN, VLM
MmemM\_\{\\mathrm\{mem\}\}, embedder
ϕ\\phi
2:graph
G=\(ℋ,E\)G=\(\\mathcal\{H\},E\), memory index
RR
3:
s0←𝖮𝖻𝗌𝖾𝗋𝗏𝖾\(𝖱𝖾𝗌𝖾𝗍\(A,D\)\)s\_\{0\}\\leftarrow\\mathsf\{Observe\}\(\\mathsf\{Reset\}\(A,D\)\)
4:
h0←𝖧𝗒𝗉𝖾𝗋𝗇𝗈𝖽𝖾\(s0\)h\_\{0\}\\leftarrow\\mathsf\{Hypernode\}\(s\_\{0\}\)
5:
ℋ←\{h0\}\\mathcal\{H\}\\leftarrow\\\{h\_\{0\}\\\};
E←∅E\\leftarrow\\emptyset;
R←∅R\\leftarrow\\emptyset
6:
G←\(ℋ,E\)G\\leftarrow\(\\mathcal\{H\},E\)
7:for
w=1,…,Nw=1,\\ldots,Ndo
8:
s←𝖮𝖻𝗌𝖾𝗋𝗏𝖾\(𝖱𝖾𝗌𝖾𝗍\(A,D\)\)s\\leftarrow\\mathsf\{Observe\}\(\\mathsf\{Reset\}\(A,D\)\)
9:
h←𝖬𝖺𝗍𝖼𝗁𝖮𝗋𝖠𝖽𝖽\(s,G\)h\\leftarrow\\mathsf\{MatchOrAdd\}\(s,G\)
10:
m←𝖲𝖺𝗆𝗉𝗅𝖾𝖶𝖺𝗅𝗄𝖬𝗈𝖽𝖾\(π\)m\\leftarrow\\mathsf\{SampleWalkMode\}\(\\pi\)
11:
Dw←𝖣𝖾𝗉𝗍𝗁𝖫𝗂𝗆𝗂𝗍\(π,w\)D\_\{w\}\\leftarrow\\mathsf\{DepthLimit\}\(\\pi,w\);
d←0d\\leftarrow 0;
k←0k\\leftarrow 0
12:while
d<Dwd<D\_\{w\}do
13:
\(a,b\)←𝖲𝖾𝗅𝖾𝖼𝗍𝖠𝖼𝗍𝗂𝗈𝗇\(s,h,G,m,d,k,π\)\(a,b\)\\leftarrow\\mathsf\{SelectAction\}\(s,h,G,m,d,k,\\pi\)
14:
\(s′,ℓ′\)←𝖤𝗑𝖾𝖼𝗎𝗍𝖾𝖮𝖻𝗌𝖾𝗋𝗏𝖾\(D,a\)\(s^\{\\prime\},\\ell^\{\\prime\}\)\\leftarrow\\mathsf\{ExecuteObserve\}\(D,a\)
15:
h′←𝖬𝖺𝗍𝖼𝗁𝖧𝗒𝗉𝖾𝗋𝗇𝗈𝖽𝖾\(s′,ℓ′,G\)h^\{\\prime\}\\leftarrow\\mathsf\{MatchHypernode\}\(s^\{\\prime\},\\ell^\{\\prime\},G\)
16:if
h′=∅h^\{\\prime\}=\\emptysetthen
17:
h′←𝖧𝗒𝗉𝖾𝗋𝗇𝗈𝖽𝖾\(s′,ℓ′\)h^\{\\prime\}\\leftarrow\\mathsf\{Hypernode\}\(s^\{\\prime\},\\ell^\{\\prime\}\)
18:
ℋ←ℋ∪\{h′\}\\mathcal\{H\}\\leftarrow\\mathcal\{H\}\\cup\\\{h^\{\\prime\}\\\}
19:else
20:
𝖠𝖽𝖽𝖮𝖻𝗌𝖾𝗋𝗏𝖺𝗍𝗂𝗈𝗇\(h′,s′,ℓ′\)\\mathsf\{AddObservation\}\(h^\{\\prime\},s^\{\\prime\},\\ell^\{\\prime\}\)
21:endif
22:
E←E∪\{\(h,a,h′\)\}E\\leftarrow E\\cup\\\{\(h,a,h^\{\\prime\}\)\\\}
23:
𝖬𝖺𝗋𝗄𝖤𝗑𝗉𝗅𝗈𝗋𝖾𝖽\(s,h,a,G\)\\mathsf\{MarkExplored\}\(s,h,a,G\)
24:
𝖢𝗁𝖾𝖼𝗄𝗉𝗈𝗂𝗇𝗍\(G,s′,a\)\\mathsf\{Checkpoint\}\(G,s^\{\\prime\},a\)
25:if
bbthen
26:
\(sback,v\)←𝖴𝗇𝖽𝗈𝖠𝗇𝖽𝖢𝗁𝖾𝖼𝗄\(D,a,s,h,π\)\(s\_\{\\mathrm\{back\}\},v\)\\leftarrow\\mathsf\{UndoAndCheck\}\(D,a,s,h,\\pi\)
27:if
¬v\\neg vthen
28:break
29:endif
30:
s←sbacks\\leftarrow s\_\{\\mathrm\{back\}\}
31:else
32:
\(s,h\)←\(s′,h′\)\(s,h\)\\leftarrow\(s^\{\\prime\},h^\{\\prime\}\)
33:endif
34:Update walk counters
\(d,k\)\(d,k\)according to
π\\pi
35:endwhile
36:endfor
37:for all
h∈ℋh\\in\\mathcal\{H\},
n∈𝖬𝖾𝗆𝖻𝖾𝗋𝗌\(h\)n\\in\\mathsf\{Members\}\(h\)do
38:
Ph,n←𝖱𝗈𝗈𝗍𝖯𝖺𝗍𝗁𝗌\(G,h,n\)P\_\{h,n\}\\leftarrow\\mathsf\{RootPaths\}\(G,h,n\)
39:
\(dh,n,Ih,n,Wh,n,Hh,n\)←Mmem\(h,n,Ph,n\)\(d\_\{h,n\},I\_\{h,n\},W\_\{h,n\},H\_\{h,n\}\)\\leftarrow M\_\{\\mathrm\{mem\}\}\(h,n,P\_\{h,n\}\)
40:
zh,nd←ϕ\(dh,n\)z^\{d\}\_\{h,n\}\\leftarrow\\phi\(d\_\{h,n\}\);
zh,nI←ϕ\(Ih,n\)z^\{I\}\_\{h,n\}\\leftarrow\\phi\(I\_\{h,n\}\)
41:
R\[\(h,n\)\]←R\[\(h,n\)\]\\leftarrow
42:
\(h,n,dh,n,Ih,n,Wh,n,Hh,n,zh,nd,zh,nI\)\(h,n,d\_\{h,n\},I\_\{h,n\},W\_\{h,n\},H\_\{h,n\},z^\{d\}\_\{h,n\},z^\{I\}\_\{h,n\}\)
43:endfor
44:return
G,RG,R
In Algorithm[1](https://arxiv.org/html/2610.22672#alg1),π\\pispecifies the exploration configuration described in Appendix[B\.2](https://arxiv.org/html/2610.22672#A2.SS2), including the probability of local expansion, depth schedule, maximum number of successful undo\-and\-check cycles, and rules for selecting actions\. The countersddandkktrack walk depth and successful undo\-and\-check cycles, respectively\.𝖲𝖾𝗅𝖾𝖼𝗍𝖠𝖼𝗍𝗂𝗈𝗇\\mathsf\{SelectAction\}returns an action and a flagbbindicating whether it is a local probe\. Local\-BFS skips actions already explored on the current screen or matching actions explored on sibling screens within the same hypernode\.𝖴𝗇𝖽𝗈𝖠𝗇𝖽𝖢𝗁𝖾𝖼𝗄\\mathsf\{UndoAndCheck\}returns the observed landing state and a flagvvindicating whether return to the source screen was verified after any configured recovery attempts\.𝖬𝖺𝗍𝖼𝗁𝖮𝗋𝖠𝖽𝖽\\mathsf\{MatchOrAdd\}matches the reset observation or adds it toGG; graph updates modifyℋ\\mathcal\{H\}andEEin place\.
### 3\.3Graph Construction and Post\-Processing
Raw exploration graphs are not used directly as prompts: mobile apps contain dynamic content, ads, pop\-ups, scroll variants, and alternate paths that would produce noisy targets and brittle action scripts if copied verbatim\. TAG\-Nav therefore post\-processes the graph into compact retrieval records that describe what each destination screen is for and how it can be reached\.
For each indexed graph state, a vision\-language model generates a concise visual page summary and a set of user intents directly satisfied by the current screen\. The prompt emphasizes the active interaction layer of the final screenshot, so if a modal, drawer, menu, or permission dialog is in the foreground, the metadata describes that foreground layer rather than the dimmed background\.
TAG\-Nav also constructs the route field of each destination\-memory record by extracting root\-to\-state paths from the graph, annotating the screenshots along each path with action evidence, and asking a vision\-language model to distill the route into semantic waypoints and transition hints\. The post\-processing prompt removes loops, retries, oscillations, and irrelevant detours, so the resulting memory is expressed as page or state labels and high\-level transitions, not fixed coordinates or event\-log replay\.
Each processed graph state\(h,n\)\(h,n\)becomes a memory recordrh,n=\(h,n,dh,n,Ih,n,Wh,n,Hh,n,zh,nd,zh,nI\)r\_\{h,n\}=\(h,n,d\_\{h,n\},I\_\{h,n\},W\_\{h,n\},H\_\{h,n\},z^\{d\}\_\{h,n\},z^\{I\}\_\{h,n\}\)with the summary, intent, waypoint, hint, and embedding fields defined in Algorithm[1](https://arxiv.org/html/2610.22672#alg1); we writei=\(h,n\)i=\(h,n\)andri=rh,nr\_\{i\}=r\_\{h,n\}for compact figure notation\. Figure[2](https://arxiv.org/html/2610.22672#S2.F2)contrasts the destination\-record unit with the per\-element hints, intent\-trajectory pairs, and page guidelines used by prior graph\-RAG GUI systems\([Wen et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib29);[Guan et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib8);[Xie et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib30);[Chen et al\., 2025b](https://arxiv.org/html/2610.22672#bib.bib4)\)\.
### 3\.4Target Retrieval and Memory Formatting
Given a user instructionqq, TAG\-Nav first retrieves candidate destination records\. The instruction is embedded and compared against both the visual\-summary embeddings and direct\-intent embeddings for all records\. Top matches from the two fields are combined so that a candidate may be retrieved because it looks like the requested page, because it directly supports the requested intent, or both\.
The candidate set is then passed to a compact target\-selection prompt\. The selector receives the user instruction, candidate screen summaries, and direct\-intent text, then chooses the graph state whose current screen best satisfies the instruction as the final destination\. The selector prefers loaded destinations over loading or transition screens, the destination page over foreground modals unless requested, routes page\-style queries to the visual summary and action\-style queries to the intents, rejects link or menu entries that merely point at the target, and prefers specific destinations for specific queries and general help pages for generic queries \(full prompts in Appendix[C](https://arxiv.org/html/2610.22672#A3)\)\. This target\-first retrieval step avoids a common graph\-memory failure mode in which a retrieved state is semantically close to the task but is not itself the destination page; unlike a direct retrieval of a past task trace, the destination is selected first and its memory is only then formatted for injection\.
TAG\-Nav then formats a destination\-memory block containing the original task, a final\-goal description, the relevant waypoint sequence, and transition hints\. The block is intentionally semantic and route\-oriented: it orients the backbone toward the correct app region while leaving grounding, action selection, and local recovery to the backbone, and it never prescribes fixed coordinates, replays exploration verbatim, or asks the actor to perform the irreversible final task action\.
### 3\.5Agent\-Agnostic Online Guidance
Algorithm[2](https://arxiv.org/html/2610.22672#alg2)formalizes the online actor loop: TAG\-Nav launches the app, captures the current screenshot, calls the GUI backbone with the user instruction plus the retrieved destination\-memory block, and executes the predicted action until the backbone emits a terminalfinishedaction or the step budget is reached\.
The memory interface itself is backbone\-independent: the destination\-memory block is plain text, and any GUI agent that consumes a task prompt and screen observation and emits mobile actions can be wrapped with the same retrieved memory without retraining\. The canonical backbone in our experiments is UI\-TARS\-1\.5\-7B; Sec\.[5](https://arxiv.org/html/2610.22672#S5)pairs TAG\-Nav memory with different GUI actors to test this agent\-agnostic property empirically\. Dynamic variants that refresh or edit memory during execution are treated as controlled ablations in Appendix[H\.7](https://arxiv.org/html/2610.22672#A8.SS7)\.
Algorithm 2Online Graph\-Memory Navigation1:instruction
qq, memory index
RR, embedder
ϕ\\phi, backbone
LL, device
DD, budget
TT
2:executed trajectory
τ\\tau, terminal status
yy
3:
Csum←𝖳𝗈𝗉𝖪summary\(ϕ\(q\),R\)C\_\{\\mathrm\{sum\}\}\\leftarrow\\mathsf\{TopK\}\_\{\\mathrm\{summary\}\}\(\\phi\(q\),R\)
4:
Cint←𝖳𝗈𝗉𝖪intent\(ϕ\(q\),R\)C\_\{\\mathrm\{int\}\}\\leftarrow\\mathsf\{TopK\}\_\{\\mathrm\{intent\}\}\(\\phi\(q\),R\)
5:
C←Csum∪CintC\\leftarrow C\_\{\\mathrm\{sum\}\}\\cup C\_\{\\mathrm\{int\}\}
6:
r∗←𝖲𝖾𝗅𝖾𝖼𝗍𝖣𝖾𝗌𝗍𝗂𝗇𝖺𝗍𝗂𝗈𝗇\(q,C\)r^\{\\ast\}\\leftarrow\\mathsf\{SelectDestination\}\(q,C\)
7:
m←𝖥𝗈𝗋𝗆𝖺𝗍𝖬𝖾𝗆𝗈𝗋𝗒\(q,r∗\)m\\leftarrow\\mathsf\{FormatMemory\}\(q,r^\{\\ast\}\)
8:
τ←∅\\tau\\leftarrow\\emptyset
9:for
t=1,…,Tt=1,\\ldots,Tdo
10:
xt←𝖲𝖼𝗋𝖾𝖾𝗇𝗌𝗁𝗈𝗍\(D\)x\_\{t\}\\leftarrow\\mathsf\{Screenshot\}\(D\)
11:
at←L\(q,xt,m\)a\_\{t\}\\leftarrow L\(q,x\_\{t\},m\)
12:
τ←𝖠𝗉𝗉𝖾𝗇𝖽\(τ,\(xt,at\)\)\\tau\\leftarrow\\mathsf\{Append\}\(\\tau,\(x\_\{t\},a\_\{t\}\)\)
13:if
at=Finisheda\_\{t\}=\\textsc\{Finished\}then
14:
y←Finishedy\\leftarrow\\textsc\{Finished\}
15:return
τ,y\\tau,y
16:endif
17:
𝖤𝗑𝖾𝖼𝗎𝗍𝖾\(D,at\)\\mathsf\{Execute\}\(D,a\_\{t\}\)
18:endfor
19:
y←StepBudgetReachedy\\leftarrow\\textsc\{StepBudgetReached\}
20:return
τ,y\\tau,y
## 4DestBench
End\-to\-end task benchmarks conflate navigation with grounding, manipulation, and finalization, so an aggregate success rate cannot attribute a failure to memory\.
### 4\.1Page\-Reaching Navigation
Each DestBench instance is a tuple\(A,q,s0,xtarget\)\(A,q,s\_\{0\},x\_\{\\mathrm\{target\}\}\)whereAAis the target app and version,qqis a natural\-language instruction,s0s\_\{0\}is a reset starting state, andxtargetx\_\{\\mathrm\{target\}\}is a ground\-truth screenshot of the pre\-action destination screen\. The agent emits a trajectoryτ=\(x0,a0,x1,a1,…,xT\)\\tau=\(x\_\{0\},a\_\{0\},x\_\{1\},a\_\{1\},\\ldots,x\_\{T\}\)that terminates when it issues aFinishedaction or hits the step budget\. Success is judged by visual equivalence betweenxTx\_\{T\}andxtargetx\_\{\\mathrm\{target\}\}rather than by completion of any downstream operation: a task like “set an alarm for 7am” is reduced to “reach the new\-alarm creation screen”; the time picker itself is out of scope\. This is a deliberate measurement choice rather than a simplification of mobile use: the post\-arrival action is where benchmarks introduce confounds \(form\-filling, sensitive state changes, tool or API use\) that have little to do with app\-specific navigation\. Accordingly, DestBench scores page reaching only; its gains should not be interpreted as gains in end\-to\-end task completion\.
### 4\.2Apps, Tasks, and Targets
DestBench contains tasks from 20 Android apps spanning Shopping, Productivity, Utility, Travel, Entertainment, Social Media, Food & Drink, Communication, and Local Services categories \(full inventory in Appendix[A\.1](https://arxiv.org/html/2610.22672#A1.SS1)\)\. The current controlled graph\-memory experiments use the 6\-app core cohort for which target annotations and graph conditions are available\. Tasks are derived from real user trajectories collected in our benchmark substrate, with each task annotated by the pre\-action destination screen from its original trajectory \(annotation protocol in Appendix[A\.3](https://arxiv.org/html/2610.22672#A1.SS3)\); Table[2](https://arxiv.org/html/2610.22672#S4.T2)summarizes per\-app task counts\.
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\)\.
### 4\.3Graph\-Aware Diagnostics
DestBench records per\-task structural metadata that attributes failures to specific causes rather than only reporting aggregate success:*target coverage*\(whether the graph contains a node visually equivalent toxtargetx\_\{\\mathrm\{target\}\}\),*retrieval correctness*\(whether top\-1 retrieval picks the correct target\),*path existence*froms0s\_\{0\}to the retrieved target,*path cleanliness*\(route length in waypoints, detours, loops, backtracks, restarts, and transition\-hint count\), and*judge match score*\(raw 1–5 rating\)\. A target is covered only when a record matches the pre\-action destination; a parent page or a screen one action too early or late is not covered\. These let us distinguish between error types, including situations when the graph missed the page, when retrieval picked the wrong target, and when the route itself was noisy\.
### 4\.4Strict Judge and Calibration
Primary navigation results use human judgments\. Strict success requires the reference destination, allowing cosmetic differences on the same functional page; near misses fail\. GPT\-4o\([Hurst et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib10)\)cross\-checks final and reference screenshots on a 1–5 scale \(4–5 indicate success\); on a 530\-pair calibration set it agrees with human judgments on 97\.5% of binary labels \(Appendix[A\.5](https://arxiv.org/html/2610.22672#A1.SS5)\)\.
## 5Experiments
### 5\.1Setup
#### Backbones and protocols\.
We wrap four visual GUI actors without fine\-tuning: UI\-TARS\-1\.5\-7B\([Qin et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib18), UI\-TARS;\)and Qwen\-VL\-Max\([Bai et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib1), Qwen;\)222Queried through the DashScope API model aliasqwen\-vl\-max\-latest\(April–May 2026\)\.as headline backbones, plus AgentCPM\-GUI\([Zhang et al\., 2025c](https://arxiv.org/html/2610.22672#bib.bib36)\)\(8B open\-weight MiniCPM\-V\-based\) and MAI\-UI\([Zhou et al\., 2025](https://arxiv.org/html/2610.22672#bib.bib37)\)as cross\-family checks \(Table[7](https://arxiv.org/html/2610.22672#S5.T7)\)\. Benchmarks used in our experiments are DestBench \(Sec\.[4](https://arxiv.org/html/2610.22672#S4)\), DroidTask\([Wen et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib29)\), and SPA\-Bench\([Chen et al\., 2025a](https://arxiv.org/html/2610.22672#bib.bib3)\)\. For DroidTask/SPA\-Bench we redefine success as reaching the pre\-action destination \(not the final action\), reusing the benchmark\-native judge \(Appendix[E](https://arxiv.org/html/2610.22672#A5)\) and reporting final numbers using human\-annotated results\. Only within\-columnno\-memory→\\rightarrow\+TAG\-Navdeltas are compared\. Table[2](https://arxiv.org/html/2610.22672#S4.T2)gives per\-app graph sizes and target coverage \(exploration effort: Appendix[B\.2](https://arxiv.org/html/2610.22672#A2.SS2)\)\. Online navigation uses the canonical configuration: dual\-field retrieval, top\-1 selection, waypoint memory \(Appendix[B\.5](https://arxiv.org/html/2610.22672#A2.SS5)\)\.
### 5\.2Main Result: Cross\-Backbone, Cross\-Benchmark
Table[3](https://arxiv.org/html/2610.22672#S5.T3)reports the headline result: TAG\-Nav improves over no\-memory in every aggregate cell\. These are navigation gains, not end\-to\-end task\-completion gains\. Graph coverage is partial \(Table[2](https://arxiv.org/html/2610.22672#S4.T2)\), and a backbone can still reach an uncovered destination from its own app knowledge, so successes are not bounded by coverage\. The aggregate masks per\-app heterogeneity \(Figure[3](https://arxiv.org/html/2610.22672#S5.F3)\): apps whose residual difficulty is execution rather than navigation \(Calendar, Settings\) show zero or negative per\-cell deltas, so TAG\-Nav is a navigation\-memory aid rather than a uniform improvement; see §[7](https://arxiv.org/html/2610.22672#S7)\. Settings already has a strong no\-memory baseline, and Calendar failures often occur at terminal date/time manipulation after reaching the relevant page\. Tables[3](https://arxiv.org/html/2610.22672#S5.T3)and[4](https://arxiv.org/html/2610.22672#S5.T4)report paired tests \(per\-app uncertainty: Appendix[D\.2](https://arxiv.org/html/2610.22672#A4.SS2)\); Table[5](https://arxiv.org/html/2610.22672#S5.T5)gives per\-app DroidTask\-Nav and SPA\-Bench\-Nav results\.
Table 3:Cross\-backbone, cross\-benchmark navigation\.Cells reportno\-memory→\\rightarrow\+TAG\-Navin 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\.pp: exact McNemar test; 95% confidence intervals \(CIs\) are in Appendix[D\.2](https://arxiv.org/html/2610.22672#A4.SS2)\.§The no\-memory arm resized screenshots to a 1,280\-pixel longest side; the \+TAG\-Nav arm used full resolution\.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;pp: exact McNemar test \(Appendix[D\.2](https://arxiv.org/html/2610.22672#A4.SS2)\)\. Some random\- and manual\-arm cells used the same app’s memory from a different graph condition \(Appendix[D\.3](https://arxiv.org/html/2610.22672#A4.SS3)\); without those cells, every gain remains positive\.AmazonCalendarClockMapsSettingsYouTube002020404060608080100100SR \(%\)UI\-TARS\-1\.5\-7B\+ TAG\-NavQwen\-VL\-Max\+ TAG\-NavFigure 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\-NavAppUI\-TARS\-1\.5\-7BQwen\-VL\-MaxUI\-TARS\-1\.5\-7BQwen\-VL\-MaxDroidTask\-Nav \(12 apps, 150 tasks\)AppLauncher2/54/55/52/5Calendar11/179/1712/1712/17Camera5/155/154/155/15Clock7/129/1211/1211/12Contacts12/1414/1413/1413/14Dialer7/1512/156/1512/15FileManager6/1610/1614/1613/16Gallery8/98/99/98/9Messenger13/158/1511/1511/15MusicPlayer7/97/97/97/9Notes9/145/146/144/14VoiceRecorder8/98/99/98/9Total95/15099/150107/150106/150SR \(%\)63\.366\.071\.370\.7SPA\-Bench\-Nav \(7 apps, 30 tasks\)Airbnb1/30/31/32/3Amazon2/33/33/33/3Calendar3/33/32/33/3Chrome2/33/33/33/3Clock6/63/66/65/6Google Maps3/65/65/66/6YouTube3/66/63/66/6Total20/3023/3023/3028/30SR \(%\)66\.776\.776\.793\.3Table 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\.
### 5\.3Graph Quality: Controlled Decomposition
Table[6](https://arxiv.org/html/2610.22672#S5.T6)decomposes the automated\-to\-manual gap on Qwen\. Row \(d\) keeps the automated waypoint pipeline but replaces the retrieved target with the manual destination \(isolating retrieval\); it does not improve over TAG\-Nav \(70\.2 vs\. 71\.4\); per\-app drilldown in Appendix[D\.4](https://arxiv.org/html/2610.22672#A4.SS4)\. Row \(f\) \(manual exploration\) sits*below*Auto\-BFS \(66\.7 vs\. 71\.4\) because manual graphs trade coverage for cleanliness; it is a “clean routes, narrow coverage” condition rather than an upper bound\. In a separate observational analysis of 313 archived memory\-augmented runs judged by GPT\-4o, success falls from 58% for routes with 1–2 waypoints to 50% for 3–4 and 38% for 5 or more \(correlation analysis in Appendix[D\.5](https://arxiv.org/html/2610.22672#A4.SS5)\)\. Appendix[D\.9](https://arxiv.org/html/2610.22672#A4.SS9)varies which record fields are injected\.
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](https://arxiv.org/html/2610.22672#A4.SS3)\)\. The UI\-TARS counterpart is in Appendix[D\.4](https://arxiv.org/html/2610.22672#A4.SS4)\.
### 5\.4Comparison to Prior Memory Systems
Table[7](https://arxiv.org/html/2610.22672#S5.T7)compares TAG\-Nav against prior memory\-augmented GUI agents as a memory\-format comparison on our task set and human\-annotated judge, not as a claim of outperforming PG\-Agent or GUI\-Explorer in their released forms\. PG\-Agent, which needs human demonstrations, trails no\-memory UI\-TARS, and GUI\-Explorer \(GPT\-4o actor\) falls between UI\-TARS without and with TAG\-Nav, while TAG\-Nav adds unsupervised exploration plus one retrieval per task and improves every wrapped backbone \(adaptation rules and actors in App\.[E](https://arxiv.org/html/2610.22672#A5)\)\. These rows isolate the memory abstraction \(custom validators and planners omitted\) and do not reflect each system’s published end\-to\-end performance\.
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\.
### 5\.5Transfer to Additional Apps
To test whether the benefit extends beyond the six core apps, we ran UI\-TARS\-1\.5\-7B with and without Auto\-BFS memory on 68 tasks from five further apps, labeled with the same human strict rule\. Memory raises success from 28/68 to 35/68 \(\+10\.3 pp; 11 tasks improved, 4 regressed; exact McNemarp=0\.12p=0\.12\), with gains on four of the five apps and a loss on Instagram \(Table[8](https://arxiv.org/html/2610.22672#S5.T8)\)\. The direction matches the core results, though the gain is not significant in this small cohort\.
Table 8:Transfer to five additional apps\.UI\-TARS\-1\.5\-7B, human\-judged strict destination match; separate from the 84\-task core\.
### 5\.6Failure Taxonomy
Of 48 labeled open\-loop TAG\-Nav failures, 22 are wrong retrievals \(A\), 15 near misses \(B\), and 11 execution failures \(C\); A and B together account for∼\\sim77% and are addressable to the memory pipeline, so destination retrieval and target selection remain fragile \(per\-class notes in §[7](https://arxiv.org/html/2610.22672#S7)and App\.[F\.1](https://arxiv.org/html/2610.22672#A6.SS1)\)\.
## 6Conclusion
TAG\-Nav introduces a destination\-memory module that wraps existing visual GUI agents without retraining, converting task\-agnostic offline exploration into compact target and route records injected at inference time\. Across two backbones and three benchmarks, this memory improves aggregate navigation success, and graph\-quality controls associate success more with route cleanliness than with graph size\. This makes app\-specific memory a measurable destination map rather than a larger exploration trace\.
## 7Limitations
Current evidence is strongest for Android app\-navigation tasks and a Qwen\-VL\-Max backbone\. Auto\-BFS graph memory still trails clean/manual memory in some conditions\. Graph memory depends on app version, account/login state, UI drift, and exploration coverage\. Apps with sufficiently large navigation\-affecting UI updates require re\-exploration before previously collected destination memory can be trusted; in a small two\-app probe, full\-record memory gave no benefit over no memory before or after updates \(Table[26](https://arxiv.org/html/2610.22672#A8.T26)\)\. TAG\-Nav is also not plug\-and\-play with arbitrary task\-completion benchmarks because it requires page\-reaching targets, safe stopping points, and graph\-aware diagnostics\. Manual/clean graph results should be interpreted as a control rather than the deployment assumption\. Comparisons to external benchmarks require careful protocol matching\. TAG\-Nav is most useful when the destination is graph\-covered, the route is short and clean, and the backbone can reliably execute visible actions; coverage gaps, app\-state drift, and sibling\-page retrieval errors are the dominant remaining failure modes\. The three behavioral failure classes documented in Table[24](https://arxiv.org/html/2610.22672#A6.T24)\(§[5\.6](https://arxiv.org/html/2610.22672#S5.SS6)\) correspond to these limits:*wrong retrieval*\(Class A\) reflects coverage and embedding limits,*near miss*\(Class B\) reflects last\-step disambiguation limits that sharper target selection and cleaner routes may address, and*execution failure*\(Class C\) reflects step\-budget exhaustion and open\-loop route\-following limits that per\-step memory refresh may address\.
#### Per\-app heterogeneity\.
Gains are not uniform across apps \(Figure[3](https://arxiv.org/html/2610.22672#S5.F3)\): Calendar and Settings, where the residual difficulty is execution rather than navigation, show smaller or negative deltas \(§[5\.2](https://arxiv.org/html/2610.22672#S5.SS2)\)\. We do not claim TAG\-Nav improves every \(app, backbone\) cell\.
## 8Ethical Considerations
Authorized test setting and privacy\.TAG\-Nav exercises third\-party mobile applications, so all exploration and evaluation used dedicated test devices, disposable accounts, and locally collected test data, not personal user accounts\. DestBench tasks are derived from existing benchmark trajectories and our disposable\-account collection; released artifacts use scrubbed or generic targets, and we do not distribute user\-identifiable content\. Screenshots captured during exploration may incidentally contain account\-specific content; explored graphs are intended for the same app version and account state in which they were collected, and we recommend that downstream users re\-collect graphs under their own accounts rather than reusing ours when account state matters\. Downstream use should respect app\-level terms of service and obtain authorization where required\.
Dual use and release\.Autonomous mobile GUI agents can in principle be repurposed for spam, automated account creation, or unauthorized actions on user accounts\. TAG\-Nav is a navigation\-memory module for existing backbones rather than a new execution capability: it improves where the agent goes, not what novel actions it can perform\. DestBench is intentionally scoped to page reaching and excludes the irreversible final actions most relevant to abuse scenarios such as purchasing, sending, deleting, or changing sensitive settings\. All backbone models are used under their respective open\-weight or API licenses\. We plan to release code, exploration scripts, and the evaluation protocol under terms limiting use to authorized accounts and test environments; app graphs and trajectories will be shared only where the underlying screenshots can be released\.
Compute and environmental impact\.Offline exploration and online evaluation run on commodity Android emulators; open\-weight backbones run on a local GPU host, while Qwen models and GPT\-4o are queried through the DashScope and OpenAI APIs\. We do not train a new GUI backbone in this work, so compute usage is modest relative to model\-training contributions, and the offline exploration cost amortizes across all later navigation tasks for the same app version\. At inference time, TAG\-Nav adds one retrieval call per task to the backbone’s own calls; graph\-construction counters are reported in Appendix[D\.8](https://arxiv.org/html/2610.22672#A4.SS8)\.
Data minimization and annotator labor\.DestBench task descriptions and final\-screenshot targets were annotated by the authors\. Strict\-judge calibration used the same pool to label 530 \(task, final\-screenshot\) pairs, with labelers shown only the two screens and the user instruction\.
## References
- Bai et al\. \(2025\)Shuai Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, Sibo Song, Kai Dang, Peng Wang, Shijie Wang, Jun Tang, Humen Zhong, Yuanzhi Zhu, Mingkun Yang, Zhaohai Li, Jianqiang Wan, Pengfei Wang, Wei Ding, Zheren Fu, Yiheng Xu, and 8 others\. 2025\.[Qwen2\.5\-VL technical report](https://arxiv.org/abs/2502.13923)\.*arXiv preprint arXiv:2502\.13923*\.
- Chai et al\. \(2026\)Yuxiang Chai, Shunye Tang, Han Xiao, Weifeng Lin, Hanhao Li, Jiayu Zhang, Liang Liu, Pengxiang Zhao, Guangyi Liu, Guozhi Wang, Shuai Ren, Rongduo Han, Haining Zhang, Siyuan Huang, and Hongsheng Li\. 2026\.[A3: Android agent arena for mobile GUI agents with essential\-state procedural evaluation](https://doi.org/10.18653/v1/2026.findings-acl.184)\.In*Findings of the Association for Computational Linguistics: ACL 2026*, pages 3774–3789, San Diego, California, United States\. Association for Computational Linguistics\.
- Chen et al\. \(2025a\)Jingxuan Chen, Derek Yuen, Bin Xie, Yuhao Yang, Gongwei Chen, Zhihao Wu, Li Yixing, Xurui Zhou, Weiwen Liu, Shuai Wang, Kaiwen Zhou, Rui Shao, Liqiang Nie, Yasheng Wang, Jianye Hao, Jun Wang, and Kun Shao\. 2025a\.[SPA\-Bench: A comprehensive benchmark for SmartPhone agent evaluation](https://proceedings.iclr.cc/paper_files/paper/2025/hash/9a75f4dd9679aa4ff80a4e6f0a1dc700-Abstract-Conference.html)\.In*Proceedings of the International Conference on Learning Representations*\.
- Chen et al\. \(2025b\)Weizhi Chen, Ziwei Wang, Leyang Yang, Sheng Zhou, Xiaoxuan Tang, Jiajun Bu, Yong Li, and Wei Jiang\. 2025b\.[PG\-Agent: An agent powered by page graph](https://doi.org/10.1145/3746027.3755189)\.In*Proceedings of the 33rd ACM International Conference on Multimedia*, pages 6878–6887, New York, NY, USA\. Association for Computing Machinery\.
- Cheng et al\. \(2024\)Kanzhi Cheng, Qiushi Sun, Yougang Chu, Fangzhi Xu, Yantao Li, Jianbing Zhang, and Zhiyong Wu\. 2024\.[SeeClick: Harnessing GUI grounding for advanced visual GUI agents](https://doi.org/10.18653/v1/2024.acl-long.505)\.In*Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 9313–9332, Bangkok, Thailand\. Association for Computational Linguistics\.
- Deng et al\. \(2024\)Shihan Deng, Weikai Xu, Hongda Sun, Wei Liu, Tao Tan, Jianfeng Liu, Ang Li, Jian Luan, Bin Wang, Rui Yan, and Shuo Shang\. 2024\.[Mobile\-Bench: An evaluation benchmark for LLM\-based mobile agents](https://doi.org/10.18653/v1/2024.acl-long.478)\.In*Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 8813–8831, Bangkok, Thailand\. Association for Computational Linguistics\.
- Gou et al\. \(2025\)Boyu Gou, Ruohan Wang, Boyuan Zheng, Yanan Xie, Cheng Chang, Yiheng Shu, Huan Sun, and Yu Su\. 2025\.[Navigating the digital world as humans do: Universal visual grounding for GUI agents](https://proceedings.iclr.cc/paper_files/paper/2025/hash/4ca0e369689dadb25a5345ba9755ad6f-Abstract-Conference.html)\.In*Proceedings of the International Conference on Learning Representations*\.
- Guan et al\. \(2025\)Ziyi Guan, Jason Chun Lok Li, Zhijian Hou, Pingping Zhang, Donglai Xu, Yuzhi Zhao, Mengyang Wu, Jinpeng Chen, Thanh\-Toan Nguyen, Pengfei Xian, Wenao Ma, Shengchao Qin, Graziano Chesi, and Ngai Wong\. 2025\.[KG\-RAG: Enhancing GUI agent decision\-making via knowledge graph\-driven retrieval\-augmented generation](https://doi.org/10.18653/v1/2025.emnlp-main.274)\.In*Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing*, pages 5396–5405, Suzhou, China\. Association for Computational Linguistics\.
- Hong et al\. \(2024\)Wenyi Hong, Weihan Wang, Qingsong Lv, Jiazheng Xu, Wenmeng Yu, Junhui Ji, Yan Wang, Zihan Wang, Yuxiao Dong, Ming Ding, and Jie Tang\. 2024\.[CogAgent: A visual language model for GUI agents](https://doi.org/10.1109/CVPR52733.2024.01354)\.In*Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pages 14281–14290\.
- Hurst et al\. \(2024\)Aaron Hurst, Adam Lerer, Adam P\. Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Ostrow, Akila Welihinda, Alan Hayes, Alec Radford, Aleksander Mądry, Alex Baker\-Whitcomb, Alex Beutel, Alex Borzunov, Alex Carney, Alex Chow, Alex Kirillov, Alex Nichol, Alex Paino, and 398 others\. 2024\.[GPT\-4o system card](https://arxiv.org/abs/2410.21276)\.*arXiv preprint arXiv:2410\.21276*\.
- Im et al\. \(2026\)Youngmin Im, Byeongung Jo, Jaeyoung Wi, Seungwoo Baek, Tae Hoon Min, Joo Hyung Lee, Sangeun Oh, Insik Shin, and Sunjae Lee\. 2026\.[MobiBench: Multi\-branch, modular benchmark for mobile GUI agents](https://arxiv.org/abs/2512.12634v3)\.*arXiv preprint arXiv:2512\.12634v3*\.
- Kong et al\. \(2026\)Quyu Kong, Xu Zhang, Zhenyu Yang, Nolan Gao, Chen Liu, Panrong Tong, Chenglin Cai, Hanzhang Zhou, Jianan Zhang, Liangyu Chen, Zhidan Liu, Steven Hoi, and Yue Wang\. 2026\.[MobileWorld: Benchmarking autonomous mobile agents in agent\-user interactive and MCP\-augmented environments](https://doi.org/10.18653/v1/2026.acl-long.278)\.In*Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 6142–6167, San Diego, California, United States\. Association for Computational Linguistics\.
- Li et al\. \(2024\)Wei Li, William Bishop, Alice Li, Chris Rawles, Folawiyo Campbell\-Ajala, Divya Tyamagundlu, and Oriana Riva\. 2024\.[On the effects of data scale on UI control agents](https://doi.org/10.52202/079017-2925)\.In*Advances in Neural Information Processing Systems*, volume 37, pages 92130–92154\. Curran Associates, Inc\.
- Li et al\. \(2025\)Yanda Li, Chi Zhang, Wenjia Jiang, Wanqi Yang, Bin Fu, Pei Cheng, Xin Chen, Ling Chen, and Yunchao Wei\. 2025\.[AppAgent v2: Advanced agent for flexible mobile interactions](https://arxiv.org/abs/2408.11824)\.*arXiv preprint arXiv:2408\.11824*\.
- Li et al\. \(2017\)Yuanchun Li, Ziyue Yang, Yao Guo, and Xiangqun Chen\. 2017\.[DroidBot: a lightweight UI\-guided test input generator for Android](https://doi.org/10.1109/ICSE-C.2017.8)\.In*2017 IEEE/ACM 39th International Conference on Software Engineering Companion \(ICSE\-C\)*, pages 23–26\.
- Lu et al\. \(2025\)Quanfeng Lu, Wenqi Shao, Zitao Liu, Lingxiao Du, Fanqing Meng, Boxuan Li, Botong Chen, Siyuan Huang, Kaipeng Zhang, and Ping Luo\. 2025\.[GUIOdyssey: A comprehensive dataset for cross\-app GUI navigation on mobile devices](https://doi.org/10.1109/ICCV51701.2025.02080)\.In*Proceedings of the IEEE/CVF International Conference on Computer Vision*, pages 22404–22414\.
- Lu et al\. \(2024\)Yadong Lu, Jianwei Yang, Yelong Shen, and Ahmed Awadallah\. 2024\.[OmniParser for pure vision based GUI agent](https://arxiv.org/abs/2408.00203)\.*arXiv preprint arXiv:2408\.00203*\.
- Qin et al\. \(2025\)Yujia Qin, Yining Ye, Junjie Fang, Haoming Wang, Shihao Liang, Shizuo Tian, Junda Zhang, Jiahao Li, Yunxin Li, Shijue Huang, Wanjun Zhong, Kuanye Li, Jiale Yang, Yu Miao, Woyu Lin, Longxiang Liu, Xu Jiang, Qianli Ma, Jingyu Li, and 16 others\. 2025\.[UI\-TARS: Pioneering automated GUI interaction with native agents](https://arxiv.org/abs/2501.12326)\.*arXiv preprint arXiv:2501\.12326*\.
- Qwen Team \(2026a\)Qwen Team\. 2026a\.[Qwen3\.5: Towards native multimodal agents](https://qwen.ai/blog?id=qwen3.5)\.Qwen blog post,[https://qwen\.ai/blog?id=qwen3\.5](https://qwen.ai/blog?id=qwen3.5)\.Accessed: 2026\-09\-30\.
- Qwen Team \(2026b\)Qwen Team\. 2026b\.[Qwen3\.6\-Plus: Towards real world agents](https://qwen.ai/blog?id=qwen3.6)\.Qwen blog post,[https://qwen\.ai/blog?id=qwen3\.6](https://qwen.ai/blog?id=qwen3.6)\.Accessed: 2026\-09\-30\.
- Radford et al\. \(2021\)Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever\. 2021\.[Learning transferable visual models from natural language supervision](https://proceedings.mlr.press/v139/radford21a.html)\.In*Proceedings of the 38th International Conference on Machine Learning*, volume 139 of*Proceedings of Machine Learning Research*, pages 8748–8763\. PMLR\.
- Rawles et al\. \(2025\)Christopher Rawles, Sarah Clinckemaillie, Yifan Chang, Jonathan Waltz, Gabrielle Lau, Marybeth Fair, Alice Li, William E\. Bishop, Wei Li, Folawiyo Campbell\-Ajala, Daniel Kenji Toyama, Robert James Berry, Divya Tyamagundlu, Timothy P\. Lillicrap, and Oriana Riva\. 2025\.[AndroidWorld: A dynamic benchmarking environment for autonomous agents](https://proceedings.iclr.cc/paper_files/paper/2025/hash/01a83bc2f2732a58e6aa731e659e7101-Abstract-Conference.html)\.In*Proceedings of the International Conference on Learning Representations*\.
- Rawles et al\. \(2023\)Christopher Rawles, Alice Li, Daniel Rodriguez, Oriana Riva, and Timothy Lillicrap\. 2023\.[Android in the Wild: A large\-scale dataset for Android device control](https://doi.org/10.52202/075280-2609)\.In*Advances in Neural Information Processing Systems*, volume 36, pages 59708–59728\. Curran Associates, Inc\.
- Shi et al\. \(2026\)Yibo Shi, Jungang Li, Linghao Zhang, Zihao Dongfang, Biao Wu, Sicheng Tao, Yibo Yan, Chenxi Qin, Weiting Liu, Zhixin Lin, Hanqian Li, Yu Huang, Song Dai, Yonghua Hei, Yue Ding, Xiang Li, Shikang Wang, Chengdong Xu, Jingqi Liu, and 9 others\. 2026\.[AndroTMem: From interaction trajectories to anchored memory in long\-horizon GUI agents](https://arxiv.org/abs/2603.18429)\.*arXiv preprint arXiv:2603\.18429*\.
- Sun et al\. \(2025\)Yuchen Sun, Shanhui Zhao, Tao Yu, Hao Wen, Samith Va, Mengwei Xu, Yuanchun Li, and Chongyang Zhang\. 2025\.[GUI\-Xplore: Empowering generalizable GUI agents with one exploration](https://doi.org/10.1109/CVPR52734.2025.01814)\.In*Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pages 19477–19486\.
- Wang et al\. \(2025a\)Haoming Wang, Haoyang Zou, Huatong Song, Jiazhan Feng, Junjie Fang, Junting Lu, Longxiang Liu, Qinyu Luo, Shihao Liang, Shijue Huang, Wanjun Zhong, Yining Ye, Yujia Qin, Yuwen Xiong, Yuxin Song, Zhiyong Wu, Aoyan Li, Bo Li, Chen Dun, and 93 others\. 2025a\.[UI\-TARS\-2 technical report: Advancing GUI agent with multi\-turn reinforcement learning](https://arxiv.org/abs/2509.02544)\.*arXiv preprint arXiv:2509\.02544*\.
- Wang et al\. \(2024\)Junyang Wang, Haiyang Xu, Haitao Jia, Xi Zhang, Ming Yan, Weizhou Shen, Ji Zhang, Fei Huang, and Jitao Sang\. 2024\.[Mobile\-Agent\-v2: Mobile device operation assistant with effective navigation via multi\-agent collaboration](https://doi.org/10.52202/079017-0088)\.In*Advances in Neural Information Processing Systems*, volume 37, pages 2686–2710\. Curran Associates, Inc\.
- Wang et al\. \(2025b\)Zhenhailong Wang, Haiyang Xu, Junyang Wang, Xi Zhang, Ming Yan, Ji Zhang, Fei Huang, and Heng Ji\. 2025b\.[Mobile\-Agent\-E: Self\-evolving mobile assistant for complex tasks](https://arxiv.org/abs/2501.11733)\.In*NeurIPS 2025 Workshop on Scaling Environments for Agents*\.
- Wen et al\. \(2024\)Hao Wen, Yuanchun Li, Guohong Liu, Shanhui Zhao, Tao Yu, Toby Jia\-Jun Li, Shiqi Jiang, Yunhao Liu, Yaqin Zhang, and Yunxin Liu\. 2024\.[AutoDroid: LLM\-powered task automation in Android](https://doi.org/10.1145/3636534.3649379)\.In*Proceedings of the 30th Annual International Conference on Mobile Computing and Networking*, pages 543–557, New York, NY, USA\. Association for Computing Machinery\.
- Xie et al\. \(2025\)Bin Xie, Rui Shao, Gongwei Chen, Kaiwen Zhou, Yinchuan Li, Jie Liu, Min Zhang, and Liqiang Nie\. 2025\.[GUI\-explorer: Autonomous exploration and mining of transition\-aware knowledge for GUI agent](https://doi.org/10.18653/v1/2025.acl-long.282)\.In*Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 5650–5667, Vienna, Austria\. Association for Computational Linguistics\.
- Xu et al\. \(2025a\)Weikai Xu, Zhizheng Jiang, Yuxuan Liu, Pengzhi Gao, Wei Liu, Jian Luan, Yuanchun Li, Yunxin Liu, Bin Wang, and Bo An\. 2025a\.[Mobile\-Bench\-v2: A more realistic and comprehensive benchmark for VLM\-based mobile agents](https://arxiv.org/abs/2505.11891)\.*arXiv preprint arXiv:2505\.11891*\.
- Xu et al\. \(2025b\)Yifan Xu, Xiao Liu, Xueqiao Sun, Siyi Cheng, Hao Yu, Hanyu Lai, Shudan Zhang, Dan Zhang, Jie Tang, and Yuxiao Dong\. 2025b\.[AndroidLab: Training and systematic benchmarking of Android autonomous agents](https://doi.org/10.18653/v1/2025.acl-long.107)\.In*Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 2144–2166, Vienna, Austria\. Association for Computational Linguistics\.
- Yu et al\. \(2026\)Mingxian Yu, Siqi Luo, and Xu Chen\. 2026\.[GraphPilot: GUI task automation with one\-step LLM reasoning powered by knowledge graph](https://doi.org/10.64509/jicn.21.45)\.*Journal of Intelligent Computing and Networking*, 2\(1\):13–21\.
- Zhang et al\. \(2025a\)Chi Zhang, Zhao Yang, Jiaxuan Liu, Yanda Li, Yucheng Han, Xin Chen, Zebiao Huang, Bin Fu, and Gang Yu\. 2025a\.[AppAgent: Multimodal agents as smartphone users](https://doi.org/10.1145/3706598.3713600)\.In*Proceedings of the 2025 CHI Conference on Human Factors in Computing Systems*, pages 1–20, New York, NY, USA\. Association for Computing Machinery\.
- Zhang et al\. \(2025b\)Yanzhao Zhang, Mingxin Li, Dingkun Long, Xin Zhang, Huan Lin, Baosong Yang, Pengjun Xie, An Yang, Dayiheng Liu, Junyang Lin, Fei Huang, and Jingren Zhou\. 2025b\.[Qwen3 Embedding: Advancing text embedding and reranking through foundation models](https://arxiv.org/abs/2506.05176)\.*arXiv preprint arXiv:2506\.05176*\.
- Zhang et al\. \(2025c\)Zhong Zhang, Yaxi Lu, Yikun Fu, Yupeng Huo, Shenzhi Yang, Yesai Wu, Han Si, Xin Cong, Haotian Chen, Yankai Lin, Jie Xie, Wei Zhou, Wang Xu, Yuanheng Zhang, Zhou Su, Zhongwu Zhai, Xiaoming Liu, Yudong Mei, Jianming Xu, and 6 others\. 2025c\.[AgentCPM\-GUI: Building mobile\-use agents with reinforcement fine\-tuning](https://doi.org/10.18653/v1/2025.emnlp-demos.12)\.In*Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing: System Demonstrations*, pages 155–180, Suzhou, China\. Association for Computational Linguistics\.
- Zhou et al\. \(2025\)Hanzhang Zhou, Xu Zhang, Panrong Tong, Jianan Zhang, Liangyu Chen, Quyu Kong, Chenglin Cai, Chen Liu, Yue Wang, Jingren Zhou, and Steven Hoi\. 2025\.[MAI\-UI technical report: Real\-world centric foundation GUI agents](https://arxiv.org/abs/2512.22047)\.*arXiv preprint arXiv:2512\.22047*\.
- Zhu et al\. \(2026\)Sibo Zhu, Wenyi Wu, Kun Zhou, Stephen Wang, and Biwei Huang\. 2026\.[Hybrid self\-evolving structured memory for computer\-use agents](https://doi.org/10.18653/v1/2026.findings-acl.549)\.In*Findings of the Association for Computational Linguistics: ACL 2026*, pages 11287–11304, San Diego, California, United States\. Association for Computational Linguistics\.
## Appendix
### Table of Contents
## Appendix ADestBench Construction
This section documents the construction of DestBench, from app selection through annotation through automated judging\.
### A\.1App selection rationale and full app list
We selected 20 Android apps spanning nine product categories, with a core cohort of 6 apps used for the controlled graph\-condition study \(no\-memory, random, Auto\-BFS, clean manual\)\. Apps were chosen to span \(i\) shallow vs deep navigation depth, \(ii\) static vs dynamic content, \(iii\) presence vs absence of account\-gated screens, and \(iv\) presence of modals, drawers, and bottom\-sheet UI patterns\. Table[9](https://arxiv.org/html/2610.22672#A1.T9)lists all apps with their category and core\-cohort membership\.
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\)\.
### A\.2Task\-collection pipeline
Tasks are derived from real user\-trajectory recordings collected in our benchmark substrate\. Each recording is segmented at the pre\-action destination boundary \(the last screen before a task\-specific irreversible operation, defined in §[4](https://arxiv.org/html/2610.22672#S4)\) and labeled with a natural\-language instruction by paraphrasing the original goal\. Instructions are filtered to remove user\-identifying content and to disambiguate destinations that admit multiple visually\-distinct correct pages\.
### A\.3Destination annotation protocol
Each task instance is annotated with a target screenshotxtargetx\_\{\\mathrm\{target\}\}that visually identifies the pre\-action destination, plus a dynamic\-state tolerance mask that lists which UI regions \(e\.g\., timestamps, scroll positions, advertisement slots\) are ignored by the judge\. The primary curator annotated the full core cohort; a second author audited a random 20% sample of the annotated targets, and the small number of disagreements \(predominantly cases where multiple visually\-distinct pages plausibly satisfied the instruction\) were resolved jointly against the original trajectory recording\. We report this rather than a full second\-pass inter\-annotator agreement because the dominant source of annotation noise in our pipeline is target ambiguity, not labeler disagreement on unambiguous cases, and the strict\-judge calibration in App\.[A\.5](https://arxiv.org/html/2610.22672#A1.SS5)provides a downstream check on residual labeling noise\. The primary metric requires the reference destination; a near miss is a failure\.
### A\.4Representative tasks
Table[10](https://arxiv.org/html/2610.22672#A1.T10)gives six representative tasks across six apps, showing the instruction, target page, and the stopping boundary that excludes downstream execution from scoring\.
Table 10:Representative DestBench task examples\.Each task specifies a natural\-language instructionqq, 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\.
### A\.5GPT\-4o judge calibration
The judge prompt \(Appendix[C\.4](https://arxiv.org/html/2610.22672#A3.SS4)\) is calibrated against a single\-curator gold set of 530 \(task, final\-screenshot\) pairs\. Table[11](https://arxiv.org/html/2610.22672#A1.T11)reports binary agreement, false\-pass/false\-fail breakdown, and ordinalκ\\kappa\. The residual 13 disagreements are primarily false\-pass, and concentrate on near\-miss cases \(sibling pages, stopping one page early\)\. The ordinal Cohen’sκ\\kappaof 0\.95 indicates substantial agreement beyond chance\.
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\.
### A\.6DestBench app counts
Table[2](https://arxiv.org/html/2610.22672#S4.T2)\(rendered inline in §[4](https://arxiv.org/html/2610.22672#S4)\) shows per\-app task counts in the core cohort\. The 6\-app core cohort spans Google Maps, Amazon, YouTube, Settings, Clock, and Calendar, totaling 84 tasks\.
## Appendix BTAG\-Nav Implementation Details
### B\.1Hypernode matching
Hypernode matching compares a new screen against each stored member screen of a hypernode on two signals: visual similarity, as the cosine similarity of CLIP ViT\-B/32 screenshot embeddings\([Radford et al\., 2021](https://arxiv.org/html/2610.22672#bib.bib21)\), and layout similarity of the Android XML view hierarchy, using a normalized tree\-edit distance andtext\-embedding\-v4embeddings of the page layout\. A screen joins the hypernode when both signals are within thresholds tuned during graph collection\.
### B\.2Local\-BFS walk policy
Exploration runs up to 1,000 walks from the app root, each with at most five forward steps\. With probability 0\.7, a walk expands locally: it tries untested actions on the current screen and verifies each return, for up to 15 successful undo\-and\-check cycles; otherwise it explores randomly\. Actions already tried on the current screen or its matched siblings are skipped, and the rest are ordered by type \(image elements first, then scroll, swipe, and card actions, then the rest\), with random tie\-breaking\. Table[20](https://arxiv.org/html/2610.22672#A4.T20)reports the resulting walk and action counts per app\.
### B\.3Memory record schema
Each destination recordrh,nr\_\{h,n\}is a tuple\(h,n,d,I,W,H,zd,zI\)\(h,n,d,I,W,H,z^\{d\},z^\{I\}\)wherehhis the hypernode id,nnis the member\-node id,ddis a natural\-language page summary,IIis a list of direct user\-intents the page satisfies,WWis a deduplicated waypoint sequence from the app root,HHis a list of per\-transition disambiguation hints, andzd,zIz^\{d\},z^\{I\}are DashScopetext\-embedding\-v4embeddings\([Zhang et al\., 2025b](https://arxiv.org/html/2610.22672#bib.bib35)\)ofddand the concatenation ofII\. Records are stored as JSONL with one record per line for fast top\-kkretrieval at inference\.
### B\.4Backbone configurations
Table[12](https://arxiv.org/html/2610.22672#A2.T12)lists the shared prompting and decoding settings used for both backbones\.
Table 12:Backbone configurations\.Same prompting and decoding hyperparameters across both backbones; only the model weights and tokenizer differ\.mobile\-opsis the shared action vocabulary \(click,type,scroll,back,home,wait,finished\)\.
### B\.5Protocol details
Device configuration \(Android emulator on Android 16, API level 36\.1, ABI arm64\-v8a\), action space, retrieval top\-kk, step budgets, and seed/temperature settings used in §[5](https://arxiv.org/html/2610.22672#S5)\. Each app runs on a freshly reset emulator image with a dedicated benchmark account; login state and account\-private data are persisted across tasks within the same app but never shared across apps\.
## Appendix CPrompts
All prompts are reproduced verbatim\. We use them with the model versions reported in Appendix[H\.6](https://arxiv.org/html/2610.22672#A8.SS6)\.
### C\.1Metadata extraction prompt \(page summary, direct intent, route distillation\)
The page summary, direct\-intent extraction, and route distillation are performed by a single VLM call that extracts all three fields jointly\. Given a sequence of annotated screenshots \(with green rectangles marking tap targets and arrows marking scrolls\) plus optional action descriptions, the VLM returns a JSON object withvisual\_page\_summary,intent\_from\_current\_screen, andnavigation\_memory\(containingrelevant\_waypoint\_sequenceandtransition\_hints\)\.
#### System prompt
ReturnonlyvalidJSON\.Nomarkdown\.Noexplanation\.
Youaregiven:
1\.asequenceofannotatedscreenshots
2\.optionalactiondescriptionsthathelpexplainthevisualannotations
Thescreenshotsareorderedfromearliertolater\.Thelastscreenshotisthecurrent/finalscreen\.Onlythelastscreenshotshouldbetreatedasthetargetscreenforretrieval\.
Theearlierscreenshotsshowhowtheuserarrivedatthefinalscreen\.Theymaycontainvisualizedactions:
\-scrollorswipeactionsareshownwitharrows
\-otheractionsareshownwithgreenrectanglesaroundtheclickedtarget
Mostimportantruleforretrievalmetadata:focusontheactiveinteractionlayerofthefinalscreenshot\.
Activeinteractionlayer:
\-Ifamodal,dialog,popup,bottomsheet,drawer,menu,permissionprompt,overlay,snackbaractionpanel,orforegroundpanelisopen,treatthatforegroundlayerasthecurrentscreen\.
\-Inthatcase,ignorethedimmed,blurred,partiallycovered,orbackgroundcontentbehindit\.
\-Donotextractintentsfromthebackgroundscreenwhenaforegroundlayerisactive\.
\-Ifabottomsheetormodalcoversonlypartofthescreen,stilltreatthesheet/modalastheactivescreenandignoreunrelatedbackgroundcontent\.
\-Ifanoverflowmenuorfloatingmenuisopen,describethemenu’spurposeandvisiblemenuoptions,notthepagebehindit\.
\-Ifapermissiondialogorsystemdialogisopen,describethedialog’sintent,nottheappscreenbehindit\.
\-Ifthereisnoforegroundoverlay,usethefullfinalscreenshot\.
Importantforretrievalmetadata:
\-Theactionannotationsonearlierscreenshotsarecontextforthepath\.
\-Ifthefinalscreenshotcontainsvisibleactions,controls,tabs,menuitems,ordestinationsthatwouldleadsomewhereelse,donottreatthoseastheuser’sintent\.
\-Donotlistsiblingpagesordestinationsvisibleonthefinalscreenasintents\.
\-Donotinferthattheuserwantstogotoanotherpagejustbecausethatoptionisvisible\.
\-Thegoalistodescribewhattheactivefinalscreen/layeritselfdirectlysatisfiesifitistheintendeddestination\.
Extractthesefields:
visual\_page\_summary:
\-oneshortphrasedescribingthestablepurposeoftheactivefinalscreenorforegroundlayer
\-basethismainlyontheactivelayerinthefinalscreenshot
\-useearlierscreenshotsonlytodisambiguatewhatthefinalactivelayeris
\-donotdescribethepathorpreviousscreens
\-ifamodal/dialog/menu/sheetisactive,summarizethatforegroundcomponent,notthebackgroundpage
intent\_from\_current\_screen:
\-userintentsdirectlysatisfiedbytheactivefinalscreenorforegroundlayeritself
\-includeinformationtheusercaninspectontheactivelayer
\-includeactionstheusercancompleteontheactivelayerwithoutneedingtonavigatetoanotherscreen
\-donotincludeintentsrequiringleavingtheactivelayer
\-donotincludesiblingtabs,bottomnavigationdestinations,menuentriesfromthebackground,orlinkstootherpages
\-donotincludelow\-levelUImechanics
\-ifanoverlayisopen,includeonlyintentssupportedbytheoverlay,dialog,menu,sheet,orforegroundpanel
navigation\_memory:
\-acompactreusablememorydescribinghowtoreachtheCURRENT/finalnodefromthetrajectory
\-useearlierscreenshotsandactiondescriptionstoinferthecleansemanticroutetothefinalscreen
\-theCURRENTnoderemainsthesourceoftruth
\-removeloops,retries,oscillations,backtracking,andirrelevantdetours
\-prefertheshortestsemanticallyvalidforwardroutetotheCURRENTnode
\-ifearlypathsegmentsvaryorarenoisy,preferthesharedsub\-routeclosesttotheCURRENTnode
\-keepeverythingstrictlyin\-app
\-neverimplyleavingtheapp,goingtothelauncher,orusingtheOShomescreen
\-ifawaypointcouldbeconfusedwithOShome,rewriteitasanin\-appdestinationsuchas"homefeedtab\(in\-app\)","mainfeed",or"apphomescreen"
\-waypointsmustbesemanticpage/statelabels,notactionphrases
\-transitionhintsmustdescribesemanticguidance,notlow\-levelgesturemechanics
\-avoidcoordinates,boundingboxes,brittlevisualdetails,andliteralevent\-logreplay
\-preferreusablesemanticlabelsoverusernames,productnames,exactposttopics,timestamps,counts,orone\-offvisiblevaluesunlessessential
\-donotmentioninternalreasoning,clusters,nodeids,graph\-analysislanguage,retrieval,ranking,screenshots,annotations,ortrajectories
Outputstylerules:
\-uselowercaseforvisual\_page\_summaryandintent\_from\_current\_screen
\-navigation\_memorymayusetitle\-casesemanticwaypointlabelsifclearer
\-keeponlysemanticallydistinctintents
\-preferspecificusergoalsovergenericdescriptions
\-ignoreos/statusbardata,ads,timestamps,temporaryfeeditems,andpromotionalcontent
\-avoidlow\-levelUIwordsinintents:tap,click,press,icon,button,rectangle,arrow,swipe,scroll,tab,menu
\-returnatmost8intents
\-returnatmost6waypoints
\-returnatmost6transitionhints
#### User prompt
Actiondescriptions,intrajectoryorder:
\{action\_descriptions\}
Remember:
\-screenshotsareprovidedinorder
\-thelastscreenshotisthecurrent/finalscreen
\-earlierscreenshotsareonlypathcontext
\-greenrectanglesandarrowsshowactionstakeninthetrajectory
\-focusretrievalmetadataonlyontheactiveinteractionlayerinthefinalscreenshot
\-ifamodal,dialog,popup,bottomsheet,drawer,menu,permissionprompt,orforegroundoverlayisopen,extractmetadataonlyfromthatforegroundlayer
\-ignoredimmed,blurred,covered,orbackgroundcontentbehindanactiveforegroundlayer
\-donottreatactionsavailableonthefinalscreenastheuser’sintentunlesstheactivefinalscreen/layeritselfdirectlysatisfiesthatintent
\-donotincludedestinationsreachablefromthefinalscreenorfromthebackgroundscreen
\-fornavigation\_memory,inferthecleanestsemanticin\-approutethatreachesthecurrent/finalscreen
\-removeloops,retries,oscillations,backtracking,andirrelevantdetours
\-waypointsmustbesemanticpage/statelabels,notactionphrases
\-transitionhintsmustbesemanticguidance,notlow\-levelgestureinstructions
ReturnstrictJSONonlywithexactlythisschema:
\{"visual\_page\_summary":"","intent\_from\_current\_screen":\[\],
"navigation\_memory":\{"relevant\_waypoint\_sequence":\[\],
"transition\_hints":\[\]\}\}
### C\.2Target selector prompt
Given the user query and a list of candidate nodes, this prompt asks the VLM to rank the candidate nodes and select the single best target\. Each candidate node has avisual\_page\_summaryandintent\_from\_current\_screen\.
#### System prompt
Youreceive:
1\.auserquery
2\.alistofcandidateUInodes
3\.eachcandidatehas:index,visual\_page\_summary,intent\_from\_current\_screen,optionalretrievalscores
Yourjob:ChoosethecandidatewhoseCURRENTscreenbestsatisfiestheuserqueryasthefinaltargetnode\.
Importantrankingrules:
\-Prefertheactualtargetscreen,notaloadingscreenbeforeit\.
\-Penalizeloadingscreens,splashscreens,blankscreens,andtemporarytransitionscreensunlesstheuserexplicitlyasksforthem\.
\-Penalizemodals,dialogs,bottomsheets,overlays,drawers,andoverflowmenusunlesstheuserexplicitlyasksforthatforegroundcomponent\.
\-Donotchooseapageonlybecauseithasanoptionthatleadstothetarget\.
\-Donotchooseasettingspagemerelybecauseitmentionstherequestedfeature\.Example:"timersoundsettings"isnotthesameas"timersection"\.
\-Forpage/navigationqueriessuchas"navigatetothehelppage","opentimer",or"gotosettings":prioritizevisual\_page\_summary\.
\-Fortask/actionqueriessuchas"turnoffalarm","changetimersound",or"sendfeedback":useintent\_from\_current\_screenmorestrongly\.
\-Ifthequeryasksforageneralhelppage,preferahelpresources/supportpageoveraspecifichelparticle,unlessthequeryasksforthatarticle\.
\-Ifthequeryasksforaspecifichelptopic,preferthematchinghelparticle\.
\-Ifacandidateisaloadingscreenforapageandanothercandidateistheactualloadedpage/content,choosetheactualloadedpage/content\.
\-Chooseonlyfromtheprovidedcandidateindices\.
Candidatelabels:
\-target:thecurrentscreenisthebestfinaltarget\.
\-acceptable:relevantandusable,butnotthebest\.
\-transient\_related:loading/temporarystaterelatedtothetarget\.
\-waypoint:canleadtothetargetbutisnotitselfthetarget\.
\-related\_but\_wrong:relatedtermsappear,butitisnotthetarget\.
\-wrong:irrelevant\.
ReturnonlyvalidJSON\.Nomarkdown\.NoexplanationoutsideJSON\.
Outputschema:
\{"best\_index":0,"best\_label":"target","confidence":0\.0,
"reason":"shortreason","ranked\_candidates":\[\{"index":0,
"label":"target\|acceptable\|transient\_related\|waypoint\|related\_but\_wrong\|wrong",
"score":0\.0,"reason":"shortreason"\}\]\}
#### User prompt
Applicationdescription:\{app\_description\}
CandidateUInodes:\{compact\_candidates\}
Selectthebesttargetnodeindex\.
Remember:
\-Thetargetisthenodewhosecurrentscreenitselfsatisfiesthequery\.
\-Donotchooseloadingscreensifanactualcontentpageisavailable\.
\-Donotchoosemenus,modals,orbottomsheetsunlessthequeryasksforthem\.
\-Donotchooseasettingspagejustbecauseitmentionstherequestedfeature\.
\-For"helppage",preferthegeneralhelp/support/resourcespageoveraspecificarticleunlessthequerynamesthatarticle\.
### C\.3Destination\-memory injection template
At the beginning of task navigation, this text block is prepended to the backbone actor’s system prompt with the memory plan to complete the current task\. The injected memory contains the user instruction, the retrieved waypoint sequence, and the per\-transition hints\. The block is fixed across the trajectory in the open\-loop canonical configuration; dynamic variants \(Appendix[H\.7](https://arxiv.org/html/2610.22672#A8.SS7)\) update it during execution\.
Finalgoal:\{prompt\}
Relevantwaypointsequence:
\{waypoint\_1\}\-\>\{waypoint\_2\}\-\>…\-\>\{waypoint\_n\}
Transitionhints:
\-\{hint\_1\}
\-\{hint\_2\}
\-…
### C\.4GPT\-4o judge prompt
A GPT\-4o call is used to compare the agent’s final screenshot against the ground\-truth target screenshot and user instruction to return a 1–5 ordinal score plus a one\-sentence justification\. Scores 4–5 are considered a success\.
Task:\{prompt\}
Image1istheAGENT’sfinalscreen\.
Image2istheGROUND\-TRUTHtargetscreen\.
Scorefrom1to5:
5=exacttargetpage/controlreached\.
4=correctfunctionalpage/sectionreached;onlyminorvisual,scroll,modal,ordynamic\-contentdifferences\.
3=partiallycorrect:samebroadarea/appsection,butwrongspecificleaf,tab,field,orsubpage\.
2=wrongsectionofthesameapp,oragentisclearlynotattherequesteddestination\.
1=wrongapp,launcher/home,stuck,orunrelatedscreen\.
Bestrictforscore4\-5\.Asiblingsettingspage,nearbylistitem,orsamebroadmenubutwrongspecifictargetisscore3,notsuccess\.
RespondwithONLYaJSONobject:
\{"score":1\-5,"justification":"<briefexplanation\>"\}
## Appendix DAdditional Quantitative Results
### D\.1Per\-app, per\-backbone, per\-benchmark breakdown
Table[13](https://arxiv.org/html/2610.22672#A4.T13)\(DestBench\) and Table[5](https://arxiv.org/html/2610.22672#S5.T5)\(DroidTask\-Nav and SPA\-Bench\-Nav\) give the per\-app results behind Table[3](https://arxiv.org/html/2610.22672#S5.T3); cells report successes over tasks for both the no\-memory and \+TAG\-Nav arms\.
Table 13:DestBench per\-app drilldown\(6 apps, 84 tasks\)\. Human\-annotated strict SR\.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](https://arxiv.org/html/2610.22672#A4.SS2)\)\.Table 15:Qwen\-VL\-Max per\-app comparisons against no memory on DestBench \(human strict labels; intervals and tests as in Appendix[D\.2](https://arxiv.org/html/2610.22672#A4.SS2)\)\.Table 16:Converted\-benchmark comparisons against no memory \(human strict labels; intervals and tests as in Appendix[D\.2](https://arxiv.org/html/2610.22672#A4.SS2)\)\.
### D\.2Per\-app uncertainty
Tables[14](https://arxiv.org/html/2610.22672#A4.T14)and[15](https://arxiv.org/html/2610.22672#A4.T15)compare each graph condition with no memory per app on the 84 DestBench tasks, and Table[16](https://arxiv.org/html/2610.22672#A4.T16)does the same for the converted benchmarks\. All outcomes are human strict labels\. Intervals are 95% paired bootstrap intervals over tasks \(10,000 resamples\), andppvalues come from exact two\-sided McNemar tests; neither is adjusted for multiple comparisons, here or in Tables[3](https://arxiv.org/html/2610.22672#S5.T3)and[4](https://arxiv.org/html/2610.22672#S5.T4)\.
### D\.3Graph\-arm memory provenance
In some random\- and manual\-arm app cells, the harness supplied the same app’s memory from a different graph condition\. Table[17](https://arxiv.org/html/2610.22672#A4.T17)repeats the comparisons of Table[4](https://arxiv.org/html/2610.22672#S5.T4)without those apps; every gain remains positive\.
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](https://arxiv.org/html/2610.22672#A4.SS2)\.
### D\.4Per\-app graph\-quality breakdown
Table[18](https://arxiv.org/html/2610.22672#A4.T18)is the per\-app counterpart to Table[6](https://arxiv.org/html/2610.22672#S5.T6)\. Per\-app patterns make the aggregate finding concrete: deep\-menu apps benefit most from any memory \(the destination is several hops below the entry screen\), while shallow apps like Settings and Calendar benefit least because their residual difficulty is execution rather than navigation\.
AppNo memoryRandomAuto\-BFSManualAmazon9/1711/1710/1712/17Calendar5/107/104/106/10Clock1/94/93/93/9Google Maps12/2416/2415/2420/24Settings8/97/97/98/9YouTube9/159/1510/1510/15Total44/8454/8449/8459/84Success Rate52\.4%64\.3%58\.3%70\.2%Table 18:Per\-app graph\-quality breakdown on DestBench using UI\-TARS\-1\.5\-7B\.Cells aresuccesses / attemptsunder the strict human\-scoring rule; all cells are human\-labeled \(Appendix[D\.2](https://arxiv.org/html/2610.22672#A4.SS2)\)\.
### D\.5Route cleanliness
Table[19](https://arxiv.org/html/2610.22672#A4.T19)reports how properties of the injected route correlate with success in the 313 GPT\-4o\-judged runs of Section[5\.3](https://arxiv.org/html/2610.22672#S5.SS3)\. Routes from manual graphs are shorter than Auto\-BFS routes \(2\.9 vs\. 6\.0 waypoints on average\)\.
Table 19:Route\-cleanliness associations\.GPT\-4o\-judged runs of Section[5\.3](https://arxiv.org/html/2610.22672#S5.SS3)\. Route length and hint count correlate negatively with success; this observational analysis does not establish causality\.
### D\.6Memory format and retrieval\-depth ablation
Ablations supporting the canonical configuration: waypoint vs step\-numbered memory crossed with top\-kkretrieval depth\. Step\-numbered observations trigger spuriouswait\(\)loops when the agent treats a state observation as an event; top\-k\>1k\>1multi\-route injection pollutes context with routes that do not match the live UI\. The canonical configuration is semantic waypoints with top\-1 retrieval\.
### D\.7Cross\-family and prior\-memory outcomes
The AgentCPM\-GUI rows in Table[7](https://arxiv.org/html/2610.22672#S5.T7)are paired runs on the 84 DestBench tasks, with later app versions than the UI\-TARS\-1\.5\-7B and Qwen\-VL\-Max rows and labels blind to memory condition; memory raises success from 28/84 to 33/84 \(exact McNemarp=0\.23p=0\.23\)\. Some of these episodes began from in\-app state left by the previous task, such as Clock’s last tab or a Settings sub\-page\. The MAI\-UI rows come from a separate 79\-task six\-app evaluation, 72 of whose tasks overlap with DestBench; three baseline tasks were not run and are counted as failures, and one baseline task lacks a label, so the two rates use different denominators and are not a paired comparison\. The PG\-Agent adaptation reaches 36/84 strict successes \(37/84 under a second human labeling\), and GUI\-Explorer reaches 47/84 with a GPT\-4o actor and its released knowledge base\.
### D\.8Cost analysis
Table[20](https://arxiv.org/html/2610.22672#A4.T20)reports the one\-time exploration effort for each core app\. A walk is one exploration episode from the app root \(Appendix[B\.2](https://arxiv.org/html/2610.22672#A2.SS2)\), and a forward action is an action that moves the explorer to a new or known screen; resets and undo steps are not counted\. The explorer records both counts in each graph\.
Table 20:Exploration effort per core app\.Walks and forward actions recorded during graph construction \(Appendix[D\.8](https://arxiv.org/html/2610.22672#A4.SS8)\)\.
### D\.9Record\-content ablation
On 27 Instagram and eBay tasks with graphs and apps at matched versions, we vary which fields of the destination record are injected\. In this cohort, transition hints alone gave the highest success \(Table[21](https://arxiv.org/html/2610.22672#A4.T21)\); Appendix[H\.2](https://arxiv.org/html/2610.22672#A8.SS2)evaluates the same tasks after app updates\.
Table 21:Version\-matched record\-content ablation\.Human\-judged Instagram/eBay tasks at matched graph versions\. The small sample is suggestive\.
### D\.10Informed no\-memory baseline
To test whether structured records add value beyond general app knowledge, we compare them with a fixed, hand\-written manual for each core app that gives general guidance but no task\-specific destination or route \(Table[22](https://arxiv.org/html/2610.22672#A4.T22)\)\. The manual and every record variant improve on no memory by four to nine tasks, and none of the differences is significant: app\-specific text captures part of the benefit of destination memory, and this diagnostic does not separate it from the structured records\.
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\.pp: exact two\-sided McNemar against no memory\.
## Appendix EFormat\-Adapted Reimplementation Protocol
### E\.1Per\-system adaptation rules
Table[23](https://arxiv.org/html/2610.22672#A5.T23)lists how each prior system’s memory abstraction was reconstructed on our hypernode graph for Table[7](https://arxiv.org/html/2610.22672#S5.T7), and what was deliberately not reproduced \(custom actors, validators, planners\)\.
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\.
## Appendix FQualitative Examples
### F\.1Failure trajectories per class
Table 24:Failure taxonomy\.Labeled open\-loop DestBench failures\.Figures[4](https://arxiv.org/html/2610.22672#A6.F4)–[6](https://arxiv.org/html/2610.22672#A6.F6)show one canonical trajectory per failure class from Table[24](https://arxiv.org/html/2610.22672#A6.T24)\.Class A\(wrong retrieval, 46%\): the embedding\-based retrieval matched the query to the wrong graph node, and the agent faithfully followed incorrect waypoints to a semantically\-related but wrong destination\.Class B\(near miss, 31%\): the agent reached the correct area of the app but stopped at a parent page, sibling leaf, or adjacent sub\-item rather than the exact target\.Class C\(execution failure, 23%\): the memory pointed in the right direction but the agent could not execute the navigation within the step budget, typically looping or scrolling without locating the specific UI element\.



Figure 4:Class A Failure \(Wrong retrieval\)Task: “Visit the user’s saved cards” \(Amazon\)\. Memory:Shopping Cart→\\rightarrowLists Tab→\\rightarrowLists 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→\\rightarrowContribute hub→\\rightarrowProfile 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→\\rightarrowSide Navigation Menu→\\rightarrowSettings 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=15T\{=\}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\.
### F\.2Success trajectories
Two representative successes illustrate how the destination block guides the actor\. On Calendar, an unseen target buried four taps under a settings drawer is reached by following the waypoint sequence verbatim; the actor never opens the side\-menu it would have explored without memory\. On Google Maps, a multi\-route destination \(reachable through search or through the saved\-places tab\) is solved by the shorter cleaned route stored in the record; the per\-transition hints disambiguate a tab whose icon collides with a sibling control\.
### F\.3Raw destination\-record examples
Each record stores a page summary, a list of direct intents, a waypoint sequence from the app root, and per\-transition hints\. A representative record for the YouTube target “open the watch\-history list” contains the summary “screen listing previously watched videos with per\-item remove buttons,” the intent “view watch history,” the waypoint sequenceHome→\\toLibrary→\\toHistory, and the hint “Library is the bottom\-bar icon labeled You, not the side\-drawer entry of the same name\.” Records are stored as JSONL and never modified after exploration\.
## Appendix GDetailed Related\-Work Positioning
Table[25](https://arxiv.org/html/2610.22672#A7.T25)expands the categorical positioning in Table[1](https://arxiv.org/html/2610.22672#S2.T1), using concise fields so the comparison stays readable in the appendix flow\.
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\.
## Appendix HLimitations, Robustness, and Ethics
### H\.1Dynamic\-screen handling
DestBench screens contain dynamic content: advertisements, recommendation feeds, trending lists, and time\-varying notifications\. The metadata\-extraction prompt \(Appendix[C\.1](https://arxiv.org/html/2610.22672#A3.SS1)\) is written to focus on the persistent active layer, and the judge prompt \(Appendix[C\.4](https://arxiv.org/html/2610.22672#A3.SS4)\) is told to tolerate cosmetic differences\. Persistent dynamic state \(e\.g\., login\-gated content, A/B layouts\) is a known failure mode and is documented per\-app in our records\.
### H\.2Cross\-app\-version robustness
Graphs are tied to a specific app version on a specific device configuration\. In a limited 27\-task probe on Instagram \(about five months between versions\) and eBay \(about ten weeks\), full\-record memory matched no memory at both versions \(Table[26](https://arxiv.org/html/2610.22672#A8.T26)\)\. This probe does not establish general cross\-version robustness\. Apps with sufficiently large navigation\-affecting changes still require the graph to be revalidated or rebuilt before its records can be trusted\.
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\.
### H\.3Multi\-path and ambiguous\-target handling
When a destination is reachable by multiple distinct routes \(e\.g\., side\-menu vs bottom\-tab\), the record stores all routes that the explorer found and the top\-1 retrieval selects the shortest cleaned route\. When an instruction admits multiple visually\-distinct targets, the selector prompt \(Appendix[C\.2](https://arxiv.org/html/2610.22672#A3.SS2)\) breaks ties using the five preference rules; if all preferences are tied, the lower\-depth target wins\.
### H\.4Privacy and sensitive\-screen handling
We use dedicated benchmark accounts for each app, with no real user data\. Screens that would contain personal data on a real account \(e\.g\., contacts, message bodies, payment instruments\) are blank or contain synthetic placeholders\. Any public release of screenshots requires screening for identifying content\.
### H\.5Use of AI in paper preparation
LLM\-based assistants were used for literature and manuscript review, drafting, LaTeX editing, and analysis scripts\. The authors are responsible for verifying all statements, evidence, and calculations and for approving the final manuscript\. The assistants are not authors\.
### H\.6Models used in the TAG\-Nav pipeline
All hosted models were called through Alibaba Cloud’s DashScope API, except the GPT\-4o judge, which used the OpenAI API\. Exploration runs UI\-TARS\-1\.5\-7B locally for action grounding, usesqwen3\.6\-plus\([Qwen Team, 2026b](https://arxiv.org/html/2610.22672#bib.bib20)\)to extract interactive elements, and usesqwen3\.6\-flashor UI\-TARS\-1\.5\-7B for loading\-screen checks\. Hypernode matching uses CLIP ViT\-B/32 screenshot embeddings andtext\-embedding\-v4page\-layout embeddings \(Appendix[B\.1](https://arxiv.org/html/2610.22672#A2.SS1)\)\. Offline post\-processing \(page summary, direct intents, waypoint route, and transition hints\) makes oneqwen3\.6\-pluscall per root\-to\-state path\. Record fields and user instructions are embedded withtext\-embedding\-v4, a Qwen3\-Embedding model\([Zhang et al\., 2025b](https://arxiv.org/html/2610.22672#bib.bib35)\), and the target selector isqwen3\.5\-flash\([Qwen Team, 2026a](https://arxiv.org/html/2610.22672#bib.bib19)\)\. The navigation actors are UI\-TARS\-1\.5\-7B and Qwen\-VL\-Max \(qwen\-vl\-max\-latest\); the closed\-loop variant \(Appendix[H\.7](https://arxiv.org/html/2610.22672#A8.SS7)\) also describes the live screen with Qwen\-VL\-Max\. GPT\-4o\([Hurst et al\., 2024](https://arxiv.org/html/2610.22672#bib.bib10)\)is the evaluation judge\. No proprietary data leaves the local environment except through these API calls\.
### H\.7Dynamic\-memory variants
The closed\-loop variant localizes the current screen against the graph at every step and refreshes progress annotations; the plan\-edit variant rewrites the memory block when the actor signals confusion\. Both are controlled ablations of the canonical open\-loop TAG\-Nav configuration evaluated in Section[5](https://arxiv.org/html/2610.22672#S5)\.相似文章
Embodied-Navigator:指点、思考、记忆与对齐以实现高效导航
TAMP-Nav 是一个统一框架,通过将视觉语言模型与二维视觉提示对齐、使用压缩记忆的选择性推理以及策略优化来增强具身导航,实现了最先进的性能,并具有高运行时和样本效率。
相关性并不意味着适用性:面向个人 GUI 智能体的经验激活
提出了 ExpActivator,一个免训练框架,通过在冻结的 GUI 骨干网络的潜在空间中匹配当前屏幕与历史状态,仅激活与当前情境相关的经验,而非盲目追加任务相关历史;在四个 GUI 骨干网络上将轨迹内步骤成功率平均提升 28%,同时仅使用约五分之一的历史 token。
UI-KOBE:面向知识的轻量级图引导GUI代理行为探索
UI-KOBE 提出了一种框架,通过构建和利用特定应用的知识图谱来增强轻量级移动GUI代理,从而提高任务规划和执行效率。
NavGPT-3:在层级式导航运行时中驾驭上下文
NavGPT-3 提出一个将大型语言模型推理与动作策略连接的层级式导航运行时,其 NavGPT-VLA 动作策略在 R2R-CE 和 RxR-CE 上达到 SOTA,并首次使自主智能体在导航成功度和路径保真度上匹配人类水平。
学习如何记忆:GUI智能体的记忆模态选择
该论文系统研究了VLM驱动的GUI智能体中的记忆模态选择问题,发现最优记忆表示是随交互步骤变化的,并提出SwitchMem路由框架在每一步动态选择文本或视觉记忆,在三个GUI基准上超越了使用静态记忆表示的基线方法。