Spine-Branch Coordination for Multi-agent Computer Use

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.