cs.AIOct 15, 2026

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

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

Organizations: Columbia University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Figure 1: Left: tree search scores partial states with a critic and submits a leaf; Probe-and-Resume calls the critic only when the actor claims to be done, lets it probe a fork of that state, and resumes the actor on a rejection. Right: accuracy against the cost of running all of Terminal-Bench 2.1 (89 tasks, five trials each); the shape is the agent harness. The GPT-5.6 Luna squares are our three configurations (no search, MCTS, Probe-and-Resume), priced at the AWS Bedrock rate like GPT-5.6 Luna + Codex; the other points and their costs are from Harbor Hub ( Appendix C ).
 Pass@1Δ\Delta vs. baseline [95% CI]Total model cost
Baseline63.4%–$10.70
Actor + branching tools61.0%−2.4-2.4 [ −6.7-6.7 , +2.0+2.0 ]$11.40
MCTS with trajectory-only critic64.0%+0.6+0.6 [ −4.5-4.5 , +5.5+5.5 ]$40.79
Table 1: Branching tools and MCTS don’t improve pass@1 on Terminal-Bench 2.1 (GPT-5.6 Luna).
Figure 2: Critics by position in the actor’s trajectory, on 89 Terminal-Bench 2.1 tasks (numbers in Appendix F ); traj , read , act are CtrajC^{\mathrm{traj}} , CreadC^{\mathrm{read}} , CactC^{\mathrm{act}} (§ 3.2 ), traj with the plain prompt (variants in Appendix H ). (a) Share of same-task, same-depth pairs that q^\hat{q} orders like the pass rates of their 5 continuations; all pools the depths; the dashed line marks chance (50%). (b) Passing states that v^\hat{v} rejects and failing states it accepts.
 readsrunsholds the answerall
 FR ↓\downarrowFA ↓\downarrowFR ↓\downarrowFA ↓\downarrowFR ↓\downarrowFA ↓\downarrowFR ↓\downarrowFA ↓\downarrow
CtrajC^{\mathrm{traj}}46%5%64%3%68%7%60%5%
CreadC^{\mathrm{read}}42%16%54%5%62%12%52%10%
CactC^{\mathrm{act}}9%19%24%19%38%31%22%22%
Table 2: Verdicts at candidate final states against the verifier, over 406 states of 89 tasks, grouped by what the verifier does to decide a task: it reads files and compares them with a value or format it stores (22 tasks), runs the artifact or probes a service (48), or holds the answer , a value that cannot be recovered from the environment (19). FR: share of passing states rejected. FA: share of failing states accepted. Model cost per state in Appendix G .
Figure 5
Figure 5: Probe-and-Resume. When the actor claims to be done, the critic uses forks of S(r)S^{(r)} and S0S_{0} and can freely execute actions to evaluate the state; they are then discarded ( ×\times symbol). If the critic rejects, the actor resumes at S(r)S^{(r)} with the critic’s feedback. Otherwise, S(r)S^{(r)} goes to the verifier VV .
 Pass@1Δ\Delta vs. baseline [95% CI]Total model cost
Baseline63.4%–$10.70
Probe-and-Resume72.4%++ 9.0 [ ++ 5.6, ++ 12.6]$23.14
Restart from S0S_{0}66.3%–$38.12
Codex CLI (reference)76.6%–$50.29
Table 3: Pass@1 on Terminal-Bench 2.1 over 5 trials per task; cost is the model cost of one trial of every task at the AWS Bedrock rate ( Appendix C ). Restart from S0S_{0} restarts the actor from S0S_{0} after each rejection ( Appendix K ); Codex CLI is Harbor Hub’s job (§ 4.2 ), priced at the same rate.
Figure 6: (a) Flow diagram that describes the true pass rate of the first state the actor proposes to the critic S(1)S^{(1)} , the critic’s assessment of it, and the true pass rate of the final state submitted to the verifier. Trials that exceed the time limit count as failures. (b) Pass@1 if stopped after KK rounds.
Figure 7: Probe-and-Resume on Terminal-Bench 2.1 and Medium/Hard tasks in SWE-bench Pro.
Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

TaskTT (min)VerifierS0S_{0}
adaptive-rejection-sampler15R1, X1 
bn-fit-modify60R1, O 
break-filter-js-from-html20R1, X1 
build-cython-ext15R1, X1, O✓
build-pmars15R1, X1 
build-pov-ray200R1, X1, O✓
Appendix
Table 4: The 89 tasks of Terminal-Bench 2.1. TT : the task’s time limit for the actor. Verifier : every code its assertions need (R1–R3 read, X1–X2 run, O compares with a value only the verifier holds); § 3.2 groups tasks by the strongest one. S0S_{0} : the task states a requirement relative to the initial state (§ 3.3 ).
ModelUsed inInputCachedOutputSource
GPT-5.6 Lunaall Luna arms; Luna + Codex0.20 (0.25 as a cache write)0.021.20Bedrock model card, global
Claude Sonnet 5critic, Appendix J2.000.2010.00Anthropic list price
GLM-5critic, Appendix J1.00–3.20Bedrock price list, us-east-1
GPT-6 AstraAppendix L13.75 (as cache write)1.1055.00Bedrock model card, in-region
Claude Fable 5.1Appendix L13.75 (as cache write)0.27555.00Bedrock price list, in-region
Claude Opus 5.5Appendix L5.50 (as cache write)0.2222.00Bedrock price list, in-region
Appendix
Table 5: Prices in dollars per million tokens. Input : uncached input; cached : cache read; a dash means the price list has no cached rate and cached tokens are billed as input.
 Baseline+ snapshot and restore tools
Pass@1 (passed / graded trials)63.4% (282/445)61.0% (269/441)
Trials using a tool–3
Snapshots saved by the actor–1
Restores (to S0S_{0} )–3 (2)
Model cost / sweep$10.70$11.40
Appendix
Table 6: The actor with and without snapshot and restore tools, 89 tasks of Terminal-Bench 2.1, five trials per task.
 Pass@1Model cost / sweep
Baseline63.4%$10.70
MCTS64.0%$40.79
Δ\Delta [95% CI]+0.6+0.6 [ −4.5-4.5 , +5.5+5.5 ]3.81 ×\times
Appendix
Table 7: Pass@1 of the baseline and MCTS, five trials per task. MCTS has no graded trial on kv-store-grpc , so its pass@1 is over 88 tasks and the baseline’s over 89. Δ\Delta is MCTS minus the baseline; its interval is a bootstrap over tasks that draws the same tasks for both arms ( Appendix D ).
  intermediate state, depth 
  25%50%75%allfinal state
Pairwise accuracy (%) ↑\uparrowtraj4956645465
 read5655695961
 act5262685976
Pairwise, decided pairs (%) ↑\uparrowtraj5673686865
 read6770787461
Appendix
Table 8: The numbers behind Figure 2 . At the intermediate depths, the critic’s output is its estimate q^\hat{q} and the outcome is the pass rate of 5 continuations. At the final state, the output is the verdict v^∈{0,1}\hat{v}\in\{0,1\} and the outcome is the verifier’s judgment. A pair is two states of the same task at the same depth (at the final state: two final states of the same task) whose outcomes differ; pairwise accuracy is the share of pairs that the output orders like the outcome, with tied outputs counting one half. A decided pair has outcomes 0 and 1. The selection gain is the outcome of the state with the highest output among a task’s states at one depth, minus the mean outcome of those states. A false accept is a failing state with output ≥\geq 50%; a false reject is a passing state with output << 50%. At intermediate depths, these two rates use only the states from which all continuations pass or all fail. MAE is the mean of ∣output−outcome∣|\text{output}-\text{outcome}| (at the final state, the misclassification rate); best constant is the MAE of the best single answer. Rows X−YX-Y are differences between two critics. The column all pools the three depths.
Figure 8: Model cost per state of the critics of Figure 2 , on the same states. (a) Intermediate states at 25/50/75% depth; all pools the three depths. (b) Candidate final states. Intervals are 95% bootstrap intervals over tasks.
Figure 9: The three trajectory-only prompts on the states of Figure 2 ; plain is traj in Figure 2 . (a) Mean absolute error by position (Table 8 ); dashes mark the best constant answer. (b) At the candidate final state: the share of passing states rejected and the share of failing states accepted. (c) Model cost per state ( Appendix C ); for summary + ledger it includes the calls that write the summary and the ledger. Intervals are 95% bootstrap intervals over tasks.
Figure 10: GPT-5.6 Luna as the actor, with each model as the critic. (a) The loop’s gain over the baseline in the submitted pass rate (Table 3 ); bars are 95% bootstrap intervals over tasks. (b) How long the critic’s probes take, over the probes that return a verdict; the markers are the medians.
 Pass rateTotal model costTime / trial
Probe-and-Resume72.4%$23.147.8 min
Restart from S0S_{0}66.3%$38.129.3 min
Appendix
Table 9: Resuming vs. restarting after a rejection, on the 89 tasks of Terminal-Bench 2.1, five trials per task. Pass rate and cost as in Table 3 ; time is the actor’s and the critic’s per trial, averaged.
Actor / CriticTasksTrialsBaselineProbe-and-ResumeΔ\Delta [95% CI]RefusedCost
Luna / Luna157533.3%40.0%++ 6.7 [ −- 2.7, ++ 16.0]0$4.04
Astra / Fable 5.1157561.3%62.7%++ 1.3 [ −- 6.7, ++ 9.3]0$126.94
Astra / Opus 5.5157569.3%73.3%++ 4.0 [ −- 2.7, ++ 10.7]0$65.83
Opus 5.5 / Opus 5.5157569.3%69.3%0.0 [0.0, 0.0]8$52.80
Appendix
Table 10: Probe-and-Resume with stronger models as the actor and the critic, on the same 15 tasks of Terminal-Bench 2.1, five trials per task. Luna: GPT-5.6 Luna (the trials of Table 3 on these tasks); Astra: GPT-6 Astra; Fable, Opus: Claude Fable 5.1, Claude Opus 5.5. Baseline and Probe-and-Resume as in Table 3 . Intervals are 95% bootstrap intervals over tasks. Refused : trials the actor’s model refused; they count 0 in both columns. Cost : the total over the trials that were not refused ( Appendix C ).
 TasksTrialsBaselineProbe-and-ResumeGain [95% CI]
Hard, first trial414170.7%73.2%++ 2.4 [ −- 4.9, ++ 9.8]
Hard, all five trials4120565.4%66.3%++ 1.0 [ −- 3.9, ++ 5.9]
Medium18618682.3%90.9%++ 8.6 [ ++ 3.8, ++ 14.0]
Both, first trial (Figure 7 )22722780.2%87.7%++ 7.5 [ ++ 3.1, ++ 11.9]
Appendix
Table 11: SWE-bench Pro by task set. Baseline: the first proposed state; Probe-and-Resume: the submitted state. Gains are in points, with 95% intervals over tasks ( Appendix D ).
More in this topic

Computer-Use Agents

Computer-use agents perceive and operate graphical interfaces and software tools to complete tasks across websites, apps, and desktops.

See all 160 papers

Explore similar work

CardsList
Sep 10, 2026

Grounding Agent Memory: Environment-Probing Curation for Enterprise Agents

Persistent memory is entering production-oriented agent platforms to help long-horizon agents accumulate experience across sessions. Yet a post-task curator agent restricted to completed trajectories can preserve errors, overgeneralize partial evidence, or retain stale knowledge. We introduce environment-probing curation, a deployment-compatible extension that gives an existing asynchronous curator agent least-privilege, read-only world tools to check, scope, and refresh candidate memories. It requires no model retraining and leaves the task agent, retriever, memory representation, and production write authority unchanged. In a production-like GitHub Copilot (GHCP) harness built on its SDK, we compare stateless execution, full in-context learning, GHCP + Mem, and GHCP + Mem (w/ Env Probing) on CLBench database exploration and 90 adapted APEX management-consulting tasks. On CLBench, probing raises pass rate from 39% to 73% and pass-discounted reward from 8.60 to 22.60 while reducing queries from 8.8 to 4.7 per question and task-agent cost from $3.38 to $1.68. Across six APEX worlds, all 18 memory-versus-baseline mean reward comparisons are positive and task-agent tool calls fall by 16--75%; probing gives the best task-agent reward gain per dollar in five worlds. Probing also attains higher mean reward than GHCP + Mem on both Sonnet 4.6 and Opus 4.7 without schema drift. Environment probing therefore turns existing agent-memory curation into an environment-informed, auditable process while preserving a compact task-time interface.

Susheel Suresh, Hazel Mak, Sahil Bhatnagar +2

Microsoft Corporation One Microsoft Way, Redmond, WA 98052, USA

Agent MemoryMemory-Augmented AgentsAgent Memory Management
AskPDF
Mar 9, 2026

OSExpert: Computer-Use Agents Learning Professional Skills via Exploration

General-purpose computer-use agents have shown impressive performance across diverse digital environments. However, our new benchmark, OSExpert-Eval, indicates they remain far less helpful than human experts. Although inference-time scaling enables adaptation, these agents complete complex tasks inefficiently with degraded performance, transfer poorly to unseen UIs, and struggle with fine-grained action sequences. To solve the problem, we introduce a GUI-based depth-first search (GUI-DFS) exploration algorithm to comprehensively explore and verify an environment's unit functions. The agent then exploits compositionality between unit skills to self-construct a curriculum for composite tasks. To support fine-grained actions, we curate a database of action primitives for agents to discover during exploration; these are saved as a skill set once the exploration is complete. We use the learned skills to improve the agent's performance and efficiency by (1) enriching agents with ready-to-use procedural knowledge, allowing them to plan only once for long trajectories and generate accurate actions, and (2) enabling them to end inference-time scaling earlier by realizing their boundary of capabilities. Extensive experiments show that our environment-learned agent takes a meaningful step toward expert-level computer use, achieving a around 20 percent performance gain on OSExpert-Eval and closing the efficiency gap to humans by around 80 percent

Jiateng Liu, Zhenhailong Wang, Rushi Wang +6

University of Illinois Urbana-Champaign · Stevens Institute of Technology

Computer-Use AgentsAgent Skill LearningComputer-Use Agent Benchmarks
AskPDF
Aug 24, 2026

Exploit More, Explore Smarter for Budget-Constrained Agentic Search

Budget-constrained agentic search arises when an LLM agent must refine candidates under a small evaluation budget, because validation is expensive, generation requires multiple model calls, or both. In this regime, standard MCTS allocates budget poorly: exploration bonuses dominate at low visit counts, unpromising siblings are expanded before promising chains can deepen, and branching is independent of node quality. We introduce ExTS, a tree-search policy that treats expansion itself as a value-of-information decision. ExTS combines three mechanisms: discriminative reward shaping to separate candidates under narrow score distributions, a stochastic virtual child that estimates the value of creating a new branch from the parent's reward history, and quality-conditioned branching that expands only when a node's score justifies the budget cost. Across prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization, ExTS is competitive with or improves over task-specific tree-search baselines, with an average relative gain of +5.5% using a single fixed configuration. We further introduce pilot-run diagnostics that characterize what makes budget-constrained agentic search problems structurally different from one another, providing both understanding of the problem space and practical guidance for adaptation.

Haoyang Fang, Bernie Wang

Amazon AGI

Agentic SearchInference-Time SearchMonte Carlo Tree SearchLLM Agent Workflow Optimization
AskPDF