The Honest Quorum Problem: Epistemic Byzantine Fault Tolerance for Agentic Infrastructure¶

🕒 Published (v1): 2026-07-17 16:43 UTC · Source: Arxiv · link

Why this paper was selected

Byzantine fault tolerance framing for agentic infrastructure; novel epistemic trust model

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Classical Byzantine Fault Tolerance assumes non-Byzantine participants correctly implement protocol semantics, but LLM-based validators can be fully protocol-compliant while collectively endorsing semantically invalid state transitions. This paper formalizes the Honest Quorum Problem and introduces Epistemic Byzantine Fault Tolerance (EBFT), augmenting the classical Byzantine fault bound with confidence-indexed quantities that separately budget coherent invalid endorsement and liveness-degrading unusable support.

Problem¶

Classical BFT and SMR assume validators outside the Byzantine set \(B\) correctly apply transition or validation semantics. Agentic validators break this assumption: an LLM agent can be authenticated, responsive, non-equivocating, and protocol-compliant while endorsing a semantically invalid transition—an epistemic fault. Because agents may share model weights, training distributions, prompts, retrieval sources, toolchains, or provider infrastructure, these faults can be correlated, allowing a protocol-compliant quorum to form a valid certificate for an invalid action. Protocol agreement \(\neq\) semantic validity \(\neq\) execution safety, and the classical \(3f+1\) expression cannot be simply reweighted to handle this.

Method¶

The paper constructs a formal semantic-certificate protocol model over a replica set \(R\) with Byzantine set \(B\) (\(|B| \leq f\)) and protocol-compliant set \(H = R \setminus B\). Each validator returns a signed structured judgment \(J_i = \langle i, \text{view}, \text{digest}(x), s, h_s, a_i, c_i, d_i, p_i \rangle_{\sigma_i}\) where \(a_i \in \{\text{endorse}, \text{reject}, \text{abstain}\}\).

Two confidence-indexed epistemic budget quantities are defined: - \(e_\delta\): an upper bound on the weight of coherent false endorsement among protocol-compliant validators, holding with probability \(\geq 1 - \delta\) (semantic-safety budget) - \(u_\epsilon\): an upper bound on unusable protocol-compliant support (from rejections, abstentions, timeouts, or divergent outputs), holding with probability \(\geq 1 - \epsilon\) (liveness budget)

From these, the paper derives certificate-threshold conditions preventing (a) an invalid candidate from collecting a semantic certificate, (b) conflicting certificates from forming, and (c) liveness failure for valid candidates. The analysis separates coherent epistemic faults (validators converge on the same invalid semantic class—safety risk) from dispersive epistemic faults (errors scatter across incompatible classes—liveness risk). A calibration methodology estimates empirical budget values \(\hat{e}_\delta\), \(\hat{u}_\epsilon\) and their upper confidence endpoints \(\hat{e}^+_\delta\), \(\hat{u}^+_\epsilon\) for threshold selection. Diversity (model, prompt, retrieval, provider) is framed as a mechanism to reduce upper-tail concentration of invalid endorsement, not as a proof of independence.

Key Contributions¶

Formalizes the Honest Quorum Problem: authenticated, responsive, protocol-compliant validators can collectively certify a semantically invalid transition, a failure mode distinct from Byzantine, crash, benign, or equivocating faults
Defines confidence-indexed epistemic budgets \(e_\delta\) (coherent false endorsement) and \(u_\epsilon\) (unusable support), explicitly excluding the Byzantine set unless stated otherwise
Derives EBFT certificate-threshold conditions for semantic certificate validity, agreement, liveness, and feasible quorum selection—not obtainable by reweighting the classical expression
Formulates diversity-aware assurance: diversity labels do not imply epistemic independence; what matters is measured upper-tail concentration of invalid endorsement

Results¶

This is a theoretical paper; no empirical benchmarks are reported. The paper cites supporting empirical evidence from prior work: - Polling-style aggregation for truthfulness can fail to improve over a single sample and can amplify shared misconceptions when model errors are correlated (Denisov-Blanch et al.) - Correlated LLM ensemble errors exhibit saturation effects that limit majority-vote gains relative to independence-based expectations (Turkmen et al.) - Code Triangle study: clustered errors and limited diversity in LLM code implementations; model mixtures improve robustness but do not eliminate the need to measure failure concentration

Limitations¶

Purely theoretical; no implemented system, no empirical evaluation of EBFT thresholds in practice
Calibration methodology for \(e_\delta\) and \(u_\epsilon\) is outlined but not fully specified; obtaining reliable upper-confidence endpoints requires representative workload distributions that may be hard to construct
Theorem statements are not claimed to be tight beyond the proved intersection and threshold conditions
The semantic-validity predicate \(V(x, s)\) is a specification-level object; deployments can only approximate it via deterministic verifiers, model checking, or calibrated labels
Presented as positioning work within the OpenKedge research program, not a deployed or evaluated system

Relevance to Agentic AI / LLM Agents¶

This paper directly addresses a foundational safety gap in multi-agent systems where LLMs vote on or approve actions that mutate operational state. The Honest Quorum Problem formalizes why naively assembling a committee of "diverse" LLM validators does not provide semantic safety guarantees—a crucial insight for any agentic infrastructure involving approval workflows, policy enforcement, or autonomous execution. The EBFT model provides a rigorous framework for reasoning about correlated semantic failures across agents sharing lineage, prompts, or tools, which is endemic to current LLM deployments. For researchers building multi-agent architectures, it establishes that diversity must be measured through failure-concentration metrics rather than assumed from nominal heterogeneity.