PaperlayerView exact revision on arXiv

Source-linked AI summary

PANDA: A Decentralized Architecture with Flexible Orchestration for Scalable, Fault-Tolerant Multi-Agent Systems

Matthew D. Laws, Cristina Nita-Rotaru

arXiv:2609.38482v1cs.MAcs.AI

TL;DR

Existing LLM-based multi-agent systems have difficulty supporting multi-step tasks at scale while meeting needs for fault tolerance, flexible orchestration, and governance. PANDA is a decentralized architecture that forms specialized teams, supports multiple orchestration patterns, replans around failures, and governs interactions through trust relationships. On HotPotQA, it reports up to 8× faster task solving with comparable accuracy and 100% task completion under faults where existing systems fail.

  • Problem

    LLM-based MAS need to coordinate specialized agents across multi-step tasks, but existing architectures struggle to scale while supporting concurrent work, fault tolerance, flexible orchestration, and governance.

    Source: §1 · p. 1

  • Method

    PANDA uses a decentralized collective to discover agent capabilities and form specialized teams, supporting multiple planning patterns, dynamic failure recovery, and web-of-trust governance.

    Source: §1 · p. 2

  • Results

    PANDA solves HotPotQA tasks up to 8× faster than baselines with comparable accuracy and sustains 100% task completion under faults where existing systems fail.

    Source: §1 · p. 2, §3.2 · p. 8

  • Takeaways & Limitations

    PANDA demonstrates a decentralized architecture that combines scalability, recovery from failures, diverse orchestration patterns, and governance across administrative domains.

    Source: §4 · p. 10

Abstract

from arXiv · show

Existing architectures for LLM-based multi-agent systems (MAS) cannot reliably and efficiently solve multi-step tasks at scale: they struggle to support large numbers of agents and concurrent tasks, tolerate failures, govern agent interactions, and accommodate the diverse planning and execution patterns different tasks require. We present PANDA, a decentralized architecture that connects a large collective of heterogeneous, independently administered agents, letting them discover each other's capabilities and self-organize into small specialized teams per task. PANDA scales by decoupling collective communication from team communication, allowing agents to participate in multiple teams simultaneously, load-balancing tasks across the collective, and scheduling concurrent work within each agent. PANDA further separates the underlying architecture from the orchestration strategy, supporting three planning and execution patterns (star, chain, and mesh) that can be selected according to the structure and requirements of each task. PANDA detects infrastructure and orchestration failures and recovers affected tasks by dynamically replanning around failed components. Finally, to provide governance without a centralized service that would limit scalability, PANDA uses a web-of-trust model to constrain agent interactions to established trust relationships. We evaluate PANDA on the HotPotQA benchmark, demonstrating that it scales to thousands of agents, assembles teams in milliseconds, matches state-of-the-art accuracy at up to 8x the efficiency, and sustains 100% task completion under faults where existing systems fail.

1 INTRODUCTION

LLM-based MAS must coordinate specialized agents across multi-step tasks while scaling to large, dynamic collectives, tolerating failures, supporting different orchestration patterns, and governing trust. PANDA addresses these needs through decentralized team formation and communication, flexible orchestration, failure recovery, and web-of-trust governance.

Motivation

  • Large, dynamic MAS must support scalability, fault tolerance, flexible orchestration, and governance as agents collaborate concurrently across tasks.Scalability includes controlling communication and token costs while maintaining task utility; governance constrains interactions to trusted agents.Source: §1 · p. 1

Limitations of previous work

  • Centralized registries, orchestration, and governance can bottleneck growth, while discovery and coordination add latency and token costs and failures raise recovery overhead.Prior systems also have limited orchestration flexibility and lack comprehensive recovery from infrastructure and orchestration failures.Source: §1 · pp. 1–2
  • Prior architectures have limited scalability: centralized planning concentrates coordination, while decentralized discovery and agent selection can be costly at large scale.Some decentralized systems require initial knowledge of all agents; other systems retain centralized communications hubs.Source: §1 · p. 2

Our contribution

  • PANDA connects independently administered agents that discover capabilities and form specialized teams, decouples collective from team communication, and supports star, chain, and mesh patterns.It dynamically replans around infrastructure and orchestration failures and uses web-of-trust governance to constrain interactions to established trust relationships.Source: §1 · p. 2

Results

  • PANDA reports solving HotPotQA tasks up to 8× faster than baselines with comparable accuracy, while sustaining 100% task completion under faults where existing systems fail.It assembles teams in milliseconds at constant per-assembly cost even at 106 agents, and maintains >99% trust precision under churn.Source: §1 · p. 2

Architecture

  • PANDA’s agent design separates team messaging from system-wide communication and combines an agent registry, team manager, failure detector, and backend wrapper.The team manager handles topology-specific planning and execution as well as replanning after failures.Source: Figure 1 · p. 3

2 PANDA ARCHITECTURE

PANDA is a peer-to-peer architecture for heterogeneous agents to discover capabilities, form teams, and coordinate on tasks. Its design combines scalable communication and scheduling, locally configurable trust, multiple orchestration patterns, and recovery from infrastructure and orchestration failures.

2.1 DESIGN GOALS AND OVERVIEW

  • PANDA uses a peer-to-peer architecture to let independently created agents discover one another, establish teams, and coordinate without a central point of failure.Agents can belong to multiple teams working on separate tasks concurrently.Source: §2.1 · pp. 3–4

2.2 SCALABILITY

  • PANDA separates scalable collective communication from reliable team communication, while local scheduling and load balancing support concurrent work and distribute team assignments.Agents enqueue subtasks until available; during team assembly, the least-loaded agents among the polled candidates join the team.Source: §2.2 · p. 4

2.3 WEB-OF-TRUST GOVERNANCE

  • PANDA’s web-of-trust governance uses certificates and depth-bounded trust paths, with each agent choosing its anchor mode and depth locally.Agents may be certified by existing members, and certificates are gossiped with capability announcements.Source: §2.3 · p. 5

2.4 FLEXIBLE ORCHESTRATION

  • Team assembly selects agents for required capabilities from local registries and creates an overlay network for the team’s communication pattern.The required capabilities may be supplied by the user or identified dynamically by the entrypoint.Source: §2.4 · p. 5
  • PANDA supports star, chain, and mesh planning and execution, separating communication topology from orchestration logic.Star uses an orchestrator to plan and dispatch subtasks; chain passes a linear plan between agents; mesh collaborators reach a plan through propose–rank–revise.Source: §2.1 · p. 4, §2.4 · p. 5, Figure 2 · p. 6

2.5 FAULT TOLERANT ORCHESTRATION

  • PANDA combines backup-agent provisioning and redundant execution with failure detection, agent swapping, and replanning to recover tasks.DAG-structured subtasks let the system replace the agent assigned to a failed vertex rather than restart the whole task; orchestration-specific recovery varies across star, chain, and mesh.Source: §2.5 · pp. 5–6

3 EXPERIMENTS

The experiments evaluate PANDA’s scalability, fault resilience, and decentralized governance on HotPotQA, comparing it with three baseline systems. Across these evaluations, PANDA assembles teams quickly, improves runtime while maintaining comparable accuracy, and sustains task completion under faults.

3.1 PANDA SCALABILITY

  • After sufficient capability redundancy is reached, team assembly time is constant with collective size and remains on the order of milliseconds.The load balancer probes a capped candidate set regardless of collective size; assembly time still scales with team size, and network overhead depends on the maximum RTT to probed candidates.Source: §3.1 · pp. 7–8, Figure 3 · p. 7
  • PANDA-MESH essentially matches IoA in EM and F1 with a 3-4× faster runtime, while PANDA-STAR and PANDA-CHAIN are roughly 2× faster than Magentic-One and AgentNet.PANDA-STAR and PANDA-CHAIN improve EM and F1 over Magentic-One and are comparable with AgentNet; IoA records higher accuracy than those two PANDA topologies but incurs 5-8× runtime.Source: §3.1 · p. 8, Table 2 · p. 8

3.2 TASK COMPLETION WITH FAILURES

  • Under agent crashes, none of the baselines complete any task, while all three PANDA topologies sustain high accuracy and reasonable per-task runtimes.Each task had at least one agent crash; the experiment used a per-step crash probability of p = 0.5 with a backstop guaranteeing a crash.Source: §3.2 · p. 8, Table 3 · p. 8
  • Under orchestration faults, PANDA outperforms the baselines across all metrics, using its swap protocol to replace a faulty agent with a healthy one.The experiment began with one agent returning an unrelated search result; complete knowledge improved EM and F1 for Magentic-One and IoA, but increased the probability of incorrect answers for AgentNet.Source: §3.2 · pp. 8–9, Table 4 · p. 9

3.3 PANDA GOVERNANCE

  • Under the genesis anchor, trusted recall reaches nearly 70% at depth n = 3, and trusted set size remains stable under churn.Across the evaluated configurations, trusted precision exceeds 99%; self anchoring is weaker at lower depths but recovers nearly 100 trusted agents at n = 3.Source: §3.3 · p. 9, Figure 4 · p. 9

4 CONCLUSION

PANDA addresses scalability, fault tolerance, flexible orchestration, and decentralized governance in large-scale LLM-based multi-agent systems. Its evaluation reports scaling while maintaining task utility, recovering from failures, and supporting diverse orchestration patterns.

4 CONCLUSION

  • PANDA addresses four requirements that existing architectures satisfy only partially or not at all: scalability, fault tolerance, flexible orchestration, and decentralized governance.The conclusion frames these as the architecture’s central goals.Source: §4 · p. 10
  • PANDA distributes agents and tasks across the infrastructure and preserves task execution despite orchestration and infrastructure failures.Source: §4 · p. 10
  • Its web-of-trust governance lets agents from different administrative domains establish trust without a single central authority.Source: §4 · p. 10
  • The evaluation reports that PANDA scales efficiently while maintaining task utility, recovering from failures, and supporting diverse orchestration patterns.Source: §4 · p. 10

A TEAM ASSEMBLY AND REPAIR

Team formation and maintenance are fundamental components of PANDA. This appendix formalizes initial team assembly and team repair through the swap protocol.

A TEAM ASSEMBLY AND REPAIR

A.1 ASSEMBLY PROTOCOL

The assembly protocol matches required capabilities to trusted agents, balancing distinct capability pools against minimizing the number of recruited agents. It assembles teams locally when possible and otherwise requests agents for unmatched capabilities.

A.1 ASSEMBLY PROTOCOL

  • Each capability is matched to the requested number of trusted agents, and every assigned agent must satisfy that capability’s matching test.The matching primitive may use direct string comparison or thresholded semantic scoring.Source: §A.1 · p. 13
  • Dedicated matching gives each capability a distinct agent pool, while consolidated matching minimizes the total number of distinct agents recruited.Source: §A.1 · p. 13
  • Because minimal consolidated matching is an instance of NP-hard set cover, PANDA uses an approximate greedy solution.Source: §A.1 · p. 13
  • The entrypoint assembles a valid team from its local registry when possible, otherwise broadcasting a request for agents able to cover unmatched capabilities.Source: §A.1 · p. 13

A.2 SWAP PROTOCOL

The swap protocol handles a failed team member by reassigning that agent’s unfinished work when another assigned agent can cover the capability, or finding a replacement when none remain.

A.2 SWAP PROTOCOL

  • When another agent remains assigned to the failed agent’s capability, unfinished subtasks are reassigned to that agent and the failed agent is evicted.Source: §A.2 · p. 13
  • If no assigned agent remains for a capability, the fault detector searches its registry for a replacement and otherwise broadcasts a request.Source: §A.2 · p. 13

B FAULT-TOLERANT ORCHESTRATION DETAILS

PANDA’s fault-tolerant orchestration supports three execution topologies and represents tasks as capability-assigned subtasks in a dependency graph. Redundancy and agent replacement provide recovery options when agents fail.

B.1 PROBLEM FORMULATION

  • Each topology uses a structured plan that decomposes a task into a graph of capability-specific subtasks, enabling step-based recovery.The task is given with required capabilities, a redundancy mapping, a team, and assignments of capable-agent pools to capabilities.Source: B FAULT-TOLERANT ORCHESTRATION DETAILS · p. 13, §B.1 · pp. 13–14
  • A task plan is a DAG whose vertices are subtasks and whose edges encode dependencies; each subtask is assigned a required capability and capable agent.Source: §B.1 · p. 14
  • When an agent fails, PANDA replaces it with another agent capable of the same capability; redundancy can make a replacement immediately available.Without redundancy, the swap protocol searches for and dynamically adds a replacement.Source: §B.1 · p. 14

B.2 STAR TOPOLOGY

PANDA instantiates star, chain, and mesh orchestration with topology-specific planning, execution, and recovery. It also specifies core protocols in TLA+ and verifies safety and liveness properties under stated assumptions.

B.2 STAR TOPOLOGY

  • In the star topology, a central orchestrator executes dependency-free subtasks in parallel, dispatches newly enabled work, and can revise plans while preserving completed subtasks.It tracks plan, completed work, outputs, and in-flight subtasks; in-flight work no longer needed after replanning is canceled.Source: §B.2 · p. 14
  • Star recovery swaps failed workers and reissues their active subtasks; checkpointed orchestrator state lets a replacement resume without discarding completed work.Redundant execution accepts the first response and can tolerate up to n −1 failures without swap recovery, at additional computation cost.Source: §B.2 · pp. 14–15

B.3 CHAIN TOPOLOGY

  • The chain topology plans sequentially and forwards each subtask downstream; agents can replan the remaining sequence, with the number of replans capped to ensure termination.Source: §B.3 · p. 15
  • For chain recovery, predecessors retain handoff state until a downstream DONE acknowledgment, allowing local reissue after failure; generation numbers suppress stale duplicate chains.Redundant execution can tolerate up to n −1 failures without invoking swap.Source: §B.3 · p. 15

B.4 MESH TOPOLOGY

  • Mesh collaborators covering all required capabilities propose DAG plans, rank them by ranked-choice voting, and iterate proposal revisions until consensus.Planning is restricted to the capability-covering subset to keep the process efficient.Source: §B.4 · p. 16
  • Mesh execution broadcasts the plan and outputs, starts dependency-ready subtasks, and uses multi-agent debate when multiple agents share a capability; a supermajority can trigger replanning.Source: §B.4 · p. 16
  • Mesh recovery swaps failed nonredundant agents, while redundant pools can continue debate after a member fails; redundant first-response execution trades debate’s accuracy gains for lower latency.Source: §B.4 · p. 16

C FORMAL VERIFICATION

  • TLA+ modeling and TLC verification establish capability assignment and valid team membership as safety properties, and task completion or failure as liveness under standard fairness assumptions.Load-aware candidate selection is abstracted as nondeterministic choice, so safety holds under any selection policy.Source: C FORMAL VERIFICATION · p. 16

D ADDITIONAL GOVERNANCE EXPERIMENTS

The additional governance experiments examine how certification requirements affect trust propagation in a collective subject to churn. They measure trusted recall across anchoring policies and depths.

D ADDITIONAL GOVERNANCE EXPERIMENTS

D.1 VARYING THE NUMBER OF CERTIFIERS

With 1,000 agents, the experiments vary the number of certificates required to join and assess trusted recall under different anchors and depths. Genesis anchoring retains broad coverage at t = 1, while trust recall improves at t = 3 and remains stable under churn.

D.1 VARYING THE NUMBER OF CERTIFIERS

  • Across both t = 1 and t = 3 configurations, trusted-set size remains stable under churn; the authors suggest t = 2 as a reasonable default.The authors note that the Debian developers group also uses t = 2.Source: §D.1 · p. 17
  • At t = 1, genesis anchoring yields nearly 100 trusted peers per agent even at depth n = 3, while self anchoring reaches near-perfect recall at n = ∞ because the trust graph is connected.The reduced certification requirement produces a less connected graph, and fewer connections reduce the trusted set overall.Source: Figure 5 · p. 17, §D.1 · p. 17
  • At t = 3, trusted recall improves relative to t = 2, with a smaller gain than the increase from t = 1 to t = 2.Source: Figure 6 · p. 17, §D.1 · p. 17

D.2 LARGER COLLECTIVES

In a 2,000-agent collective, trusted sets grow in absolute number but sublinearly with collective size. PANDA brings together decentralized discovery, orchestration, recovery, and trust governance in one architecture.

D.2 LARGER COLLECTIVES

  • Trusted agents increase in number at 2,000 agents, but the slight recall drop indicates trusted-set size grows sublinearly with collective size.The experiment uses t = 2; shaded regions show the IQR of trusted recall across agents.Source: §D.2 · pp. 17–18, Figure 7 · p. 18

E RELATED WORK

  • PANDA combines collective discovery and coordination with collective-based fault tolerance, unlike systems focused on discovery, routing, or a particular coordination mechanism.Source: E RELATED WORK · p. 18
  • PANDA separates its execution substrate from orchestration strategy, supporting star, chain, and mesh topologies; adaptive topology-selection methods could be integrated.Source: E RELATED WORK · p. 18
  • PANDA adds infrastructure-failure handling and workflow recovery to reliability work focused on faulty outputs, coordination errors, faulty agents, or DAG execution.Source: E RELATED WORK · p. 18
  • PANDA extends decentralized trust ideas, including SDSI’s certificate-based authorization and PGP’s web-of-trust, to LLM-based multi-agent systems.It integrates decentralized trust into its collective rather than relying on centralized governance services or commonly trusted credential issuers.Source: E RELATED WORK · pp. 18–19

Related papers

Loading 2609.38482v1…