PaperlayerView exact revision on arXiv

Source-linked AI summary

DeltaReplay: Task-Relative Memory Reuse for Mobile GUI Agents

Yudong Bai, Yihong Chen, Quanming Yao, Yaqing Wang

arXiv:2610.11707v1cs.AI

TL;DR

Stored GUI trajectories often only partly fit new tasks, creating a need to distinguish usable steps from mismatched ones. DeltaReplay routes each step to replay, parameter re-grounding, or the base agent. It improves success over same-backbone agents on AndroidWorld and SPA-Bench.

  • Problem

    Stored GUI trajectories may use different parameters, overlap with a new task only partly, or be irrelevant, so each retrieved step may call for a different use.

    Source: §1 · p. 1

  • Method

    DeltaReplay stores trajectories as transition-graph paths and decides per step whether to replay an action, replace its task-specific parameters, or leave it to the base agent.

    Source: §1 · p. 2

  • Results

    7.8–10.3 and 16.6–25.0 percentage points: DeltaReplay improves task success over same-backbone agents on AndroidWorld and SPA-Bench, respectively.

    Source: §1 · p. 2

  • Takeaways & Limitations

    On AndroidWorld and SPA-Bench, deciding how to use memory at each step lets agents benefit from partially matching trajectories.

    Source: §6 · p. 9

    Records are retrieved by benchmark task identifiers, while retrieving them from instructions alone is left to future work.

    Source: §6 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

Stored GUI trajectories often only partly fit new tasks, so agents must decide which steps to replay, re-ground, or leave unused. DeltaReplay makes that choice step by step, improving success over same-backbone agents on both benchmarks.

1 INTRODUCTION

  • New tasks may differ in parameters, share only some stored steps, or encounter screens changed by app updates, making retrieved steps variably suitable.Figure 1 illustrates shared initial steps, a changed value, and differing later steps.Source: §1 · p. 1, Figure 1 · p. 3
  • Existing methods use or discard retrieved memory as a whole, although a record’s steps can vary in usefulness for the new task and current screen.This creates slow reuse, over-discarding of partly usable records, and misuse of inapplicable memory.Source: §1 · pp. 1–2
  • DeltaReplay stores trajectories as transition-graph paths and splits each recorded action into a task-independent operation and task-specific parameters.At each step it chooses among replay, re-grounding with current-task parameters, and leaving the step to the base agent.Source: §1 · p. 2
  • 7.8–10.3 and 16.6–25.0 percentage points: DeltaReplay improves task success over same-backbone agents on AndroidWorld and SPA-Bench, respectively.It also outperforms two memory baselines on AndroidWorld, cuts per-step latency by up to 57% when tasks are already in memory, and shows no measurable loss when memory does not apply.Source: §1 · p. 2

2 RELATED WORK

Prior GUI-agent memory work varies in what it stores and how retrieved experience enters decisions, but generally uses memories or predefined units as wholes. DeltaReplay instead evaluates whether individual recorded steps fit the new task.

2 RELATED WORK

  • GUI-agent memory research stores varied forms of experience, while retrieved memories are usually placed in context or executed as a whole rather than judged step by step for fit.MAGNET separates stable UI-element functions from changing appearances when memory is built, with retrieved elements and workflows serving as prompt references.Source: §2 · p. 3
  • Memory-as-context methods leave selection of usable parts to the model, while memory-execution methods operate on whole memories or predefined units.Examples include shortcut arguments, high-level actions, subtask replay, and executable paths with parameter replacement.Source: §2 · pp. 3–4
  • Unlike approaches that repair records before reuse, DeltaReplay keeps records fixed and decides at each step which recorded actions still hold.Prior app-graph and GUI-testing approaches repair or re-explore records after app changes, requiring extra device interactions and model calls.Source: §2 · p. 4

3 PROBLEM FORMULATION

The problem formulation treats memory reuse as a per-step decision based on whether a retrieved action can be executed as recorded and whether it advances the current task. These properties determine whether to execute, use memory as guidance, or ignore it.

3 PROBLEM FORMULATION

  • At each step, the agent observes the screenshot, parsed UI tree, and actionable elements, then forms a decision context from the instruction, action history, screen, and executable actions.The base policy acts without memory, while memory is a read-only graph of successful-run paths whose edges are recorded steps.Source: §3 · p. 4
  • Executability identifies the current action that realizes a recorded step as-is, while applicability indicates whether its operation advances the current task on the current screen.A step is not executable as recorded if no current action realizes it or if it would enter differing old-task parameters.Source: §3 · p. 4
  • Direct steps are executed, partial steps guide selection of a new action, and inapplicable steps are ignored; DeltaReplay estimates these unobserved properties at every step.Partial steps with old-task parameters are re-grounded, while steps whose recorded targets are missing are left to the base agent.Source: §3 · p. 4

4 DELTAREPLAY

DeltaReplay represents recorded runs as paths in a transition graph and evaluates memory step by step against the current task and screen. It chooses whether to replay, re-ground, or leave a step to the base agent.

4.1 MEMORY AS A TRANSITION GRAPH

  • Recorded runs form graph paths whose nodes store screenshots and UI trees, while edges separate reusable operations from task-specific parameters.The parameter split determines how far each action generalizes.Source: §4.1 · pp. 4–5

4.2 STRUCTURAL MATCHING: CAN THE STEP BE EXECUTED AS RECORDED?

  • Structural matching compares the current screen with a tracked recorded page and maps the recorded target by structural context rather than element index.A step carrying old-task parameters is not executed as recorded; if target mapping fails, the base agent acts.Source: §4.2 · p. 5

4.3 SEMANTIC MATCHING: DOES THE STEP APPLY?

  • When no recorded position matches the current screen, semantic matching selects among candidate steps whose recorded screens match, with an option to reject them all.Same-task or same-template records can resume path following; borrowed records are searched again at every step.Source: §4.3 · p. 6

4.4 THREE ROUTES

  • Route A replays a mapped step without old-task parameters, while Route B replaces old parameters using aligned task descriptions and the current screen.If alignment fails or multiple elements match the new label, Adapt abstains and the base agent performs the step.Source: §4.4 · p. 6
  • Route C gives the step to the base agent after memory is rejected, mapping fails, or adaptation abstains.If the base agent's action matches the next recorded step, the path position can still advance for later reuse.Source: §4.4 · p. 6
  • All routes return an action tied to the current screen, and replayed or re-grounded steps are not repeated on an unchanged screen.Selectedge and the base policy use prompted backbone calls; Adapt uses rules, and nothing is trained.Source: §4.4 · p. 6

5 EXPERIMENTS

The experiments test DeltaReplay against same-backbone base agents and memory baselines, examine how gains vary with memory coverage, assess routed-step correctness, and ablate routing decisions. DeltaReplay improves overall success on both benchmarks, while coverage-specific results and ablations probe when memory helps and which safeguards matter.

5.1 SETUP

  • Evaluation covers 116 AndroidWorld task templates and 60 SPA-Bench tasks, with memory drawn from successful base-agent runs and groups defined by the closest available record.Each task is run once per method; the authors treat differences of about one task per group or 2–4 s per step as within run-to-run variation.Source: §5.1 · p. 7

5.2 MAIN RESULTS (RQ1)

  • DeltaReplay raises success over same-backbone base agents by 10.3 (Qwen3-VL-30B) and 7.8 points (Qwen3.8-Flash) on AndroidWorld, and 25.0 and 16.6 points on SPA-Bench.It also exceeds two memory baselines on AndroidWorld; with Qwen3.8-Flash, AndroidWorld latency is 19.7 s versus 24.8 s per step for its base agent.Source: Table 2 · p. 8, §5.2 · p. 8

5.3 RESULTS BY MEMORY COVERAGE (RQ2)

  • On AndroidWorld tasks with same-task or same-template memory, Qwen3.8-Flash success rises from 80.0% to 90.0% and from 63.6% to 86.4%, respectively.For same-template tasks, GUI-explorer also reaches 86.4% but takes 15.9–32.2 s per step; Qwen3-VL-30B same-template latency rises from 7.8 s to 10.4 s.Source: §5.3 · p. 8
  • For 15 SPA-Bench same-family tasks whose record shares only the first steps, neither base agent succeeds, while DeltaReplay reaches 33.3% and 46.7%.The tasks are grouped by closest record, and the authors report each group separately because memory coverage correlates with task difficulty.Source: §5.1 · p. 7, §5.3 · p. 8

5.5 ABLATIONS (RQ4)

  • Unchecked verbatim replay solves only 9.1% of same-template tasks; removing Route C and the screen check lowers success below the base agent.The full system uses 1.00 model calls per step on same-template tasks, versus 2.11 for the base agent.Source: Table 4 · p. 9, §5.5 · p. 9

5.3 RESULTS BY MEMORY COVERAGE (RQ2)

  • When memory contains only other same-app tasks or no record from the app, DeltaReplay stays at or above its base agent, while prompting baselines fall below it.On SPA-Bench, DeltaReplay gains 11.1 points with each backbone on tasks without a family record, including cases where other families from the same app are in memory.Source: §5.3 · p. 9

5.4 ROUTE USAGE AND STEP CORRECTNESS (RQ3)

  • Replay takes 56.1% of steps with same-task memory and 41.5% with same-template memory, while parameter adaptation and borrowed steps use Route B in other coverage groups.A blind LLM judge labeled 150 steps; Route A and B precision was 83.7% and 78.0% versus 75.5% for Route C, with differences within sampling error.Source: §5.4 · p. 9

6 CONCLUSION AND LIMITATIONS

DeltaReplay selects per-step whether to replay, re-ground, or discard memory; the paper reports improved success on both benchmarks and describes limitations in task retrieval, parameter adaptation, app-version coverage, and evaluation.

6 CONCLUSION AND LIMITATIONS

  • App-version changes, instruction-implied values, and task-ID-based retrieval constrain when recorded steps can be reused or found.The evaluation does not vary app versions; instruction-implied values such as “tomorrow” are left to the base agent, and instruction-only retrieval is left to future work.Source: §6 · p. 10
  • On AndroidWorld and SPA-Bench, per-step memory routing improves success over same-backbone base agents, can speed tasks covered by memory, and avoids prompting-based memory losses when memory does not fit.The paper also reports using generative AI tools throughout the work and says the authors reviewed the AI-assisted work and take responsibility for the final content.Source: AI USE STATEMENT · p. 11
  • The study uses benchmark tasks without human subjects, and recommends user confirmation for sensitive actions, action logging, and avoiding private-data storage without consent.SPA-Bench runs use the authors’ own app accounts; recorded screens that may show account data are not released.Source: ETHICS STATEMENT · p. 11
  • Section 4 and Algorithm 1 specify the method, while the appendices document implementation, prompts, task sets, baselines, ablations, route statistics, and annotation.Ancillary files contain code, full prompts, and benchmark task lists.Source: REPRODUCIBILITY STATEMENT · p. 11

A ROUTING ALGORITHM

  • Algorithm 1 checks the tracked screen position, searches semantically when needed, then verifies or adapts a matching edge; otherwise, it falls back to the base policy.Borrowed parameter-bearing steps are not reused, while a base-agent action matching the next recorded step can advance the tracked position.Source: A ROUTING ALGORITHM · p. 16

B IMPLEMENTATION DETAILS

The implementation stores successful runs as paths in a frozen graph and compares screens to decide which recorded steps can be reused. The prompts guide the selector and base agent in choosing the next action from current candidates.

B IMPLEMENTATION DETAILS

  • Successful runs are stored as paths in a frozen, read-only graph whose nodes hold screen descriptions and screenshots, and whose edges hold actions and task identity.Task identity comes from benchmark identifiers for the task, template or family, and app.Source: B IMPLEMENTATION DETAILS · p. 16
  • Screen matching combines text-embedding cosine similarity, widget-structure overlap, and fuzzy text similarity, with looser thresholds for tracked steps than for finding a new position.A screen matches if cosine and structural scores both reach threshold, or fuzzy matching is at least 80; thresholds are 0.60/0.70 while following and 0.65/0.80 when searching.Source: B IMPLEMENTATION DETAILS · p. 16
  • When no recorded position matches, the selector considers at most eight candidate steps and can reject them all, after which the base agent acts on the same candidate set.Episodes end after max(8, ⌈3 nref⌉) steps and AndroidWorld episodes are capped at 15 minutes; reported latency excludes device time.Source: B IMPLEMENTATION DETAILS · p. 16

C PROMPTS

  • The selector prompt presents recorded steps from the current screen and asks for the correct next step given action history, including rejecting candidates that would repeat or skip progress.Its candidate lines include recorded position, action type, target text, arguments, and screen text.Source: C PROMPTS · pp. 17–18
  • For same-task, same-template, easier-family, and same-app records, the selector prompt distinguishes which recorded values or endings may be reused and when candidates must be rejected.The base-agent prompt asks it to choose one candidate that best advances the goal using visible evidence, while avoiding unproductive repeats and closing blocking overlays.Source: C PROMPTS · p. 17

D BENCHMARKS AND MEMORY CONSTRUCTION

The evaluation uses AndroidWorld-116 and a selected 60-task SPA-Bench subset, with memory built from successful base-agent runs. It compares DeltaReplay with base-agent and memory-augmented baselines under benchmark-specific coverage and scoring procedures.

D BENCHMARKS AND MEMORY CONSTRUCTION

  • AndroidWorld-116 contains one test instance per 116 templates, with frozen memory from 42 successful runs across 42 templates and coverage groups defined by the closest available record.Same-task and same-template groups include only templates solved by the base agent at least once.Source: D BENCHMARKS AND MEMORY CONSTRUCTION · p. 18
  • SPA-Bench-60 is a fixed-seed sample of 60 tasks selected after exclusions, with coverage groups based on same-task, easier-family, or no-family records.Of the 33 tasks in the latter two groups, 32 were failed by both backbones when memory was built, so their base-agent success rate is low by construction.Source: D BENCHMARKS AND MEMORY CONSTRUCTION · p. 18
  • Both benchmarks use a single-app evaluator with PaddleOCR and Qwen3.8-Flash, while AndroidWorld rule-based checkers are not used for scoring.The checkers cannot score 41 AndroidWorld tasks; on the other 75, they agree with study success labels on 91.5% (248/271) of specified episodes.Source: D BENCHMARKS AND MEMORY CONSTRUCTION · p. 18

E BASELINES

  • The base-agent baseline uses DeltaReplay’s backbone, prompts, and candidate-action interface without memory or the repeat guard.Source: E BASELINES · p. 20
  • The memory baselines add retrieved records or mined transition knowledge to the Qwen3.8-Flash prompt, using the same frozen memory as DeltaReplay.RAG-prompting adds records at every step; GUI-explorer ranks recorded entries by page-text and task similarity and presents the top five.Source: E BASELINES · p. 20

F ABLATION VARIANTS

The ablation variants remove or alter DeltaReplay’s routes and matching checks, while the route-statistics table reports the share of executed steps taken by each route across AndroidWorld coverage groups.

F ABLATION VARIANTS

  • The ablations compare the full method with naive replay, removal of Route C, and removal of semantic matching, using Qwen3.8-Flash and fixed task-set denominators.The same-template ablations use 22 tasks, and the same-app ablation uses the first 30 of 48 same-app tasks.Source: F ABLATION VARIANTS · p. 20

G ROUTE STATISTICS

  • Table 7 reports each route’s share of executed steps by AndroidWorld-116 coverage group.Same-app borrowed steps count as Route B because only their operation is reused; treating them as Route A would shift 10.1% of same-app steps.Source: Table 7 · p. 21, G ROUTE STATISTICS · p. 21

H STEP-LEVEL ANNOTATION PROTOCOL

The annotation protocol samples executed steps across DeltaReplay’s three routes and has a blind annotator judge whether each action is correct, incorrect, or unclear.

H STEP-LEVEL ANNOTATION PROTOCOL

  • 150 executed steps were sampled, with 50 per route and at most four steps per task for Routes A and B and two for Route C.The sample came from DeltaReplay using Qwen3.8-Flash on AndroidWorld.Source: H STEP-LEVEL ANNOTATION PROTOCOL · p. 21
  • The annotator was blind to route and saw the goal, marked target, before-and-after screens, and action when judging each step.Labels were correct, incorrect, or unclear; incorrect steps were divided into no-ops and harmful actions.Source: H STEP-LEVEL ANNOTATION PROTOCOL · p. 21
  • Precision is correct steps divided by judged steps, and Route B combines parameter-adapted replays with steps borrowed from another task’s record.The Route B sample included 20 parameter-adapted steps, 19 correct, and 30 borrowed steps, 20 correct.Source: H STEP-LEVEL ANNOTATION PROTOCOL · p. 21, Table 8 · p. 21

I PAIRED COMPARISON

The paired comparison covers 42 AndroidWorld tasks whose template is in memory and contrasts DeltaReplay with the Qwen3.8-Flash base agent task by task.

I PAIRED COMPARISON

  • +16.7 percentage points separated DeltaReplay-only successes from base-agent-only successes on the 42 paired tasks.The base agent alone solved 1 task, while DeltaReplay alone solved 8.Source: I PAIRED COMPARISON · p. 21
  • The paired comparison had 9 discordant tasks, with one solved only by the base agent and eight only by DeltaReplay.Under equal success, the discordant outcomes were modeled as Binomial(9, 1/2).Source: I PAIRED COMPARISON · p. 21
  • An exact two-sided McNemar test was used to assess the paired success difference.The supplied passage states the test but does not provide a complete p-value.Source: I PAIRED COMPARISON · p. 21

J WHEN IS ROUTE-BASED REUSE SAFE?

The analysis gives local sufficient conditions for a re-grounded step to preserve its recorded semantic successor and bounds negative transfer when the agent can discard a match.

J WHEN IS ROUTE-BASED REUSE SAFE?

  • A transition-consistent shift preserves the semantic states before and after a recorded step and makes the shifted action transition commute with the shift.The analysis concerns one recorded step and does not require the recorded and current UI graphs to be isomorphic.Source: J WHEN IS ROUTE-BASED REUSE SAFE? · pp. 21–22
  • Under transition consistency, re-grounding the recorded action in the shifted current state reaches the recorded semantic successor.This is a sufficient condition for transfer from a local correspondence.Source: J WHEN IS ROUTE-BASED REUSE SAFE? · p. 22
  • Route A reuses the recorded action as-is, whereas Route B re-grounds it after changing its task-specific parameters.Route B applies when the action’s parameters shift, so the recorded action cannot simply be copied.Source: J WHEN IS ROUTE-BASED REUSE SAFE? · p. 22
  • With per-step utility in [0, 1], the routed policy’s utility difference is bounded below by p g − δ.Here p is the probability of a correct accepted match, g its conditional gain over the base policy, and δ the probability of an incorrect accepted match.Source: J WHEN IS ROUTE-BASED REUSE SAFE? · p. 22
  • When correct matches do not hurt, negative transfer is bounded by the false-acceptance rate, but the sufficient conditions are not guaranteed by the prompted modules.The analysis identifies executable grounding and a low false-acceptance rate as testable requirements.Source: J WHEN IS ROUTE-BASED REUSE SAFE? · p. 22

Related papers

Loading 2610.11707v1…