Edit Distance Robust Watermarks for Language Models

Noah Golowich, Ankur Moitra

This research paper, "Edit Distance Robust Watermarks via Indexing Pseudorandom Codes," by Noah Golowich and Ankur Moitra (MIT), presents a significant theoretical breakthrough in the field of AI safety. It introduces the first watermarking scheme for Large Language Models (LLMs) that is simultaneously undetectable (cryptographically indistinguishable from real text) and robust to adversarial edit distance (insertions, deletions, and substitutions).

TL;DR

The authors develop a novel watermarking framework that embeds hidden cryptographic signals into LLM outputs. Unlike previous methods that break when a user adds or removes a few words, this scheme remains detectable even after significant adversarial mangling, thanks to a new technique called "Indexing Pseudorandom Codes."

What Problem Does This Paper Address?

As AI-generated content proliferates, the ability to reliably identify it becomes crucial for preventing plagiarism and misinformation. However, watermarking faces a "trilemma" of competing goals:

  1. Quality/Undetectability: The watermark shouldn't change the "feel" or statistical distribution of the text.
  2. Soundness: We shouldn't get "false positives" (accusing a human of using AI).
  3. Robustness: An adversary shouldn't be able to remove the watermark by simply editing the text (e.g., swapping synonyms, deleting sentences, or inserting fluff).

Previous "undetectable" watermarks were fragile; they often relied on the exact position of tokens. If an adversary deleted the first word, the entire detection alignment would shift, rendering the watermark invisible. This paper specifically tackles edit distance robustness—the ability to survive arbitrary, adversarial changes to the text.

Methods

The authors build their solution through a three-step modular reduction:

  1. Binary Substitution PRCs: They first construct a Pseudorandom Code (PRC) over a binary alphabet that is robust to simple bit-flips (substitutions). Notably, they achieve this using Weak Pseudorandom Functions (PRFs), a "Minicrypt" assumption that is much lighter than the public-key cryptography used in prior work.
  2. Indexing PRCs: This is the core innovation. To handle insertions and deletions, they interpret symbols from a large alphabet not just as data, but as indices into a codeword. By treating the text as a set of indexed values rather than a rigid sequence, the decoder can "re-synchronize" even if the text has been shifted or padded by an adversary.
  3. Watermarking Transformation: They provide a generic mathematical "wrapper" 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.

Datasets

This is a theoretical research paper focused on provable guarantees and algorithmic construction. Consequently, no empirical datasets (like C4 or WikiText) were used for training or evaluation. The results are presented as mathematical proofs that hold for any language model satisfying certain entropy requirements.

Key Insights and Ideas

  • Indexing as Synchronization: The "aha moment" is moving away from sequence-based detection. By making each token "know" its own relative position through indexing, the watermark becomes a "bag of indexed symbols" rather than a fragile chain.
  • The Entropy Requirement: The authors prove that robustness is tied to the entropy rate of the model. If a model is highly predictable (low entropy), it is mathematically harder to hide a watermark without it being detectable. Their scheme scales its robustness based on the available entropy in the text.
  • Weaker Cryptographic Assumptions: By showing that these watermarks only require local weak PRFs, the authors move the field toward more efficient, "Minicrypt"-based primitives, which are generally preferred over heavier "Cryptomania" (public-key) assumptions.

Key Results

  • Provable Robustness: The scheme can tolerate a constant fraction of adversarial edits. If an adversary changes $1\%$ or $5\%$ of the text (depending on the entropy), the watermark remains detectable with high probability.
  • Theorem 5.2 (Main Result): The authors formally prove the existence of a watermarking scheme that is sound, undetectable, and robust to a $c\alpha^2$ fraction of edits (where $\alpha$ is the entropy rate) for any language model over a sufficiently large alphabet.
  • Large Alphabet Efficiency: The scheme works efficiently when the LLM's alphabet size is polynomial in the security parameter—a condition met by most modern LLM tokenizers (which often have vocabularies of 32k to 100k+ tokens).

Limitations and Future Work

  • Alphabet Size Blowup: While the scheme works for large alphabets, the current proof requires the alphabet size to grow as a polynomial of the security parameter. The authors suggest that future work could aim for similar robustness over smaller (e.g., binary) alphabets.
  • Computational Practicality: As a theoretical work, the "efficiency" mentioned is in the asymptotic sense ($O(poly(\lambda))$). Real-world implementation would require optimizing the hashing and decoding steps to ensure they don't add significant latency to text generation.
  • Fine-Grained Analysis: The authors note that their robustness bounds ($O(\alpha^2)$) might be improvable through more fine-grained average-case hardness assumptions.

Summary updated

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.
BibTeX
@article{golowich2024edit,
  author = {Noah Golowich and Ankur Moitra},
  title = {{Edit Distance Robust Watermarks for Language Models}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2024},
  url = {https://openreview.net/forum?id=StmFOcXZPr},
}

Loading related content...

Figure