SemStamp: A Semantic Watermark with Paraphrastic Robustness for Text Generation

1 Introduction

• SEMSTAMP applies watermarking in sentence-embedding semantic space rather than token vocabulary to preserve signals under paraphrase.It combines a contrastively fine-tuned sentence encoder with locality-sensitive hashing and a margin constraint.Source: §1 · pp. 1–2
• The bigram paraphrase attack selects paraphrases with minimal bigram overlap while maintaining paraphrase quality constraints.It is designed to stress token-level methods whose next-token watermark signatures depend on preceding tokens.Source: §1 · pp. 1–2
• SEMSTAMP remains effective under the bigram attack, whereas token-level watermarks suffer significant degradation.Source: §1 · p. 1
• The proposed semantic watermark is reported to be more quality-preserving than a token-level watermark algorithm.Source: §1 · pp. 1–2

2.2 SEMSTAMP: A Semantic Watermark with Paraphrastic Robustness

• SEMSTAMP maps candidate sentences into embeddings, hashes them into LSH signatures, and uses valid semantic regions for watermark-guided generation.Detection counts valid-region sentences in generated text.Source: §2.2 · p. 3
• The paraphrase-robust encoder is based on SBERT and is further fine-tuned with contrastive learning using paraphrase-positive and non-paraphrase-negative examples.Source: §2.2 · p. 4

Semantic Space Partitioning through LSH

• LSH uses random hyperplane projections to partition the embedding space into 2^d binary-signature regions.At each step, previous-sentence signatures seed pseudorandom valid and blocked region sets.Source: Semantic Space Partitioning through LSH · p. 4
• Margin-based rejection discards candidate embeddings near LSH hyperplane boundaries to improve signature stability under paraphrasing.The candidate must have absolute cosine similarity with every normal vector greater than margin m > 0.Source: Semantic Space Partitioning through LSH · p. 4, Figure 2 · p. 4

2.3 The Bigram Paraphrase Attack

• The bigram paraphrase attack beam-searches multiple candidates and selects the one with the smallest bigram overlap subject to a BERTScore constraint.The constraint preserves paraphrase quality while targeting token-level watermark sensitivity.Source: §2.3 · p. 5

3.2 Results

• SEMSTAMP is more robust than KGW across multiple paraphrasers, datasets, and both regular and bigram paraphrase attacks.Table 1 reports detection results using AUC, TP@1%, and TP@5%.Source: Table 1 · p. 6, §3.2 · pp. 6–7
• The bigram attack lowers KGW’s AUC by 7.9% and TP@5% by 27.1% on RealNews, versus SEMSTAMP decreases of 3.5% and 13.2%.The attack preserves paraphrase quality under the added BERTScore constraints.Source: §3.2 · p. 7
• SEMSTAMP preserves generation quality: its perplexity is on par with the non-watermarked base model, while token and semantic diversity are preserved.Table 2 compares non-watermarked, KGW, and SEMSTAMP generations using PPL, Ent-3, and Sem-Ent.Source: Table 2 · p. 6, §3.2 · p. 7
• SEMSTAMP maintains higher AUC than KGW across generation lengths of 100–400 tokens under regular and bigram paraphrase attacks.Figure 3 evaluates detection robustness as generation length varies.Source: Figure 3 · p. 6, §3.2 · p. 7
• Increasing the rejection margin improves LSH consistency because sampled sentences lie farther from region boundaries, although larger margins slow generation.The authors find m = 0.02 works well empirically.Source: §3.2 · p. 7, Figure 4 · p. 7
• Contrastive fine-tuning on Pegasus-paraphrased data improves LSH consistency across margins and generalizes robustness to Parrot, GPT-3.5-Turbo, and different domains.The encoder is fine-tuned on 8k RealNews paragraphs, and experiments use multiple paraphrasers and datasets.Source: §3.1 · pp. 5–6, §3.2 · p. 7

• Prior watermarked-generation methods add imperceptible signatures during decoding, including token-level bias, distortion-free watermarking, robust infilling, and cryptographic schemes.Source: §4 · pp. 7–8
• Token-level watermark designs are susceptible to paraphrase attacks because perturbing generated tokens can alter subsequent watermark signals.Source: §4 · p. 8
• SEMSTAMP is presented as the first sentence-level semantic watermark algorithm specifically targeted against paraphrase attacks.Source: §4 · p. 8
• Post-hoc detection methods either require large fine-tuning corpora or white-box generator access, depending on whether they use classifiers or statistical patterns.Source: §4 · p. 8
• Related work also covers copyright-oriented watermarking and LSH or contrastive-learning applications, whereas SEMSTAMP focuses on paraphrase robustness.Source: §4 · p. 8

• SEMSTAMP maps candidate sentences into paraphrase-robust embeddings, partitions semantic space with LSH, and rejection-samples sentences whose embeddings fall in valid regions.Source: §5 · p. 8
• SEMSTAMP remains robust to paraphrase attacks and preserves generation quality better than a token-level baseline watermark.Source: §5 · p. 9
• The proposed bigram paraphrase attack weakens token-level watermarking while causing only minor performance deterioration to SEMSTAMP.Source: §5 · p. 9
• The authors position SEMSTAMP as a potential tool for regulating the proliferation of machine-generated texts.Source: §5 · p. 9

Robustness to Stronger Attacks

• SEMSTAMP is not robust to inter-sentence attacks such as sentence reordering and is less effective when machine text is embedded in substantial human text.Source: Limitations and Discussion · p. 9

Semantic Constraint from LSH

• Enforcing valid LSH regions may reduce generation flexibility, although the authors observe no visible quality degradation with LSH dimension d = 3.Source: Limitations and Discussion · p. 9

Speed

• Generation is 20.9 times slower than non-watermarked generation with d = 3 and m = 0.02, or 5.26 times slower when m = 0.Source: Limitations and Discussion · p. 9
• Batch sampling and multi-GPU parallel decoding are proposed to mitigate SEMSTAMP’s rejection-sampling overhead, trading memory or infrastructure for speed.Source: Limitations and Discussion · p. 9

Reverse Engineering

• Reverse engineering is difficult because the sentence encoder and LSH hyperplanes are private, but larger LSH dimensions may increase that difficulty while reducing paraphrase robustness.Source: Limitations and Discussion · p. 9

Bigram Paraphrase Attack Control

• A BERTScore constraint controls bigram-attack intensity; removing it lowers AUROC more forcefully but sacrifices paraphrase quality.Source: Limitations and Discussion · p. 9

A Additional Related Works

• Prior NLP uses of LSH include noun clustering, approximate cosine similarity, lexically similar sentence retrieval, and conditioning generation on sentence-embedding signatures.Source: A Additional Related Works · p. 13
• Copyright-oriented watermarking embeds triggers, membership-inference signals, or secret keys, whereas SEMSTAMP studies robustness against paraphrasing.Source: A Additional Related Works · p. 13
• Contrastive learning improves representation distinguishability by pulling positive pairs together and pushing negative pairs apart, with applications including sentence embedding and language understanding.Source: A Additional Related Works · p. 13

B Watermark Detection

• The baseline test instead counts green-list tokens and rejects its null hypothesis when the resulting z-score exceeds a threshold.The green-token count is normalized by total tokens and the chosen green-token ratio γ.Source: B Watermark Detection · p. 13
• SEMSTAMP adapts the one-proportion z-test by replacing green-token counts with valid sentences under a sentence-level null hypothesis.The valid-region ratio γ is defined over the total number of sentences in the text.Source: B Watermark Detection · p. 13
• Detection breaks text into sentences, computes z_SEMSTAMP from the number of valid sentences, and classifies text as machine-generated when it exceeds M_r.M_r is selected so that r percentage of human texts are misclassified; r = 0.05 gives the TP@5% setting.Source: B Watermark Detection · p. 13
• Figure 6 compares original non-watermarked generations, baseline-watermarked generations, and paraphrases of SEMSTAMP generations.The figure provides additional generation examples rather than a quantitative detection result.Source: Figure 6 · p. 14
• Table 3 examines how increasing LSH dimensions affects the sampling rate for producing valid watermarked sentences at margin m = 0.0.The supplied caption identifies the sampling-rate measure but does not provide cell values.Source: Table 3 · p. 14

C Effect of LSH dimension d

• Fewer LSH dimensions increase LSH consistency because paraphrased sentences are more likely to remain in the same larger semantic region.LSH Consistency is the fraction of paraphrased sentences retaining the original sentence’s LSH signature.Source: C Effect of LSH dimension d · p. 14
• Lowering LSH dimensions slightly increases the average number of sentences sampled per valid sentence, so the method accepts a minor speed sacrifice for accuracy.The authors choose d = 3.Source: C Effect of LSH dimension d · p. 14

D Additional Experimental Results

• The KTH watermark performs poorly against both KGW and SEMSTAMP on paraphrased detection results.The supplied evidence reports this comparison for the BookSum dataset with Pegasus paraphrasing.Source: D Additional Experimental Results · p. 14
• UNIGRAM-WATERMARK remains robust against paraphrasing but can be reverse-engineered through repeated detection-API submissions over the tokenizer vocabulary.After |V| submissions, an adversary can recover its fixed greenlist.Source: D Additional Experimental Results · p. 14
• SEMSTAMP avoids this specific hack because its valid and blocked regions are not fixed during generation, while attacking it requires the private sentence embedder and LSH hyperplanes.The cited comparison concerns access requirements and region randomization, not general invulnerability.Source: D Additional Experimental Results · p. 15
• UNIGRAM-WATERMARK’s reverse-engineering vulnerability may limit its applicability in high-stakes domains despite strong paraphrase robustness.This is presented as a scope concern when adversaries can conduct reverse-engineering.Source: D Additional Experimental Results · p. 15
• The experiments used 8 A40 GPUs and approximately 100 GPU hours for sampling and paraphrase-attack jobs.This reports the computational budget for the experimental jobs.Source: D Additional Experimental Results · p. 15

E Additional Details

• A paraphrased sentence preserves the LSH signature when each normal-vector dot product keeps the same positive sign before and after paraphrasing.The original and paraphrased embeddings are produced by the sentence embedder and paraphraser, respectively.Source: E Additional Details · p. 15
• Cosine similarity is used for the similarity between two vectors, and GPT-3.5-Turbo is prompted with preceding context and the sentence to paraphrase.These details specify notation and an alternative paraphrasing setup.Source: E Additional Details · p. 15
• Data are split into sentences with nltk.sent_tokenize, and sentences lacking terminal punctuation receive a period.Sentence generation treats comma, period, question mark, or exclamation mark as delimiters.Source: E Additional Details · p. 15
• The bigram attack generates multiple paraphrases from the target sentence and preceding context, with larger num-beams strengthening the attack at higher computational cost.The prompt returns a numbered list of candidate paraphrases.Source: E Additional Details · p. 15

F Ethical Impacts

• The paper motivates robust watermarking by the risks of misinformation, plagiarism, copyright violations, and difficulty distinguishing human from machine text.It frames SEMSTAMP as a way to counter paraphrase-based attempts to evade watermarks.Source: F Ethical Impacts · p. 15
• Table 4 reports BERTScore for original and paraphrased generations, with separate vanilla and bigram-attack values; bigram paraphrasing causes only minor semantic-similarity degradation.Tables 5 and 6 provide paraphrased detection results for UNIGRAM-WATERMARK and KTH, respectively.Source: Table 4 · p. 16, Table 5 · p. 16, Table 6 · p. 16