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

ReTrace is a scalable evaluation framework that formalizes transition-consistent recovery and uses goal-oriented action replay after controlled error injection to systematically study model-based recovery in computer-use agents.

Computer-use agents remain fragile in long-horizon settings, where errors accumulate and executed actions leave unintended side effects. Existing remedies are inadequate: environment resets are often infeasible, action replay is expensive over long horizons, and API-based rollback is largely confined to web environments. Autonomous model-level recovery, where the agent restores a prior state itself, remains largely unexplored.

ReTrace is a pipeline for systematically studying autonomous, model-based recovery in computer-use agents. It formalizes successful recovery as Transition-Consistent Recovery: a recovered state matches its target if executing identical downstream actions from both states yields identical outcomes. It operationalizes this criterion through goal-oriented action replay following controlled error injection. The evaluation set is built by replaying each on-policy trajectory multiple times and retaining only trajectories with consistent successful outcomes, then sampling intermediate states as recovery targets and perturbing them into erroneous states. Recovery is evaluated by checking whether replaying the remaining actions reproduces the original task outcome. ReTrace is instantiated on OSWorld and WindowsAgentArena across closed- and open-source computer-use agents.

• Ideal recovery, in which agents are returned to an oracle prior state, boosts performance over naive environment resets and unlocks latent task completion capabilities. §4
• Current computer-use agents fail to exploit their latent recovery capabilities, lacking both the tendency and capability to recover autonomously. §5
• When equipped with explicit model-based recovery, recovery success climbs by more than an order of magnitude, showing that the underlying capability is latent rather than absent. §5
• Accurate model-level recovery delivers measurable end-to-end gains, while weak recovery can actively derail the trajectory. §6
• After recovery to incorrect states, forward-agent rationales show two major behavior patterns: spurious perception and state tracking failure. §6.3
• Human evaluation used 150 evaluation samples and reported an average agreement rate of 82% and a Cohen kappa coefficient of 0.45 across annotator pairs. §B.3

• ReTrace is designed to measure and analyze recovery capabilities and behaviors rather than to directly improve them.
• Explicit recovery settings can only elicit capabilities already present in the underlying model and cannot compensate for fundamental deficiencies in GUI understanding, state tracking, or action planning.
• Inaccurate recovery by specialist agents with weaker recovery capabilities may induce additional trajectory drift and reduce task success.
• Recovery-aware post-training and auxiliary objectives for tracking latent environment states and predicting action-induced transitions are proposed future directions but are beyond the scope of the present work.

• Existing recovery remedies are inadequate: environment resets are often infeasible, action replay is costly over long horizons, and API-based rollback is largely confined to web environments. §1
• Transition-Consistent Recovery uses behavioral equivalence rather than visual similarity to capture latent environment changes. §5.1
• The recovery oracle combines a transition-consistency check with observation-level agreement. §5.1
• ReTrace evaluates recovery in three stages: transition-consistent evaluation-set construction, perturbation into erroneous states, and goal-oriented action replay. §5.2
• The study is instantiated on OSWorld and WindowsAgentArena across closed- and open-source computer-use agents. §1
• Ideal recovery identifies recovery as a key lever for unlocking agents' latent task-solving capacity. §4
• Current agents lack both the tendency and capability to recover autonomously under erroneous conditions. §5
• Accurate model-based recovery yields measurable end-to-end gains, while poor recovery can severely degrade downstream task completion. §6