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

2610.21088 ↗ · 2026-10-15 · cs.AI, cs.LG · h-max 13 · 0 citations

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

The finding

Headline claim

For terminal computer-use agents, test-time compute is best spent verifying claimed completions, not guiding search: a critic that probes a fork of the environment only when the actor says it is done raises success by 8.4 percentage points, while conventional MCTS with a trajectory critic adds almost nothing at nearly 4x cost.

The test

All 89 tasks of Terminal-Bench 2.1 with five trials each (GPT-5.6 Luna actor, Terminus-2 harness, Waypoint branchable containers), plus a SWE-bench Pro replication; 1,111 intermediate states and 406 candidate final states scored against 5-rollout pass rates and the ground-truth verifier; critic variants with no access, read-only, and execute access compared at 25/50/75% trajectory depth and at completion; costs priced at AWS Bedrock token rates.

Effect size & scope

Baseline pass@1 63.4% at $10.70; MCTS with trajectory-only critic 64.0% (+0.6, CI [−4.5, +5.5]) at $40.79; Probe-and-Resume reaches 72.4% at submission. At intermediate states critics rank continuations barely better than chance (49–56% at 25% depth; 64–69% at 75%), and execute access helps little (+4.4 points pooled). At final states, execute access cuts error from 36–39% to 22% (false rejects >50% down to ~20%); adding a fork of the initial state raises accuracy 76% to 80% and cuts false rejects 24% to 17%. Gains hold within one actor-harness-model combination on one main benchmark.

Limitations

The authors concede their measurements do not rule out better value estimators or other search policies, do not show completion-time is optimal, and note scope and model dependence (single actor model, two benchmarks). They also drop 18 ungradable trials from search baselines and note pass-rate targets estimated from only 5 rollouts pull measured critic accuracy toward 50%. Unstated: results are benchmark tasks with deterministic verifiers present at grading; a critic that effectively reverse-engineers verifier-style checks may not transfer to fuzzier real workplace tasks; appendix text is truncated so full SWE-bench Pro numbers are not visible.

Counterpoint

Small task count (89) with wide bootstrap CIs on several comparisons; all critic variants use the same model family as the actor, so conclusions may be model-specific; the headline comparison prices only tokens and excludes verifier overhead and engineering cost; 'approaches Codex CLI at less than half cost' is a harness-on-harness comparison within one lab's setup; the 8.4-point gain could partly reflect retry-with-feedback rather than superior verification, since the actor resumes after rejection.

Economy implication

Little or nothing yet for aggregate economics. It is a methods paper, but it bears on the price of reliability: if agent quality can be bought with a critic loop on the same base model rather than a stronger model, the value of frontier-model differentiation at the app layer erodes further, and inference spend shifts toward verification compute. Watch whether vendors productize completion-checking critics within 12 to 24 months.

Who this matters for

Technical Capability: Gives agent builders a concrete, measured design rule: intermediate-state value estimates are near useless in terminal environments, but execute-access probing at claimed completion cuts misclassification by roughly a third.

Market & Valuation: Weakly relevant: if verification loops substitute for stronger models, model-level pricing power and the premium for frontier upgrades shrink at the margin.

Bears on (advisory · papers never write evidence)

[1.3] Agentic reliability (multi-step completion without human correction) is improving materially, not just peak single-shot.

[1.4] Inference-time compute yields gains that don't saturate quickly on hard reasoning.

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.