Introduction

Large language models (LLMs) have enabled multi-agent systems (MAS) where multiple agents discuss, critique, and coordinate to solve complex tasks. However, most LLM-based MAS either adopt fully connected graphs, simple sparse rings, or ad-hoc dynamic selection with little structural guidance. This work revisits classic theory on small-world networks and asks: what changes if we treat SW connectivity as a design prior for MAS?

Theory and Application

Small-world networks are structures that combine local clustering with long-range integration. In this work, we explore how this concept can be used to improve multi-agent systems.

We develop a debate multi-agent system (MAD) testbed to evaluate the impact of small-world networks on accuracy and token cost. Results show that small-world networks improve consensus trajectory stability without compromising accuracy.

Scalability and Adaptability

To scale multi-agent systems, we developed an uncertainty-guided rewiring scheme. This protocol uses LLM-oriented uncertainty signals to add long-range shortcuts between epistemically divergent agents.

Results show that this protocol can create controllable small-world structures that adapt to task difficulty and agent heterogeneity.