Tracing Provenance and Detecting Tampering with Complementary LLM Watermarks

This paper introduces Cocktail, a watermarking scheme for large language models (LLMs) that simultaneously provides provenance tracing and tamper evidence, addressing the vulnerability of piggyback spoofing where an adversary alters critical content while retaining attribution.

Problem and Motivation:

Existing LLM watermarks preserve provenance under editing, but this robustness allows adversaries to modify content while keeping the watermark signal strong. The paper states: An adversary may alter critical details of watermarked text while keeping the signal strong, making the scheme endorse content the model did not generate. This attack is called piggyback spoofing. Countering this requires tamper evidence, which demands a signal sensitive to edits—the opposite of what provenance requires. Most schemes embed a single signal and face this dilemma.

Proposed Method:

Cocktail co-embeds two complementary signals into each generated token:

• A robust signal for provenance, using a short seeding window (hr = 1 token)

• A fragile signal for tamper evidence, using a long seeding window (full normalized prefix)

Both signals are seeded on normalized text (invisible-character cleanup, Unicode NFKC, homoglyph folding, whitespace collapsing) rather than token IDs, ensuring tamper evidence is defined over the content the reader receives rather than the token IDs that carry it.

The signals are co-embedded through vectorized tournament reweighting with multiple rounds of unbiased probability adjustments. A periodic pattern controls the strength ratio between signals (1:1, 2:1, or 4:1 robust-to-fragile). The method preserves the expected generation distribution: Because the lists are independent across rounds, unbiasedness is preserved after all d rounds, i.e., E[p̂(d)(x)] = p(x).

Detection:

Detection produces two z-scores (zr for robust, zf for fragile) forming a 2D score space supporting three decisions:

• Intact: zr > τr and zf > τf

• Tampered: zr > τr and zf ≤ τf

• No-Watermark: zr ≤ τr

Key Results:

1. Attribution: Cocktail attributes unattacked text at 99.7–100.0%, and under paraphrasing and round-trip translation, its 4:1 variant stays within a few points of the strongest single-signal baseline.

2. Tamper evidence: Every Cocktail variant flags 89.5–100.0% of tampered texts at a 1% false-alarm rate, whereas no baseline exceeds 23.1%. The paper states: Cocktail's lowest tamper-evidence score of 89.5 still exceeds the best baseline of 23.1 by over 66 points.

3. Generation quality: Perplexity stays within the baseline range (8.0–9.3 for Cocktail vs. 7.1–10.6 for baselines), confirming unbiased reweighting preserves quality.

Ablation Studies:

• Normalization at seeding time is required: Without normalization, homoglyph substitution cuts attribution to 33.6%; normalization at detection only recovers attribution but collapses tamper recall from 99.8% to 43.5%. Normalizing before seeding gives both sides the same canonical form, maintaining 98.3% tamper recall.

• Co-embedding outperforms one-signal-per-token: Assigning each token wholly to one signal drops attribution at T=50 from 98.3% to 86.0% and round-trip attribution from 89.8% to 60.2%.

• Long fragile window is necessary: When the fragile window shrinks to the robust one, Intact and tampered text collapse onto one diagonal cloud. Tamper evidence reaches 7.0% at nf=40 and 88.0% at nf=200.

Comparison with Bileve (closest prior work):

• Bileve signs token IDs, and re-tokenization fails verification on 91.1% of unmodified texts

• Bileve's perplexity rises to 62.2, six times Cocktail's 10.3

• Bileve's detection takes 144 seconds per text vs. Cocktail's closed-form scoring

Conclusion:

The paper concludes: "A signal that survives edits cannot also expose them, leaving single-signal watermarks open to piggyback spoofing. Cocktail escapes this conflict by co-embedding a robust and a fragile signal into every token through unbiased reweighting, both seeded on the text the reader receives, and read jointly as a three-state decision."

Improvements to AI systems:

1. Dual-signal watermarking for content integrity: AI text generators (e.g., chatbots, document writers) can embed both a robust watermark (for authorship verification) and a fragile watermark (for tamper detection) into every token. This allows the system to output a three-state verdict—intact, tampered, or no watermark—so users can trust that a document is both authentic and unaltered.

2. Edit-sensitive provenance tracking: The improved system can detect if critical content (e.g., numbers, dates, legal clauses) has been changed after generation, even if the text is paraphrased or translated. It flags subtle modifications that preserve fluency but alter meaning, preventing piggyback spoofing where an attacker edits a model's output while keeping attribution.

3. Canonical-text-based verification: By seeding watermarks on normalized text (Unicode NFKC, homoglyph folding, whitespace collapsing) rather than token IDs, the system verifies content as the reader sees it. This makes it robust to re-tokenization, font changes, or invisible-character attacks, ensuring verification succeeds on unmodified text and fails on tampered text.

4. Unbiased generation with quality preservation: The co-embedding method uses vectorized tournament reweighting with multiple independent rounds, preserving the expected token distribution. The improved system maintains near-baseline perplexity (e.g., 8.0–9.3 vs. 7.1–10.6), so watermarking does not degrade text quality or coherence.

5. Fast, closed-form detection: The system computes two z-scores (robust and fragile) in a single pass without iterative decoding or neural classifiers, enabling real-time verification (e.g., seconds per text vs. 144 seconds for prior work). This makes it practical for high-volume applications like news agencies, legal document review, or API-based content verification.

6. Adaptive strength control: The system can tune the robust-to-fragile signal ratio (1:1, 2:1, 4:1) based on use case—e.g., higher robust ratio for long-term provenance across heavy editing, higher fragile ratio for strict tamper detection in contracts or medical records.

7. Resilience to normalization attacks: The system normalizes text before seeding, not just at detection, so homoglyph substitution or whitespace manipulation cannot evade tamper evidence. This closes a known vulnerability where attackers exploit token-ID-based signatures.

8. Three-state decision interface: The improved AI system can expose a simple API that returns intact, tampered, or no watermark for any text, enabling downstream tools (e.g., plagiarism checkers, fact-checkers, content moderation) to automatically reject or flag altered AI-generated content.

What the improved AI system can do:

• Generate watermarked text that is provably attributable to the model and provably unaltered.

• Detect any post-generation edit—even subtle ones—while still attributing the original text to the model.

• Operate in multilingual, Unicode-rich environments without breaking verification.

• Provide tamper evidence at >89% recall with 66 points.

• Maintain generation quality and speed, making it deployable in production LLM services, document generation pipelines, and content authenticity platforms.