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

1 Introduction

• Long-horizon errors accumulate, and executed actions can leave unintended side effects, making restoration to a previously intact state critical for reliable operation.The paper gives silently overwriting files during directory organization as an example of a side effect.Source: §1 · p. 1
• Existing remedies constrain general-purpose recovery: resets may be infeasible in proprietary settings, replay is costly over long horizons, and API rollback is largely web-limited.The paper therefore identifies autonomous model-level recovery as an essential capability that remains largely unexplored.Source: §1 · p. 2
• RETRACE defines Transition-Consistent Recovery as matching a target state when identical downstream actions from both states yield identical outcomes.It operationalizes the criterion by replaying the remaining actions after perturbing a sampled intermediate state.Source: §1 · p. 2
• Ideal recovery boosts performance over naive resets, current agents lack the tendency and capability to recover autonomously, and accurate model-based recovery yields end-to-end gains.Weak recovery can actively derail the trajectory.Source: §1 · p. 2

2 Related Works

• Prior work strengthens forward policies through screenshot-based LVLMs, reinforcement learning, and external memories, while long-horizon brittleness remains largely unaddressed.The paper frames systematic recovery analysis as a complementary, underexplored axis.Source: §2 · pp. 2–3
• Failure-handling approaches include feedback-driven reflection, reward-based plan revision, environment resets with action replay, and web rollback operations.Computer-use studies also use external verifiers and semantic actions for state recovery.Source: §2 · p. 3
• Earlier mechanisms were used as inference-pipeline heuristics rather than systematically analyzed for their behavior and effects.RETRACE's Figure 2 outlines rollout, perturbation, and goal-oriented action replay for evaluating recovery.Source: §2 · p. 3, Figure 2 · p. 3

3 Preliminary

• A computer-use task is modeled as a POMDP with states, actions, observations, environment, transition function, and observation function.Each state contains a hidden component and an observation, with observations generated from the state.Source: §3 · p. 3
• The policy selects actions from the observation-action history, producing a trajectory through the digital environment.Actions range from high-level clicks to low-level operations such as pyautogui.click.Source: §3 · p. 3
• The forward formulation does not specify how an agent should behave when early actions lead to an erroneous state from which the query can no longer be completed.That recovery setting is the focus of the paper.Source: §3 · p. 3

Expected Gains from Ideal Recovery

• Success@5 measures success over five independent continuations resumed from different recovery steps.The experiment is motivated by variation across repeated rollouts of the same task.Source: §4 · p. 3

Setup

• The evaluation focuses on tasks EvoCUA-32B fails under standard rollouts, using OSWorld and several choices of recovery step R.Choices include the initial state, one step before the detected error, a uniformly sampled past step, and an LLM-identified step.Source: §4 · p. 4

Results

• Every nonzero recovery strategy outperforms a full reset (R = 0), with the largest advantage at low K; the gap diminishes as K increases.Under the same retry budget, recovery from a previous state uses retries more efficiently than restarting from scratch.Source: §4 · p. 4, Figure 3 · p. 4

5.1 Transition-Consistent Recovery

• Transition-consistent recovery judges a restored state by whether the same downstream action reproduces the target transition, capturing latent differences that visual matching can miss.The final oracle combines this transition check with observation-level agreement.Source: §5.1 · p. 4

5.2 Recovery Evaluation

• RETRACE builds its evaluation set from successful on-policy trajectories, repeats action sequences to establish reliable transitions, then perturbs a target state to create a verified error state.The perturbation is checked against the user query so each instance pairs an off-track state with a reachable target.Source: §5.2 · p. 5
• From each error state, recovery runs for a limited number of steps; replaying the remaining target actions tests whether the original task outcome is reproduced.The evaluation uses the task-completion oracle together with observation-level matching.Source: §5.2 · p. 5

5.3 Recovery Policy

• Implicit recovery lets the forward policy continue without recovery-specific instructions, whereas explicit recovery uses a dedicated policy conditioned on the target observation and recovery context.The context represents target-state information that cannot be inferred from the target observation alone.Source: §5.3 · p. 5

5.4.1 Setup

• The evaluation covers OSWorld and WindowsAgentArena, several closed- and open-source agents, short- and long-horizon settings, recovery budgets of 1, 3, or 10 steps, and varied recovery contexts.Recovery distance is set to 1 for short-horizon and 5 for long-horizon experiments.Source: §5.4.1 · p. 6

5.4.2 Results and Analysis

• Below 1% average recovery rate for EvoCUA-32B, while current agents also show limited restorative behavior and rarely attempt recovery implicitly.Implicit-recovery rationales have substantially lower similarity to ground-truth recovery prompts.Source: §5.4.2 · pp. 6–7
• 17.86% average margin across Linux and Windows: explicit model-based recovery outperforms implicit recovery, with the largest gains among generalist agents.Post-trained open-source agents show considerably smaller gains.Source: §5.4.2 · p. 7
• In long-horizon settings, generalist agents show greater recovery potential than post-trained specialists, yet even capable models with basic explicit strategies fail to achieve complete recovery.These results are reported under the paper’s evaluation settings.Source: §5.4.2 · p. 7, Figure 7 · p. 7

6.1 Setup

• The forward and recovery agents share a backbone model, and explicit recovery strategies follow the evaluation protocols of Sections 4 and 5.4.Source: §6.1 · pp. 7–8

Potential Gains from Model-Based Recovery

• 2.12% average gain: Qwen3.5-9B improves over the no-recovery baseline across every recovery setting in the end-to-end evaluation.The gains occur despite suboptimal recovery success rates.Source: Potential Gains from Model-Based… · p. 8
• Weaker recovery degrades end-to-end performance for UI-TARS-1.5-7B and EvoCUA-32B, while more attempts benefit Qwen3.5-9B and UI-TARS-1.5-7B.For EvoCUA-32B, low recovery success means additional attempts more often derail the trajectory; even one successful recovery can improve downstream performance.Source: Potential Gains from Model-Based… · p. 8

6.3 Qualitative Analysis

• Imperfect restoration prompts spurious perception of non-target elements and state-tracking failures that make agents act as if the target interface remained open.A cursor hovering over the alignment button can prompt a click that skips the required text drag; a masked font-selection interface can still be treated as open.Source: §6.3 · p. 8, Table 4 · p. 8

• RETRACE operationalizes Transition-Consistent Recovery through goal-oriented action replay, treating a recovered state as matching its target when identical downstream actions yield identical outcomes.Source: §7 · p. 8
• Evaluations find that current computer-use agents lack both the tendency and capability to recover autonomously, while accurate model-based recovery produces measurable end-to-end gains.Source: §7 · p. 9
• The findings position accurate model-based recovery as a key step toward reliable computer-use agents, despite failure modes including spurious perception and state-tracking errors.Source: §7 · p. 9

• RETRACE measures and analyzes recovery behavior; it is not designed to directly improve recovery.Source: Limitations · p. 9
• Explicit recovery cannot compensate for fundamental deficiencies in GUI understanding, state tracking, or action planning.Source: Limitations · p. 9
• Inaccurate recovery by specialist agents with weaker recovery capabilities may induce additional trajectory drift and reduce task success.Recovery-aware post-training and auxiliary state-tracking or transition-prediction objectives are proposed directions, but designing and validating them is beyond this work's scope.Source: Limitations · p. 9

Ethical Considerations

• More capable agents could in principle be repurposed for harmful automation, a dual-use risk the authors acknowledge.Source: Ethical Considerations · p. 9
• Experiments used sandboxed virtual environments and publicly available benchmarks, without real user accounts or personal data; the authors recommend deployment safeguards.Source: Ethical Considerations · p. 9

A RETRACE Details

• Appendix A provides implementation details for evaluation-set construction and recovery evaluation, including trajectory statistics and domain distributions in Tables 6 and 7.Source: A RETRACE Details · p. 13

A.1 Evaluation Set Construction

• OSWorld and WindowsAgentArena provide web and non-web tasks, but evaluation excludes tasks requiring proxy or Google Drive settings.Trajectories are retained after three consecutive successful replays to reduce environment-stochasticity effects; the filtered set retains 64.4% of recovery trajectories.Source: §A.1 · p. 13, Table 5 · p. 13, Table 6 · p. 14
• Evaluation datasets are built from replay-validated trajectories, perturbed into oracle-confirmed failure states, then filtered and sampled for recovery tests.The experiments use isolated benchmark environments and exclude problematic samples that complicate annotation.Source: §A.1 · pp. 13–14

A.2 Recovery Evaluation

• Recovery evaluation compares implicit policies using interaction history with explicit policies given different combinations of error-state history and target-state context.Recovery success is tested by replaying the remaining ground-truth actions from the recovered state; observation-wise matching uses SSIM with a 0.99 threshold.Source: §A.2 · pp. 14–15, Table 7 · p. 15

B.1 Ideal Gains from Recovery

• The ideal-gains experiment compares restart, pre-error, random prior, and LLM-predicted recovery steps on failed OSWorld tasks.It reports Success@K across five continuations reconstructed from each selected recovery state.Source: §B.1 · pp. 15–16

B.2 End-to-End Evaluation

• The end-to-end evaluation uses three open-source forward agents, with same-backbone recovery agents triggered by LLM-based error and recovery-step detectors.Recovery attempts have a 10-step budget, and the forward agent resumes with context truncated to the recovery boundary.Source: §B.2 · pp. 16–17

• The evaluation uses 150 samples, split into 50 cases for each of three evaluator variants.Samples are selected where RETRACE’s oracle decisions differ from alternative evaluator decisions.Source: §B.3 · p. 17
• Twelve annotators independently label whether each recovery target state was successfully restored.Annotators work in pairs on subsets and may flag cases where stochastic environment dynamics do not prevent judging recovery successful.Source: §B.3 · p. 17
• 82% average agreement and a Cohen’s kappa coefficient of 0.45 were observed across annotator pairs.The study compares the RETRACE oracle against alternative evaluators using human annotations as reference labels.Source: §B.3 · p. 17

C Supplementary Experiments

• Generalist agents show higher recovery success under implicit recovery and generally larger gains from explicit instructions on WindowsAgentArena.Claude-Sonnet-4.6, GPT-5.4-CUA, and Qwen-3.5-9B show this pattern in the expanded results.Source: C Supplementary Experiments · p. 17, Figure 9 · p. 18
• Implicit recovery success rates for most agents decrease as recovery-step budgets grow, but remain above zero.The results suggest agents retain some restorative ability but do not reliably use it under failure scenarios.Source: C Supplementary Experiments · p. 18, Table 8 · p. 18
• Under Recovery Target Contextualization, EvoCUA-32B shows limited recovery capability compared with UI-TARS-1.5-7B across a wide range of hyperparameter configurations, even with explicit recovery prompting.Source: C Supplementary Experiments · p. 18
• Explicit recovery gains persist across three randomly sampled evaluation sets, with generalist agents gaining substantially and EvoCUA showing nearly no capability.UI-TARS shows only modest improvements from explicit instructions.Source: C Supplementary Experiments · p. 19, Figure 10 · p. 19
• 86.0% of RETRACE judgments in the analyzed cases were favorable decisions unaffected by stochastic environmental dynamics.The analysis uses disagreement cases where annotators agreed on recovery success and the presence of environmental effects.Source: C Supplementary Experiments · pp. 19–20, Table 11 · p. 19
• Joint use of RO and RTC agrees with human judgments more often than either oracle alone on their disagreement cases.The analysis considers cases where both human annotators agree on recovery success.Source: C Supplementary Experiments · p. 20, Table 12 · p. 20
• Lowering RO’s SSIM threshold causes overestimation of recovery success and reduces alignment with human annotations.The results support the default threshold of 0.99 for screenshot-level matching.Source: C Supplementary Experiments · p. 20, Table 13 · p. 20

D Qualitative Analyses

• Table 14 provides additional qualitative examples of erroneous agent behavior induced by imperfect state restoration.Source: Table 14 · p. 21, D Qualitative Analyses · p. 21

E Human Evaluation Guidelines

• Evaluators assign success only when the recovered state is functionally equivalent to the goal, using fine-grained visual comparison and checking that the original task can continue correctly.They inspect interaction-sensitive UI state, including active pages, selections, focus, menus, cursor or hover states, and drag-and-drop; minor dynamic rendering differences may be ignored if functional state remains equivalent.Source: E Human Evaluation Guidelines · p. 22

F Prompts

• The cited appendix materials include system prompts for Claude-Sonnet-4.6 and Evocua-32B forward agents in OsWorld, an Evocua tool-description prompt, a UI-Tars-1.5-7B action space, and Qwen-3.5-9B prompts for OsWorld and WindowsAgentArena.Source: F Prompts · pp. 22–27
• Perturbation prompts require valid actions that differ from the correct action and actively drive the interface toward a substantially unrelated state.They discourage minor mistakes and, in the GPT-5.4-CUA prompt, prohibit waiting actions that do not change the state.Source: F Prompts · p. 29
• The Recovery Agent’s primary objective is to return from the current Error State to the Goal State by analyzing their differences and taking the most direct path while ensuring accuracy.When the agent believes it has returned to the Goal State, it takes a screenshot to verify the match.Source: F Prompts · p. 30
• A state counts as semantically the same when the task can continue exactly as from the expected state without extra recovery, with the same page and critical UI state.The guidelines identify the same site or app, logical screen, and modal, popup, or overlay as relevant state features.Source: F Prompts · p. 31
• Goal-state contextualization uses trajectory history and the goal screenshot to produce a detailed description that helps the recovery agent restore the target.The instructions ask for a comprehensive visual account of the goal state.Source: F Prompts · p. 32
• The error detector reviews the task trajectory and current observation, flags clear counterproductive actions, and can retrospectively identify an earlier error revealed by later evidence.It returns whether an error occurred and the 0-based step where it becomes visible.Source: F Prompts · p. 33
• The recovery-step detector selects the observation to rewind to, where step k means returning to observation_k before action_k.The prompt uses 0-based indexing and gives the initial observation as recovery step 0.Source: F Prompts · p. 34
• Recovery evaluation compares the final recovery state with the ground-truth goal, emphasizing semantic and functional equivalence despite minor visual differences.The evaluator receives the goal and error states, recovery and preceding trajectories, final state, and original instruction.Source: F Prompts · p. 35