Can we Watermark Low-Entropy LLM Outputs?

Computer Science > Cryptography and Security [Submitted on 13 Apr 2026] Can we Watermark Low-Entropy LLM Outputs? Noam Mazor, Andrew Morgan, Rafael Pass A recent and exciting thread of work focuses on developing methods for watermarking the output of large language models (LLMs). We focus on provably undetectable watermarking-that is, schemes that do not alter the output distribution of the LLM, yet enable embedding a watermark in the output that identifies the output as having been generated by the particular LLM. Furthermore, the watermark should be hard to remove by an adversary that may potentially edit, insert, or delete tokens from the watermarked output. Indeed, recent work (Christ et al. [COLT'24], Christ et al. [CRYPTO'24], Golowich et al. [NeuroIPS'24]) shows how to develop such schemes that are robust against a constant fraction of substitutions, or even against a constant fraction of arbitrary edits. These works, however, make strong assumptions on the entropy present in the output of the LLM. Most notably, they all require constant entropy rate-that is, a constant fraction of the tokens in a sufficiently long substring of the output need to have empirical entropy at least O(log |T|), where T is the alphabet of tokens, and Golowich et al. additionally require T to be larger than the security parameter. In this work, we consider whether we can also watermark the outputs of LLMs when the per-token entropy is just a constant, discarding the dependence on the alphabet size or security parameter. In this regime, we construct: - A watermarking scheme robust against random substitutions (assuming subexponential LPN, as in Christ et al. [CRYPTO'24]) - A watermarking scheme robust against random substitutions and random deletions, given either the additional heuristic assumption that the output of the LLM only introduces random errors (analogous to the assumption made by Christ et al. [CRYPTO'24]) or a construction of a pseudorandom error-correcting code robust to adversarial substitutions and random deletions. Comments: 27 pages. To be published in FORC 2026 Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2604.12051 [cs.CR]   (or arXiv:2604.12051v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2604.12051 Focus to learn more Submission history From: Andrew Morgan [view email] [v1] Mon, 13 Apr 2026 20:47:08 UTC (6,214 KB) Access Paper: view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-04 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)