Tractable Asymmetric Verification for Large Language Models via Deterministic Replicability

Zan-Kai Chong School of Science and Technology Kwansei Gakuin University Japan [email protected] Hiroyuki Ohsaki School of Science and Technology Kwansei Gakuin University Japan [email protected] Bryan Ng School of Engineering & Computer Science Victoria University of Wellington New Zealand ckbryan · 2025

Read Tractable Asymmetric Verification for Large Language Models via Deterministic Replicability by Zan-Kai Chong School of Science and Technology Kwansei Gakuin University Japan [email protected] Hiroyuki Ohsaki School of Science and Technology Kwansei Gakuin University Japan [email protected] Bryan Ng School of Engineering & Computer Science Victoria University of Wellington New Zealand ckbryan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11068.txt.

Introduction

Zan-Kai Chong and 2 co-authors design a cheap way to check that a language model really did the work in this 2025 paper. In multi-agent systems, one agent may claim an answer came from a strong model while quietly using a cheaper one. Proving otherwise sounds expensive, since the checker might have to redo the whole computation.

Their framework leans on deterministic replicability: on identical hardware and software, the same model repeats its output exactly. Validators can then re-run small random slices of an answer instead of the whole thing. Simulations found targeted checking ran more than twelve times faster than full regeneration, with dials to trade speed against the chance of catching a cheat.

Catalog record

CREATORZan-Kai Chong School of Science and Technology Kwansei Gakuin University Japan [email protected] Hiroyuki Ohsaki School of Science and Technology Kwansei Gakuin University Japan [email protected] Bryan Ng School of Engineering & Computer Science Victoria University of Wellington New Zealand ckbryan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-11068

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tractable Asymmetric Verification for Large Language Models via Deterministic Replicability Zan-Kai Chong School of Science and Technology Kwansei Gakuin University Japan [email protected] Hiroyuki Ohsaki School of Science and Technology Kwansei Gakuin University Japan [email protected] Bryan Ng School of Engineering & Computer Science Victoria University of Wellington New Zealand [email protected] Abstract 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. I Introduction The paradigm of large language models (LLMs) is rapidly shifting from monolithic, single-turn systems to dynamic, multi-agent systems, where autonomous agents collaborate to solve complex problems [ 1 , 2 ] . This evolution unlocks transformative potential in high-stakes domains such as automated financial compliance, software engineering, and scientific research, in which tasks can be delegated and synthesised by specialised AI agents. This collaborative model, however, also presents a fundamental challenge to the principles of responsible AI: how can interacting agents reliably trust each other’s outputs as these systems are increasingly deployed in real-world applications? This fundamental challenge arises when one agent generates an output sequence, and another agent, acting independently, must determine whether this output is the authentic result of the computation and genuinely produced by the designated LLM under the specified conditions (e.g., exact prompt, configuration, and constraints). Establishing such provenance and integrity is essential in increasingly complex and autonomous multi-agent workflows, where erroneous or unverified outputs could propagate silently and have cascading, safety-critical consequences, especially in regulated sectors such as finance and healthcare [ 3 , 4 ] . For example, a recent discussion paper from Malaysia’s central bank, Bank Negara Malaysia (BNM), highlights the critical need for accountability mechanisms to ensure responsible AI adoption in the financial sector [ 5 ] . This regulatory focus implies a potentially growing demand for crucial, auditable trails to ensure AI-generated reports adhere to certified model standards and to enhance accountability in the near future. Addressing this challenge at scale requires a validation mechanism built on the principle of asymmetric effort, also known as asymmetric computation. This principle dictates that the computational cost required to verify the correctness of a task must be significantly cheaper, ideally by orders of magnitude lower than the cost to perform the original task. A canonical example of this principle is the Proof-of-Work (PoW) consensus mechanism used in blockchain networks [ 6 ] . A miner must expend a vast amount of computational energy (trillions of hashes) to solve a difficult puzzle, representing the work. Once a solution is found, any node on the network can verify its correctness with a single, near-instantaneous calculation. Here, the effort is highly asymmetric as the verification is exceptionally cheap compared to the immense cost of the original computation. While our framework does not use a blockchain, this principle of low-cost verification is the bedrock of our approach to establish trust in multi-agent systems. Central to this challenge is the lack of efficient, scalable mechanisms for agents to verify the computational integrity of each other’s outputs in LLMs [ 7 ] . There is currently no direct method to verify the output of a LLM with true asymmetric effort. Verifying generative work naively requires re-running the same expensive inference process. This cost is significant as the generation of output tokens is priced substantially higher than the processing of input tokens by commercial API providers, often by a factor of 3x to 5x, reflecting the higher computational demand of generation [ 8 , 9 ] . To address this gap, we propose a validation framework that achieves asymmetric effort through tractable mechanism. We imagine a scenario with one agent acting as the generator and multiple agents as validators. Our framework achieves an efficient, system-wide verification process by leveraging the deterministic and autoregressive nature of LLMs and probabilistic verification. Exploiting these properties, however, introduces a critical requirement, i.e., a computationally homogeneous environment. Although this confines the framework to controlled ecosystems, it establishes a vital baseline for tractable low-cost verification with asymmetrical effort. The remainder of this paper is organised as follows. Section II contextualises our contribution by reviewing related work in multi-agent systems, LLM output verification, and the principles of verifiable computation. Section III details of our proposed framework, presenting the core mechanisms of targeted validation and probabilistic verification. Section IV presents our experimental validation, where we quantify the tractable asymmetric effort of our approach. Finally, Section V concludes the paper and discusses avenues for future work. II Related Work Building on the principles of verifiable computation and asymmetric effort discussed in Section I , this section positions our work within the existing academic landscape. We review key literature across three relevant domains to highlight the specific gaps our framework addresses. First, we explore trust and robustness mechanisms in multi-agent systems. Second, we examine current approaches to verifying LLM reasoning and outputs. Finally, we discuss the foundations of verifiable computation to differentiate our framework from formal cryptographic methods. II-A Trust and Robustness in Multi-Agent Systems Multi-agent systems have traditionally confronted the challenge of establishing trust and accountability among decentralised, heterogeneous agents. Early solutions focused on reputation-based mechanisms [ 10 , 11 ] , while later work introduced game-theoretic incentives to foster cooperation and reduce deception [ 12 ] . The need for such mechanisms is amplified in the high-stakes, regulated environments mentioned earlier, where unverified agent actions can carry significant financial or safety-critical consequences. The emergence of LLM-based agents has introduced novel challenges. These LLM agents often exhibit complex behaviours, i.e., unforeseen patterns of interaction that arise from the interplay of multiple agents. They can be difficult to interpret, predict, or control [ 13 ] . Such dynamics are further explored in frameworks dedicated to emergent multi-agent behaviours [ 14 ] and in studies documenting the spontaneous formation of social conventions among LLM-agent populations [ 15 ] . A particularly acute issue is that LLM agents are prone to hallucinations, i.e., generating outputs that are plausible and coherent, but factually incorrect or misleading. Recent theoretical and empirical work shows that hallucination is an inherent limitation of LLM architectures, unavoidable in both single and multi-agent settings [ 13 , 16 ] , and surveys confirm

Read the complete text