acceptodds
Desk rejected at ICLR 2027

Spine-branch Coordination for Multi-agent Computer Use

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Computer use agents (CUAs) are increasingly deployed as multi-agent systems that decompose a task into multiple subtasks executed across parallel virtual machines (VMs). However, a critical physical bottleneck is that the state of multiple VMs cannot be merged. Previous systems handle this ad-hoc rather than treating it as a first-class concern. We propose spine-branch coordination for multi-agent computer use, a framework that decomposes a task into a Spine-Branch graph, where the spine carries the main task flow with continuous VM state and branch tasks execute in parallel to collect information the spine needs to complete the task. Branch VMs are discarded once their tasks finish, so no VM merging ever occurs. Experiments show that on 200 long-horizon tasks from Odysseys and across three CUA backbones, Spine-Branch improves success rate over the baseline system by 6.0% to 16.5%, while reducing per-task cost by 34% to 70% and manager-token overhead by approximately 5×, indicating that respecting VM-state constraints enables multi-agent computer use to scale efficiently.

Primary area:
applications to robotics, autonomy, planning
Keywords:
computer use agent, multi-agent coordination

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_KpgTOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper separates multi-agent computer-use workflows into a persistent VM-state lineage, called the spine, and disposable branches that return transferable artifacts. This prevents plans from requiring incompatible VM states to be merged. Experiments on Odysseys show improved success and lower API costs, while OSWorld experiments reveal settings where decomposition introduces excessive overhead.

Critical strengths

The distinction between transferable artifacts and persistent execution state is clear and practically motivated. It turns an important deployment constraint into an explicit planning rule.

The main evaluation covers 200 tasks, three worker backbones, and repeated runs. The negative OSWorld results and manager-backbone ablation provide useful evidence about the framework’s limits.

Critical weaknesses

The comparison with MACU changes state handling, artifact routing, and the amount of runtime manager involvement together. The component ablations help, but the full system improves success over spine-only by just 2.2 points on the 45-task subset. A larger paired comparison and a MACU variant with explicit state inheritance would better establish which design choices drive the gains.

The main scores depend on one LLM judge examining trajectories with up to 200 screenshots. The paper does not report a human audit of these judgments. Different coordination methods produce different amounts and distributions of evidence, so the authors should explain how final VM state and branch artifacts are presented consistently to the judge.

The reported financial savings use API-token prices and assign zero cost to the locally hosted worker. VM provisioning, cloning, local inference, and wall-clock execution are outside that comparison. These costs matter for the efficiency claim, particularly given the substantial timeout rate observed on OSWorld.

Questions for authors

How much improvement remains over a state-aware MACU baseline with direct artifact transfer?

Do blinded human judgments confirm the main success-rate differences?

What are the end-to-end latency and resource costs when local inference and VM operations are included?

Reviewer_2HUxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper aims to solve the problem of decompsing the subtasks to run on parallel VMs for computer use agents. Motivated by that VM states cannot be directly merged, the authors propose Spine-Branch, which utilize a planner to decompose the task into a DAG, and the sub-tasks are executed in parallel and the necessary artifacts will be passed to the nodes need them. Spine-Branch improves success rate over MACU by 6-16.5 pts while cutting the cost by 34%-70% on Odyssey tasks.

Critical strengths
  • [S1] The motivation is clear, and the design makes sense.

The motivation that VM states cannot be merged studies a real problem for multi-agent CUA systems.

  • [S2] Large gains at lower cost.

While Spine-Branch improves the performance against the strongest baselines in Odyssey tasks, it still significantly reduce the per-task cost and the planner cost.

Critical weaknesses
  • [W1] The gains are not shown to come from VM inheritance.

In Table 2, Branch-only, which never inherits VM state, already beats MACU by 8.9 SR, and the spine adds only 3 of 45 tasks, apparently in single runs. So the gains may come from static planning, the prompt, or SBP rather than from the VM constraint, which is the paper’s central claim.

  • [W2] Limited novelty and a narrow setting.

MACU already clones a VM from a single parent and keeps one final VM, so the main delta is fixing this lineage at planning time. The method assumes full control of the VM layer and is tested only on a read-only benchmark without login-gated tasks, where the live state is mostly open tabs. Outside this setting, the results are negative. There are only 19 out of 65 tasks in OSWorld 2 that worth decomposing, and Spine-Branch loses to a single agent.

Questions for authors
  • [Q1] Baseline. Why does MACU use a replan budget of 5 when its paper uses 10? Is SBP enabled for MACU in Table 1?

  • [Q2] Variance. Is the ± in Table 1 a standard deviation or a standard error? The gain on gpt-5.4-mini seems to be within noise. Please add per-task paired CIs, win/tie/loss against the single agent, and repeated runs for the ablations.

  • [Q3] Judging. For multi-VM runs, which screenshots and artifacts does the judge see? Odysseys scores each rubric with a separate judge call and validated this against humans on single-agent trajectories, so why score all rubrics in one pass here?

  • [Q4] Cost. Several listed costs are below what the token counts imply. For example, for MACU on Qwen3.6-27B, 492K Opus tokens cost at least 2.46 usd at the input rate, but 1.46 usd is listed. Wall-clock time and VM cost numbers are also missing, though they matter most for a parallel method.

  • [Q5] Deployment. How would the method work when the agent operates a user’s own machine or browser, where live cloning is unavailable?

Reviewer_e65XOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Building upon existing VM inheritance and outcome propagation capabilities, the author restricts the graph generated by the planner: critical states are propagated along a single main thread, other branches can only be connected via the handover of outcomes, and manager intervention is minimised through the use of a fixed data flow. On 200 Odysseys tasks across three CUA backbones, the authors report success-rate improvements of 6.0–16.5 percentage points over MACU and reductions of 34%–70% in token-priced API cost. Additional experiments on OSWorld 2.0 show decomposition can underperform single-agent execution when coordination overhead outweighs useful parallel work.

Critical strengths
  1. The distinction between transferable artifacts and live operational state provides a useful abstraction for planning computer-use workflows. Encoding these dependencies separately makes otherwise implicit handoff requirements explicit, and the single-lineage construction prevents plans that require a worker to inherit multiple VM states.

  2. Reporting both task completion and coordination costs makes the practical benefit easier to assess.

Critical weaknesses
  1. The contribution relative to closely related systems needs clearer positioning.** MACU [1] already supports VM-state inheritance and file transfer. ParaGUI [2], which is not discussed, combines parallel GUI workers, artifact exchange, and repeated dispatch to the same worker when preserving UI state is useful. Neither imposes the same topology, but these capabilities narrow the conceptual contribution to the single-spine restriction. The rebuttal should explain what this restriction adds beyond existing mechanisms.
  2. The experiments do not sufficiently isolate the benefit of the single-spine topology. The MACU comparison also changes planning, artifact routing, and runtime replanning and cancellation, leaving several plausible explanations for the gains. Moreover, single-parent inheritance permits multiple independent state lineages; it does not establish the need for one global spine. Table 2 offers partial support for the proposed combination, but its success-rate advantage over spine-only execution amounts to approximately one task out of 45. The additional comparison that holds the other coordination mechanisms fixed is necessary.
  3. Odysseys results rely on a single LLM judge inspecting trajectories of up to 200 screenshots, but the paper does not clearly explain how parallel worker trajectories, branch artifacts, and the retained final VM are assembled into the judge’s evidence. It also does not report an independent human or programmatic audit of these judgments. Because the methods organize and expose intermediate results differently, a common judge alone does not establish that their outcomes are equally observable.

References: [1] Koh et al. Multi-Agent Computer Use. https://arxiv.org/abs/2606.01533v1 [2] Yu et al. Beyond Sequential Interaction: Benchmarking Parallel Execution and Coordination for GUI Agents. https://arxiv.org/abs/2607.22689v1

Questions for authors
  1. What evidence separates the benefit of the single-spine topology from state-aware parent selection and reduced manager intervention?
  2. How exactly are parallel trajectories, branch artifacts, and the final retained VM presented to the Odysseys judge? Do the three evaluation runs involve independent agent executions or repeated grading?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.