BR-MAS: Byzantine-Resilient Multi-Agent Collaboration via Adaptive Quorum Consensus

Multi-agent systems (MAS) built from LLMs are increasingly deployed on real collaborative tasks, yet their interaction fabric is fragile: a few Byzantine participants (colluding, contradicting, or injecting misinformation) can derail outcomes that no single-agent defense addresses. Existing collaboration paradigms fail structurally: discussion-based schemes have no containment mechanism, role-based schemes concentrate trust in single points of failure, and consensus-based protocols rest on self-reported confidence that adversaries can fabricate. We observe that LLM agents can judge each other’s proposals, so voting weight can track verified behavior instead of self-report. The honest/Byzantine weight ratio ρ then becomes a single lever on both fault tolerance and quorum cost: the bound improves from the classical f < n/3 to f < nρ/(ρ + 2) in general, and to f < nρ/(ρ + 1) under single-proposal-single-vote enforcement. We instantiate this in BR-MAS, a pluggable Byzantine-resilient collaboration framework combining structured consensus proposals, four-dimensional decentralized verification, a behavior-driven Byzantine classifier with weight amplification, and an adaptive quorum with early termination. Across MMLU-Pro, TAMAS, ARGUS, and MARBLE—two backbone families, three capability tiers, and up to six of seven agents adversarial—BR-MAS degrades gracefully where baseline accuracy collapses nearly to zero, sharply reduces attack success, and cuts token cost by an order of magnitude.