- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies how LLM agents can recover from mistakes within an ongoing task instead of restarting from the beginning. The authors propose ReTRAIL, which gives the agent an environment-level rewind action. The agent can restore an earlier state, write a reflection on what it learned from the abandoned branch, and continue from the restored state with that reflection. The agent is trained with RL using two signals. State-Anchored GRPO compares continuations from the same state to improve actions. A branch-advancement reward scores a reflection by how much more progress the resumed branch makes than the abandoned one. With Qwen3-4B on MineSweeper, Sokoban, ALFWorld, and ScienceWorld, ReTRAIL achieves the highest success when rewinds and retries are allowed.
Critical strengths
- The idea of moving the environment backward while carrying knowledge forward is intuitive and well-motivated. It is also clearly distinguished from multi-episode adaptation, which restarts from the initial state.
- The two learning signals fit the setting well. Continuations from the same state give a natural group for comparing actions, and scoring a reflection by the progress of the branch that follows gives reflection its own learning signal.
- The paper provides ablations of rewind, reflection, and both learning objectives, along with analyses by difficulty, number of attempts, and task length.
Critical weaknesses
- Baselines are not trained with rewind: ReTRAIL is the only method trained with the rewind interface. The RL baselines are trained without it and only given rewind at test time, so it is expected that they use it poorly. When State-Anchored GRPO is replaced with GiGPO inside the same rewind framework (Table 3), most of the gap closes.
- Rewind changes what the benchmarks test: On MineSweeper, after the agent reveals a mine, it can restore an earlier state of the same board. Similarly, Sokoban is meant to test planning with moves that cannot be undone, and rewind removes that difficulty.
- Limited practicality: The method assumes any earlier state can be restored for free, either from saved snapshots or by replaying actions in a deterministic environment. Replayed actions are also not counted in the budget. Most realistic settings the paper uses as motivation, such as web or software tasks with side effects, cannot be rewound this way. Training also relies on progress scores that are rarely available in practice, such as the shortest-solution distance found by search in Sokoban.
- Limited evaluation: The tasks are small and short: 6×6 MineSweeper boards with three mines, Sokoban rooms with two or three boxes, and a 60-call budget. This makes the long-horizon framing a stretch. ALFWorld is evaluated only on the seen split, not on the unseen split that tests generalization, and all fine-tuned methods already exceed 89%. All results use a single 4B model, limiting generalization.
Questions for authors
- Could the authors train the RL baselines with the same rewind interface so that the comparison isolates the proposed objectives?
- On MineSweeper, how often do successful T@3 attempts depend on mine locations revealed by earlier failed attempts?
- Do the RL baselines receive the same progress signals as ReTRAIL, such as the Sokoban progress score computed by search, or only the task outcome?
- How much training compute does ReTRAIL use compared with the baselines?
5 comments
Response to Reviewer o63W (Part 2/3)
W3: Limited practicality We thank the reviewer for raising these points and address them in turn.
● Practicality: Environments for autonomous agent execution are increasingly restorable by design: virtual machines support snapshots [2], sandbox runtimes roll back an agent's workspace in milliseconds [3], and web agents are given explicit rollback operations [1]. In these environments, the side effects of an action, such as file edits, application state and browser sessions, stay inside the workspace and can be reverted. What is missing is a policy that uses this ability well. With rewind at test time, the trained baselines change by only −3.0 to +1.8 points, whereas ReTRAIL gains up to 10.9 points from proactive rewind and 36.5 points with three attempts (Table 1). Learning when to rewind and what to carry over is the gap that ReTRAIL fills. We acknowledge that some actions have effects outside the workspace that cannot be undone, such as completing a payment. In such cases, ReTRAIL simply acts without rewind, and its performance without rewind (P@1) is still competitive.
● Progress signals: In all four environments, the progress score is computed on the environment side from the task state, including the solver distance in Sokoban, and requires no human annotation. Such verifiable progress is increasingly available, through checkpoints and state-based tests in realistic benchmarks [4] and through learned progress models [5], and ReTRAIL can use any of these as its branch score. To test how much ReTRAIL depends on such scores, we conducted an experiment in which every method is trained with only the binary task outcome:
| Method (binary outcome only) | MineSweeper T@1 | MineSweeper T@3 | Sokoban T@1 | Sokoban T@3 |
|---|---|---|---|---|
| GiGPO | 54.8 | 60.2 | 77.3 | 83.1 |
| LaMer | 56.0 | 68.9 | 69.1 | 81.6 |
| ReTRAIL | 60.2 | 89.1 | 83.9 | 89.6 |
Under this sparse signal, ReTRAIL still trains well. It loses 6.2 and 4.1 points of T@3 relative to Table 1, and remains 20.2 and 6.5 points above the stronger baseline.
Revision. We have added a discussion of restorable environments, this scope, and the availability of progress signals to Appendix B, the restoration cost to Appendix D.3, and the binary-outcome experiment to Appendix C.8 (Table 11).
[1] WebRollback: Enhancing Web Agents with Explicit Rollback Mechanisms. EACL 2026. [2] OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments. NeurIPS 2024. [3] DeltaBox: Scaling Stateful AI Agents with Millisecond-Level Sandbox Checkpoint/Rollback. ACM ATC 2026. [4] AppWorld: A Controllable World of Apps and People for Benchmarking Interactive Coding Agents. ACL 2024. [5] Web-Shepherd: Advancing PRMs for Reinforcing Web Agents. NeurIPS 2025.
W4: Limited evaluation
We thank the reviewer for these comments and address them one by one.
● Task size and horizon: We agree that the default instances are relatively small. In figure 4(a) we scales their difficulty, and ReTRAIL keeps its advantage at every level. We additionally scaled the step budget on the hardest instances, using the same checkpoints:
| T@3 (%) | MineSweeper, 5 mines: 60 steps | 90 steps | 120 steps | Sokoban, 4 boxes: 60 steps | 90 steps | 120 steps |
|---|---|---|---|---|---|---|
| GiGPO | 34.6 | 36.7 | 37.5 | 38.1 | 40.2 | 41.0 |
| LaMer | 45.3 | 47.7 | 48.4 | 45.5 | 48.0 | 49.2 |
| ReTRAIL | 63.9 | 71.5 | 75.8 | 55.2 | 63.3 | 68.0 |
With a larger budget, ReTRAIL improves by 11.9 and 12.8 points, against at most 3.7 for the baselines. Its benefit also grows with the horizon within the main benchmarks: the retry gain rises from 4.5 points on tasks with short reference solutions to 19.0 points on long ones (Appendix C.1).
ALFWorld unseen split: We additionally evaluated the same checkpoints on the unseen split (134 tasks) under the same protocol:
| Method | P@1 | T@1 | T@3 |
|---|---|---|---|
| GiGPO | 86.6 | 85.8 | 90.3 |
| LaMer | 84.3 | 85.1 | 91.8 |
| ReTRAIL | 88.1 | 90.3 | 96.3 |
All methods lose 2.2 to 5.4 points relative to the seen split, and ReTRAIL remains the best method in every column.
We trained GiGPO, LaMer and ReTRAIL on MineSweeper and Sokoban with Qwen2.5-7B and Llama-3.1-8B, which covers a larger model and a second model family:
| Model | Method | MineSweeper T@1 | MineSweeper T@3 | Sokoban T@1 | Sokoban T@3 |
|---|---|---|---|---|---|
| Qwen2.5-7B | GiGPO | 48.0 | 56.3 | 53.1 | 59.8 |
| Qwen2.5-7B | LaMer | 48.8 | 62.1 | 44.9 | 58.2 |
| Qwen2.5-7B | ReTRAIL | 55.1 | 88.7 | 61.7 | 72.3 |
| Llama-3.1-8B | GiGPO | 44.1 | 51.6 | 31.3 | 36.7 |
| Llama-3.1-8B | LaMer | 49.2 | 64.5 | 32.8 | 44.1 |
| Llama-3.1-8B | ReTRAIL | 53.9 | 85.2 | 43.0 | 58.6 |
ReTRAIL still achieve the best method in every column, with T@3 margins of 12.5 to 26.6 points.
In summary, the advantage of ReTRAIL holds on harder instances, on the unseen split of ALFWorld, and across three base models from two families.
Response to Reviewer o63W (Part 3/3)
Q2: Dependence of successful T@3 attempts on revealed mine locations
About two thirds of the successful T@3 trials succeed within the first macro-attempt and never reveal a mine (T@1 is 63.5 and T@3 is 95.3). Among the remaining third, the reflection states the location of the revealed mine in 81% of the trials, which is 27% of all successful trials. To measure the actual dependence, we re-evaluated the same checkpoints with the coordinates of revealed mines removed from the reflection and from every retained observation:
| Method | T@3 | T@3, mine locations masked |
|---|---|---|
| GiGPO | 65.5 | 63.9 |
| LaMer | 70.8 | 66.0 |
| ReTRAIL | 95.3 | 88.4 |
Masking costs ReTRAIL 6.9 points, so part of its retry gain does come from revealed mine locations. Most of the gain remains: with the locations masked, ReTRAIL is still 22.4 points above LaMer under the same masking.
Revision. We have added this analysis to Appendix C.9 (Table 12) and summarized it in §6.
Q3: Progress signals received by the RL baselines
For a fair comparison, all trained baselines receive the same environment feedback as ReTRAIL, namely the progress score of Table 14, including the search-based score on Sokoban. The only signal specific to ReTRAIL is the branch-advancement reward, which compares an abandoned branch with the branch resumed after a rewind and is therefore defined only under retrospective exploration.
Revision. We have listed the training signals of every method in Appendix D.2 (Table 15).
Q4: Training compute of ReTRAIL compared with the baselines
ReTRAIL uses no more training compute than the baselines. All methods are trained for 300 updates on 8 NVIDIA H200 GPUs, and the table reports the realized GPU-hours:
| GPU-hours for 300 updates | MineSweeper | Sokoban | ALFWorld | ScienceWorld |
|---|---|---|---|---|
| GiGPO | 441 | 482 | 186 | 359 |
| LaMer | 480 | 523 | 203 | 391 |
| ReTRAIL | 416 | 427 | 174 | 332 |
ReTRAIL samples 8 trials per task where the baselines sample 24 trajectories, and it uses 61% to 85% of their tokens. The full breakdown into model calls, tokens and evaluation cost is given in our response to Reviewer 6QEV (W1 & Q1).
Revision. We have added the full breakdown to Appendix D.3 (Tables 17 and 18).
Thank you again for the detailed and constructive feedback, which shaped most of the additional experiments in this revision. We hope these results and clarifications address your concerns, and we would be glad to discuss any remaining questions.
Response to Reviewer o63W (Part 1/3)
Thank you for recognizing that moving the environment backward while carrying knowledge forward is intuitive and clearly distinguished from multi-episode adaptation and the two learning signals fit the setting. We have marked all revisions in red in the updated PDF and respond to your concerns point by point below. Section, appendix, and table numbers refer to the revised PDF.
We thank the reviewer for this suggestion. We would first like to clarify that the GiGPO row of Table 3 is not a baseline trained with rewind. It is ReTRAIL with only State-Anchored GRPO replaced by GiGPO, and it keeps retrospective exploration and the branch-advancement reward for reflection. We agree that the baselines in Table 1 only receive rewind at test time, so we trained GRPO and GiGPO with the same rewind interface as ReTRAIL.
● Setup: During training, the baselines can rewind and write a reflection exactly as ReTRAIL does, under the same call ceiling and attempt limit.
● Baselines trained with the interface: Training with the interface improves the baselines, for example GiGPO gains 8.4 points of T@3 on MineSweeper. They nevertheless remain 21.4 points below ReTRAIL on MineSweeper and 6.5 points below on Sokoban. Having access to rewind during training is not enough: the policy also has to learn what to carry over from an abandoned branch.
The gap between GiGPO trained with the interface and the Table 3 variant (73.9 versus 90.1 on MineSweeper) comes from learning reflection through branch advancement. State-Anchored GRPO adds a further 5.2 points of T@3 and 5.9 points of T@1.
Revision. We have added the interface-trained baselines to Appendix C.3 (Table 5), referenced from §5.2, and clarified in §6 what the GiGPO variant of Table 3 retains.
We thank the reviewer for this comment. We agree that rewind changes the task setting, and we therefore report both settings.
Under P@1, which keeps the original irreversible setting of each benchmark, ReTRAIL achieves the best result on MineSweeper (58.8), ALFWorld (92.7) and ScienceWorld (56.7), and stays within 2.3 points of GiGPO on Sokoban (76.6 versus 78.9, Table 1).
T@1 and T@3 measure success in a recoverable environment, which is the setting our work targets. A revealed mine or a deadlocked box becomes a failed branch that can be reverted. Whether the agent can recognize such a branch and make use of what it revealed is crucial for autonomous execution and full exploration. Rewind does not remove this difficulty by itself: with rewind enabled, GRPO drops from 54.6 to 51.6 on MineSweeper and from 70.3 to 68.9 on Sokoban under the same protocol (Table 1). We analyze how much revealed mine locations contribute in our response to Q2.
Revision. We have clarified in §5.1 what P@1 and T@1/T@3 each measure.