PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Agent Computer Use

Jing Yu Koh, Ruslan Salakhutdinov, Daniel Fried

arXiv:2606.01533v1cs.MAcs.CLcs.LG

TL;DR

Complex long-horizon computer-use tasks challenge serial agents. This paper introduces multi-agent coordination with DAG planning, parallel subagents, and continuous replanning, consistently improving benchmark success rates by 3.4–25.5%.

  • Problem

    Single serial computer-use agents are limited on complex long-horizon tasks that benefit from decomposition, parallel execution, and continual replanning.

  • Method

    MACU uses a manager to maintain a revisable DAG of subtasks executed in parallel by computer-use subagents under partial observability.

  • Results

    MACU consistently improves success rates across four benchmarks, including a 25.5% increase on Odysseys over strong single-agent baselines.

  • Takeaways & Limitations

    Multi-agent coordination, continuous replanning, and parallel execution are promising axes for scaling computer-use agents to longer tasks.

  • Takeaways & Limitations

    MACU can require substantially more model calls and execution time, and may increase wall-clock time on largely serial tasks.

Abstract

from arXiv · show

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.

1 Introduction

The paper proposes multi-agent computer use (MACU) to address the limits of serial computer-use agents on complex, long-horizon tasks through decomposition, parallel execution, and continual replanning. Its manager-driven DAG framework handles partially observable GUI environments and improves benchmark success over strong single-agent baselines.

  • Motivation: MACU targets complex long-horizon tasks that benefit from decomposition, parallel execution, and consistent replanning beyond primarily single-agent CUA deployments.The paper frames serial deployment as suboptimal for these tasks.
  • MACU framework: A manager model decomposes tasks into a directed acyclic graph (DAG) whose subtasks are executed in parallel by computer-use subagents.At each iteration, ready subtasks are launched while the manager updates the graph using completed-subagent information.
  • MACU framework: The manager can add, cancel, rewire, or modify pending subtasks, enabling continual adaptation as new information arrives.This open-ended graph decomposition directly targets long-horizon and complex tasks.
  • Partial observability: MACU treats computer use as partially observable because filesystem state, processes, browser tabs, cookies, and dynamic content may not be re-observable by downstream subtasks.The manager and DAG retain and pass forward information that downstream agents cannot independently recover.
  • Empirical results: 4.7% on OSWorld, 3.4% on Online-Mind2Web, 8.7% on WebTailBench-v2, and 25.5% on Odysseys are MACU’s reported success-rate improvements over strong single-agent baselines.MACU also substantially improves wall-clock time on OSWorld and Odysseys and shows more promising scaling trends with increased test-time computation.

2 Related Work

Related work spans computer-use benchmarks and rapidly improving frontier-model performance, alongside LLM-based multi-agent systems across several domains. This paper positions its framework as a general, simple, and scalable approach for partially observable computer use using a planner and homogeneous subagent workers.

  • Computer Use Agents: OSWorld evaluates 369 open-ended Ubuntu tasks spanning native applications and multi-application workflows, while WindowsAgentArena adapts the framework to 150+ real-Windows tasks.Gym-Anything automatically installs and configures real software using coding and audit agents.
  • Computer Use Agents: 200 long-horizon web navigation tasks in Odysseys are based on real human browsing patterns.Frontier models have quickly improved on computer-use benchmarks, with GPT-5.4 at 75.0% on OSWorld, Opus 4.6 at 72.7%, and Kimi K2.6 at 73.1%, surpassing human performance at 72.4%.
  • Multi-Agent LLM Systems: LLM-based multi-agent systems have been explored in software engineering, scientific discovery, web search, and other settings.Prior work often represents these systems as computational graphs that can be dynamically adjusted and scaled.
  • This Paper: This paper develops a general, simple, and scalable multi-agent framework for partially observable computer use with one planner and homogeneous subagent workers.The framework addresses grounding, computer interaction, and long-horizon planning, contrasting with prior work using specialized low-level-action modules or fully observable environments.

3 Multi-Agent Computer Use

MACU uses a manager agent to decompose tasks into a DAG and coordinate parallel CUA subagents on dependency-ready subtasks. The manager replans this graph from subagent observations, while isolated VMs preserve modularity across subagents.

  • Manager: A manager agent creates and mutates a directed acyclic graph of subtasks while coordinating a pool of CUA subagents.The initial DAG is generated from the natural-language task instruction and validated as JSON.
  • Parallel execution: At each iteration, subagents execute nodes on the DAG’s ready frontier in parallel, subject to satisfied dependencies.The ready frontier contains nodes whose dependencies are completed, and the algorithm limits launches by the maximum parallel-subagent count N.
  • Replanning: After subagent completion, the manager replans using the current DAG, recent screenshots, final responses, and parent-node VM context.Replanning can add, remove, modify, or cancel nodes; each edit consumes one unit of the replan budget B.
  • Subagents: Each subagent runs a standard screenshot-observation and computer-action loop inside its own isolated virtual machine, treated as a black box by MACU.This design keeps the manager agnostic to model-specific assumptions and the particular CUA used.

4 Experiments

Experiments across four desktop and web-navigation benchmarks show that MACU improves success rates over single-agent baselines, with larger gains on complex long-horizon tasks. Ablations further indicate that dynamic replanning, stronger managers and subagents, and parallel execution drive performance and speedups.

  • Benchmark setup: The evaluation covers OSWorld, Online-Mind2Web, WebTailBench-v2, and Odysseys, spanning desktop control, real-world websites, broad navigation, and long-horizon browsing.OSWorld contains 369 tasks, Online-Mind2Web 300 tasks across 136 websites, WebTailBench-v2 609 tasks, and Odysseys 200 long-horizon tasks.
  • Main results: MACU improves OSWorld success rate from 43.8% to 48.5% and reduces median wall-clock time from 26.6 to 21.4 mins per task, while Online-Mind2Web success rate rises from 52.2% to 55.6%.Online-Mind2Web tasks are largely serial, so their wall-clock time increases despite the success-rate improvement.
  • Main results: MACU improves WebTailBench-v2 success rate from 20.8% to 29.5% and percentage of rubrics satisfied from 35.9% to 46.3%, benefiting from parallel decomposition of complex tasks.The passage attributes larger gains on WebTailBench-v2 and Odysseys to tasks that are more complex or require longer horizons.
  • Scaling: MACU scales more favorably with inference budget: single-agent success rates plateau earlier, while the gap widens as more CUA subagent steps are executed.The scaling analysis plots success rate against the total number of CUA subagent steps executed.
  • Ablations: Dynamic replanning, stronger subagents, and stronger managers each improve MACU: planning beyond B > 1 raises success rate, capable managers can more than double the fixed worker’s rate, and Qwen3.6-27B is adopted as the subagent backbone.Opus 4.6 is the best evaluated manager at 58.3% SR, while Qwen3.6-27B is selected because of its strong subagent results.
  • Parallel execution: Increasing parallel subagents from N = 1 to N = 4 reduces median wall-clock time from 25.4 minutes to 7.9 minutes, while success rate rises from 53.3% to 60.4%.On the Odysseys easy subset, average rubric score also improves from 76.4% to 85.8%; these results exclude inference overhead.

5 Conclusion

The paper argues for moving beyond single serial computer-use agents and proposes MACU for complex, long-horizon tasks. Across four diverse benchmarks, MACU improves strong single-agent baselines and offers more favorable test-time scaling.

  • Conclusion: MACU targets complex and long-horizon computer-use tasks through a general multi-agent framework.The framework is proposed as an alternative to the prevailing single serial agent paradigm.
  • Conclusion: Across four diverse computer-use benchmarks, MACU consistently improves the success rates of strong single-agent baselines.
  • Conclusion: MACU exhibits more favorable test-time scaling than its single-agent counterpart and solves long-horizon tasks.

A Additional Experimental Details · A.1 Virtual Machines Technical Details

The appendix specifies shared MACU experiment settings, resource allocations, and VM infrastructure for parallel subagents, including VMware and Apptainer/QEMU backends with mechanisms for state transfer, resumption, retries, and parallel variants.

  • A Additional Experimental Details: Table 7 summarizes hyperparameters shared across main benchmark runs and retained for ablations unless specific settings change.The explicitly variable settings include the manager model, CUA worker model, parallelism, and replan budget.
  • A Additional Experimental Details: MACU hosts Qwen/Qwen3.6-27B with vLLM on two A6000 GPUs using tensor parallelism of 2.Each task also requires 64G RAM and 16 CPUs for subagent virtual machines.
  • A Additional Experimental Details: MACU runs 6 tasks per vLLM server, typically fully saturating the inference workload.Benchmark completion times vary by task, and approximate wall-clock times are reported in Sec. 4.1.
  • A Additional Experimental Details: Single-agent runs allow up to 200 steps per subagent while using 16G RAM and 4 CPUs per task.The reduced resource allocation reflects running only one CUA worker per task.
  • A Additional Experimental Details: The Qwen3.5 and Qwen3.6 baseline implementation is reproduced from existing implementations because the original releases lack implementation details.Despite falling short of reported Qwen3.5 release numbers, the implementation substantially outperforms other open-weight CUAs.
  • A.1 Virtual Machines Technical Details: MACU launches each CUA subagent through OSWorld’s DesktopEnv, which records VM endpoints and service ports in vm_info.json.The runtime supports initialization from a provided VM state and exposes HTTP, browser-debugging, VNC, and VLC ports.
  • A.1 Virtual Machines Technical Details: The VMware backend snapshots claimed pool VMs for DAG nodes, reclaims completed predecessor VMs for state transfer, and clones frozen states for retry or variant nodes.Reclaimed VMs preserve the predecessor’s final desktop and filesystem state, while clones let parallel attempts start from the same pre-subtask state without sharing mutable VMs.
  • A.1 Virtual Machines Technical Details: The Apptainer/QEMU backend runs the OSWorld image inside an Apptainer SIF, giving each fresh subagent a writable qcow2 overlay backed by a shared base image.Initialization and resumption are handled similarly to the VMware backend.

B Limitations

MACU’s gains come with higher inference-time cost, dependence on task decomposability, and added infrastructure complexity. Benchmark results also do not establish readiness for real-world deployment because evaluations omit important operational risks and constraints.

  • Evaluation limitations: The results support multi-agent coordination as a compelling research direction, not as evidence that MACU is ready for real-world deployments.This limitation reflects the practical considerations and unresolved directions identified by the paper.
  • Practical limitations: N = 4 parallel subagents and B = 10 replan budget can require substantially more model calls and VM execution time than single-agent settings.The added compute is not always offset by wall-clock speedup on Online-Mind2Web.
  • Practical limitations: MACU is strongest on tasks that naturally decompose into parallel exploration, independent information gathering, retries, or alternative execution strategies.Benefits are lower on tasks involving single-task GUI execution, serial interactions, or inherently sequential work.
  • Practical limitations: MACU requires isolated VMs, screenshot context, filesystem diffs, and an archive pool, introducing overhead for maintaining additional infrastructure concerns.Computer-use state can span screenshots, open tabs, filesystem changes, background processes, cookies, and application state.
  • Evaluation limitations: OSWorld, Online-Mind2Web, and Odysseys measure computer-use capabilities but do not fully capture risks and operational constraints of real-world deployments.Real user environments may involve private accounts, irreversible actions, authentication flows, or stricter reliability requirements.

C Broader Impacts · D Additional Qualitative Examples

MACU is presented as a research framework with potential benefits and ethical risks, requiring safeguards before real-world deployment. Additional examples illustrate spawned subtasks, manager-generated instructions, and evolving DAGs.

  • C Broader Impacts: MACU is evaluated on existing computer-use and web-navigation benchmarks as a research framework, without deployment to real users or introduction of new weights or datasets.Its potential positive impact is discussed alongside ethical considerations rather than demonstrated through live-user deployment.
  • C Broader Impacts: MACU is intended as a research demo, not for live accounts, production websites, or security-sensitive environments, and future use requires authorization guardrails and access safeguards.Real-world deployment should follow further research and careful scoping of accessible applications, websites, files, and accounts.
  • C Broader Impacts: Dispatching multiple CUA workers could scale phishing, spam, manipulation, scraping, and unauthorized workflows, while benign agents may still make unintended or destructive changes.Eventual deployment should impose action restrictions and require human approval for irreversible or sensitive operations.
  • C Broader Impacts: Screenshots, filesystem diffs, and selected files may expose credentials, cookies, personal information, or proprietary data, requiring redaction, limited retention, and terms-of-service compliance.Privacy safeguards should protect artifacts routed through the manager and shared archive pool.
  • C Broader Impacts: More capable agents may automate routine computer workflows and augment people, but deployment could affect repetitive computer-work roles and create worker transition costs.Developers should proactively consider human oversight and the effects on workers whose roles center on repetitive computer tasks.
  • C Broader Impacts: Because MACU depends on manager and CUA models, performance may vary across languages, interfaces, accessibility contexts, and user groups, requiring diverse evaluation and user appeal mechanisms.Underlying models may inherit biases or uneven capabilities from their training data and design.
  • C Broader Impacts: MACU’s manager-mediated DAG enables safety checks during decomposition, replanning, file management, and final aggregation, including rejecting disallowed websites or confirming file deletion.Isolated VMs, explicit subtask instructions, and terminating looping or policy-violating subagents are additional mitigation strategies.
  • D Additional Qualitative Examples: Additional qualitative examples show spawned subtasks, evolving DAGs, and manager-generated subtask instructions.These examples provide concrete illustrations of how the multi-agent workflow changes across tasks.

D.1 OSWorld Examples

The OSWorld examples show MACU recovering from failed desktop actions, gathering evidence in parallel, and combining complementary search results through manager-directed subtasks.

  • D.1 OSWorld Examples: MACU recovers from missing software during a font-install task by sending manager-written instructions to CUA subtasks.The example is documented in Fig. 7 and Tab. 8.
  • D.1 OSWorld Examples: When an automatic-save setup attempt reaches its per-subtask time limit, the manager launches recovery subtasks.This GUI timeout recovery is shown in Fig. 8.
  • D.1 OSWorld Examples: After the app-store path fails, the manager recovers Spotify installation through a CLI-based subtask.The fallback is illustrated in Fig. 9.
  • D.1 OSWorld Examples: The manager parallelizes README and Colab-script inspection, then combines their evidence in a follow-up configuration step.This parallel evidence-gathering workflow appears in Fig. 10.
  • D.1 OSWorld Examples: The manager runs two complementary search branches—through the main cars.com interface and a direct relevant URL—then aggregates their findings.The complementary web-search strategy is shown in Fig. 11.

D.2 Online-Mind2Web Examples

Online-Mind2Web examples show MACU recovering from timeouts and browser stalls by resuming partial progress or adding alternative execution branches. These examples demonstrate recovery through filtered-search resumption, direct-page navigation, and fallback search routes.

  • Recovery strategies: MACU resumes a successful filtered-search state after a Petfinder GUI-filter attempt times out before applying all constraints.The manager sends written instructions to each CUA subtask in this run.
  • Recovery strategies: After repeated Amtrak browser stalls, the manager adds a direct branch to the passenger-identification page.The branch bypasses the stalled landing page or search-results path.
  • Recovery strategies: When date-specific Yahoo Finance lookups time out, MACU launches direct-URL and simple-search branches that both identify Tesla’s requested closing price.The two fallback routes provide alternative ways to complete the lookup.

D.3 Odysseys Examples

The Odysseys examples illustrate MACU’s ability to decompose long-horizon web-navigation tasks into parallel branches, retry blocked paths, and revise plans as information arrives.

  • Odysseys Examples: MACU splits travel planning into hotel-review and flight-search branches, then retries blocked branches through alternate routes.The manager writes instructions for each CUA subtask in the run.
  • Odysseys Examples: For scholarship research, the manager retries a blocked American University branch and finds PIPS scholarship information for the final outreach plan.
  • Odysseys Examples: For restaurant comparison, the manager aggregates weather, menu, and brunch-hours information and adds a verification branch after an incomplete first attempt.

D.4 WebTailBench Examples · E Manager Prompts

The WebTailBench examples show MACU combining parallel decomposition with retries, variants, and replanning to solve price-comparison, hotel-availability, and compositional job-search tasks. The manager prompts formalize DAG dependencies, agent roles, cancellation and retry decisions, state-preserving continuation, and graph-update constraints.

  • D.4 WebTailBench Examples: Parallel price comparison decomposes retailer-specific lookups and aggregates returned prices into one comparison.The example covers A Tale of Two Cities across Amazon, Barnes & Noble, Books-A-Million, ThriftBooks, Powell’s, and AbeBooks, with paperback and hardcover results combined by retailer and format.
  • D.4 WebTailBench Examples: Retry expansion turns a stalled hotel-booking attempt into converging branches that confirm no availability.The branches include direct-URL, forward-navigation, and date-confirmation variants for fixed dates at a SureStay by Best Western property.
  • D.4 WebTailBench Examples: Compositional job search first enumerates open roles by level, then adds a salary-range subtask for the most senior role.The Genentech example combines role counts with the senior-level salary range in the final aggregation.
  • D.4 WebTailBench Examples: Other examples recover from failed or timed-out GUI paths by launching direct-URL, CLI, keyboard-shortcut, retry, or variant branches.These runs include font installation, automatic saves, Spotify installation, Petfinder filtering, Amtrak identification, and Yahoo Finance historical-price lookup.
  • E Manager Prompts: The graph-decomposition prompt requires unique subtask identifiers, explicit dependencies, and agent_type values of either cua or manager.Website interaction must use cua, while pure reasoning or synthesis over other subtasks’ text outputs may use manager; aggregation depends on every needed subtask.
  • E Manager Prompts: The replanning prompt favors natural completion over cancellation unless evidence shows a subtask is unrecoverable, and recommends parallel variants for alternative approaches.Repeated identical errors, uncleared login walls, wrong-domain navigation, or obsolete goals are listed as good cancellation triggers; slow progress or one failed click are not.
  • E Manager Prompts: State-preserving continuation uses init_from to clone a completed CUA subtask’s final VM state into a dependent replacement or follow-up subtask.The cloned state can include browser tabs, open applications, typed text, and downloaded files, while init_from must reference an existing CUA subtask and appear in dependencies.
  • E Manager Prompts: Replanning updates must use the no_change or update action schema, with updates modifying graph elements through permitted partial fields.A no_change action requires empty graph-operation fields, whereas an update requires at least one remove, add, modify, or cancel operation; modified identifiers and agent types cannot be changed.
Loading 2606.01533v1…