Research map / Adversarial robustness and security / Attacks on text and graphs
Edit Distance Robust Watermarks via Indexing Pseudorandom Codes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Builds watermarks for language models that are undetectable and robust to a constant fraction of adversarial edits (substitutions, insertions, deletions) by constructing "indexing pseudorandom codes" over polynomial-size alphabets from local weak PRFs.
Problem
Watermarking LLM outputs with provable undetectability and robustness to a constant fraction of adversarial edits (edit distance), rather than only i.i.d. or substitution noise.
Approach
Interpret symbols of a large alphabet as indices into a binary substitution-robust PRC codeword (with random redundant hash mapping psi), so insertions/deletions only change a few decoded positions; then a generic reduction turns large-alphabet PRCs into substring-robust watermarks via hashing the LM's token distribution.
Key results
- Main theorem: under local weak PRFs with log n-locality, watermark is sound, undetectable, and substring-robust to any c*alpha^2-edit-bounded channel, with alphabet size n^{O((1/alpha) log(1/alpha))}.
- Indexing PRC is robust to (1-Omega(p0))-edit-bounded channels given a substitution PRC robust to (1/2-p0) substitutions and redundancy rho >= C0/p0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use indexing with redundant alphabet symbols to convert a substitution-robust PRC into an edit-robust PRC | Substitution PRCs · Polynomial-sized alphabet | edit-robustness fraction: 1-C_rob p_0 | Helped |
| Apply rejection-sampling watermarking transformation to an edit-robust PRC | PRC · Language models with sufficiently large alphabets | edit-robustness fraction: α^2/48 | Helped |
| Use a random hash from the language-model alphabet to the PRC alphabet | Watermarking from PRCs · High-entropy language-model text | substitution error fraction in the embedded PRC codeword: 1-Ω(α) | Helped |
Surprising findings
- Earlier distortion-free watermarks with edit robustness only tolerate sub-constant fractions of insertions/deletions, and the prior undetectable-style reduction needed the LM to behave like a binary symmetric channel.
Limitations
- Alphabet size must grow polynomially in the security parameter, exponentially in 1/alpha, so not practical for current LLM vocabularies.
- Requires constant entropy rate of generated text; near-deterministic models cannot be watermarked.
- Relies on local weak PRF assumption, which is not standard and is only shown to follow from hardness of learning sparse parities/juntas.
Experimental setup
Baselines: Christ & Gunn 2024 substitution-robust PRC watermark Kirchenbauer et al. green-list watermark Kuditipudi et al. distortion-free watermark
Builds on: pseudorandom codes (Christ & Gunn 2024) undetectable watermarks (Christ, Gunn & Zamir 2023) synchronization strings substring robustness
Closest papers by meaning
- Provable Robust Watermarking for AI-Generated Text (ICLR 2024 · similarity 0.91)
- Watermarks in the Sand: Impossibility of Strong Watermarking for Language Models (ICML 2024 · similarity 0.91)
- Black-Box Detection of Language Model Watermarks (ICLR 2025 · similarity 0.90)
- A Semantic Invariant Robust Watermark for Large Language Models (ICLR 2024 · similarity 0.89)
- On the Learnability of Watermarks for Language Models (ICLR 2024 · similarity 0.89)
- Adaptive Text Watermark for Large Language Models (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.