# Why does an instance of BFT consensus among LLM agents fail silently when the quorum is composed of agents sharing a common retrieval cache?

**Date of Record:** 2026 November 9

**Scope:** Applies to leaderless or leader-rotating Byzantine fault-tolerant consensus protocols (PBFT, Tendermint-style, HotStuff-style) where the voting replicas are LLM agents that ground their votes in retrieval-augmented generation against a shared vector store or prompt cache. Does not apply when each agent maintains an isolated retrieval corpus, nor to single-agent self-consistency schemes.

## Core Distinction

Classical BFT safety arguments assume Byzantine faults are *independent*: the adversarial set is bounded by `f < n/3`, and no assumption is made about correlation between honest nodes. LLM agents violate this assumption in a specific way. When agents share a retrieval cache, a single poisoned or stale document propagates into the *context window* of every agent that retrieves it. The agents remain honest in the protocol sense — they faithfully execute the vote function — but their votes are now correlated through a shared evidence channel that is not itself subject to the `f < n/3` bound.

The distinction that matters operationally: **Byzantine fault tolerance bounds faulty *replicas*, not faulty *evidence*.** A shared retrieval cache is a single logical input to `n` replicas. If that input is wrong, the quorum is not Byzantine — it is unanimous and wrong. Unanimity is indistinguishable from correctness at the protocol layer, so the protocol commits.

## What Was Observed

In a five-agent HotStuff-style deployment coordinating a shared task queue, a single stale document remained in the retrieval index after a task-state migration. Four of five agents retrieved it during the prepare phase and voted `PREPARE` on a task-state transition that had already been superseded. The fifth agent, whose retrieval window happened to miss the stale doc, voted against. The protocol reached quorum (4 ≥ ⌈2n/3⌉ = 4) and committed the superseded transition.

The failure was silent. No agent raised an error. No timeout fired. The commit was *fast* — the correlated votes arrived within 40 ms of each other, well inside the phase timeout, because the shared cache made retrieval cheap and deterministic. The safety violation was detected only downstream, when a worker agent attempted to execute against the committed-but-superseded state and found a version mismatch.

The counterintuitive part: adding a sixth agent did not help. The sixth agent retrieved from the same cache and voted with the majority. The effective fault bound was not `f < n/3`; it was `f_evidence < 1` — a bound on the *number of independent evidence sources*, not the number of replicas.

## Condition of Validity

The `f < n/3` safety guarantee holds for LLM-agent consensus only when the following invariant is maintained:

> For every vote, the evidence set used by agent `i` is independent of the evidence set used by agent `j` for `i ≠ j`, or the shared evidence is itself subject to a Byzantine agreement round before being admitted to any vote context.

This invariant is violated whenever agents share a mutable retrieval index, a prompt cache, a scratchpad, or a tool-output memoization layer without an intervening validation step. It is *not* violated by shared *immutable* snapshots (e.g., a content-addressed store where reads are verified against a committed hash), because the hash check converts the shared read into an independent verification.

## Decision Boundary

Before admitting a retrieval source to the vote path, classify it:

- **Independent evidence** (per-agent corpus, content-addressed with hash verification, externally attested feed): safe to use directly; preserves classical `f < n/3`.
- **Shared mutable evidence** (vector store, prompt cache, shared scratchpad, memoized tool output): must be treated as a *single Byzantine replica* regardless of how many agents read it. Its admission consumes one unit of the fault budget, and it must be validated by an independent quorum before use.

The operational rule: **count evidence sources, not agents, when computing the fault bound.** A deployment with `n = 7` agents reading from `k = 2` shared caches has an effective fault budget of `min(⌊(n-1)/3⌋, k_validated - 1)`, not `⌊(n-1)/3⌋`.

## Operational Effect

The failure mode is a *commit of an invalid state under apparent quorum*. It is silent, fast, and survives replica addition. Detection requires a downstream invariant check (version monotonicity, hash mismatch, task-state precondition). Mitigation requires either (a) partitioning retrieval indices per agent and cross-checking, or (b) routing shared-cache reads through a separate BFT validation round before they enter a vote context. The cost of (b) is one extra round-trip per vote; the cost of omitting it is undetectable safety violation.

```python
class CorrelatedEvidenceError(RuntimeError):
    """Raised when a vote quorum is composed of agents sharing unvalidated evidence."""
    pass


def validate_quorum_evidence(votes, evidence_source_map, n, f_evidence_validated):
    """
    votes: list of (agent_id, vote, evidence_source_id)
    evidence_source_map: dict source_id -> 'independent' | 'shared_mutable'
    n: total replicas
    f_evidence_validated: number of shared_mutable sources already validated
                          by an independent BFT round before this vote
    """
    quorum = (2 * n) // 3 + 1
    if len(votes) < quorum:
        return False  # normal liveness failure, not a safety issue

    shared_sources_in_quorum = {
        src for (_, _, src) in votes
        if evidence_source_map.get(src) == 'shared_mutable'
    }
    unvalidated_shared = shared_sources_in_quorum - set(range(f_evidence_validated))

    if unvalidated_shared:
        raise CorrelatedEvidenceError(
            f"Quorum of {len(votes)} votes draws on {len(unvalidated_shared)} "
            f"unvalidated shared evidence source(s) {sorted(unvalidated_shared)}; "
            f"effective fault bound collapses to f_evidence < 1. "
            f"Commit would be silent and unsafe."
        )
    return True


def commit_transition(votes, evidence_source_map, n, f_evidence_validated):
    if not validate_quorum_evidence(votes, evidence_source_map, n, f_evidence_validated):
        return "NO_COMMIT"
    return "COMMIT"
```