# Edit Distance Robust Watermarks via Indexing Pseudorandom Codes

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 46 references that are in the map.
- First posted on arXiv 4 Jun 2024.

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

- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Generating Diverse High-Fidelity Images with VQ-VAE-2](https://mlsanity.com/paper/1906.00446/) (2019)
- [Scaling Autoregressive Models for Content-Rich Text-to-Image Generation](https://mlsanity.com/paper/2206.10789/) (2022)
- [Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Prediction](https://mlsanity.com/paper/2404.02905/) (2024)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Vector-quantized Image Modeling with Improved VQGAN](https://mlsanity.com/paper/2110.04627/) (2021)
- [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)
- [On the Reliability of Watermarks for Large Language Models](https://mlsanity.com/paper/2306.04634/) (2023)
- [A Semantic Invariant Robust Watermark for Large Language Models](https://mlsanity.com/paper/2310.06356/) (2023)
- [Unbiased Watermark for Large Language Models](https://mlsanity.com/paper/2310.10669/) (2023)
- [Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models](https://mlsanity.com/paper/2311.04378/) (2023)
- [On the Learnability of Watermarks for Language Models](https://mlsanity.com/paper/2312.04469/) (2023)
- [Publicly-Detectable Watermarking for Language Models](https://mlsanity.com/paper/2310.18491/) (2023)
- [Adaptive Text Watermark for Large Language Models](https://mlsanity.com/paper/2401.13927/) (2024)
- [Pseudorandom Error-Correcting Codes](https://mlsanity.com/paper/2402.09370/) (2024)
- [Excuse me, sir? Your language model is leaking (information)](https://mlsanity.com/paper/2401.10360/) (2024)
- [Deletion codes in the high-noise and high-rate regimes](https://mlsanity.com/paper/1411.6667/) (2014)
- [Edit Distance in Near-Linear Time: it's a Constant Factor](https://mlsanity.com/paper/2005.07678/) (2020)
- [Synchronization Strings and Codes for Insertions and Deletions -- a Survey](https://mlsanity.com/paper/2101.00711/) (2021)
- [Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes](https://mlsanity.com/paper/1605.04611/) (2016)
- [Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound](https://mlsanity.com/paper/1704.00807/) (2017)

## Built on by (most cited first, 13 of 13)

- [An Undetectable Watermark for Generative Image Models](https://mlsanity.com/paper/2410.07369/) (2024)
- [SoK: Watermarking for AI-Generated Content](https://mlsanity.com/paper/2411.18479/) (2024)
- [AdaDetectGPT: Adaptive Detection of LLM-Generated Text with Statistical Guarantees](https://mlsanity.com/paper/2510.01268/) (2025)
- [On the Impossibility of Separating Intelligence from Judgment: The Computational Intractability of Filtering for AI Alignment](https://mlsanity.com/paper/2507.07341/) (2025)
- [Marking Code Without Breaking It: Code Watermarking for Detecting LLM-Generated Code](https://mlsanity.com/paper/2502.18851/) (2025)
- [Learn-to-Distance: Distance Learning for Detecting LLM-Generated Text](https://mlsanity.com/paper/2601.21895/) (2026)
- [Position: LLM Watermarking Should Align Stakeholders' Incentives for Practical Adoption](https://mlsanity.com/paper/2510.18333/) (2025)
- [Verifying LLM Inference to Detect Model Weight Exfiltration](https://mlsanity.com/paper/2511.02620/) (2025)
- [WaterMod: Modular Token-Rank Partitioning for Probability-Balanced LLM Watermarking](https://mlsanity.com/paper/2511.07863/) (2025)
- [AI Security in the Foundation Model Era: A Comprehensive Survey from a Unified Perspective](https://mlsanity.com/paper/2603.24857/) (2026)
- [Watermark Smoothing Attacks against Language Models](https://mlsanity.com/paper/2407.14206/) (2024)
- [Watermarks for Language Models via Probabilistic Automata](https://mlsanity.com/paper/2512.10185/) (2025)
- [Pin It on Anyone: Certified Targeted Displacement of Multi-Bit LLM Watermarks Without the Key](https://mlsanity.com/paper/2610.18359/) (2026)

## Abstract (arXiv)

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.