Abstract: Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which satisfy: (a) undetectability, a cryptographic notion introduced by Christ, Gunn & Zamir (2024) which stipulates that it is computationally hard to distinguish watermarked language model outputs from the model's actual output distribution; and (b) robustness to channels which introduce a constant fraction of adversarial insertions, substitutions, and deletions to the watermarked text. Earlier schemes could only handle stochastic substitutions and deletions, and thus we are aiming for a more natural and appealing robustness guarantee that holds with respect to edit distance. Our main result is a watermarking scheme which achieves both undetectability and robustness to edits when the alphabet size for the language model is allowed to grow as a polynomial in the security parameter. To derive such a scheme, we follow an approach introduced by Christ & Gunn (2024), which proceeds via first constructing pseudorandom codes satisfying undetectability and robustness properties analogous to those above; our key idea is to handle adversarial insertions and deletions by interpreting the symbols as indices into the codeword, which we call indexing pseudorandom codes. Additionally, our codes rely on weaker computational assumptions than used in previous work. Then we show that there is a generic transformation from such codes over large alphabets to watermarking schemes for arbitrary language models.
Introduction
As AI-generated content becomes increasingly prevalent, the ability to reliably identify machine-authored text is essential for maintaining information integrity and preventing plagiarism. Watermarking—the process of embedding hidden signals into a model's output—offers a promising solution. However, effective watermarking must navigate a difficult "trilemma":
- Undetectability: The watermark must be cryptographically indistinguishable from the model's original distribution, ensuring no degradation in text quality.
- Soundness: The system must maintain a near-zero false-positive rate to avoid misidentifying human text as AI-generated.
- Robustness: The watermark must survive adversarial attempts to remove it, such as synonym swapping, sentence deletion, or the insertion of "fluff" text.
While previous research achieved undetectability, these schemes were often fragile. Specifically, they relied on the exact positioning of tokens; a single deletion could shift the entire sequence, breaking the alignment required for detection. This paper addresses this gap by introducing a scheme robust to adversarial edit distance.
The Innovation: Indexing Pseudorandom Codes
The core contribution of this work is the development of Indexing Pseudorandom Codes (PRCs). Traditional watermarking treats text as a rigid sequence. In contrast, the indexing approach interprets symbols from a large alphabet as indices into a codeword.
By treating the watermark as a "bag of indexed symbols" rather than a fragile chain, the decoder can "re-synchronize" even if the text has been shifted or padded by an adversary. This allows the watermark to remain detectable even after a constant fraction of the text has been modified through insertions, deletions, or substitutions.
Methodology
The authors construct their solution through a modular three-step reduction:
- Binary Substitution PRCs: The foundation is a code robust to simple bit-flips (substitutions). Notably, the authors utilize Weak Pseudorandom Functions (PRFs). This is a "Minicrypt" assumption, which is computationally lighter and more efficient than the public-key cryptography (Cryptomania) required by prior works.
- Indexing PRCs: The binary code is extended to handle insertions and deletions by using symbols to encode their own relative positions. This indexing mechanism is the key to surviving edit-distance attacks.
- Watermarking Transformation: Finally, the authors provide a generic mathematical framework to apply these codes to any autoregressive language model. They use a random hash function to map the LLM's high-dimensional token space into the code's alphabet, ensuring the watermark is embedded without distorting the model's original probability distribution.
Key Results
The paper's primary theoretical contribution is Theorem 5.2, which proves the existence of a watermarking scheme that is simultaneously sound, undetectable, and robust to a constant fraction of edits (specifically $c\alpha^2$, where $\alpha$ is the entropy rate).
Key takeaways include:
- Entropy-Dependent Robustness: The scheme's resilience is tied to the model's entropy. If a model is highly predictable (low entropy), it is mathematically harder to hide a robust watermark. The proposed scheme scales its robustness based on the available entropy in the generated text.
- Large Alphabet Efficiency: The scheme is particularly effective for modern LLMs, which typically use large tokenizers (vocabularies of 32k to 100k+ tokens). The proof requires the alphabet size to grow as a polynomial in the security parameter, a condition satisfied by most contemporary models.
Limitations and Future Directions
As a theoretical breakthrough, the work identifies several avenues for future research. While the scheme is asymptotically efficient, real-world implementation will require optimizing the hashing and decoding steps to minimize latency during text generation. Additionally, while the current proof focuses on large alphabets, future work could explore achieving similar edit-distance robustness over smaller alphabets (e.g., binary strings).
By moving the field toward more efficient cryptographic primitives and providing the first provable defense against adversarial edits, this research represents a significant step toward practical and secure AI provenance.
Summary updated