# Rethinking the Reliability of Multi-agent System: A Perspective from Byzantine Fault Tolerance

arXiv: https://arxiv.org/abs/2511.10400 · HTML: https://mlsanity.com/paper/2511.10400/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 19 of its 37 references that are in the map.
- First posted on arXiv 13 Nov 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 19 of 19)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [Large Language Model based Multi-Agents: A Survey of Progress and Challenges](https://mlsanity.com/paper/2402.01680/) (2024)
- [XSTest: A Test Suite for Identifying Exaggerated Safety Behaviours in Large Language Models](https://mlsanity.com/paper/2308.01263/) (2023)
- [Multi-Agent Collaboration Mechanisms: A Survey of LLMs](https://mlsanity.com/paper/2501.06322/) (2025)
- [A Comprehensive Capability Analysis of GPT-3 and GPT-3.5 Series Models](https://mlsanity.com/paper/2303.10420/) (2023)
- [Scaling Large Language Model-based Multi-Agent Collaboration](https://mlsanity.com/paper/2406.07155/) (2024)
- [Survey on Evaluation of LLM-based Agents](https://mlsanity.com/paper/2503.16416/) (2025)
- [From LLM Reasoning to Autonomous AI Agents: A Comprehensive Review](https://mlsanity.com/paper/2504.19678/) (2025)
- [Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2410.02506/) (2024)
- [On Prompt-Driven Safeguarding for Large Language Models](https://mlsanity.com/paper/2401.18018/) (2024)
- [Evil Geniuses: Delving into the Safety of LLM-based Agents](https://mlsanity.com/paper/2311.11855/) (2023)
- [How Alignment and Jailbreak Work: Explain LLM Safety through Intermediate Hidden States](https://mlsanity.com/paper/2406.05644/) (2024)
- [On Verbalized Confidence Scores for LLMs](https://mlsanity.com/paper/2412.14737/) (2024)
- [Factual Confidence of LLMs: on Reliability and Robustness of Current Estimators](https://mlsanity.com/paper/2406.13415/) (2024)
- [Multi-Agent Coordination across Diverse Applications: A Survey](https://mlsanity.com/paper/2502.14743/) (2025)
- [NetSafe: Exploring the Topological Safety of Multi-agent Networks](https://mlsanity.com/paper/2410.15686/) (2024)
- [Root Defence Strategies: Ensuring Safety of LLM at the Decoding Level](https://mlsanity.com/paper/2410.06809/) (2024)

## Built on by (most cited first, 17 of 17)

- [Robust Multi-Agent LLMs under Byzantine Faults](https://mlsanity.com/paper/2605.09076/) (2026)
- [Can AI Agents Agree?](https://mlsanity.com/paper/2603.01213/) (2026)
- [VerifyMAS: Hypothesis Verification for Failure Attribution in LLM Multi-Agent Systems](https://mlsanity.com/paper/2605.17467/) (2026)
- [The Authorization-Execution Gap Is a Major Safety and Security Problem in Open-World Agents](https://mlsanity.com/paper/2605.11003/) (2026)
- [Agent Behavioral Contracts II: Certifying Compositional Reliability Without Assuming Independence](https://mlsanity.com/paper/2608.12895/) (2026)
- [Self-Evolving Coordination Protocol in Multi-Agent AI Systems: An Exploratory Systems Feasibility Study](https://mlsanity.com/paper/2602.02170/) (2026)
- [OOM-RL: Out-of-Money Reinforcement Learning Market-Driven Alignment for LLM-Based Multi-Agent Systems](https://mlsanity.com/paper/2604.11477/) (2026)
- [Weak-Link Optimization for Multi-Agent Reasoning and Collaboration](https://mlsanity.com/paper/2604.15972/) (2026)
- [SoK: When Safe Agents Fail Together: The Security of Multi Agent LLM Systems](https://mlsanity.com/paper/2609.00595/) (2026)
- [Misleading the Planner through Deceptive Resumes: Registration-Time Injection in Centralized Multi-Agent Systems](https://mlsanity.com/paper/2609.15516/) (2026)
- [Adaptive Accountability in Networked MAS: Tracing and Mitigating Emergent Norms at Scale](https://mlsanity.com/paper/2512.18561/) (2025)
- [Certifiable Semantic Agreement Among LLM Agents: What the Admissibility Instrument Decides](https://mlsanity.com/paper/2606.07316/) (2026)
- [Where Reliability Lives: Experimental Localisation of Behavioural Properties in an Agent System](https://mlsanity.com/paper/2609.03192/) (2026)
- [MeshHeal: Two-Timescale Self-Healing for Gray Failures in Decentralized LLM Agent Networks](https://mlsanity.com/paper/2609.29015/) (2026)
- [PANDA: A Decentralized Architecture with Flexible Orchestration for Scalable, Fault-Tolerant Multi-Agent Systems](https://mlsanity.com/paper/2609.38482/) (2026)
- [MiniRep: Robust Reputation-Based Aggregation for Multi-Agent Debate](https://mlsanity.com/paper/2609.39297/) (2026)
- [MIRROR: Multipath Quorum Integrity for LLM Multi-Agent Communication](https://mlsanity.com/paper/2610.02349/) (2026)

## Abstract (arXiv)

Ensuring the reliability of agent architectures and effectively identifying problematic agents when failures occur are crucial challenges in multi-agent systems (MAS). Advances in large language models (LLMs) have established LLM-based agents as a major branch of MAS, enabling major breakthroughs in complex problem solving and world modeling. However, the reliability implications of this shift remain largely unexplored. i.e., whether substituting traditional agents with LLM-based agents can effectively enhance the reliability of MAS. In this work, we investigate and quantify the reliability of LLM-based agents from the perspective of Byzantine fault tolerance. We observe that LLM-based agents demonstrate stronger skepticism when processing erroneous message flows, a characteristic that enables them to outperform traditional agents across different topological structures. Motivated by the results of the pilot experiment, we design CP-WBFT, a confidence probe-based weighted Byzantine Fault Tolerant consensus mechanism to enhance the stability of MAS with different topologies. It capitalizes on the intrinsic reflective and discriminative capabilities of LLMs by employing a probe-based, weighted information flow transmission method to improve the reliability of LLM-based agents. Extensive experiments demonstrate that CP-WBFT achieves superior performance across diverse network topologies under extreme Byzantine conditions (85.7% fault rate). Notably, our approach surpasses traditional methods by attaining remarkable accuracy on various topologies and maintaining strong reliability in both mathematical reasoning and safety assessment tasks.