- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper builds a harness to help computer-use agents on long tasks. Its Checkpoint Tree Search (CTS) splits a task into milestones. At each milestone it saves the full virtual-machine state, runs several branches from that state, and keeps one before moving on. The agent can use both GUI and command-line tools. It can also submit screenshots and the contents of saved files, so the verifier can check whether a milestone is done. The authors evaluate the full harness on OSWorld and OSWorld-V2, and study the action space, the evidence mechanism, and the checkpointed search separately.
Critical strengths
Strength 1: The paper provides useful implementation details for restoring desktop state
Restoring the full virtual machine at each milestone keeps open applications, dialogs, and unsaved edits. The authors report the cost of saving and restoring, and give the infrastructure settings and prompts. Others building retry mechanisms for desktop agents can reuse these details.
Strength 2: The evidence mechanism gives a clear gain
In Table 2, adding evidence collection and review to the tree raises the graded score from 0.2444 to 0.3024, moving it from below best-of-3 (0.2750) to above it. Checking saved files as well as screenshots addresses a real problem in desktop tasks: what the screen shows may not be what is saved to disk.
Critical weaknesses
Weakness 1: Missing baseline: best-of-3 with the same evidence mechanism
The evidence mechanism does not need checkpoints or branch search, so it could also be added to plain best-of-3 over full trajectories. The paper does not report this. This matters because in Table 2 the tree without evidence (frame-window verifier) scores 0.2444, below best-of-3 (0.2750), and passes it only after evidence is added (0.3024). The evidence condition also gives the agent extra tools to collect and read evidence, which may improve execution and not just branch selection. So best-of-3 with the same evidence might score about as well. Without this baseline, the value of branching mid-task is unclear.
Weakness 2: The "theoretical ceiling" and "exploration bottleneck" claims go beyond the evidence
The pass@3 that CTS beats is the best of three trajectories that were already sampled, not a theoretical limit of independent sampling. CTS produces new trajectories, so beating this number does not "breach the theoretical ceiling." Table 9 also does not show that CTS explores better. The best tree branch scores 0.6250, below flat pass@3 (0.6667), so the tree's candidate pool is weaker. The tree only gets closer to the best of its own pool. This does not support crediting the gain to better exploration. Also, picking a branch early changes what can be reached later, so looking only at the kept candidates cannot rule out bad picks at earlier milestones. It is still unclear where the gain of branch search comes from, and when it beats full-trajectory sampling.
Weakness 3: Related work misdescribes GTA1, and the new contribution is unclear
Related Work says GTA1 selects only at the whole-trajectory level. But the official GTA1 abstract says it samples several action proposals at each step and picks one. Tree Search for Language Model Agents also runs candidate actions in real web environments and uses reset-and-replay to go back to earlier states and keep searching. CTS restores full virtual machines instead, but picking per step and searching from mid-task states are not new. What is new is combining milestone-level branching with file-based evidence on a full desktop VM. This is useful engineering, but with the current baselines and analysis it is not clear what research advance it adds over existing agent search methods.
Questions for authors
-
(Related to Weakness 1) Have you run best-of-3 with the same evidence tools and verifier as CTS? How much does branching mid-task add over it?
-
(Related to Weakness 2) Table 9 shows that the tree's best branch scores below flat pass@3. What evidence then supports that exploration, not selection, is the bottleneck? Did you check the branches dropped at earlier milestones and how they affected later outcomes?
-
(Related to Weakness 3) What problems does full-VM checkpointing solve that GTA1's per-step selection and reset-and-replay search cannot? Do you have experiments or failure cases that show this?
-
(Related to Weakness 1, Weakness 2) Table 2 reports 0.3024 for the tree with evidence, while Tables 6 and 8 report 0.3142. Which configuration and task set does each number use? Do all OSWorld-V2 rows in Table 1 use the same executor model and task set?
4 comments
Thanks for the response. But I think my worry about contribution in W3 is still not solved. As an engineering combination of exiting work and doesn't make a a clear improvement over existing methods. So I keep my score.
Thank you for the follow-up. We respectfully disagree with the characterization that our work is merely an engineering combination without a clear research advance:
1. Our contribution is not a new generic tree-search algorithm, nor do we claim it to be. As explicitly stated in our paper, we study test-time scaling and harness design for long-horizon computer-use agents. While intermediate-state search has been explored in other agent settings, applying it to full desktop environments introduces distinct challenges: persistent application states, unsaved edits, complex GUI interactions, and the lack of reliable intermediate verification. Addressing these challenges requires more than directly transferring an existing search algorithm.
2. Our contribution is supported by controlled empirical findings, rather than simply assembling existing components. With identical evidence capabilities and API budgets, CTS improves OSWorld-V2 graded score from 29.2% to 32.6% over best-of-3. We further show that the benefits increase with task horizon, reaching +5.0 percentage points on tasks with three or more milestones. Our experiments also quantify the reliability and efficiency of full-VM restoration versus reset-and-replay, and independently analyze evidence-based verification and hybrid GUI–CLI execution.
3. we believe research contributions should be evaluated beyond the novelty of individual algorithmic primitives. Understanding how to allocate test-time compute, verify intermediate progress, and reliably recover state in long-horizon desktop environments is itself an important research problem. Our work provides a concrete methodology, controlled evaluations, and empirical insights into these questions, which are not established by the cited prior work.
We fully acknowledge the relevant prior search methods and will clarify the positioning accordingly. However, we believe the demonstrated improvements and systematic findings constitute a meaningful contribution to computer-use agent research.
Thanks for your time, but I still think this is a method paper not an analysis paper, because most of experiments are aim to support that the harness you proposed.
Separately, the answer to Question 4 still conflicts with the paper: Table 2, Section 5.1, and Table 15 describe the 0.3024 as using evidence, while the response says it does not. Please clarify this in the revision.
Table 2 is an ablation using a standard LLM judge, without our full evidence-based evaluation system; this setting scores 30.24%.
To be honest, I like the engineering behind the fast VM checkpointing, and i expect this will become a important infra for CUA agentic rl and test time scaling, however your paper claimed things do not convince me to give a 3 rating. If this as a analysis paper, i think what you need is to relay on this mechanism to compare more tree search methods and analyze when they work and when they fail. And i think analyzing how many middle stats to keep exploring is a good experiements, because a state that does not look very good at the current point does not decide whether the task will succeed in the end. Just like this submission, the current version does not convince me yet, but I think it could become a strong paper with further improvement.
Finally, I'm sorry, but I will keep my score of 2.
Thank you for pointing out the missing baseline and the problems with our interpretation. We address each below.
1. Best-of-3 with the same evidence. We add best-of-3 with the same evidence tools, collection instructions, and verifier as CTS. The judge checks the full task for best-of-3 and the assigned milestone for CTS. Both methods use the same executor, task set, and total API budget.
CTS adds 3.4 percentage points with evidence available to both methods. These percentages represent mean graded score. Separately, we apply frame-based and evidence-based selection to the same evidence-equipped flat candidate pool. The scores are 28.0% and 29.2%, respectively. This 1.2-point difference measures the effect of selection on a fixed pool. The matched-evidence comparison above measures what CTS adds when both agents can collect evidence during execution.
2. What pass@3 and the pruning analysis show. We agree with your correction. The reported pass@3 is the best checker score among three sampled trajectories. We remove the “theoretical ceiling” claim and the claim that exploration, rather than selection, is the bottleneck. We also remove the suggestion that CTS independently explores all N^m segment combinations.
In Table 9, CTS scores 61.11%, close to the best of its own explored branches at 62.50%. That branch pool is weaker than flat pass@3 at 66.67%. This table describes selection within the explored pool; it does not evaluate earlier pruning decisions.
We therefore continue the retained and discarded states at 30 sampled boundaries, using the same downstream policy and budget. A discarded state leads to a better outcome at 3 boundaries. Its average advantage, counting zero at the remaining boundaries, is 1.2 percentage points. We report the extra cost of this analysis separately.
Across the full V2 comparison, CTS gains 0.0 percentage points on one-milestone plans, 2.5 on two-milestone plans, and 5.0 on plans with three or more milestones. These results locate the benefit in multi-stage tasks and show where early branch choices lose useful continuations.
3. Related work and full-VM recovery. We will correct the GTA1 description: it selects among action proposals at each step. Tree Search for Language Model Agents also searches from intermediate environment states using backtracking. Our contribution is the study of milestone search, file-based evidence, and full desktop-state recovery in one harness. The matched-evidence baseline above tests the value added by this search setup. GTA1, Tree Search for Language Model Agents.
GTA1 ranks proposals before execution. CTS runs alternative continuations and restores the selected state. Full-VM snapshots save memory, device state, and disk, preserving unsaved edits and open dialogs. To compare restoration with replay, we test both on the same 30 boundaries:
VM restoration takes 9 seconds versus 180 seconds for replay in this test. The state checks cover the relevant application, files, and dialog state. Downstream scores are 32.0% and 34.0%. Restore time excludes saving the snapshot; Table 4 reports a V2 snapshot cost of 12.5 seconds. We include snapshot costs in the overall resource accounting. Services outside the VM require separate state management.
4. Configuration and task sets. The two scores come from different evaluation settings. Table 2 is an ablation using a standard LLM judge, without our full evidence-based evaluation system; this setting scores 30.24%. Tables 6 and 8 report the full system with evidence-based evaluation, which scores 31.42%. We will make this distinction explicit in the table captions and row labels, including the “tree, evidence” label in Table 2, which currently makes the two settings look identical.
We will also replace “ours” in Table 1 with the executor, task count, and budget for each row. The 40.3%/43.8%/45.7% rows need to be checked against their source runs. The same audit will reconcile Figure 3's task count and Table 9's subset description.
Thanks again for the valuable feedback, we will updates those experiments in the paper or appendix later after discussion.