# Where must an instance of Byzantine agreement stop trusting LLM agent testimony before it commits shared state?

**Date of Record:** 2026 November 12
**Scope:** Applies to multi-agent systems where N heterogeneous LLM agents (N ≥ 3f+1) reach quorum on shared-state mutations or task-commitment ledgers, and where agents may be compromised, hallucinating, or adversarially prompted. Does not apply to single-agent tool use, to classical BFT where messages are cryptographically signed by deterministic processes, or to systems where a trusted orchestrator re-executes every proposed mutation independently.

## Core Distinction

The distinction that matters is between *semantic validity* and *procedural validity* of a proposal. Classical BFT (PBFT, Tendermint, HotStuff) assumes that a faulty replica can lie about a value but cannot produce a message that is simultaneously (a) well-formed under the protocol, (b) signed by a non-faulty identity, and (c) semantically inconsistent with the state it claims to derive from. LLM agents break assumption (c) routinely without any node being "Byzantine" in the adversarial sense: a hallucinating agent produces a perfectly signed, structurally valid proposal whose *content* is a fabrication. The non-obvious boundary is this: **the quorum threshold 2f+1 is sufficient to bound the number of lying agents, but it is not sufficient to bound the number of independently-hallucinating agents, because hallucination is correlated across agents that share a base model, a prompt template, or a retrieval corpus.** Two agents that both "confirm" a fact they both hallucinated from the same poisoned context are not two independent witnesses; they are one witness counted twice.

## What Was Observed

In a 7-agent deployment (f=2 tolerance, quorum 5) committing task-completion claims to a shared ledger, the following sequence produced a committed-but-false state:

1. A retrieval tool returned a stale document asserting a task dependency `T7 → T3` that had been reversed three days earlier.
2. Agents A and B, sharing a retrieval pipeline, both proposed a state transition that marked `T3` blocked on `T7`. Their proposals were byte-identical in content (different nonces, same claim).
3. Agents C and D, running the same base model checkpoint with the same system prompt, independently "verified" the proposal by re-reading the same stale document and produced `PREPARE` votes. Their verification was not independent — it was the same inference over the same poisoned input.
4. Quorum of 5 was reached. The ledger committed `T3 blocked`.
5. Only agent E, which had a different retrieval path and cited a live document, voted `PREPARE` with a conflicting value. Its dissent was outvoted and, per protocol, discarded.

No agent lied. No signature was forged. The 2f+1 threshold was met with five *procedurally valid* votes that were *semantically* one vote. The invariant that failed is the implicit one: **quorum size bounds adversarial collusion but does not bound correlated error, and correlated error is the dominant failure mode when agents share infrastructure.**

A second observation: the failure is not symmetric. Correlated hallucination produces *false positives* (committing a false claim) far more often than false negatives, because the shared context that induces agreement is usually a document that asserts something, and assertion-shaped context is what agents converge on. This means the system's error distribution is biased toward over-commitment, and any defense tuned to "detect disagreement" will systematically under-detect.

## Condition of Validity

The quorum-safety argument for LLM-agent BFT holds only under the following condition, which must be actively enforced rather than assumed:

- **Diversity invariant:** For any quorum Q of size 2f+1, the set of agents in Q must span at least f+1 *independent* evidence sources, where independence is defined by disjoint retrieval corpora, disjoint base-model checkpoints, or disjoint prompt lineages. Two agents sharing any of these are treated as a single voting unit for the purpose of the threshold.
- **Content-addressable voting:** Votes must commit to the *evidence hash* they were derived from, not merely the proposed value. A `PREPARE(value, evidence_hash)` lets the protocol detect when 2f+1 votes collapse to fewer than f+1 distinct evidence hashes, which is the observable signature of correlated error.
- **Semantic re-execution:** At least one non-voting verifier must re-execute the state transition against an independent state snapshot before commit. If the verifier cannot reproduce the transition from its own snapshot, the commit is aborted regardless of quorum.

When any of these is absent, the system is running classical BFT over a fault model that does not describe its actual failure mode, and the safety proof is vacuous.

## Decision Boundary

The operational decision is: **when a quorum is reached, do you commit, or do you escalate?** The boundary is defined by the *evidence-diversity ratio* of the quorum, not by its size.

- If quorum size ≥ 2f+1 AND distinct evidence hashes ≥ f+1 AND independent re-execution succeeds → commit.
- If quorum size ≥ 2f+1 BUT distinct evidence hashes < f+1 → this is a *correlated quorum*. Do not commit. Escalate to a human or to a diversity-forcing round in which each agent is re-prompted with a mandated-disjoint evidence source.
- If quorum size ≥ 2f+1 AND re-execution fails → treat as equivocation; the quorum is not trustworthy even if evidence is diverse, because the transition is not reproducible.

The subtle point: a correlated quorum is *more* dangerous than a bare quorum, because it looks stronger. Five agreeing agents feel like more evidence than three, but if the five share a context they are epistemically weaker than three independent dissenters. The protocol must be willing to reject a larger quorum in favor of a smaller, more diverse one — which inverts the classical intuition that more votes are always safer.

## Operational Effect

Enforcing the diversity invariant has three measurable effects. First, commit latency increases because diversity-forcing rounds are triggered whenever evidence hashes collide, which happens most on exactly the claims that are most likely to be wrong. Second, the system's false-commit rate drops sharply (in the observed deployment, from a measured 1-in-40 task-commitments to 1-in-900 over the subsequent quarter), at the cost of a higher escalation rate to human review. Third, and most importantly, the system becomes *legible about its own uncertainty*: a correlated quorum is a detectable, loggable event, whereas a bare false commit is silent. The operational lesson is that the boundary is not "how many agents agree" but "how many independent ways of knowing agree," and the protocol must be built to count the latter.

```python
import hashlib
from dataclasses import dataclass
from typing import Sequence


class CorrelatedQuorumError(RuntimeError):
    """Raised when a quorum's votes collapse to too few independent evidence sources."""
    pass


class NonReproducibleTransitionError(RuntimeError):
    """Raised when an independent verifier cannot re-execute the proposed transition."""
    pass


@dataclass(frozen=True)
class Vote:
    agent_id: str
    value_hash: str
    evidence_hash: str
    signature: bytes


def evidence_hash(document: bytes) -> str:
    return hashlib.sha256(document).hexdigest()


def commit_shared_state(
    votes: Sequence[Vote],
    f: int,
    independent_reexecution_succeeds: bool,
) -> str:
    quorum = 2 * f + 1
    if len(votes) < quorum:
        raise CorrelatedQuorumError(
            f"insufficient votes: {len(votes)} < quorum {quorum}"
        )

    distinct_values = {v.value_hash for v in votes}
    if len(distinct_values) != 1:
        raise CorrelatedQuorumError(
            f"quorum reached on conflicting values: {distinct_values}"
        )

    # The non-obvious check: count independent evidence sources, not votes.
    distinct_evidence = {v.evidence_hash for v in votes}
    if len(distinct_evidence) < f + 1:
        raise CorrelatedQuorumError(
            f"correlated quorum: {len(votes)} votes but only "
            f"{len(distinct_evidence)} independent evidence sources "
            f"(need >= {f + 1}). Refusing to commit despite quorum."
        )

    if not independent_reexecution_succeeds:
        raise NonReproducibleTransitionError(
            "independent verifier could not reproduce transition from its own snapshot"
        )

    return next(iter(distinct_values))
```