S em S tamp: A Semantic Watermark with Paraphrastic Robustness for Text Generation (2024)

Abstract: Existing watermarked generation algorithms employ token-level designs and therefore, are vulnerable to paraphrase attacks. To address this issue, we introduce watermarking on the semantic representation of sentences. We propose SemStamp, a robust sentence-level semantic watermarking algorithm that uses locality-sensitive hashing (LSH) to partition the semantic space of sentences. The algorithm encodes and LSH-hashes a candidate sentence generated by a language model, and conducts rejection sampling until the sampled sentence falls in watermarked partitions in the semantic embedding space. To test the paraphrastic robustness of watermarking algorithms, we propose a “bigram paraphrase” attack that produces paraphrases with small bigram overlap with the original sentence. This attack is shown to be effective against existing token-level watermark algorithms, while posing only minor degradations to SemStamp. Experimental results show that our novel semantic watermark algorithm is not only more robust than the previous state-of-the-art method on various paraphrasers and domains, but also better at preserving the quality of generation.

## introduction this work focuses on algorithms for detecting machine-generated text via watermarked generation-adding signatures during text generation which are algorithmically detectable, yet are imperceptible to human eye @xcite . this problem is of extreme importance now that large language models (llms) such as @xcite generate realistic text, increasing risks of llm misuse, such as generation of misinformation, impersonation, and copyright infringements @xcite @xcite . the dominant body of recent works on watermarked generation operate by injecting token-level signatures during decoding time @xcite @xcite @xcite . as a representative example, @xcite propose a watermarked generation algorithm that injects watermark signals that are extracted based on the previously generated tokens. despite its efficiency, follow-up work has shown that corrupting the generated text, especially paraphrasing, could weaken its robustness @xcite @xcite . we propose semstamp, a semantic watermark algorithm that is robust to sentence-level paraphrase attacks ( §2.2). depicted in figure 1 , our core intuition is that while paraphrasing alters the surface-form tokens, the sentence-level semantics are unchanged. thus, instead of partitioning the vocabulary, our watermark operates on the semantic space of sentence embeddings, partitioned by locality-sensitive hashing (lsh; @xcite . we develop two key components-a sentence encoder trained with contrastive learning (cl; @xcite and a margin-based constraint-to enhance paraphrastic robustness. to stress-test the robustness of watermarking algorithms, we develop a novel attack method that minimizes bigram overlap during paraphrasing, and name it the bigram paraphrase attack ( §2.3). experimental results ( §3) demonstrate that our proposed semantic watermark remains effective while token-level watermarks suffer significantly from the bigram attack. we summarize our main contributions as follows. first, we propose a sentence-level semantic watermark for llms and show that it is robust to paraphrasing and more quality-preserving than a token-11 10 01 00 lucy smiled. it was genuine. her eyes crinkled. she was happy. she felt delighted. ## related work machine-generated text detection, aiming at distinguishing llm-generated texts from human-written ones, can be categorized into proactive and posthoc methods. our focus, watermarked generation, belongs to the first category. watermarked generation early approaches to watermarking include text-meaning representation tree for information hiding @xcite , and a watermarking scheme for machine translation using an output selector that considers hashing operation @xcite . watermarked language generation, specifically pertinent to llms, is a renewed trend of proactive machine-prompt: aylesbury's new deputy area commander has been getting stuck in to his new role and says he's determined to make himself 'approachable'. non-watermarked generation: chief inspector neil kentish joined thames valley police less than a week ago as deputy chief constable. he's already got his work cut out as the force tries to tackle crime in the post brexit age. here he shares his top tips for doing your job well. 1. look the part -be respectful, look presentable, dress appropriately and be on time. keep an eye out for the telly chaps who may be trying to use you for your money -you should never let this happen. semstamp: chief inspector neil kentish joined thames valley police less than a month ago and has been thrust into the hot seat of the aylesbury district commander team. he was chosen from a wide range of candidates put forward by deputy chief constable peter borsack, who said, "i am delighted to have appointed neil as deputy chief officer of police in aylesbury district. he is a real character and i believe he will be a great addition to the team." pegasus paraphrase: neil kentish was the chief inspector of thames valley police. "i was thrust into the hot seat of the district commander team a month ago." he was chosen from a wide range of candidates put forward by peter borsack who said: "i am delighted to have appointed neil as deputy chief officer of police in aylesbury district. i think he will be a great addition to the team." pegasus bigram paraphrase: neil kentish was the chief inspector of thames valley police. he was put into the hot seat of the district commander team a month ago. neil was chosen from a wide range of candidates put forward by peter borsack, who said he was delighted to have appointed neil as deputy chief officer of police. "i think he will be a good addition to the team. he will bring a good level of leadership and management skills to the community." generated text detection. the scheme works by adding signatures imperceptible to humans during decoding time to enable stable detection at a later time. @xcite propose a watermarking algorithm by adding token-level bias (reviewed in §2). @xcite proposes a distortion-free watermark that preserves the original distribution of lm during watermarking. @xcite embeds multi-bit information into watermark and enhances performance against corruption through a robust infilling model. they inject the watermark via word replacement after initial generation, which is incorporated into one-stage watermarked generation by @xcite . @xcite propose a watermarking scheme that is computationally undetectable without the secret key in theory. importantly, these existing works employ a token-level design and focus on span-level corruption such as editing and cropping, which renders the watermarks susceptible to paraphrase attacks. more related to our focus on paraphrase attack, @xcite propose a retrievalbased method that requires saving all previouslygenerated sequences, and @xcite empirically shows that @xcite is more robust under longer generation length. contemporary to our work, @xcite improves robustness via a cryptographicfree watermark without hashing previous tokens, which is more robust to editing and paraphrasing attacks. to the best of our knowledge, our work is the first sentence-level semantic watermark algorithm targeted against paraphrase attacks. ## conclusion we introduce semstamp, a novel sentence-level semantic watermark for llms. the watermark is injected by mapping candidate sentences into embeddings with a paraphrase-robust encoder, partitioning the semantic space through lsh, and rejection sampling to generation sentences with valid region embeddings. empirical results show that semstamp is not only robust to paraphrase attacks but also more quality-preserving than a token-level baseline watermark algorithm. we also propose a bigram paraphrase attack which effectively weakens the token-level watermark while only causing minor performance deterioration to semstamp. we hope semstamp can serve as an effective tool for regulating the proliferation of machinegenerated texts.