Linear Scalability in Multi-Agent Coordination

46 concepts41 papers1 proposal

In traditional centralized planning, adding a single agent to a system doesn't just add a bit of work—it often multiplies the complexity. This "curse of dimensionality" occurs because the joint state and action spaces grow exponentially with the number of participants. To coordinate a million agents, researchers have shifted away from global optimization toward decentralized architectures where computational costs scale linearly, or even remain constant, per agent.

The Locality Principle

The most effective way to achieve linear scalability is to ensure that an agent’s decision-making process is independent of the total population size. By restricting an agent's focus to a local sensing horizon or a neighborhood of immediate collaborators, the computational burden per individual plateaus rather than climbs.

Zhou et al. demonstrate this in the EGO-Swarm system, where quadrotors navigate cluttered environments by planning only within a local window. Because agents ignore distant obstacles and peers, the swarm can expand indefinitely without increasing the processing requirements of any single drone. Similarly, Andreychuk shows that a decentralized pathfinding solver using local observation windows can coordinate up to one million agents in real-time, maintaining constant inference time regardless of the total swarm density.

This locality applies to communication as well. Itoh et al. argue that managing information locally allows multi-vehicle systems to maintain constant complexity. When agents only exchange data with nearby neighbors, the communication overhead for the entire system scales linearly ($O(N)$) rather than quadratically ($O(N^2)$). As Davison et al. observe in their work on distributed localization, the overhead is determined by the density of local interactions, not the total number of agents in the network.

Task and Spatial Decomposition

Beyond spatial locality, scalability is achieved by breaking complex global goals into independent sub-problems. This process, known as factoring, allows a system to solve many small problems in parallel rather than one massive problem in sequence.

  • Factored Planning: Douglas Aberdeen introduced the FPG-Planner, which assigns independent agents to specific tasks. This shift ensures the system scales linearly with the number of tasks, avoiding the exponential explosion of the state space.
  • Hierarchical Structures: Ma et al. propose a "feudal" reinforcement learning structure for traffic control. By dividing a city into regions managed by "manager" agents who oversee "worker" agents, the system can scale to larger networks simply by adding new regions, preventing any single agent from becoming a bottleneck.
  • Specification Partitioning: For complex missions, Leahy et al. use SMT solvers to decompose global temporal logic specifications into independent sub-tasks for heterogeneous teams, enabling parallelized planning that is computationally feasible for large populations.

Factorization and Permutation Invariance

Modern machine learning approaches achieve scalability by ensuring that the underlying models are "size-agnostic." If a policy is trained to interact with three neighbors, it should theoretically work just as well in a crowd of thousands if the interaction logic is properly factorized.

Khan et al. leverage Graph Neural Networks (GNNs) to exploit permutation invariance. Because GNNs process local neighborhood information using the same weights regardless of the graph's total size, policies trained on small groups can be transferred "zero-shot" to massive swarms.

In the realm of generative models, Li et al. introduced Diffusion Factorization (DoF). By applying the Individual-Global-identically-Distributed (IGD) principle, the authors decouple a centralized team diffusion model into individual agent components. This reduces the input complexity for each agent from a linear function of the team size to a constant factor, allowing generative coordination to scale to large teams without the typical computational penalties.

Robustness through Decentralization

Linear scaling does more than just save time; it enhances system resilience. In centralized systems, the central planner is a single point of failure. In decentralized systems, agents can "self-heal." Park et al. show that by decoupling sensor models and using decentralized control laws, mobile sensor networks can maintain accurate environmental mapping even as individual robots fail. Because the computational and logic structures are distributed, the loss of an agent does not collapse the coordination framework, but merely reduces the local density of the network.

Key Foundational Work

Development of Multi-Vehicles Navigation System based on Local Information Management (1st Report) (2003) — contributed 1 concept elements to this direction.
Policy-Gradient Methods for Planning (2005) — contributed 1 concept elements to this direction.
Decentralized Multiple Target Tracking Using Netted Collaborative Autonomous Trackers (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_scalability_in_multi_agent_system_aad7f745,
  title = {linear scalability in multi-agent systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-scalability-in-multi-agent-systems/rdr_aad7f745ba4b49faa767816f8aef86b7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_scalability_in_multi_agent_system_aad7f745_v1,
  title = {linear scalability in multi-agent systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-scalability-in-multi-agent-systems/rdr_aad7f745ba4b49faa767816f8aef86b7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake