In terminal‑based computer‑use settings, agents only observe a partial view of the underlying state. Test‑time search, which explores alternative actions and lets a critic select promising branches, is expected to boost success. We evaluated a Monte Carlo tree search (MCTS) configuration in such environments and found that it does not significantly raise task success.
Two factors undermine critic performance: the agent’s observations omit state needed for evaluation, and intermediate states provide little evidence about eventual success. Empirically, critics rank continuations only slightly better than random at intermediate points, and even granting more environment access yields only marginal gains.
We then examined when to invoke a critic and what access to grant it. Results indicate that calling the critic only when the agent believes it has finished is more effective than invoking it during partial progress. Moreover, the critic should receive read, write, and execute rights on a fork of both the current and initial computer state, allowing it to probe and even perform destructive actions without affecting the real environment, thereby exposing hidden state the trajectory omits.
These insights lead to the Probe‑and‑Resume design: when the agent claims to be done, the critic probes a forked state; if the critic rejects, the agent resumes from where it stopped.
On the Terminal‑Bench 2.1 benchmark, this approach raises success by 8.4 percentage points over conventional‑critic MCTS and approaches the success rate of the Codex CLI agent while costing less than half as much.
Review