Recent advances in large (vision) language models have enabled computer-use agents that automate digital workflows via fine-grained keyboard and mouse operations. However, these agents remain fragile in long-horizon tasks: errors accumulate, and executed actions leave unintended side effects, making recovery capability critical. Existing remedies are limited—environment resets are infeasible in proprietary settings, action replay over long horizons is prohibitively costly, and API‑based rollbacks only work for web environments, leaving model‑driven recovery largely unexplored. To fill this gap we introduce ReTrace, a scalable evaluation framework for systematically studying recovery behavior in computer-use agents. We formalize Transition‑Consistent Recovery as the requirement that identical downstream actions from the recovered state and the target state produce identical outcomes. By injecting controlled errors and then performing goal‑oriented action replay, we operationalize this criterion. Using ReTrace we conduct the first systematic study of autonomous, model‑based recovery and uncover three key findings: (i) ideal recovery can unlock the model’s latent task‑completion abilities; (ii) current computer-use agents fail to exploit these latent recovery capabilities; (iii) accurate model‑based recovery yields measurable end‑to‑end performance gains. Together these results establish recovery as a fundamental capability for building reliable computer-use agents. Code and dataset are released at https://github.com/BangProx/ReTRACE.
Review: This work provides a rigorous quantification of recovery via the ReTrace framework, offering valuable insights for improving robustness in long‑horizon automation scenarios.