Source-linked AI summary
Undetectable Watermarks for Language Models
Miranda Christ, Sam Gunn, Or Zamir
TL;DR
The paper asks whether language-model watermarks can avoid detectable changes to model outputs, addressing the quality and detectability costs of prior schemes. It constructs cryptographically inspired undetectable watermarks with secret-key detection, unchanged output distributions, and guarantees that remain applicable under adaptive queries, while detection requires sufficient empirical entropy and the scheme remains removable in principle.
Problem
Existing watermarking schemes alter language-model output distributions detectably, creating the possibility of observable quality degradation.
Method
The paper constructs cryptographically inspired watermarks using a secret key and formalizes empirical entropy as the randomness condition supporting detection.
Results
The construction makes original and watermarked outputs computationally indistinguishable to users, while the secret key enables detection and independent text has negligible false-detection probability.
Takeaways & Limitations
Watermarks can preserve generated-text quality and remain undetectable under adaptive prompting while still supporting secret-key detection.
Takeaways & Limitations
Detection requires enough empirical entropy in the generated text, and no undetectable watermark can be completely unremovable.
Abstract
from arXiv · showhide
Recent advances in the capabilities of large language models such as GPT-4 have spurred increasing concern about our ability to detect AI-generated text. Prior works have suggested methods of embedding watermarks in model outputs, by noticeably altering the output distribution. We ask: Is it possible to introduce a watermark without incurring any detectable change to the output distribution? To this end we introduce a cryptographically-inspired notion of undetectable watermarks for language models. That is, watermarks can be detected only with the knowledge of a secret key; without the secret key, it is computationally intractable to distinguish watermarked outputs from those of the original model. In particular, it is impossible for a user to observe any degradation in the quality of the text. Crucially, watermarks should remain undetectable even when the user is allowed to adaptively query the model with arbitrarily chosen prompts. We construct undetectable watermarks based on the existence of one-way functions, a standard assumption in cryptography.
1 Introduction
The paper addresses the fragility and detectability costs of existing AI-text detection and watermarking methods by constructing watermarks that preserve the original output distribution. Its guarantees include secret-key detection, negligible false positives on independent text, and robustness to adaptive prompting, subject to sufficient empirical entropy for detection.
- Existing watermarking schemes noticeably change output distributions, allowing users to distinguish watermarked from original text and potentially observe quality degradation.
- The construction makes watermarks computationally infeasible to detect without the secret key, even under many adaptive queries.
- A secret key enables efficient detection from a contiguous response substring when enough randomness was used, without requiring other information.
- Text generated independently of the secret key has only a negligible chance of being detected as watermarked.
- The authors state that the construction’s undetectability and soundness hold for any LLM parameters without assumptions on the text, while noting vulnerability to simple watermark-removal attacks.
- The paper formalizes undetectable watermarks and empirical entropy, then constructs a single-response scheme whose output distribution is unchanged for users lacking the key.
2 Modeling the Problem
The paper models language models as token-distribution samplers and formalizes watermarking through completeness, soundness, and adaptive-query undetectability. Its guarantees depend on the empirical entropy of the specific generated response, with a substring-complete extension.
- 2.2 Language Models: A language model deterministically maps a prompt and prior tokens to a token distribution, then generates a response by iterative sampling until termination.Responses are modeled as random variables over token sequences of polynomially bounded length.
- 2.3 Entropy and Empirical Entropy: Empirical entropy, defined as the negative log-probability of the realized output under the original model, measures the random bits used to generate that specific response.The expected empirical entropy equals the Shannon entropy, but the paper applies the realized quantity to outputs and substrings.
- 2.4 Watermarks: A watermarking scheme consists of secret-key setup, randomized response generation, and a detector that maps token sequences to true or false.Completeness concerns detecting watermarked responses, while soundness concerns rejecting text generated independently of the secret key.
- 2.4 Watermarks: Completeness is restricted to outputs with empirical entropy at least b(L), because deterministic or very low-entropy responses cannot support detectable watermarking without changing them.The paper states that low-empirical-entropy outputs cannot be watermarked in any undetectable scheme.
- 2.5 Undetectable Watermarks: Undetectability requires computational indistinguishability between the original and watermarked models under adaptive arbitrary prompts, preserving quality for evaluations independent of the secret key.The formal property is paired with soundness and entropy-conditioned completeness in the paper’s main constructions.
- 2.6 Statement of our Theorems: The main construction is undetectable, sound, and complete for sufficiently high empirical entropy, while a modified scheme additionally provides substring completeness with similar parameters.The paper also introduces a simple weaker construction before presenting the efficient main scheme.
3 Simplified Construction
The simplified constructions use secret-key predicates or pseudorandom functions to watermark sufficiently random outputs while preserving undetectability, with explicit trade-offs in completeness, soundness, and efficiency.
- Limitations and open problem: The simple scheme has false-positive rate 1/poly(λ) and unbounded worst-case runtime, whereas the main construction is efficient and negligibly sound but has suboptimal completeness.Bridging this completeness gap remains an open problem.
- Random-oracle construction: The random-oracle scheme samples model outputs until O(x) = 0^b, then detects a response by checking the same predicate.This achieves completeness for selected outputs but requires 2^b expected model calls.
- Security properties: 2^-b is the weak-soundness false-positive rate, while predicate-conditioned outputs are detected as watermarked.The construction’s completeness follows directly from returning only outputs satisfying O(x) = 0^b.
- Removing the min-entropy assumption: The entropy-adaptive scheme leaves low-empirical-entropy outputs unchanged and watermarks only outputs exceeding the 6λ threshold.Its undetectability follows either because high-entropy outputs are rare or because the high-entropy conditional distribution has sufficient min-entropy.
- Removing the random-oracle assumption: The practical implementation replaces the random oracle with a PRF, requiring b = O(log λ) and yielding 2^-b-weak soundness.The simplified PRF scheme is undetectable and (6λ)-complete, with expected generation cost 1 + 2^b model calls.
4 Constructing Undetectable Watermarks
The main construction uses secret-key randomness to correlate outputs with a detector score without changing their distribution, then extends detection to long texts and high-entropy substrings.
- Motivation: A token-level biasing strategy is easily detectable because it changes token frequencies, motivating a watermark that preserves each token’s distribution.The target is to plant a detectable signal without noticeably altering the model’s output distribution.
- Single-response construction: For a single response, secret uniform values select tokens according to the model’s probabilities, so the watermarked output distribution remains unchanged without the key.The key determines each token while preserving its marginal probability under the original model.
- Detection: The detector aggregates token scores whose expectation is higher for watermarked text because secret values correlate with generated bits.For non-watermarked text, the secret values are independent of the output bits.
- Empirical entropy: High entropy is necessary for reliable detection because large score variance makes expectation-based arguments insufficient; empirical entropy supplies the relevant condition.The paper uses empirical entropy to construct effective distinguishers.
- Multiple responses: A PRF-based scheme removes the single-response length bound, while response identifiers and high-entropy prefixes support detection across multiple outputs.The identifier must be recoverable by the detector without being explicitly appended to the text.
- Formal guarantees: Theorems establish soundness, undetectability, and substring completeness for the resulting construction.The cited results include separate theorems for soundness, undetectability, and substring completeness.
- Substring completeness: The construction is extended to detect watermarks in any contiguous substring with sufficiently high empirical entropy.The modification resets the response identifier whenever enough new entropy is observed.
5 Necessity of Assumptions
The paper shows that undetectability has fundamental limits: efficient adversaries cannot detect nontrivial schemes, but unbounded computation or low-entropy outputs make detection possible. These results establish empirical entropy and computational boundedness as necessary conditions.
- Computational limitations: Undetectability is possible only against computationally bounded adversaries using polynomially many queries; exponential-time detection remains possible.This is proved in Lemma 4 for nontrivial watermarking schemes.
- Entropy limitations: Low empirical entropy outputs cannot be watermarked undetectably when a non-negligible fraction are watermarked.Such outputs can be detected with exp(t) queries and time when their empirical entropy is at most t.
- Entropy limitations: Model entropy alone is insufficient: some models generate arbitrarily high-entropy text while undetectable schemes watermark only a negligible fraction of outputs.The paper therefore requires empirical entropy of the specific output rather than standard model entropy.
- Computational limitations: The paper proves that computational assumptions are necessary because efficient indistinguishability does not imply identical output distributions.An unbounded distinguisher can statistically distinguish the original and watermarked models.
- Computational limitations: A statistical distinguisher can use polynomially many queries from a prompt producing watermarked outputs with non-negligible probability.The proof bounds the secret-key search using the key size and exponential running time.
- Entropy limitations: The detection bound for low-entropy outputs uses O(exp(t) · poly(λ)) queries and time.The argument approximates the probabilities of all outputs with empirical entropy at most t.
6 Removing Watermarks
The paper studies practical and theoretical watermark-removal attacks. Although undetectable schemes preserve the original distribution, they cannot be completely unremovable, especially for prefix-specifiable models.
- Limits of robustness: No undetectable watermarking scheme can be completely unremovable, although removal may require significantly more resources than ordinary generation.The paper presents both practical attacks and an expensive provable attack.
- Practical attacks: Practical attacks include emoji insertion, translation, paraphrasing, synonym substitution, and changing generation parameters.These attacks can remove or evade watermarks, though translation and heavier text changes may degrade quality.
- Practical attacks: The emoji attack removes watermarks that rely on detectors observing consecutive token sequences, including this paper’s scheme.The attacker inserts emojis between words and removes them afterward.
- Theoretical attack: For prefix-specifiable models, an efficient attack samples the watermarked model one token at a time by conditioning each query on the generated prefix.The attack constructs a response through repeated prefix-conditioned queries.
- Theoretical attack: The attacker’s resulting distribution is negligibly close in statistical distance to the original model’s distribution.Theorem 11 states that the number of queries equals the length of the generated output.
- Theoretical attack: Soundness then implies that the watermark is not detected in the attack output with non-negligible probability.Thus the attack removes the watermark while preserving near-original output distribution.
7 Open Problems
The paper leaves open how to strengthen robustness and improve the quantitative completeness guarantees of undetectable watermarks.
- Robustness: A central open problem is extending robustness beyond intact consecutive substrings to non-consecutive subsets of the output.The construction currently guarantees detection when a sufficiently high-empirical-entropy consecutive substring remains intact.
- Robustness: Another open question is whether undetectable watermarks can resist larger classes of removal techniques.The paper asks for the most general achievable robustness notion.
- Completeness: The main schemes may not achieve an optimal completeness parameter.The paper asks whether this gap can be closed by improving entropy requirements or proving stronger lower bounds.