PaperlayerView exact revision on arXiv

Source-linked AI summary

UFO3: Weaving the Digital Agent Galaxy

Chaoyun Zhang, Liqun Li, He Huang, Chiming Ni, Bo Qiao, Si Qin, Yu Kang, Minghua Ma, Qingwei Lin, Saravan Rajmohan, Dongmei Zhang

arXiv:2511.11332v2cs.DCcs.MA

TL;DR

Existing agent frameworks are often confined to one device or platform, limiting cross-device workflows that draw on distributed resources. UFO3 coordinates heterogeneous agents through an evolving task graph and persistent communication, and NebulaBench results report successful orchestration with lower latency than a sequential baseline.

  • Problem

    Most agent frameworks remain confined to a single device or platform, while modern workflows span heterogeneous endpoints and resources.

    Source: §1 · p. 2

  • Method

    UFO3 models requests as mutable task DAGs that evolve during execution and coordinates asynchronous work across heterogeneous devices.

    Source: §1 · p. 3, §13 · p. 43

  • Results

    31% faster than a sequential baseline, UFO3 achieved 83.3% subtask completion and 70.9% task success on NebulaBench.

    Source: §13 · p. 43

  • Takeaways & Limitations

    UFO3 brings heterogeneous devices and agents into a unified fabric for collective execution of user intents.

    Source: §13 · p. 43

    UFO3’s overall capability remains constrained by individual device-agent competence, so one agent’s failure can cascade into global task failure.

    Source: §11.2 · p. 42

Abstract

from arXiv · show

Large language model (LLM)-powered agents are transforming digital devices from passive tools into proactive intelligent collaborators. However, most existing frameworks remain confined to a single OS or device, making cross-device workflows brittle and largely manual. We present UFO$^3$, a system that unifies heterogeneous endpoints, desktops, servers, mobile devices, and edge, into a single orchestration fabric. UFO$^3$ models each user request as a mutable TaskConstellation: a distributed DAG of atomic subtasks (TaskStars) with explicit control and data dependencies (TaskStarLines). The TaskConstellation continuously evolves as results stream in from distributed devices, enabling asynchronous execution, adaptive recovery, and dynamic optimization. A Constellation Orchestrator} executes tasks safely and asynchronously while applying dynamic DAG updates, and the Agent Interaction Protocol (AIP) provides persistent, low-latency channels for reliable task dispatch and result streaming. These designs dissolve the traditional boundaries between devices and platforms, allowing agents to collaborate seamlessly and amplify their collective intelligence. We evaluate UFO$^3$ on NebulaBench, a benchmark of 55 cross-device tasks across 5 machines and 10 categories. UFO$^3$ achieves 83.3% subtask completion, 70.9% task success, exposes parallelism with an average width of 1.72, and reduces end-to-end latency by 31% relative to a sequential baseline. Fault-injection experiments demonstrate graceful degradation and recovery under transient and permanent agent failures. These results show that UFO$^3$ achieves accurate, efficient, and resilient task orchestration across heterogeneous devices, uniting isolated agents into a coherent, adaptive computing fabric that extends across the landscape of ubiquitous computing.

1 Introduction

UFO3 addresses the limits of single-device agents with a cross-device orchestration system that decomposes requests into evolving task graphs and coordinates heterogeneous agents. Its NebulaBench evaluation reports task completion, parallelism, latency, and fault-recovery results.

1 Introduction

  • Most agent frameworks remain confined to one device or platform, limiting users’ ability to harness distributed computing resources and coordinate cross-device workflows.The motivating examples include GPU clusters, desktop applications, and mobile sensors.Source: §1 · p. 2
  • UFO3 represents each request as a TaskConstellation, a distributed DAG of executable subtasks whose edges encode data and control dependencies.The graph serves as both the logical plan and live runtime substrate.Source: §1 · pp. 2–3
  • Intermediate outputs, failures, and new observations trigger graph rewrites, while asynchronous scheduling and safe updates support adaptive execution.Rewrites can add diagnostics or fallbacks, rewire dependencies, or prune completed nodes.Source: §1 · p. 3
  • AIP supplies persistent, fault-tolerant agent communication, while templates and MCP servers support integration of new device agents.The design combines decomposition, scheduling, execution, and adaptation while maintaining safety and consistency.Source: §1 · p. 3
  • 83.3% Subtask Completion Rate and 70.9% Task Success Rate; end-to-end latency fell 31% versus a sequential baseline on NebulaBench.The benchmark covers 55 cross-device tasks across 10 categories and 5 machines.Source: §1 · p. 3

2 Background

The background describes digital agents, the limits of single-device frameworks, and cross-device intelligence as a collaborative alternative. It then identifies the coordination, parallelism, and extensibility challenges that UFO3’s orchestration components address.

2.1 Digital Agents

  • 2.1 Digital agents interpret requests and system state and act across platforms, but single-device limits, fragmented personalization, and manual coordination constrain cross-device workflows.Such workflows increasingly combine desktops, mobile devices, cloud services, and specialized hardware.Source: §2.1 · p. 4

2.2 Cross-Device Agent: A New Paradigm

  • 2.2 Cross-device intelligence coordinates heterogeneous endpoints to assign tasks to capable devices, propagate context and preferences, and automate complex workflows.The paper illustrates this with builds on laptops, tests on GPU clusters, deployments in cloud containers, and report generation on local or mobile devices.Source: §2.2 · p. 5

2.3 Design Challenges in Cross-Device Orchestration

  • 2.3 Cross-device orchestration must handle asynchronous parallelism, persistent coordination across variable networks, and extensibility across different platforms and toolchains.UFO3 combines a global ConstellationAgent, an event-driven orchestration engine, AIP, and a development interface for new device agents.Source: §2.3 · pp. 5–6

3 UFO3: Design Principles and Overview

UFO3 uses hierarchical orchestration to coordinate heterogeneous device agents. A global control plane tracks agents and capabilities, an event-driven orchestrator runs and adapts task graphs, and AIP handles cross-agent interactions.

3 UFO3: Design Principles and Overview

  • UFO3 separates global coordination from local execution in a hierarchical architecture designed for diverse operating systems and network environments.The architecture is presented as a unified, fault-tolerant execution fabric.Source: §3 · p. 6

3.1 Hierarchical Control Plane

  • The global control plane maintains a live registry of agent capabilities, system specifications, and runtime health to place tasks on suitable devices.Device clients expose local tool environments and monitoring through a common interface.Source: §3.1 · p. 7

3.2 Orchestration Flow

  • The Constellation Orchestrator runs the task DAG asynchronously; completions trigger dependent tasks, while failures prompt retries, migration, or partial rewrites.These adaptations account for device churn, network variability, and incremental task updates while preserving progress and global consistency.Source: §3.2 · p. 7

3.3 Cross-Agent Communication

  • AIP handles registration, capability synchronization, dispatch, progress reporting, and result aggregation over persistent WebSocket channels.The communication layer supports bidirectional structured events and low-latency propagation despite intermittent connectivity or asynchronous updates.Source: §3.3 · p. 7

4 Formal Constellation Model

The TaskConstellation models a distributed workflow as a dependency-aware DAG of subtasks, supporting explicit ordering and runtime adaptation. Its mutable structure allows the workflow to respond to changing inputs, results, and device failures.

4 Formal Constellation Model

  • A TaskConstellation represents a complex request as a DAG of interdependent subtasks, with runtime additions, removals, or rewiring supported as the workflow evolves.This formal model captures dependencies and execution order while supporting scheduling and recovery across heterogeneous devices.Source: §4 · p. 7, §4.4 · p. 9

4.1 TaskStar: Atomic Execution Unit

  • A TaskStar is the smallest indivisible computation scheduled on a device agent, carrying the context needed for autonomous execution.That context includes its semantic description, assigned device, execution state, and dependencies.Source: §4.1 · p. 8

4.2 TaskStarLines: Dependency Edge

  • A TaskStarLine links two TaskStars and specifies when the target task may begin, enforcing dependency conditions while preserving possible concurrency.Dependency edges maintain causal consistency and logical task ordering.Source: §4.2 · p. 8

4.3 TaskConstellation: Directed Acyclic Task Graph

  • A complete constellation is a compact workflow representation whose nodes are TaskStars and whose edges are TaskStarLines.Its DAG topology exposes parallelism and permits task or edge changes based on predecessor completion.Source: §4 · p. 7, §4.3 · p. 8
  • Figure 3’s example combines sequential and parallel dependencies across Linux, Windows, and mobile agents.Task A must finish before C; B and C precede D, and E depends on both C and D.Source: §4.3 · p. 8, Figure 3 · p. 9

4.4 Runtime Dynamism and Adaptivity

  • Unlike static DAG schedulers, UFO3 allows runtime graph edits in response to new inputs, intermediate results, or device failures, without restarting the workflow.The formalism is intended to support reasoning and orchestration in asynchronous, failure-prone environments.Source: §4.4 · p. 9

5 ConstellationAgent: The Centralized Constellation Weaver

The ConstellationAgent turns user goals into executable task constellations and revises them as distributed agents provide feedback. Its finite-state control and structured mutation interface are designed to keep orchestration adaptive and consistent.

5 ConstellationAgent: The Centralized Constellation Weaver

  • The ConstellationAgent acts as planner and replanner, synthesizing a TaskConstellation from user instructions and refining it as distributed-agent feedback arrives.The feedback-driven loop is described as maintaining global consistency and forward progress while adapting to device conditions.Source: §5 · p. 9

5.1 Responsibilities and I/O Interface

  • The control loop separates creation from editing, allowing recovery, reallocation, and opportunistic task generation as failures or goals change.The agent also maintains task-state and dependency lineage for introspection, debugging, and traceability.Source: §5 · p. 10, §5.1 · pp. 10–11
  • In creation mode, the agent uses the user goal and AgentProfile registry to build a machine-readable graph of dependent, device-assigned TaskStars.During editing, completion or failure events can prompt changes, but only non-terminal TaskStars are edited.Source: §5.1 · pp. 10–11

5.2 Finite-State Machine and Lifecycle

  • The FSM organizes agent lifecycle transitions, separating LLM reasoning from deterministic control logic to support predictable recovery, safety, and debuggability.Its states include START, CONTINUE, FINISH, and FAIL.Source: §5.2 · p. 11

5.3 Constellation MCP Server: Structured Task Management

  • The Constellation MCP Server applies idempotent task-graph mutations and returns consistent snapshots, while enforcing structural integrity such as DAG validity and single assignment.Separating semantic decisions from structured mutation is presented as supporting robustness, auditability, and extensibility.Source: §5.3 · p. 12

6 Asynchronous Dynamic Constellation Orchestrator

The Constellation Orchestrator executes and adapts a changing task DAG across heterogeneous devices while balancing asynchronous progress with safe, consistent updates. Its event-driven coordination, assignment locking, invariants, and batching support responsive execution without sacrificing correctness.

6 Asynchronous Dynamic Constellation Orchestrator

  • Five design pillars—event-driven coordination, asynchronous scheduling, safe assignment locking, consistency enforcement, and batched editing—govern orchestration over evolving task graphs.Together, they target scalability and adaptivity while preserving correctness and efficiency.Source: §6 · p. 13

6.1 Event-Driven Coordination

  • Event-driven handlers react to task and constellation events asynchronously, avoiding centralized coordination delays and providing the foundation for responsive adaptation.The orchestrator uses an internal event bus and observer pattern rather than polling or global checkpoints.Source: §6.1 · pp. 13–14

6.2 Asynchronous Scheduling

  • The asynchronous scheduler dispatches ready TaskStars concurrently and overlaps DAG edits with ongoing executions, reducing idle waiting and supporting parallel progress across devices.Each TaskStar runs in an asyncio coroutine that handles execution, result collection, and event publication.Source: §6.2 · p. 14

6.3 Safe Assignment Locking and Synchronization

  • A lock-bounded edit cycle queues incoming events, merges DAG changes with concurrent runtime updates, validates the result, and resumes scheduling only after synchronization.The lock prevents assignments based on stale DAG states; edits are atomically merged and validated before the lock is released.Source: §6.3 · pp. 14–15

6.4 Consistency and Safety Guarantees

  • Three runtime invariants constrain edits: a TaskStar has at most one active assignment, the DAG remains acyclic, and only pending tasks and dependent nodes may be modified.Running, completed, and failed nodes are immutable.Source: §6.4 · p. 15

6.5 Batched Constellation Editing

  • Batched editing aggregates events arriving during a reasoning round and applies their changes atomically, amortizing LLM invocation and synchronization overhead while preserving consistency.The edit–sync confluence lemma concerns folding runtime events with lock-bounded edits in the same window.Source: §6.5 · pp. 16–17
  • The resulting orchestrator treats execution as an open-world process: event handling supports responsiveness, asynchronous scheduling supports concurrency, and locking, batching, and DAG checks support safe adaptation.It bridges declarative intent and distributed execution across heterogeneous agents.Source: §6.5 · p. 17

7 Agent Interaction Protocol (AIP)

AIP is a persistent, event-driven communication fabric for coordinating registration, execution, and recovery across heterogeneous agents. Its layered design supports capability discovery, ordered task delivery, streamed feedback, and fault handling as workflows and agents change.

7.1 Design Overview

  • AIP provides a unified event-driven control plane connecting the ConstellationClient, device agent services, and device clients through a five-layer protocol stack.The layers combine message contracts, transport, protocol handling, resilience, and endpoint orchestration.Source: §7.1 · pp. 17–18, Figure 9 · p. 18
  • Persistent bidirectional sessions, capability discovery, reliability, deterministic command ordering, extensibility, and task continuity under transient failures define AIP’s six design goals.The protocol uses persistent WebSocket transport and five logical strata.Source: §7.1 · p. 17

7.2 Agent Registration and Profiling

  • Registration combines administrator endpoint preferences, service-advertised tools and metadata, and client telemetry into a unified, refreshed AgentProfile for capability and topology awareness.Telemetry includes OS version, hardware status, GPU utilization, and software environment; it supports adaptation to resource drift or device churn.Source: §7.2 · pp. 19–20

7.3 Task Dispatch and Result Delivery

  • Persistent sessions deliver assigned tasks with ordering guarantees, while incremental logs and evaluator outputs update the global TaskConstellation and can trigger DAG adjustments.AIP thereby serves as a feedback-driven coordination substrate linking reasoning, scheduling, and execution.Source: §7.3 · p. 20

7.4 Command Execution

  • AIP commands carry identifiers, target functions, and typed arguments; sequential execution preserves determinism, while batching reduces round-trip overhead and structured results support recovery or reassignment.Failures and timeouts are propagated through the same channel.Source: §7.4 · p. 20

7.5 Resilient Connection Protocol

  • On device-agent disconnection, AIP removes the agent from scheduling, attempts exponential-backoff reconnection, and automatically restores participation after re-registration.Tasks affected during execution are marked failed for DAG revision; if the ConstellationClient disconnects, its device server aborts associated tasks to avoid orphaned execution states.Source: §7.5 · pp. 20–21
  • AIP consolidates registration, dispatch, command execution, and resilience into an evolution-tolerant communication fabric designed to remain stable as workflows, models, and environments evolve.The paper characterizes the design as minimal and extensible.Source: §7.5 · p. 21

8 Design and Development of Device Agents

UFO3’s device-agent template separates workflow progression, execution logic, and device commands, with server–client separation supporting deployment across heterogeneous platforms. LinuxAgent and WindowsAgent illustrate single-agent CLI and multi-agent GUI instantiations of this architecture.

8.1 Architecture Overview

  • Device agents use a three-layer, state-machine-driven framework, and a server–client split separates orchestration and FSM logic from local command execution.The template is intended to let developers onboard devices by defining relevant states, strategies, and commands rather than rewriting orchestration or communication logic.Source: §8.1 · pp. 21–22, §8 · p. 21

8.2 Server-Client Architecture

  • The server manages workflow logic and AgentProfiles, while clients execute commands through local or remote MCP tools and return structured outputs over persistent AIP connections.This separation supports independent updates to server reasoning strategies and client tools, and a server can manage multiple clients.Source: §8.2 · p. 23

8.3 State: Finite-State Machine Layer

  • The FSM governs workflow progression by invoking state-specific processors and selecting transitions dynamically through LLM reasoning or rule-based responses to errors, timeouts, and external events.Separating state transitions, processors, and commands makes agent behavior easier to reason about and debug.Source: §8.3 · pp. 23–24

8.4 Strategy: Composable Execution Logic

  • Processors sequence modular strategies for context gathering, LLM interaction, action execution, and memory updates, which can be reordered, added, or replaced without changing the core state machine.The separation supports customization and makes workflows easier to test, debug, and extend.Source: §8.4 · p. 24

8.5 Command: Atomic Execution Units

  • Commands are atomic, testable tool-call units transmitted through AIP to clients, where they execute on devices and return structured results.Additional device capabilities can be integrated by registering commands at the client layer without changing server-side state or strategy definitions.Source: §8.5 · p. 25

8.6 Example Device Agents: LinuxAgent and WindowsAgent

  • LinuxAgent and WindowsAgent demonstrate the architecture in single-agent CLI and multi-agent GUI settings, respectively, with Windows coordination delegating subtasks to application agents.The Windows workflow collects screenshots and accessibility metadata; its hybrid GUI and application-API interactions balance generality and robustness.Source: §8.6 · p. 25, §8.6.2 · p. 27

8.6.1 LinuxAgent: Single-Agent CLI Execution

  • LinuxAgent is a lightweight CLI implementation whose on-demand system and environment queries avoid the overhead of polling-based or externally triggered data collection.It combines a small deterministic state set with modular strategies and commands for traceable task execution.Source: §8.6.1 · pp. 25–26

8.6.2 WindowsAgent: Multi-Agent Coordination on GUI Systems

  • WindowsAgent extends the shared design to multi-application GUI work: a HostAgent assigns subtasks to AppAgents and regains control after each agent finishes or fails.The host can retry, re-plan, or advance to another subtask; AppAgents can combine GUI actions with application-specific APIs.Source: §8.6.2 · pp. 26–27

9 Implementation and Engineering

UFO3 integrates asynchronous orchestration, cross-device agents, and communication infrastructure with tools for interactive monitoring, extension, model configuration, and debugging.

9 Implementation and Engineering

  • The implementation combines a centralized ConstellationAgent, asynchronous orchestrator, AIP, and Linux, Windows, and Android agents, with asyncio supporting nonblocking registration and execution.Source: §9 · p. 28

9.1 Interactive UFO3 WebUI

  • The WebUI combines natural-language chat, live TaskConstellation DAG and status views, device-agent management, and streamed execution events for monitoring and intervention.Source: §9.1 · pp. 28–29

9.2 Plugin and Extension Framework

  • Configurable MCP servers let developers add agent capabilities through lightweight interfaces without changing orchestration or protocol logic.Source: §9.2 · p. 29

9.3 Prompt and Model Integration

  • Hierarchical prompt configuration combines core templates with few-shot exemplars, while a unified API supports GPT-based, Claude-based, and local open-weight models.Source: §9.3 · p. 29

9.4 Automated Task Logging.

  • Markdown task logs record agent actions, reasoning, outputs, TaskConstellation changes, and execution timelines; Figure 18 shows an example log.Source: §9.4 · pp. 29–30, Figure 18 · p. 29

10 Experimental Evaluation

The experimental evaluation uses an internal multidimensional study to examine UFO3’s cross-device, cross-platform orchestration in heterogeneous settings, including reliability, adaptation, parallelism, latency, and fault tolerance. It also describes scalable execution and three workflows illustrating parallelism, spreadsheet integration, and resource-aware orchestration.

10.1 Experiment Setup

  • Five physical machines run UFO3 with AIP over simulated local links of 1–10 ms and a 50–100 ms wide-area link to the GPU node.The setup combines Ubuntu workstations, an Ubuntu GPU node, and a dedicated management node for discovery, scheduling, and monitoring.Source: §10.1 · p. 30

10.2 NebulaBench: A Crossed-Device Evaluation Benchmark

  • NebulaBench contains 55 representative multi-agent tasks across ten categories, proposed by five volunteers with Linux and Windows experience.Tasks span Easy, Medium, and Hard difficulty and include infeasible negative cases, which are expected to be safely rejected without agent actions.Source: §10.2 · p. 31

10.3 Metrics and Methodology

  • Evaluation measures task and subtask success, DAG edits, parallelism, latency, and recovery under three controlled agent-failure modes.Negative cases count as successful when the agent correctly reports the intended failure; parallelism is characterized using maximum width, critical path, total workload, and their ratio.Source: §10.3 · pp. 32–33

10.4 RQ1: Task Completion Analysis

  • 83.3% SCR and 70.9% TSR overall; TSR is 72.2% for easy, 73.7% for medium, and 66.7% for hard tasks.SCR generally exceeds TSR because a failure in one dependent subtask can fail the whole request. Figure 20 summarizes success rates by difficulty and category.Source: §10.4 · pp. 33–34, Figure 20 · p. 33
  • Data and Proc subtasks reach 100% and 96% SCR, while Browsing and Negative scenarios reach 64.2% and 66.7%.Failures involve text-only AIP file transfers, missing-precondition handling, and Windows GUI variability; the generated TaskConstellations are nevertheless largely correct.Source: §10.4 · p. 34

10.5 RQ2: Orchestration and Adaptation

  • 1.09 modifications per edit and 5.91 per request reflect active runtime DAG refinement, chiefly by enriching downstream tasks with earlier results.Task and dependency additions or removals remain minimal, indicating stable initial DAGs; harder tasks receive slightly more edits.Source: §10.5 · pp. 34–35, Table 3 · p. 34

10.6 RQ3: Parallelism and Execution Efficiency

  • 1.72 average parallelism ratio and up to 3.5 concurrent subtasks show UFO3 schedules independent work across devices.Maximum parallel width stays around three tasks as difficulty rises; critical-path length grows from 144s to 232s while total execution time grows from 315s to 340s.Source: §10.6 · pp. 35–36, Table 4 · p. 35

10.7 RQ4: Latency and Scalability

  • 243.7 seconds average end-to-end latency is 31% below the 352.5-second combined orchestration-and-execution time of a sequential workflow.TaskConstellation creation takes 16–20 seconds, editing takes 8–12 seconds, and task completion averages about 48 seconds; overlapping orchestration and execution hides reasoning latency.Source: §10.7 · p. 36, Figure 22 · p. 36
  • UFO3 overlaps task execution with reasoning and orchestration, scales to complex multi-host tasks, and dynamically edits TaskConstellations with minimal overhead.The evaluation describes the system as performant and scalable for heterogeneous distributed workloads.Source: §10.7 · p. 36, Scenario 1 · p. 37

10.8 RQ5: Robustness and Fault Handling

  • Across three failure scenarios, UFO3 retries transient failures, preserves useful progress under partial failures, and terminates transparently when recovery is infeasible.Transient disconnection is recovered through a replacement task without human intervention; persistent partial failure allows remaining subtasks to finish with failure traces, while total Linux-agent unavailability results in honest termination rather than speculative output.Source: §10.8 · p. 38

10.9.1 Case 1: Collecting Logs and Writing Reports

  • For log reporting, UFO3 runs retrieval across three Linux agents in parallel, then aggregates results and completes Excel entry and email dispatch on Windows.The case illustrates asynchronous collection and centralized fusion to reduce manual effort and turnaround time while maintaining cross-device consistency.Source: §10.9.1 · p. 39

10.9.2 Case 2: Task Allocation and Result Integration via Excel

  • For spreadsheet-listed tasks, UFO3 dispatches work to Linux hosts concurrently and preserves task-to-cell correspondence when writing synthesized summaries back to Excel.The ConstellationAgent aggregates remote outputs and writes concise summaries into the appropriate cells without human supervision.Source: §10.9.2 · p. 39

10.9.3 Case 3: Resource-Aware Distributed Computation

  • For resource-aware computation, UFO3 inspects four Linux hosts in parallel, assigns workloads according to hardware and current load, and reports the assignments on Windows.This workflow combines real-time environment sensing, distributed execution, and autonomous reporting, illustrating orchestration beyond predefined templates.Source: §10.9.3 · p. 40

11 Discussion

UFO3’s protocol-based architecture is designed to accommodate diverse agents and platforms. The discussion also identifies limits from unreliable device agents and text-only communication, and proposes shared memory as a path toward richer cross-device workflows.

11.1 Scalability and Ecosystem Growth

  • AIP-compatible agents can join without changes to the core system, supporting a broader ecosystem across platforms and agent implementations.Source: §11.1 · p. 42

11.2 Limitations of Device-Centric Execution

  • Overall capability remains constrained by individual device agents: incomplete execution or incorrect reporting can cascade into global task failure.Future work includes capability validation, task-level sandboxing, and adaptive reallocation for unreliable nodes.Source: §11.2 · p. 42

11.3 Toward Shared Cross-Device Memory

  • Text-only communication is insufficient for data-rich workflows; planned shared agent memory would support storing and retrieving intermediate results across devices.The discussion says this could simplify file sharing and enable richer collaboration.Source: §11.3 · p. 42

12 Related Work

Related work traces progress in device agents and multi-agent orchestration, while emphasizing that most device agents remain isolated. UFO3 targets cross-device coordination across heterogeneous platforms.

12.1 Digital Device Agents

  • Early GUI agents such as SeeAct Zheng et al. (2024), Mobile-Agent Wang et al. (2024a), and UFO Zhang et al. (2025b) enabled human-like interactions across platforms.Later work is described as pursuing system-level integration and model-level adaptation.Source: §12.1 · p. 42
  • UFO3 addresses the isolation of existing device agents with cross-device orchestration, shared state, and coordination through AIP.The related-work discussion positions this as a way to unite agents across devices.Source: §12.1 · p. 43

12.2 Multi-Agent Orchestration

  • Multi-agent orchestration research identifies role assignment, communication, collaboration, and context sharing as central design challenges.The section also reviews the Internet of Agents and Federation of Agents as approaches to flexible and capability-driven coordination.Source: §12.2 · p. 43
  • UFO3 extends orchestration across desktops, browsers, and operating systems, using AIP for low-latency communication and shared context.The design also supports composable agent teams.Source: §12.2 · p. 43

13 Conclusion

UFO3 combines a mutable task constellation, asynchronous orchestration, and AIP communication to coordinate agents across heterogeneous devices. The formal model states safety, liveness, and confluence properties under specified conditions.

13 Conclusion

  • UFO3 integrates planning and execution in a mutable TaskConstellation, with asynchronous scheduling, safe batched updates, and persistent communication across devices.A layered device-agent template backed by MCP servers lets endpoints join without control-plane changes.Source: §13 · p. 43

A Formal Guarantees and Model

  • The orchestrator model represents the constellation DAG, task states, device assignments, edit lock, pending events, and available devices.A task is ready when it is pending and all predecessor tasks are completed.Source: A Formal Guarantees and Model · p. 48
  • Committed edits preserve single assignment, DAG acyclicity, and edit locality through an atomic edit–validate–synchronize–publish cycle.The model restricts edits to pending tasks and their dependent nodes.Source: A Formal Guarantees and Model · p. 48
  • The edit phase terminates and releases its lock; perpetually ready tasks are eventually dispatched under weak fairness of event delivery and device availability.The termination argument uses a variant that decreases with each synchronization or completion event.Source: A Formal Guarantees and Model · p. 48
  • Constellation edits and event synchronization commute within a lock interval when edits preserve edit locality and acyclicity.The resulting observable post-state is independent of their ordering.Source: A Formal Guarantees and Model · p. 48

A.1 TLA+ Specification

  • The TLA+ specification matches the model, but its small-instance checking stubs acyclicity and edit/synchronization operations and bounds the event queue.The stated safety checks still exercise I1 and I2 under this configuration.Source: §A.1 · pp. 48, 50

A.2 Model-Checking Configuration and Results

The appendix reports model-checking results for a bounded orchestrator configuration and describes the typed message primitives underpinning AIP.

A.2 Model-Checking Configuration and Results

  • The model-checking setup uses a bounded event window; larger instances or unbounded event ingress grow the state space quickly.The configuration also fixes the device set and bounds the event queue.Source: §A.2 · p. 51
  • All checked invariants held and TLC reported no deadlocks after exploring 93,633 generated states and 7,168 distinct states.The exploration reached a graph search depth of 8.Source: §A.2 · p. 51

B AIP Message Schema Reference

  • AIP message primitives cover registration, device information, heartbeats, tasks, commands, command results, and errors.The taxonomy identifies message direction and whether duplicate delivery is idempotent; COMMAND must not be replayed without coordination.Source: Table 5 · p. 52, B AIP Message Schema Reference · p. 52
  • The message types map to profile and resilience, execution-control, and recovery functions in AIP’s layered design.The discussion links these functions to freshness and liveness, deterministic execution, and extensibility and robustness.Source: B AIP Message Schema Reference · p. 52

C Details of NebulaBench

The NebulaBench appendix lists task queries with metadata and UFO3 execution outcomes, supporting examination of benchmark composition and individual-query performance.

C Details of NebulaBench

  • Table 6 lists NebulaBench queries with functional category, difficulty, devices involved, and UFO3 execution outcomes.The appendix presents the listing as a resource for examining task distribution, per-query performance, and reproducibility.Source: C Details of NebulaBench · p. 52, Table 6 · p. 52
  • Log and system tasks include collecting server warnings, searching authentication logs, rotating logs, scanning for OOM events, and comparing Windows and Linux logs.Other listed tasks count systemd service starts and stops and report CPU models.Source: C Details of NebulaBench · pp. 52–53
  • Process and DevOps queries cover service control, concurrent jobs, scheduled tasks, container checks, repository builds, and cross-host deployment.Some tasks require reporting results through Windows applications.Source: C Details of NebulaBench · pp. 53–54
  • Browsing and orchestration tasks combine web searches or host checks with cross-machine actions and reports, including software installation, security patching, and scheduled-work summaries.The listed queries also include comparing CPU benchmarks with recommended optimizations.Source: C Details of NebulaBench · p. 55
  • GPU tasks include smoke testing, merging distributed logs for training, and assigning workloads across hosts; negative queries include unsupported requests and deployment conditions.The listed negative tasks include starting UFO3 services on Linux and deploying a service on a machine specified to have 2TB memory.Source: C Details of NebulaBench · p. 56
Loading 2511.11332v2…