Multi-Agent Consensus

The shift from monolithic LLMs to distributed multi-agent architectures demands new frameworks for verifying and securing autonomous coordination. Unlike traditional multi-agent systems focused on cooperative state alignment, modern LLM patterns: multi-agent debate, constitutional oversight, helper-critic loops-rely on adversarial critique for error correction and reasoning refinement. Since LLMs are dynamical systems whose latent states are imperfectly observable from verbalized outputs, securing these networks requires understanding both macroscopic topology and microscopic agent observability. This paper establishes a rigorous graph-theoretic framework for analyzing consensus in signed, directed interaction networks, bridging graph theory and LLM reasoning by formally mapping Transformer cross-entropy log-odds to the signed Laplacian. We characterize agreement stability through structural balance theory, showing how unbalanced critique cycles produce logical frustration and persistent reasoning oscillations, and prove that unobservable latent states from hidden system prompts act as topological Trojan horses that destabilize cooperative consensus. To resolve unobservable deadlocks, we restrict interaction topologies to chordal graphs and apply matrix decomposition with Gram-Schmidt orthogonalization, proving that rank-one spectral edge perturbations deterministically break expertise symmetry by shifting eigenvalues into the stable left-half plane. Core contributions include consensus theorems, polynomial-time Perfect Elimination Ordering verification algorithms, and large-scale empirical validation on clustered ensembles of LLaMA-3, Mistral, and Gemma agents.

Multi-agent systems (MAS) can substantially extend the reasoning capacity of large language models (LLMs). Most MAS frameworks aggregate agent outputs via simple majority voting, discarding the evidential structure of reasoning traces. Majority voting is brittle under confabulation consensus, where agents share correlated biases and converge on the same incorrect rationale. We introduce AgentAuditor, which moves beyond frequency-based aggregation by organizing agent traces into a Reasoning Tree that explicitly represents agreements and divergences in their reasoning. AgentAuditor resolves conflicts by comparing branch-level evidence at critical divergence points, turning global adjudication into efficient, localized verification. We further propose Anti-Consensus Preference Optimization (ACPO), which trains the adjudicator with evidence-verified preference supervision to reduce conformity to misleading majority cues. Across four MAS frameworks and multiple reasoning benchmarks, AgentAuditor consistently improves aggregation performance over majority voting, with gains of up to 5% absolute accuracy while remaining token-efficient.

Reaching consensus on massive discussion networks is critical for reducing noise and achieving optimal collective outcomes. However, the natural tendency of humans to preserve their initial ideas constrains the emergence of global solutions. To address this, Collective Intelligence (CI) platforms facilitate the discovery of globally superior solutions. We introduce a dynamical system based on the standard $O(N)$ model to drive the aggregation of semantically similar ideas. The system consists of users represented as nodes in a $d=2$ lattice with nearest-neighbor interactions, where their ideas are represented by semantic vectors computed with a pretrained embedding model. We analyze the system's equilibrium states as a function of the coupling parameter $β$. Our results show that $β> 0$ drives the system toward a ferromagnetic-like phase (global consensus), while $β< 0$ induces an antiferromagnetic-like state (maximum dissent), where users maximize semantic distance from their neighbors. This framework offers a controllable method for managing the tradeoff between cohesion and diversity in CI platforms.

How hard is it to achieve consensus in a social network under uncertainty? In this paper we model this problem as a social graph of agents where each vertex is initially colored red or blue. The goal of the agents is to achieve consensus, which is when the colors of all agents align. Agents attempt to do this locally through steps in which an agent changes their color to the color of the majority of their neighbors. In real life, agents may not know exactly how many of their neighbors are red or blue, which introduces uncertainty into this process. Modeling uncertainty as perturbations of relative magnitude $1+\varepsilon$ to these color neighbor counts, we show that even small values of $\varepsilon$ greatly hinder the ability to achieve consensus in a social network. We prove theoretically tight upper and lower bounds on the price of uncertainty, a metric defined in previous work by Balcan et al. to quantify the effect of uncertainty in network games.

Large Language Models (LLMs) have shown strong capabilities in reasoning and planning, prompting researchers to explore their use as decentralized decision-makers for multi-robot formation control. However, directly applying LLMs to such tasks often leads to unstable behavior, in which robots may collapse to the centroid of their positions or diverge entirely, due to hallucinated reasoning and limited coordination awareness. We propose LLM-Flock, a decentralized multi-robot flocking framework that addresses these challenges through two key mechanisms: (1) an influence-based consensus protocol, where robots iteratively refine individually generated formation plans by adopting those of more connected neighbors, driving the team toward a unified plan without centralized control, and (2) a two-layer collision avoidance strategy that pairs LLM-based urgency reasoning with a programmatic collision checker and re-prompting mechanism. We evaluate LLM-Flock across five state-of-the-art LLMs, including both closed-source (GPT-5, Claude 4.5) and open-source (Llama3.1-405b, Qwen-Max, DeepSeek-R1) models, demonstrating notable improvements in formation stability and convergence over prior LLM-based methods. Real-world experiments with Crazyflie drones further validate the framework's applicability to physical multi-robot systems.

We consider open multi-agent systems, which are systems subject to frequent arrivals and departures of agents while the studied process takes place. We study the behavior of all-to-all pairwise gossip interactions in such open systems. Arrivals and departures of agents imply that the composition and size of the system evolve with time, and in particular prevent convergence. We describe the expected behavior of the system by showing that the evolution of scale-independent quantities can be characterized exactly by fixed-size linear dynamical systems that correspond to Markov processes with states of potentially unbounded dimension. For this purpose we develop a general methodology that could be applicable to larger classes of models. We apply this approach to characterize the evolution of the two first moments (and thus also of a variance-like measure of disagreement) for open systems of fixed and variable size.