Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Autoregressive LLM outputs are cheaply auditable by regenerating random segments under identical hardware.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

T0 review · deepseek-v4-flash

2026-08-04 17:07 UTC pith:GYA6U77B

load-bearing objection A clean but thinly tested idea: verify LLM outputs by re-generating random segments on identical hardware, with the entire mechanism resting on an untested determinism assumption. the 3 major comments →

arxiv 2509.11068 v1 pith:GYA6U77B submitted 2025-09-14 cs.AI

Tractable Asymmetric Verification for Large Language Models via Deterministic Replicability

classification cs.AI
keywords LLM verificationasymmetric computationdeterministic replicabilityprobabilistic verificationmulti-agent trusttargeted validationtamper detection
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper tries to establish that LLM outputs in multi-agent systems can be verified with asymmetric effort, meaning checking a response costs much less than generating it. The mechanism relies on deterministic replicability: the same model, with the same prompt and environment, should reproduce the same continuation tokens. By having validators regenerate small random chunks of the output and compare them, the framework detects tampering with a tunable probability. Because the check only regenerates a slice of the sequence, it is far cheaper than full re-generation; the paper reports a 12.41x speedup for a 50-token check. The framework is confined to strictly homogeneous execution environments, which the authors identify as a prerequisite.

Core claim

In the paper's own terms, the central discovery is the combination of targeted validation with distributed probabilistic verification. Starting from the proposition that an autoregressive LLM, given a prompt concatenated with the first j tokens of its own output, will deterministically produce the exact remaining tokens when external conditions are fixed, the authors derive a detection probability for tamper detection: P(Detect) = 1 - (C(k-f, r)/C(k, r))^q, where the output is split into k segments, f are tampered, each of q validators checks r random distinct segments. They demonstrate empirically that the detection probability matches this formula and that verifying the final 50 tokens of

What carries the argument

The load-bearing mechanism is deterministic replicability combined with random subsampling. Deterministic replicability states that an identical LLM under identical conditions regenerates the same continuation given the prompt plus prior output tokens; this turns validation into a comparison of regenerated tokens. Distributed probabilistic verification turns the otherwise intractable search for a tampered position into a sampling problem: each validator randomly selects a small number of segments, and the probability of missing all tampered segments drops exponentially with the number of validators. The central identity is the detection probability formula, which shows how detection scales w

Load-bearing premise

The framework stands or falls on the claim that an identical LLM on identical hardware and software will regenerate the exact same tokens for a given prefix; this positive case is asserted but not directly tested in the paper.

What would settle it

Run the same autoregressive model twice on the same GPU with the same seed, same prompt, and the same software versions, and compare the full output token by token; if any token differs, deterministic replicability fails. A more targeted falsifier is to reproduce the 792-token response and the 50-token validation on identical hardware and verify both the exact token match and the claimed 12.41x time ratio.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • If the central claim is correct, validators can audit LLM outputs without re-running full inference, making multi-agent systems practically auditable in controlled deployments.
  • The detection probability formula gives system designers a direct way to tune security: increase q or r to reach desired detection rates, as shown for k=20, f=2.
  • The framework specifically counters cost evasion (cheaper model substitution) and malicious content injection (small tampered segments), the two threats in its threat model.
  • Because verification is independent per validator, the workload spreads across agents without any single validator bearing full regeneration cost.
  • The requirement of a homogeneous execution environment means deployments should use standardized cloud instances or version-controlled containers for the framework to work.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the framework's usefulness hinges on the untested positive case of same-hardware determinism; if even identical GPUs with the same software stack produce token differences (e.g., due to nondeterministic kernel execution), the whole approach fails, so a natural next experiment is a bitwise reproducibility test on identical hardware.
  • Editorial inference: the same probabilistic scheme could be adapted to fuzzy verification that tolerates small numeric differences, which would relax the strict homogeneity requirement the paper names as future work.
  • Editorial inference: the 12.41x speedup is for a particular model and hardware, but the cost ratio should generalize roughly linearly with the fraction of tokens regenerated, so longer checks trade off cost against detection probability in a predictable way.
  • Editorial inference: the framework only verifies that a claimed model was literally run on the stated prompt; it does not validate reasoning quality, so it is complementary to, not a replacement for, output-quality checks.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes a verification framework for LLM outputs in multi-agent systems. It relies on deterministic replicability: under identical hardware/software/seed conditions, an autoregressive LLM reproduces the same tokens from a given prefix. The framework lets a validator construct a prompt by concatenating the original prompt with a prefix of the output, regenerate the remaining tokens, and compare them to the original output. To avoid exhaustive checking, the scheme divides an output into k segments, assumes f tampered segments, and has q validators each randomly checking r segments. The paper derives the detection probability P(Detect) = 1 - (C(k-f,r)/C(k,r))^q and validates it with Monte Carlo simulation. It also reports timing experiments on Llama 3 showing that verifying the last 50 tokens of a 792-token response takes 2.59 s versus 32.13 s for full generation, a 12.41x asymmetric effort ratio. The paper further reports that validation across two different GPU models fails, and concludes that a homogeneous computational environment is required.

Significance. If the deterministic-replicability premise holds, the framework offers a simple, parameter-free method for probabilistic output auditing at substantially lower cost than full regeneration. Equation (3) is mathematically correct for the stated sampling scheme, and the Monte Carlo validation in Figure 3 is consistent. The approach is notable for avoiding fitted parameters and for providing an explicit, tunable trade-off between validation effort and detection probability. However, the central premise is external to the derivation and is not positively tested. The paper's own text in Section IV-A explicitly declines to test same-hardware determinism, and Section IV-C only demonstrates the negative cross-GPU case. Since the entire mechanism collapses if token-exact replication fails on identical stacks, the contribution is conditional on an unverified empirical claim. The stress-test concern lands squarely on this gap. The combinatorial derivation itself is sound but does not, by itself, establish practical security.

major comments (3)
  1. [Section III-B and IV-A] The load-bearing assumption is deterministic replicability on identical hardware/software, stated in Section III-B. Section IV-A explicitly declines to test it: 'the output of a targeted validation will always align with the corresponding portion of the original sequence in the controlled conditions. Hence, we will not revisit it here.' This is not acceptable for a central premise. The only empirical evidence in Section IV-C is a negative result on different GPU models (RTX 4000 Ada vs. A40), which does not establish that the same GPU and software stack are token-exact. Nondeterministic CUDA kernels, atomic operations, thread scheduling, or version drift can create differences even on identical hardware. Citations [25]–[27] are about stochastic decoding choices and reproducibility reporting, not a direct demonstration of token-exact determinism. The paper needs a positive experiment: rep
  2. [Section III-C, Eq. (3)] The detection probability formula assumes the tampered segments are fixed before validators sample, and that the generator cannot adapt to the validators' choices. The paper does not state this as a security assumption or specify a commitment mechanism. If a malicious generator can choose which f segments to tamper after observing the validators' random queries, or if validators' random seeds are predictable, the uniform-sampling model in Eq. (3) no longer applies and the detection probability can drop to zero. A practical deployment needs a delayed-randomness or commit-reveal protocol. Also, Figure 3 is a Monte Carlo simulation of the same combinatorial sampling scheme; it validates the algebra and implementation, but it is not an empirical security test against an actual adversary. The paper should distinguish these and state what security guarantees are proved versus assumed.
  3. [Section IV-A, Table I] The asymmetric effort ratio of 12.41x is based on a single run with no variance, confidence intervals, or specification of how prompt processing and model loading are counted. Verification of the last 50 tokens requires processing a 742-token prefix and generating 50 tokens; full generation processes a short prompt and generates 792 tokens. The cost composition differs, and the reported ratio may depend on the specific implementation, GPU, batch size, and whether KV-cache reuse or graph compilation is used. I recommend multiple trials with mean/standard deviation and a clear statement of the experimental conditions (decode strategy, temperature, seed, max new tokens, prompt-processing times).
minor comments (4)
  1. [Section III-C] Typographical and notation issues: 'r distinct segment' should be 'r distinct segments'; the set notation for tampered segments is garbled by LaTeX braces ('n{˙y}1 ,· · ·,{˙y}f o' renders poorly). The text says 'tuneable' and 'tunable' inconsistently; 'tunable' is fine. The parameter f is used both as the count of tampered segments and as an index in the notation; please clarify.
  2. [Section IV-A] The experimental section does not state the decoding parameters used for Llama 3 (temperature, top-p, seed, max_new_tokens, batch size). Since deterministic replicability depends on these, please report them. Also note whether the final 50-token verification was run from the exact prefix of the original generation, and whether the output was produced in a single generation call or with any control-flow features that could affect determinism.
  3. [Section IV-C] The phrase 'we posit that a standardised execution environment ... is a prerequisite' is appropriate, but the paragraph conflates 'different GPU models produce non-identical outputs' with 'identical stacks are deterministic.' Please separate the negative cross-hardware result from the unverified same-hardware claim, and consider stating explicitly that the same-hardware case remains an open empirical question in this paper.
  4. [Section III-B] References [25]–[27] are not strong evidence for the 'deterministic nature' of LLMs under controlled conditions. [25] discusses nucleus sampling and degeneration; [26] is about reproducibility reporting; [27] contrasts stochastic and deterministic decision patterns in LLMs. None demonstrate token-exact replication on identical hardware. Either add direct experiments or replace these citations with sources that actually establish the property (e.g., reproducibility studies of HuggingFace transformers on fixed hardware).

Circularity Check

0 steps flagged

No significant circularity: Eq. (3) is an exact combinatorial result, the determinism premise is an external assumption, and the untested same-hardware determinism is a correctness risk rather than a circular step.

full rationale

The paper's derivation chain is not circular. Deterministic replicability (Section III-B) is stated as an external premise about autoregressive LLMs under homogeneous conditions, supported by external citations [25]-[27]; it is not derived from the paper's own formulas, and none of those citations are self-citations of the present authors. The detection probability P(Detect) in Eq. (3) follows by exact combinatorial counting from the sampling model in Eq. (2), with no fitted parameters. The Section IV-B simulation implements exactly the same uniform-without-replacement sampling process used to define Eq. (2)-(3), so the near-perfect agreement is a self-consistency check rather than an independent empirical test; this weakens the evidence but does not make the formula circular, since the formula is a mathematical consequence of the stated model. The main quantitative claim, a 12.41x asymmetric effort ratio, is a direct wall-clock measurement comparing targeted validation to full regeneration and is not obtained by fitting the theory. The acknowledged limitation that positive same-hardware, same-software token-exact determinism is asserted but not tested (Section IV-A: 'we will not revisit it here'; Section IV-C only demonstrates cross-GPU mismatches) is an external validity risk, not a circular derivation. No load-bearing self-citation, imported uniqueness theorem, or ansatz-smuggling-via-citation was found. Overall circularity score: 0.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The framework introduces no new physical or mathematical entities; it relies on an unverified deterministic-replicability assumption and standard independence assumptions. No free parameters are fitted; k, f, r, q are tunable design choices.

axioms (5)
  • domain assumption Autoregressive LLMs are exactly deterministic under identical conditions (same model, seed, hardware, software).
    The entire verification mechanism requires exact token replication. Stated in Section III-B and explicitly not tested in Section IV-A.
  • domain assumption All agents operate in a computationally homogeneous environment.
    The framework requires identical hardware and software stacks across generators and validators; Section IV-C shows cross-GPU failure.
  • standard math Validators sample r distinct segments uniformly at random without replacement.
    The detection probability (Eq. 3) is derived under this sampling model.
  • domain assumption Validator selections are independent of each other.
    The failure probability is raised to the q-th power, requiring independent sampling across validators.
  • domain assumption A detected mismatch can be broadcast and trigger consensus-based rejection.
    The framework assumes a communication mechanism for propagating detection, but no protocol is specified (Section III-C).

pith-pipeline@v1.3.0-alltime-deepseek · 8133 in / 10703 out tokens · 115131 ms · 2026-08-04T17:07:07.211432+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Tractable Asymmetric Verification for Large Language Models via Deterministic Replicability." pith.science (2026). https://pith.science/paper/GYA6U77B

@misc{pith2026250911068,
  author       = {Pith},
  title        = {Pith review of: Tractable Asymmetric Verification for Large Language Models via Deterministic Replicability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GYA6U77B}},
  note         = {Machine review of arXiv:2509.11068}
}
Share X Bluesky LinkedIn Reddit HN
read the original 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.

Figures

Figures reproduced from arXiv: 2509.11068 by Bryan Ng, Hiroyuki Ohsaki, Zan-Kai Chong.

Figure 1
Figure 1. Figure 1: Verifying LLM generated content via deterministic replicability. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of the distributed probabilistic verification mech [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Validation of the probabilistic verification with [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. When Planning Fails Despite Correct Execution: On Epistemic Calibration for LLM-Based Multi-Agent Systems

    cs.AI 2026-05 unverdicted novelty 6.0

    Introduces EPC-AW to mitigate epistemic miscalibration in LLM multi-agent planning via consistency-based selection and refinement, reporting 9.75% average success improvement.

Reference graph

Works this paper leans on

31 extracted references · 15 linked inside Pith · cited by 1 Pith paper

  1. [1]

    A survey on LLM-based multi-agent system: Recent advances and new frontiers in application,

    S. Chen, Y . Liu, W. Han, W. Zhang, and T. Liu, “A survey on LLM-based multi-agent system: Recent advances and new frontiers in application,” 2025. [Online]. Available: https://arxiv.org/abs/2412.17481

  2. [2]

    Large language model agent: A survey on methodology, applications and challenges,

    J. Luo, W. Zhang, Y . Yuan, Y . Zhao, J. Yang, Y . Gu, B. Wu, B. Chen, Z. Qiao, Q. Long, R. Tu, X. Luo, W. Ju, Z. Xiao, Y . Wang, M. Xiao, C. Liu, J. Yuan, S. Zhang, Y . Jin, F. Zhang, X. Wu, H. Zhao, D. Tao, P. S. Yu, and M. Zhang, “Large language model agent: A survey on methodology, applications and challenges,” 2025. [Online]. Available: https://arxiv...

  3. [3]

    Responsible innovation: A strategic framework for financial llm integration,

    A. Tavasoli, M. Sharbaf, and S. M. Madani, “Responsible innovation: A strategic framework for financial llm integration,” 2025. [Online]. Available: https://arxiv.org/abs/2504.02165

  4. [4]

    Evaluating large language models for use in healthcare: A framework for translational value assessment,

    S. Reddy, “Evaluating large language models for use in healthcare: A framework for translational value assessment,”Informatics in Medicine Unlocked, vol. 41, p. 101304, 2023

  5. [5]

    Discussion paper on artificial intelligence and machine learning in the financial sector,

    Bank Negara Malaysia, “Discussion paper on artificial intelligence and machine learning in the financial sector,” Kuala Lumpur, Malaysia, 2025

  6. [6]

    Bitcoin: A peer-to-peer electronic cash system,

    S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” ht- tps://bitcoin.org/bitcoin.pdf, oct 2008

  7. [7]

    Survey of hallucination in natural language generation,

    Z. Ji, N. Lee, R. Frieske, T. Yu, D. Su, Y . Xu, E. Ishii, Y . J. Bang, A. Madotto, and P. Fung, “Survey of hallucination in natural language generation,”ACM Computing Surveys, vol. 55, no. 12, pp. 1–38, Mar

  8. [8]

    Models and pricing,

    Anthropic, “Models and pricing,” https://www.anthropic.com/pricing, 2025, accessed: 2025-08-24

  9. [9]

    Models - OpenAI API,

    OpenAI, “Models - OpenAI API,” https://openai.com/api/pricing/, 2025, accessed: 2025-08-24

  10. [10]

    Trust in multi-agent systems,

    J. Sabater and C. Sierra, “Trust in multi-agent systems,”The Knowledge Engineering Review, vol. 19, no. 1, pp. 1–25, 2004

  11. [11]

    Review on computational trust and reputation models,

    J. Sabater-Mir and C. Sierra, “Review on computational trust and reputation models,”Artificial Intelligence Review, vol. 24, pp. 33–60, 2005

  12. [12]

    Computational trust and reputation models for open multi-agent systems: a review,

    I. Pinyol and J. Sabater-Mir, “Computational trust and reputation models for open multi-agent systems: a review,”Artificial Intelligence Review, vol. 40, no. 1, pp. 1–25, 2013

  13. [13]

    Hallucination is inevitable: An innate limitation of large language models,

    Z. Xu, S. Jain, and M. Kankanhalli, “Hallucination is inevitable: An innate limitation of large language models,” 2025. [Online]. Available: https://arxiv.org/abs/2401.11817

  14. [14]

    Maebe: Multi-agent emergent behavior framework,

    S. Erisken, T. Gothard, M. Leitgab, and R. Potham, “Maebe: Multi-agent emergent behavior framework,” 2025. [Online]. Available: https://arxiv.org/abs/2506.03053

  15. [15]

    Emergent social conventions and collective bias in llm populations,

    A. F. Ashery, L. M. Aiello, and A. Baronchelli, “Emergent social conventions and collective bias in llm populations,” 2025. [Online]. Available: https://arxiv.org/abs/2410.08948

  16. [16]

    On the fundamental impossibility of hallucination control in large language models,

    M. P. Karpowicz, “On the fundamental impossibility of hallucination control in large language models,” 2025. [Online]. Available: https://arxiv.org/abs/2506.06382

  17. [17]

    A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions,

    L. Huang, W. Yu, W. Ma, W. Zhong, Z. Feng, H. Wang, Q. Chen, W. Peng, X. Feng, B. Qin, and T. Liu, “A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions,”ACM Transactions on Information Systems, vol. 43, no. 2, pp. 1–55, Jan. 2025. [Online]. Available: http://dx.doi.org/10.1145/3703155

  18. [18]

    Trust me, i’m wrong: Llms hallucinate with certainty despite knowing the answer,

    A. Simhi, I. Itzhak, F. Barez, G. Stanovsky, and Y . Belinkov, “Trust me, i’m wrong: Llms hallucinate with certainty despite knowing the answer,” 2025. [Online]. Available: https://arxiv.org/abs/2502.12964

  19. [19]

    Judging llm-as-a-judge with mt-bench and chatbot arena,

    L. Zheng, W.-L. Chiang, Y . Sheng, S. Zhuang, Z. Wu, Y . Zhuang, Z. Lin, Z. Li, D. Li, E. P. Xing, H. Zhang, J. E. Gonzalez, and I. Stoica, “Judging llm-as-a-judge with mt-bench and chatbot arena,”

  20. [20]

    Toward verifiable misinformation detection: A multi-tool llm agent framework,

    Z. Cui, T. Huang, C.-E. Chiang, and C. Du, “Toward verifiable misinformation detection: A multi-tool llm agent framework,” 2025. [Online]. Available: https://arxiv.org/abs/2508.03092

  21. [21]

    Available: https://arxiv.org/abs/2306.05685

    [Online]. Available: https://arxiv.org/abs/2306.05685

  22. [22]

    Airepr: An analyst- inspector framework for evaluating reproducibility of llms in data science,

    Q. Zeng, C. Jin, X. Wang, Y . Zheng, and Q. Li, “Airepr: An analyst- inspector framework for evaluating reproducibility of llms in data science,” 2025. [Online]. Available: https://arxiv.org/abs/2502.16395

  23. [23]

    Codeagents: A token-efficient framework for codified multi-agent reasoning in llms,

    B. Yang, X. He, H. Gao, Y . Cao, X. Li, and D. Hsu, “Codeagents: A token-efficient framework for codified multi-agent reasoning in llms,”

  24. [24]

    zkllm: Zero knowledge proofs for large language models,

    H. Sun, J. Li, and H. Zhang, “zkllm: Zero knowledge proofs for large language models,” 2024. [Online]. Available: https://arxiv.org/abs/2404.16109

  25. [25]

    The curious case of neural text degeneration,

    A. Holtzman, J. Buys, L. Du, M. Forbes, and Y . Choi, “The curious case of neural text degeneration,” 2020. [Online]. Available: https://arxiv.org/abs/1904.09751

  26. [26]

    A survey of verifiable computation,

    Z. Wan, J. Qin, and B. Niu, “A survey of verifiable computation,”Mobile Networks and Applications, vol. 22, no. 3, pp. 438–453, 2017

  27. [27]

    Do language models have bayesian brains? distinguishing stochastic and deterministic decision patterns within large language models,

    A. Y . Cui and P. Yu, “Do language models have bayesian brains? distinguishing stochastic and deterministic decision patterns within large language models,” 2025. [Online]. Available: https://arxiv.org/abs/2506.10268

  28. [28]

    Meta-llama-3-8b-instruct,

    AI@Meta, “Meta-llama-3-8b-instruct,” https://huggingface.co/meta- llama/Meta-Llama-3-8B-Instruct, 2024, accessed on: 2025-09-05. [Online]. Available: https://huggingface.co/meta-llama/Meta-Llama-3- 8B-Instruct

  29. [29]

    Show your work: Improved reporting of experimental results,

    J. Dodge, S. Gururangan, D. Card, R. Schwartz, and N. A. Smith, “Show your work: Improved reporting of experimental results,” 2019. [Online]. Available: https://arxiv.org/abs/1909.03004

  30. [2023]

    Available: http://dx.doi.org/10.1145/3571730

    [Online]. Available: http://dx.doi.org/10.1145/3571730

  31. [2025]

    Available: https://arxiv.org/abs/2507.03254

    [Online]. Available: https://arxiv.org/abs/2507.03254