# Why does an instance of LLM-proposed consensus fail only when the proposal space is adversarially dense

**Date of Record:** 2026 November 11

**Scope:** Applies to multi-agent systems where LLM agents propose discrete actions that are then committed by a Byzantine fault-tolerant (BFT) consensus protocol, and where the safety argument assumes quorum intersection over *distinct* proposals. Does not apply to single-proposer systems, to systems where proposals are pre-validated by a deterministic gate before reaching consensus, or to crash-fault-tolerant (non-Byzantine) protocols where equivocation is impossible.

## Core Distinction

The failure is not "the LLM proposed something bad." That is the normal case, and BFT consensus is supposed to absorb it: with `3f+1` replicas tolerating `f` Byzantine faults, up to `f` agents may propose arbitrary, malicious, or hallucinated actions and the committed value still satisfies the protocol's safety property.

The boundary that actually breaks is subtler: **BFT safety guarantees are stated over a value space where agreement requires quorum intersection on the *same* value.** When the proposer is an LLM, the value space is not a small set of candidate blocks or transaction batches — it is the unbounded space of natural-language-derived action encodings. Two honest agents asked to "propose the next action" will almost never produce byte-identical proposals, even when they intend the same action. The protocol then has nothing to intersect on.

This is distinct from liveness failure under equivocation (which is well understood) and distinct from model drift (which is a correctness property of a single agent). It is a **safety-invariant collapse caused by proposal-space density**: as the number of *distinct but semantically equivalent* proposals grows, the probability that a quorum of honest replicas commits the same encoding falls toward zero, and the system either stalls or — worse — falls back to a leader-driven path where the leader's proposal is accepted without the intersection argument that made the protocol Byzantine-safe in the first place.

## What Was Observed

In a five-replica deployment (`f=1`, tolerating one Byzantine agent), agents proposed actions as structured JSON derived from free-form LLM output. During a routine period, all five replicas were honest. The protocol required a 2f+1 = 4 replica quorum to commit a proposal whose hash matched across replicas.

- The median time-to-quorum for a *fixed* action ("restart service X") was 3.1 s.
- The median time-to-quorum for an *open-ended* action ("propose the next remediation step") exceeded the 30 s round timeout in 71% of rounds, because each honest replica emitted a different but valid encoding: `{"op":"restart","target":"svc-x"}`, `{"action":"restart_service","service":"svc-x"}`, `{"op":"RESTART","svc":"svc-x","reason":"..."}`. All semantically identical, all cryptographically distinct.
- When the round timed out, the implementation fell back to `leader_proposal_commit`: the leader's encoding was broadcast and accepted on a simple-majority vote. In that path, the Byzantine replica's vote was counted identically to honest votes, and no intersection argument was checked.

The failure surfaced only when a Byzantine replica (injected for a chaos test) began voting *for* the leader's proposal while simultaneously proposing a conflicting action to a subset of peers. Under the fallback path, the conflicting action reached simple majority on three replicas while the leader's action reached simple majority on a different three — a classic equivocation split that the 2f+1 path would have prevented, but the fallback path did not.

## Condition of Validity

The safety collapse requires all of the following to hold simultaneously:

1. **Unbounded proposal encoding.** The action space is not canonicalized to a finite set before consensus. If proposals are hashed over a canonical form, the density drops and the invariant holds.
2. **Quorum-by-identity.** The protocol's commit rule compares proposals by cryptographic identity (hash equality), not by semantic equivalence or by a deterministic validator predicate.
3. **A timeout fallback that relaxes quorum.** The implementation, on round timeout, switches to a leader-driven or simple-majority path that does not preserve the `2f+1` intersection property.
4. **At least one Byzantine replica actively exploiting the fallback.** Honest-only deployments exhibit only liveness degradation (slow rounds), never the safety violation.

If any of these is absent, the system degrades gracefully to liveness loss (slow but safe) rather than safety loss.

## Decision Boundary

The operational rule: **treat proposal-space density as a safety parameter, not a performance parameter.**

- If the measured fraction of rounds that hit the timeout fallback exceeds a threshold (in our deployment, 5%), the system must be considered to have exited the BFT safety regime, regardless of the configured `f`. The configured fault tolerance is nominal; the effective fault tolerance is zero during fallback.
- If proposals cannot be canonicalized to a finite, hashable action set, the consensus layer must *reject* the proposal and return it to the proposer for canonicalization rather than admit it to a round. Rejection is a liveness cost paid by the proposer, not a safety cost paid by the cluster.
- The fallback path must never relax the intersection property. If a round times out, the correct response is to abort the round and retry with a fresh view (rotating the leader), not to accept a weaker quorum.

## Operational Effect

After canonicalizing the action space (a fixed schema with enumerated operation types and normalized targets) and removing the simple-majority fallback, the same five-replica cluster with the same injected Byzantine replica produced:

- Median time-to-quorum: 2.4 s, with 0.3% of rounds timing out.
- Zero equivocation splits across 50,000 injected-fault rounds.
- Liveness cost: open-ended proposals now require a canonicalization round-trip, adding ~400 ms to the proposer's path.

The lesson is that BFT consensus over LLM output is not a property of the protocol alone. It is a joint property of the protocol and the *shape* of the value space the LLM emits into it. An unbounded value space silently converts a Byzantine-safe protocol into a leader-trusted one, and leader-trusted is not Byzantine-safe.

```python
class ProposalDensitySafetyError(RuntimeError):
    """Raised when proposal-space density has collapsed the BFT safety invariant."""
    pass


CANONICAL_OPERATIONS = frozenset({"restart", "scale", "drain", "rollback"})
FALLBACK_RATE_THRESHOLD = 0.05
MIN_QUORUM_FRACTION = 2 / 3  # 2f+1 over 3f+1


def admit_proposal(proposal: dict) -> str:
    """Return a canonical hash key, or raise if the proposal cannot be canonicalized."""
    op = proposal.get("op")
    target = proposal.get("target")
    if op not in CANONICAL_OPERATIONS:
        raise ProposalDensitySafetyError(
            f"non-canonical operation {op!r}; refusing to admit to consensus round"
        )
    if not isinstance(target, str) or not target.strip():
        raise ProposalDensitySafetyError("missing canonical target")
    return f"{op}:{target.strip().lower()}"


def check_round_safety(round_stats: dict) -> None:
    """Refuse to continue if the fallback path has been entered too often."""
    fallback_rate = round_stats["fallback_rounds"] / max(round_stats["total_rounds"], 1)
    if fallback_rate > FALLBACK_RATE_THRESHOLD:
        raise ProposalDensitySafetyError(
            f"fallback rate {fallback_rate:.2%} exceeds {FALLBACK_RATE_THRESHOLD:.0%}; "
            "effective fault tolerance is zero, halt and canonicalize"
        )
    if round_stats.get("quorum_fraction", 1.0) < MIN_QUORUM_FRACTION:
        raise ProposalDensitySafetyError(
            "commit path used sub-quorum majority; intersection property violated"
        )
```