PaperlayerView exact revision on arXiv

Source-linked AI summary

AgentRewind: Recoverable Execution for Long-Horizon LLM Agents

Yu Zhuang, Kefei Chen, Yitong Duan, Shuxin Zheng, Jian Li, Xu-Yao Zhang

arXiv:2608.14380v1cs.AI

TL;DR

Long-horizon LLM agents lack adequate recovery when early errors disrupt execution. AgentRewind restores aligned checkpoints of agent context and controlled environment state while retaining information from previous attempts, and improves task success and checklist progress across evaluated settings.

  • Problem

    Existing long-horizon agent methods emphasize plan refinement and safety checks but provide inadequate recovery after errors disrupt execution.

  • Method

    AgentRewind records aligned checkpoints of agent context and controlled environment state, then restores a selected checkpoint with rewind memory for continued execution.

  • Results

    Across benchmarks, models, execution strategies, and agent harnesses, AgentRewind improves task success rate and average checklist progress over compared baselines.

  • Takeaways & Limitations

    Runtime recovery remains effective across evaluated long-horizon settings and models with substantially different baseline performance.

  • Takeaways & Limitations

    AgentRewind restores only controlled state, so effects outside the workspace filesystem, including network requests and external-service calls, cannot be undone.

Abstract

from arXiv · show

Many real-world tasks require LLM agents to interact with their environments over long execution horizons. Errors that occur early in execution may propagate through both the agent context and environment state, and their effects may be difficult to reverse through subsequent actions. Existing methods mainly seek to reduce such errors through plan refinement and safety checks but provide little support after errors occur. To enable recovery during long-horizon execution, we present AgentRewind, a runtime recovery framework that records aligned checkpoints of the agent context and controlled environment, allowing agents to return to an earlier state and resume execution with information from previous attempts. We also construct MettleBench, a benchmark for evaluating task completion and partial progress on long-horizon engineering assignments containing a series of related requirements. Experiments across tasks, multiple models, execution strategies, and agent harnesses show that AgentRewind improves task success rate and average checklist progress over the compared baselines.

Introduction

Long-horizon LLM agents face increasing failure risk because early planning and execution errors can degrade subsequent actions and environment state. AgentRewind addresses this by restoring aligned agent-context and environment checkpoints, while MettleBench evaluates completion and partial progress on multi-requirement engineering tasks.

  • Motivation: Early planning mistakes and environment damage can send subsequent actions in the wrong direction or prevent task completion.Examples include deleting critical files, corrupting configurations, and contaminating database states; longer trajectories increase exposure to such errors.
  • Motivation: Existing approaches use plan refinement before execution and safety checks during execution, but cumulative failure risk still grows across long horizons.Plan refinement seeks more effective execution paths, while safety checks detect unsafe behavior during execution.
  • AgentRewind: AgentRewind restores both agent context and environment state to a selected earlier checkpoint when the current trajectory is unlikely to make further progress.It retains a summary of the previous attempt and enables continuation from the restored checkpoint.
  • MettleBench: MettleBench evaluates task completion and checklist progress on real-world engineering assignments containing a series of related requirements.The benchmark is designed for long-horizon engineering tasks with multiple related requirements.
  • Evaluation: AgentRewind improves task success rate and average checklist progress across multiple base models, execution strategies, and agent harnesses.The evaluation targets long-horizon settings and varies models, execution strategies, and harnesses.

Related Work

Related work spans long-horizon agent benchmarks, reliability methods, feedback-based improvement, rollback systems, and low-level checkpointing. AgentRewind combines coordinated agent-context and environment restoration with rewind memory for agent-level recovery during long-horizon execution.

  • Long-Horizon Agent Benchmarks: Long-horizon agents have been evaluated in embodied, scientific, web-based, interactive programming, and repository-level software engineering settings.Examples include ALFWorld, ScienceWorld, WebShop, InterCode, and SWE-bench.
  • Agent Reliability: Reliability methods improve execution through action generation, reasoning, planning, search, environment models, and safety monitoring for risky behavior.The passage identifies ReAct, SayCan, LATS, and safety-oriented monitoring methods as examples.
  • Learning from Previous Attempts: Self-Refine, Reflexion, ExpeL, and failure-analysis methods use information from prior executions to revise decisions or diagnose completed trajectories.These methods improve later behavior but provide little support for recovery during execution.
  • Rollback for LLM Agents: Rollback research includes stepwise recovery, browser-specific rollback, and semantically valid restore-point selection, with DART limited by explicit control flow and recovery boundaries.GA-Rollback targets replayable environments, WebRollback targets browser navigation, and DART targets structured tool agents.
  • System-Level Checkpointing: System checkpointing tools restore process state, while DeltaBox enables efficient filesystem and process rollback in agent sandboxes but remains low-level.The passage contrasts these mechanisms with an agent-level recovery process for long-horizon execution.
  • AgentRewind: AgentRewind coordinates restoration of agent context and environment state with rewind memory, enabling continuation from earlier checkpoints using information from previous attempts.This mechanism addresses the gap between low-level rollback and agent-level recovery.

AgentRewind Framework

AgentRewind adds runtime recovery to long-horizon agent execution by recording aligned checkpoints of agent context and controlled environment state. When progress fails, it restores a selected checkpoint, injects rewind memory, and resumes from a new continuation, while workspace recovery excludes effects outside the filesystem.

  • Checkpoint Recording: At each LLM decision boundary, AgentRewind records a recoverable execution checkpoint and metadata describing the segment before the next LLM output.The metadata presents possible rewind locations to the agent.
  • Rewind Selection: When the current trajectory can no longer make progress, the agent selects a historical checkpoint and generates rewind memory from the current trajectory.Selection uses the agent context and checkpoint metadata list; accumulated memories are added to historical rewind memories.
  • Checkpoint Recording: AgentRewind operates as a runtime layer that transparently records the agent trajectory and aligns context records with controlled-environment changes into recoverable checkpoints.These checkpoints support joint recovery of agent context and controlled environment state.
  • Rewind Execution: During rewind, AgentRewind terminates current execution, restores the selected environment and context, injects accumulated rewind memory, and generates a new suffix.Prior LLM outputs and tool results are restored from the execution log rather than regenerated or re-executed.
  • Recovery Scope: Workspace recovery reverts later file modifications, restores deleted files, and removes newly created files, but cannot undo network requests, external-service calls, or external runtime state.The controlled environment is the workspace directory tree, locally or in an isolated container.

MettleBench

MettleBench evaluates long-horizon engineering assignments as ordered checklists of interdependent acceptance criteria, distinguishing complete success from prefix-based partial progress. It contains 82 executable tasks derived from five engineering benchmarks, with hidden checklists and feedback revealing only the first unsatisfied item.

  • Task formulation: MettleBench models each task as an instruction, initial environment state, agent decision space, and ordered acceptance criteria.Each criterion is a binary evaluation function over environment states.
  • Task formulation: Task success requires the final environment state to satisfy all acceptance criteria.The benchmark therefore treats completion as an all-criteria condition.
  • Progress metric: Checklist prefix progress measures the longest ordered prefix of criteria satisfied in the final state, distinguishing partial progress from full completion.The prefix length ℓ ranges from 0 to n.
  • Benchmark construction: 82 tasks comprise MettleBench, drawn from Terminal-Bench 2.0, ProgramBench, SWE-bench, ProjectEval, and GitTaskBench.The benchmark retains the underlying engineering artifacts and executable task environments.
  • Benchmark construction: Each rewritten instruction uses a hidden, ordered checklist of interdependent acceptance criteria implemented as executable checks.The natural-language instructions express a series of related requirements within each assignment.
  • Evaluation protocol: After each submission, checks run in predefined order and return feedback identifying only the first unsatisfied checklist item.Criteria share one environment state, so later actions can enable, hinder, or invalidate previously satisfied criteria.

Experiments

Experiments evaluate AgentRewind on MettleBench and Terminal-Bench 2.0 using task success and partial-progress measures, comparing forward execution, recovery strategies, harnesses, horizons, and ablations. AgentRewind consistently improves outcomes, especially when execution becomes prolonged or repeatedly failing, with environment rewind providing the largest ablation benefit.

  • Evaluation setup: MettleBench evaluation measures task success rate and average checklist progress without preset limits on wall-clock time, execution steps, or total token usage.A run terminates after an acceptance criterion is met in five consecutive submissions.
  • Forward-execution baselines: Under Continue, task success rates range from 28.0% to 73.2%, with Qwen3.7-Max highest and Kimi K2.5 lowest on task success and checklist progress.No model saturates MettleBench, leaving room for improved execution strategies.
  • Forward-execution baselines: Average checklist progress complements binary task success: unsuccessful GPT-5.4 and GLM-5.1 runs average 50.8% and 38.1%, respectively.The models achieve similar task success rates, but GPT-5.4 attains higher average checklist progress.
  • Execution-strategy comparisons: AgentRewind achieves the highest final task success and checklist progress under both GPT-5.4 and GPT-5.4 mini, outperforming the strongest baseline in every setting.Continue plateaus earliest after persistent failures, while AgentRewind continues improving and shows fewer progress regressions than Restart with Experiences.
  • Generalization and horizon effects: AgentRewind’s advantage over the strongest baseline is modest for short horizons but substantially larger for medium- and long-horizon tasks.On Terminal-Bench 2.0, AgentRewind also outperforms Continue and Restart with Experiences on task success and partial completion.
  • Robustness and ablations: AgentRewind improves task success and average checklist progress across all three harnesses, while removing environment rewind causes the largest degradation among ablations.The framework also improves recovery rate and checklist progress change over Continue from repeatedly failing states.

Conclusion … A.3 Checklist Statistics

The paper introduces AgentRewind for runtime recovery and MettleBench for evaluating long-horizon engineering agents. MettleBench uses structured, dependency-aware tasks with deterministic quality gates and machine-readable checklists.

  • Conclusion: AgentRewind restores aligned checkpoints of agent context and environment state while retaining information from previous attempts.The framework targets recovery during long-horizon execution.
  • A.1 Task Sources and Composition: MettleBench contains 82 long-horizon engineering tasks derived from five existing benchmarks.The benchmark preserves the original engineering artifacts and executable environments while rewriting specifications and acceptance criteria.
  • A.2 Provenance of the Acceptance Criteria: Each benchmark task is an engineering assignment with ordered, interdependent objectives and criteria tied to a shared environment state.The protocol excludes artificial difficulty such as forced waiting, unnecessary serial work, unknowable values, and dependencies on unavailable options.
  • A.2 Provenance of the Acceptance Criteria: An LLM agent generated each task instruction, ordered checklist, executable criterion check, forward-only reference solution, and dependency-ignoring reference run.The second reference run tests whether violating criterion dependencies causes the expected failure.
  • A.2 Provenance of the Acceptance Criteria: Three deterministic gates admit tasks only when the reference solution passes every criterion, the order-violating run fails at the removed precondition, and the shipped workspace is unsolved.These gates validate solvability, dependency sensitivity, and nontrivial initialization.
  • A.2 Provenance of the Acceptance Criteria: Human review assessed task naturalness, source fidelity, verifier fairness, absence of contrived mechanisms, and four additional dimensions scored from 1 to 5.Dimension means ranged from 3.65 to 5.00, and every reviewed task was accepted.
  • A.3 Checklist Statistics: Each task carries between 5 and 12 ordered criteria, with a mean of 7.80 and median of 7, totaling 640 criteria.The checklist statistics are reported in Table 7.

A.4 Every Task Has a Forward-Only Solution That Satisfies All Criteria at Once

Each of the 82 tasks has an executable forward-only reference solution that satisfies all acceptance criteria in one pass. These solutions establish that recovery is not required for solvability, while model evaluations show substantial task coverage.

  • Reference solutions: All 82 tasks have executable forward-only reference solutions averaging 79.3 non-empty lines, with no rollback or retry.Lengths range from 16 to 220 lines, with a median of 71.
  • Reference solutions: Every reference solution satisfies all acceptance criteria simultaneously in a single forward pass.The solutions were rerun against fresh workspaces in a clean environment before full evaluation.
  • Validation: Independent construction checks confirm that reference solutions pass, while order-violating executions and shipped workspaces fail.Order-violating runs fail at the criterion whose precondition they remove.
  • Model evaluation: At least 70 of 82 tasks were solved by some model under Continue, and at least 79 under some execution strategy.All 82 tasks were evaluated with seven base models under Continue; two GPT-5.4 variants also used three other strategies.

A.5 Evaluator Determinism and Repeatability … B.1 Setup of the Base-Model Comparison

The paper establishes deterministic evaluation, measures end-to-end repeatability, defines demanding long-horizon task criteria, illustrates checklist-based progress scoring, and specifies a controlled base-model comparison. These details clarify both benchmark construction and experimental comparability.

  • A.5 Evaluator Determinism and Repeatability: Each evaluator is plain Python inspecting final workspace state, with no LLM judgment; auditing all 82 found no random draws, network access, or generated UUIDs.Two evaluators read the wall clock, while the sole UUID reference parses a fixed constant.
  • A.5 Evaluator Determinism and Repeatability: Identical final states receive identical verdicts and feedback because each evaluator checks criteria in a fixed order and reports the first unsatisfied criterion.
  • A.5 Evaluator Determinism and Repeatability: 490 of 656 task-strategy-model triples (74.7%) reached agreement across three independent runs, with agreement requiring identical success-or-failure verdicts.The comparison comprised eight cells, four strategies, two models, and 82 tasks per cell.
  • A.5 Evaluator Determinism and Repeatability: The remaining 25.3% disagreement is an upper bound on evaluator-attributable variation, also encompassing agent trajectories, tool outputs, and filesystem timing.The bound is loose, especially in Safety Review cells involving an external monitor.
  • A.6 Long-Horizon Screening Criteria: Long-horizon tasks were required to meet four structural conditions so that tasks would not collapse into a single requirement.
  • A.6 Long-Horizon Screening Criteria: Each task requires at least four sequential stages, later deliverables quoting runtime-produced earlier values in at least two places, plus sequential defect repair or an equivalent dependency.
  • A.7 Worked Example: Task Prompt and Checklist: The worked security-incident task hides an ordered checklist, gives feedback only for the first unsatisfied criterion, and uses one repository for all criteria.The example is derived from Terminal-Bench and combines a visible task instruction with a hidden checklist.
  • A.7 Worked Example: Task Prompt and Checklist: Checklist-progress scoring distinguishes runs that stop at P03, fail at the first criterion, or satisfy more criteria, while premature credential removal can permanently prevent P04.

B.2 Setup of the Execution-Strategy Comparison · B.3 Execution Strategies · B.4 Setup of the Recovery Comparison

The experiments compare four execution strategies under controlled settings, differing only in post-rejection behavior, and separately evaluate recovery from identical failed Continue endpoints. AgentRewind preserves execution history while enabling selective checkpoint restoration and resumption.

  • B.2 Setup of the Execution-Strategy Comparison: The main comparison evaluates four execution strategies under GPT-5.4 and GPT-5.4 mini using shared environments, tools, decoding, and termination conditions.All configurations use greedy decoding at temperature 0.0 and were executed three times with identical settings.
  • B.2 Setup of the Execution-Strategy Comparison: The Terminal-Bench 2.0 experiment compares Continue, Restart with Experiences, and AgentRewind across 89 tasks.Partial completion is the average fraction of satisfied criteria, distinct from MettleBench checklist progress.
  • B.2 Setup of the Execution-Strategy Comparison: The harness comparison replaces mini-SWE-agent with FnCallAgent or CodeAgent and compares Continue with AgentRewind on the same 82 tasks under GPT-5.4.Rewind tools are presented according to each framework’s expected tool format.
  • B.3 Execution Strategies: Continue appends rejection feedback to the trajectory while preserving the process, message history, and workspace, with no rewind capability.A run ends on success or after five consecutive submissions fail at the same criterion.
  • B.3 Execution Strategies: Restart with Experiences begins each post-rejection attempt from a pristine workspace and empty history, carrying forward only an accumulating file of evaluator-derived failure experiences.The record includes feedback, log excerpts, satisfied prefixes, regressions, and outcome counts.
  • B.3 Execution Strategies: Safety Review behaves like Continue after rejection but uses a separate local monitor model before each tool call to judge whether the proposed action is safe.Unsafe actions are blocked, and the agent receives an observation requiring it to work around the block.
  • B.3 Execution Strategies: AgentRewind adds backtrack_candidates and backtrack_commit alongside the shell tool, allowing the agent to repair in place or return to a chosen checkpoint.A committed rewind restores the recorded agent context and workspace state while discarding subsequent execution.
  • B.4 Setup of the Recovery Comparison: The paired recovery comparison launches two arms from identical copies of a failed Continue endpoint, differing only in whether rewind is available.Each endpoint is produced by running Continue until termination under the repeated-failure condition.

B.5 Setup of the Component Ablation · B.6 Exact Values of the Execution-Strategy Comparison · B.7 Manual-Intervention Audit of the Formal Runs

The appendix specifies controlled component-ablation variants, clarifies how execution-strategy results and horizon groups are measured, and audits manual interventions in formal runs. The audit reports that interventions handled blocked shell processes without changing agent decisions, task states, or verdicts.

  • B.5 Setup of the Component Ablation: The ablation removes environment rewind, context rewind, or rewind memory while retaining the other rewind-module settings.Without environment rewind, the workspace remains in its prerewind state; without context rewind, the agent context remains in place; without rewind memory, no discarded-attempt summary is restored.
  • B.6 Exact Values of the Execution-Strategy Comparison: Table 13 reports task success and checklist progress at run termination, averaging independent runs with standard deviations across runs.Task success is the percentage of 82 tasks satisfying every acceptance criterion, while checklist progress is the mean task-level prefix progress ρ(sT).
  • B.6 Exact Values of the Execution-Strategy Comparison: Figure 3’s gain annotations are read at the cutoff, whereas Table 13 values are computed after runs terminate, so the two comparisons can differ slightly.Some runs terminate beyond the cutoff.
  • B.6 Exact Values of the Execution-Strategy Comparison: Figure 4’s horizon groups are cut at the tertiles of each model’s own Continue trace-length distribution, making the partitions model-specific.The groups are not one fixed partition of the 82 tasks.
  • B.7 Manual-Intervention Audit of the Formal Runs: The formal batches recorded four manual interventions, each terminating a shell child process blocked on standard input.Examples included a bare interactive interpreter and an interactive migration confirmation; unlimited shell timeouts prevented automatic termination.
  • B.7 Manual-Intervention Audit of the Formal Runs: Affected tasks were marked not clean and rerun cleanly before aggregation, with only the blocked child process group terminated.The intervention procedure preserved the formal aggregation workflow.
  • B.7 Manual-Intervention Audit of the Formal Runs: No intervention changed an agent decision, task state, or verdict.This conclusion follows the manual-intervention audit of the formal runs.

C Implementation of the Runtime Recovery Layer … C.5 What Is Not Rolled Back

AgentRewind integrates with agent harnesses through LLM and tool-call hooks, records execution nodes, and resumes rewound attempts in fresh processes using persisted context and workspace state. Its recovery boundary is limited: effects outside the workspace and repository history inside .git directories are not automatically undone.

  • C.1 Harness Adaptation: AgentRewind attaches only at LLM and tool calls, capturing completions through the client entry point and tool executions through a wrapper.The wrapper receives the tool name, JSON arguments, and execution function; harness-specific integration avoids modifying the adapted framework.
  • C.1 Harness Adaptation: Harnesses expose two rewind tools using shared JSON Schema guidance, represented as function calls in mini-SWE-agent and FnCallAgent and as Python in CodeAgent.CodeAgent also requires the rewind signal to use a BaseException subclass so it passes through ordinary exception handling; integration required 150–300 lines per harness.
  • C.2 The Execution Record: Each LLM or tool call is a node serialized as one JSON-line record with a shared envelope containing an identifier, kind, and canonicalized-input hash.LLM records include requests, model parameters, tool schemas, responses, and token usage, while tool records capture tool execution information.
  • C.3 Rewind Execution: A rewind raises an exception that the runner catches outside the agent session, persisting the target node and resume context before restarting as a fresh process.The new process receives only file locations through environment variables and reconstructs state from written records because in-memory state does not survive.
  • C.4 Workspace Snapshot and Restore: Only tracked workspace paths participate in restoration, defining the recovery boundary as the workspace directory tree.This boundary is implemented through the snapshot and restore treatment of path classes.
  • C.3 Rewind Execution: The retained execution prefix is restored from the execution log rather than regenerated or re-executed.The runner writes the information needed for the next attempt into small files alongside the log, then the restarted process rebuilds its state from those files.
  • C.4 Workspace Snapshot and Restore: Workspace snapshots use an external bare Git repository and private index driven by low-level Git commands, keeping the live workspace separate from both the snapshot repository and any task repository.The repository writes objects and commits without checking out the workspace.
  • C.5 What Is Not Rolled Back: Network requests, external-service calls, and state in outside processes survive rewinds, while .git directories are skipped by the workspace snapshot.Copies of workspace-internal .git directories are kept separately so repository history can be restored.

D Statistical Significance · D.1 Sensitivity Checks

The paper evaluates AgentRewind against baselines using task-level paired Wilcoxon signed-rank tests over 82 tasks, finding broad improvements and eleven of twelve Holm-corrected comparisons significant. Sensitivity checks show that conclusions remain supported under alternative pairing and binary-outcome analyses.

  • D Statistical Significance: Two-sided Wilcoxon signed-rank tests compare AgentRewind with each baseline separately by model and metric.The metrics are task success and checklist progress.
  • D Statistical Significance: The pairing unit is the task (n = 82), with repeated runs aggregated before pairing under identical runs for both arms.Task success is the fraction of runs solved, while checklist progress is mean prefix progress across runs.
  • D Statistical Significance: Table 15 reports W, non-zero differences n̸=, Holm-corrected p-value, and matched-pairs rank-biserial correlation r.The p-value is corrected across the twelve tests in the table.
  • D Statistical Significance: Eleven of the twelve comparisons remain significant at α = 0.05 after Holm correction, with effect size r between 0.34 and 1.00.The reported exception is task success against Restart.
  • D Statistical Significance: All twelve comparisons favor AgentRewind across the baselines and metrics reported in Table 15.The table uses task-level aggregation and same-run pairing for both comparison arms.
  • D.1 Sensitivity Checks: Individual-run pairing makes every comparison significant at α = 0.05 without correction, with largest p = 8.6 × 10−3.The paper notes that individual-run pairing is too ready to declare significance and therefore reports task-level analysis instead.
  • D.1 Sensitivity Checks: Mc-Nemar’s test is additionally applied to pooled runs because task success is binary within a run.The passage identifies this as the standard test for paired binary outcomes but does not provide its result.
Loading 2608.14380v1…