Mobile GUI agents frequently perform repetitive tasks with similar interaction procedures. Reusing previous executions can reduce redundant LLM inference and execution overhead, but variations in user instructions and execution environments may invalidate previously successful actions. We systematically characterize these variations into six representative categories and observe that such changes do not necessarily invalidate entire procedures: individual transitions can remain reusable when validated against the current task context and interface state. Based on this insight, we propose graph-text templates for selective execution-trace reuse. The graph captures UI states and action transitions, while the text encodes task intent, procedural structure, and typed slots for variable content. A record-template-replay framework constructs templates from verified executions and leverages the current instruction and live UI state to reuse, adapt, or discard individual transitions. Given an execution trace, our framework reduces LLM inference token consumption by approximately 80% on average across five base agents on AndroidWorld, with most agents achieving at least 1.5-fold execution speedup over LLM-only execution. In real-device evaluations on Android and HarmonyOS, our framework achieves action reuse ratios of 70.7-79.8% while maintaining over 2-fold execution speedup in most evaluated configurations.
Figures & tables
Figure 1: A recorded transition links an action to checked before-and-after UI evidence. The illustrative add-to-cart action connects the selected jasmine milk tea and quantity to the resulting cart state. The lower panels organize evidence into a graph and text template for reuse decisions.
Figure 2: A changed request is matched to a candidate transition through task semantics, UI structure, and live grounding. In the illustrative milk-tea task, the current request supplies quantity 2. The controller retrieves a compatible app subgraph, binds the current slots, and checks the live target before admitting a local action or falling back to the model.
Figure 3: Replay proceeds through individually checked transitions. Left: live context and contract checks determine whether to reuse, rewrite, or reject a candidate. Right: the green branch illustrates local rewriting; the red rejected edge is not executed, and fallback provides a new observation for realignment. Admitted actions execute once and undergo a post-check before the next local decision.
Model
Original success score
Replay successful rate
Success score with replay
Replay rate
Token ↓ (%)
LLM steps ↓ (%)
Execution speedup
AndroidWorld
GUI-Owl-7B
59.1
97.7
57.7
87.5
89.6
79.8
1.7 ×
MAI-UI-8B
66.4
95.5
63.4
86.4
78.3
72.5
1.9 ×
GELab-Zero-4B
71.7
94.5
67.8
85.6
78.0
75.8
1.5 ×
AutoGLM-Phone-9B
51.0
95.9
48.9
83.4
89.0
76.4
1.4 ×
UI-TARS-1.5-7B
21.0
94.0
19.7
82.0
79.2
71.1
1.2 ×
Table 1: AndroidWorld and real-world results for five base agents. Success, Replay successful rate, replay, token reduction, and LLM-step reduction are percentages (higher is better); execution-time speedup is a multiplier.
Change source
Category Implication for trace reuse
Environment changes
Background-state changes Check the live state and preserve satisfied goals; avoid duplicate or inverse actions. Layout and workflow changes Re-ground displaced targets and reject paths invalidated by a changed workflow. Modal interruptions Detect blocking overlays and reassess which actions remain executable.
Instruction changes
Parameter changes Bind current quantities, times, or other values and verify the resulting state. Entity substitutions Resolve the requested product, contact, or destination in the current interface. Goal-expression changes Retrieve procedures across paraphrases; require supporting evidence for contextual references.
Table 2: Two sources and six categories of variation in real-world phone use. Ablations examine background-state and parameter changes, and paraphrases within goal-expression changes.
Figure 4: The full controller improves task success over replay only across all five agents under background-state changes, parameter changes, and paraphrased instructions. Each model group has four configurations in blue shades darkening from left to right, followed by PreAct in orange, with matching legend swatches below each panel. The vertical scale starts at 25%. Component additions are cumulative across the blue bars. Model abbreviations refer to the five agents in Table 1 .
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Field group
Content and role
Record identity
Record/episode ID, instruction, application, environment, and links to the source trajectory. These identify the execution from which an edge was extracted.
State evidence
Before/after screenshots, UI tree when available, foreground application/window, and observable state attributes needed by the contract. Missing metadata is distinguished from a negative observation.
Action and selector
Action type and payload, semantic target description, and available selector evidence, such as text, role, resource identifier, or bounds. Historical bounds alone do not establish a live match.
Procedure and slots
Procedure intent g ; typed slots k with recorded values, live binding sources, and constraints. Values and entity identities remain explicit.
Checks and outcome
Preconditions ϕ− ; expected effect ϕ+ ; observed check result; progress/completion evidence; and any truncation or failure reason.
Risk and provenance
Risk r , source record/step IDs, and links to evidence supporting admission or rejection.
Appendix
Table 3: Logical fields of a recorded transition and their roles in selective replay.
Contract field
Example value
Provenance
Illustrative record timer-record , duration-entry step.
vi , vj
Timer editor before entry; timer editor displaying the accepted duration after entry.
g , a , s
Set duration; enter a duration value; live editable duration control identified from its label/role and current state.
k
duration : positive duration; recorded value 600 seconds; live value 900 seconds, explicitly bound from the instruction.
r
Reversible local edit; this edge does not start the timer or perform an external transaction.
ϕ−
Correct timer editor is active, no blocking window is present, and the duration control is editable and unambiguously grounded.
Appendix
Table 4: The transition contract specifies how to rewrite a timer duration from 10 to 15 minutes using the live instruction, with explicit grounding, preconditions, postconditions, and fallback.
Condition
C1: first addition
C2: additional component
Background state
State recheck / TOCTOU-aware replay
Goal preservation: detect an already satisfied goal.
Parameter change
Parameter generalization
Instruction–outcome agreement: check the requested value.
Paraphrase
App-level semantic retrieval
Soft task matching: associate wording with a stored procedure.
Appendix
Table 5: Cumulative component configurations. C0 uses replay only; C1 and C2 add the listed mechanisms without model fallback, and C2 retains the C1 addition. C3 uses the full controller with base-model fallback and includes semantic routing in the paraphrase comparison.
Google Chrome, Microsoft Edge, Quark, Baidu, Google, Bing
Appendix
Table 6: Applications included in real-world testing, grouped by usage category. Names are given in English or romanized product names. This inventory documents coverage rather than per-application success rates or a balanced application-level benchmark.
Application
English task description
Taobao
Add the specified smartphone, Smartphone A, to the cart.
Taobao
Find the best-selling jacket in the requested category priced between CNY 100 and CNY 200 for purchase.
Ctrip
Check hotel prices in Destination A for a two-night stay with the specified check-in and check-out dates.
Taobao Instant Commerce
Find a kumquat–lemon drink and add one cup to the cart.
Xiaohongshu
View the latest post by Creator A.
Taobao
Search for Store A, open the first matching store, search within it for Product B, select the default configuration, and add the product to the cart.
Appendix
Table 7: Neutralized task descriptions drawn from real-device testing. Aliases replace identifying or preference-specific details; rows describe tasks rather than their execution outcomes.
Condition
Replay
Token ↓
LLM steps ↓
Speedup
AndroidWorld
82.0–87.5
78.0–89.6
71.1–79.8
1.2–1.9 ×
Background-state changes
72.6–78.0
65.4–78.9
80.6–88.8
1.9–3.6 ×
Parameter changes
70.7–79.8
68.3–78.7
73.1–85.8
1.8–3.5 ×
Paraphrased instructions
73.2–79.2
60.8–79.6
76.0–86.8
2.9–3.9 ×
Appendix
Table 8: Execution-efficiency ranges across five base agents. Replay, token reduction, and LLM-step reduction are percentages; speedup is a multiplier.
Memory-augmented mobile GUI agents store successful execution trajectories and reuse them in later tasks, but a stored trajectory rarely matches a new task exactly. The new task may use different parameters, share only some of its steps with a stored trajectory, or have no relevant record in memory. Forcing the agent to use irrelevant memory can mislead it, whereas discarding memory that may still be useful deprives it of guidance from past experience. To address this dilemma, we propose DeltaReplay, a step-level memory reuse framework that decides how to use existing memory without modifying it. We observe that the reusable part of a stored record is determined not by the record itself but by its relation to the new task, mainly through two factors: page-level consistency and action-level generality. We therefore store execution trajectories as paths in a transition graph, whose nodes (pages) and edges (actions between pages) capture these two factors. At reuse time, the action on each edge is split into a task-independent operation and task-specific parameters. DeltaReplay then compares each recorded step with the new task and the current screen, and decides whether to follow it, execute it after replacing its parameters, or leave it to the base agent. On AndroidWorld and SPA-Bench, DeltaReplay improves the task success rate over a base agent with the same backbone by up to 10.3 and 25.0 percentage points, respectively. These results indicate that deciding at each step how to use retrieved memory lets agents benefit even from partially matching trajectories.
Running GUI agents on edge devices can keep sensitive screens and interaction histories local, but the computational cost of inference at every action step makes deployment challenging. Existing GUI agent systems either perform full vision-language model (VLM) inference at each action step or reuse coarse-grained knowledge matched to prior tasks. However, dynamic mobile environments and user tasks make it difficult to fully utilize prior task executions without additional fine-tuning or task-specific offline exploration. To address this challenge, we present PastForward, a system that accelerates GUI agents through validated, fine-grained reuse of computational experience accumulated during ordinary task execution. During decoding, PastForward retrieves prior output sequences as device-adaptive multi-token proposals and verifies them in a single VLM forward pass. Across action steps, it uses prior GUI transitions to begin next-step inference while the device executes the current action, retains the early computation only when the predicted screen matches the observed screen, and carries reusable KV states forward. We evaluate PastForward on AndroidWorld workloads derived from real mobile usage patterns using multiple VLM backbones across server and edge platforms. On device, PastForward achieves action-step latency speedups of 1.63-2.36× while maintaining task success rates.
Modern GUI agents typically rely on a model-centric and step-wise interaction paradigm, where LLMs must re-interpret the UI and re-decide actions at every screen, which is fragile in long-horizon tasks. In this paper, we propose Executable Agentic Memory (EAM), a structured Knowledge Graph (KG) that shifts GUI planning from free-form generation to a robust retrieval-and-execution process. Our approach includes a sample-efficient memory construction pipeline using state-aware DFS and action-group mining to compress multi-step routines. To ensure efficient planning, we introduce a value-guided graph search where a lightweight Q-function model steers Monte Carlo Tree Search (MCTS) over the KG. We theoretically establish bias-consistency for the Q-model and derive sample complexity bounds for path recovery. Empirically, EAM outperforms state-of-the-art baselines like UI-TARS-7B by up to 19.6% on AndroidWorld, while reducing token costs 6× relative to GPT-4o. With a 2.8s average latency, EAM enables reliable, quick, and long-horizon GUI automation.
Zerui Qin, Sheng Yue, Xingyuan Hua +2
1Tsinghua University, China · 2Sun Yat-sen University, China