Watermarking › Watermark Robustness

A watermark that dissolves under mild editing is not useful. Any practical deployment must assume that adversaries will attempt to remove or spoof the watermark. Robustness research characterizes what attacks are possible and how schemes can be designed to resist them.

The tension here is fundamental. The watermark signal lives in token choices, and any operation that changes tokens has the potential to reduce the signal. But many legitimate text transformations change tokens: editing for clarity, correcting errors, translating to another language, summarizing, quoting, or continuing text all involve token changes. A robust watermark must survive these benign transformations while remaining detectable, which is an inherently difficult requirement.

Attacks on watermarks fall into three categories, each with different goals and requirements for the attacker.

Removal attacks attempt to eliminate the watermark signal while preserving semantic content. The attacker has the watermarked text and wants to produce a clean version that passes no watermark test. Examples include:

• Paraphrase attacks: Using a second language model (or human) to rewrite the text in different words. If the watermark is tied to specific token choices, paraphrasing that changes those tokens may remove the signal. The effectiveness depends on how aggressively the paraphraser rewrites and whether synonym substitutions happen to preserve green token rates by chance.
• Word substitution: Replacing individual words with synonyms using a thesaurus or masked language model. Each substitution may flip a token from green to red or vice versa. Targeted substitution, where only red-list words are replaced with green-list alternatives, would theoretically increase the z-score (an insertion attack) rather than decrease it, so naive word substitution reduces the signal randomly rather than systematically.
• Translation attacks: Translating to a different language and back. The round-trip typically changes many tokens while preserving meaning, potentially removing enough of the green-token signal to defeat detection. This is one of the more effective practical attacks because translation systems are widely available and produce fluent text.
• Cropping and insertion: Removing tokens from the end of the text (reducing $T$ and thus statistical power) or inserting red-list tokens to dilute the green-token fraction. Inserting 50 randomly chosen tokens into a 100-token watermarked text can reduce the z-score significantly, depending on how many of the inserted tokens happen to be green.

Forgery attacks attempt to produce watermarked text without knowing the key. If an attacker can generate text that passes the watermark test, they can falsely attribute text to the watermarking entity, creating a false provenance claim. Forgery is generally much harder than removal because it requires knowing the green list partition, which is derived from the secret key. Without the key, an attacker cannot systematically choose tokens that will score highly under the detector. They could try to brute-force the key space, but cryptographic hash functions make this computationally infeasible.

Spoofing attacks target the detector's behavior rather than any specific watermark. An attacker who knows the detection algorithm (but not the key) might generate a large volume of texts and submit them for detection, attempting to overwhelm the system or to learn information about the key from which texts pass and which fail. Against an oracle detector, an attacker can conduct a binary search over the vocabulary: submit a text, observe whether it passes, modify one token, repeat. Over many queries, this allows the attacker to infer which tokens are green in specific contexts.

The KGW scheme has been analyzed extensively for robustness. Paraphrase attacks are the most effective known removal attack. Because paraphrasing changes specific words, each substituted token may be on the red list in the new context, reducing the green-token count. With enough substitutions, the z-score drops below the detection threshold.

The key variable is how many tokens must be changed to remove the watermark. If a text has 200 tokens and needs to maintain a z-score above 2.33, it needs approximately $\gamma T + 2.33 \sqrt{T \gamma (1-\gamma)} \approx 123$ green tokens out of 200 (with $\gamma = 0.5$). An attacker who substitutes 30% of tokens (60 tokens) reduces the expected green count by roughly 30 tokens, potentially pushing the z-score below the threshold.

The quality-robustness tradeoff is important here. Each token substitution changes the text slightly. If the substitutions preserve meaning well (synonyms, reorderings), the quality cost is low. If they degrade meaning significantly, the attacker has succeeded only by making the text worse. The question is whether a sufficiently capable paraphraser can substitute enough tokens to defeat the watermark at acceptable quality cost. Kirchenbauer et al. showed empirically that naive paraphrase attacks using T5 or GPT-3.5 as the paraphraser could reduce TPR substantially at typical detection thresholds, suggesting that soft watermarks are not fully robust against capable paraphrasers. Newer, more capable paraphrase models increase this vulnerability.

Several techniques improve robustness against token-level modifications, each with its own tradeoffs.

Context window extension: Instead of hashing only the previous token to determine the green list, hash the previous $k$ tokens. This creates longer-range dependencies in the watermark signal. An attacker who substitutes one token must also verify that the change does not cascade: since each green list depends on the preceding $k$ tokens, changing token at position $t$ alters the green lists at positions $t+1$ through $t+k$, potentially undoing other carefully chosen substitutions. The cost is computational: detection requires re-computing the green list for each position based on a window of preceding tokens, and detecting the watermark after arbitrary edits requires alignment between the original and edited sequences.

Robust statistics: Replacing the z-test on raw green counts with a more robust test statistic. For example, a test based on the fraction of runs of consecutive green tokens is more resistant to isolated red-token insertions than a simple count. If an attacker inserts single red tokens between otherwise green sequences, the run-based test can partially discount these interruptions. The tradeoff is reduced detection power on unattacked texts, because the robust statistic is less sensitive than the optimal z-test under the clean watermarked distribution.

Edit distance-aware detection: Detecting the watermark not in the exact sequence of tokens but in the closest matching alignment between the candidate text and the expected green-list pattern. This requires solving an alignment problem similar to dynamic programming sequence alignment, which is computationally more expensive than a simple token scan but enables detection after arbitrary insertions and deletions. The statistic is based on the alignment score rather than a simple count, making it robust to the cropping and insertion attacks that defeat naive detection.

Synonym-resilient watermarking: Embedding the watermark at the semantic level by using multiple green-list tokens that are near-synonyms. If "happy," "glad," and "pleased" are all on the green list for a given context, then synonym substitution between these words does not remove the signal. Designing such coherent green lists requires additional structure beyond random partitioning, but the robustness gains can be significant against synonym-based attacks.

One direction for achieving robustness is to embed the watermark in semantic content rather than specific token choices. A semantically invariant watermark produces a signal that survives paraphrasing because it is tied to concepts or propositions, not surface forms.

Implementing this is challenging because it requires the model to have fine-grained semantic control over its output at a level that current decoding-time watermarks do not. Some proposals encode bits into the choice of which facts to include or emphasize rather than which words to use. For example, a model might be instructed to include certain supporting details in one variant of an explanation and different details in another, with the pattern of included details encoding the watermark. These approaches are more resistant to paraphrase because paraphrasing changes words but typically preserves the factual content of a passage.

The practical challenges are substantial. Semantic watermarks require a sophisticated encoding and decoding scheme that operates at the discourse level rather than the token level. The signal capacity per sentence is much lower because there are fewer discrete choices about what facts to include than about which tokens to use. Detection requires understanding the semantic content of the text, which is a harder problem than counting green tokens. These approaches remain largely in the research prototype stage.

The security of watermarking schemes relies on the secret key remaining private. If an attacker learns the key, they can generate text that passes the watermark test (forgery) or identify the green list and avoid those tokens entirely (targeted removal). The security model is analogous to symmetric cryptography: the scheme is secure as long as the key is not disclosed.

Multi-key schemes address this by using different keys for different users or time periods. An enterprise deploying a watermarked LLM might issue different keys to different departments, so that if one department's key is leaked, only texts generated with that key are compromised. Key rotation limits the exposure window: even if an attacker infers the key from a corpus of watermarked texts generated during a specific period, future texts use a different key.

The more fundamental vulnerability is oracle access: an attacker who can submit texts to the detector and observe whether they pass can, in principle, reconstruct which tokens are green by binary search. Against this oracle attack, context-dependent watermarks are more resistant than fixed-partition unigram watermarks, because the attacker's query tells them the partition only at specific context strings. If the attacker changes the preceding token, the partition changes completely. A context-dependent scheme requires the attacker to conduct a separate oracle attack for each context, making full key reconstruction computationally expensive even with unlimited query access.

Rate limiting and query monitoring are operational mitigations. If the detector logs queries and flags accounts that submit suspiciously many queries, the oracle attack becomes detectable. The attacker must balance information gain per query against the risk of detection, which limits how much of the key space they can probe.