mlsanityData to 14 Oct 2026

Certifiable Semantic Agreement Among LLM Agents: What the Admissibility Instrument Decides

arXiv 2606.07316 ↗First posted 5 Jun 2026cs.MA cs.AI cs.DCcited by 0

On the map: LLM agents and tool use → Agent threats, guardrails and governance

Abstract (arXiv)

Can a committee of LLM agents reach agreement that is certifiable at the level of meaning, not only at the level of a label? We build a protocol to find out. H-CSC emits one of three typed outcomes per round -- semantic commit, verdict commit, or typed abort -- under a common 2f+1 distinct-signer certificate, and we use it to measure what such agreement costs and buys. The answer is conditional, and the condition is not the protocol. We prove a containment lemma: whenever the semantic core is large enough to make the committed verdict deterministically valid, the verdict margin already exceeds f, so at matched deterministic guarantees no coverage separation from certificate-wrapped majority is possible. Measurement agrees: the two rules commit the identical task set. What matters instead is the admissibility instrument. Against adversaries that preserve the verdict and corrupt only the reasoning, a 442 MB fine-tuned encoder reaches AUROC 0.621-0.744 at 0-8% TPR (5% honest FPR), while a training-free lexical predicate reaches 0.865-0.982 at 38-80% (50 tasks, 200 attacks, 400 honest) and is exactly deterministic, discharging an assumption the digest proofs rely on. Honest agents disperse further than attacks displace (90th-percentile honest angular distance 0.992 rad against a 0.65 radius), so on free-text rationales no embedding filter is viable -- a property of the output schema, which when tightened collapses dispersion twenty-fold. The committed digest is not inert: under non-disclosure a similarity-preserving sketch separates faithful from substituted derived statements at AUROC 0.741 (n=350), where a cryptographic hash and a verdict-only digest score exactly 0.500. We also report a tie-break capture vulnerability found in our own protocol, and its four-line fix. We claim no safety or coverage advantage over verdict-only certification; the lemma explains why there is none to claim.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use. Builds on 19 of its 49 references that are in the map. First posted on arXiv 5 Jun 2026.

Builds on

19 of 49 references.

Closest ancestors · 2

Same direction, newest first

  1. 2026From Agent Traces to Trust: A Survey of Evidence Tracing and Execution Provenance in LLM Agents3 Jun
  2. 2025From Prompt Injections to Protocol Exploits: Threats in LLM-Powered AI Agents Workflows29 Jun

Other references · 17

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  2. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,170
  3. 2023Generative Agents: Interactive Simulacra of Human Behaviorcited by 3,568
  4. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,340
  5. 2023Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debatecited by 1,011
  6. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 711
  7. 2019Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailmentcited by 671
  8. 2020BERT-ATTACK: Adversarial Attack Against BERT Using BERTcited by 491
  9. 2018Generating Natural Language Adversarial Examplescited by 424
  10. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  11. 2019Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulationcited by 141
  12. 2025Beyond Majority Voting: LLM Aggregation by Leveraging Higher-Order Informationcited by 26
5 more
  1. 2024Language Model Council: Democratically Benchmarking Foundation Models on Highly Subjective Taskscited by 18
  2. 2025Rethinking the Reliability of Multi-agent System: A Perspective from Byzantine Fault Tolerancecited by 17
  3. 2026Robust Multi-Agent LLMs under Byzantine Faultscited by 10
  4. 2025A Weighted Byzantine Fault Tolerance Consensus Driven Trusted Multiple Large Language Models Networkcited by 9
  5. 2018HotStuff: BFT Consensus in the Lens of Blockchaincited by 5

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Theoria: Rewrite-Acceptability Verification over Informal Reasoning States
  2. 2026Proof-Carrying Certificates for LLM Pipelines: A Trust-Boundary Architecture
  3. 2026Know Your Limits : On the Faithfulness of LLMs as Solvers and Autoformalizers in Legal Reasoning
  4. 2026MNC: Scope-Bound Semantic Declassification for Private LLM-Agent Communication
  5. 2026Beyond Local Accuracy: A Protocol-Level Identifiability Audit for Controlled LLM Reasoning Evaluation
  6. 2025NP-Hard Lower Bound Complexity for Semantic Self-Verification
  7. 2026Silence Is Endorsement: Verification-Status Laundering in LLM Agent Pipelines
  8. 2026LLMs as a Jury: Cross-Model Consensus Can Outperform Process Reward Models for LLM Reasoning