acceptodds
Under review as a conference paper at ICLR 2027

Probe-and-Resume: When and How to Evaluate Agent Execution

Abstract

Test-time search can improve agent performance by exploring alternative actions and using a critic to select promising branches. We study this approach in terminal-based computer-use environments, which expose only a partial view of a large underlying state, and find that the Monte Carlo tree search (MCTS) configuration we evaluate does not significantly improve task success. We identify two sources of poor critic performance: the agent's observations omit environment state needed for evaluation, and intermediate states offer limited evidence of whether a trajectory will succeed. At intermediate states, critics rank continuations only modestly better than chance, and environment access improves this little. We study when to invoke a critic and what access to give it to evaluate a node. Our findings motivate a policy that invokes the critic only at nodes the agent believes are final, rather than during partial progress. Further, the policy gives the critic read, write, and execute access to a fork of the computer's current and initial state, allowing it to probe and perform potentially destructive actions to surface any hidden state the trajectory omits. We call the resulting design Probe-and-Resume: when the agent claims to be done, the critic probes a fork of its state, and a rejected agent resumes where it stopped. On Terminal-Bench 2.1, this raises success by 8.4 percentage points over MCTS with conventional critics, and approaches the success rate of the Codex CLI agent with the same underlying model at less than half its cost.

Primary area:
reinforcement learning
Keywords:
LLM agents, critics, process reward models, verification, tree search, agent evaluation, environment access, terminal 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_JeL5OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies when a critic for terminal agents should be consulted and what environment access it needs. On all 89 Terminal-Bench 2.1 tasks (five trials each, GPT-5.6 Luna with Terminus-2), neither snapshot/restore tools nor MCTS with a trajectory-only critic improves pass@1. Measured directly, critics rank intermediate states near chance early in a trajectory, with little help from environment access. At claimed completions, however, a critic that executes commands in a fork cuts misclassification from 36–39% to 22%, and a fork of the initial state helps further. The resulting Probe-and-Resume calls the critic only when the actor claims completion, lets it probe copies of the candidate and initial states, and returns unmet requirements to an actor that resumes from the preserved state. Pass@1 rises from 63.4% to 72.4% at 2.2× model cost, with a similar gain on a SWE-bench Pro subset.

Critical strengths
  1. The experiments are reliable, the arguments are clear, and the content is substantial.
  2. Non-significant results are reported for the strong model and the difficult subset of SWE-bench Pro.
Critical weaknesses
  1. The algorithm budget is completely fixed, and more parameter adjustments and experiments should be conducted to demonstrate the effectiveness of the parameters.
  2. How much benefit do you get from a cheaper second pass when the cost is 2.2x?
Questions for authors
  1. Public completion evaluation resumes after checking on the current state (action_critic.py lines 343–358, 410–474), while Figures 1 and 5 depict discardable forks. Which one was used in the experiment?
5 comments

Thank you for the review. Before we finalize our response, we would like to better understand the second weakness you mention: “How much benefit do you get from a cheaper second pass when the cost is 2.2x?”

To make sure we answer it directly, could you clarify which comparison you have in mind as “a cheaper second pass”:
(a) a cheaper evaluation step inside the loop, such as a trajectory-only critic or a self-check prompt in place of the execution-based critic
(b) a different use of the same 2.2x budget, such as best-of-2 sampling with critic selection
(c) the cost of stopping after the second round, which already recovers 78% of the gain (Fig. 6b)

Please let us know if you meant something different.

Also, we want to ask why you flagged an ethics violation so that we can promptly address it.

AuthorsOpenReview ↗

Response to Reviewer JeL5 (1/3)

We thank the reviewer for the positive assessment and for reading our code closely.

[W1 Fixed budget and parameter choices]

Probe-and-Resume has three parameter limits. The first is the time limit T, which is each task’s official timeout in the corresponding benchmark and is shared by the actor, the critic, and every snapshot and restore operation. We never change T, so every task keeps its own official limit and all methods, including the Codex CLI reference, follow the benchmark’s rules. The other two limits are our choices. The loop stops after six critic calls (the critic is called each time the actor claims it has finished), and after the first rejection, the actor has at most 50 more turns. To test how much these two choices matter, we vary each of them on the same 445 Terminal-Bench 2.1 trials as in Table 3, and every task keeps its own T.

ClaimsTurns after first rejectionPass rateΔ vs. baseline [95% CI]Total model cost
650 (paper)72.4%+9.0 [+5.6, +12.6]$23.14
1–63.4%0.0$10.70
25070.3%+7.0 [+3.8, +10.1]$20.45
35072.6%+9.2 [+5.8, +12.8]$21.80
61071.9%+8.5 [+5.2, +12.1]$20.05
62572.4%+9.0 [+5.6, +12.6]$21.60
610072.4%+9.0 [+5.6, +12.6]$24.95
6no limit72.4%+9.0 [+5.6, +12.6]$30.45
  • Critic calls beyond the third add nothing. A second call gives +7.0 points, and a third gives the full gain. This matches Figure 6b. Only 11 of the 445 trials (2.5%) were stopped by the limit of six critic calls.
  • The turn limit mainly controls cost. From 25 turns to no limit, the pass rate stays at 72.4% while the cost rises from \21.60to21.60 to \\30.45. Even with 10 turns, the gain is +8.5 points. Only 14 trials (3.1%) were stopped by the 50-turn limit, all on hard tasks, and removing the limit does not change the pass rate.

Across these settings, the gain stays between +8.5 and +9.2 points, and it drops only when the loop allows two critic calls or fewer. Three critic calls keep the full gain at 2.0x the baseline cost, which also bears on the cost question in W2. We will add this table to a new appendix.

AuthorsOpenReview ↗

Response to Reviewer JeL5 (2/3)

[W2 Benefit of a cheaper second pass at 2.2x cost]

Probe-and-Resume raises the model cost from \10.70to10.70 to \\23.14 (Table 3). Of the extra \12.44,thecriticcosts12.44, the critic costs \\7.48 and the actor’s revisions after a rejection account for \$4.96. We read “a cheaper second pass” in the three ways listed in our earlier question and answer each below.

(a) A cheaper evaluation step inside the loop

We tested two alternatives to the acting critic C_act in the loop. Both use the same time limit T, limit on critic calls, and turn limit as Probe-and-Resume.

  • A read-only critic. We use C_read (§3.2) in place of C_act in Probe-and-Resume. A single evaluation costs less than with C_act (App. G), but in the loop it rejects 64% of the actor’s first answers that already pass, against 21% for C_act (§4.2), because many requirements cannot be checked by reading files alone. The actor therefore has to revise correct work more often. 30% of trials use all six critic calls, against 2.5% with C_act, and the critic and the actor’s revisions together cost 1.5x as much as with C_act.
  • The actor as its own critic. No separate critic is used here. The actor’s own conversation runs the same probe on a fork of the candidate state, and the probe turns are removed from its context afterwards. This variant reaches 65.2%, 7.2 points below Probe-and-Resume, at a similar total cost (\24.73against24.73 against \\23.14). Its verdicts are also less reliable. Over all rounds, it accepts 28% of the failing answers and rejects 36% of the passing ones, against 21% and 21% for a separate critic.

(b) A different use of the same budget

Best-of-2 runs the actor twice on each task, each run within the task’s own time limit T, and C_act judges the final state of both runs. It submits the run the critic accepts, and picks one at random when the critic accepts both or neither. Best-of-2 reaches 69.0% (+5.7 [+3.6, +7.8]) at \31.25,whichis2.9xthebaselinecost.Probe−and−Resumeis3.3pointshigherandcostsless(31.25, which is 2.9x the baseline cost. Probe-and-Resume is 3.3 points higher and costs less (\\23.14, 2.2x). Even with an oracle selector that always picks a passing run whenever one exists, at no cost, Best-of-2 would reach 74.2% at \21.41(2.0x).Probe−and−Resumethereforecomeswithin1.8pointsofthisoracle,withoutknowinginadvancewhichrunpasses.RestartingtheactorfromS0aftereachrejectionisanotherwaytospendmore,anditreaches66.321.41 (2.0x). Probe-and-Resume therefore comes within 1.8 points of this oracle, without knowing in advance which run passes. Restarting the actor from S0 after each rejection is another way to spend more, and it reaches 66.3% at \\38.12 (Table 3, App. K).

(c) Stopping after the second claim

Most of the gain comes from the second claim. With at most two claims, Probe-and-Resume reaches 70.3% (+7.0 [+3.8, +10.1]) at \20.45(1.9x).Andthisisalready7820.45 (1.9x). And this is already 78% of the full pass rate gain. With at most three claims, it keeps the full gain of 72.6% (+9.2 [+5.8, +12.8]) at \\21.80 (2.0x). Further claims add cost but no gain (Figure 6b).

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

This paper studies when and how to evaluate agent execution using an LLM critic. The proposed method, Probe-and-Resume, invokes the critic when an actor claims task completion. The critic checks task requirements through executable probes in disposable forks of the candidate environment, with an additional fork of the initial environment serving as a reference. If the critic rejects the candidate, the actor receives feedback and resumes from its preserved state and conversation.

The paper reports improvements on Terminal-Bench 2.1 and a selected SWE-bench Pro subset, together with diagnostic experiments on critic access, evaluation timing, and initial-state references. These results suggest that the workflow can be practically useful. However, I find the scientific contribution incremental: the method combines established components, while the analysis does not sufficiently explain the underlying limitations of intermediate-state evaluation or establish the generality and necessity of the proposed design.

Critical strengths
  • A practically useful verification workflow. Evaluating disposable environment copies allows the critic to perform potentially destructive checks without corrupting the actor’s candidate solution. Preserving the actor’s state and conversation also avoids discarding useful progress after rejection.

  • Useful diagnostic analysis and transparent reporting. The paper examines several levels of critic access and reports false acceptances, false rejections, repair outcomes, and null results for stronger actors and harder tasks. These analyses are more informative than reporting aggregate success alone.

Critical weaknesses
  • Limited scientific novelty beyond combining existing components. The method combines tool-assisted critique, iterative feedback and revision, environment branching, and state-preserving resumption. The paper acknowledges relevant prior approaches and builds on existing branching infrastructure. Its distinctive contribution is therefore primarily the integration of these components and an empirical investigation of their use.
  • The paper characterizes intermediate-state critic limitations without sufficiently explaining them. A central motivation is that the tested critics are relatively ineffective at evaluating intermediate execution states. However, the experiments primarily describe when these critics struggle, rather than establish why they struggle.
  • Generalization across models and task difficulty remains uncertain. The broad-benchmark positive actor results are concentrated on GPT-5.6 Luna. Experiments with alternative critics demonstrate some critic-model flexibility, but do not establish actor-model generality.
Questions for authors
  • The method relies on disposable environment forks, but these do not isolate external services or irreversible actions. What assumptions are required for Probe-and-Resume to operate safely in live online settings, and which of those assumptions are satisfied by the current implementation?
  • How are snapshots and forks stored and reclaimed, and what is the peak storage overhead per task? Does the implementation share unchanged data between forks or duplicate entire environments?
6 comments
AuthorsOpenReview ↗

Response to Reviewer mZDX (1/3)

We thank the reviewer for the thoughtful review. We are glad they found the workflow practically useful and the diagnostic analysis informative.

[W1 Novelty beyond combining existing components]

The goal of this paper is to make test-time search useful for terminal tasks. Test-time search depends on a critic to decide which branches/directions to pursue. Our contributions concern when to invoke that critic and what environment access to give it, particularly in settings where there are resource constraints that must be effectively allocated during search (such as wall-clock time budgets in Terminal-Bench):

  • Critics are unreliable at intermediate states. MCTS with a conventional critic (as the reviewers suggested, we also tested alternative search configurations) does not significantly improve success on Terminal-Bench 2.1. We trace this to the critic, which, at intermediate states, ranks continuations only modestly better than random.
  • Critics are reliable at claimed completions when they can act to test the final environment state. When the actor claims completion, a critic that executes commands in a fork of the environment (to avoid corrupting a correct final state) cuts misclassification from 36–39% to 22%. Adding a fork of the initial state as a reference raises accuracy further, from 76% to 80%, primarily by reducing false rejects from 24% to 17%.
  • Probe-and-Resume. Building on these findings, our test-time search method, Probe-and-Resume, invokes the critic only at claimed completions and lets it probe forks of the candidate and initial states. It then returns the evidence it gathers to an actor that resumes from its preserved state. This raises success by 8.4 percentage points over MCTS with conventional critics on Terminal-Bench 2.1.

Prior work falls into two groups.

  • Some critics are invoked at the final stage to grade a finished attempt, such as ProRe (Dai et al., 2026), VAGEN (Cui et al., 2026), and IRA (Shi et al., 2026b). Their judgments are used to evaluate an actor, as in Agent-as-a-Judge (Zhuge et al., 2024), to assign credit for RL training (VAGEN, IRA), or to select among rollouts, as in R2E-Gym (Jain et al., 2025). In these uses, the evidence they gather, such as a syntax error, is used for judgement only and not communicated to the actor so that it can try to recover. Work that does return a final-stage critique to the actor, such as Reflexion (Shinn et al., 2023), Self-Debugging (Chen et al., 2024), CRITIC (Gou et al., 2023), Self-Refine (Madaan et al., 2023), and Pan et al. (2024), relies on a checking pipeline or tool set fixed in advance for one task type, and is not applicable to the general setting with the task type not known in advance.
  • Critics are also invoked at intermediate stages to judge unfinished trajectories and feed their judgments back into the search, as in LATS (Zhou et al., 2024) and Koh et al. (2024). As contribution 1 shows, these judgments do not significantly improve success on complex terminal tasks. Across both groups, most critics have read-only access and cannot act in the environment, and those that execute code run a fixed test pipeline rather than arbitrary commands. Although VAGEN found read-only access sufficient for GUI tasks, we show that terminal tasks modify filesystem, terminal, and application state, and contribution 2 shows that a critic that executes commands judges such states more accurately.

[Additional references]

  • Chen et al. (2024). Teaching Large Language Models to Self-Debug. ICLR 2024. arXiv:2304.05128
  • Cui et al. (2026). Agentic Reward Modeling: Verifying GUI Agent via Progressive Trajectory-Grounded Interaction. arXiv:2602.00575
  • Dai et al. (2026). ProRe: A Proactive Reward System for GUI Agents via Reasoner-Actor Collaboration. ICLR 2026. arXiv:2509.21823
  • Pan et al. (2024). Autonomous Evaluation and Refinement of Digital Agents. COLM 2024. arXiv:2404.06474
  • Shi et al. (2026b). Interactive Reward Agent: GUI Task Evaluation via Environment-State Verification. arXiv:2607.25904
AuthorsOpenReview ↗

Response to Reviewer mZDX (2/3)

[W2 Why critics struggle at intermediate states]

An intermediate state does not have a fixed outcome: its success depends on the actor’s subsequent policy and mistakes. Environment access can reveal more about the current state, but it does not reveal which future actions the actor will take. In contrast, at a claimed completion, the critic evaluates whether the current environment already satisfies the task and can obtain direct evidence by executing tests that may modify state (e.g., the kv-store-grpc task issues writes to verify that writes and persistence work in the database). This distinction explains why acting access substantially improves final-state verification but provides little improvement in ranking intermediate states.

  • Future actions drive the final outcomes of an intermediate state. From each intermediate state, we run the actor five times. 21% of the states have mixed passed and failed outcomes (App. F). This is solely due to the actor's randomness, as all rollouts continue from the same state. As trajectories progress from 25% to 75% depth, there are fewer future steps, the share of mixed states drops from 33% to 9%, and the accuracy of the three critics (trajectory-only C_traj, read-only C_read, and acting C_act) at ranking two states rises from 49–56% to 64–69% (§3.2).
  • Estimation noise does not explain the results. Since 5 runs per state may introduce estimation error, we focus on the states where all five runs agree (as pass or fail). We then select 117 pairs of such states where one state is all-pass and one state is all-fail, and ask critics to order these pairs correctly. The critics order 68–74% of these pairs correctly, and C_act marginally improves over C_traj by +3.4 points [−5.4, +12.2] (App. F).

Our finding complements recent work showing that intermediate-state critics can become useful with explicit outcome supervision. FOCUS (Jiang et al., 2026) trains a critic using selectively sampled continuations from intermediate states, while Li et al. (2026) learn when to intervene from approximately 82,000 counterfactual continuations. In contrast, we study a general-purpose critic used zero-shot at inference time. We find that simply giving such a critic access to the current environment does not resolve uncertainty about the actor’s future behavior. This motivates concentrating critic computation at claimed completions, where acting access provides direct evidence of correctness.

[W3 Generality across actor models and task difficulty]

Beyond GPT-5.6 Luna, the paper tests stronger actors (App. L), tasks of different difficulty (App. M), and other critic models (App. J). We also ran Claude Haiku 5.5, an actor from a different model family, as both actor and critic on all 89 Terminal-Bench 2.1 tasks, five trials each, with the same settings as in §4.2. Together with the other actors in the paper:

Actor / CriticBenchmarkTasksBaselineOursΔ [95% CI]
Luna / Luna (§4.2)Terminal-Bench 2.18963.4%72.4%+9.0 [+5.6, +12.6]
Haiku 5.5 / Haiku 5.5Terminal-Bench 2.18966.5%70.6%+4.1 [+0.3, +8.3]
Astra / Fable 5.1 (App. L)Terminal-Bench 2.11561.3%62.7%+1.3 [−6.7, +9.3]
Astra / Opus 5.5 (App. L)Terminal-Bench 2.11569.3%73.3%+4.0 [−2.7, +10.7]
Luna / Luna (App. M)SWE-bench Pro, medium18682.3%90.9%+8.6 [+3.8, +14.0]
Luna / Luna (App. M)SWE-bench Pro, hard4170.7%73.2%+2.4 [−4.9, +9.8]

The loop also improves an actor from a different model family, but the gain is smaller than with Luna. We hypothesize the size of the gain depends on the actor’s first claims more than on the actor itself. The loop can only help when a first claim fails, the critic catches it, and the actor can fix it. On the 30 tasks where the loop rescues Luna’s trials, Haiku’s first claim already passes 77% of the time. More of Haiku’s failures are trials that never claim completion, and the loop never reaches these. App. L shows the same pattern for stronger actors where most of their first claims already pass, and a critic of the same strength misses the remaining failures. Task difficulty on SWE-bench Pro gives the same picture that the gain comes from the medium tasks, and on the hard tasks it cannot be told apart from zero (App. M). We will add the Haiku results as a new appendix and discuss in §4.4 when the loop is expected to help.

[Additional references]

  • Jiang et al. (2026). FOCUS: Active Critic Learning for Long-Horizon Language Model Agents. arXiv:2610.35801
  • Li et al. (2026). From Uncertainty to Action: Learning to Steer LLM Agents. arXiv:2610.09115
AuthorsOpenReview ↗

Response to Reviewer mZDX (3/3)

[Q1 Safety assumptions in live settings]

A probe is safe if the changes stay within the forked environment. For instance, Waypoint (Xu et al., 2026) forks the filesystem, the processes and their memory, and the terminal session, but nothing outside the machine, such as a remote database or a cloud API. This is consistent with almost all terminal and coding benchmarks, including Terminal-Bench 2.1 (Marten et al., 2026), SWE-bench Pro (Deng et al., 2025), Terminal-Bench Pro (Wang et al., 2025), SETA-Env (Shen et al., 2026) and Endless Terminals (Gandhi et al., 2026). They all run in a container, do not rely on external services, and validate based on container state. Finally, since the actor’s actions already introduce risk, the only new risk that we introduce is from the critic’s probes.

Systems that support branching with external services remain an open research problem in the systems community. For safety purposes, a container may simply block external services, only communicate with other branchable containers, or communicate with natively branchable services such as branchable databases (Dolt Team, 2026). Otherwise, a read-only critic (C_read) can be used, but as we show, it misclassifies more candidate final states, 36% against 22% for C_act (§3.2). We will add this discussion to §4.4.

[Q2 Snapshot storage and sharing]

We use Waypoint’s (Xu et al., 2026) snapshot and fork mechanisms. For memory, each snapshot records the full state of the task’s processes, but this is usually very small, with a median of 1.9 MiB per snapshot, because Terminal-Bench processes are mostly a shell and a few tools. Only tasks that keep a VM or a server running reach 1.0–1.6 GiB per snapshot. For disk, each snapshot only records file deltas, and the overhead is a median of 7 MiB per trial, with 91% of trials under 1 GiB. The larger cases come from tasks that download models or datasets or build large projects, which write these files with or without Probe-and-Resume.

We hope the new experiments and clarifications address the reviewer's concerns, and we would be grateful if the reviewer would reconsider their assessment. We are happy to clarify anything further.

[Additional references]

  • Dolt Team (2026). Using Branches and Database Revisions. Dolt documentation. https://www.dolthub.com/docs/sql-reference/version-control/branches
  • Gandhi et al. (2026). Endless Terminals: Scaling RL Environments for Terminal Agents. arXiv:2601.16443
  • Shen et al. (2026). SETA: Scaling Environments for Terminal Agents. arXiv:2607.10891
  • Wang et al. (2025). Let It Flow: Agentic Crafting on Rock and Roll, Building the ROME Model within an Open Agentic Learning Ecosystem. arXiv:2512.24873
Reviewer_buBBOpenReview ↗
Rating
3(+2)
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper revolves around the use of agents to perform terminal-based tasks. The difficulty of this problem lies with the lack of proper evaluations for actions performed by the agent --- it is not trivial for the agent to determine whether it has successfully completed a task without external guidance (in the form of a critic). The paper is divided into two portions: i) the first portion investigates different critics that is available to the agent, ii) the second portion introduces probe-and-resume, a method for controlling the agents operations for terminal-based tasks. The paper concludes with a set of experiments to demonstrate the capabilities of their proposed method.

Critical strengths

i) The paper is reasonably well-written and motivates the problem. I am not familiar with the problem domain but found it easy to understand the challenges it presents by reading this paper.

ii) The problem being addressed by the paper is an open problem of importance the community.

iii) I do think the experimental designs were well thought through and the evaluation criteria was reasonable.

Critical weaknesses

I believe the main weakness with the paper is its lack of impact and/or significance. I cannot say that I learned anything from this paper that was not already well known or apparent. My two takeaways from the paper were:

  1. having a stronger, more accurate critic would provide better agent evaluations;
  2. an agent should iterate on its candidate solution until it can either solve its task or until some time limit is reached.

Neither of these observations provide new insight into the problem domain.

Furthermore, on several occasions emphasises how their approach outperforms MCTS. I have several gripes about this. Firstly, the results demonstrating the main contribution do not really have any relation to MCTS --- MCTS was only used for one of the tested critics. Secondly, the way MCTS is implemented in this paper does not follow typical patterns. MCTS is powerful when trying to approximate the best actions to take given a large candidate set. In the context of the problem, MCTS was only given two actions (sequence of actions?) at each decision state. The paper also states that each node is a sequence of 5 turns (I am assuming this constitutes 5 primitive actions). Given a fixed-length sequence, it is easy for the nodes MCTS to overshoot the effective length of the optimal sequence of actions. Finally, once the MCTS tree is built, the paper's implementation chooses an arbitrary node in the tree --- this is not correct. The idea is MCTS is used to provide estimates of the values of the actions at the root of the tree. Every other node would have higher variance in their estimates. I also do not think UCT makes sense for this domain. UCT's regret minimization approach makes it innately pessimistic in its search since it assumes an adversarial environment. While, there are processes that may affect the agent's actions, I think a search technique specifically built for domains with similar properties would be more appropriate, for instance, Levin Tree Search with Policies.

Some of the explanations of the results seem a little misleading.

  • The paper states that CactC^{act} reduces the false reject. Does this mean the other critics don't?
  • The paper ignores the false accept rates, which the critics have lower rates. Why are we not considering this? If I were to evaluate an agent, I'd rather it assume it is incorrect and do nothing instead of thinking it is correct and do the wrong thing.
Questions for authors

None.

4 comments
AuthorsOpenReview ↗

Response to Reviewer buBB (1/3)

We thank the reviewer for the careful review and for finding the experimental design well thought through. We also highly appreciate their feedback on our MCTS configuration and their further improvement suggestions.

[W1 Novelty and significance]

The goal of this paper is to make test-time search useful for terminal tasks. Test-time search depends on a critic to decide which branches/directions to pursue. Our contributions concern when to invoke that critic and what environment access to give it, particularly in settings where there are resource constraints that must be effectively allocated during search (such as wall-clock time budgets in Terminal-Bench):

  • Critics are unreliable at intermediate states. MCTS with a conventional critic (as the reviewers suggested, we also tested alternative search configurations) does not significantly improve success on Terminal-Bench 2.1. We trace this to the critic, which, at intermediate states, ranks continuations only modestly better than random.
  • Critics are reliable at claimed completions when they can act to test the final environment state. When the actor claims completion, a critic that executes commands in a fork of the environment (to avoid corrupting a correct final state) cuts misclassification from 36–39% to 22%. Adding a fork of the initial state as a reference raises accuracy further, from 76% to 80%, primarily by reducing false rejects from 24% to 17%.
  • Probe-and-Resume. Building on these findings, our test-time search method, Probe-and-Resume, invokes the critic only at claimed completions and lets it probe forks of the candidate and initial states. It then returns the evidence it gathers to an actor that resumes from its preserved state. This raises success by 8.4 percentage points over MCTS with conventional critics on Terminal-Bench 2.1.

Prior work falls into two groups.

  • Some critics are invoked at the final stage to grade a finished attempt, such as ProRe (Dai et al., 2026), VAGEN (Cui et al., 2026), and IRA (Shi et al., 2026b). Their judgments are used to evaluate an actor, as in Agent-as-a-Judge (Zhuge et al., 2024), to assign credit for RL training (VAGEN, IRA), or to select among rollouts, as in R2E-Gym (Jain et al., 2025). In these uses, the evidence they gather, such as a syntax error, is used for judgement only and not communicated to the actor so that it can try to recover. Work that does return a final-stage critique to the actor, such as Reflexion (Shinn et al., 2023), Self-Debugging (Chen et al., 2024), CRITIC (Gou et al., 2023), Self-Refine (Madaan et al., 2023), and Pan et al. (2024), relies on a checking pipeline or tool set fixed in advance for one task type, and is not applicable to the general setting with the task type not known in advance.
  • Critics are also invoked at intermediate stages to judge unfinished trajectories and feed their judgments back into the search, as in LATS (Zhou et al., 2024) and Koh et al. (2024). As contribution 1 shows, these judgments do not significantly improve success on complex terminal tasks. Across both groups, most critics have read-only access and cannot act in the environment, and those that execute code run a fixed test pipeline rather than arbitrary commands. Although VAGEN found read-only access sufficient for GUI tasks, we show that terminal tasks modify filesystem, terminal, and application state, and contribution 2 shows that a critic that executes commands judges such states more accurately.

[Additional references]

  • Chen et al. (2024). Teaching Large Language Models to Self-Debug. ICLR 2024. arXiv:2304.05128
  • Cui et al. (2026). Agentic Reward Modeling: Verifying GUI Agent via Progressive Trajectory-Grounded Interaction. arXiv:2602.00575
  • Dai et al. (2026). ProRe: A Proactive Reward System for GUI Agents via Reasoner-Actor Collaboration. ICLR 2026. arXiv:2509.21823
  • Pan et al. (2024). Autonomous Evaluation and Refinement of Digital Agents. COLM 2024. arXiv:2404.06474
  • Shi et al. (2026b). Interactive Reward Agent: GUI Task Evaluation via Environment-State Verification. arXiv:2607.25904
AuthorsOpenReview ↗

Response to Reviewer buBB (2/3)

[W2 MCTS comparison and setup]

We first explain the high-level design constraints of terminal-use environments, which motivated our MCTS setup in §3.1 and App. E.2. We then present new experiments that directly evaluate the reviewer's suggested MCTS variations, including equipping MCTS with our strongest acting critic (C_act), reducing node length to prevent overshooting, and replacing UCT with Best-First Search and Levin Tree Search (LTS). Together, these results show that the pass rate improvement from MCTS is still limited on terminal tasks.

Design Constraints: In our setup, one turn corresponds to one API call, including observation, reasoning, and command output. Because the action space in terminal tasks is unlimited, we do not provide a fixed set of candidate actions at decision states. Instead, we let the actor choose the action for the child branch. The benchmark enforces an official timeout for every task, so tree search algorithms must ensure the time budget is used effectively to complete at least one deep trajectory. Another challenge is that the actors are not capable of using branching themselves, so we must adapt the search algorithm.

  • If we snapshot after every turn, the overhead consumes the timeout, and so we group 5 turns into each tree node. If the actor declares completion within the 5 turns, we stop execution immediately and that node becomes a candidate leaf (App. E.2).
  • We also found that not limiting the number of child branches results in a wide-but-shallow tree, and we found that 2 children is a good balance.
  • MCTS describes a family of algorithms whose configurations vary in node granularity, branching factor, selection rule, and evaluation method. Language-agent search has used modified UCT with value feedback (Antoniades et al., 2024), best-first traversal with explicit depth and breadth budgets (Koh et al., 2024), and policy-guided LTS under a query budget (Pendurkar and Sharon, 2025).
  • 2 implementation details: 1) UCT does not assume an adversarial environment: its exploration term is optimistic under uncertainty and balances high estimated value against low visit count. 2) We do not submit an arbitrary tree node. We submit the highest-scoring candidate leaf, and fall back to the highest-scoring internal node only when no branch declares completion before the timeout (App. E.2).

We will better justify these choices in the paper. Below, we evaluate the reviewer’s proposed alternatives: 1-turn nodes for finer-grained branching, wider/unlimited branching, greedy best-first traversal, LTS-style policy-guided traversal, and C_act in place of the trajectory-only critic (C_traj). The methods were developed for different action spaces and budget settings, so we adapted them for the terminal environment and wall-clock budgets.

AlgorithmNode length / Max childrenCriticPass RateHit time limit
MCTS (UCT) in paper5 / 2C_traj64%32%
MCTS (UCT; Antoniades et al., 2024)1 / 3C_act20%99%
Best-first (Koh et al., 2024)1 / 5C_act32%67%
Best-first variant3 / 3C_act53%33%
LTS (Pendurkar and Sharon, 2025)5 / 2Stop when C_act accepts65%34%
MCTS (UCT, unlimited children)1 / ∞C_act8%100%

The results suggest that one-turn nodes incur excessive search overhead, and wider or unlimited branching spends the budget on shallow alternatives and increases timeout rates to 67–100%. Longer nodes and narrower branching preserve depth. Replacing UCT with best-first or LTS does not materially improve over our reported 64% pass rate. We will explain these design rationales in the paper, so it is clear why we arrived at the 5-turn, 2-child UCT design as a strong baseline. We will qualify our statements with respect to MCTS in the paper.

[Additional references]

  • Pendurkar and Sharon (2025). Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries. TMLR 2025. arXiv:2601.03606
AuthorsOpenReview ↗

Response to Reviewer buBB (3/3)

[W3 Do other critics also reduce false rejects?]

We found that the acting critic C_act reduces the false reject rate (22%) compared to the other critics (60% for the trajectory-only C_traj and 52% for the read-only C_read).

[W4 Why are false accepts not considered?]

We agree that different use cases may assign different costs to false accepts and false rejects. In this paper, we optimize for the task success rate. If the critic falsely accepts, it is equivalent to the actor directly submitting its candidate completion state. In contrast, a false reject can turn a passing state into a failure, which adversely affects the task success rate. In practice, the drop in false rejects (30–38 points) far outweighs the increase in false accepts (12–17 points; Table 2), cutting overall misclassification from 36–39% to 22%. A benefit of C_act is that it can enumerate and test candidate violations, so it can explain why it fails a state and help the actor recover. If we prioritize minimizing false accepts, we can prompt the critic to be more cautious.

We hope the new experiments and clarifications address the reviewer's concerns, and we would be grateful if the reviewer would reconsider their assessment. We are happy to clarify anything further.

I thank the authors for taking the time to write a rebuttal and address my concerns.

The responses from the authors go a long way to assuage my misgivings of the paper. The responses clarified the significance of the paper and the results from the additional experiments support the decisions behind the experimental setup. I think including this and polishing the paper to make its impact more obvious, it would definitely make it a stronger paper.

I will increase my rating to "Weak Accept".

Comments on the paper

3 comments

We thank all reviewers for their thoughtful and constructive feedback. Below we clarify the goal and contributions of the paper and how they relate to prior work; we address each reviewer's points in the individual replies.

The goal of this paper is to make test-time search useful for terminal tasks. Test-time search depends on a critic to decide which branches/directions to pursue. Our contributions concern when to invoke that critic and what environment access to give it, particularly in settings where there are resource constraints that must be effectively allocated during search (such as wall-clock time budgets in Terminal-Bench):

  • Critics are unreliable at intermediate states. MCTS with a conventional critic (as the reviewers suggested, we also tested alternative search configurations) does not significantly improve success on Terminal-Bench 2.1. We trace this to the critic, which, at intermediate states, ranks continuations only modestly better than random.
  • Critics are reliable at claimed completions when they can act to test the final environment state. When the actor claims completion, a critic that executes commands in a fork of the environment (to avoid corrupting a correct final state) cuts misclassification from 36–39% to 22%. Adding a fork of the initial state as a reference raises accuracy further, from 76% to 80%, primarily by reducing false rejects from 24% to 17%.
  • Probe-and-Resume. Building on these findings, our test-time search method, Probe-and-Resume, invokes the critic only at claimed completions and lets it probe forks of the candidate and initial states. It then returns the evidence it gathers to an actor that resumes from its preserved state. This raises success by 8.4 percentage points over MCTS with conventional critics on Terminal-Bench 2.1.

Prior work falls into two groups.

  • Some critics are invoked at the final stage to grade a finished attempt, such as ProRe (Dai et al., 2026), VAGEN (Cui et al., 2026), and IRA (Shi et al., 2026b). Their judgments are used to evaluate an actor, as in Agent-as-a-Judge (Zhuge et al., 2024), to assign credit for RL training (VAGEN, IRA), or to select among rollouts, as in R2E-Gym (Jain et al., 2025). In these uses, the evidence they gather, such as a syntax error, is used for judgement only and not communicated to the actor so that it can try to recover. Work that does return a final-stage critique to the actor, such as Reflexion (Shinn et al., 2023), Self-Debugging (Chen et al., 2024), CRITIC (Gou et al., 2023), Self-Refine (Madaan et al., 2023), and Pan et al. (2024), relies on a checking pipeline or tool set fixed in advance for one task type, and is not applicable to the general setting with the task type not known in advance.
  • Critics are also invoked at intermediate stages to judge unfinished trajectories and feed their judgments back into the search, as in LATS (Zhou et al., 2024) and Koh et al. (2024). As contribution 1 shows, these judgments do not significantly improve success on complex terminal tasks. Across both groups, most critics have read-only access and cannot act in the environment, and those that execute code run a fixed test pipeline rather than arbitrary commands. Although VAGEN found read-only access sufficient for GUI tasks, we show that terminal tasks modify filesystem, terminal, and application state, and contribution 2 shows that a critic that executes commands judges such states more accurately.

[Additional references]

  • Chen et al. (2024). Teaching Large Language Models to Self-Debug. ICLR 2024. arXiv:2304.05128
  • Cui et al. (2026). Agentic Reward Modeling: Verifying GUI Agent via Progressive Trajectory-Grounded Interaction. arXiv:2602.00575
  • Dai et al. (2026). ProRe: A Proactive Reward System for GUI Agents via Reasoner-Actor Collaboration. ICLR 2026. arXiv:2509.21823
  • Pan et al. (2024). Autonomous Evaluation and Refinement of Digital Agents. COLM 2024. arXiv:2404.06474
  • Shi et al. (2026b). Interactive Reward Agent: GUI Task Evaluation via Environment-State Verification. arXiv:2607.25904
Area_Chair_YqV5OpenReview ↗

Please Read The Authors' Response

Dear Reviewers,

We're near the end of the discussion phase. The authors have provided their responses to your reviews. Please check whether their responses have resolved your concerns. If not, please raise any remaining concerns and leave some time for the authors to respond again. If yes, please still respond to the authors. Note that simply admitting that you've read the rebuttal will also be helpful.

Many thanks, AC

AuthorsOpenReview ↗

Summary of the Discussion

Dear Area Chair and Reviewers,

We sincerely thank the reviewers for their thoughtful feedback and active engagement during the discussion. We are encouraged by the reviewers' recognition that our paper tackles an important and well-motivated problem (buBB, JeL5) and proposes a practically useful verification workflow (mZDX), and that its findings rest on well-designed and reliable experiments (buBB, JeL5) and informative diagnostic analysis (JeL5, mZDX). We also thank Reviewer buBB for raising their score.

During the discussion, we made the following additions:

  1. We ran Probe-and-Resume with three more model families (Claude Haiku 5.5, Kimi K2.5, and MiniMax M2.5) to demonstrate its generality beyond GPT-5.6 Luna (mZDX).
  2. We compared against a broader set of search configurations, including best-first and Levin tree search, to confirm that the bottleneck is evaluating intermediate states, not the search configuration (buBB).
  3. We analyzed how outcomes vary when the actor continues from the same state to explain why critics struggle at intermediate states but succeed at claimed completions (buBB, mZDX).
  4. We varied the loop's limits and compared other uses of the same budget, such as Best-of-2, to show that the gain is robust and cost-effective (JeL5).

We also clarified the fork implementation (JeL5), the safety assumptions for live settings, and the storage overhead of snapshots (mZDX).

As promised in our responses, we will incorporate all of these results and clarifications into the final version of the paper, together with the rationale for our MCTS configuration and a clearer statement of the contributions.

Thank you for your time and effort in handling our submission.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.