# Can we Watermark Low-Entropy LLM Outputs?

arXiv: https://arxiv.org/abs/2604.12051 · HTML: https://mlsanity.com/paper/2604.12051/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 10 of its 13 references that are in the map.
- First posted on arXiv 13 Apr 2026.

## Placed in

- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

## Builds on (most cited first, 10 of 10)

- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [Undetectable Watermarks for Language Models](https://mlsanity.com/paper/2306.09194/) (2023)
- [Pseudorandom Error-Correcting Codes](https://mlsanity.com/paper/2402.09370/) (2024)
- [Provably Robust Watermarks for Open-Source Language Models](https://mlsanity.com/paper/2410.18861/) (2024)
- [Ideal Pseudorandom Codes](https://mlsanity.com/paper/2411.05947/) (2024)
- [New constructions of pseudorandom codes](https://mlsanity.com/paper/2409.07580/) (2024)
- [Improved Pseudorandom Codes from Permuted Puzzles](https://mlsanity.com/paper/2512.08918/) (2025)
- [Black-Box Crypto is Useless for Pseudorandom Codes](https://mlsanity.com/paper/2506.01854/) (2025)

## Abstract (arXiv)

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.