Consensus and Byzantine Fault Tolerance for Agents

You have N LLM agents, each producing an answer, and they disagree. Majority vote picks the wrong one because two agents are correlated (same base model, same training data, same failure modes). A third agent happens to be wrong in a novel way, so the majority is a false majority.

Now add a deceptive agent that lies on purpose. Or a sycophantic agent that agrees with whoever spoke last. Classical BFT assumes the Byzantine nodes are a fraction f < n/3 and behave arbitrarily. LLM nodes in 2026 are stochastic even when honest, correlated across models, and influenced by each other's outputs, so you can't treat them as independent Bernoulli voters.

Classical BFT (PBFT, 1999) is not wrong, just incomplete. It handles arbitrary bit-flipping. It does not handle three honest agents sharing a hallucination because they share training data. This lesson starts from PBFT's foundation and layers three 2025-2026 adaptations on top.

What classical BFT gives you

Practical Byzantine Fault Tolerance (Castro & Liskov, OSDI 1999) tolerates f < n/3 Byzantine nodes. The protocol has three phases (pre-prepare, prepare, commit) and two primitives (signed messages, quorum certificates). It gets n >= 3f + 1 honest-or-malicious nodes to agree on a single value.

The guarantees are strong, but they rest on three assumptions:

1. Independent faults. Byzantine nodes do not coordinate.
2. Honest nodes are truly honest. Correctness of honest outputs is a non-issue, and the protocol only aligns disagreement.
3. The question has a ground-truth answer. Consensus on a wrong fact is still consensus.

LLM agents break all three. Two agents running the same base model share faults. An "honest" LLM still hallucinates. On ambiguous questions the "truth" is whatever the agents decide, because there is no external oracle.

The three LLM-specific attacks

Byzantine lie. One agent outputs a deliberately wrong answer. Classical BFT handles this when f < n/3.

Sycophantic conformity. One agent reads the others' answers before voting and aligns with whoever spoke last. It isn't malicious, but its vote tracks the loudest voice. Classical BFT can't prevent this because the agent passes every signature check.

Correlated-error monoculture. Three agents share a base model and hallucinate the same wrong answer. The majority is wrong, and classical BFT can't help because all three "honestly" agree.

The 2025-2026 responses

CP-WBFT (arXiv:2511.10400) is Confidence-Probed Weighted BFT. Each voter attaches a confidence probe to its answer, either a self-reported probability or a separate calibration model's prediction, and vote weights scale with confidence. The paper reports a +85.71% BFT improvement on complete graphs. It targets sycophantic conformity, since conforming agents tend to have low confidence in a position they only volunteered.

DecentLLMs (arXiv:2507.14928) is leaderless. Worker agents propose in parallel, evaluator agents score the proposals, and the final answer is the geometric median of the scored positions. It is robust when f < n/2. It targets the Byzantine lie and correlated errors, because the geometric median resists outliers and pulls toward the dense cluster instead of the model-biased average.

WBFT (arXiv:2505.05103) is Weighted BFT with Hierarchical Structure Clustering. Vote weights come from response quality plus a trust score learned from history. Agents are clustered into Core and Edge: Core agents reach consensus first and Edge agents follow. This helps with scalability (the Core is small and fast) and partly with monoculture (you can pick the Core for diversity).

Empirical: "Can AI Agents Agree?" (arXiv:2603.01213)

The paper measures scalar agreement, meaning LLM agents agreeing on a single numeric value, across multiple frontier models. The findings are uncomfortable:

• With no adversaries at all, LLM agents disagree on scalar questions at rates above 30% on many benchmarks.
• A single agent with a deceptive persona can pull the Mixture-of-Agents consensus 40+ percentage points off the honest baseline.
• Disagreement rates correlate with model diversity. Heterogeneous ensembles disagree more than homogeneous ones, which is good because their errors are less correlated. They also drift toward agreement more slowly, which is bad because time-to-agreement grows.

The takeaway: BFT gives you machinery to align outputs, but it can't tell you whether the aligned output is right. Pair it with verification (Phase 16 · 08 role specialization), diversity (Phase 16 · 15 debate variants), and evaluator agents (Phase 16 · 24 benchmarks).

The core protocol, stripped down

A minimal BFT round for LLM agents:

1. task arrives; each agent i produces answer a_i
2. each agent attaches confidence probe c_i in [0, 1]
3. aggregator collects (a_i, c_i) from all n agents
4. aggregator groups by semantic cluster (equivalent answers)
5. aggregator computes weight for each cluster C:
     w(C) = sum_{i in C} c_i
6. winner = cluster with max weight, if max > threshold * sum(c_i)
   else: retry or escalate
7. minority clusters logged with provenance for post-hoc audit

Semantic clustering is the LLM-specific twist. "The study reports 4.2%" and "4.2% improvement" belong in the same cluster, and a naive string-equality check would miss that. So would the demo's canonicalizer below, which strips case and punctuation but not extra words, so 4.2%improvement would land in its own cluster. In production, use a cheap embedding model or explicit canonicalization.

Threshold tuning

The threshold parameter decides when to accept a result and when to retry. Set it too low and you accept weak majorities. Set it too high and you never accept anything. The empirical range is 0.5-0.67 for n=5-7 agents, and higher for smaller n. Below the threshold, escalate to a human or to a different agent ensemble.

Where consensus does not help

• Ambiguous questions. If the question has no ground truth, consensus is an opinion. Call it that.
• Compound questions. "Write code and explain it" is two answers, so vote on each independently.
• Adversarial multi-round. If agents can observe prior rounds and mimic each other (Du 2023 debate), they start agreeing regardless of truth. Bound the rounds, typically to 2-3.

code/main.py is stdlib-only Python. The pieces:

• Vote, a dataclass holding (agent, answer, confidence). Its canonical() method is the clustering step: lowercase the answer and strip everything except alphanumerics, . and %. That is string canonicalization, not embeddings.
• plurality, classical one-agent-one-vote counting.
• cp_wbft, which sums confidence per cluster and rejects the round if the winner holds less than threshold (default 0.5) of the total weight.
• decentllms, a simplified stand-in. The aggregator scores clusters itself, using confidence as the score. Each cluster gets size * max(0, 1 - dist), where dist is the summed absolute distance of its members' confidences from the cluster median. It is not a true geometric median over scored proposals.
• scenario, which prints the votes and each aggregator's answer, marked [CORRECT], [WRONG] or [rejected below threshold].

main() runs four scenarios on the same question, where the correct answer is 4.2%: no attack, byzantine (one agent lies with high confidence), sycophancy (two agents echo the first answer, 42%, with low confidence) and monoculture (three agents confidently share the same wrong answer).

Run:

python3 code/main.py

The output is one block per scenario, listing each agent's vote and then the three aggregators' answers. On the votes hard-coded in main(), all three aggregators get the first three scenarios right and all three get monoculture wrong. The takeaways printed at the end say why: no aggregator here can beat a wrong cluster that is both larger and more confident than the right one. That case needs diversity or verification.

outputs/skill-consensus-designer.md designs a consensus protocol for a multi-agent ensemble. It picks the clustering method, the weighting, the threshold, and the escalation policy for sub-threshold rounds.

Before shipping any consensus mechanism:

• Attack-test with at least the three patterns above. Your protocol should fail predictably, not silently.
• Log each minority cluster with provenance. Minority clusters are your early-warning system for correlated errors.
• Bound the rounds. "Keep debating until agreement" rewards sycophancy.
• Separate agreement from correctness. Consensus output goes to a verifier, and the verifier is independent of the ensemble.
• Monitor the agreement rate. A sharp rise points to conformity bias, and a sharp fall points to model drift.

1. Run code/main.py. Confirm plurality fails the monoculture attack, and note that CPWBFT fails it too on the shipped votes. Then lower the three monoculture confidences until CPWBFT flips to the right answer, and record where that happens.
2. Add a fourth attack pattern: silent abstention: one agent refuses to answer ("I don't know"). How should each aggregator treat abstentions? Implement your choice.
3. Swap the semantic clustering from string canonicalization to embedding-similarity (use any open-source embedding model). What happens to the sycophancy attack?
4. Read CP-WBFT (arXiv:2511.10400). Implement the confidence-probe calibration step (a separate calibration model checks each agent's self-reported confidence). Measure the accuracy gain on the monoculture scenario.
5. Read "Can AI Agents Agree?" (arXiv:2603.01213). Reproduce a simplified scalar-agreement experiment: three agents, one scalar question, the deceptive-persona prompt. Does CPWBFT or DecentLLMs catch it?

• Castro & Liskov: Practical Byzantine Fault Tolerance (OSDI 1999): the foundation
• CP-WBFT: Confidence-Probe Weighted BFT: vote weighting by confidence
• DecentLLMs: leaderless multi-agent consensus: geometric-median aggregation
• WBFT: Weighted BFT with Hierarchical Structure Clustering: Core/Edge split for bounded latency
• Can AI Agents Agree?: scalar-agreement fragility and deceptive-persona attack