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

Lost in Recovery. Demystifying Recovery Behavior of Computer-Use Agents via Goal-Oriented Action Replay. By Byeonghun Bang and five others, from KAIST, ETRI, and one other institution. Published on the twentieth of October.

Large language and vision language models now drive computer-use agents, systems that automate digital workflows through fine-grained keyboard and mouse operations. These agents are fragile over long horizons. Errors accumulate, and actions already executed leave side effects nobody intended. Recovering from failure becomes critical, yet the existing remedies fall short. Resetting the environment is not possible in proprietary settings. Replaying actions from the start is prohibitively expensive when the horizon is long. Rolling back through an API only works for web environments. What remains, recovery carried out by the model itself, has gone largely unexplored, and there has been no systematic way to measure it.

ReTrace is a scalable evaluation framework built to fill that gap. Its measuring stick is a criterion the authors formalize as Transition-Consistent Recovery. The idea is a behavioural test of sameness. Take the state the agent recovered to, and the target state it should have reached. If the same downstream actions, applied from each, yield identical outcomes, the recovery counts. Two states are treated as equivalent when nothing done next can tell them apart.

To put that criterion into practice, ReTrace first injects errors in a controlled way, so the failure is known. It then uses goal-oriented action replay: actions directed at the task goal are replayed from both the recovered state and the target state, and the outcomes are compared. This is how the framework checks consistency without needing a reset or a rollback interface.

With ReTrace in hand, the authors present what they describe as the first systematic study of autonomous, model-based recovery. Three findings come out. First, ideal recovery can unlock task completion capabilities the model already has but could not reach from a broken state. Second, current computer-use agents fail to exploit their own latent recovery capabilities. Third, when model-based recovery is accurate, it yields measurable gains end to end.

Read together, the findings separate two abilities that are easy to blur: doing the task, and getting back on track after a mistake. Agents appear to hold more of both than they use, and the gap between them shows up in final results. The authors conclude that recovery deserves to be treated as a fundamental capability for reliable computer-use agents, and ReTrace is their instrument for measuring it.