Lost in Recovery: Demystifying Recovery Behavior of Computer-Use Agents via Goal-Oriented Action Replay

AI summary

Overview

Research area: Computer-use agents (CUAs) — large vision-language models that operate desktops and applications through keyboard and mouse actions — with a specific focus on how they recover after mistakes.

Technical level: Advanced. The paper formalizes recovery as a POMDP problem, defines a transition-based success criterion, and runs multi-model evaluations on OSWorld and WindowsAgentArena.

Scope (one sentence): The paper introduces ReTrace, an evaluation pipeline that measures whether computer-use agents can autonomously return to a previously valid state after an error, and reports the first systematic study of model-based recovery across five closed- and open-source agents on two desktop benchmarks.

What This Paper Is About

Computer-use agents make mistakes in long tasks, and those mistakes accumulate: an agent may leave behind unintended side effects (for example, overwriting files a user wanted to keep) that later actions cannot undo. The usual fixes — resetting the whole environment, replaying every action from the start, or using web-only "back" APIs — are either infeasible, expensive, or limited to browsers. This paper asks whether the agent itself can restore a prior valid state, and builds a controlled pipeline (ReTrace) to measure that ability rather than assuming it.

Key Contributions

1. A formal definition of successful recovery. The authors define Transition-Consistent Recovery: a recovered state matches its target only if executing the same downstream actions from both states produces the same outcomes. The final oracle combines this transition check with an observation-level match, so a state that looks identical in a screenshot but differs in hidden state is not counted as recovered.

2. ReTrace, a three-stage evaluation pipeline. (A) On-policy trajectory rollout collects successful trajectories and replays each action sequence N times, keeping only trajectories that succeed consistently (N=3 is used, retaining 64.4% of recovery trajectories). (B) Trajectory drift via perturbation takes an intermediate state as the recovery target and drives the agent into a verified erroneous state. (C) Goal-oriented action replay runs the remaining original actions from the recovered state to test whether the original task outcome is reproduced.

3. The first systematic study of autonomous, model-based recovery. The authors evaluate implicit recovery (the forward agent continues unaided) and explicit recovery (a dedicated policy is given the target), across Claude Sonnet 4.6, GPT-5.4-Computer-Use, EvoCUA-32B, UI-TARS-1.5-7B and Qwen3.5-9B-Thinking on OSWorld and WindowsAgentArena.

4. A human-validated oracle and a failure taxonomy. The recovery oracle is checked against 12 human annotators (50 samples per variant, 25 ratings each), and the paper categorizes why imperfect recovery degrades downstream performance into spurious perception and state tracking failure.

Main Findings

• Ideal recovery beats restarting (Finding 1). Using EvoCUA-32B on OSWorld and measuring Success@K over 5 independent continuations, every non-zero recovery step — one step before the error, a random past step, or an LLM-selected step — outperforms a full reset (R=0), with the largest advantage in the low-K regime. Under a fixed retry budget, resuming from a prior state uses each retry more efficiently than restarting.

• Current agents almost never recover on their own (Finding 2). Even Claude Sonnet 4.6 and GPT-5.4-CUA show limited recovery capability, and EvoCUA-32B shows an average recovery rate below 1%. Rationales produced during implicit recovery are substantially less similar to ground-truth recovery prompts than under explicit recovery, indicating agents rarely even attempt restoration.

• The capability exists but is not elicited (Finding 3). Explicit model-based recovery outperforms implicit recovery by an average margin of 17.86% across the Linux and Windows environments, with the largest improvements for generalist agents (Claude Sonnet 4.6, GPT-5.4-CUA, Qwen3.5-9B).

• Extensive post-training may weaken recovery (Finding 4). Gains from explicit recovery are considerably smaller for post-trained open-source agents, and the long-horizon results (recovery distance d=5) show the same trend: generalist agents have far more recovery potential than post-trained specialists.

• Even imperfect recovery can help (Finding 5). For Qwen3.5-9B, model-based recovery improves over the no-recovery baseline under every recovery setting, with an average gain of 2.12% end-to-end. Per-configuration results range from 39.38 ± 1.17 (baseline) to 44.26 ± 1.90 with recovery-target contextualization (+4.88).

• Weak recovery can actively hurt (Finding 6). On OSWorld end-to-end runs, Claude Sonnet 4.6 improves from 70.27 ± 0.70 to 71.81 ± 1.51 and Qwen3.5-9B from 38.76 ± 0.64 to 41.56 ± 4.14, but UI-TARS-1.5-7B drops from 17.25 ± 1.55 to 15.74 ± 0.65 and EvoCUA-32B from 54.88 ± 4.39 to 51.55 ± 2.54. More recovery attempts help models with better recovery skill and derail EvoCUA-32B further.

• The oracle agrees with humans more than alternatives. ReTrace achieves an 82.0% win rate against an oracle without the observation-matching term, 63.0% against one without the transition-consistency term, and 54.0% against a GPT-5.4 evaluator, with 82% inter-annotator agreement and Cohen's kappa of 0.45.

• Two characteristic failure modes. Spurious perception: the agent fixates on whatever element happens to be under the cursor in the imperfectly restored state (e.g., clicking an alignment button instead of dragging the text first). State tracking failure: the agent hallucinates that the restored state matches the target, acting as if a font-selection UI were still open when it is no longer visible.

Methodology in Plain English

The researchers first let each agent solve tasks normally and keep only successful runs. To make sure the environment behaves deterministically, they replay each action sequence three times and keep only trajectories that succeed all three times — this filters out flaky runs. They also report that OSWorld contains 12.66% web tasks and 87.34% non-web tasks, and WindowsAgentArena 21.28% web and 78.72% non-web, which matters because web-only rollback APIs cannot cover the non-web majority.

From a kept trajectory they pick an intermediate step as the "target" state to return to. They then push the agent off course with a perturbation policy until an oracle evaluator confirms the state is genuinely erroneous. A recovery policy — either the same agent continuing (implicit) or a dedicated policy given the target (explicit) — acts for up to r steps (r ∈ {1, 3, 10}). Finally they replay the rest of the original action sequence from the recovered state; if the task evaluator still reports success, recovery is judged transition-consistent.

Recovery distance is set to d=1 for short-horizon and d=5 for long-horizon experiments. Explicit recovery variants differ in what context they receive: history up to the error (0-E), history up to the target (0-R), no history, or an LLM-summarized context of the transitions leading to the target. Environments run in isolated Docker containers with a 10-second settle window after each action, at 1920×1080 for OSWorld and 1280×800 for WindowsAgentArena; the exact size of the final recovery evaluation set is deferred to the paper's tables (Tables 6 and 7) and is not stated in the body text.

Why This Matters

Impact on research. Prior work treated rollback, action replay and back-navigation as heuristics bolted onto inference pipelines. This paper turns recovery into a measurable capability with a formal success criterion, showing that the bottleneck is elicitation rather than raw model ability — a reframing that points at post-training and auxiliary objectives rather than prompt engineering.

Real-world applications:

• Automating tasks on proprietary or production systems (websites, operating systems) where a full environment reset is impossible.
• Document, spreadsheet and file-management agents where a wrong action silently destroys user data and an undo stack does not exist.
• Long enterprise workflows where early errors otherwise propagate and force a restart of a costly multi-step process.
• Safer deployment monitoring: recovery success rate as a diagnostic signal before trusting an agent with consequential actions.

Industry relevance. The finding that heavy task-completion post-training may erode recovery ability is directly relevant to teams fine-tuning agentic models, and the failure modes give concrete targets for product-level guardrails. The paper's own framing is that recovery is a fundamental capability for reliable computer-use agents, not a nice-to-have.

Future Directions

• Recovery-aware post-training. Training on erroneous states paired with target states and corrective action trajectories, which the authors name as the natural remedy for specialists that currently fail at restoration.
• Auxiliary objectives for hidden state. Objectives that track latent environment state and predict action-induced transitions, so agents do not fall into state-tracking failure after an imperfect restoration.
• More robust recovery policies. Even the strongest models with basic explicit recovery do not achieve complete recovery in these settings, so better recovery mechanisms and continuation-from-recovery policies remain open.
• Cheaper and broader evaluation. The current oracle relies on multi-replay verification and an LLM verifier, and single-step annotation was judged impractical, which limits scaling to finer-grained recovery distances and larger task sets.

Target Audience

Researchers and engineers working on computer-use and GUI agents, agent reliability and long-horizon task execution; practitioners fine-tuning agentic models who need to know whether post-training trades away error-recovery behavior; and evaluators or safety engineers who need a validated protocol for judging whether an agent has truly restored a state rather than merely reproduced its screenshot.

Authors’ abstract

Recent advances in large (vision) language models have enabled computer-use agents that automate digital workflows via fine-grained keyboard and mouse operations. However, such agents remain fragile in long-horizon settings, where errors accumulate and executed actions leave unintended side effects, making the ability to recover from failures critical. Yet, existing remedies remain inadequate: environment resets are infeasible in proprietary settings, action replay is prohibitively expensive over long horizons, and API-based rollback is limited to web environments, leaving model-based recovery largely unexplored. To address this gap, we present ReTrace, a scalable evaluation framework for systematically studying recovery behavior in computer-use agents. We formalize Transition-Consistent Recovery: identical downstream actions from the recovered and target states must yield identical outcomes. We operationalize this criterion through goal-oriented action replay following controlled error injection. Using ReTrace, we present the first systematic study of autonomous, model-based recovery, revealing that (i) ideal recovery can unlock model's latent task completion capabilities, (ii) current computer-use agents fail to exploit their latent recovery capabilities, and (iii) accurate model-based recovery yields measurable end-to-end gains. Together, these findings establish recovery as a fundamental capability for building reliable computer-use agents. Our code and dataset is available at https://github.com/BangProx/ReTRACE.