acceptodds
Under review as a conference paper at ICLR 2027

Don’t Blame Your Agent (Yet): Environment-Aware Error Recovery for Long-Horizon Agents

Abstract

Long-horizon agents show promise on complex tasks that require many interdependent steps, yet reliable execution remains an open challenge. Existing approaches improve agent components through training, context management, and harness design. We study the complementary problem of online error recovery, which redirects an agent away from a suboptimal intermediate state before it produces a wrong task outcome. Online recovery is particularly important for long-horizon tasks because one error can propagate through dependent later steps. Yet recovery is difficult because an agent's expected behavior depends on environmental preconditions that it can only partially observe. A failed attempt can therefore reflect either inadequate execution or an inaccurate premise about the environment. We propose ALTER, an environment-aware strategy selection framework for online agent error recovery. ALTER separates environmental premises from the behavior expected under them, allowing it to calibrate the actor or revise a premise. A lightweight per-query DSL organizes alternative and combinable strategies, allowing ALTER to select a new strategy under the revised premise. We evaluate ALTER on three long-horizon benchmarks with three actor models, comparing it with the original agent without recovery and five error or failure recovery baselines. ALTER improves task success by 5.9–47.1 % over the original agent and by 7.1–41.2 % over the strongest environment-unaware recovery baseline, while achieving broader coverage of resolution strategies.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
long-horizon agents, error recovery, environment-aware agents

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_fcqWOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors propose a framework for long-horizon agents, designed for online recovery by selecting a strategy from a lightweight DSL and separating environmental premises from behavior. The framework was evaluated on 3 benchmarks and 3 models against the original agent work and 5 recovery baselines, and the results show improved performance over the original agents.

Critical strengths

S1: A well-motivated problem framing, and importantly, unlike the baselines, offering an evaluation on whether an agent's failure is caused by an inaccurate environmental premise S2: A clear and simple-to-follow explanation of the framework S3: In the experimental results, the proposed framework improved task success on the 3 benchmarks and 3 models shown

Critical weaknesses

W1: The results are reported without confidence intervals or paired significance tests. Adding CIs or a paired test to compare the method with the baseline to show significant success would make it stronger

S2: The scope of experiments is narrow, and the ablation, the repeat study, and the extended split each use a single model; running these on all three models, and adding more models or benchmarks, would strengthen the claims of the paper

S3: Running the framework adds additional LLM calls, especially in complex tasks, which require additional costs for the LLMs, but the authors acknowledge this as a limitation; however, baselines are not given an equal compute budget, so a cost-matched comparison would help

Questions for authors

Q1: Can you report CIs or a paired test?

Q2: As mentioned in W2, some of the experiments use only one model each; can you extend them to all three models or add additional models?

1 comment

We thank the reviewer for the constructive feedback and questions.

W1. Confidence intervals and paired tests

During the rebuttal, we additionally calculated 95% paired bootstrap confidence intervals and conducted two-sided exact McNemar tests to compare ALTER with each baseline. Differences and confidence intervals are in percentage points, with differences computed as ALTER minus the baseline. Statistical significance is assessed at the 0.05 level.

GLM-5

BaselineDiff (pp)95% CI (pp)Paired p-valueSignificant
Vanilla+24.2[12.9, 35.5]0.000729Yes
Reflexion+24.2[11.3, 37.1]0.000729Yes
FineVerify+25.8[12.9, 38.7]0.000402Yes
AgentRewind+32.3[19.4, 45.2]0.0000110Yes
COMPASS+32.3[21.0, 43.5]0.0000110Yes
PIVOT+19.4[8.1, 30.6]0.00754Yes

GPT-5.6-Terra

BaselineDiff (pp)95% CI (pp)Paired p-valueSignificant
Vanilla+26.7[11.1, 42.2]0.00754Yes
Reflexion+26.7[13.3, 42.2]0.00183Yes
FineVerify+17.8[4.4, 31.1]0.0386Yes
AgentRewind+33.3[20.0, 46.7]0.0000610Yes
COMPASS+35.6[20.0, 51.1]0.000145Yes
PIVOT+15.6[2.2, 28.9]0.0654No

Kimi-K2.5

BaselineDiff (pp)95% CI (pp)Paired p-valueSignificant
Vanilla+22.2[8.9, 35.6]0.00635Yes
Reflexion+22.6[11.3, 35.5]0.00131Yes
FineVerify+29.0[14.5, 43.5]0.000534Yes
AgentRewind+33.9[21.0, 46.8]0.0000194Yes
COMPASS+30.6[17.7, 43.5]0.0000210Yes
PIVOT+27.4[14.5, 40.3]0.000221Yes

ALTER’s advantage is statistically significant in 17 of the 18 comparisons.

W2. Experiments across all three models

During the rebuttal, we extended the repeated-run, ablation, and extended-split evaluations across all three models. The additional results are consistent with the findings in the paper.

Repeated runs

ModelVanillaPIVOTALTER
GLM-522.9%34.3%51.4%
GPT-5.6-Terra63.8%60.0%79.0%
Kimi-K2.527.6%32.4%57.1%

Ablation

ModelFull ALTERNo PlanNo Env-Aware
GLM-573.33%53.33%57.78%
GPT-5.6-Terra84.44%80.00%77.78%
Kimi-K2.568.89%66.67%60.00%

Extended splits

ModelVanillaPIVOTALTER
GLM-536.9%45.2%60.0%
GPT-5.6-Terra56.8%56.8%62.2%
Kimi-K2.531.5%45.5%66.7%

Across all three studies, ALTER achieves the best performance for all three models. This is consistent with the paper’s conclusion.

W3. Cost-matched comparison

Figure 17 discusses ALTER’s performance with respect to its cost. Across the evaluated models, ALTER achieves better performance with comparable computation budgets.

During the rebuttal, we additionally conducted a cost-matched budget analysis with the strongest baselines. Each baseline has a budget at least as large as ALTER’s. The tables report the budgets alongside pass rates from the available recorded runs.

GLM-5

TechniqueBudget (USD)Pass rate
Vanilla$4.28038.0%
PIVOT$4.66839.4%
Reflexion$6.05646.6%
FineVerify$7.90431.7%
ALTER$3.43362.0%

GPT-5.6-Terra

TechniqueBudget (USD)Pass rate
Vanilla$1.44786.1%
PIVOT$1.31282.2%
Reflexion$1.45953.4%
FineVerify$2.45965.9%
ALTER$1.27292.3%

Kimi-K2.5

TechniqueBudget (USD)Pass rate
Vanilla$1.84045.7%
PIVOT$1.91425.5%
Reflexion$2.65044.2%
FineVerify$2.81238.0%
ALTER$1.60949.5%

Across all three models, ALTER achieves the highest pass rate in this cost-matched budget analysis. These results support the contribution of ALTER’s recovery strategy alongside additional test-time computation.

Reviewer_mZxpOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces ALTER, an online recovery framework for long-horizon agents that distinguishes between poor execution under a reasonable environmental assumption and an assumption that no longer fits the observed environment. ALTER represents task strategies in a per-query DSL of alternative and composable subgoals; after an unsuccessful attempt, it either gives the agent more specific behavioral guidance or revises its environmental premise and selects another strategy. The authors evaluate ALTER on BrowseCompPlus, DeepSearchQA, and CVE-Bench using three actor models and five recovery baselines. They report that ALTER performs best in every evaluated model–benchmark setting, with gains of 5.9–47.1 percentage points over the unrecovered agent, and provide ablations, strategy-coverage analyses, cost estimates, and additional evaluation on extended splits and selected repeated runs.

Critical strengths
  1. The distinction between execution failure and a mistaken environmental premise is consequential: simply refining an agent’s behavior may not help when the route it is following is infeasible. ALTER makes this distinction actionable by pairing premises with behavior specifications and an explicit space of alternative or augmentative strategies.
  2. The paper compares against five recovery baselines across multiple task types and actor models, and includes component ablations, strategy-coverage measures, and cost reporting. The ablations support the claim that both environment-aware attribution and the strategy DSL contribute to performance, while the added analyses make the proposed mechanism more assessable than a success-rate-only evaluation.
Critical weaknesses
  1. The main evaluation uses 17 BrowseCompPlus, 28 DeepSearchQA, and 17 CVE-Bench cases. The paper first filters cases based on whether a model solves them in one vanilla attempt, and the five-repeat analysis uses only 21 selected challenging cases on two benchmarks. Without uncertainty estimates or paired significance analyses across the main evaluation, it is difficult to tell how stable the reported gains are or how broadly they generalize.
  2. Recovery is driven by an unsuccessful or incomplete trajectory, but an agent can present a plausible-looking answer without producing an observation that challenges its environmental premise. The paper’s own DeepSearchQA failure case illustrates this limitation: ALTER does not revise the premise when the agent completes an extraction and ranking over a non-equivalent data series. This matters because detecting such errors is central to reliable long-horizon execution; the paper does not establish that ALTER reliably catches incorrect but apparently complete answers.
Questions for authors
  1. Given the small, difficulty-filtered main cohorts, could you report paired, per-instance uncertainty estimates or significance tests for the main comparisons? How sensitive are the gains to the screening procedure, and can the repeated-run results be extended beyond the selected 21 challenging cases?
  2. What exact condition determines that a task is complete and ends recovery? Is every final answer independently checked against the task constraints, or can an agent’s unsupported success claim terminate the run? If the latter, how often do such silent errors occur in the evaluated data?
  3. How do the methods compare when accounting for inference cost or recovery-call/token budgets? Since ALTER adds computation, a cost-matched comparison would help establish whether its advantage reflects the recovery strategy itself, additional test-time compute, or both.
2 comments

We thank the reviewer for the constructive feedback and questions.

W1. Significance of the results

We use the two-sided exact McNemar test to compare ALTER with each baseline. Each entry below reports ALTER’s success-rate gain in percentage points, followed by the p-value in parentheses.

BaselineGLM-5GPT-5.6-TerraKimi-K2.5
Vanilla+24.2 (0.000729)+26.7 (0.00754)+22.2 (0.00635)
Reflexion+24.2 (0.000729)+26.7 (0.00183)+22.6 (0.00131)
FineVerify+25.8 (0.000402)+17.8 (0.0386)+29.0 (0.000534)
AgentRewind+32.3 (0.0000110)+33.3 (0.0000610)+33.9 (0.0000194)
COMPASS+32.3 (0.0000110)+35.6 (0.000145)+30.6 (0.0000210)
PIVOT+19.4 (0.00754)+15.6 (0.0654)+27.4 (0.000221)

ALTER’s advantage is statistically significant in 17 of the 18 comparisons at the 0.05 level.

W2. Capturing apparently complete but incorrect answers

We agree that capturing apparently complete but incorrect answers is challenging. However, this is not due to a design limitation of ALTER. Instead, it arises because the ground-truth reward signal is unavailable during online error recovery. ALTER mitigates this challenge by decomposing complex tasks into explicit strategies and goals through its strategy language, as described in Section 3.3.

During the rebuttal, we audited the evaluation trajectories to measure the percentage of all runs that presented an incorrect answer as complete.

BenchmarkVanillaALTER
BrowseCompPlus29.4%9.8%
DeepSearchQA34.5%19.0%
CVE-Bench2.9%0%
Overall26.6%12.4%

The results show that these cases constitute a minority of all evaluated runs, and ALTER further reduces their frequency. We attribute ALTER’s improvement in reducing silent errors to its explicit goal structure. ALTER’s strategy language explicitly describes the goals of a task, giving the agent clearer targets for recognizing blockers during execution and judging completion.

Q1. Significance tests and repeated runs

Please see W1 for the significance tests.

The screening process filters out trivial cases that the LLM can readily solve, typically within 20 steps and without invoking error recovery. Figure 8 illustrates a similar pattern, with ALTER’s advantage most pronounced on cases of medium to high difficulty.

During the rebuttal, we extended the five-run repeat analysis to the full evaluation split. Overall measures success across attempts, pass@5 measures success in at least one of five runs, and pass^5 measures success in all five runs.

TechniqueOverallpass@5pass^5
Vanilla71.4%89.4%44.4%
COMPASS35.5%66.4%10.7%
PIVOT67.5%90.5%34.3%
ALTER77.4%90.5%55.0%

These results are consistent with the paper and demonstrate ALTER’s better overall performance and reliability.

Q2. Silent errors and independent checks

Please see W2 for the detailed discussion of silent errors.

Both ALTER and the baselines perform online recovery without an independent ground-truth check against task constraints. Such a check would provide an additional task-correctness signal beyond the agent’s own reasoning and observed tool outputs. Neither ALTER nor the baselines receive this signal during recovery.

Q3. Cost discussion

Figure 17 discusses ALTER’s performance with respect to its cost. Across the evaluated models, ALTER achieves better performance with comparable computation budgets.

During the rebuttal, we additionally conducted a cost-matched budget analysis with the strongest baselines. Each baseline has a budget at least as large as ALTER’s. The tables report the budgets alongside pass rates from the available recorded runs.

GLM-5

TechniqueBudget (USD)Pass rate
Vanilla$4.28038.0%
PIVOT$4.66839.4%
Reflexion$6.05646.6%
FineVerify$7.90431.7%
ALTER$3.43362.0%

GPT-5.6-Terra

TechniqueBudget (USD)Pass rate
Vanilla$1.44786.1%
PIVOT$1.31282.2%
Reflexion$1.45953.4%
FineVerify$2.45965.9%
ALTER$1.27292.3%

Kimi-K2.5

TechniqueBudget (USD)Pass rate
Vanilla$1.84045.7%
PIVOT$1.91425.5%
Reflexion$2.65044.2%
FineVerify$2.81238.0%
ALTER$1.60949.5%

Across all three models, ALTER achieves the highest pass rate in this cost-matched budget analysis. These results support the contribution of ALTER’s recovery strategy alongside additional test-time computation.

After reading the authors' response, which largely addresses my concerns, I have raised my score.

Reviewer_RfSsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces ALTER, an environment-aware framework for online error recovery in long-horizon agents. The framework explicitly separates environmental premises from the behavior expected under those premises, allowing it to distinguish inadequate execution from potentially inaccurate assumptions about the environment. For each task, ALTER generates a lightweight strategy program that organizes alternative and combinable subgoals. When the agent yields without completing the task, the framework examines its trajectory and either provides more specific guidance under the current strategy or revises the environmental premises and selects another strategy. Experiments across three benchmarks covering document search, live-web research, and code auditing, using three actor models, show improvements over the original agents and five recovery baselines. Additional analyses examine strategy coverage, constraint validation, inference costs, recovery-event usefulness, and the contributions of environment-aware attribution and structured strategy selection.

Critical strengths

The authors define environmental premises as assumptions about environmental conditions that cannot be directly observed, distinguishing them from directly inspectable states and action instructions. This helps clarify what the recovery process targets.

All methods use the same underlying harness, while the recovery model and execution model are kept identical, reducing confounding effects from differences in implementation and model capability.

Policy coverage is defined over combinations of query constraints, attempting to distinguish genuine changes in approach from mere changes in search strings and thereby improving the interpretability of the metric.

Critical weaknesses

General tool-use tasks and several workspace benchmarks are also important long-horizon settings, but the experiments give insufficient attention to these tasks.

In Section 3.4, the three recovery decisions may all be applicable simultaneously, with the final choice left to the recovery model.

The recovery procedure is primarily triggered when the agent invokes yield after failing to complete the task. Its coverage therefore depends on whether the agent recognizes that execution is blocked, while the main text does not specify an independent mechanism for detecting stagnation.

Questions for authors

How is the “online error recovery” shown in Figure 1 implemented?

Please also address the concerns raised in the Weaknesses section.

1 comment

Thank you for the constructive comments on the scope of the evaluation and the clarity of the recovery mechanism.

W1. Additional workspace benchmarks

During the rebuttal period, we extended the evaluation to 120 randomly sampled cases from four additional workspace benchmarks, AppWorld, OdysseyBench, EnterpriseOps-Gym, and TheAgentCompany. We select the best-performing fault recovery and error recovery techniques from our main evaluation and report the results below.

TechniqueSuccess rate
Baseline31.7%
Reflexion36.7%
PIVOT35.0%
ALTER38.3%

These additional results support the generalization of ALTER’s gains to a broader set of long-horizon workspace tasks.

W2. Combining recovery decisions

Thank you for pointing out the ambiguity. The recovery guidance can combine behavioral refinement with revision of an environmental premise. ALTER first asks the model to reason along both directions. When both explanations are plausible, the resulting recovery decision can incorporate both a new behavioral proposal and a revised environmental premise.

For example, in the case study at lines 1324–1327, the agent revises its environmental premise to recognize that the target match information can be obtained from scorecards. It also refines its search strategy to first identify matches and then filter them by score. The recovery guidance therefore addresses both the environmental premise and the agent’s behavior in the same intervention.

We will revise the paragraph around line 260 to make this combination explicit.

W3. Recovery when the agent does not recognize blocked execution

Thank you for identifying this gap in the presentation. In addition to recovery triggered by the agent’s yield call, our implementation invokes ALTER after 50 steps without a yield call to check the execution. This fallback allows recovery to be invoked even when the agent continues acting without recognizing that it is blocked.

Empirically, yield triggers 41.6%, 65.9%, and 100% of recovery events for Kimi K2.5, GLM-5, and GPT-5.6-Terra, respectively, in our evaluation. We will clarify the 50-step fallback in the main text.

Q1. Online recovery in Figure 1

The two online recovery methods shown in Figure 1 are ALTER, shown in orange, and PIVOT, shown in blue. PIVOT is the best-performing error recovery baseline in that comparison. We will explicitly identify both methods in the text accompanying Figure 1.

Comments on the paper

1 comment
Area_Chair_QM2EOpenReview ↗

Please engage in the discussion

Reviewers: if you have not responded to the authors' reply, please read it and engage in the discussion. Thanks!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.