Pith. sign in

REVIEW 2 major objections 4 minor 58 references

Optimized Couplings for Watermarking Large Language Models

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read This paper derives a closed-form limit for single-token LLM watermark detection under worst-case token distributions, and proves that a zero-perception coupled random-partition scheme, the Correlated Channel watermark, attains it.

desk verdict The CC watermark and fixed-partition analysis are solid, but Theorem 3's balanced-class optimality is asserted, not proven, for general k and λ. read the letter →

arxiv 2505.08878 v1 pith:ITFUGWS7 submitted 2025-05-13 cs.CR cs.AIcs.ITmath.IT

Dor Tsur , Carol Xuan Long , Claudio Mayrink Verdun , Hsiang Hsu , Haim Permuter , Flavio P. Calmon This is my paper · ORCID
classification cs.CRcs.AIcs.ITmath.IT MSC 94A1762C20
keywords LLMwatermarkingone-shotdetection-perceptiontrade-offcorrelatedchannelwatermarkmin-entropyconstrainthypothesistestingwithsideinformationrandomizedvocabularypartitionmax-mindetection
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 aims to pin down the fundamental limit of single-token watermarking of large-language-model output: under a worst-case next-token distribution whose peak probability is at most $\lambda$, the best detection rate for an indicator-style detector that sees only shared side information and a randomized vocabulary partition takes a closed form. The claimed optimum is attained by the Correlated Channel (CC) watermark, which couples uniform side information with a random balanced partition of the vocabulary and, averaged over the side information, leaves the next-token distribution unchanged (zero perception). If the claim holds, the per-token cap of about $3/4$ for binary side information is a hard limit rather than a defect of any particular scheme, and the small per-token gains compound exponentially across a generated sequence.

What carries the argument

The load-bearing object is the correlated channel: an optimal coupling between the uniform side information $S \sim \mathrm{Unif}([k])$ and the random partition variable $Y = f(X, B_m)$ that maximizes the acceptance probability $\Pr(S = Y)$, constructed through the dual representation of total variation and reducing to a Z-channel when $k = 2$. Its job is to convert a public random assignment of colors to tokens ($B_m$, shared by watermarker and detector) into a private signal: the distribution of $Y$ is coupled to $S$ so that detector and watermarker agree on the color far more often than chance, while the marginal over tokens is untouched. This mechanism delivers zero perception ($\mathbb{E}_S[Q_{X|S}] = Q_X$), collapses the detection probability to the closed form $R_d = 1 - \frac{1}{2k} - \frac{1}{2}\mathrm{TV}(P_Y, P_S)$, and reduces the whole design problem to choosing the distribution of $B_m$; Theorem 3 then solves that choice in the max-min sense with the balanced permutation class.

What would settle it

Take a small instance, say $m = 12$ tokens with $k = 3$ colors, pick $\lambda$ strictly between $1/3$ and $1/2$, and compare the balanced class $(4,4,4)$ against unbalanced classes such as $(6,3,3)$ and $(8,2,2)$ by evaluating the formula (48) for $\mathbb{E}[g(Q^*_\lambda, B_m)]$ in each class; any unbalanced class with a smaller value refutes the optimality half of Theorem 3. The same verdict can be reached numerically by solving the max-min problem (6) directly over the finitely many extreme distributions $\{Q : \lVert Q\rVert_\infty \le \lambda\}$ for small $m$ and $k$ and checking whether $R^*_d(\lambda)$ is actually attained.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3: for a vocabulary of $m$ tokens, side information uniform over $k$ values, and the min-entropy constraint $\lVert Q_X\rVert_\infty \le \lambda$ (equivalently, $H_\infty(Q_X) \ge -\log\lambda$), the optimal max-min one-shot detection probability is $R^*_d(\lambda) = 1 - \frac{1}{2k} - \frac{1}{4}\mathbb{E}[g(Q^*_\lambda, B_m)]$, where the expectation is taken over $B_m$ sampled uniformly from the balanced permutation class (each of the $k$ colors appears exactly $m/k$ times) and $Q^*_\lambda$ is the extreme worst-case token distribution with $t = \lfloor 1/\lambda \rfloor$ entries equal to $\lambda$, one entry equal to $1-t\lambda$, and the rest zero. The scheme that achieves this, the Correlated Channel watermark, couples the shared side information $S$ with the partition label $Y = f(X, B_m)$ so as to maximize $\Pr(S = Y)$; for $k=2$ this optimal coupling is the Z-channel, and the detector simply announces 'watermarked' when $S = f(A, B_m)$. The paper further claims that this test is equivalent to the likelihood-ratio test at threshold $1$, that the scheme has zero perception in the sense $\mathbb{E}_S[Q_{X|S}] = Q_X$, and that sampling the partition i.i.d. Bernoulli$(1/k)$ is near-optimal with approximation error at most $2k\lceil 1/\lambda \rceil/m$.

Load-bearing premise

The closed-form optimum assumes that for every number of colors $k$ and every allowed peak probability $\lambda$, the best choice of partition randomness is the balanced permutation class in which each color appears exactly $m/k$ times; the appendix establishes this optimality only for $k = 2$ over restricted ranges of $\lambda$, so for general $k$ an unbalanced permutation class could in principle perform better, and that would invalidate the claimed closed-form maximum.

Editorial extensions

If this is right

  • With binary side information ($k=2$) the worst-case single-token detection probability is capped at $3/4$ no matter how the vocabulary is partitioned, so any practical detector must spread its gains across many tokens rather than chase a higher per-token rate.
  • Because the approximation error of i.i.d. Bernoulli$(1/k)$ sampling is $O(1/m)$, real vocabularies of roughly 100,000 tokens can sample partitions simply and stay within a negligible distance of the balanced-class optimum.
  • The zero-perception property means detection power is bought without shifting the expected next-token distribution, which the paper's language-model experiments show as lower perplexity than the tilting red-green scheme at comparable or better detection statistics.
  • The sequential extension has a binomial test statistic with known null probability $1/k$ per token, so false-positive rates can be controlled without any access to the underlying token distribution.
  • Larger $k$ raises the single-token ceiling, but the gain diminishes as $k$ grows and depends on $m$ being divisible by $k$; when it is not, the balanced class does not exist and detection degrades.

Reading between the lines

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

  • A natural extension the paper does not work out is the asymmetric-prior regime $\pi_0 \ne \pi_1$: Proposition 1 carries the factor $\gamma = \pi_1/\pi_0$ into the detection expression, and a max-min version of the balanced-partition argument would plausibly give closed forms $R^*_d(\lambda, \gamma)$ interpolating between random guessing and the $\gamma = 1$ values.
  • The construction reads as a zero-perception single-token embedding result: choosing $k$ colors effectively encodes $\log_2 k$ bits of shared randomness per token, so the balanced-class optimization doubles as a capacity statement for invisible single-token watermarks, a connection the paper leaves implicit.
  • Because the worst-case distributions $Q^*_\lambda$ are exactly the extreme points of the min-entropy polytope, Theorem 3 could serve as the atomic step of a fully adversarial sequential analysis in which the adversary picks the worst distribution at every position; Proposition 4 already moves that way under an i.i.d. assumption.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. This paper studies one-shot LLM watermarking as a hypothesis-testing problem with side information. The authors formulate a max-min detection probability over randomized partitions of the vocabulary under a min-entropy constraint on the worst-case token distribution, propose the 'correlated channel' (CC) scheme, and claim a closed-form optimal detection rate R*_d(λ) given in Eq. (10), achieved by uniform sampling over the balanced permutation class. They also provide a simpler Bernoulli-sampling approximation with O(1/m) error, a sequential extension bound, and experiments on synthetic data and the WaterBench LLM benchmark. The paper is clearly written and includes code.

Significance. If the optimality theorem were fully proven, the paper would provide a fundamental single-token detection limit within the considered restricted test class and show that a zero-perception scheme can attain it. The formulation is clean, the max-min analysis is parameter-free (no fitted constants), and the closed-form expressions are useful for benchmarking practical watermarks. However, the central optimality claim currently rests on an unproven assertion about the balanced permutation class, so the theoretical contribution is not yet established at the level claimed.

major comments (2)
  1. [Appendix A.9, Eqs. (40)-(49)] The proof of Theorem 3 reduces the max-min problem to selecting a permutation class that minimizes E[g(q*_λ,B_m)] (Eq. (42)), but it computes E[g] only for the balanced class (Eq. (49)) and proves optimality of that class only for k=2 in the restricted ranges 1/2≤λ≤1 and 1/3≤λ<1/2 (Eqs. (58)-(61)). For k>2, and for λ<1/3 with k=2, no argument rules out a permutation class with unequal color counts yielding a smaller E[g]. Since Eq. (10) and Corollary 1 assert the balanced class achieves the optimum for all k and λ, this is a load-bearing gap: if a non-balanced class is better, R*_d(λ) in Eq. (10) is not the max-min detection rate and the optimality narrative of the central theorem is unsupported. The authors should either supply a complete proof of the balanced-class optimality (e.g., via a swap/majorization argument across color counts) or restrict the claim of the theorem accordingly.
  2. [Appendix A.9, Eq. (42)] In the reduction following Eq. (42), the text states that it is sufficient to select a b uniformly over the permutation class 'that maximizes 1/|B_i| Σ_{b∈B_i} g(q*_λ,b)'. The min over w in Δ_K of a linear function in Eq. (42) is attained at the vertex corresponding to the class with the minimum average of g, not the maximum. If this is a typo, it should be corrected; as written, the proof appears to optimize the wrong objective when choosing the balanced class.
minor comments (4)
  1. [Appendix A.9, after Eq. (59)] The line 'As m→∞, R*_d(λ)→3/4 − m/4' should read '3/4 − λ/4'; the main text's subsequent statement that the penalty equals λ/4 is correct, so the appendix expression appears to be a typo.
  2. [Appendix A.11 and A.12] Sections A.11 and A.12 contain identical proofs of Proposition 4; one of the two copies should be removed.
  3. [Table 1 caption] The caption says 'We compare C with two values of k and RG with two values of δ'; this should read 'We compare CC with two values of k'.
  4. [Section 3.3] The notation for the optimal distribution P*_Bm and the distinction between 'uniform sampling over the balanced permutation class' and 'i.i.d. Bernoulli sampling' is introduced informally; a formal definition of the distribution underlying the expectation in Eq. (10) would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the max-min detection rate is derived from an explicit optimization over couplings and partition randomness, with no fitted inputs or load-bearing self-citations.

full rationale

The paper's derivation chain is self-contained rather than circular. The one-shot watermarking task is posed as a hypothesis-testing problem (Proposition 1), and the correlated-channel construction follows from a standard maximum-coupling/TV-distance identity (Proposition 2). The central max-min detection rate in Theorem 3 is a closed-form expression obtained by optimizing over the partition-randomization distribution PB_m against the worst-case token distribution in the constraint set {Q_X : ||Q_X||_inf <= lambda}; the only inputs are m, k, and lambda, and no parameter is fitted to data or to a desired detection outcome. The numerical sections benchmark the scheme against an independent exact solver (GUROBI solution of Eq. 4) and against the external red-green baseline, so the empirical claims are not validated by re-inserting the theorem's conclusion. The only self-citation is a non-load-bearing footnote in Remark 1 referring to [39] for a convention about the residual term in E_gamma divergence. The skeptical concern that Theorem 3's optimality of the balanced permutation class is not fully proved for general k and lambda is a proof gap or correctness risk, not circularity: the balanced class is asserted as the optimum of an explicit minimization, not assumed as an input, and the closed form does not reduce to the constraint set by construction. Therefore no circular step is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central derivation depends on standard information-theoretic facts plus two explicit modeling choices about the one-shot watermarking setting. The only unsupported premise is the balanced-class optimality in Theorem 3, which is flagged both here and in the red flags. No free parameters are fitted to data, and no new physical or mathematical entities are introduced.

assumptions (6)
  • standard math Neyman-Pearson lemma and E-gamma divergence representation for optimal hypothesis tests
    Used in Proposition 1 to express optimal detection and perception probabilities in terms of E-gamma and total variation divergences. This is textbook material, but it is the foundation of the trade-off analysis.
  • standard math Dual representation of total variation distance as a coupling problem
    Used in Proposition 2 to construct the optimal coupling between uniform side information S and partition output Y. The Z-channel structure of the optimal coupling follows from this representation.
  • standard math de Finetti's theorem for finite exchangeable sequences
    Used in the proof of Theorem 4 to bound the total variation between sampling with and without replacement from the balanced permutation class, giving the O(1/m) approximation error.
  • domain assumption The detector has no access to the token distribution QX, so detection is restricted to equality tests of the form 1[f(A,B_m)=S]
    Section 3 motivates this restriction as the practical setting for LLM watermarking. The claimed optimality in Theorem 3 is only within this partition-based test class, not over all possible detectors.
  • domain assumption The adversarial next-token distribution lies in the set {QX : ||QX||infinity <= lambda}
    Equation (6) defines the worst-case class via a min-entropy constraint. If real LLM next-token distributions violate this constraint, the max-min detection guarantees may not apply.
  • ad hoc to paper The balanced permutation class, equal counts of each color, is the optimal choice of partition randomness for all k and lambda
    Theorem 3 explicitly relies on this. The proof in Appendix A.9 derives the expectation for the balanced class and proves optimality only for k=2 in restricted lambda intervals. No proof is given for general k, so this premise is currently unsupported.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimized Couplings for Watermarking Large Language Models." pith.science (2026). https://pith.science/paper/ITFUGWS7

@misc{pith2026250508878,
  author       = {Pith},
  title        = {Pith review of: Optimized Couplings for Watermarking Large Language Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ITFUGWS7}},
  note         = {Machine review of arXiv:2505.08878}
}
read the original abstract

Large-language models (LLMs) are now able to produce text that is, in many cases, seemingly indistinguishable from human-generated content. This has fueled the development of watermarks that imprint a ``signal'' in LLM-generated text with minimal perturbation of an LLM's output. This paper provides an analysis of text watermarking in a one-shot setting. Through the lens of hypothesis testing with side information, we formulate and analyze the fundamental trade-off between watermark detection power and distortion in generated textual quality. We argue that a key component in watermark design is generating a coupling between the side information shared with the watermark detector and a random partition of the LLM vocabulary. Our analysis identifies the optimal coupling and randomization strategy under the worst-case LLM next-token distribution that satisfies a min-entropy constraint. We provide a closed-form expression of the resulting detection rate under the proposed scheme and quantify the cost in a max-min sense. Finally, we provide an array of numerical results, comparing the proposed scheme with the theoretical optimum and existing schemes, in both synthetic data and LLM watermarking. Our code is available at https://github.com/Carol-Long/CC_Watermark

Figures

Figures reproduced from arXiv: 2505.08878 by the authors.

Figure 1
Figure 1. Watermarking problem as a hypothesis test with side information. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Optimal coupling between side information [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Optimal detection probability of CC in one-shot on the adversarial token distribution (Eq. 6) is plotted [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: One-shot watermark detection results on QX = Unif(X ). For αp = 0, CC achieves a detection probability of 0.75 and 0.7 with balanced and Bernoulli partitions, respectively. CC Balanced achieves the optimal detection (Eq. 4 with γ = 1 and |S|= 2). Standard deviations pl…
Figure 5
Figure 5. Figure 5: Detection probability vs. k for two values of m and a uniform token distribution QX. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: ROC of the sequence-level watermarking scheme. We compare the red-green method [5] with the CC scheme [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: ROC of the sequence-level watermarking scheme under CC method for a range of [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: Numerical solution of (78) vs. |S|= k. where ∥V∥1,1≜ Pk i=1 Pm j=1|vi,j | is the entrywise l1-norm of V, 1m,n is an (m, n) matrix of ones, and 0m is an (m, 1) vector of zeros. Note that we can reduce the objective function from TV QX|S, QX|PS  to ∥V∥1,1 since PS is a …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 29 canonical work pages

  1. [17]

    Watermarking language models with error correcting codes

    Patrick Chao, Edgar Dobriban, and Hamed Hassani. Watermarking language models with error correcting codes. arXiv preprint arXiv:2406.10281, 2024

    arXiv 2024

  2. [1]

    TrustLLM: Trustworthiness in large language models.arXiv preprint arXiv:2401.05561, 2024

    Yue Huang, Lichao Sun, Haoran Wang, Siyuan Wu, Qihui Zhang, Yuan Li, Chujie Gao, Yixin Huang, Wenhan Lyu, Yixuan Zhang, et al. TrustLLM: Trustworthiness in large language models.arXiv preprint arXiv:2401.05561, 2024

    arXiv 2024

  3. [2]

    Constitutional ai: Harmlessness from ai feedback

    Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint arXiv:2212.08073, 2022

    arXiv 2022

  4. [3]

    Transformer feed-forward layers are key-value memories

    Mor Geva, Roei Schuster, Jonathan Berant, and Omer Levy. Transformer feed-forward layers are key-value memories. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 5484–5495, 2021

    2021

  5. [4]

    Truthfulqa: Measuring how models mimic human falsehoods

    Stephanie Lin, Jacob Hilton, and Owain Evans. Truthfulqa: Measuring how models mimic human falsehoods. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3214–3252, 2022

    work page 2022

  6. [5]

    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. In International Conference on Machine Learning, pages 17061–17084. PMLR, 2023

    2023

  7. [6]

    Undetectable watermarks for language models

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

    2024

  8. [7]

    Robust distortion-free watermarks for language models

    Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307.15593, 2023

    arXiv 2023

Show all 58 references
  1. [8]

    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. In The Twelfth International Conference on Learning Representations, 2024

    2024

  2. [9]

    Watermarking of large language models

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

    2023

  3. [10]

    Universally optimal watermarking schemes for llms: from theory to practice

    Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, and Yuheng Bu. Universally optimal watermarking schemes for llms: from theory to practice. arXiv preprint arXiv:2410.02890, 2024

    2024

  4. [11]

    A watermark for black-box language models

    Dara Bahri, John Wieting, Dana Alon, and Donald Metzler. A watermark for black-box language models. arXiv preprint arXiv:2410.02099, 2024

    2024

  5. [12]

    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, et al. Scalable watermarking for identifying large language model outputs. Nature, 634(8035):818–823, 2024

    2024

  6. [13]

    Water- marking text generated by black-box language models

    Xi Yang, Kejiang Chen, Weiming Zhang, Chang Liu, Yuang Qi, Jie Zhang, Han Fang, and Nenghai Yu. Water- marking text generated by black-box language models. arXiv preprint arXiv:2305.08883, 2023

    2023 arXiv

  7. [14]

    Subtle signatures, strong shields: Advancing robust and imper- ceptible watermarking in large language models

    Yubing Ren, Ping Guo, Yanan Cao, and Wei Ma. Subtle signatures, strong shields: Advancing robust and imper- ceptible watermarking in large language models. In Findings of the Association for Computational Linguistics ACL 2024, pages 5508–5519, 2024

    2024

  8. [15]

    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 The Twelfth International Conference on Learning Representations, 2024

    2024

  9. [16]

    Permute-and-flip: An optimally robust and watermarkable decoder for llms

    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

  10. [18]

    Provably robust multi-bit watermarking for AI-generated text via error correction code

    Wenjie Qu, Dong Yin, Zixin He, Wei Zou, Tianyang Tao, Jinyuan Jia, and Jiaheng Zhang. Provably robust multi-bit watermarking for AI-generated text via error correction code. arXiv preprint arXiv:2401.16820, 2024

    2024 arXiv

  11. [19]

    Debiasing watermarks for large language models via maximal coupling

    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

  12. [20]

    Adaptive text watermark for large language models

    Yepeng Liu and Yuheng Bu. Adaptive text watermark for large language models. In Forty-first International Conference on Machine Learning, 2024

    2024

  13. [21]

    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. 14 Optimized Couplings f...

    2023

  14. [22]

    Coding for channels with random parameters

    Israel Gel’Fand and Mark Pinsker. Coding for channels with random parameters. Probl. Contr. Inform. Theory, 9(1):19–31, 1980

    1980

  15. [23]

    An informationtheoretical approach to information embedding

    Frans MJ Willems. An informationtheoretical approach to information embedding. In 2000 Symposium on Information Theory in the Benelux, SITB 2000, pages 255–260. Werkgemeenschap voor Informatie-en Communi- catietheorie (WIC), 2000

    2000

  16. [24]

    Design and analysis of digital watermarking, information embedding, and data hiding systems

    Brian Chen. Design and analysis of digital watermarking, information embedding, and data hiding systems. PhD thesis, Massachusetts Institute of Technology, 2000

    2000

  17. [25]

    Information-theoretic analysis of information hiding

    Pierre Moulin and Joseph A O’Sullivan. Information-theoretic analysis of information hiding. IEEE Transactions on information theory, 49(3):563–593, 2003

    2003

  18. [26]

    Authentication with distortion criteria

    Emin Martinian, Gregory W Wornell, and Brian Chen. Authentication with distortion criteria. IEEE Transactions on Information Theory, 51(7):2523–2542, 2005

    2005

  19. [27]

    Text data-hiding for digital and printed documents: Theoretical and practical considerations

    Renato Villán, Sviatoslav V oloshynovskiy, Oleksiy Koval, J Vila, Emre Topak, Frédéric Deguillaume, Yuri Rytsar, and Thierry Pun. Text data-hiding for digital and printed documents: Theoretical and practical considerations. In Security, Steganography, and Watermarking of Multi...

    2006

  20. [28]

    Rethinking lossy compression: The rate-distortion-perception tradeoff

    Yochai Blau and Tomer Michaeli. Rethinking lossy compression: The rate-distortion-perception tradeoff. In International Conference on Machine Learning, pages 675–685. PMLR, 2019

    2019

  21. [29]

    A coding theorem for the rate-distortion-perception function

    Lucas Theis and Aaron B Wagner. A coding theorem for the rate-distortion-perception function. arXiv preprint arXiv:2104.13662, 2021

    2021 arXiv

  22. [30]

    On the rate-distortion-perception function

    Jun Chen, Lei Yu, Jia Wang, Wuxian Shi, Yiqun Ge, and Wen Tong. On the rate-distortion-perception function. IEEE Journal on Selected Areas in Information Theory, 3(4):664–673, 2022

    2022

  23. [31]

    Information theory: From coding to learning

    Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Cambridge university press, 2024

    2024

  24. [32]

    Waterbench: Towards holistic evaluation of watermarks for large language models

    Shangqing Tu, Yuliang Sun, Yushi Bai, Jifan Yu, Lei Hou, and Juanzi Li. Waterbench: Towards holistic evaluation of watermarks for large language models. arXiv preprint arXiv:2311.07138, 2023

    2023 arXiv

  25. [33]

    Towards optimal statistical watermarking

    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]

    Sok: Watermarking for ai-generated content

    Xuandong Zhao, Sam Gunn, Miranda Christ, Jaiden Fairoze, Andres Fabrega, Nicholas Carlini, Sanjam Garg, Sanghyun Hong, Milad Nasr, Florian Tramer, et al. Sok: Watermarking for ai-generated content. arXiv preprint arXiv:2411.18479, 2024

    2024 arXiv

  27. [35]

    Testing statistical hypotheses, volume 3

    Erich Leo Lehmann, Joseph P Romano, and George Casella. Testing statistical hypotheses, volume 3. Springer, 1986

    1986

  28. [36]

    Channel coding: Non-asymptotic fundamental limits

    Yury Polyanskiy. Channel coding: Non-asymptotic fundamental limits. Princeton University, 2010

    2010

  29. [37]

    Channel coding rate in the finite blocklength regime.IEEE Transactions on Information Theory, 56(5):2307–2359, 2010

    Yury Polyanskiy, H Vincent Poor, and Sergio Verdú. Channel coding rate in the finite blocklength regime.IEEE Transactions on Information Theory, 56(5):2307–2359, 2010

    2010

  30. [38]

    IEEE Transactions on Information Theory, 63(5):2629– 2658, 2016

    Jingbo Liu, Paul Cuff, and Sergio Verdú.eγ-resolvability. IEEE Transactions on Information Theory, 63(5):2629– 2658, 2016

    2016

  31. [39]

    Contraction of eγ-divergence and its applications to privacy

    Shahab Asoodeh, Mario Diaz, and Flavio P Calmon. Contraction of eγ-divergence and its applications to privacy. arXiv preprint arXiv:2012.11035, 2020

    2012 arXiv

  32. [40]

    Information Theory: From Coding to Learning

    Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2022

    2022

  33. [41]

    Elements of Information Theory

    Thomas M Cover and A Joy Thomas. Elements of Information Theory. Wiley, New-York, 2nd edition, 2006

    2006

  34. [42]

    Finite exchangeable sequences

    Persi Diaconis and David Freedman. Finite exchangeable sequences. The Annals of Probability, pages 745–764, 1980

    1980

  35. [43]

    The llama 3 herd of models

    Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024

    2024 arXiv

  36. [44]

    Gurobi Optimizer Reference Manual, 2024

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024

    2024

  37. [45]

    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. arXiv preprint arXiv:2306.04634, 2023. 15 Optimized Couplings fo...

    2023 arXiv

  38. [46]

    A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules

    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. arXiv preprint arXiv:2404.01245, 2024

    2024 arXiv

  39. [47]

    Mark my words: Analyzing and evaluating language model watermarks

    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

  40. [48]

    Markllm: An open-source toolkit for llm watermarking

    Leyi Pan, Aiwei Liu, Zhiwei He, Zitian Gao, Xuandong Zhao, Yijian Lu, Binglin Zhou, Shuliang Liu, Xuming Hu, Lijie Wen, et al. Markllm: An open-source toolkit for llm watermarking. arXiv preprint arXiv:2405.10051, 2024

    2024 arXiv

  41. [49]

    Evaluating durability: Benchmark insights into image and text watermarking

    Jielin Qiu, William Han, Xuandong Zhao, Shangbang Long, Christos Faloutsos, and Lei Li. Evaluating durability: Benchmark insights into image and text watermarking. Journal of Data-centric Machine Learning Research, 2024

    2024

  42. [50]

    A survey of text watermarking in the era of large language models

    Aiwei Liu, Leyi Pan, Yijian Lu, Jingjing Li, Xuming Hu, Xi Zhang, Lijie Wen, Irwin King, Hui Xiong, and Philip Yu. A survey of text watermarking in the era of large language models. ACM Computing Surveys, 57(2):1–36, 2024. 16 Optimized Couplings for Watermarking Large Language...

    2024

  43. [51]

    In this case, there is at least one possible value for eachqj that results in a nonnegative value off(qj)

    Thus we will focus on γ∈ (1,m ). In this case, there is at least one possible value for eachqj that results in a nonnegative value off(qj). First, we note that the mappingx7→x−γx2 is a concave function ofx forγ >0, whose maximum is obtained inx⋆ = 1 2γ . Therefore, we would li...

  44. [52]

    Generate B∼ Bernoulli(t)

  45. [53]

    If B = 0, drawZ∼R and setS =Y =Z

  46. [54]

    To show that this is a valid coupling, we verify the marginal distribution is kept the same

    If B = 1, drawS∼P′ andY ∼Q′ independently. To show that this is a valid coupling, we verify the marginal distribution is kept the same. We have: PS(a) = P(B = 0)R(a) + P(B = 1)P′(a) = (1 −t) P∧Q 1−t (a) +t P−P∧Q t (a) = P (a) Similarly, PY (a) = P(B = 0)R(a) + P(B = 1)Q′(a) = ...

  47. [55]

    Hence,H0 is rejected by CC detection test

    By construction of the Z-S channel, S =f(X,Bm). Hence,H0 is rejected by CC detection test. A.8 Proof of Proposition 3 We start by proving the following identity: TV QX,QX|(S,Bm)|PS,Bm = TV PS,PS|Y|PY Proof: Recall that in the correlated channel watermark we have side informati...

  48. [56]

    (60) 25 Optimized Couplings for Watermarking Large Language Models A PREPRINT Next, we consider the case for 1 3≤λ< 1

  49. [57]

    q∗ λ has three non-zero entries: q∗ λ = (λ,λ, 1− 2λ, 0,..., 0). Consequently, there are 4 cases with the corresponding ˆP (q∗ λ, b) andg(q∗ λ, b): a.B1 =B2 =B3 : ˆP = [1, 0,..., 0] g(q∗ λ, b) = 2(1− 1 k ) b.B1 =B2,B 3 :̸=B1 ˆP = [2λ, 1− 2λ, 0..., 0] g(q∗ λ, b) = (2λ− 1 k ) +|1...

  50. [58]

    1− s PS|Y (s|Y (X,bm)) P (s) # , whereP (S|Y ) is the correlated channel. AssumingS∼ Ber 1 2 , we have H2 PQ,P eQ = 2ES,X

    (61) Asm→∞ ,R∗ d(λ)→ 5 8. A.10 Proof of Theorem 4 Our results so far have been based on the discussion that it is sufficient to consider the optimal distributionP∗ Bm as one that selects b uniformly over a single permutation classB∗∈P m. Recall that b is a sequence ofm element...

Pith tools

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