PaperlayerView exact revision on arXiv

Source-linked AI summary

REBASE: Device-Cloud Experience Coherence for GUI Agents Across App Updates

Beining Wu, Jun Huang, Yanxiao Zhao

arXiv:2609.32130v1cs.DC

TL;DR

App updates can silently invalidate cached GUI-agent paths, and stale experience performs worse than having none. REBASE coordinates device and cloud copies through replay, verification, and staged, version-keyed repair; on two Jetson devices it restores stale experience to fresh experience’s success rate within one episode, with lower upload and device-energy costs than the stated baselines.

Abstract

from arXiv · show

A graphical user interface (GUI) agent that ships on a phone runs a small model and reuses experience: action paths recorded on earlier runs and cached from the cloud. When an app updates, part of this experience becomes silently wrong. On nine real app version pairs, an agent carrying experience recorded on the old version succeeds 10.1 points less often than one carrying none, and it does not notice the mismatch until 3 steps after acting on it. We propose REBASE, a protocol that keeps the device copy and the cloud copy of the experience coherent across updates. When a version changes, the cloud replays its copy on the new version and the device verifies each recorded step before executing it; when a step still fails, the device sends the cloud evidence in increasing size, starting from an accessibility-subtree diff, until the cloud re-derives an executable patch, keyed by version so that one repair serves the whole fleet. On two Jetson devices, REBASE restores the success rate of stale experience to that of fresh experience recorded on the new version within one episode, at 708x fewer bytes and 47.3x fewer cloud calls than uploading screenshots to the cloud, and 2.5x less device energy than running without experience.

I. INTRODUCTION

App updates can silently invalidate cached GUI-agent experience, while existing device–cloud and memory systems leave post-update experience repair unresolved. REBASE coordinates device and cloud copies across updates, using replay, verification, and staged evidence to restore stale experience efficiently.

I. INTRODUCTION

  • Stale experience succeeds 10.1 points less often than no experience, and broken steps remain walkable in 62.2% of executions, delaying mismatch detection by 3 steps.Device–cloud systems focus on completing current tasks, while experience and memory systems treat apps as fixed; the post-update evidence and timing question remains open [3]–[15].Source: §I · p. 1
  • REBASE treats an app update as a coherence event: the cloud replays experience on the new version, the device verifies steps before execution, and failures trigger evidence escalation until the cloud derives a patch.Evidence grows from a fingerprint and accessibility-subtree diff to a screenshot only when smaller evidence fails.Source: §I · p. 1
  • REBASE uses a two-clock protocol and version-keyed repairs, so one cloud re-derivation can serve devices reporting the same update-broken experience.The paper also reports 80.0× fewer re-derivations than without version keys in a trace-driven fleet of 100 devices.Source: §I · p. 1
  • On two Jetson devices and nine Android apps, REBASE restores stale experience to fresh experience’s success rate within one episode, using 708× fewer bytes and 47.3× fewer cloud calls than screenshot upload.It also uses 2.5× less device energy than running without experience.Source: §I · p. 1

II. BACKGROUND AND OBSERVATIONS

GUI-agent experience consists of executable paths tied to accessibility elements, with cloud and device copies that can diverge when an app updates. Across nine real version pairs, stale paths reduce success and can fail silently.

A. Device and Cloud Copies of GUI Experience

  • Experience comprises executable paths bound to accessibility-tree elements, with each step fingerprinting an element’s role, label, and position; the cloud consolidates paths and the device caches a copy.The copies agree until an app update, and experience recorded on one version is stale when walked on the next.Source: A. Device and Cloud Copies of GUI… · p. 2

B. Observation: Silent Failure of Stale Experience

  • Stale experience lowers success by 10.1 points relative to no experience; update-broken steps remain walkable in 62.2% of executions, delaying detection by 3 steps.Figure 1’s left panel compares success on new versions across nine apps for no experience and old-version experience.Source: B. Observation: Silent Failure of… · p. 2, Figure 1 · p. 2
  • Relayouts, renames, reflows, and policy updates can break paths; a still-walkable broken step may produce the wrong screen, so the agent continues until a later element is missing or the episode ends.Mean success loss ranges from −8.4 points for relayouts to −12.7 for policy updates; fresh experience raises success by 45.6 points over no experience.Source: B. Observation: Silent Failure of… · p. 2

C. Observation: Repair Value of Accessibility-Subtree Diffs

Accessibility-subtree diffs repair most failing steps by isolating changed elements around the broken one. Larger evidence adds comparatively little repair value while requiring substantially more bytes.

C. Observation: Repair Value of Accessibility-Subtree Diffs

  • 79.1% of failing steps are repaired with an accessibility-subtree diff; a screenshot adds only 9.4 points at 36.6× the per-step median bytes.The result is reported as Observation 2.Source: C. Observation: Repair Value of… · p. 2
  • A fingerprint repairs 27.4%, while an 8.0 KB accessibility-subtree diff raises the repair rate to 79.1%.An element crop, 298 KB screenshot, and complete trajectory each add about 9.4 points; the diff is the evidence knee for four of six apps, while the crop is the knee for two.Source: C. Observation: Repair Value of… · p. 2
  • The diff isolates changed elements and places the recorded element in its new neighborhood, helping the model relocate it; screenshots cost a median 36.6× more bytes and do not identify changed elements.Trajectory history adds information unused by relocation; these observations motivate update-time replay and verification, followed by failure-triggered evidence escalation.Source: C. Observation: Repair Value of… · p. 2

A. Overview and Problem Formulation

REBASE coordinates device and cloud experience around app updates, using replay and step verification to identify broken paths. Its design selects repair evidence and update-time pushes to favor autonomous success within the first K episodes.

A. Overview and Problem Formulation

  • The device agent runs a small model over cached paths, while the cloud maintains experience and the gateway monitors releases and indexes events by version key.The device and cloud copies agree until an app update; either side may see the new version first.Source: A. Overview and Problem Formulation · p. 2
  • A path applies actions to elements identified by fingerprints containing role, text label, normalized box, and a two-ancestor hash.Fingerprint matching compares role and hash, label edit distance, and box displacement under thresholds.Source: A. Overview and Problem Formulation · p. 2
  • Verification passes only when the step’s element exists on the updated screen and the resulting screen matches its recorded successor; D contains each path’s first failing step.A stale-but-walkable step passes the element match but fails the successor-screen check.Source: A. Overview and Problem Formulation · p. 3
  • REBASE selects evidence levels and an update-time push set to maximize autonomous success over the first K episodes, subject to byte and energy budgets.The recovery index Tr is zero if all episodes succeed, records the last failed episode when recovery occurs by K, and is K + 1 otherwise.Source: A. Overview and Problem Formulation · p. 3

B. Cloud Replay and On-Device Verification

When the cloud can obtain the updated app, it replays cached paths on a virtual device and precomputes patches. The device verifies paths that were not replayed before continuing execution.

B. Cloud Replay and On-Device Verification

  • 86.7% of consolidated paths are replayable on the cloud’s virtual device; paths blocked by login, payment, or device state remain for device verification.Replay stops at the first failed verification without a model call.Source: B. Cloud Replay and On-Device… · p. 3
  • For each replayable path, the gateway re-derives and stores a patch, pushes a per-path bit and step index, then serves patches on demand.Patches are stored in the updated version’s patch set.Source: B. Cloud Replay and On-Device… · p. 3
  • If an update precedes the push or replay was unavailable, the device marks paths unverified and checks each step before and after acting; a mismatch raises an event.A stale-but-walkable step therefore costs one action rather than the longer detection lag described for the original failure mode.Source: B. Cloud Replay and On-Device… · p. 3

C. Staged Evidence and Patch Return

On a verification failure, REBASE escalates evidence from a fingerprint and failing step through an accessibility-subtree diff to image evidence. The cloud tests a derived patch on a virtual device and returns a successful repair for reuse.

C. Staged Evidence and Patch Return

  • The failure clock sends the smallest evidence first, escalating only when the re-derivation operator returns no patch.Evidence levels progress from fingerprint and failing step to subtree diff, low-resolution crop, and screenshot, in increasing byte size.Source: C. Staged Evidence and Patch Return · pp. 3–4
  • The cloud proposes candidate elements and tests each step on a virtual device, committing a successful patch under the app-and-version key.The first successful evidence level resolves the event.Source: C. Staged Evidence and Patch Return · pp. 3–4
  • Past the knee, crops or screenshots add about 9.4 points at a multiple of the diff’s bytes, so the ladder closes most events at ξ0 or ξ1.The ladder reaches screenshot evidence when earlier levels fail and returns to the small model if every level fails.Source: C. Staged Evidence and Patch Return · pp. 3–4
  • A patch replaces the failed path segment from step k, and the executor replays its actions so the on-device model can apply the repair and continue.The returned patch is applied in place.Source: C. Staged Evidence and Patch Return · p. 4

D. Version Keys and Fleet Deduplication

REBASE keys repairs by app, updated version, and failing fingerprint so one cloud re-derivation can serve devices encountering the same broken step.

D. Version Keys and Fleet Deduplication

  • The version key κ = (α, v′, f) identifies an event using the app, updated version, and failing fingerprint.The first report of a key triggers one re-derivation; later reports receive the stored patch.Source: D. Version Keys and Fleet Deduplication · p. 4
  • For Nκ devices reporting the same key, the cloud re-derives once rather than once per report, and serves the repair from P(v′).The keyed re-derivation count is bounded by the number of distinct update-broken fingerprints.Source: D. Version Keys and Fleet Deduplication · p. 4
  • Keyed re-derivation depends on distinct update-broken fingerprints, not fleet size.Without the key, re-derivations scale with the number of devices reporting each broken fingerprint.Source: D. Version Keys and Fleet Deduplication · p. 4

E. Coverage and Fallbacks

REBASE retains device verification and failure-time repair when cloud replay is unavailable, while the testbed covers nine Android apps across paired releases on Jetson devices. The setup also measures device activity and includes three release pairs hidden from the cloud.

E. Coverage and Fallbacks

  • When a screen lacks an accessibility tree, the evidence ladder skips the subtree diff; paths unavailable to cloud replay still retain device verification and the failure clock.Every measured failure in the nine apps exposed a subtree, and returned patches are confirmed through the next verified step.Source: E. Coverage and Fallbacks · p. 4
  • Figure 3 depicts two walked-path screens, the devices, and the testbed topology.Source: Figure 3 · p. 4

IV. IMPLEMENTATION AND TESTBED

  • The testbed uses two Orin boards running a quantized 8B model against Android 13 environments hosted on a Thor gateway, with cloud inference and shaped uplinks.Link tiers vary bandwidth and round-trip time.Source: §IV · p. 4
  • Measurements record screenshots, accessibility forests, screen hashes, evaluator verdicts, bytes, and power traces; device energy subtracts session idle power from three sampled rails.Byte counts cover gzipped JSON and encoded images at the application layer.Source: §IV · p. 4
  • Nine apps pair AndroidWorld-pinned versions with later F-Droid releases that change an accessibility tree along a recorded path; three pairs hide the new release from the cloud.The Thor hosts the virtual device, release watcher, and fleet index, and joins the fleet experiment as a third device.Source: §IV · p. 4

V. EVALUATION

REBASE raises stale-experience success and matches fresh-experience success, while using substantially less communication than screenshot takeover. The evaluation spans nine version pairs and measures success, recovery, communication, energy, and cloud calls.

A. Experimental Setup

  • The evaluation covers 45 units from nine version pairs and five tasks, with five postupdate episodes per arm under three seeds.The main tier is 10 Mbps uplink and 80 ms round-trip time; baselines include no experience, stale experience, re-explore, and cloud-based alternatives.Source: A. Experimental Setup · pp. 4–5

B. Main Results

  • REBASE raises Succ@K by 56.1 points over stale experience and matches fresh experience on the new version within 0.4 points.Table I summarizes recovery to fresh-experience success alongside the takeover and upload baselines.Source: B. Main Results · p. 5, Table I · p. 5
  • REBASE uses 708× fewer bytes and 47.3× fewer cloud calls than screenshot-to-cloud, and 215× fewer bytes than trajectory upload.Screenshot-to-cloud matches REBASE on Succ@K by having the cloud complete broken episodes, but autonomous recovery remains censored at K +1.Source: B. Main Results · p. 5
  • Per episode, REBASE uses 2.5× less device energy than no experience and 2.3× less than re-explore.Verified steps and patched recorded actions reduce device-side model calls.Source: B. Main Results · p. 5

C. Link Tiers, Fleets, and Energy

REBASE maintains success and latency across tested link tiers, while version-keyed repairs limit fleet-wide re-derivations and staged evidence keeps event costs low.

C. Link Tiers, Fleets, and Energy

  • As bandwidth falls from 50 to 2 Mbps and round-trip time rises from 20 to 250 ms, REBASE stays within 2.7 and 4.0 Succ@K points of the fastest tier, respectively.Episode latency remains between 32.5 s and 33.2 s; screenshot-to-cloud latency rises from 48 s to 61 s as the link slows.Source: C. Link Tiers, Fleets, and Energy · p. 5
  • With version keys, cloud re-derivations stay near 42 broken steps and are 80.0× fewer than without keys in a 100-device fleet.Each of the three real devices encounters 81.7% of the same broken steps.Source: C. Link Tiers, Fleets, and Energy · p. 5
  • The median event costs 17 J, and 79.4% of ladder events close at the fingerprint or diff level.Each episode uses 1028 J less than without experience, so event energy is recovered within 0.02 of an episode.Source: C. Link Tiers, Fleets, and Energy · p. 5

D. Ablation Study

Ablations show that both clocks, device verification, and staged evidence contribute to REBASE’s performance. The conclusion bounds the measured coverage to accessibility-tree failures and identifies changed-element detection as central to recovery.

D. Ablation Study

  • Removing REBASE components reduces performance: without the failure clock, success falls to 56.4% on blind pairs and 92.7% on cloud-visible pairs; without verification, stale steps rise to 3.7 per episode.Fixing evidence at screenshots uses 14.4× the uplink bytes, while fixing it at diffs loses 9.8 points because 20.6% of ladder events need a higher level.Source: D. Ablation Study · p. 5

VI. CONCLUSION

  • REBASE restores stale-experience success to fresh-experience success within one episode, using 708× fewer bytes than screenshot upload and 2.5× less device energy than no experience.Every measured failure exposed an accessibility tree; screens without one start at a crop, and desktop agents remain future work.Source: §VI · pp. 5–6
  • Figure 4 plots Succ@K against bandwidth and round-trip time, then episode latency against bandwidth and transferred kilobytes; Figure 5 covers fleet size, energy, event bytes, and closure shares.Source: Figure 4 · p. 6, Figure 5 · p. 6

Related papers

Loading 2609.32130v1…