PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jiakai Xu, Tiancheng Ge, Tujie Guan, Yusheng Li, Rohan Timmaraju, Eugene Wu, Kostis Kaffes

arXiv:2610.21088v1cs.AIcs.LG

TL;DR

Terminal-agent search needs useful critic judgments, but the environment state relevant to task success may not appear in the agent’s observations. Probe-and-Resume has critics test claimed completions in forks and returns rejected candidates to the actor for revision. On Terminal-Bench 2.1, it raises pass@1 from 63.4% to 72.4% at less than half the cost of Codex CLI with the same model.

  • Problem

    Terminal-agent search needs critics to evaluate candidate states because ground-truth verification is unavailable during execution and observations may omit relevant computer state.

    Source: §1 · p. 1

  • Method

    Probe-and-Resume lets a critic check claimed completions in forks of the candidate and initial environments, then resumes the actor from the unchanged candidate with feedback after rejection.

    Source: §1 · p. 2

  • Results

    Probe-and-Resume raises pass@1 from 63.4% to 72.4% on Terminal-Bench 2.1, at less than half the cost of Codex CLI with the same model.

    Source: §5 · p. 10

  • Takeaways & Limitations

    Branching alone does not make search effective; it helps when critics use forks to check completed work, since evaluating a terminal task is itself a terminal task.

    Source: §5 · p. 10

    Forks do not isolate writes to external databases or shared services, so destructive checks require isolating those dependencies or restricting critic actions.

    Source: §4.4 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

Branchable environments make test-time search practical, but terminal agents need a critic to judge whether states merit continuation or satisfy the task. The paper finds that critics are weak at evaluating intermediate states and introduces Probe-and-Resume, which probes claimed completions in forks and lets the actor resume after rejection.

1 INTRODUCTION

  • Terminal tasks require long action sequences that can damage useful state, while branching environments allow agents to snapshot, restore, and explore alternatives in isolated forks.Branching makes test-time search practical, but search still needs a critic to assess candidate states because ground-truth verification is usually unavailable during execution.Source: §1 · p. 1
  • A critic may lack evidence because the actor’s records omit computer state, including files, processes, memory, packages, and databases that can change during execution.The initial-state fork also provides a reference for checking what must be preserved or changed.Source: §1 · pp. 1–2
  • The tested MCTS policy produces little improvement because critics are poor at valuing intermediate states, while environment access helps little until completion is claimed.This motivates concentrating critic computation at candidate final states, where a critic can test the actor’s claim against the environment.Source: §1 · p. 2
  • Probe-and-Resume gives the critic terminal access to forks of the candidate and initial environments, then resumes the actor from the unchanged candidate with feedback after rejection.The critic judges completions rather than intermediate states.Source: §1 · p. 2
  • Probe-and-Resume raises Terminal-Bench 2.1 success from 63.4% at the actor’s first completion claim to 72.4% at submission, expanding the accuracy–cost Pareto frontier.The evaluation used 89 tasks, five trials per task, GPT-5.6 Luna, and the basic Terminus-2 harness; the result is higher than Opus 4.7 using Claude Code at over an order of magnitude lower cost.Source: §1 · p. 2

2 BACKGROUND AND RELATED WORK

Prior work uses test-time search, iterative feedback, external evidence, and trajectory judgments across reasoning and agent tasks. This paper focuses on the distinct choices involved when critics evaluate live terminal environments, including access to execution state and initial-state evidence.

2 BACKGROUND AND RELATED WORK

  • Search methods allocate inference compute across candidate solutions, from sampling and answer aggregation to beam search, best-first search, and MCTS; process evaluation is also studied in mathematical reasoning.The cited work spans games (Silver et al., 2016; 2018), mathematical reasoning, software and web tasks (Koh et al., 2024; Antoniades et al., 2024), and process evaluation.Source: §2 · pp. 2–3
  • Self-Refine and Reflexion use critique or reflection to revise attempts, while Probe-and-Resume preserves the candidate environment and trajectory and resumes from that candidate after rejection.This differs from resetting the environment for another trial, as in Reflexion’s ALFWorld experiments.Source: §2 · p. 3
  • Prior critics obtain external evidence through tools, tests, or environment interaction; this work asks what access is needed when judging a live environment without verifier output.The cited examples include CRITIC (Gou et al., 2023), program and patch testing (Jain et al., 2025; Ehrlich et al., 2025; Li et al., 2025), and interactive judges (Zhuge et al., 2024).Source: §2 · p. 3
  • Trajectory and patch judgments have been used for web and software agents, and pairwise judgments on Terminal-Bench 2 recover part of the gap to oracle selection over five samples.Judge performance varies across web-agent benchmarks, while execution-free patch judgments can rely on stylistic features.Source: §2 · p. 3
  • Waypoint supports snapshots, restores, and isolated forks of filesystem, process, memory, and terminal state, enabling disposable execution checks and initial-state comparisons for critics.Only feedback returns to the actor; critic mutations are discarded, and the actor resumes from the candidate state.Source: §2 · p. 3

3 CRITIC DESIGN FOR SEARCH IN TERMINAL ENVIRONMENTS

The section finds that the tested branching tools and MCTS provide little improvement, while critic judgments depend on when they are made and what state evidence is available. Critic access to the initial state improves completion judgments, especially for states where it is used.

3.1 SEARCH BASELINES

  • MCTS changes pass@1 from 63.4% to 64.0% at 3.81× the model cost, while branching tools change it from 63.4% to 61.0%.The actor used branching tools in only 3 of 445 trials.Source: §3.1 · p. 4, Table 1 · p. 4

3.2 WHAT THE CRITIC CAN DO AND WHEN TO INVOKE IT

  • At candidate final states, Cact reduces misclassification from 36%–39% to 22%, while intermediate-state ranking reaches 64%–69% at 75% depth but only 49%–56% at 25%.Environment access changes intermediate ranking little; the pooled Cact-over-Ctraj gain is +4.4 points [−0.9, +9.9].Source: §3.2 · p. 5, Figure 2 · p. 5
  • Cread rejects 42% of passing states even when the verifier only reads files, compared with 9% for Cact.In 93% of these read-only false rejects, the critic reports insufficient evidence rather than a requirement violation.Source: §3.2 · pp. 5–6

3.3 WHAT INFORMATION TO GIVE THE CRITIC

  • Giving Cact a fork of the initial state raises accuracy from 76% to 80% and reduces false rejects from 24% to 17% across 404 states.On the 121 states where Cact+S0 inspected the initial-state fork, accuracy rises from 71% to 81%; on the other 283 states, it changes by +1.4 points [−1.3, +4.1].Source: §3.3 · p. 6, Figure 3 · p. 6, Figure 4 · p. 6

4 PROBE-AND-RESUME

Probe-and-Resume directs critic assessment to candidate completions, where execution in disposable forks can test requirements. The actor can then resume from its unchanged candidate with the critic’s feedback.

4.1 HOW PROBE-AND-RESUME WORKS

  • At each completion claim, the critic checks task requirements in disposable forks of the candidate and initial states; after rejection, the actor resumes from the candidate with feedback.The critic receives fresh forks and rechecks its requirements list after each revision; search stops on acceptance, six critic rounds, or budget exhaustion.Source: §4.1 · p. 7, Figure 5 · p. 7

4.2 TERMINAL-BENCH 2.1

  • 9 percentage points: Probe-and-Resume raises Terminal-Bench 2.1 Pass@1 from 63% to 72%, close to Codex CLI at half its cost.The comparison covers 89 tasks with five trials each; the table reports Pass@1 and model cost.Source: §4.2 · p. 7, Table 3 · p. 8
  • Restarting the actor from S0 after rejection costs 1.6× as much as resuming, takes longer, and does not yield a higher pass rate.The restart comparison uses the same critic, feedback, and time limit.Source: §4.2 · p. 8
  • Of 136 failing first proposals, critics correctly rejected 103 (76%), and actors rescued 43; of 282 passing proposals, critics falsely rejected 60 (21%), and actors rescued 57.The critic’s false-accept and false-reject rates, 21% each, were comparable to the 22% rates measured for candidate final states.Source: §4.2 · p. 8
  • Allowing a second claim raises submitted pass rate from 63% to 70%, capturing 78% of the loop’s gain; a third raises it to 73%, with no measurable gains afterward.64% of trials that claim to be finished end after one round; a three-claim cap would lose nothing measurable.Source: §4.2 · p. 8, Figure 6 · p. 8

4.3 SWE-BENCH PRO

  • On SWE-bench Pro, Probe-and-Resume raises pass rate from 80% to 88%; gains come from medium tasks, while hard-task gains cannot be distinguished from zero.The evaluation used one trial on 227 offline-gradable tasks under a 50-minute limit, with the same unchanged verifier run on a fork of the proposed state.Source: §4.3 · pp. 8–9, Figure 7 · p. 9

4.4 DISCUSSION AND LIMITATIONS

  • Branching supports both candidate evaluation without altering the actor’s resumable state and repair after rejection; avoiding a restart from the beginning improves success and lowers model cost.The authors also report that critics need not be fully correct when the actor–critic pair can rescue seemingly failing states.Source: §4.4 · p. 9
  • The evaluated setting uses Waypoint containers; forks do not isolate external databases or shared services, so destructive checks require isolated dependencies or restricted critic actions.Critic help also depends on actors being able to repair mistakes; the authors report no statistically significant gains with Astra and Opus on hard Terminal-Bench tasks.Source: §4.4 · p. 9

5 CONCLUSION

The paper concludes that critics predict intermediate-state success weakly, while execution-based checks in forks help assess candidate completions. Probe-and-Resume improves Terminal-Bench 2.1 pass@1 while costing less than half as much as Codex CLI with the same model.

5 CONCLUSION

  • The tested critics make weak predictions of success from intermediate states, even with execution access.The conclusion contrasts this with critics that run checks in a fork once the actor claims completion.Source: §5 · pp. 9–10
  • Probe-and-Resume raises Terminal-Bench 2.1 pass@1 from 63.4% to 72.4%, at less than half the cost of Codex CLI with the same model.The actor resumes from the unchanged candidate with feedback after a critic rejects it.Source: §5 · p. 10

A PROMPTS

  • The actor’s prompts, critics’ prompts, and feedback template are available in the paper’s repository.The repository also includes code showing how prompts are built from templates, the task, and the trajectory.Source: A PROMPTS · p. 15

B TASK LIST, VERIFIER ANNOTATION AND TIMEOUTS

Table 4 annotates the verifier operations needed for each Terminal-Bench task and flags requirements tied to the initial state. The appendix also explains how model costs are priced.

B TASK LIST, VERIFIER ANNOTATION AND TIMEOUTS

  • Verifier annotations record whether assertions require reading existing state, running a check, or comparing against a verifier-only value.Read codes distinguish file content, filesystem metadata, and runtime state; run codes distinguish local execution from service probes.Source: B TASK LIST, VERIFIER ANNOTATION AND… · p. 15, Table 4 · p. 16
  • The 89 tasks group by strongest verifier code into 19 hold, 48 run, and 22 read tasks; 47 instructions state a requirement relative to initial state S0.Examples include preserving a file or matching the original program’s output.Source: B TASK LIST, VERIFIER ANNOTATION AND… · p. 15, Table 4 · p. 16

C MODEL PRICES

  • Trial costs are model-token costs, not machine time, and the paper prices tokens using model rates.The GPT-5.6 Luna + Codex CLI point uses AWS pricing based on Harbor Hub token counts; other Figure 1 points use Harbor Hub job costs, with stated rate exceptions.Source: C MODEL PRICES · p. 16, Table 5 · p. 17

D STATISTICAL METHODOLOGY

The reported intervals use task-level bootstrap resampling, and the appendix describes the no-search baseline and the branching-tools arm. With optional snapshot and restore tools but no critic or search policy, the actor rarely explored alternatives.

D STATISTICAL METHODOLOGY

  • 95% percentile bootstrap intervals resample tasks 5,000 times, keeping all trials, states, and probes from each drawn task together.Comparisons are paired by trial or state when the arms share those observations.Source: D STATISTICAL METHODOLOGY · p. 17

E SEARCH BASELINES IN DETAIL

  • The no-search baseline runs GPT-5.6 Luna in the same harness until its first completion claim, then grades that state.It uses all 89 tasks, five trials each, under each task’s clock limit.Source: E SEARCH BASELINES IN DETAIL · p. 17

E.1 BRANCHING TOOLS WITHOUT A SEARCH POLICY (SEQ_FORK)

  • With optional snapshot and restore tools but no critic or score, the actor touched the tools in only 3 of 445 trials.Pass@1 was 61.0% versus 63.4% for baseline (∆= −2.4 [−6.7, +2.0]); restores undid damage already done rather than exploring alternatives or protecting progress.Source: §E.1 · p. 17, Table 6 · p. 17

E.2 TREE SEARCH WITH A TRAJECTORY-ONLY CRITIC (MCTS)

The MCTS arm builds a snapshot-based search tree and uses a trajectory-only critic to score nodes and guide expansion. It branches frequently, but does not significantly improve task success and costs substantially more than the baseline.

E.2 TREE SEARCH WITH A TRAJECTORY-ONLY CRITIC (MCTS)

  • Each trial builds a tree of environment snapshots, expanding a node by restoring it, letting the actor run five turns, and saving the result as a child.Nodes have at most two children; the trajectory-only critic scores each new node once, and node value is the mean score of its subtree.Source: §E.2 · p. 18
  • The search expands under a UCT policy, avoids expanding actor-declared completions, and submits the highest-value candidate or node when it stops.It stops when no node can be expanded or the task clock runs out; snapshots, restores, and critic calls count against that limit.Source: §E.2 · p. 18
  • 64.0% Pass@1 for MCTS versus 63.4% for baseline (∆= +0.6 [−4.5, +5.5]); the interval includes zero, while MCTS costs 3.81× as much.The critic accounts for 31.3% of MCTS cost.Source: §E.2 · p. 18, Table 7 · p. 18
  • The search opened a second branch in 99.3% of trials, and submitted a later branch in 70.9%.It ended before the clock ran out in 68.3% of trials because every leaf was actor-declared finished.Source: §E.2 · p. 18

F CRITIC METRICS BY POSITION

Critics select intermediate states only modestly better than random, with the clearest gains late in trajectories. Environment access improves pairwise accuracy more at final states than at intermediate states, while continuation-based labels are noisy.

F CRITIC METRICS BY POSITION

  • All critics receive the task, trajectory, and remaining budget; READ and ACT can also run commands in a fork, with ACT allowed any command.Intermediate outcomes are pass rates across five continuations; final outcomes are verifier judgments.Source: F CRITIC METRICS BY POSITION · pp. 18, 20
  • Five-continuation pass-rate labels are noisy, but on 117 decided pairs critics order 68%–74% correctly; ACT’s gain over trajectory-only scoring is +3.4 points [−5.4, +12.2].The standard error is at most 22 points, and 79% of intermediate states have continuations that all pass or all fail.Source: F CRITIC METRICS BY POSITION · p. 18
  • At 75% depth, selecting the highest-rated state yields a continuation pass rate 11.0–13.6 points above the mean, while gains at 25% depth have intervals including zero.Across intermediate depths, ACT’s gain over trajectory-only scoring is +1.8 points [−2.5, +6.3].Source: F CRITIC METRICS BY POSITION · p. 19
  • Environment access improves pairwise accuracy by +11.5 points [+2.7, +20.2] at final states and +4.4 points [−0.9, +9.9] across pooled intermediate depths.The difference between those gains is not significant (+7.1 points [−1.7, +15.5]).Source: F CRITIC METRICS BY POSITION · p. 19

G CRITIC COST

Critic execution is more costly at candidate final states, while trajectory-only prompt variants do not improve meaningfully over the plain prompt. The reference-state comparison rebuilds final states by replaying actor commands and checks them against recorded verifier results.

G CRITIC COST

  • At candidate final states, Cact costs 1.11 cents per state—3.1× Ctraj and 1.3× Cread.Cact costs 1.9× as much at final states as at intermediate states, taking 4.6 turns on average versus 3.5.Source: G CRITIC COST · p. 21, Figure 8 · p. 21

H TRAJECTORY-ONLY CRITIC PROMPTS

  • No trajectory-only prompt variant differs significantly from TRAJ; all three are within 1 MAE point at every intermediate depth.Summary + ledger adds a trajectory summary and per-step fact ledger; Checklist adds failure modes to inspect.Source: H TRAJECTORY-ONLY CRITIC PROMPTS · p. 21, Figure 9 · p. 21

I THE REFERENCE-STATE CRITIC: PROTOCOL

  • Of 411 candidate final states, 404 were rebuilt by replaying actor commands; verifier results matched recorded results on 399 states and differed on 2.The remaining three rebuilt states had no recorded result for comparison; seven states were dropped after replay, verifier, or initial-fork failures.Source: I THE REFERENCE-STATE CRITIC: PROTOCOL · p. 22

J DIFFERENT CRITIC MODELS

Alternative critics also improve submitted pass rates, though their probing times differ. Restarting after rejection lowers pass rate and raises cost and trial time compared with resuming.

J DIFFERENT CRITIC MODELS

  • +9.9 points [+5.4, +14.6]: Sonnet 5 raises the submitted pass rate to 70%, similar to Luna’s +9.0 points [+5.6, +12.6].Sonnet rejects 72% of failing first claims, and the actor turns 49 rejected claims into passing states; five passing first claims are falsely rejected.Source: J DIFFERENT CRITIC MODELS · p. 22, Figure 10 · p. 22
  • Sonnet’s probes take a median 138 seconds and 12 commands, versus Luna’s 33 seconds and 4; 59 loops time out during probes versus 13 with Luna.Timed-out loops submit their last proposed state.Source: J DIFFERENT CRITIC MODELS · p. 22, Figure 10 · p. 22
  • GLM-5 raises the submitted pass rate to 70%, a gain of +7.2 points [+4.3, +10.6], not significantly different from Luna’s gain.GLM-5 rejects 52% of failing first claims and 6% of passing first claims; its probes take a median 102 seconds and 13 commands.Source: J DIFFERENT CRITIC MODELS · pp. 22–23, Figure 10 · p. 22

K RESUMING OR RESTARTING

  • Restarting submits a passing state in 66% of trials versus 72% for resuming, a difference of −6.1 points [−10.1, −2.2].Restarting costs 1.6 times as much in model calls and averages 9.3 minutes per trial versus 7.8; 61 of 161 restarted trials timed out.Source: K RESUMING OR RESTARTING · p. 23, Table 9 · p. 23

L STRONGER MODELS AS ACTOR AND CRITIC

On 15 selected Terminal-Bench 2.1 tasks, Probe-and-Resume with stronger actor models does not significantly improve pass rates. The authors attribute the limited recovery opportunity to stronger actors’ higher first-claim pass rates.

L STRONGER MODELS AS ACTOR AND CRITIC

  • None of three stronger-actor and critic combinations gains significantly on the 15 selected tasks.Astra with Fable stays near baseline (63% versus 61%); Astra with Opus gains 4.0 points with an interval including zero, and Opus on both sides leaves the 69% baseline unchanged.Source: L STRONGER MODELS AS ACTOR AND CRITIC · p. 23, Table 10 · p. 24
  • Most first claims from these stronger actors already pass, leaving little to recover; remaining failures are not caught by a critic of the same strength.Only 33% of Luna’s first claims on these tasks pass, and the loop works on the rest.Source: L STRONGER MODELS AS ACTOR AND CRITIC · p. 23
  • Eight Opus 5.5 actor trials were refused on two lifescience tasks and counted as zero; Astra security-task endpoint errors caused no refusals.The authors identify these as model issues rather than issues with the loop.Source: L STRONGER MODELS AS ACTOR AND CRITIC · p. 24

M SWE-BENCH PRO: TASKS AND GRADING

The SWE-bench Pro evaluation uses fixed task sets and grades proposed states with the benchmark verifier on forks. Its reported gain comes from medium tasks; on hard tasks, the gain cannot be distinguished from zero.

M SWE-BENCH PRO: TASKS AND GRADING

  • Only tasks whose reference patch passes in the trial environment are scored; 20 tasks are excluded because grading tests require network access.The excluded tasks include 18 Go tasks, one task downloading Node.js, and one Python test that opens a connection when loaded.Source: M SWE-BENCH PRO: TASKS AND GRADING · p. 24
  • Each proposed state is graded on a fork after test files and fixtures are reset, then hidden tests are applied and run.The fork is discarded after grading, so hidden tests never reach the actor’s or critic’s sandbox; only the critic’s verdict controls continuation.Source: M SWE-BENCH PRO: TASKS AND GRADING · p. 25
  • Unlike patch-only grading, the trial fork retains files outside or ignored by the repository, installed packages, and running processes.With no network, no trial could download a package, but local changes outside the repository still count in the authors’ grading.Source: M SWE-BENCH PRO: TASKS AND GRADING · p. 25
  • The gain comes from medium tasks; on hard tasks it cannot be distinguished from zero, using either the first trial or all five.The task sets are fixed independently of the evaluated agent’s performance; the benchmark has no medium tier, which the authors define from released results.Source: M SWE-BENCH PRO: TASKS AND GRADING · pp. 24–25, Table 11 · p. 25

Related papers

Loading 2610.21088v1…