Resilient Consensus in Agentic AI

Technical Summary: Resilient Consensus in Agentic AI

Problem Statement
Large Language Model (LLM) agents are increasingly deployed in multi-agent systems requiring coordination and shared decision-making. A critical challenge arises when these agents must reach a consensus in the presence of adversarial or malfunctioning actors (Byzantine agents). While classical distributed systems theory provides rigorous guarantees for consensus among deterministic agents, it remains unclear whether these theoretical bounds and algorithms transfer to LLM agents, which operate via probabilistic prompting rather than deterministic update rules. The paper investigates whether prompted LLM policies can achieve the agreement theoretically guaranteed by classical resilient consensus conditions and whether classical filtering mechanisms can mitigate failures in agentic AI.

Methodology
The authors frame the agreement problem among LLM agents as a Byzantine consensus game. The experimental setup involves a synchronous network of $N$ agents, comprising $H$ honest agents and $B$ Byzantine agents, communicating over complete and general directed graphs.

• Agents: Honest agents are modeled using the meta-Llama-3.2-3B-Instruct LLM, tasked with agreeing on an integer between 0 and 50. They receive proposals from neighbors and generate new proposals via prompt engineering.
• Adversaries: Byzantine agents are also LLMs, prompted to strategically propose values (either high or low) to prevent the honest agents from converging.
• Protocol: The system runs for a fixed horizon ($T_{max}$). In each round, agents broadcast proposals, and honest agents update their state based on received values.
• Intervention: The study evaluates the efficacy of wrapping LLM policies with classical resilient consensus filters, specifically the Global MSR-type filter (for complete graphs) and the Local MSR-type filter (for general graphs). These filters function by removing the $f$ smallest and $f$ largest values from the received set before an agent computes its next proposal.

Key Contributions

1. Formalization of LLM Consensus Failure: The authors formalize the Byzantine consensus game for LLMs and demonstrate that prompted LLM policies fail to achieve agreement even in regimes where classical theory guarantees a convergent algorithm exists (specifically when $N \ge 3B + 1$). This failure persists across varying temperatures and time horizons, indicating a gap between arbitrary prompted policies and the resilient update rules required for theoretical guarantees.
2. Restoration via Classical Filters: The study shows that wrapping LLM agents with classical resilient consensus filters recovers the achievable agreement.
   • On complete graphs, the global MSR-type filter restores consensus probability to approximately 100%, even in scenarios where the baseline fails.
   • On general graphs satisfying specific topological conditions, the local MSR-type filter improves agreement, though the magnitude of improvement depends on the inherent robustness of the network topology.
3. Robustness Analysis: Through ablation studies, the authors confirm that these effects are robust across different sampling temperatures and consensus horizons. They further demonstrate that the filters remain effective even when the number of Byzantine agents ($B$) is misspecified (over-estimated), provided the filter parameter $f$ is set to an upper bound.

Experimental Results

• Baseline Performance: In complete graphs, consensus probability drops significantly as $B$ increases, failing well before the theoretical threshold of $N < 3B + 1$. For instance, with $H=15$ and $B=4$, the baseline consensus probability was only 30% at temperature 0.5, despite theory suggesting agreement should be possible.
• Filter Efficacy: Applying the global MSR-type filter ($f=B$) on complete graphs resulted in near-perfect consensus (≈100%) across all tested values of $B$ and temperatures.
• General Graphs: On a specific general graph topology, the baseline achieved high consensus within the theoretically guaranteed regime ($B \le 4$) but degraded beyond it. The local MSR-type filter performed at least as well as the baseline in the guaranteed regime but offered limited additional improvement, suggesting that in densely connected graphs, the topology itself provides substantial robustness.
• Misspecification: When the filter parameter was fixed at $f=6$ while the true $B$ was 0, 2, or 4, the filtered protocol maintained 100% consensus, outperforming the baseline even in the absence of adversaries.

Significance and Claims
The paper posits that classical resilient consensus theory serves as a useful lens for the safety of agentic AI. The primary finding is not a contradiction of classical theory, but rather a demonstration that the implementation of LLM agents via standard prompting does not inherently satisfy the conditions required for consensus. The gap lies between the behavior of a prompted policy and a mathematically resilient update rule.

The authors claim that integrating classical control-theoretic tools, such as resilient consensus filters, acts as a safety layer that can guarantee collective behavior even when individual LLM agents are unreliable or adversarial. They conclude that while the current work focuses on scalar agreement, the natural direction for future work is to extend these notions of resilience to more complex agentic tasks, such as agreeing on plans, answers, or structured decisions.