PaperlayerView exact revision on arXiv

Source-linked AI summary

Spine-Branch Coordination for Multi-agent Computer Use

Mian Zhang, Manasi Sharma, Sheng Zhang, Minglai Yang, Kejian Shi, Ying Liu, Zhiyu Zoey Chen, Daniel Yue Zhang

arXiv:2608.22077v1cs.CLcs.MA

TL;DR

Long-horizon computer-use tasks create coordination challenges because extractable deliverables can be copied, but independently evolved VM states cannot be merged. Spine-Branch Coordination plans one persistent VM lineage with parallel branches for information gathering, improving success rate by 6.0% to 16.5% and reducing per-task cost by 34% to 70% across three CUA backbones.

  • Problem

    Multi-agent computer use must coordinate extractable deliverables and non-mergeable VM state, including logged-in sessions, open tabs, and unsaved edits.

  • Method

    Spine-Branch Coordination represents tasks as a graph with a state-preserving spine and parallel branches that return extractable deliverables before their VMs are discarded.

  • Results

    Success Rate improves over MACU by 6.0% to 16.5% while per-task financial cost decreases by 34% to 70% across three CUA backbones on long-horizon Odysseys tasks.

  • Takeaways & Limitations

    Treating single-parent VM inheritance as a first-class constraint avoids VM merging and costly state reconstruction while retaining substantial parallelism.

  • Takeaways & Limitations

    Approximately 18% of tasks are genuine decomposition candidates because branching trivial tasks can impose more coordination overhead than the parallelized work.

Abstract

from arXiv · show

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 two 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%, indicating that explicitly modeling VM-state merging constraint enables multi-agent computer use to scale efficiently.

1 Introduction

Long-horizon computer-use tasks motivate parallel multi-agent execution, but independently evolved VM states cannot be merged. Spine-Branch Coordination makes this constraint explicit by retaining state on a spine and using disposable branches for extractable work.

  • Long-horizon GUI workflows create lengthy serial trajectories with growing context and more opportunities for error.
  • VM state, including sessions, open tabs, and unsaved edits, cannot be copied and merged like extractable files.A new VM can inherit state from only one existing VM after independently evolved VMs diverge.
  • Existing systems either execute serially in one environment or parallelize across VMs without modeling single-parent VM inheritance.When stateful subtasks converge, they must retain one VM, discard others, reconstruct lost state, or revise the plan.
  • Spine-Branch Coordination represents tasks as spine-branch graphs, preserving persistent state along a cloned spine while parallel branches return extractable deliverables and are discarded.Artifacts can flow through arbitrary dependencies, whereas VM state follows one lineage and never requires merging.
  • 6.0% to 16.5% higher success rate and 34% to 70% lower per-task financial cost were achieved on 200 Odysseys tasks across three CUA backbones.The reported gains were particularly pronounced on hard tasks and as task horizons increased.

2 Spine-Branch Coordination for Multi-agent Computer Use

The framework separates information that must remain attached to a VM from artifacts that can be transferred freely. A role-typed dependency DAG coordinates a continuous spine, parallel branches, and manager aggregation without VM merging.

  • Information types: Extractable deliverables can be copied, broadcast, and aggregated, whereas VM state must be booted fresh or cloned from one existing VM.VM state includes authenticated sessions, RAM, open applications, and in-progress GUI configurations.
  • Graph design: Spine-Branch keeps states that are costly to rebuild on one continuous spine and runs artifact-producing work in parallel branches.Branches may start from fresh VMs or spine clones, commit extractable artifacts, and discard their VMs after completion.
  • Graph constraints: The spine is the unique retained VM path, while branches are required to externalize results because their VMs are discarded.Artifact edges may connect any pair of nodes regardless of execution role.
  • Role architecture: The Manager plans the graph and dependencies, spine workers preserve live state, and branch workers perform auxiliary artifact-producing subtasks.The Manager does not execute GUI actions; it aggregates using the final spine VM and collected artifacts.
  • Communication channels: The dependency DAG uses live-state edges for single-parent cloning and artifact edges that support unrestricted fan-in and fan-out.The union graph is acyclic, allowing topological execution.
  • Coordination effect: Typed communication preserves one VM lineage and avoids merge conflicts and state reconstruction without using the Manager as an information relay.
  • Scheduling and context: Fixed-capacity scheduling launches ready workers concurrently, so wall-clock latency follows the graph’s critical path rather than the sum of trajectories.Workers receive localized instructions and only required artifacts, limiting context accumulation and interference.
  • Step-budget prompting: Step-budget prompting phases discourage redundant actions, prioritize deliverable completion, and require committing the best available result before budget exhaustion.It adds no agent, tool, or model call and protects branch outputs before disposable VMs disappear.

3 Experiments

Experiments compare Single-Agent, MACU, and Spine-Branch on 200 Odysseys workflows across three CUA backbones and difficulty levels. Spine-Branch achieves stronger task performance at lower cost, with especially clear advantages on hard tasks.

  • Benchmark and Evaluation: 200 Odysseys workflows across easy, medium, and hard difficulty levels are evaluated using Success Rate and Rubric Average.Each task requires every rubric to pass for success, and runs also report agent steps and token consumption.
  • Main Results: Spine-Branch outperforms MACU by 6.0% to 16.5% in Success Rate and 4.7% to 12.9% in Rubric Average across three backbones.The comparison fixes each sub-agent backbone while evaluating coordination strategies.
  • Main Results: 34% to 70% lower per-task financial cost accompanies Spine-Branch’s performance gains across all three backbones.Examples include $0.44 versus $1.46 on Qwen3.6-27B and $8.06 versus $12.23 on gpt-5.4-mini.
  • Additional Evaluation: On OSWorld 2.0, most tasks do not benefit from decomposition, motivating separate discussion of when decomposition is not worth the cost.This evaluation is reported as an additional benchmark beyond the main Odysseys testbed.
  • Main Results: 5× lower manager-token overhead is reported on representative backbones, including 115.0K versus 653.0K tokens on gpt-5.4-mini.Spine-Branch passes VM state along the spine and clean artifacts between dependent nodes instead of using the manager as a context relay.
  • Difficulty Analysis: Spine-Branch’s advantage is most pronounced on hard tasks, where its success rate degrades more mildly as task horizons lengthen.With Qwen3.7-Plus, it reaches 65.1% on hard tasks versus 60.9% on medium tasks.

4 Ablations & Analysis

Ablations show that Spine-Branch’s spine and branches are complementary, while step-budget prompting improves its performance through multiple channels. Additional analyses identify when decomposition helps and when coordination overhead outweighs its benefits.

  • Component Ablation: Removing the spine lowers Success Rate from 73.3% to 66.7%, while removing branches lowers it to 71.1%.The full framework also uses fewer agent actions per task than either ablation.
  • Component Ablation: 203.8 agent actions per task for the full framework compares with 258.9 for branch-only and 261.7 for spine-only.The result combines continuous VM-state preservation with parallel, failure-isolated exploration.
  • Step-budget Prompting: Step-budget prompting consistently improves overall performance and lowers cost for Spine-Branch, unlike its inconsistent effects on Single-Agent and MACU.The ablation applies the same prompting intervention across all three coordination strategies.
  • Step-budget Prompting: Step-budget prompting prevents truncation loss by prompting agents to commit partial results before the step cap, reducing token use.It also rescues abandoned tasks by pushing weak subagents to continue, which can increase token use.
  • When Decomposition Is Not Worth the Cost: On OSWorld 2.0, completed Spine-Branch runs achieve comparable rewards to Single-Agent, but timed-out runs sharply reduce its overall reward.The comparison covers 65 decomposable tasks and attributes the gap mainly to multi-worker execution overhead under the wall-clock limit.
  • When Decomposition Is Not Worth the Cost: Planner inspection identifies trivial branches as a failure mode, motivating decomposition only for independent, nontrivial tasks; approximately 18% of tasks qualify.The paper emphasizes that coordination benefits must justify coordination costs.

5 Related Work

Prior multi-agent coordination systems generally assume intermediate results are copyable text, but computer-use tasks may require transferring non-serializable live VM state. Related computer-use benchmarks and systems therefore motivate coordination designs that account for dynamic GUI and VM states.

  • CUA research builds on vision-language grounding and screenshot-to-action techniques, alongside native GUI models and increasingly long-horizon benchmarks.
  • Computer-use benchmarks span browser, desktop, and mobile environments with dynamic system states.
  • Multi-agent systems coordinate agents through centralized orchestration, decentralized shared context, or debate-based communication.
  • These coordination paradigms typically assume intermediate results are freely copyable text, making fan-out and gathering straightforward.
  • Computer use violates that assumption because a subtask’s deliverable may be live VM state that cannot be serialized or merged across machines.

6 Conclusion

The paper presents Spine-Branch coordination as a way to respect single-parent VM inheritance while combining persistent state with parallel artifact collection. Across Odysseys tasks and three CUA backbones, it reports higher success and lower cost than MACU.

  • Spine-Branch treats single-parent VM inheritance as a first-class constraint in multi-agent computer use.
  • The framework preserves live state along one spine and uses parallel branches for extractable deliverables, avoiding VM merging and costly state reconstruction.
  • 6.0% to 16.5% Success Rate improvement over MACU was observed across long-horizon Odysseys tasks and three CUA backbones.
  • 34% to 70% lower per-task financial cost was reported in the same evaluation.
  • The analyses attribute these gains to cleaner task decomposition and continuous preservation of important VM state.

A Prompts for Spine-Branch Coordination

The appendix specifies how Spine-Branch graphs assign operational state to one persistent spine while branches run disposable parallel work and exchange artifacts. It also describes decomposition rules, agent roles, state-flow semantics, and step-budget prompting.

  • A.1 Spine-Branch decomposition prompt: The planner emits a JSON dependency graph, and a deterministic legalizer validates references and derives the spine lineage.
  • A.1 Spine-Branch decomposition prompt: The manager decomposes tasks, while CUA subagents perform every desktop, browser, and file-producing operation; only final aggregation is managerial.
  • A.1 Spine-Branch decomposition prompt: Operational state flows through init_from from at most one parent, whereas named artifact contents can flow to any number of downstream nodes.
  • A.1 Spine-Branch decomposition prompt: Every task has exactly one spine chain whose surviving VM carries the final deliverable, while branches are parallel throwaway VMs that return reusable artifacts.
  • A.1 Spine-Branch decomposition prompt: Keep multiple pages or documents open within one spine VM rather than creating multiple operational nodes that would require multiple surviving VMs.
  • A.1 Spine-Branch decomposition prompt: Place heavy-to-restore live work on the spine and cheap independent lookups in branches, balancing state reuse against parallelism.
  • A.1 Spine-Branch decomposition prompt: A node’s role is independent of init_from: spine nodes preserve operational state, while branch nodes extract artifacts and discard their VMs.
  • A.2 Step-budget prompting: Step-budget prompting adds escalating reminders based on steps taken and the hard cap M without adding agents, tools, or model calls.

B The Odysseys-45 Development Subset

The Odysseys-45 development subset is a reproducible, difficulty-balanced sample used for costly ablations and diagnostics. It contains 45 tasks selected from the 200-task benchmark, with action-space details documented separately.

  • A 45-task Odysseys development subset is used because live browser execution and rubric judging make repeated ablations costly.
  • The subset samples 15 tasks from each difficulty level through stratified random sampling without replacement.
  • Sampling is stratified only by difficulty, with no filtering by website, category, or rubric count.
  • The appendix lists the selected task IDs grouped into easy, medium, and hard categories.
  • Each CUA step emits exactly one action, with coordinates for targets and text used either as literal input or optional modifiers.

C CUA Action Space

CUA workers interact with desktop environments through screenshot-conditioned GUI actions, using a defined computer-use tool interface and pyautogui execution. Episodes terminate through explicit agent actions or task limits.

  • CUA Action Space: Each CUA step combines a screenshot and running action history with one emitted tool call describing a GUI action.The action executes in the desktop VM through pyautogui before the next screenshot.
  • CUA Action Space: The open-weight backbones receive a single computer_use tool, while gpt-5.4-mini uses an equivalent provider-native action set.Both interfaces translate to identical pyautogui primitives in the same environment.
  • CUA Action Space: Episodes end when the agent emits terminate or answer for information-seeking tasks, or when the per-worker limit is reached.

D Does a Weak Manager Degrade Spine-Branch?

The manager ablation changes only the manager while comparing Spine-Branch against a Single-Agent reference. Weaker managers reduce scores, but preserve the decomposition structure and often retain coordination gains.

  • Manager Ablation: Replacing opus-4-8 with gpt-5.4-mini reduces the macro score by 0.07–0.14 across CUA backbones.The ablation changes only the manager, isolating manager quality as the tested factor.
  • Manager Ablation: Both managers produce nearly identical decompositions, averaging ≈1.9 spine and ≈3.5 branch nodes per task.The reported loss is attributed mainly to weaker per-node instructions and aggregation rather than degenerate decompositions.
  • Manager Ablation: With the weak manager, Spine-Branch still exceeds Single-Agent on Qwen3.6-27B and gpt-5.4-mini, scoring 0.682 vs. 0.585 and 0.678 vs. 0.596.On Qwen3.7-Plus, the gain disappears because the strong single agent leaves less room for coordination gains.

E Case Study

The case study compares coordination graphs and agent step distributions for Spine-Branch and MACU. Spine-Branch uses a distinct graph structure and shows fewer very short aborted subtasks in the reported Qwen3.6-27B analysis.

  • Case Study: Figure 5 compares MACU and Spine-Branch coordination graphs on the Babywearing-jacket and Iceland Camper-Van Trip tasks.MACU graphs appear on the left and Spine-Branch graphs on the right.
  • Agent Step Distribution: 10.8% of MACU subtasks abort within ≤10 steps, compared with 3.5% for Spine-Branch.The comparison is reported for Odysseys with Qwen3.6-27B as backbone.
  • Agent Step Distribution: 31.3 mean steps per subtask for MACU contrasts with 40.3 for Spine-Branch.MACU’s aborted subtasks accrue almost no work, lowering its mean despite attempting more subtasks.
Loading 2608.22077v1…