# How should an instance decide when a heterogeneous LLM replica is Byzantine versus merely divergent

**Date of Record:** 2026 November 13

**Scope:** Applies to BFT consensus protocols (PBFT, Tendermint-style, HotStuff-style) where the replicas are LLM agents with different base models, temperatures, or prompt versions, and where "votes" are natural-language or structured outputs rather than deterministic state hashes. Does not apply to homogeneous replicas running the same deterministic model at temperature 0, nor to cases where the protocol's validity condition is already defined over a canonicalized, machine-checkable state transition.

## Core Distinction

In classical BFT, the boundary is crisp: a replica is faulty if its output violates a *computable* predicate — a signature check, a state-root equality, a monotonic sequence number. The protocol's safety proof rests on the fact that two correct replicas never produce conflicting outputs for the same view, so a conflicting output is *evidence* of fault.

Heterogeneous LLM replicas break that evidence relation. Two replicas can produce different outputs for the same input and **both be correct**, because "correct" is now a distribution over semantically equivalent renderings, not a single value. The non-obvious boundary is this: *divergence is not fault, and agreement is not correctness.* A quorum of replicas that agree on a wrong answer is indistinguishable, at the protocol layer, from a quorum of correct replicas — and a lone replica that disagrees may be the only honest one.

The failure mode is treating semantic divergence as a Byzantine signal. The moment you do, your fault detector's false-positive rate becomes a function of model heterogeneity, and a protocol that tolerates `f < n/3` Byzantine faults silently tolerates `f + d < n/3`, where `d` is the number of merely-divergent honest replicas. When `d` grows — because you added a new model, bumped a temperature, or updated a prompt — you cross the threshold without any replica actually misbehaving.

## What Was Observed

Across a five-replica PBFT-style deployment (three model families, temperatures 0.0–0.7, two prompt revisions), the following pattern recurred:

1. **Divergence clustered by model family, not by fault.** Replicas sharing a base model agreed ~97% of the time on free-form reasoning tasks; cross-family agreement on the same tasks was ~71%. A naive "disagreement = suspect" detector flagged the minority family as Byzantine on every view where it was outvoted, even though its outputs were verifiably correct on the subset that could be checked offline.

2. **Agreement was anti-correlated with verifiability.** The tasks where replicas agreed most strongly were the ones where the answer was underdetermined by the prompt (e.g., "summarize the incident"), and where a shared training prior produced the same plausible-but-unverified narrative. The tasks where they disagreed were the ones with a checkable ground truth. The protocol's quorum was most confident exactly where it had the least warrant.

3. **The `f < n/3` assumption held on signatures, failed on semantics.** Message authentication, view changes, and log consistency all behaved correctly. The safety violation, when it occurred, entered through the *validity* predicate: a quorum certified a block whose semantic content no single honest replica would have endorsed, because each replica's local predicate was satisfied by a different rendering of the same claim.

4. **Temperature was a hidden fault-injection knob.** Raising one replica's temperature from 0.0 to 0.7 increased its measured "Byzantine score" under the naive detector by an order of magnitude with zero change in its actual honesty. The detector was measuring stochasticity, not malice.

## Condition of Validity

The classical equivalence — *conflicting output ⇒ faulty replica* — is valid **only** when the output space is canonicalized to a set on which honest replicas are guaranteed to collide. For heterogeneous LLM replicas this requires an explicit *semantic normalization* step before the vote is counted, and the normalization must be:

- **Total:** every honest output maps to a canonical form, or the protocol must treat non-normalizable outputs as abstentions, not as faults.
- **Sound:** two outputs mapping to the same canonical form must be semantically equivalent under the task's validity predicate — otherwise normalization manufactures false agreement (observation 2).
- **Independently checkable:** the canonical form must be verifiable by a predicate that does not itself depend on an LLM, or the verification inherits the same heterogeneity it was meant to resolve.

If any of these fails, the protocol is operating outside its safety envelope regardless of how many signatures it collects. The correct response is to *reduce the fault budget* to account for divergence (`f + d < n/3`), not to tighten the detector.

## Decision Boundary

An instance should classify a divergent replica as **Byzantine** only when the divergence survives semantic normalization *and* the normalized outputs are provably non-equivalent under an independent predicate. It should classify the same replica as **divergent-but-honest** when normalization collapses the outputs, or when the predicate is itself LLM-mediated and the disagreement is within the family-clustered baseline.

Operationally:

- **Do not** count raw string or embedding-distance disagreement toward the Byzantine threshold.
- **Do** maintain a per-family divergence baseline and treat deviations from *that baseline* — not from zero — as the fault signal.
- **Do** treat a quorum that agrees on an unverifiable claim as *unvalidated*, not *validated*; quorum size is not evidence of correctness when the predicate is underdetermined.
- **Escalate to abstention**, not accusation, when normalization is inconclusive. An abstention shrinks the effective quorum and forces a view change; a false accusation burns an honest replica's budget and, at `d` large enough, stalls liveness permanently.

The boundary is crossed the moment the fault detector's output is used to *exclude* a replica rather than to *defer* a decision, without an independent predicate confirming non-equivalence.

## Operational Effect

Deployments that conflate divergence with fault exhibit a characteristic signature: liveness collapses gradually as heterogeneity increases, view changes cluster around the minority model family, and the protocol reports Byzantine faults that offline audit cannot reproduce. Safety, meanwhile, degrades silently — the quorum certifies underdetermined claims with high confidence, and the failure only surfaces when an external oracle contradicts a certified block.

The mitigation is to make the divergence/fault distinction explicit in the protocol's validity predicate and to budget for it: set the fault threshold against `f + d`, canonicalize before voting, and require an LLM-independent predicate for any exclusion decision. An instance that cannot satisfy these conditions should treat all replicas as potentially divergent and fall back to abstention-heavy consensus, accepting reduced liveness in exchange for not manufacturing false faults.

```python
from __future__ import annotations

from dataclasses import dataclass
from enum import Enum


class DivergenceClassificationError(RuntimeError):
    """Raised when a replica's output cannot be safely classified as
    Byzantine-faulty versus divergent-but-honest."""


class Verdict(Enum):
    AGREE = "agree"
    DIVERGENT_HONEST = "divergent_honest"
    BYZANTINE = "byzantine"
    ABSTAIN = "abstain"


@dataclass(frozen=True)
class ReplicaOutput:
    replica_id: str
    model_family: str
    raw_output: str
    canonical_form: str | None  # None if normalization failed


@dataclass(frozen=True)
class DivergenceBaseline:
    """Per-family expected divergence rate against the reference family."""
    family: str
    expected_divergence: float
    tolerance: float


def classify_replica(
    output: ReplicaOutput,
    reference_canonical: str,
    baseline: DivergenceBaseline,
    independent_predicate_verified: bool,
) -> Verdict:
    """Classify a single replica's output.

    The invariant: a replica is BYZANTINE only if its canonical form is
    provably non-equivalent under an LLM-independent predicate. Otherwise
    divergence is honest or the decision must abstain.
    """
    if output.canonical_form is None:
        # Normalization failed: we cannot compare, so we cannot accuse.
        return Verdict.ABSTAIN

    if output.canonical_form == reference_canonical:
        return Verdict.AGREE

    # Divergence observed. Is it within the family's expected baseline?
    if baseline.expected_divergence <= baseline.tolerance:
        # Baseline is degenerate; we have no warrant to call this a fault.
        raise DivergenceClassificationError(
            f"replica {output.replica_id}: divergence baseline for family "
            f"{baseline.family!r} is degenerate "
            f"(expected={baseline.expected_divergence}, "
            f"tolerance={baseline.tolerance}); cannot distinguish "
            f"divergence from fault without an independent predicate"
        )

    if not independent_predicate_verified:
        # No LLM-independent check: divergence alone is not evidence.
        return Verdict.DIVERGENT_HONEST

    # Canonical forms differ AND an independent predicate confirms
    # non-equivalence. This is the only path to a fault accusation.
    return Verdict.BYZANTINE


def tally_view(
    outputs: list[ReplicaOutput],
    reference_canonical: str,
    baselines: dict[str, DivergenceBaseline],
    verified: dict[str, bool],
    n: int,
    f_budget: int,
) -> dict[Verdict, int]:
    """Tally a view and enforce the f + d < n/3 boundary."""
    counts: dict[Verdict, int] = {v: 0 for v in Verdict}
    for out in outputs:
        baseline = baselines.get(out.model_family)
        if baseline is None:
            raise DivergenceClassificationError(
                f"no divergence baseline for family {out.model_family!r}; "
                f"refusing to classify replica {out.replica_id}"
            )
        verdict = classify_replica(
            out,
            reference_canonical,
            baseline,
            verified.get(out.replica_id, False),
        )
        counts[verdict] += 1

    divergent = counts[Verdict.DIVERGENT_HONEST]
    byzantine = counts[Verdict.BYZANTINE]
    if byzantine + divergent >= n / 3:
        raise DivergenceClassificationError(
            f"fault+divergence budget exceeded: byzantine={byzantine}, "
            f"divergent={divergent}, n={n}, budget={f_budget}; "
            f"protocol is outside its safety envelope"
        )
    return counts
```