pith. machine review for the scientific record. sign in

arxiv: 2604.08759 · v1 · submitted 2026-04-09 · 💻 cs.IT · cs.CL· math.IT

Recognition: unknown

Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints

Chao Tian, Krishna Narayanan, Yu-Shin Huang

Authors on Pith no claims yet

Pith reviewed 2026-05-10 16:45 UTC · model grok-4.3

classification 💻 cs.IT cs.CLmath.IT
keywords multi-bit watermarkinggenerative watermarkingfalse-alarm constraintmiss-detection probabilitylinear programlanguage modelsencoding constructionsfinite-token regime
0
0 comments X

The pith

Two new encoding-decoding constructions attain the established lower bound on miss-detection probability for multi-bit generative watermarking under worst-case false-alarm constraints.

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

The paper shows that a prior scheme for embedding multiple bits of watermark information into text generated by language models fails to reach the best possible performance. It introduces two alternative constructions that match the known lower bound on the chance of missing the watermark while keeping the worst-case false-alarm rate under control. The design problem is cast as a linear program whose solutions reveal the exact structural conditions for optimality in the finite-token setting. This settles the achievable trade-off between reliable detection and low false alarms when watermarking generated text.

Core claim

The central claim is that two new encoding-decoding constructions attain the previously established lower bound on the achievable miss-detection probability, thereby completely characterizing the optimal multi-bit watermarking performance under the worst-case false-alarm constraint in the finite-token regime. The approach formulates the watermark design problem as a linear program and derives the structural conditions under which optimality holds, while also identifying the failure mechanism of the earlier construction and comparing the practical tradeoffs of the two new schemes.

What carries the argument

A linear program formulation of the watermark design problem that yields the structural conditions required for optimality.

If this is right

  • Optimal multi-bit watermarking performance is now completely characterized and achievable.
  • Concrete encoding-decoding methods exist that reach the lowest possible miss-detection probability for any given worst-case false-alarm constraint.
  • The failure mechanism of the previous scheme is understood, so similar errors can be avoided in future designs.
  • The two constructions offer distinct implementation tradeoffs that can be selected according to application needs.

Where Pith is reading between the lines

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

  • The optimal constructions could make verification of AI-generated text more dependable in practice by minimizing undetected watermarks.
  • The linear program approach may extend naturally to other constraint types or to regimes with varying token lengths.
  • These schemes provide a baseline for studying how multi-bit watermarks hold up when an adversary attempts to erase or alter them.

Load-bearing premise

The linear program correctly models the watermarking channel and the prior lower bound on miss-detection probability is tight.

What would settle it

A direct computation for a small number of tokens and bits that shows whether the miss-detection probability of either new construction exactly equals the value of the earlier lower bound.

Figures

Figures reproduced from arXiv: 2604.08759 by Chao Tian, Krishna Narayanan, Yu-Shin Huang.

Figure 1
Figure 1. Figure 1: Diagram of a generative watermarking system. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

This paper considers the problem of multi-bit generative watermarking for large language models under a worst-case false-alarm constraint. Prior work established a lower bound on the achievable miss-detection probability in the finite-token regime and proposed a scheme claimed to achieve this bound. We show, however, that the proposed scheme is in fact suboptimal. We then develop two new encoding-decoding constructions that attain the previously established lower bound, thereby completely characterizing the optimal multi-bit watermarking performance. Our approach formulates the watermark design problem as a linear program and derives the structural conditions under which optimality can be achieved. In addition, we identify the failure mechanism of the previous construction and compare the tradeoffs between the two proposed schemes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper considers multi-bit generative watermarking for LLMs under a worst-case false-alarm constraint in the finite-token regime. It demonstrates that a prior construction claimed to achieve an existing lower bound on miss-detection probability is in fact suboptimal, formulates the watermark design problem as a linear program, derives structural conditions for optimality, and proposes two new encoding-decoding constructions that attain the lower bound, thereby completely characterizing optimal performance. The work also identifies the failure mechanism of the prior scheme and compares tradeoffs between the new constructions.

Significance. If the LP formulation is shown to be a tight abstraction of the generative channel and the constructions are proven to achieve the bound without relaxation gaps, this work provides a complete characterization of the fundamental limits of multi-bit watermarking under worst-case false-alarm constraints. The explicit identification of the prior scheme's failure mechanism and the derivation of structural optimality conditions represent a clear advance over previous partial results.

major comments (2)
  1. [§3] §3 (LP formulation): The central claim that the two new constructions attain the prior lower bound requires that the linear program exactly encodes the worst-case false-alarm constraint without relaxation gaps arising from averaging over prompts or relaxing token-probability dependence in the finite-sequence generative model. An explicit argument or theorem showing that every feasible LP point maps to an achievable encoding-decoding scheme (and vice versa) is needed to confirm tightness.
  2. [§4] §4 (Constructions and optimality proof): The structural conditions derived from the LP must be shown to be both necessary and sufficient for the specific finite-token regime; the mapping from optimal LP solution to the concrete encoding and decoding procedures should be stated with sufficient detail to allow independent verification that the miss-detection probability matches the lower bound.
minor comments (2)
  1. [Abstract] The abstract and introduction should include a brief statement of the precise finite-token regime (sequence length, alphabet size) under which the lower bound and constructions hold.
  2. [§2] Notation for the worst-case false-alarm probability and the miss-detection probability should be standardized across sections to avoid ambiguity when comparing the new schemes to the prior one.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and insightful comments on our manuscript. The suggestions regarding the tightness of the LP formulation and the explicit mapping in the optimality proofs are valuable, and we will incorporate clarifications to strengthen these sections. We address each major comment below.

read point-by-point responses

  1. Referee: [§3] §3 (LP formulation): The central claim that the two new constructions attain the prior lower bound requires that the linear program exactly encodes the worst-case false-alarm constraint without relaxation gaps arising from averaging over prompts or relaxing token-probability dependence in the finite-sequence generative model. An explicit argument or theorem showing that every feasible LP point maps to an achievable encoding-decoding scheme (and vice versa) is needed to confirm tightness.

    Authors: We agree that an explicit bijection is essential to rigorously confirm that the LP captures the generative channel without gaps. In the revised manuscript, we will add a dedicated theorem in §3 establishing this equivalence: for any feasible LP solution, we construct a corresponding encoding-decoding scheme by directly assigning token probabilities per prompt (respecting the finite-token model) that achieves the exact worst-case false-alarm probability; conversely, any valid scheme induces a feasible LP point via its induced probabilities. This eliminates any averaging relaxations and confirms the LP is a tight abstraction. revision: yes

  2. Referee: [§4] §4 (Constructions and optimality proof): The structural conditions derived from the LP must be shown to be both necessary and sufficient for the specific finite-token regime; the mapping from optimal LP solution to the concrete encoding and decoding procedures should be stated with sufficient detail to allow independent verification that the miss-detection probability matches the lower bound.

    Authors: The structural conditions are derived as necessary via the LP's optimality criteria (including dual feasibility and complementary slackness) and are sufficient because we explicitly construct the schemes from the optimal solution. In the revision, we will expand §4 with a precise algorithmic mapping: the optimal LP variables dictate bit-to-token group assignments and detection thresholds; encoding samples tokens accordingly, and decoding computes a score that yields the exact miss-detection probability matching the LP objective (and thus the lower bound). A self-contained proof of this equality for the finite-token regime will be included to enable independent verification. revision: yes

Circularity Check

0 steps flagged

No significant circularity; constructions are independent of the cited lower bound

full rationale

The paper cites a prior lower bound on miss-detection probability (established externally) and demonstrates that an earlier scheme fails to meet it. It then introduces two new encoding-decoding constructions, formulates the design problem as a linear program, and verifies that these constructions satisfy the structural optimality conditions derived from the LP, thereby attaining the external bound. No equation or step reduces the claimed optimality to a fitted parameter, a self-referential definition, or a load-bearing self-citation whose validity is assumed rather than independently established. The LP acts as an analytical device to characterize achievable schemes rather than presupposing the result. This is a standard, non-circular use of prior bounds plus new explicit constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review is abstract-only, so ledger is limited; paper relies on prior lower bound and LP formulation without introducing free parameters or new entities in the summary.

axioms (2)
  • domain assumption The previously established lower bound on miss-detection probability holds in the finite-token regime under worst-case false-alarm constraints.
    Central to claiming that the new constructions are optimal.
  • domain assumption The watermarking design problem admits a linear programming formulation with identifiable structural conditions for optimality.
    Invoked to derive the new constructions and optimality conditions.

pith-pipeline@v0.9.0 · 5420 in / 1280 out tokens · 52476 ms · 2026-05-10T16:45:25.377428+00:00 · methodology

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. Fundamental Trade-Offs in Multi-Bit Watermarking of Stochastic Processes

    cs.IT 2026-05 unverdicted novelty 5.0

    Derives matched converse and achievability bounds that characterize optimal trade-offs among false-alarm probability, detection error probability, distortion, and information rate for multi-bit watermarking of station...

Reference graph

Works this paper leans on

38 extracted references · 16 canonical work pages · cited by 1 Pith paper

  1. [1]

    Digital watermarking,

    I. J. Cox, M. L. Miller, J. A. Bloom, J. Fridrich, and T. Kalker, “Digital watermarking,” Morgan Kaufmann Publishers, vol. 54, no. 56-59, p. 2, 2008

    2008

  2. [2]

    Codemark: Imperceptible watermarking for code datasets against neural code completion models,

    Z. Sun, X. Du, F. Song, and L. Li, “Codemark: Imperceptible watermarking for code datasets against neural code completion models,” inProceedings of the 31st ACM joint European soft- ware engineering conference and symposium on the foundations of software engineering, 2023, pp. 1561–1572

    2023

  3. [3]

    Learning to watermark llm-generated text via reinforcement learning.arXiv preprint arXiv:2403.10553, 2024

    X. Xu, Y. Yao, and Y. Liu, “Learning to watermark llm-generated text via reinforcement learning,”arXiv preprint arXiv:2403.10553, 2024

    work page arXiv 2024

  4. [4]

    On the learnability of watermarks for language models.arXiv preprint arXiv:2312.04469,

    C. Gu, X. L. Li, P. Liang, and T. Hashimoto, “On the learnability of watermarks for language models,”arXiv preprint arXiv:2312.04469, 2023

    work page arXiv 2023

  5. [5]

    Deep learning-based dual watermarking for image copyright protection and authentication,

    S. K. Padhi, A. Tiwari, and S. S. Ali, “Deep learning-based dual watermarking for image copyright protection and authentication,”IEEE Transactions on Artificial Intelligence, vol. 5, no. 12, pp. 6134–6145, 2024

    2024

  6. [6]

    arXiv preprint arXiv:2307.16230

    A. Liu, L. Pan, X. Hu, S. Li, L. Wen, I. King, and P. S. Yu, “An unforgeable publicly verifiable watermark for large language models,”arXiv preprint arXiv:2307.16230, 2023

    work page arXiv 2023

  7. [7]

    Deeptextmark: a deep learning-driven text watermarking approach for identifying large language model generated text,

    T. Munyer, A. A. Tanvir, A. Das, and X. Zhong, “Deeptextmark: a deep learning-driven text watermarking approach for identifying large language model generated text,”Ieee Access, vol. 12, pp. 40 508–40 520, 2024

    2024

  8. [8]

    A reinforcement learning framework for robust and secure llm watermarking,

    L. An, Y. Liu, Y. Liu, Y. Bu, Y. Zhang, and S. Chang, “A reinforcement learning framework for robust and secure llm watermarking,” inProceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), 2026, pp. 7181–7198

    2026

  9. [9]

    Watermarking of large language models,

    S. Aaronson, “Watermarking of large language models,” https://simons.berkeley.edu/talks/ scott-aaronson-ut-austin-openai-2023-08-17, Aug. 2023, talk page, Simons Institute for the Theory of Computing. Accessed: 2026-03-28

    2023

  10. [10]

    Theoretically grounded framework for llm watermarking: A distribution-adaptive approach,

    H. He, Y. Liu, Z. Wang, Y. Mao, and Y. Bu, “Theoretically grounded framework for llm watermarking: A distribution-adaptive approach,”arXiv preprint arXiv:2410.02890, 2024

    work page arXiv 2024

  11. [11]

    Distributional information embedding: A framework for multi-bit watermarking,

    ——, “Distributional information embedding: A framework for multi-bit watermarking,” in The 1st Workshop on GenAI Watermarking, 2025

    2025

  12. [12]

    A watermark for large language models,

    J. Kirchenbauer, J. Geiping, Y. Wen, J. Katz, I. Miers, and T. Goldstein, “A watermark for large language models,” inInternational conference on machine learning. PMLR, 2023, pp. 17 061–17 084

    2023

  13. [13]

    Robust distortion- free watermarks for language models.arXiv preprint arXiv:2307.15593, 2023

    R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang, “Robust distortion-free watermarks for language models,”arXiv preprint arXiv:2307.15593, 2023

    work page arXiv 2023

  14. [14]

    Provable robust watermarking for AI-generated text.arXiv preprint arXiv:2306.17439, 2023

    X. Zhao, P. Ananth, L. Li, and Y.-X. Wang, “Provable robust watermarking for ai-generated text,”arXiv preprint arXiv:2306.17439, 2023

    work page arXiv 2023

  15. [15]

    Adaptive text watermark for large language models.arXiv preprint arXiv:2401.13927,

    Y. Liu and Y. Bu, “Adaptive text watermark for large language models,”arXiv preprint arXiv:2401.13927, 2024

    work page arXiv 2024

  16. [16]

    Unbiased watermark for large language models,

    Z. Hu, L. Chen, X. Wu, Y. Wu, H. Zhang, and H. Huang, “Unbiased watermark for large language models,”arXiv preprint arXiv:2310.10669, 2023

    work page arXiv 2023

  17. [17]

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

    Y. Wu, Z. Hu, J. Guo, H. Zhang, and H. Huang, “A resilient and accessible distribution- preserving watermark for large language models,”arXiv preprint arXiv:2310.07710, 2023

    work page arXiv 2023

  18. [18]

    arXiv preprint arXiv:2406.10281 , year=

    P. Chao, Y. Sun, E. Dobriban, and H. Hassani, “Watermarking language models with error correcting codes,”arXiv preprint arXiv:2406.10281, 2024

    work page arXiv 2024

  19. [19]

    Scalable watermarking for identifying large language model outputs,

    S. Dathathri, A. See, S. Ghaisas, P.-S. Huang, R. McAdam, J. Welbl, V. Bachani, A. Kaskasoli, R. Stanforth, T. Matejovicovaet al., “Scalable watermarking for identifying large language model outputs,”Nature, vol. 634, no. 8035, pp. 818–823, 2024

    2024

  20. [20]

    Optimized couplings for watermarking large language models,

    C. X. Long, D. Tsur, C. M. Verdun, H. Hsu, H. Permuter, and F. P. Calmon, “Optimized couplings for watermarking large language models,” in2025 IEEE International Symposium on Information Theory (ISIT). IEEE, 2025, pp. 1–6

    2025

  21. [21]

    Duwak: Dual watermarks in large language models,

    C. Zhu, J. Galjaard, P.-Y. Chen, and L. Chen, “Duwak: Dual watermarks in large language models,” inFindings of the Association for Computational Linguistics: ACL 2024, 2024, pp. 11 416–11 436

    2024

  22. [22]

    Necessary and sufficient watermark for large language models

    Y. Takezawa, R. Sato, H. Bao, K. Niwa, and M. Yamada, “Necessary and sufficient watermark for large language models,”arXiv preprint arXiv:2310.00833, 2023

    work page arXiv 2023

  23. [23]

    Improved unbiased watermark for large language models,

    R. Chen, Y. Wu, J. Guo, and H. Huang, “Improved unbiased watermark for large language models,” inProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2025, pp. 20 587–20 601

    2025

  24. [24]

    Undetectable watermarks for language models,

    M. Christ, S. Gunn, and O. Zamir, “Undetectable watermarks for language models,” inThe Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024, pp. 1125–1139

    2024

  25. [25]

    Optimizing watermarks for large language models,

    B. Wouters, “Optimizing watermarks for large language models,”arXiv preprint arXiv:2312.17295, 2023

    work page arXiv 2023

  26. [26]

    On the reliability of watermarks for large language models,

    J. Kirchenbauer, J. Geiping, Y. Wen, M. Shu, K. Saifullah, K. Kong, K. Fernando, A. Saha, M. Goldblum, and T. Goldstein, “On the reliability of watermarks for large language models,” arXiv preprint arXiv:2306.04634, 2023

    work page arXiv 2023

  27. [27]

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

    A. Liu, L. Pan, Y. Lu, J. Li, X. Hu, X. Zhang, L. Wen, I. King, H. Xiong, and P. Yu, “A survey of text watermarking in the era of large language models,”ACM Computing Surveys, vol. 57, no. 2, pp. 1–36, 2024

    2024

  28. [28]

    Watermarking for large language models: A survey,

    Z. Yang, G. Zhao, and H. Wu, “Watermarking for large language models: A survey,”Mathe- matics, vol. 13, no. 9, p. 1420, 2025

    2025

  29. [29]

    Stealthink: A multi-bit and stealthy watermark for large language models, 2025

    Y. Jiang, C. Wu, M. K. Boroujeny, B. Mark, and K. Zeng, “Stealthink: A multi-bit and stealthy watermark for large language models,”arXiv preprint arXiv:2506.05502, 2025

    work page arXiv 2025

  30. [30]

    Towards codable text watermarking for large lan- guage models.arXiv preprint arXiv:2307.15992,

    L. Wang, W. Yang, D. Chen, H. Zhou, Y. Lin, F. Meng, J. Zhou, and X. Sun, “Towards codable watermarking for injecting multi-bits information to llms,”arXiv preprint arXiv:2307.15992, 2023

    work page arXiv 2023

  31. [31]

    Advancing beyond identification: Multi-bit watermark for large language models,

    K. Yoo, W. Ahn, and N. Kwak, “Advancing beyond identification: Multi-bit watermark for large language models,” inProceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), 2024, pp. 4031–4055

    2024

  32. [32]

    Multi-bit distortion-free watermarking for large language models.arXiv preprint arXiv:2402.16578, 2024

    M. K. Boroujeny, Y. Jiang, K. Zeng, and B. Mark, “Multi-bit distortion-free watermarking for large language models,”arXiv preprint arXiv:2402.16578, 2024

    work page arXiv 2024

  33. [33]

    Information-theoretic analysis of watermarking,

    P. Moulin and J. A. O’Sullivan, “Information-theoretic analysis of watermarking,” in2000 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings (Cat. No. 00CH37100), vol. 6. IEEE, 2000, pp. 3630–3633

    2000

  34. [34]

    The role of information theory in watermarking and its application to image watermarking,

    P. Moulin, “The role of information theory in watermarking and its application to image watermarking,”Signal Processing, vol. 81, no. 6, pp. 1121–1139, 2001

    2001

  35. [35]

    The gaussian watermarking game,

    A. S. Cohen and A. Lapidoth, “The gaussian watermarking game,”IEEE transactions on Information Theory, vol. 48, no. 6, pp. 1639–1667, 2002

    2002

  36. [36]

    On random coding error exponents of watermarking systems,

    N. Merhav, “On random coding error exponents of watermarking systems,”IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 420–430, 2002

    2002

  37. [37]

    Identification in the presence of side information with application to watermarking,

    Y. Steinberg and N. Merhav, “Identification in the presence of side information with application to watermarking,”IEEE Transactions on Information Theory, vol. 47, no. 4, pp. 1410–1422, 2002

    2002

  38. [38]

    Fundamental trade-offs in multi-bit watermarking of stochastic processes,

    H. He, Y. Liu, Z. Shen, Z. Wang, Y. Mao, and Y. Bu, “Fundamental trade-offs in multi-bit watermarking of stochastic processes,” Preprint via personal communication, 2026

    2026