Pith. sign in

REVIEW 2 major objections 5 minor 119 references

Robust Detection of Watermarks for Large Language Models Under Human Edits

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that a truncated goodness-of-fit test reaches the information-theoretic detection boundary for Gumbel-max watermarks under human edits, without knowing the edit level or the token distributions.

desk verdict A real phase-transition result for robust watermark detection, with a clean adaptive test, once you accept the mixture model—but the edit model is narrower than the title suggests. read the letter →

arxiv 2411.13868 v3 pith:OCFDUJSV submitted 2024-11-21 stat.ME cs.CLcs.LGmath.STstat.MLstat.TH

Xiang Li , Feng Ruan , Huiyuan Wang , Qi Long , Weijie J. Su This is my paper · ORCID
classification stat.MEcs.CLcs.LGmath.STstat.MLstat.TH MSC 62F0362F0562G10
keywords watermarkdetectionlargelanguagemodelshumaneditsmixturemodelgoodness-of-fittestHigherCriticismsparseadaptiveoptimality
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks when a watermark embedded in LLM-generated text can still be detected after humans edit the text. It models editing as a Bernoulli mixture: each token either keeps its watermark signal with probability $\epsilon_n$ or becomes pure noise. In the regime where both the surviving-signal fraction and the signal strength shrink polynomially ($\epsilon_n \asymp n^{-p}$ and $\Delta_n \asymp n^{-q}$), the paper proves a phase boundary $q+2p=1$: below it detection is asymptotically possible, above it impossible. Tr-GoF, a truncated goodness-of-fit test, attains this boundary adaptively, while sum-based score tests only reach $q+p=1/2$. So one parameter-free test matches the detectability limit that an impractical likelihood-ratio test would need full knowledge of the edit rate and the token distributions to achieve.

What carries the argument

The central object is the truncated goodness-of-fit statistic $S^+_n(s) = \sup_{r\in[p^+,1)} K^+_s(F_n(r),r)$, where $F_n$ is the empirical CDF of the p-values $p_t=1-Y_t$, $Y_t$ is the pivotal statistic attached to token $t$, and $K_s$ is the $\phi_s$-divergence between two Bernoulli distributions. The truncations exclude the smallest p-values and keep only the region where the empirical CDF exceeds the null CDF, removing the heavy-tail outliers that would otherwise dominate the statistic. At $s=2$ the statistic is exactly Higher Criticism, and the paper shows it grows like $n^{1/2-p-q/2}$ under the alternative while only reaching $\log\log n$ under the null, which is what pins the boundary $q+2p=1$.

What would settle it

Take a watermarked text, delete or replace a contiguous 5% block of tokens rather than editing tokens at random, and keep replacements semantically close; at parameter values near the boundary such as $p=0.3$, $q=0.4$, observe whether Tr-GoF's Type I plus Type II error still tends to zero as $n$ grows. Under the paper's Bernoulli-mixture model it must; if the block-edit alternative is the true one, the stated boundary need not hold.

Watch

Extended reading notes

Core claim

On its own terms, the discovery is that robust watermark detection reduces to a sparse-mixture detection problem on pivotal statistics, and that the optimal boundary is reached by comparing the empirical CDF of the p-values against the uniform null CDF instead of accumulating scores. Theorem 4.3 states that when $q+2p<1$, the Tr-GoF statistic with any truncation constant $c^+_n \le 1/n$ and $s \in [-1,2]$ drives both Type I and Type II error to zero without knowledge of $p$, $q$, $\epsilon_n$, or the next-token distributions. Theorem 4.4 states that any sum-based rule built from a parameter-free non-decreasing score function has detection boundary only $q+p=1/2$. Theorem 4.5 states that in the constant-edit regime Tr-GoF attains the optimal $\mathcal{P}_\Delta$-efficiency $D_{\mathrm{KL}}(\mu_0, (1-\epsilon)\mu_0 + \epsilon \mu_{1,P^\star_\Delta})$, again without knowing $\epsilon$ or $\Delta$.

Load-bearing premise

The load-bearing premise is that each edited token is pure noise and each unedited token keeps its watermark independently with the same probability $\epsilon_n$; if human edits arrive in blocks or leave contextual traces in the pseudorandom statistics, the data are no longer the Bernoulli mixture the theorems assume.

Editorial extensions

If this is right

  • Below the boundary $q+2p=1$, Tr-GoF separates watermarked from human-written text with both error probabilities tending to zero, and it does so without tuning to the problem.
  • Separating at the optimal boundary requires abandoning sum-based statistics: every parameter-free non-decreasing score rule is confined to $q+p=1/2$ in the sparse regime.
  • When the edit fraction and token-distribution regularity are constant, Tr-GoF reaches the optimal exponential decay rate of Type II error, matching the least-favorable benchmark without knowing $\epsilon$ or $\Delta$.
  • Empirically, on open-source LLMs, Tr-GoF keeps Type I error controlled and achieves lower Type II error than baselines at low temperature, with the largest edit-tolerance limits in substitution, insertion, and deletion experiments.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The truncation strategy should transfer to other watermark decoders whose pivotal statistics have a known null distribution, since the CDF comparison treats the decoder as a black box once pivots are defined.
  • If real edits are clustered rather than per-token independent, the true alternative is autocorrelated and the boundary $q+2p=1$ may no longer be the right description; estimating the watermark fraction or exploiting spatial edit structure could recover some of the loss.
  • Because the impossibility direction of Theorem 4.2 is an upper bound over all tests, the boundary $q+2p=1$ is plausibly information-theoretic for the Gumbel-max watermark, not just a property of p-value-based methods.
  • In deployment, the tuning-free form suggests setting $s=2$ (Higher Criticism) with a Monte-Carlo threshold as a drop-in robust detector; the main cost is computing the pseudorandom pivots, which the detector already needs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies detection of the Gumbel-max watermark when LLM-generated text may have been edited by humans. It models edits as a per-token Bernoulli mixture: with probability εn a token retains its watermark signal, and otherwise it behaves as pure noise with pivot statistic drawn from µ0. Under an asymptotic regime with watermark fraction εn ≍ n^{-p} and NTP singularity Δn ≍ n^{-q}, the paper proves that the optimal detection boundary is q+2p=1, that the proposed truncated goodness-of-fit test (Tr-GoF) attains this boundary adaptively without knowing p, q, εn, or the NTP distributions, and that sum-based detection rules are limited to the suboptimal boundary q+p=1/2. In the constant-edit regime, the paper further claims that Tr-GoF achieves the optimal P∆-efficiency rate. The theoretical results are supplemented by simulations and experiments on OPT-1.3B and Sheared-LLaMA-2.7B, including random, adversarial, and roundtrip-translation edits.

Significance. If the results hold as stated, this is a substantial contribution to the statistical theory of LLM watermark detection. The paper gives a concrete phase transition, a parameter-free test that provably reaches it, and a rigorous explanation of why additive scoring rules are fragile under edits. The proofs are theorem-driven rather than fit to simulations, the simulation boundaries in Figures 6 and 7 align with the theory, and the source code is publicly available. The main value is the demonstration that a goodness-of-fit statistic can be adaptively optimal in a sparse mixture setting with autoregressive, time-varying signal distributions. The scope of these guarantees, however, depends on the mixture assumption for human edits, and that assumption is the main point of concern.

major comments (2)
  1. [Assumption 4.1(b) / Eq. (4) / Lemma A.2] The load-bearing assumption is that each edited token is independent of the pseudorandom vector ζt, so its pivot is exactly µ0. This is contradicted by the paper's own WordNet synonym-substitution protocol in Supplementary C.1. When the m-token context preceding position t is unedited, the verifier's recomputed ζt equals the original pseudorandom vector used to generate the token, and a replacement chosen as a synonym of the watermarked token is a function of that vector. For |W|=2 with P=(1/2,1/2), swapping the observed token to the other one yields P(Yt≤r | edited)=2r−r² rather than r. Consequently the mixture in Eq. (4) does not describe the actual edited-token distribution under content-dependent edits, and the clean conditional-mixture identity in Lemma A.2, on which Theorems 4.1–4.5 rely, is misspecified. The q+2p=1 boundary and the optimality of Tr-GoF are therefore proved for an edit process that is independent of the visible watermarked text, not for the editing process featured in the title and experiments. The authors should either prove that the stated results are insensitive to this dependence, add a misspecification analysis, or explicitly restrict the theoretical claims.
  2. [Remark 4.2 / Appendix Theorem 4.2] The relaxed-assumption statement in Remark 4.2 is inverted relative to the appendix. The main text says merging follows from q+2p>1 with P1:n⊂P∆n and separation from q+2p<1 with P1:n⊂Pc∆n, while the appendix's restated Theorem 4.2 and the proof in Section A.2 use the opposite inclusions: merging is proved for P1:n⊂Pc∆n and separation for P1:n⊂P∆n. Since P∆n is the class with Δ(Pt)≥Δn, the appendix version is the correct one for a signal that strengthens with Δn. Please correct Remark 4.2 so that the main text and appendix agree.
minor comments (5)
  1. [Section 6.3] In the paragraph on edit tolerance limits, 'reported in Figure 1' should read 'reported in Table 1'.
  2. [Section 5.3 / footnote 4] The formula in footnote 4 is garbled; the displayed lower bound on q should be written cleanly as q ≥ log(|W|/(|W|-1)) / log n to be readable.
  3. [Theorem 4.5] The optimal-efficiency result is stated for s∈(0,1) and c+_n=0, but the surrounding text and Figure 4 present it as a property of Tr-GoF generally; please state these restrictions wherever the result is summarized.
  4. [Section 6.1] The sentence beginning 'Among ∆ ∈ 0.1, 0.2, 0.3' is grammatically incomplete; please revise.
  5. [Algorithm 2] The notation 'ew' in the pseudocode should be 'w'; the current typesetting appears to come from an unresolved LaTeX macro.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Tr-GoF's optimality is derived from explicit assumptions via Hellinger and empirical-process arguments; self-citations to the authors' companion framework are not used as fitted inputs.

full rationale

The paper's derivation chain is theorem-driven rather than fit-driven. The alternative hypothesis is defined by Assumption 4.1(b) as a per-token Bernoulli mixture, and the detection boundary q+2p=1 is obtained from explicit Hellinger computations (Lemmas A.3-A.5) and empirical-process bounds (Lemmas A.8, A.11, A.12), not from any calibrated parameter. Tr-GoF's rejection rule uses only the sample size through (1+delta)loglog n and permits any 0 <= c+_n <= 1/n and any s in [-1,2], so the method does not use p, q, epsilon_n, or the NTP distributions in its construction. Theorem 4.5's optimal P-Delta-efficiency is proven via large-deviation results for Kolmogorov-Smirnov-type statistics [55, 64] and does not insert the claimed DKL value as an input. Self-citations to [47] supply the P-Delta-efficiency definition and the 'Working Hypothesis' of pseudorandomness, but these are stated assumptions or formal definitions with independent content, not unverified results that force the conclusions. The strongest skeptical concern, that real content-dependent edits violate Assumption 4.1(b), is a model-misspecification/correctness risk rather than a circularity: the mathematical claims are conditional on that assumption and are not equivalent to it by construction. Overall, no circular step was found.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

Central claim rests on the mixture model and equal-singularity assumptions. The method itself has only hand-chosen, theoretically-insensitive parameters s and c+_n. No new entities are postulated.

free parameters (2)
  • s (phi-divergence index) = 1, 1.5, 2 in main LLM experiments; theorem allows any s in [-1,2]
    Hand-chosen in Algorithm 1. The optimality theorems are proven for any s in the range, so the choice is not load-bearing, but it is a user-set value.
  • c+_n (truncation threshold) = 1/n in most experiments, 10^-3 in edit tolerance; theorem allows 0 <= c+_n <= 1/n
    Hand-chosen stability parameter. Theory is insensitive to it. Not fitted to outcomes.
assumptions (5)
  • domain assumption Perfect pseudorandomness: the pseudorandom values ζt are i.i.d. and independent of the past (Assumption 4.1a).
    Standard in the watermarking literature; needed so the null distribution of the pivot is exactly µ0.
  • domain assumption Per-token edit mixture: each token is watermarked with probability εn and otherwise is pure noise independent of ζt (Assumption 4.1b).
    Load-bearing model of human edits; no clustering or partial signal. The whole H1 distribution and the phase boundary depend on it.
  • domain assumption Identical singularity: every NTP distribution has max probability 1-Δn with Δn ≍ n^{-q} (Assumption 4.2).
    Used in all phase-transition proofs. Remark 4.2 claims relaxation, but the main text statement there appears inconsistent with the appendix.
  • domain assumption Known null distribution for pivots: under H0 the pivots Yt are i.i.d. µ0 (uniform for Gumbel-max).
    Inherited from the pivot framework of Li et al. [47]; needed for p-values and the goodness-of-fit statistic.
  • standard math External large-deviation and empirical-process results, including the extreme value of the uniform empirical process, Theorem 2 in [55], and the lower bound in [64].
    Used in the proofs of Theorems 4.3 and 4.5 without full restatement.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Robust Detection of Watermarks for Large Language Models Under Human Edits." pith.science (2026). https://pith.science/paper/OCFDUJSV

@misc{pith2026241113868,
  author       = {Pith},
  title        = {Pith review of: Robust Detection of Watermarks for Large Language Models Under Human Edits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OCFDUJSV}},
  note         = {Machine review of arXiv:2411.13868}
}
read the original abstract

Watermarking has offered an effective approach to distinguishing text generated by large language models (LLMs) from human-written text. However, the pervasive presence of human edits on LLM-generated text dilutes watermark signals, thereby significantly degrading detection performance of existing methods. In this paper, by modeling human edits through mixture model detection, we introduce a new method in the form of a truncated goodness-of-fit test for detecting watermarked text under human edits, which we refer to as Tr-GoF. We prove that the Tr-GoF test achieves optimality in robust detection of the Gumbel-max watermark in a certain asymptotic regime of substantial text modifications and vanishing watermark signals. Importantly, Tr-GoF achieves this optimality \textit{adaptively} as it does not require precise knowledge of human edit levels or probabilistic specifications of the LLMs, in contrast to the optimal but impractical (Neyman--Pearson) likelihood ratio test. Moreover, we establish that the Tr-GoF test attains the highest detection efficiency rate in a certain regime of moderate text modifications. In stark contrast, we show that sum-based detection rules, as employed by existing methods, fail to achieve optimal robustness in both regimes because the additive nature of their statistics is less resilient to edit-induced noise. Finally, we demonstrate the competitive and sometimes superior empirical performance of the Tr-GoF test on both synthetic data and open-source LLMs in the OPT and LLaMA families.

Figures

Figures reproduced from arXiv: 2411.13868 by the authors.

Figure 1
Figure 1. How users modify ChatGPT’s response through edits such as substitution, deletion, [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Empirical study of detection methods for the Gumbel-max watermark. Statistical power [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Tr-GoF shows improved detection efficiency under the same setup as Figure [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (17 more)
Figure 4
Figure 4. Figure 4: P∆-efficiency rates of different detection methods for the Gumbel-max watermarks. RP∆ has non-smooth points when ∆ = 1 2 , 2 3 , 3 4 , . . . [47]. shows ε = 0.5. Here, hars, hlog, hind,δ, and hopt,∆0 represent commonly used sum-based detection rules, with δ = 0.5 and ∆…
Figure 5
Figure 5. Figure 5: Density histograms and powers of log(nS+ n (s)) for different values of s, with c + n = 1 n2 and (p, q) = (0.2, 0.5). The first row reports results under H0, while the second and third rows correspond to Hmix 1 in the M1 and M2 settings. The shaded region indicates the…
Figure 6
Figure 6. Figure 6: Empirical detection boundaries of Tr-GoFfor different values of [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: Empirical detection boundaries for sum-based detection rules [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]
Figure 8
Figure 8. Figure 8: Empirical Type I errors. We first evaluate the statistical power of consid￾ered detection methods using unmodified texts. Unlike in simulation studies, we cannot manipu￾late each NTP distribution Pt in language model experiments to ensure they are ∆-regular. How￾ever, …
Figure 9
Figure 9. Figure 9: Empirical Type II errors (top row) across different detection rules applied to the Gumbel [PITH_FULL_IMAGE:figures/full_fig_p020_9.png]
Figure 10
Figure 10. Figure 10: Effect of three random edits on Type II error across different temperatures at a fixed [PITH_FULL_IMAGE:figures/full_fig_p021_10.png]
Figure 11
Figure 11. Figure 11: Effect of adversarial edits on Type II error across different temperatures. [PITH_FULL_IMAGE:figures/full_fig_p023_11.png]
Figure 12
Figure 12. Figure 12: Effect of roundtrip translation on Type II error across different temperatures. [PITH_FULL_IMAGE:figures/full_fig_p023_12.png]
Figure 13
Figure 13. Figure 13: Density histograms and powers of log(nS+ n (s)) for different values of s with c + n = 0 and (p, q) = (0.2, 0.5). The first row presents results under H0, while the second and third rows display results under Hmix 1 , corresponding to the M1 and M2 settings, respectiv…
Figure 14
Figure 14. Figure 14: Frequency histograms for HC+ n with c + n = 1 n (top) and HC⋆ n (bottom). The dark area indicates the portion of the distribution that rejects H0 which is the the Type I error α under the null hypothesis H0 and the power 1 − β under the alternative hypothesis Hmix 1 .…
Figure 15
Figure 15. Figure 15: The smallest sum of Type I and Type II errors of [PITH_FULL_IMAGE:figures/full_fig_p057_15.png]
Figure 16
Figure 16. Figure 16: Empirical Type II errors (top row) on the C4 dataset across different detection rules [PITH_FULL_IMAGE:figures/full_fig_p060_16.png]
Figure 17
Figure 17. Figure 17: Effect of three random edits on Type II error across different temperatures at [PITH_FULL_IMAGE:figures/full_fig_p061_17.png]
Figure 18
Figure 18. Figure 18: Empirical Type II errors on Sheared-LLaMA-2.7B across different lengths of edited texts [PITH_FULL_IMAGE:figures/full_fig_p062_18.png]
Figure 19
Figure 19. Figure 19: Complete results of Type II error under adversarial edits across various temperatures [PITH_FULL_IMAGE:figures/full_fig_p063_19.png]
Figure 20
Figure 20. Figure 20: Complete results of Type II error under adversarial edits across various temperatures and [PITH_FULL_IMAGE:figures/full_fig_p064_20.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

119 extracted references · 63 canonical work pages

  1. [1]

    Watermarking of large language models, August 2023

    Scott Aaronson. Watermarking of large language models, August 2023. URLhttps://simons. berkeley.edu/talks/scott-aaronson-ut-austin-openai-2023-08-17

    2023

  2. [2]

    GPT-4 technical report

    Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. GPT-4 technical report. arXiv preprint arXiv:2303.08774, 2023. 24

    arXiv 2023

  3. [3]

    A learning algorithm for Boltzmann machines.Cognitive science, 9(1):147–169, 1985

    David H Ackley, Geoffrey E Hinton, and Terrence J Sejnowski. A learning algorithm for Boltzmann machines.Cognitive science, 9(1):147–169, 1985

    1985

  4. [4]

    Distribution-free tests for sparse heterogeneous mixtures

    Ery Arias-Castro and Meng Wang. Distribution-free tests for sparse heterogeneous mixtures. Test, 26:71–94, 2017

    2017

  5. [5]

    An intensive introduction to cryptography, lectures notes for Harvard CS 127

    Boaz Barak. An intensive introduction to cryptography, lectures notes for Harvard CS 127. https://intensecrypto.org/public/index.html, Fall 2021

    2021

  6. [6]

    On asymptotically optimal non-parametric criteria.Theory of Probability & Its Applications, 13(3):359–393, 1968

    AA Borokov and NM Sycheva. On asymptotically optimal non-parametric criteria.Theory of Probability & Its Applications, 13(3):359–393, 1968

    1968

  7. [7]

    Boundary-value problems for random walks and large deviations in function spaces

    Aleksandr A Borovkov. Boundary-value problems for random walks and large deviations in function spaces. Theory of Probability & Its Applications, 12(4):575–595, 1967

    1967

  8. [8]

    Language models are few-shot learners

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. InAdvances in Neural Information Processing Systems, volume 33, pages 1877–1901, 2020

    1901

Show all 119 references
  1. [9]

    Optimal detection of sparse mixtures against a given null distribution

    T Tony Cai and Yihong Wu. Optimal detection of sparse mixtures against a given null distribution. IEEE Transactions on Information Theory, 60(4):2217–2232, 2014

    2014

  2. [10]

    Optimal detection of heterogeneous and het- eroscedastic mixtures

    T Tony Cai, X Jessie Jeng, and Jiashun Jin. Optimal detection of heterogeneous and het- eroscedastic mixtures. Journal of the Royal Statistical Society Series B: Statistical Methodology, 73(5):629–662, 2011

    2011

  3. [11]

    Towards better statistical understanding of watermarking LLMs.arXiv preprint arXiv:2403.13027, 2024

    Zhongze Cai, Shang Liu, Hanzhao Wang, Huaiyang Zhong, and Xiaocheng Li. Towards better statistical understanding of watermarking LLMs.arXiv preprint arXiv:2403.13027, 2024

    2024 arXiv

  4. [12]

    Pseudorandom error-correcting codes

    Miranda Christ and Sam Gunn. Pseudorandom error-correcting codes. InAnnual International Cryptology Conference, pages 325–347. Springer, 2024

    2024

  5. [13]

    Undetectable watermarks for language models

    Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In Conference on Learning Theory, pages 1125–1139. PMLR, 2024

    2024

  6. [14]

    Routledge, 2017

    Ralph B D’Agostino.Goodness-of-fit-techniques. Routledge, 2017

    2017

  7. [15]

    Scalable watermarking for identifying large language model outputs

    Sumanth Dathathri, Abigail See, Sumedh Ghaisas, Po-Sen Huang, Rob McAdam, Johannes Welbl, Vandana Bachani, Alex Kaskasoli, Robert Stanforth, Tatiana Matejovicova, Jamie Hayes, Nidhi Vyas, Majd Al Merey, Jonah Brown-Cohen, Rudy Bunel, Borja Balle, Taylan Cemgil, Zahra Ahmed, Ki...

    2024

  8. [16]

    Cambridge university press, 2023

    Ilias Diakonikolas and Daniel M Kane.Algorithmic high-dimensional robust statistics. Cambridge university press, 2023

    2023

  9. [17]

    RL Dobrusin. A statistical problem arising in the theory of detection of signals in the presence of noise in a multi-channel system and leading to stable distribution laws.Theory of Probability & Its Applications, 3(2):161–173, 1958. 25

    1958

  10. [18]

    Higher criticism for detecting sparse heterogeneous mixtures

    David Donoho and Jiashun Jin. Higher criticism for detecting sparse heterogeneous mixtures. The Annals of Statistics, 32(3):962–994, 2004

    2004

  11. [19]

    Higher criticism for large-scale inference, especially for rare and weak effects.Statistical science, 30(1):1–25, 2015

    David Donoho and Jiashun Jin. Higher criticism for large-scale inference, especially for rare and weak effects.Statistical science, 30(1):1–25, 2015

    2015

  12. [20]

    AI watermarking must be watertight to be effective.Nature, 634:753, 2024

    Nature editorial. AI watermarking must be watertight to be effective.Nature, 634:753, 2024. URL https://www.nature.com/articles/d41586-024-03418-x

    2024

  13. [21]

    M. R. Farhangdoost and M. Kargar Dolatabadi. New inequalities for Gamma and Digamma functions. Journal of Applied Mathematics, 2014, 2014

    2014

  14. [22]

    Three bricks to consolidate watermarks for large language models

    Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS), pages 1–6. IEEE, 2023

    2023

  15. [23]

    GumbelSoft: Diversified language model watermarking via the GumbelMax-trick.arXiv preprint arXiv:2402.12948, 2024

    Jiayi Fu, Xuandong Zhao, Ruihan Yang, Yuansen Zhang, Jiangjie Chen, and Yanghua Xiao. GumbelSoft: Diversified language model watermarking via the GumbelMax-trick.arXiv preprint arXiv:2402.12948, 2024

    2024 arXiv

  16. [24]

    WaterMax: Breaking the LLM watermark detectability- robustness-quality trade-off

    Eva Giboulot and Furon Teddy. WaterMax: Breaking the LLM watermark detectability- robustness-quality trade-off. arXiv preprint arXiv:2403.04808, 2024

    2024 arXiv

  17. [25]

    Edit distance robust watermarks for language models.arXiv preprint arXiv:2406.02633, 2024

    Noah Golowich and Ankur Moitra. Edit distance robust watermarks for language models.arXiv preprint arXiv:2406.02633, 2024

    2024 arXiv

  18. [26]

    The intermediates take it all: Asymptotics of higher criticism statistics and a powerful alternative based on equal local levels

    Veronika Gontscharuk, Sandra Landwehr, and Helmut Finner. The intermediates take it all: Asymptotics of higher criticism statistics and a powerful alternative based on equal local levels. Biometrical Journal, 57(1):159–180, 2015

    2015

  19. [27]

    US Government Printing Office, 1948

    Emil Julius Gumbel.Statistical theory of extreme values and some practical applications: A series of lectures, volume 33. US Government Printing Office, 1948

    1948

  20. [28]

    Properties of higher criticism under strong dependence.The Annals of Statistics, pages 381–402, 2008

    Peter Hall and Jiashun Jin. Properties of higher criticism under strong dependence.The Annals of Statistics, pages 381–402, 2008

    2008

  21. [29]

    Innovated higher criticism for detecting sparse signals in correlated noise

    Peter Hall and Jiashun Jin. Innovated higher criticism for detecting sparse signals in correlated noise. The Annals of Statistics, 38(3):1686–1732, 2010

    2010

  22. [30]

    Convex analysis and minimization algorithms I: Fundamentals, volume 305

    Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal. Convex analysis and minimization algorithms I: Fundamentals, volume 305. Springer science & business media, 1996

    1996

  23. [31]

    SemStamp: A semantic watermark with paraphrastic robustness for text generation

    Abe Hou, Jingyu Zhang, Tianxing He, Yichen Wang, Yung-Sung Chuang, Hongwei Wang, Lingfeng Shen, Benjamin Van Durme, Daniel Khashabi, and Yulia Tsvetkov. SemStamp: A semantic watermark with paraphrastic robustness for text generation. InNorth American Chapter of the Association...

    2024

  24. [32]

    Unbiased watermark for large language models

    Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. In International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=uWVC5FVidc. 26

    2024

  25. [33]

    Towards optimal statistical watermarking.arXiv preprint arXiv:2312.07930, 2023

    Baihe Huang, Hanlin Zhu, Banghua Zhu, Kannan Ramchandran, Michael I Jordan, Jason D Lee, and Jiantao Jiao. Towards optimal statistical watermarking.arXiv preprint arXiv:2312.07930, 2023

    2023 arXiv

  26. [34]

    Robust estimation of a location parameter

    Peter J Huber. Robust estimation of a location parameter. InBreakthroughs in statistics: Methodology and distribution, pages 492–518. Springer, 1992

    1992

  27. [35]

    John Wiley & Sons, 2011

    Peter J Huber and Elvezio M Ronchetti.Robust statistics. John Wiley & Sons, 2011

    2011

  28. [36]

    Some problems of hypothesis testing leading to infinitely divisible distributions

    Yuri I Ingster. Some problems of hypothesis testing leading to infinitely divisible distributions. Mathematical Methods of Statistics, 6(1):47–69, 1997

    1997

  29. [37]

    Goodness-of-fit tests via phi-divergences.Annals of Statistics, 35(5):2018–2053, 2007

    Leah Jager and Jon A Wellner. Goodness-of-fit tests via phi-divergences.Annals of Statistics, 35(5):2018–2053, 2007

    2018

  30. [38]

    Categorical reparameterization with Gumbel-Softmax

    Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with Gumbel-Softmax. In International Conference on Learning Representations, 2016

    2016

  31. [39]

    Rare and weak effects in large-scale inference: Methods and phase diagrams

    Jiashun Jin and Zheng Tracy Ke. Rare and weak effects in large-scale inference: Methods and phase diagrams. Statistica Sinica, pages 1–34, 2016

    2016

  32. [40]

    Optimal adaptivity of signed-polygon statistics for network testing.The Annals of Statistics, 49(6):3408–3433, 2021

    Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Optimal adaptivity of signed-polygon statistics for network testing.The Annals of Statistics, 49(6):3408–3433, 2021

    2021

  33. [41]

    Covariance assisted screening and estimation.Annals of statistics, 42(6):2202, 2014

    Tracy Ke, Jiashun Jin, and Jianqing Fan. Covariance assisted screening and estimation.Annals of statistics, 42(6):2202, 2014

    2014

  34. [42]

    Martingale approach in the theory of goodness-of-fit tests.Theory of Probability & Its Applications, 26(2):240–257, 1982

    Estate V Khmaladze. Martingale approach in the theory of goodness-of-fit tests.Theory of Probability & Its Applications, 26(2):240–257, 1982

    1982

  35. [43]

    A watermark for large language models

    John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. InInternational Conference on Machine Learning, volume 202, pages 17061–17084, 2023

    2023

  36. [44]

    On the reliability of watermarks for large language models

    John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. InInternational Conference on Learning Representations,

  37. [45]

    Robust distortion- free watermarks for language models.Transactions on Machine Learning Research, 2024

    Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion- free watermarks for language models.Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https://openreview.net/forum?id=FpaCL1MO2C

    2024

  38. [46]

    Higher criticism: p-values and criticism.The Annals of Statistics, 43(3):1323–1350, 2015

    Jian Li and David Siegmund. Higher criticism: p-values and criticism.The Annals of Statistics, 43(3):1323–1350, 2015

    2015

  39. [47]

    Xiang Li, Feng Ruan, Huiyuan Wang, Qi Long, and Weijie J. Su. A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules.The Annals of Statistics (to appear), 2024. 27

    2024

  40. [48]

    A semantic invariant robust watermark for large language models

    Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. A semantic invariant robust watermark for large language models. InInternational Conference on Learning Representations,

  41. [49]

    Adaptive text watermark for large language models

    Yepeng Liu and Yuheng Bu. Adaptive text watermark for large language models. InInter- national Conference on Machine Learning, 2024. URLhttps://openreview.net/forum?id= 7emOSb5UfX

    2024

  42. [50]

    URL https://openreview.net/forum?id=6p8lpe4MNf

  43. [51]

    Large language models challenge the future of higher education.Nature Machine Intelligence, 5(4):333–334, 2023

    Silvia Milano, Joshua A McGrane, and Sabina Leonelli. Large language models challenge the future of higher education.Nature Machine Intelligence, 5(4):333–334, 2023

    2023

  44. [52]

    A* sampling

    Chris J Maddison, Daniel Tarlow, and Tom Minka. A* sampling. InAdvances in Neural Information Processing Systems, volume 27, 2014

    2014

  45. [53]

    Fast calculation of p-values for one-sided Kolmogorov-Smirnov type statistics

    Amit Moscovich. Fast calculation of p-values for one-sided Kolmogorov-Smirnov type statistics. Computational Statistics & Data Analysis, 185:107769, 2023

    2023

  46. [54]

    WordNet: A lexical database for English.Communications of the ACM, 38 (11):39–41, 1995

    George A Miller. WordNet: A lexical database for English.Communications of the ACM, 38 (11):39–41, 1995

    1995

  47. [55]

    Hodges-Lehmann asymptotic efficiency of the Kolmogorov and Smirnov goodness- of-fit tests

    Ya Yu Nikitin. Hodges-Lehmann asymptotic efficiency of the Kolmogorov and Smirnov goodness- of-fit tests. Journal of Soviet Mathematics, 36:517–520, 1987

    1987

  48. [56]

    Cambridge University Press, 1995

    ÍÀkov ÍÙr’evich Nikitin.Asymptotic efficiency of nonparametric tests. Cambridge University Press, 1995

    1995

  49. [57]

    Understanding the source of what we see and hear online, May 2024

    OpenAI. Understanding the source of what we see and hear online, May 2024. URL https://https://openai.com/index/understanding-the-source-of-what-we-see- and-hear-online/

    2024

  50. [58]

    ChatGPT: Optimizing language models for dialogue, Jan 2023

    OpenAI. ChatGPT: Optimizing language models for dialogue, Jan 2023. URLhttp://web. archive.org/web/20230109000707/https://openai.com/blog/chatgpt/

    2023

  51. [59]

    Mark my words: Analyzing and evaluating language model watermarks.arXiv preprint arXiv:2312.00273, 2023

    Julien Piet, Chawin Sitawarin, Vivian Fang, Norman Mu, and David Wagner. Mark my words: Analyzing and evaluating language model watermarks.arXiv preprint arXiv:2312.00273, 2023

    2023 arXiv

  52. [60]

    Perturb-and-map random fields: Using discrete opti- mization to learn and sample from energy models

    George Papandreou and Alan L Yuille. Perturb-and-map random fields: Using discrete opti- mization to learn and sample from energy models. InInternational Conference on Computer Vision, pages 193–200. IEEE, 2011

    2011

  53. [61]

    Language models are unsupervised multitask learners.OpenAI blog, 1(8):9, 2019

    Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners.OpenAI blog, 1(8):9, 2019

    2019

  54. [62]

    Large deviations and bahadur efficiency of the Khmaladze-Aki statistic

    OA Podkorytova. Large deviations and bahadur efficiency of the Khmaladze-Aki statistic. Journal of Mathematical Sciences, 68:560–565, 1994

    1994

  55. [63]

    Exploring the limits of transfer learning with a unified text-to-text transformer

    Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(1):5485–5551, 2020

    2020

  56. [64]

    Robust speech recognition via large-scale weak supervision

    Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision. InInternational Conference on Machine Learning, pages 28492–28518. PMLR, 2023. 28

    2023

  57. [65]

    A robust semantics-based watermark for large language model against paraphrasing

    Jie Ren, Han Xu, Yiding Liu, Yingqian Cui, Shuaiqiang Wang, Dawei Yin, and Jiliang Tang. A robust semantics-based watermark for large language model against paraphrasing. InFindings of the Association for Computational Linguistics, pages 613–625, 2024

    2024

  58. [66]

    Efficient estimates and optimum inference procedures in large samples

    C Radhakrishna Rao. Efficient estimates and optimum inference procedures in large samples. Journal of the Royal Statistical Society: Series B (Methodological), 24(1):46–63, 1962

    1962

  59. [67]

    The curse of recursion: Training on generated data makes models forget

    Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Yarin Gal, Nicolas Papernot, and Ross Anderson. The curse of recursion: Training on generated data makes models forget. arXiv preprint arXiv:2305.17493, 2023

    2023 arXiv

  60. [68]

    Applied Cryptography

    Bruce Schneier. Applied Cryptography. John Wiley & Sons, 1996

    1996

  61. [69]

    AI bot ChatGPT writes smart essays—Should professors worry?Nature News, 2022

    C Stokel-Walker. AI bot ChatGPT writes smart essays—Should professors worry?Nature News, 2022

    2022

  62. [70]

    Disinformation’s spread: Bots, trolls and all of us.Nature, 571(7766):449–450, 2019

    Kate Starbird. Disinformation’s spread: Bots, trolls and all of us.Nature, 571(7766):449–450, 2019

    2019

  63. [71]

    Ethical and social risks of harm from language models.arXiv preprint arXiv:2112.04359, 2021

    Laura Weidinger, John Mellor, Maribeth Rauh, Conor Griffin, Jonathan Uesato, Po-Sen Huang, Myra Cheng, Mia Glaese, Borja Balle, Atoosa Kasirzadeh, et al. Ethical and social risks of harm from language models.arXiv preprint arXiv:2112.04359, 2021

    2021 arXiv

  64. [72]

    LLaMA: Open and efficient foundation language models.arXiv preprint arXiv:2302.13971, 2023

    Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. LLaMA: Open and efficient foundation language models.arXiv preprint arXiv:2302.13971, 2023

    2023 arXiv

  65. [73]

    DiPmark: A stealthy, efficient and resilient watermark for large language models.arXiv preprint arXiv:2310.07710, 2023

    Yihan Wu, Zhengmian Hu, Hongyang Zhang, and Heng Huang. DiPmark: A stealthy, efficient and resilient watermark for large language models.arXiv preprint arXiv:2310.07710, 2023

    2023 arXiv

  66. [74]

    A note on the asymptotic distribution of Berk—Jones type statistics under the null hypothesis

    Jon A Wellner and Vladimir Koltchinskii. A note on the asymptotic distribution of Berk—Jones type statistics under the null hypothesis. InHigh Dimensional Probability III, pages 321–332. Springer, 2003

    2003

  67. [75]

    Su, and Ruixun Zhang

    Yangxinyu Xie, Xiang Li, Tanwi Mallick, Weijie J. Su, and Ruixun Zhang. Debiasing watermarks for large language models via maximal coupling.arXiv preprint arXiv:2411.11203, 2024

    2024 arXiv

  68. [76]

    Sheared LLaMA: Accelerating language model pre-training via structured pruning

    Mengzhou Xia, Tianyu Gao, Zhiyuan Zeng, and Danqi Chen. Sheared LLaMA: Accelerating language model pre-training via structured pruning. InInternational Conference on Learning Representations, 2023

    2023

  69. [77]

    Defending against neural fake news

    Rowan Zellers, Ari Holtzman, Hannah Rashkin, Yonatan Bisk, Ali Farhadi, Franziska Roesner, and Yejin Choi. Defending against neural fake news. In Advances in Neural Information Processing Systems, volume 32, 2019

    2019

  70. [78]

    Robust multi-bit natural lan- guage watermarking through invariant features

    KiYoon Yoo, Wonhyuk Ahn, Jiho Jang, and Nojun Kwak. Robust multi-bit natural lan- guage watermarking through invariant features. InAnnual Meeting Of The Association For Computational Linguistics, 2023. 29

    2023

  71. [79]

    Provable robust watermarking for AI-generated text

    Xuandong Zhao, Prabhanjan Vijendra Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for AI-generated text. InInternational Conference on Learning Representations,

  72. [80]

    OPT: Open pre-trained transformer language models.arXiv preprint arXiv:2205.01068, 2022

    Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. OPT: Open pre-trained transformer language models.arXiv preprint arXiv:2205.01068, 2022

    2022 arXiv

  73. [81]

    Duwak: Dual watermarks in large language models

    Chaoyi Zhu, Jeroen Galjaard, Pin-Yu Chen, and Lydia Y Chen. Duwak: Dual watermarks in large language models. InFindings of the Association for Computational Linguistics, 2024

    2024

  74. [82]

    URL https://openreview.net/forum?id=SsmT8aO45L

  75. [83]

    Permute-and-Flip: An optimally robust and watermarkable decoder for LLMs.arXiv preprint arXiv:2402.05864, 2024

    Xuandong Zhao, Lei Li, and Yu-Xiang Wang. Permute-and-Flip: An optimally robust and watermarkable decoder for LLMs.arXiv preprint arXiv:2402.05864, 2024

    2024 arXiv

  76. [85]

    Human behavior and the principle of least effort: An introduction to human ecology

    George Kingsley Zipf. Human behavior and the principle of least effort: An introduction to human ecology. Ravenio books, 2016. 30 Supplementary Material This Supplementary Material includes the remaining proofs and technical details. Section A presents the proofs, while Sectio...

    2016

  77. [86]

    If n · supPt∈P H 2(µ0, (1 − εn)µ0 + εnµ1,Pt) = o(1), then TV(ρ0, ρ1) → 0 as n → ∞

  78. [87]

    , Yt−1] be the conditional version ofµ1,Pt given the history information Y1,

    Let µ1,t = E1[µ1,Pt|Y1, . . . , Yt−1] be the conditional version ofµ1,Pt given the history information Y1, . . . , Yt−1. If there exists a positive non-random sequencecn satisfying ncn → ∞such that mint∈[n] inf Pt∈P H 2(µ0, (1 − εn)µ0 + εnµ1,t) ≥ cn holds almost surely for eac...

  79. [88]

    By the last inequality, (14), and (13), it follows that H 2(ρ0, ρ1) ≤ 1 − nY t=1 1 − sup Pt∈P H 2(µ0, (1 − εn)µ0 + εnµ1,Pt)

    By conditional Jensen’s inequality, it follows that EYn∼µ0 q (1 − εn) + εnf 1,n(Yn) ≥ EYn∼µ0 E1 q (1 − εn) + εnf1,Pn(Yn) Gn−1 ≥ inf Pn∈P EYn∼µ0 q (1 − εn) + εnf1,Pn(Yn) = 1 − sup Pn∈P H 2(µ0, (1 − εn)µ0 + εnµ1,Pn). By the last inequality, (14), and (13), it follows that H 2(ρ0...

  80. [89]

    E1 " nY t=1 1Yt∈At|Gn−1 ## = E1

    By the condition, it follows that EYn∼µ0 q (1 − εn) + εnf 1,n(Yn) = 1 − H 2(µ0, (1 − εn)µ0 + εnµ1,n) ≤ 1 − cn. By the last inequality, (14), and (13), it follows that H 2(ρ0, ρ1) ≥ 1 − (1 − cn)n ≥ 1 − e−ncn → 1. Proof of (14). To prove equation(14), we require an important lem...

  81. [90]

    Hence, for any test, the sum of Type I and Type II errors tends to 1 asn → ∞

    If q + 2p >1 and P1:n ⊂ Pc ∆n, H0 and H mix 1 merge asymptotically. Hence, for any test, the sum of Type I and Type II errors tends to 1 asn → ∞

  82. [91]

    Furthermore, for the likelihood-ratio test that rejectsH0 if the log-likelihood ratio is positive, the sum of Type I and Type II errors tends to 0 asn → ∞

    If q + 2p <1 and P1:n ⊂ P∆n, H0 and H mix 1 separate asymptotically. Furthermore, for the likelihood-ratio test that rejectsH0 if the log-likelihood ratio is positive, the sum of Type I and Type II errors tends to 0 asn → ∞. Proof of Theorem 4.2.We prove this theorem with the ...

  83. [92]

    Then, H 2(µ0, 1 − εn + εnµ1,Pt) = Θ(1) · ε2 n · E0(f1,Pt(Y ) − 1)2

    Let f1,Pt(r) = P w∈W r1/Pt,w−1 be the PDF ofµ1,Pt. Then, H 2(µ0, 1 − εn + εnµ1,Pt) = Θ(1) · ε2 n · E0(f1,Pt(Y ) − 1)2

  84. [93]

    Let Gn = σ({Yt}n t=1) is the σ-field generated by allY1, . . . , Yn. We define the conditioned PDF and probability measure:f 1,t(y) = E1[f1,Pt(y)|Gt−1] and µ1,t = E1[µ1,Pt|Gt−1]. It follows that H 2(µ0, 1 − εn + εnµ1,t) = Θ(1) · ε2 n · E0(f 1,t(Y ) − 1)2. Here Θ(1) in the abov...

  85. [94]

    By Lemma A.1, it suffices to show nX t=1 sup Pt∈P c ∆n H 2(µ0, (1 − εn)µ0 + εnµ1,Pt) → 0

    To prove the first point, we could use a similar argument in the proof of Theorem 4.1. By Lemma A.1, it suffices to show nX t=1 sup Pt∈P c ∆n H 2(µ0, (1 − εn)µ0 + εnµ1,Pt) → 0. (19) Lemma A.4. Fix Pt. Let f1,Pt(r) = P w∈W r1/Pt,w−1 be the PDF ofµ1,Pt. Then, E0(f1,Pt(Y ) − 1)2 ...

  86. [95]

    Lemma A.5

    To prove the second point, by Lemma A.1, we only have to show that there exists a positive non-random sequence cn satisfying ncn → ∞and H 2(µ0, (1 − εn)µ0 + εnµ1,t) ≥ cn almost surely for ∀n ≥ 1. Lemma A.5. If Pt ∈ P∆n holds almost surely andn is sufficiently large so that∆n <...

  87. [96]

    For eacht ∈ [n], we obtain a p-value by pt := P0(Y ≥ Yt|Yt) = 1 − Yt

  88. [97]

    Sort the p-values to p(1) < p(2) < . . . <p(n). We make a convention that p(n+1) = 1

  89. [98]

    (22) 38 For any givenδ >0, we would rejectH0 if HC+ n ≥ p 2(1 + δ) log logn

    Define the HC statistic as HC+ n = sup t:p(t+1)≥c+ n HCn,t, HCn,t = √n t/n −p(t)q p(t)(1 −p(t)) . (22) 38 For any givenδ >0, we would rejectH0 if HC+ n ≥ p 2(1 + δ) log logn. (23) Remark A.1. We mention that except for the expression in(22), there are other variants or general...

  90. [99]

    As a result, Tr-GoF can asymptotically distinguish between H0 and H mix 1

    These results imply that by rejecting H0 whenever nS+ n (s) ≥ (1 + δ) log logn for any givenδ >0, both Type I and Type II errors converge to zero asymptotically. As a result, Tr-GoF can asymptotically distinguish between H0 and H mix 1 . To prove Theorem 4.3, we start by intro...

  91. [100]

    Proof of Lemma A.11.If u < v, K+ s (u, v) = 0; thus, all the inequalities follow directly

    For s = 1, it follows that K+ 1 (u, v) ≥ K+ 2 (u, v) · v u . Proof of Lemma A.11.If u < v, K+ s (u, v) = 0; thus, all the inequalities follow directly. We then assume 0 < v≤ u <1. Note that by definition,K2(u, v) = 1 2 (u−v)2 v(1−v) is always non-negative

  92. [101]

    (31) Given v ≤ u and s ≤ 2, it follows that −(1 − v) 1 − v u 2−s ≤ v(1 − v)Ds(u⋆, v) − 1 ≤ v " 1 − v 1 − u 2−s − 1 #

    If s ̸= 1, from the proof of Lemma 7.2 (ii) in [37], it follows that Ks(u, v) = K2(u, v) [1 +v(1 − v)Ds(u⋆, v) − 1] , where u⋆ ∈ [v, u] is determined by the mean value theorem andDs(u⋆, v) is given by Ds(u, v) = v u 2−s 1 v + 1 − v 1 − u 2−s 1 1 − v . (31) Given v ≤ u and s ≤ ...

  93. [102]

    We then complete the proof by noting thatK+ s (u, v) = Ks(u, v) if v ≤ u

    If s = 1, from the proof of Theorem 1.1 in [72], we similarly have K1(u, v) = K2(u, v) [1 +v(1 − v)D1(u⋆, v) − 1] , where u⋆ ∈ [v, u]is determined by the mean value theorem and the quantityD1(u⋆, v), according to (31), is given by D1(u⋆, v) = 1 u⋆(1 − u⋆) By the inequalityu⋆ ∈...

  94. [103]

    For hars, E1,P hars(Y ) − E0 hars(Y ) = Θ(1) · Ent(P ) = Θ ∆ log 1 ∆

  95. [104]

    For hlog, E1,P hlog(Y ) − E0 hlog(Y ) = 1 − P w∈W P 2 w = Θ(∆)

  96. [105]

    For hind,δ with δ ∈ (0, 1), E1,P hind,δ(Y ) − E0 hind,δ(Y ) = δ − FP (δ) = Θ(∆)

  97. [106]

    5This inequality deviates slightly from the original version (see Theorem 2(a) in [21])

    For hopt,∆0 with ∆0 ∈ (0, 1), E1,P hopt,∆0(Y ) − E0 hopt,∆0(Y ) = Θ(∆). 5This inequality deviates slightly from the original version (see Theorem 2(a) in [21]). It can be established using the same methodology they employed, with the alteration being the adjustment of the doma...

  98. [107]

    It is easy to find the lower bound holds:Ent(P ) ≥ (1 − Pmax) log 1 1−Pmax = ∆ log 1 ∆

    We first note that Ent(P ) = Pmax log 1 Pmax + (1 − Pmax) log 1 1 − Pmax + (1 − Pmax) X w:Pw̸=Pmax Pw 1 − Pmax log 1 − Pmax Pw . It is easy to find the lower bound holds:Ent(P ) ≥ (1 − Pmax) log 1 1−Pmax = ∆ log 1 ∆. For the upper bound, we note that ifPmax ≥ 1 − c (due to ∆ ≤...

  99. [108]

    It follows that1 − Pmax ≤ 1 − P w∈W P 2 w ≤ 1 − P 2 max ≤ 2(1 − Pmax)

  100. [109]

    Given Pmax is smaller than a constant, sayc, we have that−g′(θ) is a positive constant that depends only onδ and c, which implies the above equation(∗)

    Due toPmaxδ1/Pmax ≤ FP (δ) ≤ δ1/Pmax, once we setg(x) = δx, the mean value theorem implies that g(1) − g 1 Pw = g′(θ) 1 − 1 Pw (∗) = Θ(1 − Pmax) where θ ∈ [1, 1/Pmax]. Given Pmax is smaller than a constant, sayc, we have that−g′(θ) is a positive constant that depends only onδ ...

  101. [110]

    We first consider the simplest case where∆0 ∈ (0, 0.5), hopt,∆0(y) = log y ∆0 1−∆0 + y 1 ∆0 −1 = ∆0 1 − ∆0 log y + log 1 + y 1−∆0 ∆0 − ∆0 1−∆0 . We note that by integration by parts, it follows that E1,P hopt,∆0(Y ) − E0 hopt,∆0(Y ) = ∆0 1 − ∆0 [E1,P hlog(Y ) − E0 hlog(Y )] + ...

  102. [111]

    If q + p <1 2 and P1:n ⊂ P∆n, the sum of Type I and Type II errors tends to 0

  103. [112]

    If q + p >1 2 and P1:n ⊂ Pc ∆n, the sum of Type I and Type II errors tends to 1. Proof of Theorem 4.4.Recall that the considered detection rule has the following form: Th(Y1:n) = ( 1 if Pn t=1 h(Yt) ≥ n · E0 h(Y ) + C · n 1 2 an, 0 if Pn t=1 h(Yt) < n· E0 h(Y ) + C · n 1 2 an,...

  104. [113]

    By condition an n1/2−p−q → 0, we haveX n√n → −∞as n → ∞

    If p + q <1 2 and P1:n ⊂ P∆n, we then have that X n ≤ −Θ(n · εn · ∆n). By condition an n1/2−p−q → 0, we haveX n√n → −∞as n → ∞. Hence, by Chebyshev’s inequality, it follows that as long asn is sufficiently large, P1(Th(Y1:n) = 0) ≤ P1 Xn√n ≥ X n√n − Can ≤ O(1) n 1 2 −p−q → 0

  105. [114]

    Hence, by Chebyshev’s inequality, it follows that as long as n is sufficiently large, P1(Th(Y1:n) = 1) ≤ P1 Xn√n ≥ Can − X n√n ≤ O(1) a2n → 0

    If p + q >1 2 and P1:n ⊂ Pc ∆n, we then have that 0 ≥ X n ≥ −Θ(n · εn · ∆n), which implies that X n√n → 0 as n → ∞. Hence, by Chebyshev’s inequality, it follows that as long as n is sufficiently large, P1(Th(Y1:n) = 1) ≤ P1 Xn√n ≥ Can − X n√n ≤ O(1) a2n → 0. The case forhars w...

  106. [115]

    Draw n = 104 samples from U (0, 1) to represent H0 and then calculateHC+ n or HC⋆ n

  107. [116]

    Replace ⌈nεn⌉ of the previous samples by the same number of samples fromF1,Pt where Pt is generated according to theM3 method in which the top probability is forced to be1 − ∆n

  108. [117]

    heavy tails

    Repeat Steps 1 and 2 overN = 103 times and make histograms of the simulatedHC+ n or HC⋆ n. See Figure 14 for the distribution ofHC+ n (top) and HC⋆ n (bottom) under interesting(p, q) pairs. Let’s first focus on the top row. UnderH0, the distribution ofHC+ n values is primarily...

    2000

  109. [118]

    Helsinki-NLP/opus-mt-tc-big-en-fr for English to French translation,

  110. [119]

    This method leverages the subtle nuances of translation to detect inconsistencies or vulnerabilities in language models

    Helsinki-NLP/opus-mt-tc-big-fr-en for French to English translation. This method leverages the subtle nuances of translation to detect inconsistencies or vulnerabilities in language models. Since the text length may change after roundtrip translation, we use the last 200 token...

  111. [2024]

    URL https://openreview.net/forum?id=DEJIDCmWOz

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.