# Tractable Asymmetric Verification for Large Language Models via Deterministic Replicability

arXiv: https://arxiv.org/abs/2509.11068 · HTML: https://mlsanity.com/paper/2509.11068/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 28 references that are in the map.
- First posted on arXiv 14 Sep 2025.

## Builds on (most cited first, 18 of 18)

- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Hallucination is Inevitable: An Innate Limitation of Large Language Models](https://mlsanity.com/paper/2401.11817/) (2024)
- [Large Language Model Agent: A Survey on Methodology, Applications and Challenges](https://mlsanity.com/paper/2503.21460/) (2025)
- [Show Your Work: Improved Reporting of Experimental Results](https://mlsanity.com/paper/1909.03004/) (2019)
- [Emergent social conventions and collective bias in LLM populations](https://mlsanity.com/paper/2410.08948/) (2024)
- [A Survey on LLM-based Multi-Agent System: Recent Advances and New Frontiers in Application](https://mlsanity.com/paper/2412.17481/) (2024)
- [zkLLM: Zero Knowledge Proofs for Large Language Models](https://mlsanity.com/paper/2404.16109/) (2024)
- [Trust Me, I'm Wrong: LLMs Hallucinate with Certainty Despite Knowing the Answer](https://mlsanity.com/paper/2502.12964/) (2025)
- [CodeAgents: A Token-Efficient Framework for Codified Multi-Agent Reasoning in LLMs](https://mlsanity.com/paper/2507.03254/) (2025)
- [MAEBE: Multi-Agent Emergent Behavior Framework](https://mlsanity.com/paper/2506.03053/) (2025)
- [On the Fundamental Impossibility of Hallucination Control in Large Language Models](https://mlsanity.com/paper/2506.06382/) (2025)
- [Toward Verifiable Misinformation Detection: A Multi-Tool LLM Agent Framework](https://mlsanity.com/paper/2508.03092/) (2025)
- [AIRepr: An Analyst-Inspector Framework for Evaluating Reproducibility of LLMs in Data Science](https://mlsanity.com/paper/2502.16395/) (2025)
- [Responsible Innovation: A Strategic Framework for Financial LLM Integration](https://mlsanity.com/paper/2504.02165/) (2025)
- [Do Language Models Have Bayesian Brains? Distinguishing Stochastic and Deterministic Decision Patterns within Large Language Models](https://mlsanity.com/paper/2506.10268/) (2025)

## Abstract (arXiv)

The landscape of Large Language Models (LLMs) shifts rapidly towards dynamic, multi-agent systems. This introduces a fundamental challenge in establishing computational trust, specifically how one agent can verify that another's output was genuinely produced by a claimed LLM, and not falsified or generated by a cheaper or inferior model. To address this challenge, this paper proposes a verification framework that achieves tractable asymmetric effort, where the cost to verify a computation is substantially lower than the cost to perform it. Our approach is built upon the principle of deterministic replicability, a property inherent to autoregressive models that strictly necessitates a computationally homogeneous environment where all agents operate on identical hardware and software stacks. Within this defined context, our framework enables multiple validators to probabilistically audit small, random segments of an LLM's output and it distributes the verification workload effectively. The simulations demonstrated that targeted verification can be over 12 times faster than full regeneration, with tunable parameters to adjust the detection probability. By establishing a tractable mechanism for auditable LLM systems, our work offers a foundational layer for responsible AI and serves as a cornerstone for future research into the more complex, heterogeneous multi-agent systems.