acceptodds
Under review as a conference paper at ICLR 2027

Budget-Aware Counterfactual Recovery for Long-Horizon AI Agents

Abstract

Long-horizon AI agents act through learned policies, tools, and external environments, but the action proposed by a base agent can be unreliable and runtime self-correction is not free. An external reliability controller can challenge a suspect action by restoring the current state, executing alternative recoveries, and comparing their realized continuations before committing. Because these counterfactual checks consume model, tool, and environment resources, they cannot be applied indiscriminately. We study when an agent action is worth challenging under a finite fork-execution budget, while tracking replay and critic costs separately, and learn state-conditioned recovery value for budget-aware runtime intervention. In a fault-injected tool-agent sandbox with noisy diagnostics, learned allocation raises held-out episode success from 9.3% without runtime forks and 14.1% with equal allocation to 17.0% at a fork budget of 12. The same learned allocation idea transfers to Taxi-v4 without latent-state access: at budget 24 it improves deadline-constrained success over direct execution by 13.9, 10.1, and 6.5 percentage points at action-error rates 0.10, 0.20, and 0.30 while using fewer forks than a hand-designed reserve-aware policy; the 0.40 condition is inconclusive and reserve-aware retains higher success overall. On a pre-locked 24-task ALFWorld OOD set with Gemini 3 Flash, direct execution succeeds on 21/24 tasks and selective recovery policies on 22/24, with fewer interventions than fixed forking but no population-level superiority claim. We then freeze an agent-specific learned challenge model on the development set and evaluate it on a second untouched 24-task OOD set with exact repeated base-policy prompts shared across methods. Direct, reserve-aware, and learned challenge each succeed on 23/24 tasks; learned challenge uses 1.50 forks per task versus 2.50 for reserve-aware, but does not rescue the sole direct failure and incurs 16.75 replay steps versus 14.92. Recovery can also harm otherwise successful trajectories, and fewer forks need not imply lower total runtime cost when restoration requires replay. The evidence supports counterfactual challenge as a bounded inference-time reliability mechanism rather than an unlimited local repair operation.

Primary area:
reinforcement learning
Keywords:
long-horizon AI agents, runtime self-correction, counterfactual challenge, budget-aware recovery, test-time computation, agent reliability, reinforcement learning

Reviews

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

This paper studies the question of when a runtime controller should spend a limited budget to challenge an agent’s proposed action. This is called “forking” in which a controller can either trust the agent or restore the current state, and try the proposed action as well as an alternative, choosing the better option overall. The authors use learned estimates to allocate challenges across a trajectory and evaluate on a controlled fault sandbox, Taxi-v4, and ALFWorld. They find a learned allocation improves success over direct execution in the first two settings, but does not beat a hand-designed policy in Taxi success and does not improve task success over direct execution in the ALFWorld.

Critical strengths

The intervention that this paper presents is straightforward and simple to understand. Before taking an action, a separate controller can either trust the agent or restore the current state, try the proposed action and an alternative, compare what happens, and choose one. These “forks” are limited in number so the controller must learn where to spend them.

Critical weaknesses

This paper is difficult to read and the general writing style seems like LLMs may have been used too much in the writing process. For instance, I have found that one action that LLMs tend to take in writing up results is simply listing a series of numbers that the readers probably would not care about (e.g. many of the numbers in line 22-33 are not important for a reader to immediately know). The authors are encouraged to clean up the writing and make the most important points more evident.

Additionally, the empirical contribution is difficult to assess against existing methods. Although the paper discusses selective reflection, verifier-guided action selection, and learned allocation of agent compute, the experiments do not compare against representative techniques from those lines of work or explain clearly why such comparisons are infeasible. The gains are confined largely to controlled settings and Taxi. In the better-controlled ALFWorld evaluation, the learned controller does not improve task success or total runtime cost over direct execution. As a result, the paper does not establish that this method offers any advantage.

Questions for authors

N/A

1 comment

Thank you for the close read. You are right about the writing, and the abstract is the worst of it. It lists success rates for the sandbox, for Taxi at three error rates, and for two ALFWorld sets, one after another, before the reader knows what the paper is for. We have rewritten it for the revision. It now carries two numbers: the Taxi gain over direct execution at error rate 0.10, and the ALFWorld result that all three methods finish 23/24. Everything else moves to the results section. The introduction has been rewritten the same way: it opens with a concrete case — a tool agent about to run a destructive command in a sandbox — states the scope limit about irreversible actions in the second paragraph, and states the narrowed contribution in one paragraph. We have also removed the orphan bibliography entry for Kim et al. on agentic test-time compute, which was listed but never cited.

You are right that the paper discusses selective reflection, verifier-guided selection, and learned allocation without comparing against any of them. VeGAS is the closest: it samples 16 candidate actions and picks the one a generative verifier scores highest, without running any of them. We did not run it head-to-head. It does not run on our locked 24-task ALFWorld set or on Taxi at a matched fork budget without a rebuild, and a rebuild inside a rebuttal would be a new method, not a baseline. We ran that ablation. Score-only also finishes 23/24, with the same sole failure, 0 forks and 0 replay, but 5,711.8 tokens per task against 5,347.1 for executed branches, 24 challenges against 18, and 2 overrides against 5. Executing the branches adds no success on this set; with 24 tasks and one direct failure, that is an exploratory null. The revision will also add a Related Work paragraph for each of CATTS, VeGAS, CHILL-Harness, AgentCheck, and EvoHarness-RL, saying what each does and where this paper differs. That does not replace a head-to-head. It stops the paper reading as if those methods did not exist.

Your summary of where the gains sit is accurate. They sit in the controlled sandbox and in Taxi against direct execution and equal allocation. The sandbox gives 17.0% success against 14.1% for equal allocation and 9.3% for direct execution at a fork budget of 12, but that is a controlled setting with noisy diagnostics, and it does not carry the paper on its own. On Taxi, the learned controller beats direct execution by 13.9, 10.1, and 6.5 points at error rates 0.10, 0.20, and 0.30, and loses to reserve-aware by 3.4, 4.1, 5.1, and 5.4 points. At matched fork counts it never beats reserve-aware; the full table is in our reply to Reviewer pWNY. The better-controlled ALFWorld test shows no success gain and no total-cost gain: 23/24 for all three methods, with replay rising from 14.92 to 16.75 steps per task even as forks fall from 2.50 to 1.50.

We will not dress that up. The revision will frame the ALFWorld result as a null result with a cost breakdown, and the Taxi result as a win over direct execution and over a harmful baseline, not over the best hand rule. Four changes carry that framing: the rewritten abstract and introduction, the matched-fork table added to the Taxi section with reserve-aware named as the best rule for success, the ALFWorld cost table in the main text (forks, replay, critic calls, tokens), and the Related Work paragraphs above. If that leaves the paper thinner, it also leaves it accurate, and we would rather submit the thinner accurate version.

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

This paper studies when an AI agent should spend additional resources checking its proposed actions during long-horizon tasks. The authors introduce a runtime controller that can checkpoint the environment, execute alternative actions, compare their outcomes, and decide which action to commit. Since these operations are costly, the paper uses learned estimates and dynamic programming to allocate a limited execution budget across different decision points.

The method is evaluated in a synthetic tool-agent environment, Taxi-v4, and ALFWorld with Gemini 3 Flash. The results show some improvements over direct execution in the synthetic environment and Taxi-v4, although the learned method performs worse than a hand-designed heuristic in Taxi-v4. In ALFWorld, the proposed method reduces the number of fork executions but does not improve task success. It also introduces additional replay costs, leaving its overall efficiency benefits unclear.

Critical strengths
  1. The authors evaluate their method in both synthetic and public benchmark environments, including ALFWorld with a real LLM agent. They also consider different sources of runtime overhead, such as fork executions and replay costs, rather than relying solely on task success rates.
Critical weaknesses
  1. The research problem is overcomplicated and not well motivated.

My main concern is that the paper makes a relatively straightforward problem unnecessarily complicated. The core question is simply when an agent should spend additional resources checking its actions under a limited budget. However, the authors introduce a rather elaborate framework around this question without clearly explaining why this particular formulation is important. I get the impression that the authors started with a collection of existing technical components and then constructed a narrowly defined research problem around them, rather than starting from a meaningful practical challenge. I am not convinced that the paper identifies a sufficiently important problem to justify this level of complexity.

  1. The methodological novelty is limited.

Most of the technical components used in this paper are already well established, including checkpointing, counterfactual execution, risk-based intervention, and dynamic programming for budget allocation. The authors acknowledge these limitations in the introduction, but I still find it difficult to identify a substantial new technical contribution beyond combining these existing ideas. In particular, the learned challenge model in ALFWorld predicts whether a critic would overturn an action, rather than whether the intervention would actually improve task success. This further weakens the connection between the proposed method and the reliability problem it claims to address.

  1. The experimental results are not strong enough to support the claimed contribution.

The experimental results are not particularly convincing. In Taxi-v4, the learned allocator does not outperform the hand-designed reserve-aware baseline in task success. More importantly, in ALFWorld, the proposed method achieves exactly the same success rate as direct execution (23/24 tasks). Although it reduces the number of forks compared with reserve-aware, it also increases replay costs. Therefore, the experiments do not demonstrate a clear improvement in either task reliability or overall runtime efficiency. The positive results from the synthetic environments are not sufficient to compensate for this lack of improvement in the LLM-agent setting. Overall, I am not convinced that the experiments establish the practical value of the proposed framework.

Questions for authors
  1. Could the authors provide a concrete practical scenario where the proposed framework is necessary, and explain why simpler existing methods would not be sufficient?

  2. Given that the proposed method does not improve task success in ALFWorld and introduces additional replay costs, what is its main practical advantage over direct execution or simpler heuristics?

1 comment

Thank you for the direct criticism. You are right that the paper makes a simple question sound complicated. The question is: when is it worth spending limited compute to check an action before committing to it? The paper answers it with a learned controller, a DP, a calibration model, and four environments, and it never stops to say why that much machinery is needed. Part of the answer is that the machinery is not all needed. The DP buys fork savings at a success cost: against a myopic version of the same controller it loses 3.4, 2.7, 3.5, and 3.9 points at cap 24, while cutting forks by 65–78%. The revision will cut the framing down to what the experiments support: a runtime that can restore a state and run two branches, a rule for when to pay for that, and a cost account that includes replay. It will lead with one concrete case — a tool agent about to run a destructive command in a sandbox — instead of a general claim about long-horizon reliability.

We do not claim checkpointing, counterfactual execution, risk-based intervention, or dynamic programming as new. The paper says that on page 1, and we mean it. The one narrower thing we claim is timing plus execution: a challenge made before commitment, from the same live state, with the competing branches actually run and compared, under a budget shared across the whole trajectory. VeGAS scores candidates without executing them. CATTS gates on vote disagreement. CHILL-Harness estimates advantage and changes workflows. LATS searches whole trajectories. None runs two branches from a restored state and prices the replay. That distinction is thin, and we know it. It is the whole novelty claim, and the revision will present it as such, in one paragraph. We will also add the missing citations, CATTS in particular: its gating rule — spend only where the decision is contentious — is the same idea as ours, with a different currency.

You caught the weakest link in the ALFWorld part. The learned model predicts whether the critic would overturn the base action. It does not predict whether the intervention improves the task. It was fitted on 86 audited states with 16 overturns, and its leave-one-game-out AUC is 0.687. That is a weak signal, and a weak signal cannot carry a reliability claim. The revision will say so in the results section, next to the numbers, not only in the limitations.

We agree with your reading of the experiments. On Taxi, the learned controller beats direct execution and loses to reserve-aware; at matched fork counts it never beats reserve-aware (see our reply to Reviewer pWNY). On ALFWorld, the second locked set gives 23/24 for direct, reserve-aware, and learned alike, with 0 rescues and 0 harms. The learned controller uses fewer forks (1.50 per task against 2.50) and fewer critic calls (0.75 against 1.25), but replay rises from 14.92 to 16.75 steps per task, and tokens fall from 5,579 for direct and 5,475 for reserve-aware to 5,347 for learned. Put together, that is not an efficiency win. It is a fork saving paid for in replay. The revision will report forks, replay, critic calls, and tokens in one table and call the result what it is: no success gain, no total-cost gain.

On the figure, thank you for raising it directly. Figure 1 was not made by a generative image model. The data figures were drawn by a Python script, figures/main/make_main_figures.py, using matplotlib: every plotted value comes from a source CSV in the same folder. The architecture schematic exists as an editable SVG with 20 editable text elements and Inkscape 1.4.4 metadata, and it was revised by hand on Sep 1–2, 2026. The paper's AI Use Statement already says generative AI tools assisted with manuscript drafting, language polishing, literature retrieval, software and figure preparation, and result interpretation, and that the authors verified the results and take responsibility for the content.

That disclosure was in the paper, but the figure still looks schematic and unpolished, and we understand why a reader would doubt it. Two things went wrong on our side. The schematic was assembled from script output and hand edits in a way that left no visible trace of the hand work. And the statement says AI assisted with figure preparation without saying which figures, or how. We will fix both: a provenance note in the supplement listing, for each figure, the script or file it came from and what was edited by hand; and a redrawn Figure 1 with cleaner labels and spacing, built as a plain editable SVG. We will post the redrawn figure as a revised PDF during discussion. We are not asking you to withdraw the flag on our word alone. The script, the SVG, and the source CSVs are in the supplementary material, and they can be checked.

Reviewer_pWNYOpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper asks when an agent should test an alternative action before continuing. When the agent proposes an action, the system can try that action and one alternative in saved copies of the environment, then let a critic pick the better outcome. Since these checks cost resources, the authors train a controller to decide when to use them. They test this in a small controlled simulator, a simulated tool environment, the Taxi game, and ALFWorld with Gemini 3 Flash.

Critical strengths

The evaluation seems careful, because the authors fixed their test tasks in advance and kept them separate from the tasks they used during development. They also report results where their method did not help, instead of leaving them out.

Critical weaknesses
  1. I am unsure what the learned controller adds over simpler approaches. In Taxi, it uses fewer checks, but the hand-written rule completes more tasks. I would like to see how they compare when both use roughly the same number of checks.

  2. The scope and comparison with existing methods need clarification. The approach requires an environment that can be restored or replayed, which excludes many real actions with side effects. The authors acknowledge this limitation and briefly mention tree search and verifier-guided action selection. However, I would find concrete application examples and an experimental comparison with the closest existing method helpful.

Questions for authors
  1. How does the learned controller compare with the hand-written rule when both use roughly the same number of checks?

  2. Which tree-search or verifier-guided method would be the closest baseline, and how would you compare them at similar resource use?

  3. Which applications do you see as the best fit for this approach, given the need to restore or replay the environment?

1 comment

Thank you for the close read, and for the matched-fork question. The published paper did not answer it. It compared methods at the same budget cap, not at the same number of forks used. The learned controller uses fewer forks than reserve-aware at the same cap, so that comparison mixed two things: who spends less, and who wins per fork spent.

We ran the missing comparison. We swept reserve-aware and risk-gated over budget caps 0, 4, 6, 8, 12, 24, with the same 5 seeds, 300 episodes per seed, 1,200 training episodes, 40-step horizon, and error rates 0.10–0.40 as the published Taxi runs (480 seed-level rows). We paired the learned controller, at cap 24, against the reserve-aware cap whose mean fork count was closest, seed by seed. Differences are learned minus reserve-aware, with two-sided 95% t intervals over 5 seeds.

ErrorLearned forksReserve forksDifference95% CI
0.104.814.80-0.009[-0.054, +0.036]
0.204.915.20-0.017[-0.030, -0.004]
0.306.175.61-0.034[-0.087, +0.019]
0.407.865.97-0.025[-0.084, +0.035]

The answer is not what we hoped for. At matched fork counts the learned controller never beats reserve-aware. Three of the four gaps sit inside zero, so those are ties. One is below zero: error 0.20, -0.017, with an interval that stays under zero. Two caveats. First, the match is by aggregate mean forks, picked after the sweep from six pre-set caps, so it is not a controlled equal-fork experiment. Second, the error 0.40 row is a loose match (7.86 against 5.97 forks). We report it because it is the closest cap we ran, not because the forks are equal. The full 8-row table and the sweep files are in the supplement.

What the learned controller does beat, at the same budget cap, is direct execution and equal allocation. At cap 24 it beats direct execution by 13.9, 10.1, and 6.5 points at error rates 0.10, 0.20, and 0.30. Equal allocation turns harmful at 0.30 (-8.5 points) and 0.40 (-18.3 points). The learned controller stays above direct execution in all eight conditions. Reserve-aware stays the best rule for success on Taxi, and the revision will say so in the main text. The DP future-value term also costs success against a myopic version of the same controller: at cap 24 it loses 3.4, 2.7, 3.5, and 3.9 points, while cutting forks by 65–78%. We will move that ablation into the main text.

The closest baseline is VeGAS (Singhi et al., arXiv:2605.12620). At each step it samples 16 candidate actions and picks the one a generative verifier scores highest. It never runs any of them. Our method runs two branches from a restored state and compares what happened. That is the whole difference we claim: scored candidates versus executed branches. LATS runs tree search over whole sequences, CATTS gates on vote disagreement, and CHILL-Harness changes workflows; none runs two branches from a restored state. We did not run any of them head-to-head. None runs on our locked 24-task ALFWorld set or on Taxi at a matched fork budget without a rebuild, and a rebuild inside a rebuttal would be a new method, not a baseline. We ran that ablation. On the same 24 tasks, score-only also finishes 23/24, with the same sole failure (game 64), 0 forks and 0 replay, but 5,711.8 tokens per task against 5,347.1 for executed branches, 24 challenges against 18, and 2 overrides against 5. Executing the branches adds no success here; it changes the cost profile. With 24 tasks and one direct failure, that is an exploratory null, not a proof either way.

This fits only where the state can be put back. Three settings meet that test: code and tool agents in a container or sandbox with a snapshot, before a destructive command; simulated robotics and game environments, where reset is cheap; and web agents with a saved page and session state. It does not fit any action with an irreversible side effect — sending a message, charging a card, writing to a shared file, moving a physical robot. The revision will put that limit in the introduction, next to the first description of a fork.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.