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

cs.CLAug 22, 2026

Spine-Branch Coordination for Multi-agent Computer Use

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

Organizations: Scale AI · University of Texas at Dallas · Johns Hopkins University

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 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.

Figures & tables

Figure 1: Spine-Branch Coordination . A task is decomposed into a role-typed dependency DAG. VM state is continuous along the spine via VM cloning; artifacts flow freely between any dependent nodes. Branches commit extractable artifacts on completion and their VMs are discarded after use.

	Primary Metrics					Execution Stats (per task)
Method	Rubric Avg. $\uparrow$		Success Rate $\uparrow$		Cost ( $)$ \downarrow$ *	Agent Steps	CUA Actions	Manager Tok. (K)	CUA Tok. (M)
Qwen3.6-27B
Single-Agent	46.7	$\pm 1.08$	24.0	$\pm 0.76$	0.00	67	92	–	2.5
MACU	53.9	$\pm 0.83$	28.5	$\pm 0.76$	1.46	187	250	492	5.9
Spine-Branch	66.6	$\pm 2.72$	44.0	$\pm 1.32$	0.44	198	334	106	6.7
$\Delta$ vs. MACU	+12.8		+15.5		$-$ 1.02	-	-	-	-

Table 1: Main results on Odysseys. Each block fixes the sub-agent backbone and compares coordination strategies. Best values among multi-agent methods (MACU, Spine-Branch) are in bold on the primary metrics. For Spine-Branch we annotate the relative change vs. MACU in green . The standard variance are shown for three evaluation runs.

Figure 2: Model Performance Across Task Difficulties

Method	Spine	Branches	Success Rate	Rubric Avg.	Actions / Task	Cost / Task
Single-Agent	–	–	62.2	83.0	91.9	$1.16
MACU	–	–	57.8	80.2	288.1	$4.53
Branch-only	No	Yes	66.7	83.2	258.9	$2.54
Spine-only	Yes	No	71.1	88.0	261.7	$2.37
Spine-Branch	Yes	Yes	73.3	90.6	203.8	$2.20

Table 2: Component Ablation on 45 Tasks from Odysseys with Qwen3.7-Plus

CUA backbone	Tokens $\downarrow$	Tokens $\uparrow$
Qwen3.6-27B	$9\ (+6.2)$	$6\ (+7.6)$
gpt-5.4-mini	$6\ (+5.4)$	$2\ (+3.5)$
Qwen3.7-Plus	$8\ (+7.7)$	$0\ (+0.0)$

Table 3: Distribution of Two Main Patterns that Step-budget Prompting Induces

Figure 3: Ablation of step-budget prompting across Single-Agent, MACU, and Spine-Branch, which shows inconsistent effects on Single-Agent and MACU, it consistently improves Spine-Branch.

Method	Reward $\uparrow$	Success Rate $\uparrow$	Steps	Timeouts
Single-Agent	0.22	5/65	74	0/65
Spine-Branch	0.16	3/65	127	21/65
Mean reward conditioned on Spine-Branch completion status
Subset	$n$	Single-Agent	Spine-Branch	$\Delta$
SB finished	44	0.220	0.224	$+0.004$
SB timed out	21	0.219	0.026	$-0.193$

Table 4: Results on the 65 decomposable OSWorld 2.0 tasks. Reward is the mean programmatic score in

[0,1]

; Success Rate is the fraction of tasks receiving full reward.

Method	Reward $\uparrow$	Success Rate $\uparrow$	Steps	Timeouts
Single-Agent	0.12	0/19	83	0/19
Spine-Branch	0.17	1/19	132	0/19

Table 5: Results on 19 OSWorld 2.0 tasks worth decomposing.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Action	Arguments	Description
Mouse
mouse_move	coordinate	Move the cursor to $(x,y)$ .
left_click	coordinate, [text]	Left-click at $(x,y)$ ; optional held modifier key(s).
right_click	coordinate, [text]	Right-click at $(x,y)$ .
middle_click	coordinate, [text]	Middle-click at $(x,y)$ .
double_click	coordinate, [text]	Double-click at $(x,y)$ .

Appendix

Table 6: The CUA action space. Each step emits exactly one action. coordinate is an

(x,y)

pixel target. The text argument has two cases: (i) for type and answer it is the literal string to type or return; (ii) for click and scroll actions it is optional and names modifier key(s) to hold during the action (e.g. ctrl, shift, ctrl+shift).

CUA backbone	Manager	Macro	SR
Qwen3.7-Plus	Single-Agent	0.830	0.622
	Spine-Branch, opus-4-8	0.906	0.733
	Spine-Branch, gpt-5.4-mini	0.819	0.644
Qwen3.6-27B	Single-Agent	0.585	0.311
	Spine-Branch, opus-4-8	0.751	0.511
	Spine-Branch, gpt-5.4-mini	0.682	0.444

Appendix

Table 7: Manager ablation for Spine-Branch on Odysseys-45: a strong (opus-4-8) vs. a weak (gpt-5.4-mini) manager, with only the manager changed.

Figure 5: Coordination graphs for the Babywearing-jacket task and Iceland Camper-Van Trip task. The graphs on the left are from MACU and the graphs on the right belong to Spine-Branch.

Figure 6: Agent step distribution of Spine-Branch and MACU on Odysseys with Qwen3.6-27B as backbone . MACU’s manager continuously re-plans ( $2.6$ replans/task) and aggressively cancels underperforming subtasks: $\mathbf{10.8\%}$ of MACU subtasks abort within $\leq\!10$ steps, versus $\mathbf{3.5\%}$ for Spine-Branch (shaded bin). Because an aborted subtask accrues almost no work, this pulls MACU’s mean steps-per-subtask down to $31.3$ (vs. $40.3$ for Spine-Branch) and, despite MACU attempting more subtasks, leaves it with fewer CUA tokens ( $5.93$ M vs. $6.69$ M) and fewer agent actions ( $250$ vs. $334$ ) per task. Spine-Branch fixes its plan up front and runs each subtask to completion, so its heavier, uninterrupted execution costs more compute but yields far higher completion (success rate $44.0\%$ vs. $28.5\%$ ; macro score $66.6\%$ vs. $53.9\%$ )

Multi-Agent Coordination

Multi-agent coordination studies how autonomous agents align actions, share information, and divide work to achieve individual or collective goals.

See all 520 papers

Multi-Agent Computer Use
Jun 1, 2026Jing Yu Koh, Ruslan Salakhutdinov, Daniel FriedMulti-Agent Coordination Computer-Use Agents
Carnegie Mellon University
Scaling Inference-Time Compute with Teams of Coding Agents
Oct 12, 2026Keenan Samway, Daniel D'souza, Omar Darwiche Domingues +3Inference-Time Scaling Inference-Time Compute Allocation
Cohere Labs · Cohere
When Parallelism Pays Off: Cohesion-Aware Task Partitioning for Multi-Agent Coding
May 31, 2026Xu Yang, Lunyiu Nie, Ethan Chandra +3Graph Partitioning Multi-Agent System Optimization
1The University of Texas at Austin · University of Oxford

Jun 1, 2026J/K move · Enter open · S save

Multi-Agent Computer Use

Jing Yu Koh, Ruslan Salakhutdinov, Daniel Fried

Carnegie Mellon University

Multi-Agent Coordination Computer-Use Agents Long-Horizon Agent Tasks Multi-Agent Planning

Open paper AskPDF arXiv

Computer use agents (CUAs) today are primarily deployed as single serial agents. This setup is suboptimal for complex long-horizon tasks that benefit from task decomposition, parallel execution, and consistent re-planning based on new information. In this paper, we argue that we should instead move towards evaluating and building multi-agent computer use (MACU) systems. These systems, which emphasize planning and parallel execution, alleviate many of the shortcomings of single-agent CUAs. We propose a general multi-agent setup in which a manager model decomposes computer use tasks as a directed acyclic graph (DAG), encoding relevant dependencies and goals for subagents. At each iteration, the manager dispatches parallel CUA subagents to carry out nodes on the ready frontier of the DAG, and continuously revises the DAG (adding, canceling, or rewriting nodes) as new findings arrive from subagents. This design treats the partially observable environment of computer use as a first class challenge: information that downstream agents may not be able to re-observe are retained and passed forward through the manager and DAG structure. We demonstrate that MACU consistently improves over strong single-agent baselines by

3.4-25.5\%

on desktop (OSWorld) and web navigation (Online-Mind2Web, WebTailBench, Odysseys) benchmarks, exhibits more favorable test-time scaling, and solves complex long-horizon tasks where single-agent CUAs get stuck. On Odysseys, a long-horizon web navigation benchmark, MACU improves average task completion wall-clock time by

{\sim} 1.5 \times

, demonstrating its efficacy in speeding up traditionally slow CUA pipelines. Our findings highlight that multi-agent coordination is a promising axis for scaling computer use agents to work productively for longer and more effectively. We release all code and interactive visualizations at https://jykoh.com/multi-agent-computer-use.

Abstract

Multi-Agent Coordination

Explore similar work

Multi-Agent Computer Use

Scaling Inference-Time Compute with Teams of Coding Agents

When Parallelism Pays Off: Cohesion-Aware Task Partitioning for Multi-Agent Coding