k- S em S tamp: A Clustering-Based Semantic Watermark for Detection of Machine-Generated Text (2024)

Abstract: Recent watermarked generation algorithms inject detectable signatures during language generation to facilitate post-hoc detection. While token-level watermarks are vulnerable to paraphrase attacks, SemStamp (Hou et al., 2023) applies watermark on the semantic representation of sentences and demonstrates promising robustness. SemStamp employs locality-sensitive hashing (LSH) to partition the semantic space with arbitrary hyperplanes, which results in a suboptimal tradeoff between robustness and speed. We propose k-SemStamp, a simple yet effective enhancement of SemStamp, utilizing k-means clustering as an alternative of LSH to partition the embedding space with awareness of inherent semantic structure. Experimental results indicate that k-SemStamp saliently improves its robustness and sampling efficiency while preserving the generation quality, advancing a more effective tool for machine-generated text detection.

## introduction to facilitate the detection of machine-generated text @xcite , recent watermarked generation algorithms usually inject detectable signatures @xcite @xcite @xcite . a major concern for these approaches is their robustness to potential attacks, since a malicious user could attempt to remove the watermark with text perturbations such as editing and paraphrasing @xcite @xcite @xcite . @xcite propose semstamp, a paraphrase-robust and sentence-level watermark which assigns signatures to each watermarked sentence according to the locality sensitive hashing (lsh) @xcite partitioning of semantic space (see 2.1). while demonstrating promising robustness semantic space cluster centroid with index blocked sentence embedding valid sentence embedding binary signature of a lsh region lsh region boundary semantic space margin area of valid cluster k-means region with boundaries against paraphrase attacks, semstamp arbitrarily partitions the semantic space by a set of random hyperplanes, possibly splitting semantically similar sentences into different partitions (see fig. 1 ). this limitation motivates our proposed method, k-semstamp (detailed in §2.2), which partitions the space via k-means clustering @xcite on the semantic structure of a given text domain (e.g. news, narratives, etc.). in §3, we show that the clustering-based partitioning in k-semstamp greatly improves its robustness against sentencelevel paraphrase attacks and sampling efficiency. 1 ## approach we first review the existing watermark algorithms for machine-generated text detection ( §2.1) and introduce our proposed watermark ( §2.2). ## conclusion we propose k-semstamp, a simple but effective enhancement of semstamp. to watermark generated sentences, k-semstamp maps embeddings of candidate sentences to a semantic space which is partitioned by k-means clustering, and only accept sampled sentences whose embeddings fall into a valid region. this variant greatly improves the paraphrastic robustness and sampling speed.