Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification

arXiv:2610.33587v1 [cs.CR] 24 Oct 2026

Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification Yanna Jiang∗

Mingyuan Li∗

University of Technology Sydney Australia

ELLIS Institute Finland University of Turku Finland

Xu Wang

Guangsheng Yu†

University of Technology Sydney Australia

University of Technology Sydney Australia

Abstract Large language models (LLMs) increasingly decide whether Web evidence supports online claims, often by voting over several assessors whose errors are presumed independent and benign. On the open Web, retrieved pages can steer the assessors that read them, and assessors from one model family fail together. We prove that even for independent assessors whose every output sequence is possible on both valid and invalid claims, any protocol that decides only from their outputs and always reaches an agreed verdict never rejects invalid claims or rejects valid ones with positive probability. We present Astral, which pins all assessors to one committed snapshot of the Web evidence. With up to 𝑓 assessors faulty, Astral accepts a verdict only when 2𝑓 +1 assessors attest to it above a confidence threshold and no signed challenge stands. On five public benchmarks with two of seven assessors adversarial, Astral lowers pooled attack success to 21.5–53.1%, against 54.7–77.8% for majority voting. The cost is coverage, as without attack 16.0–61.7% of claims receive a binary verdict and the rest are disputed for audit. Our code runs at https://anonymous.4open.science/r/Astral-55F1.

CCS Concepts • Information systems → World Wide Web; • Computing methodologies → Natural language processing.

Keywords Web information integrity, LLM assessors, fact verification, semantic consensus, Byzantine fault tolerance, accountability

1

Introduction

Large language models (LLMs) mediate much of what Web users read about online claims, and LLM verdicts reach users with the authority of the services that display them. Search engines answer queries with generated summaries of retrieved pages, and LLMs are proposed and deployed as fact-checking assistants that flag or annotate misleading claims [1, 8]. In each pipeline, an LLM decides whether the evidence it retrieved supports a Web claim. LLMs also judge other systems’ outputs, and agreement with human assessors is the main evidence that LLMs are valid judges [39]. Because these ∗ Yanna Jiang and Mingyuan Li contributed equally to this work. † Corresponding author.

WWW ’27, Dublin, Ireland 2027.

AI systems help establish trust on the Web, we ask how to make them trustworthy. The work fits the Responsible Web track by addressing Web information integrity and accountability for AI systems that assess Web content. Problem Deployments use several LLM assessors to avoid a single point of failure and aggregate their verdicts by majority vote or confidence-weighted refinement [15, 38]. Aggregation helps only when assessor errors are independent and benign, and the open Web violates both conditions. Retrieval exposes assessors to content written to mislead them, including indirect prompt injection in Web pages [18]. Assessors from one model family share failure modes and misjudge the same claims. Some assessors may also be operated by parties with a stake in the verdict. Label aggregation then turns the errors of a minority into an authoritative Web decision. With two of seven assessors adversarial, confidence-weighted aggregation accepts 20–36% of refuted synthetic multi-source claims because one assessor claiming high confidence shifts the others to its label (§4.3). Why stronger voting fails Stronger voting rules do not remove this weakness. Consider any protocol that decides claims only from assessors’ outputs and always reaches an agreed verdict. When independent assessors can produce every output sequence on both valid and invalid claims, such a protocol provably rejects valid claims with positive probability or rejects no invalid claim (Proposition 2.1). For majority voting, this probability grows with each assessor’s error rate. The proposition also binds the quorum of Astral. Trust in AI-mediated Web verification therefore requires bounded residual risk and the ability to contest a verdict. We study this requirement through three research questions. • RQ1. How reliably do aggregation rules decide Web claims when heterogeneous assessors disagree benignly? • RQ2. How fast does verification integrity degrade when a minority of assessors fail systematically or act adversarially? • RQ3. Is semantic consensus a usable integrity primitive for AImediated Web verification, and what does it cost? Semantic consensus certifies a verdict only when assessors independently attest it using the same snapshot of evidence and the verdict remains open to challenge. Approach We propose Astral (Accountable Semantic Triage, Reasoning Attestation & Liveness), a semantic consensus layer that treats each AI verdict on a Web claim as a protocol object with a lifecycle (Figure 1). An ordering layer (L1) fixes the verdict proposal. Because Web pages change, assessors would see different evidence

WWW ’27, May 10–14, 2027, Dublin, Ireland

if they retrieved pages at different times. An evidence layer (L2) therefore requires every assessor to evaluate the same committed snapshot of retrieved Web evidence. With up to 𝑓 assessors Byzantine, a semantic layer (L3) collects 2𝑓 +1 attestations that pass a confidence threshold and opens a window in which any assessor can file a signed challenge. A platform may act on the ordered verdict immediately, and Astral upgrades it to accountable acceptance only after attestation succeeds and no challenge stands. Contested verdicts are marked as disputed and are left unresolved by vote. Contributions We make four contributions. • Assessor failure in Web verification. We identify failures by assessors as a weakness of AI-mediated Web verification and prove that when the output sequences of independent assessors never separate valid from invalid claims, a protocol that rejects invalid claims also rejects valid ones with positive probability (§2). • Accountable semantic consensus. Astral commits a snapshot of Web evidence, counts attestations that pass a confidence threshold, and keeps verdicts challengeable. We bound residual false acceptance by assessor error, error correlation, and challenge success (§3). • Robustness on Web claims. We evaluate seven open-weight assessors on five public benchmarks. With two adversarial assessors, Astral lowers pooled attack success over four attacks to 21.5– 53.1%, against 54.7–77.8% for majority voting and 70.8–85.2% for confidence-weighted aggregation. Without attack it returns binary verdicts on 16.0–61.7% of claims, certifies 6.8–30.3% with a StableQC, and sends the rest to DISPUTED for audit (§4). • Assessor diversity. We observed joint false acceptances in a committee from one model family but none in committees spanning three or more families. On the public benchmarks, single-model committees range from 1.4–8.0% to 57.5–90.1% pooled attack success depending on the backend. We therefore identify diversity as a hedge against a weak backend, which does not guarantee lower risk than the strongest single model.

2 AI-Mediated Web Verification 2.1 Setting A Web verification task 𝐷 pairs a Web claim with pointers to evidence retrieved for it, such as news articles, encyclopedia entries, or vulnerability records. A committee of 𝑛 LLM assessors 𝑝 1, . . . , 𝑝𝑛 , each identified by a public key, decides 𝐷. Each 𝑝𝑖 queries its LLM backend, stochastic oracle 𝑂𝑖 , to run 𝑉infer (𝐷), which stochastically estimates the inference policy. The check returns a label in {SUPPORT, REJECT}, a confidence in [0, 1], and a pointer to the evidence used. Retrieved evidence is written to an append-only, content-addressed store AFS, whose Merkle root is committed with the proposal for 𝐷. Every assessor therefore evaluates the same snapshot even when live pages change or disappear after retrieval. A claim is semantically valid when the committed policy assigns the claim confidence at or above the acceptance threshold using this snapshot. Membership is static, and up to 𝑓 assessors may be Byzantine (arbitrarily faulty), with 𝑛 ≥ 3𝑓 +1. The network is partially synchronous. After an unknown global stabilization time (GST), messages arrive within the known bound Δ (Assumption 1). An ordering protocol can provide the ordering layer if it exposes an externalvalidity hook [5, 6, 37] and meets the assumptions of Appendix B.

Yanna Jiang, Mingyuan Li, Xu Wang, and Guangsheng Yu

CommitQC lets the platform act on an ordered verdict immediately, and StableQC later certifies accountable acceptance (§3).

2.2

How Assessors Fail on the Web

Each of four failure sources in Web verification maps to a quantity controlled by the protocol or its analysis. An honest assessor makes a model error by hallucinating or misreading. Model error contributes to each assessor’s false-accept rate 𝜖, which we measure as 𝜖ˆ(𝜏) at confidence threshold 𝜏 (§3.3). Content-induced error arises when a retrieved page is written to mislead, for instance through an injected instruction or fabricated corroboration [18]. Such a page raises the false-accept rate of every assessor that reads it to some 𝜖 ′ ≥ 𝜖. Correlated error arises when assessors share a model family or read the same misleading page and therefore misjudge the same claims. We account for correlated error with the correlation factor 𝜌𝑘ℎ (Equation (4)), which is at most 1 when assessor errors are independent and grows as assessors share failures. Adversarial assessors are operated by a party with a stake in the verdict or steered into arbitrary behavior by content. Up to 𝑓 such assessors may collude, suppress evidence, equivocate selectively, or otherwise behave arbitrarily. We design the quorum, certificate, and challenge rules of Astral for this fault model. Content that steers more than 𝑓 assessors to the same wrong label lies outside any quorum guarantee. In the analysis this case appears as 𝜖 ′ close to 1 and 𝜌𝑘ℎ ≫ 1. The residual-risk estimate then degrades without overstating protection. We confine all four failure sources to LLM outputs through the following rule. Invariant 1 (Deterministic Wrapper). Protocol state transitions never invoke an LLM. All consensus messages (VOTE, NO_ CHALLENGE, CWIT, and the like) are generated by deterministic code from verified local state. LLM inference is invoked only to generate proposal content, to produce SEM_PASS attestations via 𝑉infer , and to produce COUNTER_SUSTAIN or semantic COUNTER_REJECT votes during counter triage. An honest assessor misled by content can therefore produce wrong labels only in these three message types, and it cannot cause equivocation, invalid votes, or inconsistent protocol transitions. A Byzantine assessor need not run the wrapper.

2.3

Agreement Is Not Validity

Adding assessors cannot by itself make a Web verdict valid. Proposition 2.1 (False Rejection under Shared Support). Let a protocol Π read the input 𝐷 only through outputs of independent stochastic oracles 𝑂𝑖 in a common finite set, with queries, stopping, and verdict that depend only on earlier outputs and on coins independent of 𝐷 and of the oracles. Assume shared support, meaning that for every coin value and after every reachable history each next output has positive probability on every semantically non-trivial input. Let Π achieve agreement, terminate with probability 1, and reject with positive probability some input in its rejection coverage 𝐹 inv , the set of non-trivial invalid inputs it can reject. Then Π falsely rejects every non-trivial valid input 𝐷 ′ with probability 𝑃err (Π, 𝐷 ′ ) > 0.

(1)

Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification

WWW ’27, May 10–14, 2027, Dublin, Ireland

Inputs Web claim v

ASTRAL L1: Ordering

Votes: 2f+1

Leader proposes verdict

Vote

Ordered verdict

CommitQC Platform acts now (tentative)

Retrieved Web evidence E(v)

L2: Evidence Pinning

ACKs: 2f+1

Vstruct: pointers resolve

DA_ACK

Pinned Web evidence snapshot

DAQC

Web pages / news Encyclopedia entries

Web API records URL, timestamp, version

L3: Semantic Stabilization

concurrent

Phase 1: Attestation

Phase 2: Challenge ...

COUNTER filed (cites evidence)

LLM assessors Byzantine

Vinfer

Vinfer

Vinfer

...

Vinfer

Filter: conf≥ τ

Parameters

SemQC

SEM_PASS

(signed attestation)

PASS: 2f+1

VerifyCounterStruct CWIT (witness) → CounterQC

CRQC (counter dismissed) unblocks NCC

n: assessors f: Byzantine bound k = 2f+1: quorum τ: confidence threshold W: challenge window

COUNTER_SUSTAIN / DISPUTED DISPUTED: flagged for human audit

Phase 3: Closure / Finality No unresolved challenge

NCC

StableQC = CommitQC ∧ SemQC ∧ NCC

Accountable acceptance Verdict carries attestation record

Figure 1: Astral as a verification layer for Web claims. L1 orders the verdict proposal and yields CommitQC, on which a platform can act immediately. L2 pins the retrieved Web evidence, because assessors sign DA_ACK only after the structural check 𝑉struct passes and DAQC certifies one committed evidence snapshot. L3 runs attestation concurrently with a challenge window. Attestation aggregates SEM_PASS messages into SemQC, and during the window assessors file and triage COUNTERs. With no unresolved challenge, NCC forms and StableQC = CommitQC ∧ SemQC ∧ NCC certifies accountable acceptance. If each of 𝑛 assessors is wrong on 𝐷 ′ independently with probability 𝑒, majority reconciliation falsely rejects 𝐷 ′ with probability Í 𝑛
𝑖 𝑛−𝑖 , which is 2.7 × 10 −3 for 𝑛 = 7 and 𝑒 = 0.1. 𝑒 (1 − 𝑒) 𝑖>𝑛/2 𝑖

Proof sketch. With positive probability over the coins, some finite output history leads Π to reject an input in 𝐹 inv . Because Π sees 𝐷 only through outputs, the same history leads to INVALID on a valid 𝐷 ′ , where shared support gives it positive probability. Appendix C.1 gives the full proof. The proposition fixes what a Web verification layer can certify. Astral certifies accountable acceptance, meaning a verdict that was independently attested on a pinned evidence snapshot, survived a challenge window, and carries a signed certificate chain recording who attested and who challenged. Its guarantees hold at three levels. Ordering agreement is inherited unconditionally from L1. Evidence consistency is deterministic, since DAQC binds every attestation to one committed snapshot that at least 𝑓 +1 honest assessors hold. Semantic acceptance is distributional, with a residual false-acceptance rate bounded by 𝛿 over the task distribution (Equation (5)).

3

The Astral Protocol

Astral handles a Web verdict in three layers with different guarantees (Fig. 1). A platform acts at CommitQC, while Astral runs L3 entirely after commitment to certify accountable acceptance (StableQC) or flag the verdict as disputed.

3.1

Ordering and Evidence Pinning

L1 provides Commit(ℎ) = valℎ , a totally ordered sequence of verdict proposals with agreement (unconditional for deterministic BFT) and post-GST liveness. An ordering protocol that exposes an external-validity predicate and meets the assumptions of Appendix B suffices, including deterministic BFT [6, 31, 37] and probabilistic chains with 𝑘-deep confirmation (Appendix D). The fault threshold 𝑛 ≥ 3𝑓 + 1 is inherited from L1. Ordering treats the proposal as opaque bytes and says nothing about whether the claim is supported. Each proposal carries a decision object 𝐷 = (claim, evid_pointers, lineage_pointers, policy_hash, afs_root, 𝐻 ctx ),

(2)

which binds a Web claim to pointers into the committed evidence store, the hash of an inference policy 𝜋, and a context hash 𝐻 ctx . The policy assigns confidence to a claim given evidence. A claim is semantically valid under 𝜋 when 𝜋 (𝐸, claim) ≥ 𝜏 for the committed evidence 𝐸. Each assessor’s 𝑉infer estimates 𝜋 stochastically (Appendix B.2). Honest assessors can therefore disagree on claims whose confidence lies near 𝜏. Evidence pinning (L2). Web pages change, so retrieving at different times would give assessors different evidence and make their attestations incomparable. After CommitQC, the leader broadcasts the pre-block 𝑃 and referenced artifacts. 𝑃 carries the committed value with afs_root, the evidence pointers, and 𝐻 ctx . Each assessor runs the deterministic admission check 𝑉struct to verify that every

WWW ’27, May 10–14, 2027, Dublin, Ireland

evidence pointer resolves against afs_root and that the policy hash is valid. The check verifies that 𝐻 ctx is consistent with the pointers and that recorded tool outputs match their hashes. An assessor whose check passes signs DA_ACK(DS, 𝐻 (𝑃), afs_root), and 2𝑓 +1 signatures form DAQC. As with the certificates of availability in Narwhal [14], 2𝑓 +1 signatures guarantee that at least 𝑓 +1 honest assessors hold the evidence. L3 begins only after DAQC, so every honest assessor evaluates the snapshot fixed by the committed Merkle root. All honest assessors agree on the outcome of 𝑉struct because it is deterministic. The check is purely restrictive, so it cannot introduce an L1 safety violation. A failed check makes the committed block a no-op for L2 and L3. Unavailable evidence stalls DAQC, which costs liveness but never safety.

3.2

Semantic Stabilization

L3 moves a committed verdict from tentative agreement (CommitQC) to accountable acceptance (StableQC). Attestation 1 and the challenge window (Phase ○) 2 run concurrently (Phase ○) 3 follows the window. after DAQC, and closure (Phase ○) 1 attestation. Each assessor runs 𝑉infer (𝐷) on the pinned Phase ○: snapshot. An assessor that obtains SUPPORT with confidence at least 𝜏 signs a SEM_PASS attestation, and 𝑘 = 2𝑓 +1 attestations from distinct assessors form SemQC. We count attestations whose confidence meets 𝜏 equally because weighting by confidence can let a single Byzantine assessor reporting high confidence set the outcome (§4.3). The 2𝑓 +1 distinct attesters include at least 𝑓 +1 honest assessors (Lemma 3.2). Thus the 𝑓 Byzantine assessors cannot form SemQC alone, whatever confidence they report. Setting 𝑘 = 2𝑓 +1 maximizes how many honest assessors attest to each accepted verdict. Reducing 𝑘, down to 𝑓 +1, tolerates more false rejections by honest assessors at the cost of a weaker residual-risk bound (Appendix E.1). 2 challenge window. After CommitQC, a challenge winPhase ○: dow of duration 𝑊 (𝑣) ≥ 2Δ opens, during which any assessor can file a signed COUNTER that references evidence in AFS contradicting the claim. Because assessors admit only counters filed before 𝑊 (𝑣)−Δ, every admitted counter reaches all honest assessors before the window closes post-GST. The window adapts the fraud proofs of optimistic rollups [21, 32] to non-deterministic verification. A deterministic fraud proof re-executes a recorded tool call and can be checked by every assessor, whereas a semantic counter argues from evidence and must be triaged with 𝑉infer . Accountability is cryptographic, and no staking is involved. The window grows linearly in the view number as 𝑊0 · 𝑣, where 𝑊0 is added at each view (Algorithm 1). This linear growth guarantees coverage while the network remains unstable before GST. A lower cap on 𝑊 (𝑣) gives faster acceptance but leaves less time for honest challenges (Appendix E). A counter first passes VerifyCounterStruct, which deterministically rejects malformed and duplicate counters. Then 2𝑓 +1 witness signatures (CWIT) form a CounterQC. A valid fraud proof marks the claim refuted and blocks StableQC permanently. Each assessor triages a semantic counter with 𝑉infer and votes COUNTER_ SUSTAIN or COUNTER_REJECT. Then 2𝑓 +1 COUNTER_REJECT votes form CRQC, which dismisses the counter. If the counter is not dismissed by the triage timeout 𝑇arb , the decision becomes DISPUTED.

Yanna Jiang, Mingyuan Li, Xu Wang, and Guangsheng Yu

Table 1: Dual-finality outcomes of a Web verdict. Level

Certificate

Guarantee

Platform action

Tentative Stable Rejected Disputed

CommitQC StableQC none none

L1 agreement Accountable acceptance No quorum yet (provisional) Liveness preserved

Act immediately Upgrade confidence Withdraw action Suspend, human audit

Definition 3.1 (Counter Lifecycle). A counter for (ℎ, 𝐻 (𝑏), wid) is pending once it is structurally valid and added to unresolvedCounters. It becomes resolved when it reaches a terminal state (CRQC rejection, sustained, or disputed timeout), and it is then pruned from the Mandatory Inclusion enforcement set. Only a CRQC rejection removes it from unresolvedCounters, the authoritative blocking criterion for NCC signing. A sustained fraud proof is final for height ℎ. A disputed flag is provisional, and a StableQC formed later replaces it. A structurally valid counter enters unresolvedCounters and leaves it only at a terminal state (Definition 3.1), so its filer cannot withdraw it. Mandatory Inclusion prevents leaders from dropping certified counters because assessors deny DA_ACK to proposals that omit a known CounterQC for an unresolved counter. Unblocking NCC requires 2𝑓 +1 COUNTER_REJECT votes so that the 𝑓 Byzantine assessors alone can never dismiss a sound counter. Each Byzantine assessor can file at most one structurally valid counter per window, and triaging each counter adds at most 𝑇arb . Hence, including data availability and inference time, stabilization after CommitQC satisfies 𝑇stable ≤ 𝑇DA + 𝑇infer + 𝑊 (𝑣) + 𝑓 · 𝑇arb . (3) Beyond this bound, unresolved counters trigger DISPUTED, and the platform suspends its CommitQC action pending human audit. 3 closure. When the window closes with no unrePhase ○: solved counter, assessors sign NO_CHALLENGE. Then 2𝑓 +1 signatures form NCC, and the verdict reaches semantic finality with StableQC = CommitQC ∧ SemQC ∧ NCC. Without SemQC at closure and with no counter pending or final, the verdict is rejected provisionally until a forwarded SemQC arrives. Table 1 lists the four outcomes a platform sees.

3.3

Residual-Risk Bound

On invalid claims from a characterized distribution D of Web claims, 𝜖 bounds each honest assessor’s false-accept rate, and we estimate it by 𝜖ˆ(𝜏). With 𝐴𝑖 the event that honest assessor 𝑖 falsely accepts and 𝐻 a fixed set of 𝑛 − 𝑓 honest assessors, we define the correlation factor Ñ 𝜌𝑘ℎ := max Pr[ 𝑖 ∈𝑆 𝐴𝑖 ] /𝜖 𝑘ℎ , (4) 𝑆 ⊆𝐻, |𝑆 |=𝑘ℎ

where 𝑘ℎ := 𝑓 + 1 is the number of attesters from 𝐻 that every SemQC contains (Lemma 3.2). Lemma 3.2 (Honest Subset in SemQC). SemQC requires 𝑘 = 2𝑓 + 1 attestations from distinct assessors. Only 𝑓 assessors lie outside 𝐻 , so at least 𝑘 − 𝑓 = 𝑘ℎ attestations come from assessors in 𝐻 . An invalid claim obtains SemQC only in the event 𝑄 that at least 𝑘ℎ assessors in 𝐻 falsely accept. Because 𝑄 is the union of the joint

Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification

false-acceptance events of the 𝑛−𝑓 subsets of 𝐻 of size 𝑘ℎ , the 𝑘ℎ 𝑛−𝑓
𝑘ℎ union bound gives Pr[𝑄] ≤ 𝑘 𝜖 𝜌𝑘ℎ . A counter that is filed in ℎ time, delivered, and upheld in triage blocks accountable acceptance. With 𝑝 ch the probability of such a counter conditioned on 𝑄,
𝑘 𝛿 (𝜖, 𝑘ℎ ) ≤ 𝑛−𝑓 · 𝜖 ℎ · 𝜌𝑘ℎ · (1 − 𝑝 ch ). (5) 𝑘 ℎ

An unconditional estimate of 𝑝 ch is valid only when 𝑄 and challenge failure are close to independent, and subtle invalidity can violate that independence (Appendix B). Post-GST, CounterQC and Mandatory Inclusion deliver every filed counter. If the 𝑚 honest checkers detect independently given 𝑄 with probability 𝑝 det each, at least one of them detects with probability 1 − (1 − 𝑝 det )𝑚 , and triage must still uphold the counter. Diversity. Operators should configure a diversity predicate that requires attestations from ≥ 𝑑 distinct oracle implementations to reduce 𝜌𝑘ℎ . This predicate is an engineering recommendation (Section E.1). Because 𝜌𝑘ℎ multiplies the bound in Equation (5), correlated errors in a less diverse committee loosen 𝛿. On the multisource claims of §4.1, a fixed group drawn from a single model family has an observed ratio 𝜌ˆ𝑠 = 50 (Table 3).

3.4

Security Properties

Theorem 3.3 (Agreement Safety). No two honest assessors commit conflicting values at the same height. Theorem 3.4 (Stable Agreement). If two honest assessors independently output Certify(ℎ) for height ℎ, they output the same value. Theorem 3.5 (Astral Liveness). Assume Assumptions 5 to 10, post-GST operation, and 2𝑓 +1 SEM_PASS attestations that arrive in time. Honest assessors falsely reject at rate 𝜖fn , so for 𝑛 = 3𝑓 +1 this count holds in expectation when 𝜖fn ≤ 𝑓 /(2𝑓 +1) and all 𝑓 Byzantine assessors attest in time. Under worst-case withholding it holds with certainty only when 𝜖fn = 0. Then Commit(ℎ) is emitted within 𝑂 (𝑓 ) view-changes, as inherited from L1. Unless a valid deterministic fraud proof refutes the claim, StableQC also forms within 𝑂 (2Δ + 𝑊 (𝑣) + 𝑇DA + 𝑇infer + 𝑓 · 𝑇arb ) after CommitQC, or the decision is flagged DISPUTED. Theorem 3.6 (Eventual Counter Dissemination). Post-GST, deterministic CounterQC forwarding and Mandatory Inclusion guarantee that all honest assessors converge on the same counter set within Δ. Censoring counters delays progress by at most 𝑂 (𝑓 ) view-changes. Agreement safety is inherited from L1 because 𝑉struct filters blocks after commitment. Stable agreement follows because CommitQC, SemQC, and NCC must reference the same committed block hash 𝐻 (𝑏). Liveness follows because L1 progresses, attestation and triage take bounded time, and a timeout flags the decision DISPUTED. Appendix C proves Proposition 2.1 and sketches the proof of Theorem 3.5. The anonymous artifact repository (https://anonymous.4open.science/r/Astral-55F1) contains the full formal proofs of Theorems 3.3 to 3.6. Appendix E.1 gives pseudocode and invariants that keep L3 state out of L1 voting (Invariant 2) and give all honest assessors the same input to L3 (Invariant 3). The certificate chain also makes signature equivocation, invalid evidence pointers, CounterQC censorship, and semantic-layer equivocation provable. It further supports best-effort detection of evidence suppression.

4

WWW ’27, May 10–14, 2027, Dublin, Ireland

Evaluation

The evaluation follows the three research questions of §1. RQ1 measures how accurately each aggregation rule decides benign Web claims (§4.2). RQ2 measures how fast integrity degrades under adversarial and correlated assessors (§4.3). RQ3 measures what the challenge path, the bound, and assessor diversity contribute and what they cost (§4.4).

4.1

Setup

Public benchmarks We use fixed evaluation splits with published evidence and labels (Table 2). Table 2 lists claim counts by fixed split. Here 𝑁 counts the claims in each fixed split and does not count protocol trials. AVeriTeC and FEVER cover general fact-checking, Climate-FEVER covers climate, PUBHEALTH covers public health, and SciFact pairs scientific claims with abstracts. We replay each claim with its released evidence and ground-truth label. No benchmark claim, evidence item, or label is generated or rewritten by an LLM. Synthetic and live cohorts We use two additional cohorts to test controlled mechanisms and mutable evidence. Multi-source fact verification (MFV) uses 100 synthetic claims over five topics, half supported and half refuted. Each claim’s difficulty is set by consistency among its three to five evidence excerpts. The live cohort uses evidence from the NVD Web API for 80 vulnerability claims, 40 about real CRITICAL-severity CVEs and 40 about fabricated ones. Two non-Web domains (code patching and log auditing) appear in Appendix F.1. Assessors and harness We form committees of 𝑛 ∈ {7, 13, 31, 67, 100} assessors from seven model families, using four families at 𝑛=7 (Appendix F.1). We set 𝑓 = ⌊(𝑛 − 1)/3⌋. For 𝑛 ≥ 31 the committee cycles over the seven families, so the number of independent sources stays at seven. The public-benchmark runs use a separate 𝑛=7 committee of seven open-weight models (Table 2), namely Qwen2.5-1.5B and Qwen2.5-3B, SmolLM2-1.7B, OLMo-21B, TinyLlama-1.1B, StableLM-2-1.6B, and Phi-3.5-mini at pinned revisions, decoding greedily with at most 128 new tokens. We use 𝑘 = 2𝑓 +1, 𝜏 = 0.7, and seed 42. In the synthetic and non-Web runs, API models decode greedily and local models use temperature 0.01. Each assessor’s response is cached once per claim and reused across protocols. L2 and L3 are simulated in logical rounds on top of a deterministic L1 stub after GST, so Δ, 𝑊 (𝑣), 𝑇infer , 𝑇DA , and 𝑇arb take no wall-clock values. The challenge window lasts one round. During this window, every honest assessor whose 𝑉infer label is REJECT attempts to file one counter. A counter enters triage only if it passes VerifyCounterStruct. The 𝑚 checkers of §3.3 are therefore the honest assessors (𝑛−𝑓 in attack trials and 1 label all 𝑛 in benign trials), and we use each checker’s Phase ○ as its detection outcome. Each assessor casts one triage vote, and a counter with fewer than 2𝑓 +1 COUNTER_REJECT votes sends the decision to DISPUTED. This triage rule replaces the 𝑇arb fallback in the simulation. We select members to obtain diversity and leave the diversity predicate unchecked at attestation time. Adversarial assessors In attack trials, 𝑓 assessors are Byzantine and attest with confidence 0.95. Prompt or tool injection (A1) [18]

WWW ’27, May 10–14, 2027, Dublin, Ireland ASTRAL w/o Challenge

Yanna Jiang, Mingyuan Li, Xu Wang, and Guangsheng Yu

MV CP-WBFT

Simple-Thr. Single-model (avg.)

100

75

75

Pooled ASR (%)

100

50 25

Clean

PH

25

AV

0

Method

0 0

25

50

75

100

(a) Coverage without attack (%)

AV

CF

FE

PH

SF

(b) Pooled ASR per benchmark

Figure 2: Pooled ASR under A1–A4 on the public benchmarks of Table 2 (AV = AVeriTeC, CF = Climate-FEVER, FE = FEVER, PH = PUBHEALTH, SF = SciFact). (a) Coverage without attack against pooled ASR, with arrows from Astral-NoCh to Astral. (b) Pooled ASR with Clopper–Pearson 95% CIs, omitting Single-model and L1-BFT.

embeds an instruction that asks for a SUPPORT verdict in the evidence that every assessor reads, and the Byzantine assessors attest the wrong verdict. In a fabricated proposal (A2), a Byzantine leader proposes a plausible false verdict. In evidence truncation (A3), the last 30% of the evidence is removed for every assessor, and the Byzantine assessors endorse the incomplete decision object. For model-aware corruption (A4), the evidence carries the A1 injection, and we corrupt the 𝑓 assessors that reject most reliably and leave the weakest models honest. In counter-spam (A5), each Byzantine assessor files one structurally valid but vacuous counter per window. Baselines and metrics We compare against majority voting (MV) over the assessors’ labels and against CP-WBFT [38], which probes confidence and refines labels with confidence-weighted aggregation. L1-BFT, which orders verdicts without semantic checks, and an oracle with a perfect 𝑉infer bound the range. Astral-NoCh drops the challenge window, Astral-NoDiv uses one backend for all assessors, and Simple Threshold accepts on one assessor’s confidence. In Table 2, “Single-model (avg.)” averages seven independent runs that each use one backend. “w/o Challenge” is Astral-NoCh, and “Simple-Thr.” is the single-assessor threshold baseline. For Table 2, the semantic correctness success rate (SCSR) is the fraction of benign trials whose final binary decision matches the ground-truth label. Coverage (Cov.) is the fraction of benign trials that end in a binary ACCEPT or REJECT instead of DISPUTED. Both SCSR and Cov. use all benign trials as the denominator. A DISPUTED outcome is not a binary decision, so it never counts as correct, and SCSR never exceeds Cov. Each A1–A4 column reports the attack success rate (ASR), counting a refuted claim as an attack success only when the final output is ACCEPT. A DISPUTED outcome lowers coverage and suspends any action taken at CommitQC. The pooled ASR aggregates accepted refuted claims over all four attacks, and Disp. is the fraction of attacked trials that end in DISPUTED.

4.2

Table 2: Main results on five public benchmarks using seven open-weight assessors. 𝑁 is the claim count in the fixed evaluation split. SCSR and Cov. are clean metrics, A1–A4 are attack success rates, and pooled ASR aggregates the four attacks.

50

SF CF FE

L1-BFT

RQ1: Reliability under Benign Disagreement

Without adversaries, label aggregation always reaches a binary verdict on the five public benchmarks, while Astral reaches one on 16.0–61.7% of claims and leaves the remaining 38.3–84.0% DISPUTED

Byzantine attacks (%)

SCSR↑ Cov.↑ A1↓ A2↓ A3↓ A4↓

ASR↓ Disp.†

AVeriTeC (𝑁 = 500) 100.0 100.0 100.0 100.0 100.0 100.0 [99.8,100.0] 100.0 96.6 17.5 26.7 100.0 60.2 [57.7,62.7] 100.0 97.6 50.3 51.9 100.0 74.9 [72.7,77.1] 100.0 73.0 40.5 45.0 85.4 61.0 [58.5,63.4]

L1-BFT MV CP-WBFT Simple-Thr.

24.4 88.2 50.6 75.6

Single-model (avg.) w/o Challenge ASTRAL

56.1 76.1 57.1 86.0 100.0 64.6 14.0 16.0 27.2

L1-BFT MV CP-WBFT Simple-Thr.

42.6 70.4 46.3 61.8

Single-model (avg.) w/o Challenge ASTRAL

54.0 87.4 68.5 29.0 29.6 68.5 67.9 100.0 84.3 14.9 14.8 100.0 26.2 37.5 61.1 11.4 11.7 87.9

L1-BFT MV CP-WBFT Simple-Thr.

29.1 83.0 44.3 67.5

Single-model (avg.) w/o Challenge ASTRAL

50.2 80.7 66.3 33.3 29.5 66.3 84.5 100.0 83.1 20.6 15.1 100.0 27.5 33.3 53.4 15.0 12.4 67.2

L1-BFT MV CP-WBFT Simple-Thr.

51.6 62.8 72.6 62.5

Single-model (avg.) w/o Challenge ASTRAL

57.2 90.6 57.9 55.5 100.0 66.5 29.6 55.9 45.7

L1-BFT MV CP-WBFT Simple-Thr.

41.3 63.7 42.0 60.7

15.8 3.4 1.6

20.4 57.1 9.5 99.7 6.1 51.1

0.0 0.0 0.0 0.0

37.6 44.3 [41.8,46.9] 21.5 [19.4,23.7]

17.3 0.0 50.5

Climate-FEVER (𝑁 = 1,535) 100.0 100.0 100.0 100.0 100.0 100.0 [99.9,100.0] 100.0 99.3 42.3 45.1 100.0 71.7 [70.2,73.2] 100.0 99.3 67.4 74.2 100.0 85.2 [84.0,86.4] 100.0 77.8 52.9 47.3 90.8 67.2 [65.6,68.7]

0.0 0.0 0.0 0.0

48.9 53.5 [51.8,55.1] 43.0 [41.3,44.6]

9.6 0.0 26.7

FEVER (𝑁 = 15,935) 100.0 100.0 100.0 100.0 100.0 100.0 [100.0,100.0] 100.0 99.5 54.0 47.6 100.0 75.3 [74.9,75.7] 100.0 99.7 66.5 57.8 100.0 81.0 [80.6,81.3] 100.0 75.7 52.3 49.6 91.3 67.2 [66.8,67.6]

0.0 0.0 0.0 0.0

48.9 54.7 [54.2,55.2] 37.0 [36.6,37.4]

14.0 0.0 31.9

PUBHEALTH (𝑁 = 1,220) 100.0 100.0 100.0 100.0 100.0 100.0 [99.8,100.0] 100.0 97.0 7.8 14.2 100.0 54.7 [52.7,56.8] 100.0 96.4 35.5 51.3 100.0 70.8 [68.9,72.6] 100.0 70.9 30.8 43.5 83.1 57.1 [55.0,59.1]

0.0 0.0 0.0 0.0

8.0 2.4 2.4

12.9 57.9 4.1 100.0 3.7 92.6

34.2 43.2 [41.2,45.3] 36.1 [34.1,38.1]

5.9 0.0 16.8

SciFact (𝑁 = 300) 100.0 100.0 100.0 100.0 100.0 100.0 [99.5,100.0] 100.0 99.4 71.0 40.9 100.0 77.8 [74.6,80.9] 100.0 97.2 86.9 56.8 100.0 85.2 [82.4,87.8] 100.0 82.4 59.1 50.6 94.3 71.6 [68.1,74.9]

0.0 0.0 0.0 0.0

Single-model (avg.) 53.1 93.0 72.5 45.7 27.8 72.5 54.6 7.5 w/o Challenge 70.0 100.0 90.9 41.5 11.4 100.0 60.9 [57.2,64.6] 0.0 ASTRAL 43.0 61.7 72.2 36.4 10.2 93.8 53.1 [49.4,56.9] 16.5 All metrics in %. ↑/↓ mark the better direction, and bold marks the best value within each dataset (ties included). † Disp. is the disputed-output rate and has no preferred direction. Brackets give Clopper–Pearson 95% CIs for the pooled ASR, whose bounds lie within 1.2 points of claim-clustered bootstrap CIs. Single-model (avg.) averages seven single-backend runs without CI, pooled ASR ranges from 1.4–8.0% for the best backend to 57.5–90.1% for the worst, and A4 equals A1 because one backend leaves no assessor to select.

(Table 2 and Figure 2a). Only 6.8–30.3% of claims reach accountable acceptance with a StableQC, and the other binary verdicts are rejections without SemQC. The whole loss comes from the challenge window. Astral-NoCh uses the same 2𝑓 +1 quorum without a window, never outputs DISPUTED, and decides every claim. Because disputed claims never count as correct, Astral’s SCSR is 20.7–74.2 points below MV’s on all five benchmarks. On decided claims, Astral is correct 52.9–87.5% of the time, against 62.8–88.2% for MV. On the synthetic suite, Astral’s SCSR falls from 43.3% at 𝑛=7 to 32.9% at 𝑛 ≥ 13, with coverage of 43.8% and 33.3%, while MV and CP-WBFT decide every claim with SCSR of 93.8% and 94.3% (Appendix F.1).

Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification

MV

ASR (%)

40

CP-WBFT 40

20

20

ASTRAL

Table 3: Assessor correlation on MFV (𝜏=0.7) over 50 trials for one fixed group of 𝑠 honest assessors per configuration, with group-mean false-accept rate 𝜖¯ and observed ratio 𝜌ˆ𝑠 . 𝑠 grows with the family count, and – marks no joint false acceptance. Diversity configuration

0

0 A1

A2

A3

A4

(a) Attack at n = 7

7

13

31

67

Same model family Mixed 2 families Mixed 3 families Full diversity (4+)

100

(b) Committee size n under A4

Figure 3: Attack success rate on MFV multi-source claims over 50 refuted claims per point (4% has 95% CI [0.5, 13.7]). (a) Each attack at 𝑛=7. (b) A4 across committee size 𝑛.

Takeaway. Under benign disagreement, Astral withholds a binary verdict on 38.3–84.0% of public-benchmark claims, and the challenge window accounts for all of that loss because the 2𝑓 +1 quorum alone decides every claim.

4.3

WWW ’27, May 10–14, 2027, Dublin, Ireland

RQ2: Robustness to Adversarial Assessors

Adversarial assessors With two of seven assessors adversarial, Astral has the lowest pooled ASR among the aggregation protocols on every public benchmark. Its pooled ASR is 21.5–53.1% against 54.7–77.8% for MV and 70.8–85.2% for CP-WBFT (Table 2 and Figure 2b). L1-BFT accepts every refuted claim, which shows that ordering without a semantic check offers no protection. At the same confidence threshold, Simple Threshold reaches 57.1–71.6% pooled ASR. With the 2𝑓 +1 quorum, Astral-NoCh lowers pooled ASR by 10.7–16.7 points relative to Simple Threshold. Adding the challenge window lowers it a further 7.1–22.8 points and attaches a signed record to every decision (Figure 2a). At Astral’s benign coverage, MV that abstains below a confidence threshold still accepts 54.7–77.7% of refuted claims, so abstention alone does not explain Astral’s lower ASR (Table 5). Model-aware corruption (A4) remains the strongest attack, as Astral accepts 51.1–93.8% of refuted claims under A4. On PUBHEALTH, the average single-backend run reaches a pooled ASR of 34.2%, 1.9 points below Astral. CP-WBFT is weakest where one confident assessor can move the others. On MFV at 𝑛=7, CP-WBFT accepts 20–36% of refuted claims because one assessor reporting confidence 0.95 can shift honest assessors to that assessor’s label during refinement (Figure 3a). Astral’s attack success on MFV is 2–4%. Correlated assessors Growing the committee by replicating the same seven families adds assessors whose errors coincide. As 𝑛 grows under model-aware corruption, attack success on MFV rises from 6% to 10% for MV and from 28% to 36–38% for CP-WBFT, while Astral stays at 0–4% (Figure 3b). In log auditing, the same replication raises MV’s attack success to 88% at 𝑛 ≥ 13 (Appendix F.1). Live Web evidence On the 80 live vulnerability claims at 𝑛=7, Astral supports 39 of 40 real CVEs (97.5%, 95% CI [86.8, 99.9]) and rejects all 40 fabricated ones, both without attack and under A1. When one assessor is degraded to reject conservatively, the protocol supports 38 of 40 real CVEs without attack and 39 of 40 under A1, and still accepts no fabricated CVE.

𝑠

Pr[∩𝐴𝑖 ]

𝜖¯𝑠

𝜌ˆ𝑠

2 2 3 4

2.0 × 10−2

4.0 × 10 −4 9.0 × 10 −4 3.7 × 10 −5 1.5 × 10 −6

50.0 22.2 – –

2.0 × 10−2 0 0

Takeaway. When a minority of assessors is adversarial or correlated, label aggregation turns their errors into accepted Web verdicts, while Astral lowers pooled attack success by 18.6–38.7 points relative to MV on public benchmarks and keeps it at 0–4% on multi-source claims.

4.4

RQ3: Accountability, Diversity, and Cost

Diversity and the bound On MFV, groups that span more model families show fewer joint false acceptances (Table 3). A committee from one model family produced one joint false acceptance in 50 trials. The observed ratio 𝜌ˆ𝑠 = 50 has a wide interval because it rests on that single event. Two families also produced one joint false acceptance (𝜌ˆ𝑠 = 22.2), and three or more families produced none (one-sided 95% upper bound 0.06 on the joint false-acceptance rate). These joint false-acceptance rates exclude the challenge factor of Equation (5). Appendix F.1 reports the unconditional rate at which counters are filed under attack, which is only the first stage of 𝑝 ch , whereas the bound conditions 𝑝 ch on 𝑄. The conditional probability can be lower, so we do not evaluate the bound end to end. In the MFV ablation under A2, attestation alone lowers attack success from 100% to 6%, and adding the challenge window lowers it to 2% (Appendix F.1). Astral-NoDiv reaches 2.0–4.0% depending on the backend (3.5% on average), and its single-family ratio of 50 indicates strongly correlated errors. Simple Threshold, which faces the same Byzantine assessors, accepts 40.0% of refuted MFV claims under A2. On the public benchmarks, diversity hedges against a weak backend but does not beat the strongest one. Single-backend committees reach 1.4–8.0% pooled ASR with the best model and 57.5–90.1% with the worst, against 21.5–53.1% for Astral’s mixed committee (Table 2). Accountability The challenge path records who disagrees instead of returning a label without an attributable record. At 𝑛=7 under attacks A1–A4, counters are filed in 56.7–59.0% of trials, CRQC resolution occurs in 5.0–8.9%, and 53.8–55.7% of decisions end as DISPUTED. Pooled over the synthetic domains, the filing rate is 58.3% at 𝑛=7 and 67.0% at 𝑛=31 (Table 6). Cost and liveness Astral spends tokens and liveness to keep false acceptance low. On the code-patching domain at 𝑛=7, a decision costs 8.1K tokens under MV, 16.4K under CP-WBFT, and 12.0K under Astral (Table 6). At 𝑛=31 the costs are 36.9K, 180.0K, and 172.7K. On the same domain with 31 assessors, MV’s attack success under A4 is 46.7% against 0% for Astral. Under counter-spam (A5), varying each Byzantine assessor’s counter budget 𝐾 over 0, 1, and 𝑓 (with 𝐾 >1 lifting the one-counter limit) yields 2.7–6.7 counters per

WWW ’27, May 10–14, 2027, Dublin, Ireland

Yanna Jiang, Mingyuan Li, Xu Wang, and Guangsheng Yu

Table 4: Decision-integrity approaches compared, with measured results from Table 2, Figure 3, and Table 6. Decision guarantees

Accountability

Measured (%, tokens)

Ordering Cert. Semantic Evidence Network Challenge Counter Dist. agreement finality attestation provenance forensics mechanism triage bounds

System

Paradigm

L1-BFT [5, 6, 37] Accountable BFT [11] Optimistic rollups [21, 32]

BFT BFT Fraud proof

✓ ✓ ✓

✓ ✓ ✓

✗ ✗ ✗

Single-model (avg.) Simple Threshold Majority vote [20, 29] Debate [15] CP-WBFT [38]

Single Threshold Vote Debate Conf.-weighted

✗ ✗ ✗ ✗ ✓

✗ ✗ ✗ ✗ ✗

Astral-NoCh Astral

Sem. consensus Sem. consensus

✓ ✓

✓ ✓

Clean SCSR↑

Cov. w/o attack↑

Pooled ASR↓

MFV A4 Tokens/ Capab. ASR↓ decision coverage

✗ ✗

✗ ✓

∼

✗ ✗ ✓

✗ ✗ ✗

✗ ✗ ✗

24.4–51.6 – –

100.0 – –

100.0 – –

– – –

– – –

2/8 3/8 3+2/8

✗ ✗

∼ ∼ ∼

✗ ✗ ✗ ✗ ✗

✗ ✗ ✗ ✗ ✗

✗ ✗ ✗ ✗ ✗

✗ ✗ ✗ ✗ ✗

✗ ✗ ✗ ✗ ✗

50.2–57.2 60.7–75.6 62.8–88.2 – 42.0–72.6

76.1–93.0 100.0 100.0 – 100.0

34.2–54.6 57.1–71.6 54.7–77.8 – 70.8–85.2

– – 6.0 – 28.0

– – 8.1K – 16.4K

0/8 0/8 0+1/8 0+1/8 1+1/8

✓ ✓

✓ ✓

✓ ✓

✗ ✓

✗ ✓

∼ ∼

55.5–86.0 14.0–43.0

100.0 16.0–61.7

43.2–60.9 21.5–53.1

– 4.0

– 12.0K

5+1/8 7+1/8

∼

✓ = supported, ∼ = partial, ✗ = not addressed, – = not evaluated. Coverage counts full+partial of eight. Rollups resolve challenges by deterministic re-execution, and fraud proofs convict a wrong state root. Ranges span five public benchmarks with two of seven assessors adversarial. MFV A4 ASR and tokens (code patching) are at 𝑛=7. Astral’s bound is not evaluated end to end.

trial at 𝑛=7 and 11.4–111.4 at 𝑛=31. For every 𝐾, 55.2% and 63.3% of decisions end as DISPUTED, with 2.2 and 7.7 sustained counters per trial, respectively. Byzantine assessors voting COUNTER_SUSTAIN during triage are therefore the bottleneck, and mitigations such as weighting votes or relaxing CRQC thresholds should target these votes. Counter-spam costs liveness, and a decision it pushes to DISPUTED carries no StableQC. Of the attacked synthetic trials, which mix supported and refuted claims, 43.9% reach stable finality at 𝑛=7 and 54.6% are flagged for audit. Takeaway. Astral fails conservatively. Groups of three or more families had no joint false acceptance on multi-source claims, diversity hedges against a weak backend, and under attack Astral flags more verdicts as DISPUTED. L1 composition Astral applies to an L1 that provides agreement, total ordering, and an external-validity predicate, including DAG-based protocols in which evidence binds to vertex hashes. For probabilistic L1s with 𝑘-deep confirmation, 𝛿 joint ≤ 𝛿 L3 + 𝑝 rev , and in simulated L1 reversion the joint-failure rates track this bound, at 0.71% vs. 0.72% for 𝑝 rev =10−4 and 5.5% vs. 5.7% for 𝑝 rev =0.05. Limitations MFV is synthetic, and the five public benchmarks are static corpora. The live CVE cohort of 80 claims is the only evaluation with mutable Web evidence and evaluates Astral without baselines. The bound is distributional and gives no guarantee against adaptive adversaries who model every assessor. Membership is static. In A1–A4, attack payloads are structural and are not optimized against specific assessors. In A1 and A4 honest assessors also read the injected evidence and do not count toward 𝑓 . Content that steers more than 𝑓 assessors to the same wrong label lies outside the quorum guarantee and appears only through 𝜖 and 𝜌𝑘ℎ (§2.2). Astral bounds risk conditional on the committed evidence, so evidence that retrieval never collected is beyond its scope. The evaluated Byzantine assessors withhold neither DA_ACK nor SEM_ PASS, which leaves the withholding case of Theorem 3.5 untested. Latency is measured only in logical rounds. Assessor diversity is selfdeclared in our setting. Such tags can be spoofed, and models from the same family may share failure modes. Periodic known-answer probes can test behavioral diversity, high-stakes deployments can use trusted hardware to attest the served model, and the correlation term can be calibrated for each deployment (Table 3).

5

Related Work

Web information integrity and fact-checking Benchmarks such as FEVER [33] and SciFact [35] pair claims with retrieved evidence to evaluate automated fact verification on the Web. LLMs generate fluent misinformation at scale and are also adopted as assistants that detect and annotate it [1, 8]. Work in this line evaluates or improves individual verifiers, and systems such as ProveRAG [17] use retrieval to reduce hallucination within one agent. A single-agent verifier can supply an assessor’s 𝑉infer in an Astral quorum. Astral addresses how verdicts from several such verifiers are combined into one Web decision. LLMs as assessors and their aggregation LLM judges are validated mainly by agreement with human assessors [39]. Multi-agent systems [19, 28, 36] resolve disagreement among LLM assessors by voting [20, 29] or debate [15]. Voting and debate assume benign assessors. Sycophancy makes agents defer to perceived authority [30], fixed personas reduce epistemic diversity [3], and indirect prompt injection lets retrieved Web content steer an assessor [18]. As a result, one compromised or confident assessor can propagate a wrong verdict through the group. CP-WBFT [38] examines reliability in multi-agent systems from a Byzantine perspective by probing confidence and weighting verdicts during aggregation. Our evaluation shows that one confident assessor can exploit how CP-WBFT weights verdicts by confidence (§4.3). Accountable agreement and challenge-based finality Classical Byzantine fault-tolerant (BFT) protocols [6, 16, 22, 37] and their successors [10, 11, 13, 23] agree on bytes and attribute networklevel equivocation. A signed proposal that contains a false claim still passes all of their checks. Blockchain oracles [4, 26] aggregate independent data feeds without a challenge path, and prediction markets [27] rely on economic incentives over long horizons. Optimistic rollups [21, 32] use challenges against deterministic execution to reach finality. Astral adapts these challenges by having stochastic assessors triage counters. Verifiable computation [2, 7, 25] and trusted hardware [12, 34] prove that a computation ran as specified but do not prove that its conclusion about a claim is right. Within one agent or orchestrator, evidence-binding frameworks [9, 24] gate outputs on evidence. We are not aware of work that jointly pins Web evidence, requires a quorum of attestations that pass a confidence threshold, and keeps LLM assessors’ verdicts open to challenge before accountable acceptance (Table 4).

Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification

6

Conclusion

We presented Astral, an accountable semantic consensus layer for AI-mediated Web verification. When the output sequences of independent LLM assessors never separate valid from invalid claims, a protocol that rejects invalid claims also falsely rejects valid ones with positive probability. Astral pins Web evidence, counts attestations above a confidence threshold, and admits signed challenges before accountable acceptance. With two of seven assessors adversarial, it lowered pooled attack success by 18.6–38.7 points relative to majority voting on five public benchmarks. The cost was coverage, as without adversaries 16.0–61.7% of public claims reached a binary verdict and the rest were disputed for audit. Groups of three or more model families showed no joint false acceptance on multisource claims, and diversity hedged against a weak backend on public benchmarks. These results support Web verification layers whose verdicts carry an attestation record and remain open to challenge.

WWW ’27, May 10–14, 2027, Dublin, Ireland

WWW ’27, May 10–14, 2027, Dublin, Ireland

References [1] Isabelle Augenstein, Timothy Baldwin, Meeyoung Cha, Tanmoy Chakraborty, Giovanni Luca Ciampaglia, David Corney, Renee DiResta, Emilio Ferrara, Scott Hale, Alon Halevy, Eduard Hovy, Heng Ji, Filippo Menczer, Ruben Miguez, Preslav Nakov, Dietram Scheufele, Shivam Sharma, and Giovanni Zagni. 2024. Factuality Challenges in the Era of Large Language Models and Opportunities for FactChecking. Nature Machine Intelligence 6, 8 (2024), 852–863. doi:10.1038/s42256024-00881-z [2] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2019. Scalable Zero Knowledge with No Trusted Setup. In CRYPTO. 701–732. [3] Onur Bilgin, Abdullah As Sami, Sriram Sai Vujjini, and John Licato. 2026. The Effect of Belief Boxes and Open-Mindedness on Persuasion. In ICAART. 260–267. [4] Lorenz Breidenbach, Christian Cachin, Benedict Chan, Alex Coventry, Steve Ellis, Ari Juels, Farinaz Koushanfar, Andrew Miller, Brendan Magauran, Daniel Moroz, Sergey Nazarov, Alexandru Topliceanu, Florian Tramèr, and Fan Zhang. 2021. Chainlink 2.0: Next Steps in the Evolution of Decentralized Oracle Networks. Whitepaper. [5] Ethan Buchman. 2016. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains. Master’s thesis. University of Guelph. [6] Miguel Castro and Barbara Liskov. 1999. Practical Byzantine Fault Tolerance. In OSDI. 173–186. [7] Bing-Jyue Chen, Suppakit Waiwitlikhit, Ion Stoica, and Daniel Kang. 2024. ZKML: An Optimizing System for ML Inference in Zero-Knowledge Proofs. In EuroSys. 560–574. [8] Canyu Chen and Kai Shu. 2024. Combating Misinformation in the Age of LLMs: Opportunities and Challenges. AI Magazine 45, 3 (2024), 354–368. doi:10.1002/ aaai.12188 [9] Ruiying Chen. 2025. Evidence-Bound Autonomous Research (EviBound): A Governance Framework for Eliminating False Claims. arXiv:2511.05524 [10] Hao Cheng, Yuan Lu, Zhenliang Lu, Qiang Tang, Yuxuan Zhang, and Zhenfeng Zhang. 2025. JUMBO: Fully Asynchronous BFT Consensus Made Truly Scalable. TDSC 22, 5 (2025), 5584–5602. [11] Pierre Civit, Daniel Collins, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira, and Pouriya Zarbafian. 2026. Scalable Accountable Byzantine Agreement and Beyond. In S&P. [12] Victor Costan and Srinivas Devadas. 2016. Intel SGX Explained. Cryptology ePrint Archive, Report 2016/086. [13] Xiaohai Dai, Chaozheng Ding, Hai Jin, Julian Loss, and Ling Ren. 2026. Ipotane: Balancing the Good and Bad Cases of Asynchronous BFT. In NDSS. [14] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and Tusk: A DAG-Based Mempool and Efficient BFT Consensus. In EuroSys. 34–50. [15] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. 2024. Improving Factuality and Reasoning in Language Models through Multiagent Debate. In ICML. 11733–11763. [16] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the Presence of Partial Synchrony. JACM 35, 2 (1988), 288–323. [17] Reza Fayyazi, Stella Hoyos Trueba, Michael Zuzak, and Shanchieh Jay Yang. 2025. ProveRAG: Provenance-Driven Vulnerability Analysis with Automated Retrieval-Augmented LLMs. IEEE Access 13 (2025), 212815–212826. doi:10.1109/ ACCESS.2025.3638251 [18] Kai Greshake, Sahar Abdelnabi, Shailesh Mishra, Christoph Endres, Thorsten Holz, and Mario Fritz. 2023. Not What You’ve Signed Up For: Compromising RealWorld LLM-Integrated Applications with Indirect Prompt Injection. In Proceedings of the 16th ACM Workshop on Artificial Intelligence and Security (AISec). 79–90. doi:10.1145/3605764.3623985 [19] Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Ceyao Zhang, Jinlin Wang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. 2024. MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework. In ICLR. [20] Marcin Iwanowski and Marcin Gahbler. 2025. Multiple Large AI Models’ Consensus for Object Detection—A Survey. Applied Sciences 15, 24 (2025), 12961. [21] Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S. Matthew Weinberg, and Edward W. Felten. 2018. Arbitrum: Scalable, Private Smart Contracts. In USENIX Security. 1353–1370. [22] Leslie Lamport. 1998. The Part-Time Parliament. TOCS 16, 2 (1998), 133–169. [23] Xuyang Liu, Zijian Zhang, Zhen Li, Xin Lu, Meng Li, Lei Xu, Meng Ao, and Liehuang Zhu. 2025. Group BFT: Two-Round BFT Protocols Via Replica Grouping. TDSC 22, 6 (2025), 6309–6326. [24] Edward Meyman. 2025. Verifiable AI Governance: The Four Tests Standard (4TS) and Proof-Carrying Decisions. SSRN Preprint. [25] Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. 2013. Pinocchio: Nearly Practical Verifiable Computation. In S&P. 238–252. [26] Amirmohammad Pasdar, Young Choon Lee, and Zhongli Dong. 2023. Connect API with Blockchain: A Survey on Blockchain Oracle Implementation. Comput. Surveys 55, 10 (2023), 1–39.

Yanna Jiang, Mingyuan Li, Xu Wang, and Guangsheng Yu

[27] Jack Peterson, Joseph Krug, Micah Zoltu, Austin K. Williams, and Stephanie Alexander. 2019. Augur: a Decentralized Oracle and Prediction Market Platform (v2.0). Whitepaper. Forecast Foundation. [28] Chen Qian, Wei Liu, Hongzhang Liu, Nuo Chen, Yufan Dang, Jiahao Li, Cheng Yang, Weize Chen, Yusheng Su, Xin Cong, Juyuan Xu, Dahai Li, Zhiyuan Liu, and Maosong Sun. 2024. ChatDev: Communicative Agents for Software Development. In ACL. 15174–15186. [29] Sami Saadaoui and Eduardo Alonso. 2025. Coordinated LLM Multi-Agent Systems for Collaborative Question-Answer Generation. Knowledge-Based Systems 330 (2025), 114627. [30] Mrinank Sharma, Meg Tong, Tomasz Korbak, David Duvenaud, Amanda Askell, Samuel R. Bowman, Newton Cheng, Esin Durmus, Zac Hatfield-Dodds, Scott R. Johnston, Shauna Kravec, Timothy Maxwell, Sam McCandlish, Kamal Ndousse, Oliver Rausch, Nicholas Schiefer, Da Yan, Miranda Zhang, and Ethan Perez. 2024. Towards Understanding Sycophancy in Language Models. In ICLR. [31] The Diem Team. 2021. DiemBFT v4: State Machine Replication in the Diem Blockchain. Technical Report. [32] Louis Tremblay Thibault, Tom Sarry, and Abdelhakim Senhaji Hafid. 2022. Blockchain Scaling Using Rollups: A Comprehensive Survey. IEEE Access 10 (2022), 93039–93054. [33] James Thorne, Andreas Vlachos, Christos Christodoulopoulos, and Arpit Mittal. 2018. FEVER: a Large-scale Dataset for Fact Extraction and VERification. In NAACL-HLT. 809–819. [34] Florian Tramèr and Dan Boneh. 2019. Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware. In ICLR. [35] David Wadden, Shanchuan Lin, Kyle Lo, Lucy Lu Wang, Madeleine van Zuylen, Arman Cohan, and Hannaneh Hajishirzi. 2020. Fact or Fiction: Verifying Scientific Claims. In EMNLP. 7534–7550. [36] Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, Ahmed Hassan Awadallah, Ryen W. White, Doug Burger, and Chi Wang. 2024. AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversations. In COLM. [37] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In PODC. 347–356. [38] Lifan Zheng, Jiawei Chen, Qinghong Yin, Jingyuan Zhang, Xinyi Zeng, and Yu Tian. 2026. Rethinking the Reliability of Multi-agent System: A Perspective from Byzantine Fault Tolerance. In AAAI. 35012–35020. [39] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. 2023. Judging LLM-as-a-Judge with MTBench and Chatbot Arena. In Advances in Neural Information Processing Systems 36 (NeurIPS). 46595–46623. doi:10.52202/075280-2020

A

Ethical Considerations

The study uses public benchmarks and synthetic tasks, involves no human participants or personal data, and runs attacks only in simulation. Code for all experiments will be released after review. The authors used LLM assistants (Anthropic’s Claude, OpenAI’s Codex) to draft and edit text, to write and review code, and to review the protocol specification and reported numbers. The authors checked all such output and take full responsibility for this paper.

B

Formalization of Probabilistic Semantic Validity B.1 Ground-Truth and Failure Event Definitions V (𝐷) ∈ {0, 1} denotes policy-relative semantic validity on D. V (𝐷) = 1 ⇐⇒ claim is supported by evidence under policy. Astral’s stable finality requires 𝑉struct (𝐷) = PASS, L1’s CommitQC, 𝑘 SEM_PASS attestations (SemQC), and challengewindow survival (NCC) for that slot. Definition B.1 (Stable Semantic Failure Event). E := {Stable(𝐷) ∧ V (𝐷) = 0} The empirical failure bound is 𝛿 (𝜖, 𝑘ℎ ) := E𝐷∼D [Pr[E | 𝐷]]

Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification

B.2

Decision Objects and Semantic Validity

Definition B.2 (Semantic Validity). Semantic validity uses decision 𝐷, evidence 𝐸, and inference policy 𝜋. • Inference policy. 𝜋 : 2Evidence × Claim → [0, 1] measurably assigns confidence to evidence–claim pairs. Domain-specific 𝜋 is committed in 𝐷 via policy_hash. • Binary validity. SemValid𝜏 (𝐷, 𝐸) ≡ 𝜋 (𝐸, claim(𝐷)) ≥ 𝜏, with acceptance threshold 𝜏 ∈ (0, 1]. • Protocol realization. 𝑉infer stochastically estimates 𝜋. For honest 𝑝𝑖 with 𝑂𝑖 , 𝑉infer at 𝑝𝑖 samples a distribution centered on 𝜋 (𝐸, claim(𝐷)) with oracle-dependent noise. Honest processes may disagree on SemValid𝜏 (𝐷, 𝐸) for 𝜋 (𝐸, claim(𝐷)) near 𝜏. Required properties of 𝜋. Each domain-specific Astral instantiation must verify them. (1) Measurability. 𝜋 is well-defined on all pairs (𝐸, claim). (2) Weak evidence monotonicity. 𝜋 (𝐸 ∪ 𝐸 ′, 𝑐) ≥ 𝜋 (𝐸, 𝑐) for corroborating evidence 𝐸 ′ . (3) Threshold sensitivity. Inputs of non-trivial measure satisfy 𝜋 (𝐸, 𝑐) ∈ (𝜏 − 𝛽, 𝜏 + 𝛽) for small 𝛽. Without near-threshold inputs, trivial decidability makes Astral unnecessary. Astral assumes neither complete 𝜋, sound 𝜋 (false-accept probability 𝜖), nor oracle agreement (Section 3.3).

B.3

Revised Minimal Explicit Assumptions

Assumption 1 (DLS Partial Synchrony). After unknown GST, all messages between honest replicas arrive within known bound Δ. View timeouts increase monotonically, so eventually timeout(𝑣) > Δ post-GST. Agreement safety is unconditional. Liveness and semantic stabilization hold post-GST. Assumption 2 (Cryptographic Primitives). Assume EUF-CMA signatures and collision-resistant hashes. All protocol signatures bind (pid, inst, ℎ, 𝑣) with domain separation against cross-instance replay. All quorum certificates contain 2𝑓 + 1 individual signatures. Assumption 3 (AFS Availability). The AFS is trusted for availability. Two-phase DAQC preserves agreement safety (Section 3.1). If AFS is unavailable, DAQC cannot form and liveness stalls. Each DA_ACK signature binds the committed Merkle root afs_root. Every honest replica independently verifies integrity before acknowledging availability. Replicating AFS across 2𝑓 +1 replicas mitigates selective evidence withholding. Erasure-coded data-availability sampling (DAS) complements replication and could reduce storage without weakening the trust model. Assumption 4 (Snapshot Determinism). All honest replicas evaluate 𝑉struct on the same committed snapshot, certified by DAQC before any attestation. Assumption 5 (Base Consensus under Partial Synchrony). The network satisfies Assumption 1. L1’s black-box standard BFT views/epochs and quorum locking prevent conflicting commit/NCC quorums formed by honest replicas for the same slot. Assumption 6 (Distributional False Accept). We provide no worst-case bounds for adaptive adversaries crafting inputs to fool 𝑉infer . For invalid claims from characterized task distribution D, each semantic verifier’s empirical false-accept probability is Pr[𝑉infer =

WWW ’27, May 10–14, 2027, Dublin, Ireland

PASS] ≤ 𝜖. We measure 𝜖 = 𝜖ˆ(𝜏) at each 𝜏. This risk metric provides no cryptographic soundness guarantee. Assumption 7 (Diversity with Bounded Correlation (Honest Subset)). Among 𝑘 = 2𝑓 + 1 attestations in SemQC, at least 𝑘ℎ = 𝑓 + 1 come from a fixed set 𝐻 of 𝑛 − 𝑓 honest assessors. For honest-verifier errors, 𝜌𝑘ℎ (Equation (4)) is at most 1 under independence, because each honest verifier’s rate is at most 𝜖, and can exceed 1 under positive correlation. It has no a priori bound and is measured for each D. Byzantine attestations are false accepts (Pr = 1) within the 𝑓 fault budget. Assumption 8 (Counter-Card Propagation via Mandatory Inclusion). Astral disseminates counters through CounterQC and Mandatory Inclusion (Section 3.2). Post-GST, partial synchrony with 𝑊 (𝑣) ≥ 2Δ and the admission cutoff at 𝑊 (𝑣) − Δ propagate every admitted counter before NCC signing. Triage resolves structurally valid, semantically vacuous counters. CRQC unblocks NCC signing within 𝑂 (𝑇infer + Δ). Fallback takes at most 𝑇arb . Because every filed counter is delivered post-GST, a challenge fails only if no honest checker detects the invalidity and files a structurally valid counter in time, or if triage dismisses the counter. Assumption 9 (Verifier Participation). Post-GST, all honest replicas complete 𝑉infer within 𝑇infer , counter triage within 𝑇arb , and DA_ACK within 𝑇DA . These bounds give DAQC liveness, while SemQC and CRQC formation also depend on honest votes (Remark 1). Assumption 10 (Pacemaker Bound). Post-GST, pacemaker timeouts eventually exceed Δ + 𝑇DA + 𝑇infer + 𝑊 (𝑣) + 𝑇arb , ensuring stabilization within one stable view. Alternatively, stabilization state persists across views, preserving all partial progress.

B.4

Stabilization Policy and Proof Sketch

Stabilization Policy P. 𝐷 becomes STABLE iff 𝑘 distinct-replica SEM_PASS attestations are collected and a 2𝑓 +1 quorum NCC forms. Proposition B.3 (Distributional Semantic Failure Decomposition). Under Assumptions 5 to 10, let 𝑄 be the event that at least 𝑘ℎ assessors in 𝐻 falsely accept. The distributional semantic failure probability satisfies
𝑘 𝛿 (𝜖, 𝑘ℎ ) ≤ 𝑛−𝑓 𝜖 ℎ 𝜌𝑘ℎ · (1 − 𝑝 ch|𝑄 ) . 𝑘ℎ | {z } | {z } ≥ Pr[𝑄 ]

challenge miss

Proof. Failure (E) requires SemQC, and hence 𝑄 by Assumption 7, together with no counter that is filed, delivered, and upheld in triage before NCC forms. Thus Pr[E] ≤ Pr[𝑄] (1 − 𝑝 ch|𝑄 ), and Ñ Pr[𝑄] = 0 gives Pr[E] = 0. Since 𝑄 is the union of 𝑖 ∈𝑆 𝐴𝑖 over all 𝑆 ⊆ 𝐻 with |𝑆 | = 𝑘ℎ , the union bound and Equation (4) give
𝑘 Pr[𝑄] ≤ 𝑛−𝑓 𝜖 ℎ 𝜌𝑘ℎ . Invalidity that fools 𝑘ℎ verifiers may also 𝑘ℎ evade detection, so unconditional estimates can overstate 𝑝 ch|𝑄 . □

C Agreement Proof and Censorship Resistance C.1 False Rejection under Shared Support Definition C.1 (Semantic Validity Decision (SVD) Task). Each process 𝑝𝑖 receives decision object 𝐷 = (claim, evidence) and must output binary judgment 𝑣𝑖 ∈ {VALID, INVALID}. • Agreement. For all honest processes 𝑝𝑖 , 𝑝 𝑗 , 𝑣𝑖 = 𝑣 𝑗 .

WWW ’27, May 10–14, 2027, Dublin, Ireland

Yanna Jiang, Mingyuan Li, Xu Wang, and Guangsheng Yu

• Rejection coverage. The set 𝐹 inv of non-trivial invalid inputs that the protocol rejects with positive probability is non-empty. Rejection coverage differs from the empirical coverage of §4.1, which is the fraction of trials that end in a binary verdict. • Termination. All honest processes output with probability 1.

This bounds only the expected count. For independent honest errors and 𝑓attest fixed independently of them, SemQC forms with probability Pr[𝑋 ≥ 2𝑓 +1− 𝑓attest ] for 𝑋 ∼ Bin(2𝑓 +1, 1−𝜖fn ). By Assumption 9, honest attestations arrive within 𝑂 (𝑇infer + Δ). Fallback. Lowering 𝑘 to 𝑓 + 1 weakens certification to 𝑘ℎ = 1 and higher 𝛿.

Majority example. For 𝑛 = 7 assessors that each give the wrong label on a valid input independently with probability 𝑒, majority
Í false rejection has probability 𝑖 ≥4 7𝑖 𝑒 𝑖 (1 − 𝑒) 7−𝑖 , which is 2.7 × 10−3 for 𝑒 = 0.1 and 3.3 × 10−2 for 𝑒 = 0.2. A disagreement rate does not determine 𝑒, because two independent calls disagree with probability 2𝑒 (1 − 𝑒) for 𝑒 and for 1 − 𝑒 alike.

Remark 1 (SemQC Liveness is Conditional). Under withholding (𝑓attest = 0), SemQC at 𝑘 = 2𝑓 + 1 forms with certainty only when 𝜖fn = 0. With all Byzantine replicas attesting in time (𝑓attest = 𝑓 ), 𝜖fn ≤ 𝑓 /(2𝑓 + 1) (Equation (6)), or 2/5 at 𝑛 = 7, brings the expected count to 𝑘, and formation remains probabilistic. Choose 𝑘 by threat model, between 𝑘 = 2𝑓 + 1 (strong, conditional on 𝜖fn ) and 𝑘 = 𝑓 + 1 (minimal, tolerates up to 𝑓 honest rejections, but 𝑘ℎ = 1).

Proof of Proposition 2.1.

Proof. Let 𝑟 be the coins of Π, drawn independently of the input and of the oracles. Given 𝑟 , the queries, stopping, and verdict of Π are functions of the outputs observed so far. The set 𝐻 rej (𝑟 ) of finite output histories after which Π stops with INVALID therefore does not depend on 𝐷. A history ℎ = (𝑜 1, . . . , 𝑜𝑡 ) has probability Î Pr𝐷 [ℎ | 𝑟 ] = 𝑗 ≤𝑡 Pr𝐷 [𝑜 𝑗 | 𝑟, 𝑜 1, . . . , 𝑜 𝑗 −1 ] on input 𝐷, and shared support, which holds for every coin value 𝑟 , makes every factor positive for every reachable ℎ and non-trivial 𝐷. Since Π terminates with probability 1, rejection is the disjoint union of the events of following some ℎ ∈ 𝐻 rej (𝑟 ), which gives Pr[Π(𝐷) = INVALID] = Í E𝑟 [ ℎ∈𝐻rej (𝑟 ) Pr𝐷 [ℎ | 𝑟 ]] for every non-trivial 𝐷. For 𝐷 ∗ ∈ 𝐹 inv this expectation is positive, hence 𝐻 rej (𝑟 ) is non-empty for coins of positive probability. For a non-trivial valid 𝐷 ′ the inner sum is positive on those coins, which yields 𝑃err (Π, 𝐷 ′ ) > 0. Examples. One round of majority voting over independent calls with valid-input error 𝑒 > 0 falsely rejects with the positive binomial tail above. Unanimous INVALID lowers false rejection to 𝑒 𝑛 , but a call that rejects an invalid input with probability 𝑞 then yields rejection only with probability 𝑞𝑛 . Both rules have the same rejection coverage and differ only in their rejection probabilities. A protocol that always outputs VALID has 𝑃err = 0 and empty 𝐹 inv . A deterministic 𝑉struct reads 𝐷 directly and lies outside the hypothesis. It agrees without false rejection, but it checks only that evidence exists and is well-formed and cannot test whether the evidence entails the claim. □

C.2

Stabilization-Layer Liveness (Post-GST, Conditional)

SemQC Liveness. Under static corruptions with 𝑛 = 3𝑓 + 1 and 𝑓 Byzantine replicas, 2𝑓 + 1 honest replicas run 𝑉infer . Let 𝜖fn denote honest-verifier REJECT probability on valid claims (false-negative rate). SemQC requires 𝑘 = 2𝑓 + 1 distinct-replica attestations, and 𝑓attest ≤ 𝑓 counts Byzantine attestations that arrive in time. If all 𝑓 Byzantine replicas withhold, every honest replica must pass, which is guaranteed only when 𝜖fn = 0. If all 𝑓 Byzantine replicas attest in time, 𝑓 + 1 honest passes suffice, and the expected honest pass count (1 − 𝜖fn ) (2𝑓 + 1) reaches 𝑓 + 1 when

𝜖fn ≤

𝑓 1 < 2𝑓 + 1 2

(6)

NCC Liveness. Without challenges, after 𝑊 (𝑣) ≥ 2Δ all honest replicas sign NO_CHALLENGE → NCC within 𝑂 (𝑊 (𝑣) + Δ). For challenged claims, triage resolves every counter or flags DISPUTED within worst-case 𝑂 (𝑓 · 𝑇arb ). StableQC Liveness. Post-GST, valid unchallenged claims obtain StableQC within 𝑂 (2Δ + 𝑊 (𝑣) + 𝑇infer + 𝑇DA ) after proposal once SemQC forms within its attestation bound. Challenges add triage time 𝑂 (𝑓 · 𝑇arb ). Unresolved counters trigger DISPUTED. Theorem C.2 (Astral Liveness (Post-GST)). Under Assumptions 5 to 10, the following hold post-GST for any height ℎ. (1) Commit liveness. Commit(ℎ) is emitted within 𝑂 (𝑓 ) viewchanges + 𝑂 (Δ + 𝑇DA ) per view (inherited from L1). (2) Stabilization liveness. If at least 2𝑓 + 1 SEM_PASS attestations arrive within 𝑂 (𝑇infer +Δ) (Remark 1) and no counter carries a valid deterministic fraud-proof, StableQC forms within 𝑂 (2Δ +𝑊 (𝑣) +𝑇infer +𝑇DA ) after CommitQC. For challenged claims, counter triage adds 𝑂 (𝑓 · 𝑇arb ). Counters unresolved after triage flag the decision DISPUTED within 𝑂 (𝑊 (𝑣) +𝑇arb ). Proof. L1 gives commit liveness (Appendix D), since Astral only restricts voting (Remark 2) and an honest leader can satisfy all conditions post-GST with AFS availability (Assumption 3). Deterministic counter forwarding converges within Δ, satisfying Mandatory Inclusion. SemQC formation under this attestation condition and NCC liveness with resolved counters or DISPUTED timeout yield stabilization within one stable view (Assumption 10). □

D

L1 Interface

Astral requires totally ordered Commit(ℎ), at most one per height, and post-GST commit liveness (§3.1). Before voting, L1 must evaluate external validity 𝑃ext (𝑏) → {accept, reject}. The L2 admission checks 𝑉struct , DAQC verification, and Mandatory Inclusion run after CommitQC (Algorithm 1), so Astral adds no evidence-dependent condition to 𝑃ext and L1 votes never wait on evidence. With deterministic BFT (HotStuff [37], PBFT [6], or Tendermint [5]), L2 starts at CommitQC. On probabilistic chains, L2 starts at 𝑘-deep confirmation. Semantic failure or reversion has probability at most 𝛿 + 𝑝 rev (𝑘) (§4.4). Remark 2 (External Validity Preserves Safety). Quorum intersection and honest non-equivocation preserve L1 safety when 𝑃ext restricts accepted proposals. Liveness. Post-GST, an honest leader can satisfy all Astral conditions given available evidence (Assumption 3) and deterministic

Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification

CounterQC forwarding for Mandatory Inclusion. Post-GST, once an unresolved CounterQC reaches all honest assessors (Theorem 3.6), a block omitting it obtains no DAQC until the counter is included or resolved. Stabilization requires bounded-time 𝑉infer (Assumption 9) and every valid counter’s resolution within 𝑇arb (§3.2).

E

Complete Protocol Specification

Window cap. Operators cap 𝑊 (𝑣) at 𝑊max to bound worst-case stabilization latency, e.g. 60 s interactively and 300 s for batch pipelines.

E.1

Formal Pipeline (Pseudocode)

Algorithm 1 specifies L1/L2 (DAQC), and Algorithm 2 specifies L3 attestation, triage, and certification. Algorithm 1 Astral Consensus Core (Replica 𝑖) 1: Params: 𝑛, 𝑓 , quorum=2𝑓 +1, 𝑘=quorum, 𝜏 ; 𝑊 (𝑣) = max(2Δ+𝜖proc , 𝑊0 ·𝑣) 2: Leader Propose: Build 𝑏=(𝑃, counter_batch, payload) , broadcast PROPOSE (DS, 𝑏, highQC) 3: Replica Vote: if valid and unvoted: log; voted[ℎ, 𝑣 ] ← true; send VOTE (DS, 𝐻 (𝑏 ) ) 4: Commit: Leader forms QC on ≥ quorum votes; on 3-chain: CommitQC; output Commit(ℎ) 5: L2 Admission: On CommitQC: if 𝑉struct (𝐷 (𝑏 ) ) = PASS: broadcast 𝑃 ; collect 2𝑓 +1 DA_ACK → DAQC; open window; trigger Algorithm 2. Mandatory Inclusion: deny DA_ACK if known CounterQCs omitted. 6: View-Change: If no progress within timeout(𝑣) : 𝑣 ← 𝑣+1

WWW ’27, May 10–14, 2027, Dublin, Ireland

F Supplementary Evaluation Results F.1 Committee, Non-Web Domains, and Additional Metrics GPT-4o, Claude Haiku 4.5, and Gemini 3 Flash are accessed via API. Llama 3.1 70B, Mixtral 8×7B, Qwen 2.5 32B, and DeepSeekR1-Distill 32B run locally, 4-bit quantized. The 𝑛=7 committee uses two replicas per API family and one Llama 3.1 70B. At 𝑛=13, each remaining local family adds two replicas. Non-Web evaluation uses 60 synthetic Python snippets across six CWE families (code vulnerability patching, CVP) and 50 synthetic syslog bundles across five incident types (semantic log auditing, SLA), half fabricated in each domain. Under A4, Astral accepts no refuted SLA (25 items) or CVP (30 items) claim at any 𝑛 ∈ {7, 13, 31, 67, 100}. MV accepts none at 𝑛=7 but 88.0% (SLA) and 46.7% (CVP) at every larger 𝑛. CPWBFT accepts 12.0–32.0% (SLA) and 0.0–13.3% (CVP). Under A1–A4 at 𝑛=7, counters are filed in 56.7–59.0% of Astral trials, a CRQC resolves them in 5.0–8.9%, and 53.8–55.7% end DISPUTED. Astral’s protocol correctness excludes DISPUTED verdicts and is 42.4–44.8%. Table 5: Abstaining majority voting on Astral’s votes (%). Conf. MV abstains below a mean-confidence threshold calibrated to Astral’s benign coverage, and MV5 needs five agreeing votes. TAR is the acceptance rate of supported claims under A1–A4. Synthetic pools MFV, CVP, and SLA at 𝑛=7.

Algorithm 2 Astral Stabilization & Counter Triage (Replica 𝑖)

Astral

1: Attestation: (label, conf, ref ) ← 𝑉infer (𝐷 (𝑏 ) ) ; if SUPPORT and conf ≥ 𝜏 : send SEM_PASS 2: SemQC: On ≥ 𝑘 distinct SEM_PASS: form and forward SemQC 3: Counter Triage: For each CounterQC of a counter filed before 𝑊 (𝑣) − Δ: 4: Deterministic fraud-proof: re-execute in WASM ( ≤ 𝐺 max ); valid → SUSTAINED (StableQC blocked); invalid → COUNTER_REJECT

5: Semantic counter: 𝑉infer triage; refutes → COUNTER_SUSTAIN; else → COUNTER_REJECT 6: CRQC: ≥ quorum COUNTER_REJECT → CRQC; remove from unresolvedCounters 7: Closure: After 𝑊 (𝑣) : if unresolvedCounters = ∅ : send NO_CHALLENGE; ≥ quorum → NCC 8: Timeout: If counters remain unresolved at 𝑊 (𝑣) + 𝑇arb : provisional disputed[ℎ] ← true 9: Certify: If CommitQC, SemQC, NCC ≠ ⊥, no SUSTAINED: Certify(ℎ) , clear disputed[ℎ] 10: Reject: After 𝑊 (𝑣)+Δ, if SemQC = ⊥, unresolvedCounters = ∅ , ¬disputed[ℎ] , no SUSTAINED: provisional Reject(ℎ) until a forwarded SemQC arrives

Invariant 2 (Stabilization–L1 Isolation). Stabilization state (L3) is monotone and block-scoped. L3 state never enters L1 voting. It reaches L2 only through Mandatory Inclusion, which reads unresolved certified counters and can only withhold DA_ACK. Voting consults only 𝑃ext , voted[ℎ, 𝑣], and lockedQC. Thus no stabilization certificate can induce a vote violating lockedQC. Invariant 3 (Input Consistency for L3). Before any L3 attestation, all honest replicas commit the same L1 block (CommitQC ensures identical valℎ ), verify structural validity with identical deterministic 𝑉struct results, and obtain DAQC certifying the same evidence snapshot’s availability. All honest replicas thus have identical, verified input for probabilistic semantic reasoning, while deterministic L1/L2 safety is independent of non-deterministic L3. Attestation threshold and diversity. Evaluation uses 𝑘 = 2𝑓 +1. Lowering 𝑘 (down to 𝑓 +1) tolerates more false negatives but weakens 𝛿 bounds. Diversity predicates are recommended (§3.3), but optional for SemQC.

AVeriTeC Climate-FEVER FEVER PUBHEALTH SciFact Synthetic

Conf. MV

MV5

Cov.

ASR↓

TAR↑

Cov.

ASR↓

TAR↑

Cov.

ASR↓

TAR↑

16.0 37.5 33.3 55.9 61.7 43.8

21.5 43.0 37.0 36.1 53.1 1.4

57.8 65.4 77.4 60.6 67.9 86.4

16.0 37.1 33.0 55.9 61.7 41.0

59.1 71.4 69.3 54.7 77.7 0.0

82.4 85.7 88.6 80.3 84.9 54.3

82.4 73.6 68.6 80.7 58.3 99.0

44.3 53.5 54.9 43.3 61.1 2.6

70.9 73.4 85.1 65.8 72.2 89.0

Forged votes carry confidence 0.95, so Conf. MV accepts 54.7– 77.7% of refuted public-benchmark claims. On the synthetic suite, it accepts no refuted claim and 54.3% of supported ones, against 86.4% for Astral. MV that needs six or seven agreeing votes has lower ASR than MV5 , but its TAR stays below Astral’s on every public benchmark, and two Byzantine assessors can block any of its decisions. With refuted claims resampled, the 95% interval of Astral’s pooled-ASR gap to each bracketed baseline in Table 2 excludes zero. Under A2, ASR on CVP and MFV is 100% for L1-BFT, 0.0% and 6.0% with a SemQC from 𝑉struct and 𝑉infer , and 0.0% and 2.0% for full Astral. Astral-NoDiv averages 3.3% and 3.5% over backends (CVP 0.0–13.3%, MFV 2.0–4.0%). Simple Threshold, which follows one seeded assessor per trial, reaches 23.3% and 40.0%. Table 6: Synthetic suite under A1–A4 (840 attacked, 210 benign trials per protocol and 𝑛). Attack Reject. counts refuted claims not accepted, and tokens are on code patching. L1 = L1-BFT, CP = CP-WBFT.

Metric (%)

L1

MV

𝑛 =7 CP

Astral

L1

MV

𝑛 = 31 CP

Astral

Attack Reject. ↑ Benign SCSR ↑ Counter-Card Filing CRQC Resolution ↑ Stable Finality ↑ Tokens/decision

0.0 50.0 – – – –

96.9 93.8 – – – 8.1K

82.1 94.3 – – – 16.4K

98.6 43.3 58.3 6.3 43.9 12.0K

0.0 50.0 – – – –

81.7 93.8 – – – 36.9K

79.5 94.3 – – – 180.0K

99.0 32.9 67.0 13.5 41.0 172.7K

Related documents

• Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification#1456410
• FORGE: Form-Optimal Routing of Grounded Evidence for Frozen LLM Agents#1119431
• Verify Less, Evolve More: Training Idea-Level Critics for Verification-Efficient ML Evolving Agents#1233032
• The Shape of Ownership: Verifying LLM Provenance through Semantic Structures#924711
• The Shape of Ownership: Verifying LLM Provenance through Semantic Structures#920477