PaperlayerView exact revision on arXiv

Source-linked AI summary

Semantic Watermarking with Order-Robust Detection over Sub-sentence Units

Abdulrahman Diaa, Jonathan Petit, Florian Kerschbaum

arXiv:2608.27666v1cs.CRcs.AIcs.CL

TL;DR

Semantic watermarks can be evaded when rewording, reordering, or resegmentation displaces the embeddings tested by the detector. The paper introduces EDA to measure this vulnerability and (k)-SwordStamp to reduce dependence on attacker-controlled structure, achieving lower attack success at a small fidelity cost.

  • Problem

    Content-preserving rewording, reordering, and resegmentation can change the units or embeddings observed by semantic watermark detectors.

  • Method

    The paper develops EDA, a no-box adaptive attack maximizing embedding displacement, and (k)-SwordStamp with best-of-N, order-robust detection, and sub-sentence units.

  • Results

    32.6%–47.9% of outputs retained 90% content preservation while removing four encoder-based watermarks at 5% FPR; adapted EDA reached 10.8% against k-SwordStamp.

  • Takeaways & Limitations

    Reducing dependence on attacker-controlled text structure improves resistance to content-preserving watermark removal within the tested settings.

  • Takeaways & Limitations

    The evaluation is limited to English news continuations up to 256 tokens from one provider model, with one paraphraser and surrogate encoder and model-based fidelity scores.

Abstract

from arXiv · show

Semantic watermarks tie the mark to sentence meaning rather than token choices, promising robustness to content-preserving edits. However, the detector only observes attacker-supplied text, which can be reworded, reordered, or resegmented to evade detection without content loss. Rewording, reordering, and resegmentation all cause embedding displacement: detection tests embeddings different from those selected during watermarking and can therefore lose the mark. Our adaptive embedding displacement attack (EDA) admits all three edits under a single objective that maximizes this displacement. It uses a public paraphraser and surrogate encoder without access to the provider's generator or secret key. At a 5% false-positive rate (FPR) and content-preservation threshold $\bar{q}=90\%$, EDA successfully removes the mark on between 32.6% and 47.9% of documents across four schemes, the highest among the tested attacks. Therefore, EDA evaluates the schemes' robustness more thoroughly than passive paraphrasing. To address these vulnerabilities, we design (k)-SwordStamp: semantic watermarks with order-robust detection over sub-sentence units, reducing sensitivity to attacker-chosen structure at a small quality cost. Against k-SwordStamp, the strongest no-box attack we test is an EDA variant adapted to its design, with a 10.8% attack-success rate. A stronger EDA with access to the provider's detector and secret key reaches a 39.7% attack-success rate, compared with 65.5% on k-SemStamp. Our code is available at https://github.com/D-Diaa/SwordStamp.

1 Introduction

The paper shows that structure-changing edits can displace encoder embeddings enough to evade semantic watermarks, motivating EDA and the more structure-robust (k)-SwordStamp design.

  • Attack vulnerability: Rewording, reordering, and resegmentation can change the embedding or tested position, defeating evaluations limited to sentence-by-sentence paraphrasing.Each edit causes detection to evaluate an embedding different from the one selected during watermarking.
  • Attack method: EDA rewrites whole text adaptively, selecting candidates farthest from each source sentence under a public surrogate encoder without querying the provider’s detector or generator.Surrogate displacement also tends to predict displacement under provider encoders, enabling no-box attacks that can reorder content and alter boundaries.
  • Attack vulnerability: 32.6%–47.9% of marked documents met the 90% content-preservation threshold while evading four encoder-based watermarks under EDA at 5% FPR.EDA achieved the highest success among the tested attacks on each scheme.
  • Defense: (k)-SwordStamp combines best-of-N selection, fixed valid sets, and deterministic sub-sentence units to reduce sensitivity to attacker-controlled structure.The mechanisms extend (k)-SemStamp with order-robust detection and semspan-like units.
  • Defense: 22.5 percentage points lower scheme-specific EDA success was achieved by k-SwordStamp versus k-SemStamp, with a 4.4-percentage-point fidelity cost.At the same 5% FPR and 90% content-preservation operating point, SwordStamp also reduced success relative to SemStamp by 29.2 percentage points at a 1.8-point fidelity cost.
  • Stress test: 39.7% attack success against k-SwordStamp under detector-access EDA compared with 65.5% on k-SemStamp shows improved robustness even with secret-key access.At the largest search budget, 85.4% evaded detection, but only 46.5% also met the content-preservation threshold.

2 Text Watermarking

The paper frames text watermarks as keyed statistical signals and contrasts token-level schemes with encoder-based methods that mark sentence meaning, including their context and order dependencies.

  • Watermarking foundations: A text watermark is defined by randomized setup, watermarking, and detection algorithms that leave a keyed statistical trace in generated text.Detection maps suspect text and the secret key to a score, with larger scores indicating stronger evidence.
  • Token-level watermarks: Token-level watermarks partition the vocabulary into green and red lists, then bias generation toward green tokens.KGW derives the split from preceding-token context, while Unigram uses one fixed split for the entire generation.
  • Token-level watermarks: Context-dependent token partitions are fragile because one substitution can alter the current hit and reseed later token partitions.The fixed Unigram split avoids this particular propagation mechanism.
  • Encoder-based watermarks: Encoder-based watermarks assign regions to sentence embeddings, so each sentence inherits a semantic mark from its embedding region.All studied encoder-based watermarks depend on a sentence encoder to place and verify the mark.
  • Encoder-based watermarks: SemStamp uses LSH regions and context-dependent valid sets, while k-SemStamp replaces hyperplane regions with k-means Voronoi cells.Both schemes generate sentences by rejection sampling and use private encoders or partition geometry.
  • Other encoder-based schemes: PMark constructs position-specific partition boundaries from candidate samples and aggregates channel-sentence evidence with a soft z-test.Its boundaries are recomputed from candidates at each sentence position.
  • Other encoder-based schemes: SAMark uses one channel bit per query, making sentence scoring order-robust, but infers that bit from the suspect text through majority voting.Its self-anchored vote rewards text concentrated on one side of a channel, whether or not it is watermarked.

3 Threat Model

The threat model frames watermark removal as an attacker’s attempt to evade detection while preserving marked-text content. It distinguishes provider and attacker capabilities and defines success through joint detection evasion and quality preservation.

  • The provider watermarking algorithm is public, but generation uses a secret key and verification flags texts exceeding an FPR-calibrated threshold.
  • The primary no-box attacker observes only released marked text and cannot query the provider’s detector or generator.It may use open paraphrasers and sentence encoders, but is restricted to lower-fidelity generators.
  • Attack success requires lowering the detection score to or below τ(ρ) while retaining Q(x,y) ≥ ¯q.Discarding content can evade detection but fails the quality constraint.
  • The attack-success probability averages over secret keys, marked texts from fixed-distribution prompts, attack randomness, and PMark detector resampling.The corresponding ASR@ρ estimates the percentage of marked texts meeting both conditions at the target FPR.
  • Provider evaluation balances pre-attack output fidelity against attack success across the robustness frontier.Fidelity F(x) scores marked text alone, whereas Q(x,y) compares attacked text with its originating marked text.

4 Edit Sensitivity and EDA

The paper treats rewording, reordering, and resegmentation as sources of embedding displacement and combines them in an adaptive no-box attack. EDA selects paraphrases that maximize surrogate displacement, which tracks provider-encoder displacement and defeats tested schemes more effectively than passive paraphrasing.

  • Edit Sensitivity: Reordering and resegmentation expose structural weaknesses beyond the in-place rewording covered by the usual robustness premise.Reordering changes position-dependent context, while resegmentation changes the units recovered and tested by the detector.
  • Edit Sensitivity: PMark sentence permutations can return its hit count to random because position-keyed bits are independent and uniform.Its dynamic partition also introduces a second mismatch after reordering.
  • Edit Sensitivity: Controlled edits separately vary wording, sentence order, or sentence boundaries while keeping the other edit types nearly unchanged.Reorder preserves sentence text; split and merge respectively increase and decrease detector unit count.
  • Edit Sensitivity: Embedding displacement measures the distance between the embedding selected during marking and the embedding tested after editing.The attack uses larger displacement as a surrogate for crossing watermark-region boundaries.
  • EDA: EDA-P reverses provider sampling by selecting, from K paraphrases, the candidate farthest from its source under a public surrogate encoder.It generates positions until EOS or 512 tokens and can produce output with different length from the marked text.
  • EDA: Conditional provider-encoder displacement rises with surrogate displacement for SemStamp and PMark, supporting the surrogate-selection strategy.The candidate is conditioned on the full marked text and prior rewrites, allowing splitting, merging, reordering, and deferred content.
  • EDA: EDA-P requires no secret key, watermark partition geometry, or provider encoder, so it applies across all evaluated embedding-based watermarks.Its no-box design uses only attacker-side models and the released marked text.

5 Robustness Mechanisms for EBWs

The design addresses whole-text edit sensitivity by increasing embedding margin, removing positional dependence, and marking semantically delimited sub-sentence units. These mechanisms target rewording, reordering, and resegmentation while exposing explicit fidelity and security trade-offs.

  • 5.1 Best-of-N Selection: Best-of-N selects candidates deepest inside valid regions, giving content-preserving rewrites more displacement before crossing a watermark boundary.It emits the deepest valid candidate when available and otherwise the blocked candidate nearest a boundary.
  • 5.1 Best-of-N Selection: Best-of-N evaluates a fixed pool of N candidates, replacing sequential rejection sampling with batched scoring and increased provider draws.The trade-off is between greater boundary depth and provider generation cost.
  • 5.2 Fixed Valid Sets: A fixed valid set G is reused at every position, so detection counts units in G independently of predecessor context.The detector inserts the hit count and recovered-unit count into its calibrated test statistic.
  • 5.2 Fixed Valid Sets: Because the fixed-set hit count does not depend on position, sentence permutation leaves the count and unit number unchanged, preventing one moved unit from re-keying another test.Rewording still loses a hit when an embedding crosses into the blocked set B.
  • 5.2 Fixed Valid Sets: Fixed valid sets preserve the target FPR through null-text calibration, but topically concentrated unmarked passages can inflate scores and reduce unattacked marked-text detection.The calibrated threshold is reported for each configuration.
  • 5.2 Fixed Valid Sets: The fixed valid set is not an unconditional security boundary: recovering it requires many marked-text queries, and its secrecy assumption is excluded from the no-box threat model.At c = 8, the fixed histogram and context-dependent transition matrix differ only by a constant factor.
  • 5.3 Semspans: Semspans are contiguous word sequences recursively delimited at the largest local embedding change, subject to window, length, and function-word constraints.The segmenter first splits sentences, then recursively cuts any sentence-derived unit longer than L.
  • 5.3 Semspans: Semspans reduce segmentation sensitivity because encoder-guided cuts can survive sentence merging, while finer units increase unit counts and provider draws.Finer units also repeat boundary-depth selection more often, potentially affecting marked-text fidelity.

6 Robustness, Fidelity, and Cost

The evaluation measures controlled edit effects, no-box and detector-access attack success, clean detection, quality, and generation costs. k-SwordStamp improves robustness, especially under EDA, while robustness mechanisms introduce fidelity and computational trade-offs.

  • Experimental setup: The evaluation reports clean detection, generation cost, output quality, and robustness using ASR@5% while sweeping content preservation from 65% to 95%.Attack settings are selected to maximize ASR at each content-preservation threshold.
  • Score loss by edit type: Each controlled edit changes its target edit rate while leaving the other two near zero, and k-SemStamp loses retention under rewording, reordering, and resegmentation.The results support embedding displacement caused by attacker-controlled structure.
  • Score loss by edit type: Adding semspans raises resegmentation retention above every sentence-based stage, while the fixed valid set eliminates reordering-induced score loss.Best-of-N improves rewording retention but does not eliminate its score loss; diversity ranking trades retention for fidelity and lower repetition.
  • Robustness under detector access: At K = 4, detector-access raw evasion is 70.2% on k-SemStamp and 29.6% on k-SwordStamp; after quality gating, ASR is 19.4%–39.7% versus 52.2%–65.5%.More search raises raw evasion but lowers content preservation for selected k-SwordStamp rewrites.
  • Clean performance and costs: The fixed valid set reduces ASR against Dipper and EDA-S but requires higher detection thresholds, while best-of-N reduces no-box ASR at a larger fidelity cost on k-means.Semspans supply additional robustness, and diversity ranking improves fidelity and reduces repetition while trading away some robustness.
  • Clean performance and costs: At 5% FPR, clean TPR is 94.9% for SwordStamp and 97.0% for k-SwordStamp, while their EDA-S ASRs are 18.7% and 10.8%, respectively.SAMark has lower EDA-S ASR at 32.6% but also the lowest clean TPR among the comparison schemes.

7 Limitations and Future Work

The evaluation is limited to English news continuations from one provider model and relies on model-based quality judgments. Future work includes quality-aware attacks and provider-side quality optimization.

  • Evaluation scope: The evaluation covers English news continuations up to 256 tokens from one provider model, so transfer to other tasks, languages, lengths, and model families is unestablished.Different settings may require different segmentation rules and content-preservation definitions.
  • Evaluation scope: The study tests two provider encoders but only one EDA paraphraser and surrogate encoder, and uses model-based rather than human fidelity and content-preservation judgments.These choices constrain the breadth and form of the evaluation evidence.
  • Future work: Neither EDA nor EDA-D uses a quality oracle during candidate selection, so quality-aware attackers could produce a different ASR–content-preservation tradeoff.The provider could also use task-specific quality scores to recover part of the measured fidelity loss.
  • Future work: A provider could fine-tune its generator to produce watermarked samples from a smaller candidate pool because the fixed valid set creates a static signal.This follows the paper’s stated provider-side future-work direction.

8 Related Work

Related work spans post-hoc detection, token- and encoder-based watermarks, candidate selection, paraphrase-centered robustness evaluations, and impossibility results under stronger attacker assumptions.

  • Watermarking versus post-hoc detection: Post-hoc detectors avoid generator cooperation but rely on empirical error estimates and rarely reach deployment-level low FPRs, whereas watermarking uses a keyed signal during generation.The comparison frames proactive watermarking as a way to control FPR during generation.
  • Watermark families: Token-level watermarks tie signals to token choices, while encoder-based watermarks raise the marking unit to sentence meaning and verify it with sentence embeddings.The paper evaluates encoder-based watermarks alongside several alternative EBW signal constructions.
  • Candidate selection and distortion: WaterMax and related black-box methods select the most detectable generated chunks, while this paper applies the same detection-strength trade-off at sentence or semspan level.Best-of-N scores candidates by how far inside their valid region they fall.
  • Attacks and robustness evaluations: Prior robustness evaluations center on paraphrasing, including sentence-by-sentence tests for k-SemStamp, while this work adds whole-text paraphrasing under matched attacker capabilities and content preservation.Whole-text paraphrase was identified as the boundary of earlier k-SemStamp robustness results.
  • Impossibility results: Prior impossibility results assume stronger quality or perturbation oracles, whereas the paper’s no-box attacker has neither oracle and uses a weaker generator than the provider’s.The comparison distinguishes the paper’s threat model from oracle-based impossibility settings.

9 Conclusion

EDA consolidates rewording, reordering, and resegmentation into a single adaptive no-box attack, removing watermarks from 32.6%–47.9% of outputs at 5% FPR with 90% content preservation. k-SwordStamp reduces the adapted EDA attack-success rate to 10.8%, at a 4.4-point fidelity cost.

  • 32.6%–47.9% of outputs retained 90% content while EDA removed their watermarks at 5% FPR.
  • EDA unifies rewording, reordering, and resegmentation through a shared embedding-displacement objective.
  • 10.8% attack success was achieved against k-SwordStamp by scheme-adapted EDA, with a 4.4-percentage-point fidelity cost.
  • Within the tested models, workloads, attacks, and budgets, reducing dependence on attacker-controlled text structure improved resistance to content-preserving watermark removal.

A.1 Controlled-Edit Results

Table 3 shows that the controlled edits are near-isolated to the properties they measure.

  • A.1 Controlled-Edit Results: Table 3 reports that the controlled edits are near-isolated.The edits remain focused on the properties they are intended to measure.
  • A.1 Controlled-Edit Results: The controlled edits primarily affect what they measure.
  • A.1 Controlled-Edit Results: The results indicate limited spillover beyond each edit’s measured target.

A.2 Quality Judges and Criteria

The evaluation uses separate model-based judges for reference-free fidelity and content preservation, with independently rated criteria and explicit aggregation rules. These scores measure writing quality and agreement with the marked reference, not factual accuracy or universal equivalence among content errors.

  • Separate judges distinguish prompt-conditioned writing quality from content preservation relative to the marked text.
  • Fidelity uses the source prompt and generated continuation without a reference answer, while the preservation judge compares marked text x with attacked text y.
  • The aggregate combines fluency, coherence, relevance, and informativeness with equal weighting, while content-error ratings are inverted.
  • Each judge rates four criteria independently on a 0-to-5 scale.
  • The judges use Qwen/Qwen3-32B with three random seeds, and unparseable responses are excluded.
  • These measures do not establish factual accuracy, may preserve errors in the marked reference, and encode equal weights as a measurement choice rather than a universal equivalence.

A.3 Fidelity by Criterion

The appendix reports criterion-level fidelity, controlled attack mixtures, quality gating, and illustrative watermarked-versus-attacked examples. It shows that stronger or more diverse attacks can reduce quality-pass rates and that structural edit channels differ across EDA configurations.

  • Fidelity by Criterion: Criterion means for SwordStamp were 1.4–2.1 percentage points lower than SemStamp, while k-SwordStamp was 3.2–6.5 points lower than k-SemStamp.
  • Attack Mixtures: EDA settings produce different edit mixtures: increasing Dipper’s order setting from 20 to 80 raised mean reordering from 6.6% to 19.5%.
  • Quality Gating: At Dipper setting 80, 48.5% of order-sweep evasions met the quality threshold, versus 6.7% for the lexical sweep.
  • Quality Gating: For K ∈ {1,2,4,8}, 64.7%–81.7% of (pos, sent) EDA evasions met the quality threshold, compared with 48.5%–58.3% for Dipper’s order sweep.
  • Structural Channels: The (bag, sent) fixed-set stage produced 17.0%–24.9% mean resegmentation, compared with 11.7%–17.4% for final-stage (bag, span).
  • Examples: A SemStamp example preserved 96.7% of content while falling below the 5% FPR detection threshold; the rewrite combined rewording, reordering, and resegmentation.
Loading 2608.27666v1…