StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Authors: Ya Jiang
Chuxiong Wu
Massieh Kordi Boroujeny
Brian Mark
Kai Zeng
Venue: ICML 2025 poster (2025)
Keywords: LLM Watermark
bias
LLM Security
Primary area: applications
TL;DR: We propose a multi-bit and stealthy watermark for large language models.

Abstract: Watermarking for large language models (LLMs) offers a promising approach to identifying AI-generated text. Existing approaches, however, either compromise the distribution of original generated text by LLMs or are limited to embedding zero-bit information that only allows for watermark detection but ignores identification. We present StealthInk, a stealthy multi-bit watermarking scheme that preserves the original text distribution while enabling the embedding of provenance data, such as userID, TimeStamp, and modelID, within LLM-generated text. This enhances fast traceability without requiring access to the language model's API or prompts.  We derive a lower bound on the number of tokens necessary for watermark detection at a fixed equal error rate, which provides insights on how to enhance the capacity. Comprehensive empirical evaluations across diverse tasks highlight the stealthiness, detectability, and resilience of StealthInk, establishing it as an effective solution for LLM watermarking applications.

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Ya Jiang' Chuxiong Wu!
Massieh Kordi Boroujeny? Brian Mark Kai Zeng? 2
Abstract
democratic processes more easily. Moreover, there is risk of misuse of LLMs for scams or academic plagiarism. To tackle these issues, it is crucial to implement regulations and technical protections to encourage fair and responsible us- age. Major providers of L.MMs, including OpenAl, Google, and Meta, have committed to watermarking text generated by their models as part of this effort (Bartz & Hu., 2023).
Watermarking for large language models (LLMs) offers promising approach identifying AI- generated text. Existing approaches, however, either compromise the distribution of original gen- erated text by LLMs or are limited to embedding zero-bit information that only allows for water- mark detection but ignores identification. We pro- pose StealthInk, stealthy multi-bit watermarking scheme that preserves the original text distribu- tion while enabling the embedding of provenance information, such as userlD, TimeStamp, and modelID, within LLM- LLL--geeeteed text. This en- hances fast traceability without requiring access to the language model's API or prompts. We de- rive a lower bound on the number of tokens neces- sary for watermark detection at fixed equal error rate, which provides insights on how to enhance the capacity. Comprehensive empirical evalua- tions across diverse tasks highlight the stealthi- ness, detectability, and resilience of StealthInk, establishing as an effective solution for LLM watermarking applications.
Several papers suggest incorporating invisible watermarks into text to detect Al-generated content (Kirchenbauer et al., 2023; 2024;
Christ et al., 2024; Kuditipudi et al., 2024; Hu et al., 2024; Wang et al., 2024; Zhao et al., 2024; Aaronson, 2023; Wu et al., 2024). However, detecting whether text is watermarked is insufficient to prevent misuse by malicious users.
Rather than solely embedding zero-bit watermark iden- tify Al-generated content, it is crucial to employ multi-bit watermark to track text provenance. Previous multi-bit wa- termarking schemes can be categorized into two groups: I) undetectable or distortion- watermarked text has exactly the same distribution as the non- watermarked text, e.g., (Kordi Boroujeny et al., 2024) and (Zamir, 2024), and 2) watermarking that allows some distortion of the output distribution (Wang et al., 2024; Fer- nandez et al., 2023; Yoo et al., 2024; Qu et al., 2024). A notable issue not tackled by the schemes in the first group is robustness against modifications made to the text generated by these methods.
watermarking, in which the
1. Introduction
Large language models (LLMs) like ChatGPT (OpenAI, 2022) or the open-sourced LLaMA (Touvron et al., 2023) and Gemini (Team et al., 2023), which have the remarkable ability to generate high-quality text, have become a crucial part of various text generation APIs, such as question an- swering, blog creation, and programming assistance (Austin et al., 2021: Perkins, 2023). However, these sophisticated language models' increased availability and capabilities present a significant concern. A key concern is their po- tential for facilitating the creation of fake news, which could be disseminated at scale, influencing public opinion and
In the second group, (Wang et al., 2024) use proxy lan- guage model to guide LLM text generation according the message, requiring extra resources and distorting the LLM's distribution. Other works (Fernandez et al., 2023; Qu et al., 2024) cyclically shift vocabulary permutations according to the message and bias tokens in a green list to enable efficient multi-bit decoding. However, overlapping shifts introduce interference, weakeming message distinctiveness and statistical separation. To counteract this, stronger bias is needed for reliable extraction, but this increases text dis- tortion and reduces stealthiness. The multi-bit watermarking schemes proposed by (Yoo et al., 2024) essentially extend the reweighting approach outlined in (Kirchenbauer et al., 2023). This approach biases the frequency of certain words or phrases embed the watermark during the generation process, such that the output distribution deviates from the
'Department of Computer Science, George Mason University, Fairfax, VA, USA 'Wireless Cyber Center, College of Engineering and Computing, George Mason University, Fairfax, VA, USA. Correspondence to: Ya Jiang <yjiang25@gmm @gmu.cdu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
distribution of the LLM. Thus, the naturalness and readabil- ity of the LLM output may be disrupted, reducing the utility and effectiveness of the LLM for the users. Furthermore, due to lack of stealthiness, these schemes (Fernandez et al., 2023; Qu et al., 2024; Yoo et al., 2024) are vulnerable to the watermark spoofing attack (Jovanović et al., 2024) whereby an attacker forges a text watermarked by the LLM at low cost without knowing the secret key of the LLM by analyz- ing the distribution of n-grams between watermarked and non-watermarked texts. This poses significant security risk, as malicious actors could fabricate harmful content that appears to be verified by a trusted model, thereby com- verification
ity (Fernandez et al., 2023), while also lacking stealthiness and being vulnerable spoofing. StealthInk ensures robust detection, high text quality, and enhanced security, making it resilient against attacks.
2. Preliminaries
Notation: We first establish a few essential notations. Let V denote the vocabulary set and [V] its size. We use 1: to denote the sequence of L tokens {x1..... Fy J: z denotes the first i elements while T: i: represents the last i elements. Denote the prompt as a and the likelihood of generating an imminent token IL+1 E V given the prompt and current a, T1LL). Due to the autoregressive model of operation that an LLMM adopts, the joint probability of producing L tokens spanning from æ æg given by
promising the credibility of watermark- systems. In contrast, a stealthy or undetectable watermark significantly increases the difficulty for adversaries attempt- ing to manipulate or forge watermarked text, enhancing the resilience of the system against spoofing attacks and strengthens the reliability of watermark-based authentica- tion.
context by Po(œ
L
Po(an. aa) = II Po(a; a, (1x-1)
We propose a novel reweighting strategy for multi-bit water- marking that satisfies all of the properties listed in Table 1, which compares our proposed StealthInk scheme with SOTA multi-bit watermarking schemes. The stealthiness property implies that the watermarked text is statistically difficult to distinguish from non-watermarked text without the wa- termark key. Efficiency refers to the low computational complexity of the encoder and decoder. High AUC implics low false positive and false negative rates in detecting the watermark. For multi-bit watermarking, high bit accuracy in decoding the hidden message is an important property. In Section 5, we provide theoretical derivation of the mini- mum number of tokens necessary for watermark detection at fixed equal error rate, i.c., the false positive and false negative rates are equal, which provides insights for capacity enhancement.
Like other LLM watermarking schemes, our approach uti- lizes pseudorandom functions (PRFs) (Goldreich et al., 1986) to generate an i.i.d. watermark cipher 0 with a uni- form distribution. Specifically, 0 is a permutation of the vocabulary V. derived by seeding the PRF with the water- mark key sk E SK and the texture key s, i.e., the context n-grams a -hk: E Va,, This results in an ordered sequence of tokens 0 = -t1,...,fa ..... .Iv1). where f is the kth token in the permutation. We denote an m-bit watermark message as M E M = {0, 1,...,,"' 2m 1}. In addition, we define PW (#++1 a, æ1.2, 0r)) as the watermarked probability distribution for generating the (L + 1)-th token.
3. Threat model
Following (Jovanović et al., 2024), the model owner deploys an LLM LMmo with a watermarking scheme and a water- mark key sk. We assume the attacker has only black- box access (e.g., API access) to full generations of LM and is aware of the presence of the watermark behind the API. In line with standard security assumptions (Kerckhoffs' princi- ple), we assume that the attacker knows all parameters of the watermarking scheme,, but not sk.
Table 1. Comparison with SOTA multi-bit LLM watermarking schemes.
A: (Kordi Boroujeny et al., 2024; Zamir, 2024); B: (Wang et al., 2024; Fernandez et al., 2023); C: (Yoo et al., 2024; Qu et al., 2024).
Stealthink
Steulthiness
x
/
Efficiency
/
High AUC
/
High accuracy
/
Editing attacks To avoid watermark detection, some attack- ers could try to edit the text while ensuring text quality. In that case, after obtaining the response from the LLM, attack- ers could employ straightforward text modification, such as substitution, insertion, and deletion, while ensuring the preservation of semanties. This method aims to subtly alter the content to evade detection, making it challenging for conventional security measures to identify the modified text. Distinct from modification attacks, in paraphrasing attacks, the attackers focus on rephrasing the text rather than making
Robustness
We empirically compare StealthInk with existing meth- ods (Yoo et al., 2024; Qu et al., 2024; Fernandez et al., 2023), demonstrating its superiority in detection, extraction, text quality, and stealthiness. Ite achieves an AUC of 0.98 and a bit accuracy of 0.92 when embedding 24- messages in 300 tokens. In contrast, prior methods either degrade text quality for better detectability (Yoo et al., 2024; Qu al., 2024) or sacrifice detectability to maintain qual-
2

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
direct modifications. This involves rearranging sentence structures, changing the order of words, altering gram- matical constructions to achieve different phrasing while preserving the underlying semantics. The intent is to create a response that is different but retains the core meaning, which complicates the task of identifying the manipulated content.
set of watermark ciphers and let Pe denote a probabil- ity distribution defined on O. We assume that Pe is the uniform distribution on θ since 0 E ④ is determined by PRF. Let Áv denote the set of all possible probability distributions on V. We then define reweighting function F' F(0, Po) : O x . x Sy + V which generates the watermarked text with embedded message M.
Watermark spoofing attacks. Targeting distribution- modified watermarking schemes that boost green-list tokens by adding 8 to their logits (Kirchenbauer et al., 2023; 2024; Zhao et al.. 2024; Yoo et al., 2024; Qu et al.. 2024), Jo- vanovic et al. (Jovanović et al., 2024) introduce watermark spoofing. Here, an attacker queries LM minimally to approximate its watermarking rules based on sk, enabling the forgery of text detected as watermarked, thus damaging the LLM provider's reputation. This attack assumes access to an auxiliary model LMas trivial condition given the abundance of open models.
Definition 4.1. (Stealthy or unbiased multi-bir bittibbitttte watermark) After embedding M E M, the watermarked distribution, PW determined by the reweighting function F(B, M. Po) is stealthy or unbiased if for all Po E Av, Be [P Po. where PW = G(F M, Po)) E Av and G is a difference operator that transforms a cumulative vector into a discrete probability distribution over the vocabulary.
Definition 4.1 establishes the unbiasedness of the water- marked distribution for single generated token. We further define the unbiasedness of the watermarked distribution for texts. Note that for a single response where M is given and fixed, stealthiness or unbiasedness is not relevant, as user cannot infer probability distribution from just one output. The concept only becomes meaningful when con- sidering multiple responses over time, where the message changes and is random due to metadata variations (e.g.. userlD, TimeStamp).
(Jovanović et al., 2024) spoof non-stealthy zero-bit water- marks by identifying distribution differences between water- marked and -on-raaerdrreed text. For instance, (Kirchen- bauer al., 2023) boost logits of tokens in the first half of permutation, increasing their selection likelihood. As re- sult, certain tokens after context n- n-grams AAA consistently have higher probabilities than in non- watermarked LLM.
In the following, to define the stealthiness over K pairs of prompt and response, we use bold lowercase a for the kth prompt and x* = .cf....,.h.)) to denote a response of a sequence of L tokens in the kth response. The em- hedded message in the kthh response is denoted M and @* (ot...., 041,) represents the sequence of vocabulary permutations used during generation. The watermarked probability distribution for generating the entire text x is denoted as Fum(a" ()).
However, mul watermarks embed diverse signals across tokens. When m = 1, some tokens carry signal O, others signal 1, creating varying bias directions. This additional complexity makes spoofing multi-bit watermarks more chal- lenging. In Section 6, we investigate the potential to extend the stealing attack proposed by (Jovanović et al., 2024) to multi-bit watermarking schemes.
4. Methodology
Definition 4.2 (K-shot stealthy watermark). Let be K prompt-response pairs, with aforemen- tioned notations, the watermarking scheme is said to be K Khshot stealthy if the expectation of joint distribution over the K generations under watermarking matches the original model's '' joint distribution:
We propose multi-bit and stealthy watermarking scheme, StealthInk, which uses novel token sampling probability reweighting strategy to embed information in the sampled tokens from randomized vocabulary permutations. We dou- ble the probabilities of certain tokens while ensuring that several others have probability of zero, thus preserving the expected distribution over the random space of permu- tation. The tokens with zero probability, referred to as red tokens, are never sampled, enabling watermark detection and information bit extraction through statistical tests. In this section, we will first extend the stealthy concept from zero-bit watermarking to multi-bit watermarking, and then describe StealthInk in detail.
{a* x "**
K
E Eg Mrx [A] = II
Po at))
(1)
km
where
K P um
aaa
aaMM @t 1:6-1 lib-l M .iki)))
4.1. Stealthy multi-bit watermarking
The following theorem illustrates the condition when K- shot stealthiness holds. See the proof in Appendix B.
We adopt the definition of a stealthy or unbiased water- mark used in (Hu et al., 2024; Wu et al., 2024) and ex- tend the concept to multi-bit watermarking. Let e denote
Theorem 4.3. For any prompt a and the response x², if the sequence of ciphers 6¹ independent, and each token
3

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
is generated with unbiasedness, then the K pairs of prompts a l and responses .: are K-shot stealthy.
Tau |Vith token. Similarly, define
8 = Σ 2o(tyla,zis-1 0.)= X(aettilV) (3)
If two seeds applied the PRF are different then the two generated watermark ciphers, say O and 03 (i.j E I * j). will "look" random and independent. To ensure the independence of 0², intuitively, when the same seed is encountered during generation of æ² the original distribution Po |a =f;--) should be used. Otherwise, the reweighted probability distribution PW " ) is applied. Therefore, the prob- ability distribution of generated tokens either follows the original distribution or an unbiased distribution. In that case, according to Theorem 4.3, the watermarked probability dis- tribution of multiple pairs of prompts and responses can be preserved.
J=1
i.e., 3 is the right cumulative probability corresponding to the (y + +-)lV|-th token. Let 3 3 and ā a.
Fig. presents a simplified example of StealthInk encoder for embedding message of 8 bits. The message is formed as a M MsgSeq, which is comprised of H message chunks and we refer to the index of the chunk as pos E {0, 1...., H1 - }. Each message chunk carries an m-bit signal. Therefore, M MsgSeq carries an Hm-bit signal. In Fig. 1, m 2, H = 4, and y = 2 m = 0.25. To enhance the capacity, we leverage the position allocation approach in MPAC, which allocates each token pseudorandomly onto a message chunk of M MsgSeq to be embedded.
The property of K-shot stcalthiness ensures that the wa- termark remains imperceptible to both users and potential attackers, even if they are aware of the original distribu- tion Po. Specifically, it makes watermark spoofing attacks more difficult for attackers to successfully execute by distin- guishing between the watermarked text distribution and the non-watermarked text distribution, as evaluated in Section 6. Moreover, preserving the text distribution inherently implies maintaining the quality of the generated text.
As illustrated in Fig. 1, given a prompt, StealthInk first derives the texture key using the last n-grams of the prompt (in this case, h = 3). The watermark key and texture key are then combined form a seed for PRF, which generates permutation over the vocabulary set V. This seed is also used to choose a position pos, determining the message chunk to embed at the current generation step.
In Fig. 1, pos = 1, meaning that the corresponding message chunk "10" (i.e., MM- = 1) is selected for embedding at this step. By forming the permutation with each token ordered according to their probabilities from Po. we compute a and B as defined in (2) and (3). This process allows us to define the red list with M embedded,
4.2. StealthInk
Notation: We define TM- M . where y = 2- to map M to an interval in a permutation 0. Consequently, yas E {0, 10,2-m,00 21_22_1_... ,..... 1 - 2- 2- Tokens within the interval associated with M are indexed as [V] : (TM +7) V-]-
RL M = 0(TM VI : (7M5 + IV]],
(4)
To generate the ith token, given the original probability distribution Po and the permutation 0, seeded by x - an axis ranging from 0 to I can be constructed. Along this axis, the tokens are arranged in the order defined by 0,, occupying positions proportional their respective probabilities. By denoting X₂ = Σラ= ( a, 11,1-1 (f)), we can define X8-1 and X₂ as the left and right cumulative probabilities corresponding to token th, which is the kth token in 9, Then the probability of la under P is X Xx-1-
where tokens within this range have their probabilities reweighted to zero and will not be sampled.
To demonstrate how StealthInk works, we present four cases in Fig. 2. In each case, 2+ indicates that the probabilities of tokens in that interval are doubled, while 0 means the prob- abilities of tokens in that interval are zeroed. In addition, * indicates that the probabilities of tokens in the correspond- ing interval keep their original values. When embedding the message M, the probabilities of tokens in the red list will be reweighted to O. Let F(B, M, Po) be the reweighted cumulative probability for the token l under permutation 0 for k- = 1....,IV], illustrated in Fig. 2, which can be expressed as?:
Next, define a to be sum of the probabilities of the tokens t, .2...., [v|. under probability distribution Po with permutation 0,;
TM Σ Poltyla.mma-1,0.) 0.) =Xaxx
+ -X
-(Xx- -5)= -0) -(X; -a)+ Case or 3,
F( =
3) + (Xa-3)+
+(X--3) -3)
ie., a is the left cumulative probability corresponding to the
(Xx -a--a--a0 -a)
-a)_ Case or 4.
'Wit slight abuse of notation, for permutation 0 = (f1..... ....... fv1). (v.)). we denote the subsequence (fa....,f fb) as A[a : b) and we assume that the ceiling operation is applied to indices, e.g., as an index, 7M [V] is interpreted as [7M [V]]
(5)
(xx) max(z, 0) and (x)- = -min(z, 0). Note that
x == (x)+ (x)
4

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Texture key
Sample pos=1 using texture key
Tokens are sampled from intervals with these two colors
Prompt: Watermark for large language model is
MagSeg
00 10 01
Seed PRF watermark
Determine the red list
key and texture key to form permutation
Red list
8
1
The tokens' probs in this interval are doubled.
The tokens' probs in the third Interval are reweighted to O.
Figure 1. StealthInk encoder: 2, H 4.
2+
hancing StealthInk's 's capacity by key enumeration. For in- stance, embedding 2-bit message requires choosing from 4 watermark keys. As shown in Appendix L, traversing sk values causes significant detection delays without nec- essarily improving capacity. Furthermore, since StealthInk leverages the position allocation approach in MPAC (Yoo et al., 2024) to enhance capacity, ensuring the randomness of the message is crucial for maintaining K-shot stealth- iness. To achieve this, the lower-end bits of TimeStamp, such as those representing seconds or even milliseconds, should be embedded in the initial tokens of the response. The remaining message chunks are then embedded into the rest of the tokens using position allocation. Therefore, even if a user repeatedly queries the same prompt, the distribu- tion of the responses preserved. Moreover, an attacker attempting a spoofing attack by distinguishing the distri- butions of the original and watermarked text can only suc- ceed if they use the same userlD to repeatedly submit the same prompt within a very short time frame (e.g., within second or even 1 millisecond) and gather a sufficiently large number of queries (e.g., 100,000). This constraint makes it significantly more challenging for an attacker to exploit distributional differences to forge the watermark. In Appendix F, we further discuss resilience against adaptive attacks through sufficiently large number of queries.
0.5
8
0.5
8
Case 1: B S 0.5
Case 2: a 2
0.5
2+
0.5
B
0.5
Case 3: a<00.5 and 9>0.55
Case 4: a<50.5 and 0.50.5
and + 11
and a + 3>1
Figure 2. Multi-bit watermarking reweighting rule.
With the original distribution Po at the ith gener- ation step, the reweighted probability of token ty G(F(O) M, Pb));
PM (f& la, 215-1,00) O,) F(.., M, Po)x P(O., M, Pi) We prove the follow- ing result in Appendix C.
Theorem 4.4. For each 0 E i.i.d. 01.L, the reweighting func- tion (0, M, Po) in (5) ensures stealthy watermarking.
Algorithm shows the process of encoding a multi-bit wa- termark in StealthInk. During a query attempt, to ensure the independence between permutations, the same texture key should not repeat for watermarking, which means the original probability distribution is applied when encounter- ing the same texture key. In this way, history log hist is maintained for each query attempt to record the texture key encountered.
In the detection stage, as described in Algorithm 2 in Ap- pendix D, each token in the given text is mapped to a posi- tion pos by seeding a PRF with the watermark and texture keys. For tokens mapped to particular pos, we count the number of tokens that fall into the red list defined by M M,, specified in Eq. (4). Under the null hypothe- sis (i.c., the text is not watermarked), the probability that token falls into the red list is 7. Let Lpps denote the number of tokens mapped to position pos; then the num- ber of red list tokens RM ~ Bin(Lpoe. 7). We extract the message chunk each position by selecting the candi- date M E M that minimizes the count of red list tokens
In Dipmark (Wu et al., 2024) and ZMH (Hu et al., 2024) (see Algorithm in both), a single hist must be shared across all user queries to maintain Ksshot stealthiness. However, as global queries increase, the pool of available texture keys shrinks, requiring periodic replacement of the watermark key sk. This necessitates keeping track of all used keys, which adds overhead in both storage and verification.
This issue becomes even more prominent when embedding the multi-bit watermark using only multiple keys or en-
5

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Mios arg Min Ross To detect whether the text is watermarked, we concatenate Mos across all positions pos E [0,1,....,It H- - 1 to form the message sequence MagSeq. Then, we compute the 2-score as
chunks can achieve the same eer with significantly fewer tokens. By analyzing the relationship between Tumin and eer under varying entropy and repetition rates p, we can determine the optimal unit capacity for improving capacity through position allocation.
(MsgSee IILL) = R- PR
(6)
Another insight from Fig. 3 is that repetitions greatly hinder watermark detection. When p = 0.2, the minimum number of tokens required for detection is much higher than when p = 0. As discussed in Section 4.2, Dipmark and ZMH share global history log across all queries, causing p to increase over time, requiring more tokens for watermarking, In contrast, our method constructs an empty history log for each query and recycles it after response completion, which keeps p significantly lower and stabilizes Immi across different query attempts through our reweighting strategy.
where AR and RR denote the empirical mean and stan- dard deviation of R. estimated from a collection of non- watermarked texts. Note that in our experiments, we evalu- ate detection performance by comparing the values of for watermarked and non- non-watermarked texts, rather than setting a threshold on the z-score.
Algorithm StealthInk Encoder
Input: a, sk, I., h, J. hist = 0, M Sgggeg, H, 7 = 2-m for i = 1,....... L do
200
bit
500
bit
Calculate Po(. a, x;))
2 bit
bit
Generate texture key 8t based -h
150
3 hit
400
bit
Sample pos from [0, 1......... H- - 1] with seed s;; let
4 hit
300
bit
M SggSoppos)] M and TM- = My
100
200
if s; E hist then
Sample x; from Po(. aa, 11)
50
100
else
hist.add(s;)
10
10
10
10
Generate permutation 0: = f(kk s;)
cot
cCr
Calculate o and using (2) and (3)
(a) p = 0
(b) 0.2
Calculate PM (- |a, I. 0.) from (5)
Figure Liuia vs. cer for p = 0 and p = 0.2.
Sample 2, from PM (- Ia, -.
end if end for
6. Experiments
We compare StealthInk with SOTA methods (Yoo et al., 2024; Qu al., 2024; Fernandez al., 2023) on stealthiness, detectability, and robustness. For text completion, unless noted otherwise, we use LLAMA2-7B (Touvron et al., 2023) and 500 randomly selected texts from the RealNewsLike subset of C4 (Raffel et al., 2020), trimming a fixed number of tokens from the start as prompts (see Appendix H).
5. Theoretical analysis
In Appendix we can derive the probability of sampling a red token when embedding the message M as
P[rt7ar-] (1 - (3 - a:) + x
2
6.1. Stealthiness Results
where p represents the probability of repeated texture keys, defined as the ratio of the number of texture keys that have already appeared to the total number of texture keys in a text. As [P[rt"ar*] increases, under a certain equal error rate (eer), the minimum number of tokens required to detect the watermark Lmin is larger. Specifically, we present the rela- tionship between Liin and eer under uniform distribution as Fig. 3, which is the best Lmmi with the maximum entropy. In that case, 3
6.1.1. STEALTHINESS PRESERVES TEXT QUALITY
Following Dipmark and ZMH, we compare text quality among the methods for machine translation, text summariza- tion, and text completion tasks. For the text summarization task, we employ the BART-large model (Liu et al., 2020). For the machine translation task, we focus on English- -oo- Romanian translation and employ the Multilingual BART (MBart) model (Liu al., 2020) on the WMT' 14 En-Ro corpus (Bojar et al., 2014). Due to the limited number of tokens in each sample, which is less than 50 tokens, we compare the quality of text watermarked by 1 bit and bit watermarks, respectively, for machine translation and text summarization tasks, as shown Table 2, where no segmen-
2-
One key insight is that capacity can be enhanced by dis- tributing unit capacity across locations. As shown in Fig. 3, the Luin needed to embed 2 bits is smaller than half of that required for 4 bits. Thus, embedding 2 bits into two separate
6

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Table 2. Text quality for machine translation and text summarization. PPL. is the median perplexity.
Machine Translation
Text Summarization
Metries
BERTScore f
BLEU t
ROUGE-1 f
PPL
ROUGE-1 1
Unit Capacity (Bit)
2
2
2
2
2
Non- Watermarked
0.6995
0.0677
0.3312
7.274
0.2319
StcalthInk
0.6941
0.6967
0.0776
0.0719
0.3317
0.3337
7.147
7.333
0.2322
0.2325
MPAC
0.6457
0.6515
0.0442
0.0488
0.2670
0.2789
10.51
10.82
0.1991
0.1963
Qu ct al.
0.5840
0,5822
0.0180
0.0153
0.1782
0.1628
26.27
25.09
0.1498
0.1512
Fernandez et al.
0.6658
0.6730
0.0489
0.0483
0.2807
0.2907
12.41
12.58
0.2083
0.2094
Table 3. Spoofing attacks on different schemes with bit and bits embedded, respectively, where m 1.
Dolly CW
Reeooot
TPR@
@FNR,
TPR@
@FNR
AUC L
10%FPR +
GPT4 f
AUC L
10%FPR +
*Ie-3* +
GPT4 1
*Ie-3"
StealthInk
0.7265
0,29
0.4482
8.11
0.8064
0.5
0,3333
8.74
H=1
MPAC
0.8301
0.6
0.7018
8.22
0.86
0.73
0.6885
8.24
Qu et al.
0.9835
0.97
0,9899
6.77
0.954
0.93
1.0
7.0
Stcalthink
0.8456
0.57
0.6667
8.73
0.893
0.65
0,5439
8,92
H=2
MPAC
0.9239
0.83
0.8313
8.21
09491
0.84
0.7125
8.67
Qu et al. 0.9979
1.0
1.0
7.0
0.999
1.0
1.0
7.1
tation is utilized, i.e. H 1. On the other hand, for text completion, we present the quality of text watermarked by 24 bits at 200 tokens for different schemes in Fig. 6, where segmentation is leveraged,
rived to test the performance of watermarking schemes in distinguishing between watermarked and non-watermarked texts. Low AUC would indicate failed spoofing attack, which means the detector cannot discern the watermarked text forged by the attacker from the non-watenn won-maatrmarked text. TPR @ 10%FPR represents the fraction of forged texts that are detected as watermarked when the ratio false identi- fied watermarrarreed texts is smaller than 10%. @FNR* lc- denotes the fraction of forged texts that are detected as watermarked at FNR=1e-3 (i.e., p-value < 0.001). There- fore, smaller TPR @ 10%FPR and @ FNR* represent an ineffective spoofing attack. We observe that the text forged from StealthInk consistently exhibits the lowest detection performance among the evaluated methods. For instance, when an attacker learns the outputs watermarked by Steal- thInk and attempts to forge watermarked text on the Dolly CW dataset, only 29% of the forged texts are detected termarked when the FPR is below 10%. In contrast, forged texts generated using MPAC and (Qu et al., 2024) achieve significantly higher detection rates, with about 70% and 98% of forgeries being correctly identified as watermarked under the FNR 10 setting.
1 and H- 24.
As shown in Table 2 and Fig. 6 in Appendix I, text quality remains largely unaffected by watermark capacity, regard- less of whether it is 1 bit, 2 bits, 24 bits, or more. Both Table 2 and Fig. shows that text quality remains consis- tent between StealthInk watermarked and non non-waaermarked texts. In contrast, the other methods degrade text quality.
6.1.2. STEALTHINESS PROTECTS AGAINST SPOOFING
Following the settings in (Jovanović et al., 2024), we com- pare the robustness against watermark spoofing attack by set- ting up LM as LLAMA2-7B and LAMate as MISTRAL- 7B (Jiang et al., 2023). We randomly select 30,000 prompts from the RealNewsl.ik subset of the C4 dataset query each LLM, generating responses of fewer than 800 tokens under various watermarking schemes, in order to learn and estimate the underlying watermark patterns. LMau then generate 100 responses of less than 800 tokens, respectively, using the prompts from Dolly-CW (Conover et al., 2023) and MMW BookReports (Piet et al., 2023). Table presents the performance of spoofing attacks on different multi-bit watermarking schemes for embedding 1 bit (H 1) and 2 bits (H~ 2), respectively, where m = 1. We exclude Fernandez et al. in this comparison because of its low de- tectability. In particular, we ignore low-quality texts (GPT4 score below 6.5). From the attacker's view, the forged text should be detected as watermarked, which is a positive sam- ple, while the true non-watermarked text which is a negative sample should be correctly identified well. AUC is de-
6.2. Detectability results First, we compare the TPR for m E (1,2,3,4] when the FPR is below 1%, with И = 1, to determine the optimal value of m for constructing the MsgSeq, as shown in Fig. 4. Using the red dashed line, which represents the TPR for embedding 1 bit in 50 tokens, we observe that the TPR for embedding 2 bits in 100 tokens is lower, and the TPR for embedding 3 and 4 bits in 150 and 200 tokens, respectively, is even less than half. Therefore, we select m = 1.
Then we evaluate the performance of message detection and
7

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
extraction among various methods in 24 bits, 36 bits, and 48 bits at 200 tokens, shown in Table 4. While the method of (Qu et al., 2024) achieves the best detection and extrac- tion accuracy, their text quality measured by perplexity is significantly compromised. (Fernandez et al., 2023) exhibit lower TPR and bit accuracy with significantly higher time cost compared to other methods. For example, when embed- ding 24-bit messages, it cost 113 s to extract the message. In contrast, StealthInk and MPAC extract the message in only 0.01 s. This highlights the inefficiency of directly using varied keys within the hash function.
text generations with theoretical guarantees.
Note that in Table 4 the PPL of the StealthInk is signifi- cantly lower than the non- non-watermarked sequences, which arises from the evaluation setup and not from a violation of the stealthiness guarantee of StealthInk. StealthInk uses a reweighting strategy that satisfies two constraints during token sampling: (1) the token must not appear in the red list (whose probability is zeroed out), and (2) it must be sampled from the remaining tokens based multinomial sampling. In contrast, non-watermarked text generation only follows the second condition. As a result, StealthInk effectively filters out low-probability tokens that fall into the red list, which may include semantically weak or low-quality op- tions. This selection bias may cause the sampled tokens to have higher average probabilities. thus reducing PPL.
0.8
TPR@I 1PR@1PPER 1
However, this observation does not contradict the stealth- iness of StealthInk. The PPL. reported in Table 4 are me- dian values aggregated over responses of 200 tokens to 500 prompts, each associated with a random message and per- mutation. Due to this variability, small empirical differences in PPL can emerge across text generations. Nonetheless, StealthInk is provably stealthy in expectation (as shown in Definition 4.1 and Theorem 4.4), i.c., when averaged over sufficiently large number of generated tokens or samples, the watermarked and non- woo-waatrmarree token distributions are statistically indistinguishable. In Appendix J, we show the PPL with various number of generations and note that if we further increase the number of prompts or use even longer generated sequences, the PPL statistics of StealthInk and non-watermarked text become closer to each other. 6.3. Robustness against editing attacks
0.6
Het
0.4
3 Bix
Hil
0.2
with
50
100
150
200
250
# Of Tokens
Figure 4. Detection performance comparisons with m E (1,2, 3, and 1.
In particular, we compare the TPR of StealthInk and MPAC with 1% FPR and D.RR,,, respectively, across various number of tokens in Fig. 5. The logits bias of MPAC are compared between 1, 1.5, and 2, where 5 = 2 is the original setting in MPAC and is applied in the evaluation of MPAC in this paper. Higher logits bias generally represents more skewed probability distribution and larger watermark detectability. We observe that while StealthInk may initially show lower TPR at shorter lengths (e.g., 200 tokens), its detectability approaches or matches MPAC as the number of tokens increases. For example, when embedding 36 bits, MPAC (8 2) achieves TPR@ 1%FPR of 0.98 at 200 tokens, while StealthInk achieves comparable TPR @ 1 1&PR (i.e., 0.985) at 400 tokens. Note that StealthInk's TPR is significantly better than that of MPAC when 5 = 1, while close to MPAC's TPR when 8 = 1.5. For example, when embedding 36 bits, MPAC (6 = 1.5) achieves TPR @ 1 1%FPR of 0.97 at 300 tokens, while StealthInk achieves comparable TPR@ 1 F& (i.e., 0.9725) at 400 tokens.
The copy-paste attack involves mixing watermarked text with non-watermarked text, while the paraphrasing attack rewrites the watermarked text using another language model to preserve its meaning. For the copy-paste attack, we randomly mix a proportion c of non-wakermarked text into the watermarked text, maintaining the total length. In the paraphrasing attack, we use the Dipper (Krishna et 2023) and PEGASUS (Zhang et al., 2020) models to paraphrase the watermarked text, with representing the paraphrasing strength.
As shown in Table 5, bit accuracy decreases steadily with the increasing proportion of watermarrdr text in the copy-paste attack. This occurs because replacing more watermarked text reduces the distinguishing features re- quired for accurate watermark extraction. Additionally, non-ward woon-watrmarked tokens distribute the watermark signal more evenly, as seen in StealthInk, where non non-waatrrdrked tokens are spread across the vocabulary permutation. Conse- quently, the watermarking schemes can maintain acceptable bit accuracy when only a small portion of the watermarked text is replaced.
This demonstrates that StealthInk is competitive in de- tectability given sufficient sequence length, while offer- ing additional benefits in terms of stealthiness, robustness to spoofing, and multi-bit capacity. Unlike distribution- modifying schemes like MPAC, which achieve higher de- tectability through aggressive token-level distortion, Steal- thin is designed to be statistically stealthy across multiple
8

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Table 4. Clean performance with 200 tokens for text generation task. PPI. is the median perplexity.
TPR
Extraction
1
Bit Accuracy t
PPL 4
+
@ 1%
Time (s)
Non- Non-Watermarked
8.016
StealthInk
0.9780
0.8475
0.8747
7.141
0.01
MPAC
0.9959
0.985
0.9437
10.19
0.01
Bit
Qu al.
1.0
1.0
0.9987
42.63
0.18
Fernandez al.
0.9433
0.655
0.61
9.46
113
StealthInk
0.9709
0.7475
0.8327
7.135
0.01
MPAC
0,9923
0,982
0.8927
9,376
0.01
Bit
Qu et al.
0.9975
1.0
1.0
39.87
0.82
Fernandez al.
45100 (Estimated)
StealthInk
0.9556
0.6185
0,7867
6.968
0.01
MPAC
0,9907
0.98
0.8611
10.11
0.01
Bit
Qu et al.
0.9998
1.0
0.9775
41.16
1.37
Fernandez al.
1.85e9 (Estimated)
Table 6 shows that all evaluated schemes suffer significant performance degradation under paraphrasing attacks, with a marked drop in bit accuracy compared to the baseline (e = 0). This decline due to the attack's alteration of sentence structure and rephrasing. which disrupts the em- bedded watermark signal. Achieving robustness against paraphrasing attacks remains major challenge for multi-bit watermarking.
Bod MPNC 2-14
F Toboop
(a) 24 Bits
Table 6. accuracy when using Dipper and PEGASUS to para- phrase 400 watermarked texts of 300 tokens with 24 bits embed- ded.
Bit Accuracy
Paraphrasing Attack
17380N77A
c=0.1
Dipper
PEGASUS
StealthInk
0.9195
0.6118
0.57
MPAC
0.9627
0.6108
0.5944
Qu et al. 0.9988
0.6337
0.6337
FOL Iriro
1:00 40
Fernandez et al.
0.6613
0.4162
0.4237
(b) 36 Bits
7. Conclusion
StealthInk a provably stealthy and multi-bit watermark- ing scheme for LLMs that enables text traceability while preserving text quality. StealthInk uses novel reweight- ing strategy for token probability distributions, ensuring unbiased distribution and effective multi-bit message em- bedding. Empirical results demonstrate StealthInk's 's high bit accuracy, superior text quality, and resilience against attacks. Our work highlights that watermarking must go be- yond embedding and extraction stealthiness to prevent detection and spoofing while main- taining text integrity. This balance enhances the practical applicability of watermarking in real-world scenarios. Fu- ture research should explore trade-offss among detectability, text quality, efficiency, and robustness to further strengthen watermarking for LLMs.
100011270
#0E Tooos
(c) 48 Bits
Figure 5. TPR of Stealthink and MPAC with number of tokens.
must ensure statistical
Table Bit accuracy when launching copy-paste attack with 24 bits embedded in 300 tokens.
Bit Accuracy
Copy-Past
Attack
c=0
e=0.1
c=0.2
e=0.3
StealthInk
0.9195
0.8932
0.8649
0.8319
MPAC
0,9627
0.9572
0,9334
0.9075
Qu et al. 0.9987
0.9981
0.9993
0.9993
Fernandez
0.6612
0.625
0.5762
0.5193
9

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Impact Statement
International Workshop, IH 2001 Pinsburgh, PA, USA, April 25-27, 2001 Proceedings 4. Springer, 2001.
We introduce StealthInk, a multi-bit watermarking scheme for large language models (LLMs) that enables the stealthy embedding of mnttaiinformation into generated text. This allows authorized user to verify the provenance of wa- termarked text without compromising its quality. Such watermarking approach is crucial in addressing ethical con- cerns related to LLM misuse, including the creation of fake news, scams, and academic plagiarism. Recognizing these incluuiinn OpenAI, Google,
Atallah, M. J., Raskin, V., Hempelmann, C. F., Karahan, M., Sion, R., Topkara, U., and Triezenberg, K. E. Natural language watermarking and tamperproofing. In Interna- tional workshop information hiding. Springer, 2002.
Austin, J., Odena, A., Nye, M., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C., Terry, M., Le, Q., et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07733 2021.
risks, major L.LM and Meta-have committed to incorporating watermarking techniques to mitigate misuse.
Bartz, D. and Hu., K. OpenAI, Google, others pledge to watermark Al content for safety, White House says. Website, 2023. http://wwww..utuersco///eeeeee/ safeuy-wlitchhoue-2223--777
To assess the security of StealthInk, we evaluated its re- silience against potential attacks aimed at forging the wa- termark or removing the watermark, including spoofing, copy-paste, and paraphrasing attacks. These attack vectors have been explored in prior watermarking research, and our focus was to compare StealthInk's robustness against other multi-bit LLM watermarking schemes. Through both theoretical analysis and empirical validation, we demon- strated StealthInk's 's advantages while also acknowledging its limitations.
Bojar, O., Buck, C., Federmann, C., Haddow, B., Koehn, P., Leveling, J., Monz, C., Pecina, P., Post, M., Saint-Amande H., Soricut, R., Specia, L., and Tamchyna, A. s. Findings of the 2014 workshop on statistical machine translation. Proceedings of the Ninth Workshop on Statistical Ma- chine Translation, pp. 12-58, Baltimore, Maryland. USA, June 2014. Association for Computational Linguistics. URL http: / www. aclweb. org/ anthology /W/ W1 4 3M//114-3322
LLM watermarking has the potential to serve as a valuable tool for preventing the ethical misuse of Al Al-generated text. Our work contributes to this effort by developing stealthy, multi-bit watermark that balances security, detectability, and text quality. In summary, we believe this research does not raise any ethical concerns and instead provides a practical approach to improving Al accountability and trustworthi- ness.
Christ, M., Gunn, S., and Zamir, O. Undetectable water- marks for language models. In Agrawal, S. and Roth, A. (eds.), Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Ma- chine Learning Research, pp. 1125-1139. PMLR, 30 Jun- 03 Jul 2024. URL ht : http:///poceenineeeeeeee .mlr. press /22//222/////// http://iristtaaaaeeeaeee .html.
Acknowledgment
This research was partially supported by the Virginia Com- monwealth Cyher Initiative (cyberinitiative.org through the Cyber Acceleration, Translation, and Advanced Protolyping for University Linked Technology (CATAPULT) Fund.
Cohran, W. G. Sampling Techniques. Wiley, 3rd edition, 1977.
Conover, M., Hayes, M., Mathur, A., Xie, J., Wan, J., Shah, S., Ghodsi, A., Wendell, P., Zaharia, M., and Xin, R. Free dolly: Introducing the world's first truly open instruction- tuned 11m. Company Blog of Databricks, 2023.
References
Aaronson, S. My AI Safety Lecture for UT Effective Altru- ism., Nov. 2023. https: / //s/sss// /scotttttt t ronson.
Fernandez, P., Chaffin, A., Tit, K., Chappelier, V., and Furon, T. Three bricks to consolidate watermarks for large lan- guage models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS). IEEE, 2023.
blog/?p=6823. Accessed May 5, 2023.
Abdelnabi, S. and Fritz, M. Adversarial watermarking trans- former: Towards tracing text provenance with data hiding. In 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021.
Goldreich, O., Goldwasser, S., and Micali, S. How to con- struct random functions. Journal of the ACM (JACM), 33 (4), 1986.
Atallah, M. J., Raskin, V., Crogan, M., Hempelmann, C., Kerschbaum, F., Mohamed, D., and Naik, S. Natural language watermarking: Design, analysis, and a proof- of-concept implementation. In Information Hiding: 4th
Hermann, K. M., Kocisky, T., Grefenstette, E., Espeholt, L., Kay, W., Suleyman, M., and Blunsom, P. Teaching machines to read and comprehend. Advances in neural information processing systems, 28, 2015.
10

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Hu, Z.,, Chen, L.,, Wu, Wu, Y., Zhang, H., and Huang, H. Unbiased watermark for large language models. In The Twelfth International Conference on Learning Represen- tations, 2024, URL https: forum? Adw.NCCFVVN.C
OpenAL. ChatGPT: Optimizing language models for di- alogue. Website, 2022. htttss///ppena. com/ blog/ hts//chattpp..
Papineni, K., Roukos, S., Ward, T., and Zhu, W.-. Bleu: a method for automatic evaluation of machine transla- tion. In Proceedings of the 40th annual meeting of the Association for Computational Linguisties, pp. 11.3111231 311-318, 2002.
Jiang, A. Q.. Sablayrolles, A., Mensch, A.. Bamford, C.,,
Chaplot, D. S., Casas, D. d. I., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., et al. Mistral 7b. Technical report, 2023.
Perkins, M. Academic Integrity considerations of Al Large Language Models in the post-pandemic era: ChatGPT and beyond. Journal of university teaching & learning practice, 20(2), 2023.
Jovanović, N., Staab, R., and Vechev, M. Watermark steal- ing in large language models. In Proceedings of the 41 International Conference on Machine Learning, 2024.
Kirchenbauer, J., Geiping, J., Wen, Y., Katz, J. Miers, I. and Goldstein, T. A watermark for large language models. Krause, A., Brunskill, E., Cho, K., En- gelhardt, B., Sabato, S., and Scarlett, (eds.), Pro- ceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 17061-17084 PMLR, 23-29 Jul 2023. v202 http://krccchbbbbueeeeua html.
Piet, J., Sitawarin, C.,, Fang, V., Mu, N., and Wagner. D. Mark my words: Analyzing and evaluating language model watermarks. arXiv preprint arXiv:2312.0027.. 2023.
Qu, W. Yin, D., He, Z., Zou, W., Tao, T., Jia, J., and Zhang, Provably Robust Multi-bit Watermarking for AI- generated Text via Error Correction Code. arXiv preprint arXiv:2401.16822 2024.
Kirchenbauer, J.. Geiping. J.. Wen, Y., Shu, M., Saifullah, K., Kong, K., Fernando, K., Saha, A., Goldblum, M., and Goldstein, T. On the reliability of watermarks for large language models. In ICLR, 2024. URL https: / //openreview.o... net / forum? DEJIDCWNO...
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of machine learning research, 21 (140), 2020.
Kordi Boroujeny, M., Jiang, Y., Zeng, K., and Mark, B. Multi-Bit Distortion-Free Watermarking for Large Lan- guage Models. arXiv preprint wxXi:2242..16577 2024.
Shih, F. Y. Digital watermarking and stegunogruphy fun- damentals and techniques. CRC press, 2017.
Team, G., Anil, R., Borgeaud, S., Alayrac, J.-B., Yu, J., Sori- cut, R., Schalkwyk, J., Dai, M., Hauth, A., Millican, K., et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805 2023.
Krishna, K., Song, Y., Karpinska, M., Wieting, J., and lyyer, M. Paraphrasing evades detectors of ai- ai-generated text, but retrieval an effective defense. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
Topkara, U., Topkara, M., and Atallah, M. J. The hiding virtues of ambiguity: quantifiably resilient watermarking of natural language text through synonym substitutions. In Proceedings of the 8th workshop on Multimedia and security, 2006
Kuditipudi, R., Thickstun, J., Hashimoto, T., and Liang, P. Robust distortion- -eree watermarks for language mod- els. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https: httt:::///peereviiii wpwneevveeee.......eeee.e..e.... net/ doooomiidd-aeeoeoooo aaa.ddd--paa.........
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine- tuned chat models. arXiv preprint arXiv:2307.09288 2023.
Lin, C.-Y. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, pp. 74-81, 2004.
Wang, L., Yang, W., Chen, D., Zhou, H., Lin, Y., Meng, F., Zhou, J.,, and Sun, X. Towards codable watermarking for injecting multi-bits information to LLMs. In The Twelfth International Conference on Learning Representations, 2024. URL https: /openrevieww net/ forum? i dd=Jyu5F gm
Liu, Y., Gu, J., Goyal, N., Li, X., Edunov, S., Ghazvininejad, M., Lewis, M., and Zettlemoyer, L. Multilingual denois- ing pre-training for neural machine translation. Transac- tions of the Association for Computational Linguistics. 8, 2020.

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Wu, Y., Hu, Z., Zhang, H., and Huang, H. Dipmark: A stealthy, efficient and resilient watermark for large lan- guage models. In Proceedings of the 41st International Conference on Machine Learning, 2024.
Yoo, K., Ahn, W., and Kwak, N. Advancing beyond identification: Multi-bit watermark for large language models. In Duh, K., Gomez, H., and Bethard, S. (eds.), Proceedings of the 2024 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 4031-4055, Mexico City, Mexico, June 2024. Association for Computa- tional Linguistics. doi: 10. 10.18653/w1/2024nmadd/
224. URL https: /ttp://anntoooooorg//////00 naacl-long.200 224/.
Zamir, O. Excuse me, sir? Your language model is leaking (information). arXiv preprinl arXiv:2401.10300 2024.
Zhang, H., Edelman, B. L., Francati, D., Venturi, D., Ate- niese, G., and Barak, B. Watermarks in the sand: Impos- sibility of strong watermarking for generative models. In Forty-first International Conference on Machine Learn- ing, 2024a.
Zhang, J., Zhao, Y.. Salch, M., and Liu, Pegasus: Pre- training with extracted gap-sentences for abstractive sum- marization. In International conference on machine learn- ing, pp. 1322 11339. PMLR, 2020.
Zhang. R., Hussain, S. S., Neekhara, P., and Koushanfar, Remark-llm: a robust and efficient watermarking frame- work for generative large language models. Proceed- ings of the 33rd USENIX Conference Security Sym- posium, SEC '24, USA, 2024b. USENIX Association. ISBN 978- 1778-1-9391333 133344-1..
Zhang. T., Kishore, V., Wu, F., Weinberger. K. Q., and Artzi, Y. Bertscore: Evaluating text generation with bert. arXiv preprint urXiv:1904.0900 09675, 2019.
Zhao, X., Ananth, P. V., Li, L., and Wang, Y.-X. Provable robust watermarking for Al-generated text. The Twelfth International Conference Learning Representations, 2024. URL /tttps://opett httpss///ppneeeeeeeeeeeeee forum?
12

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Appendix
A. Related Work
A.1. Zero-bit watermarking
Due to the discrete linguistic properties of text, watermarking for digital text is considered challenging problem (Shih, 2017). Early approaches were mainly rule-based, such as paraphrasing (Atallah et al., 2002), syntactic structure restructur- ing (Atallah et al., 2001), and synonym substitution (Topkara et al., 2006). Later, advancements in modern language models led to improved methods. (Kirchenbauer et al., 2023) introduced the first watermarking scheme for LLMs and highlighted the critical property of the tnveighting-based watermark by showing that the watermark could be detected algorithmically without any knowledge of the model parameters or access to the language model API. They categorized the vocabulary permutation into red and green lists using a hash function seeded with several previous tokens of the context text and proposed a reweighting strategy that simply adds a small bias to the logits of tokens in the green list. In this way, the tokens generated by the watermarked LLM will be biased to the green list. To detect the watermark, a detector possessing the hash function can recreate the lists and estimate the likelihood that the text is generated under reweighted probability distributions by hypothesis testing. Follow-up works proposed improvements to the robustness of this scheme against cestortion-boundee attacks such as insertion, deletion, and substitution attacks (Kirchenbauer et al., 2024; Zhao et al., 2024).
By retaining the red-green list configuration, (Hu et al., 2024) and Dipmark (Wu et al., 2024) introduced an evolved family of permutation- based reweighting strategies for watermarking which maintains the expected distribution of the text; i.e., they proposed a stealthy or unbiased reweighting strategy for LLM watermarking. However, the detector in (Hu et al., 2024) necessitates access both the prompt and the output distribution provided by the LLM for given prompt, which requires the detector possesses knowledge of the prompt used to generate the detected text. In contrast, Dipmark requires no access to the prompts nor the LLMs. Nevertheless, the stealthiness of both (Hu et al., 2024) and Dipmark rely on independent permutations at each generation step, which means when encountering the same seed (i.e., several previously generated tokens) for pseudorandom permutation generation, the token is sampled without a watermark. In this way, as more and more queries are submitted to the LLM, the available seeds for watermarking decrease dramatically, and thereby the watermark strength is sacrificed for the stealthiness guarantee. Moreover, their approach is vulnerable to an effortless attacker who removes the watermark during text generation.
In contrast, to develop stealthy watermark, (Christ al., 2024) and (Kuditipudi et al., 2024) employed another line of sampling strategy without altering the probability distribution at all when generating the watermarked text, i.c., the inverse sampling method. However, resilience to text corruption in (Christ et al., 2024) is still an open problem. While the watermarking method of (Kuditipudi et al., 2024) was designed for robust detection, it requires secret key distribution during detection, which may potentially compromise the data security and stcalthiness of the watermark. Moreover, the detection process in (Kuditipudi al., 2024) involves hundreds of resampling steps from the secret key distribution, which inefficient for lengthy texts. (Zhang et al., 2024b) trained the encoder-deoode modules facilitate watermark insertion and extraction. However, the modules have to be learned for each LLM,, which could be costly and inflexible. Besides, each text generated by the LLM will be processed by the encoder to embed the watermark, which will alter the original distribution of the LLM.
A.2. Multi-bit watermarking
(Wang et al., 2024) extended (Kirchenbauer et al., 2023) but used the message content as the hash key before selecting the green list and further utilized proxy language model for enhancing text quality. (Fernandez et al., 2023) proposed a technique for encoding a multi-bit message by providing a message-specific green list by shifting the vocabulary list dependent on the message. (Qu et al., 2024) built upon (Kirchenbauer et al., 2023), cyclically shifting vocabulary permutations according to the message and bias tokens in a green list to enable efficient multi-bit decoding. They also enhanced the embedding process by incorporating an error correction code into the message bits. However, overlapping shifts introduce interference, weakening message distinctiveness and statistical separation. To counteract this, a stronger bias is needed for reliable extraction, but this increases text distortion and reduces stealthiness. Crucially, these works achieved multi-bit watermarking by enumerating all potential messages or keys. Consequently, they involve computing across a space of potential messages that is exponentially large for the message length during decoding. This imposes practical limit to the message length due to computational or memory constraints.
MPAC (Yoo et al., 2024) introduced a multi-color technique wherein the pseudorandomly generated vocabulary permutation,
13

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
with previously generated tokens as the seed, is divided into multiple equal-length segments and the segments are represented by different color. Specifically, the message encoded into the text is formed by concatenating several message bits, each corresponding specific color segment. For instance, if the vocabulary is partitioned into four distinct colors, each message bit indicating the color interval to select should consist of two binary bits. In essence, if the message is composed of two message bits, then the message would be 4 binary bits long, as each position of the message hit is represented by two binary bits. During text generation, to embed the message using the next token, the index of the message bit is randomly chosen and the logits of the token in the color segment corresponding to the message bit are increased by a constant (6), which biases the selection of the next token be sampled from that color interval.
However, these methods (Yoo et al., 2024; Qu al., 2024) lack statistical stealthiness for potential attackers, making them very vulnerable to spoofing scrubbing attacks, we have evaluated. For example, MPAC is not stealthy according to Definition 4.1 (see Section 4), regardless of the value of 8. To give an intuitive explanation for stealthiness, if we assume an attacker with knowledge of the output distribution of the original non- non-watermarked LLM can launch a sufficient number of queries for the same prompt and estimate the probability distribution of the first token, the attacker can easily determine the presence of a watermark in the generated text of the above works since the probability distribution of the first token reflected by the LLM is not the same as that of the original non- non-watermarked LLM. In fact, the attackers can distinguish the watermark and launch several advanced attacks such watermark spoofing and scrubbing attacks (Jovanović al., 2024) even without the knowledge of the original non-watermarked probability distribution.
In contrast to these approaches, which are unstealthy or rely on different keys to embed the messages, (Kordi Boroujeny et al., 2024) and (Zamir, 2024) developed multi-bit watermarking techniques in which the input and output distributions are the same, i.c., they are distortion- free. Nonetheless, since they build upon (Christ et al., 2024). the resilience of these multi-bit watermarking schemes remains an unresolved issue. On the other hand, AWT (Abdelnabi Fritz, 2021) achieved unobtrusive encoding of text with binary message through adversarial training of the encoder-decoder structure. However, AWT is prone to errors in message extraction and occasionally yields degraded watermarked texts due to its reliance on neural networks.
B. Proof of Theorem 4.3
At the kthh query attempt, for each prompt a and the response x² length L*, to ensure 0 is independent, o (i E [1, L cannot be applied derive the reweighted probability distribution when the seed for PRF has been used during this query attempt. Instead, the original probability distribution Po Po (a²² a - should be used. Otherwise, the reweighted probability distribution PW" (afla", a 0 is applied to embed the watermark M*.
14

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Egii .Mi.
I Lami
IP wm (* la", M² 0 a 1:k-11, 1 M 1
L
g Mxnxx M
IP um (x la a M , 0h, alik-1 x2th-1 M
K
L
gg
M
P. um (2 la", 1 M of lik-1 x 1ik-- M Ml
km
==1
K
(b)
E
Bas
Eg, Parm (2 af M , 0h, a alk-1 , M 1)
k=1
1=1
K
1.a
(c)
EMs II Po (a 2. 1)
k==1
1m1
K
(d)
E as Po
k=1
K
II k=1
Po Po(x*1a*)
(8)
where (a) follows from independence of the sequence @1:k" (b) follows from the independence of e 1. (c) follows because either PW (xt aa,, xiig-) or la =f.;-)) is applied and from the unbiasedness of the reweighted probability distribution, and (d) follows from the chain rule for a joint distribution. The last equality follows from the randomness of the message, e.g., the timestamp will cause the message to be random.
C. Proof of Theorem 4.4
Let V = (Vi, V2...., Vivy} be the vocabulary of size [V], and let Po {pi, Ppi.P2.....Ppv PIv] denote the original probability distribution over V. We define permutation 0 ~ Unif(1, 2...., [V!]). The cumulative probability for the top tokens under permutation / is given by
X2(0)
Po(s)-
j=1
With slight abuse of notation, token V42 appear in position (1) in the permutation. Then its position on the cumulative probability axis the interval,
S [T,, 24 Pel, where 24
Po()-
(10)
j=1
With m-bit message M (O....,20 permutation-dependeen intervals,
2m 1} embedded, let k:
MI 2 and
(M+1)VV
Then ax0) and ((0) denote the
& (0)) Σ Poo),
8(0) = Σ PoG),
(11)
j=1
j=1
where (x)) is the sum of values sampled without replacement from Po. By standard properties of sampling without replacement (Cohran, 1977) the expectation and variance of are, respectively,
k
k(VV k)
Ma V
and 02
(12)
15

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
where x² vi Mエ Pi ) is the population variance of P.
When V is sufficiently large, which is easily satisfied for LLMs (e.g., V = 32, 000 for LLAMA2-7BJ, by the central limit theorem (CLT), a()) can be approximated by Gaussian distribution,
a(0) N (Ma:
(13)
and 2; ~ Onif 1 ps]- Since
B(0) a(0) + 8(0), where 6(0)
Σ Pol)
(14)
Given (()) is sum over Vi items sampled without replacement from the remaining [V] - k tokens, which in 2
total have mass 1 a(0). Then, under the CLT for sampling without replacement, we approximate
a ~ (us(aa) oz(a)).
(15)
where
r(1 a) [V k 0z(a)= r([V] - r) [V| 1-1 0²
mo(a)
(16)
E Ei Po(s) [V|-
where 0² vv|= 1
(P())
The value of r²2 depends on which tokens are selected into a, and
thus which tokens remain for 5. However, since do not know the specific indices 0( 0(k), approximate the residual set of tokens still following the original population distribution. Therefore, we assume of as o², In this way,
(a) r(ddk-r) -d-k-1
Using the relationship 3 = a + ö, the conditional distribution of 3 given a
1
(3 - a Ho(a)))
(3 a)
exp (a)
(17)
20 (a)
In this way,
(a, ~ fa(a)
(18)
and thus,
(- (a Maa2
1
(_ (3-a ps(aa))
(3
fa,
exp
exp
(19)
22m0g
20
20 (a)
Denote A(0) as the interval where the portion of token intersects with A(0) will be zeroed out, B(0) as the interval where the portion of token intersects with ((0) will be doubled. Then, under the four different cases, A(8) and ((t) are, respectively,
Case or 2: A(0) [a(0), 300), B(0) = - -000 a0)],
Case 3: A()) = [o<(0), 1 3(0). B(0) = [3(0), -
(20)
Case 4: A(0)
a)), B(0) [1 (0))
Since the updated probability a token depends on its position on the cumulative probability axis,
<etpp: w(2;; 0) dx.
P. (0)
(21)
16

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
where w(2;0) is defined
0, I E A(0).
w(: 0)
2, B(0),
(22)
1, otherwise.
We denote the reweighted probability of token Vi under permutation 0 as
(0) = P: - (a((0) + (B((),
(23)
where
(O = |S; ((O)), (g = |S; n B(O)-
(24)
We can calculate the expected reweighted probability under Case c as
Ea Bolp CCase = pt Eg [[S B(O) [S ( A(O)|/Case c]
(25)
According to (20), in different cases,
[S: n B(0) |S, n A(0) = mi; + Pt, [1]) - max (0) - (min + pt, A(0) max A(0) [0)
(26)
where for example, in Case or A()) a() and A(0) 3(0).
Above all, the expected reweighted probability is denoted
Ee [P.1]
Σ
P(Case cl EEa [Case c).
(27)
and the difference between E.g [pr and Pt is
e Ea Pt
P(Case E3 [S B(0) [S A(0)) Case c).
(28)
To derive e, define A Eo [[Ss n B(O) -1, A(0)) c]. Therefore,
1-p [.J. B) 1- p:
1 (BS)) |S, n A())) d8 da.-
A
(29)
Let S, = Iz Pr, - æı), which is symmetric to S. Since A(0) and B(0) symmetric,
s ((0) [s, ((()), (5AA(0)) |S, B(O)).
(30)
Therefore,
S ((0) - -(; = - - |S; A(0)).
(31)
Let ((;) = -()) then g 1 - -p:)
Therefore, g(x,)+(+))))))) -1-+ 0.
which means that g(x;)) antisymmetric about 1-p: In this way, for each fixed pair (o, the integral A the range 00, 1 p:] is evaluated to zero, i.e., A 0. Therefore, Σ IP(Case c) A = 0.
D. Algorithm 2
17

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Algorithm 2 StealthInk decoder
Input:
Text FI.L, secret key sk, texture key length h. texture key history hist, permutation generation function f. threshold
2, vocabulary size IVI, message set M, the length H of M MsgSeg, unit 2
Output: False or (True, MsgSeq)
H Initiate Rpoe - 0 for M E MM and pos E , 1]
for h 1 h do
Generate texture key & based on hh::
Set value pos [0, ......... H 1] with seed 8;
Generate permutation 0: [skk, 82)
for M E M do
Derive red list from eq. (4)
if x4 E RLM then
RM = Roos +
end if
end for
end for
...., H - Let jos = arg MiM Rad MsgSeglpos] M for pos E [0, 10.1. Calculate Z ZgM 11..)) from (6)
if (gSsgSe x1.L)= < then
return (true, Msg Seg) Else return false end
E. Clarification on the Difference between StealthInk with m = -1 and Dipmark
Although we set up m 1 for StealthInk, StealthInk is fundamentally different from Dipmark (Wu et al., 2024) in both design and functionality, and Dipmark cannot be adapted to embed multi-bit watermark using the multi-chunk mechanism. In StealthInk, under m=1, if we embed bit 0 at a certain generation step, then a=0 and /3 is the cumulated probability of the tokens in the first half of vocabulary permutation (see (2) and (3)). Then at the detector, the watermarked token would not be sampled from the first half of the vocabulary permutation because its token probabilities are reweighted to zero. Therefore, the detector knows the exact permutation and the interval of each message, and can deterministically identify whether token falls within the red list - enabling bit-accurate decoding. Each text generation step may have different denoted in Dipmark is fixed for each text generation step, In their detector, the secret key only determines
which depends on the embedded message. By contrast, which represents the probability interval in [0, oi] will be reweighted permutattoo of the vocabulary, and the detector must guess the green/red list separator 7 (e.g.. 0.5) to compute a green-tokee token ratio over the entire text. This design works well for zero-bit watermarking, but cannot recover message bits, nor can it guarantee bit accuracy when chunking the text to encode multiple bits. Therefore, chunking Dipmark to encode bit per segment would compromise decoding accuracy, as it lacks a per-step message- reweighting function and cannot verify individual bit intervals without brute-force search over the message space.
While we fixed not necessarily degrade performance. In Fig.
in the main experiments for consistency and fair comparison with prior work, increasing m does
notice that based on random selected prompts, m would be better for detectability than 2. However, as shown in theoretical analysis in Fig. 3a, the bit-per-token rate can actually improve when m increases, especially under high-entropy scenarios. For instance, under uniform distribution with maximum entropy and fixed eer of 0.01, m = 2 achieves a higher bit-per-token rate than m = (e.g., 2/42 vs. 1/30). The impact of m is denenet-dependent, and our framework supports varying m to trade off between capacity and detectability.
F. Discussion on the Resilience of StealthInk against Adaptive Attacks
We assume there is attacker who knows the probability distribution of unwatermarked model and would like infer the watermark by examining whether the distribution of responses generated by the watermarked model is the same that of the unwatermarked model. If the attacker cannot infer the watermark, then the watermark must be stealthy. He/she could launch a large number of query attempts (e.g., 100,000 or more) for the same prompt to derive the watermarked distribution. However, using our method, since randomness is injected through the timestamp metadata in the watermark (milliseconds), even though the same permutation and unwatermarked probability distribution is produced for these attempts, different
18

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
messages would involve different reweighting functions. Therefore, each attempt will result in a distinct watermarked distribution of the watermarked text, including the first couple of tokens. Thus, the averaging of these probabilities renders the spoofing attack ineffective. Additionally, because of the stealthiness property, on average. the probability distribution of the first generated token (i.e., calculate the probability of each first token in responses) would be preserved as the probability distribution of the first token from the original unwatermarked model. If the attacker launches these queries at the exact same time (e.g., 10:30:51:02, 03/28/2025) using the same userID, model, etc., then the first tokens will be generated with the same message embedded and therefore from the same distribution. In this case, the attacker could infer that the probability distribution of the first token is distorted, i.e., a bunch of tokens' probabilities are because the red tokens across these attempts are the same and will be reweighted to zero probability, which is different from the original distribution. However, launching such large number of queries at the same exact time is practically impossible.
Furthermore, in the scenario where an attacker constructs a suitable prompt to make the first few tokens almost deterministic (e.g., using a problem template like "ANSWER: nn" to fix the first several tokens), the watermark can be embedded only after the prefix. Any deterministic tokens can not include any watermark. Hence, as the watermarking starts after any fixed tokens, StealthInk still satisfies K K-shot stealthiness. The only problem that the detector would also check the prefix when detecting the watermark in the given text. Since the prefix non-watermarked, mixing it in the watermarked response could impact the detection performance. However, it is more like copy-paste attack, which mixes proportion of non-watermarked text into the watermarked text. We discussed it in Section 6.3, and in Table 5 it shows the bit accuracy will not be compromised significantly when the proportion of non-maaerdrrked text is small.
G. The Relationship between min and eer
We derive the relationship between the minimum length of text lmin for detection and the equal error rate (eer). For capacity m, we subdivide the interval [o, 1). formed by tokens' cumulated probability according the vocabulary permutation and original distribution, into subintervals of length 7 = 2- Then the red list of to is [0, 2 2-"". while the red list of 72m is [1 - 2- " 1]. Theoretically, for non- wen-waermarred text, the number of tokens in the red list of YM follows binomial distribution, _ ~ Bin(L, 7), for all M E M. Since FPR = P [mmnMMM L S 7 NW] 2 P[L
S 1 for all
M E M, we can establish a lower bound for the false positive rate by setting
117(1 ( (
1 7- Ly
+>
FPR
(32)
7 = Φ (FPR) V (1 Ly,
where (x)) denotes the cumulative distribution function of the standard normal distribution.
On the other hand, for a watermarked text with TMM- embedded, if a and B are as in Case or Case 2 in Fig. 2, no tokens
will be sampled from the red list of 7Ms which we call the no-overlapping case (Ö). In contrast, under Case 3 or Case 4, tokens could be sampled from the red list of YMs-, which we call the overlapping case (O). Obviously, P[O] = 2 2- and PPO]] = - 2-m. When context n-grams are repeated, the next token will be sampled from PM. which may result the token falling in the watermarking region as well. Assuming that the context n n-grams are repeated with probability p. denoted as P[R]- = p, the probability of non-repetition is P[R]-
p.
Next, we derive the probability that the token falls in the red list of YM- E M:
PfrtTM*] = P(R] Pf (R] + P(R] Pirt [R]
(33)
where
Pfrt7ar R = =P[O]
P(r((tr (R, + p Pfr(7N |R, Ō]
2
21.
2 y
dy
+
3
2
3 - y
dy
+
8
212
3
3 a
(34)
2m+T
Therefore,
(1 (1-p) (3 - aa)
PP(117M-)]
+ r(3 a).
(35)
2m-1
19

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
The distribution of - is binomial, i.e., L Bin (or(,,)) Similarly, L Bin(L, P(r(7ar)) and the probability that the token falls in the red list of Yas (M' * MM) is
P(rt
(36)
2m
The bound the false negative rate is given by
FNR P
min MEM
LRd 2 1j/ I.W
(37)
The right-hand side of (37) can be approximated as follows:
11 [ LIP (rt7rr [[1 Li
P
min MEM
TM 2 1) 1
2P PP 2 ] =
(38)
To derive lii., we start from the estimate of I= min = lo and derive v using (32). Then using that we derive the lower bound for the false positive rate as shown in (37). If the lower bound is larger than FNR, we increase mmin by I, where the process is iterated until the lower bound smaller than FNR. this way, we can derive the theoretical relationship between min and eer.
H. Experimental Details
Following Dipmark, we evaluate StealthInk on three tasks: machine translation, text summarization, and text completion. All experiments are conducted on the Nyidia A100 GPU with 40 GB of memory. We use SHA-256 as the pseudorandom function and a 1024-bit random bit string as the secret key sk. The default temperature 1.0 and the texture key length
3. The multinomial sampling strategy is applied during text generation. For the machine translation task, we utilize the WMT' 16 English (En) to Romanian (Ro) dataset, comprising 1,999 examples in the test set. We employ the Multilingual Bart (MBart) model (Liu et al., 2020) along with its official tokenizer. In the text summarization task, use the test set from the CNN-DM corpus (Hermann et al., 2015), consisting of 11,490 examples on BART-large (Liu et al., 2020). We compare StealthInk with MPAC and the watermarking schemes of (Qu et al., 2024) and (Fernandez et al., 2023). In MPAC, the green list bias 2, and (Qu et al., 2024) set = 6, while in (Fernandez et al., 2023), 5 = 0.5, which follow their original settings, respectively.
To evaluate text quality, we show the ROUGE score, the BLEU score, the BERTS score, and the perplexity of the text.
ROUGE Score. For the summarization task, evaluate the effectiveness of summaries using the ROUGE score (Lin, 2004), which measures n-gram overlap to determine how well the generated summaries capture key content from the reference summaries.
BLEEU score. For the machine translation task, we utilize the BLEU score (Papineni et al., 2002), which highlights the lexical similarity between machine- geeerreee translations and human reference translations.
BERTScore. BERTScore (Zhang et al., 2019) evaluates the similarity between two sentences by summing the cosine similarities of their token embeddings. We use BERTScore-F1 to assess performance in both text summarization and machine translation tasks.
Perplexity. Perplexity quantifies how well probability model predicts a given sample. Lower perplexity values indicate better predictive accuracy of the model.
To demonstrate the detectability performance of watermarking schemes, we evaluate them using metrics such as AUC, bit accuracy, TPR @1 I 1&FP, and extraction time. AUC reflects the overall detection capability, while TPR I 1%FPR represents the true positive rate when the false negative rate is below 1 1%. Bit accuracy measures the number of bits correctly extracted, and extraction time quantifies the time required to extract the watermarked message from given text.
I. Text quality comparison on text completion tasks
Fig. compares the perplexity (PPL) of different watermarking schemes at a generation length of 200 tokens. As the payload increases from 24 to 48 bits, the impact on text quality becomes more evident. StealthInk consistently preserves the
20

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
lowest perplexity among all watermarked outputs, closely aligning with the non-watermarked baseline, which indicates minimal degradation in text quality. In contrast, MPAC introduces moderate increases in perplexity, while the (Qu et al., 2024) method exhibits substantial degradation, especially under higher payloads. At 48 bits, the (Fernandez et al., 2023) method performs better than that of (Qu et al., 2024) but still lags behind StealthInk.
30
20
20-
20
10
Ray Wosersarked trackikk
MPHC
Qu Penadked wel
Nou Nutwrrrbd
Swattikk
MPAC
0t.t..
Nix Warccatae
Swatthi
MBNC
(a) 24 hits
(b) bits
(c) 48 bits
Figure 6. Text quality of watermarking schemes 200 tokens. For 36 and 48 bits, we omit (Femandez et al., 2023) due its high computational cost (see extraction time in Table 4).
J. Explanation for lower PPL of StealthInk compared to non-watermarked sequences in Table
We show the PPL with various number of generations in Table 7 and Table 8, which present the PPL statistics over responses of 200 tokens or 1000 tokens to 100 or 200 prompts. It is important to note that increasing the number of tokens response leads to faster convergence in statistical properties compared to increasing the number of prompts, since the former reduces per-sample variance more effectively. As shown in the 1000-token results, the PPL gap notably smaller across all watermark capacities, and the median values between non-wakermarked and watermarked texts are very close.
Therefore, we further increase the number of prompts or use even longer generated sequences, we expect the statistics of StealthInk and watermarrarr text to converge more closely with certain number of prompts generated tokens per response. This aligns with the theoretical stealthiness guarantee, which holds in expectation over sufficient generations. The small residual gap in practice is natural result of finite-sample variance rather than a violation of the stealthy design.
Table 7. PPL on responses to 100 prompts
of Tokens Responses to 100 Prompts
200
1000
Statisties of PPL
Mean
Median
Mean
Median
Non- Watermark
8.0437
8.0362
7.2706
7.3512
StealthInk (24 Bit)
7,4190
7.1819
7.1235
6.6913
StealthInk (36 Bit)
7.2576
7.1126
7.0746
7.0144
StealthInk (48 Bit)
7.1256
6.8348
6.9887
6.7862
Table 8. PPL on responses to 200 prompts
of Tokens Responses to 200 Prompts
200
1000
Statisties of PPI.
Mean
Median
Mean
Median
Non- Watermark
8.1686
7.9392
7.2442
7.3142
StealthInk (24 Bit)
7.3745
7.2002
6,9904
6.7184
StealthInk (36 Bit)
7.2754
7.0635
7.0528
7.0834
StealthInk (48 Bit)
7.2118
6.9258
6.9232
6.6822
For additional clarification, please refer to Fig. 6. While the central body of the violin plots for StealthInk and non- watermarked text are similar- indicating comparable overall quality- some non- non- watermarked responses exhibit extremely high PPL. (up to 30), which raises their median and average values. These outliers are not present dealthhnn-ggnneale
21

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
text due to its filtering of low-probability tokens, which can incidentally lower PPL. If we instead evaluate PPL across large number of responses the same prompt, both Stealthink and non-watermarked text would converge to similar PPL. values. That is because over many samples, Stealthink's reweighting does not introduce any overall bias into the output distribution; instead, it applies small, randomized modifications based on each specific prompt and embedded message to encode the watermark while maintaining stealthiness.
K. Fig. 7: AUC and Bit Accuracy of StealthInk with Number of Tokens
Bit accuracy
AUC
21
Capacioy bis
Cageeity-16 hits
Capicit-366 lits
Capacity
Capacity
100
200
300
400
500
600
100
2001
3001
4001
500
600
Tokeus
OI Toksus
Figure 7. Performance of StealthInk across increasing number of tokens.
L. Capacity Enhancement through Key Iteration
Intuitively, the watermark keys can be used embed messages. For instance, to embed 2-bit message, the watermark key can be selected from 4 possible candidates. Consequently, the embedding capacity be improved along dimensions simultaneously: first, by refining the watermarking scheme itself, such as with StealthInk, and second, by incorporating key iteration.
To evaluate this enhancement, we compare the performance of StealthInk with 24 bits embedded using its reweighting strategy and additional m' bits embedded via key iteration over 200 tokens. As a result, total of (24 + m') bits are embedded across these two dimensions. See the details Algorithm and Algorithm 4.
Algorithm 3 StealthInk Encoder Enhanced by Key Iteration
Input: Prompt a, secret key set SK {sko, ski...., skkmm } generation length J., texture key length h, permutation generation function f, unit 7, embedded message [Maey, M Sgg) where Mkey E {0, 1.... 2m' 1} and SggSeq message sequence of length H. texture key history hist 0.
for 1,..,, L do Calculate P. aa, 1)
Generate texture key based on x hb: Set value pos E {0, 1, 1,.., H - 1} with seed s;; let M = .M MggSeglpos) and 7M = My.
if s; E hist then
Sample æ; from Po(: (a, 1.)-1)
else
hist.add(s;)
Generate permutation 0, fsk 8:)
Calculate a and / using (2) and (3)
Calculate P. (- la, 10.i-1,0 0.) from (5)
Sample x; from PMM (. |a, 1, 8,)
end if end for
Fig. presents the AUC, @ 1%FPR, and bit accuracy when enhancing the capacity of StealthInk along these two
22

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Algorithm 4 StealthInk decoder under Key Iteration
Input: Text F1:L, secret key set SK {sko,ski skmm' -1), texture key length h, texture key history hist 0.
permutation generation function f. threshold 2, vocabulary size [V], message set M, the length H of MagSeg, unit
= 2-
Output: False or (True, [MRee, Msg Segl)
for Maey E 10.,,...,2 2m } do
SkMaey = 0 for pos E {0, 10. H - 1} and M E M
Initiate Rpos for i h++ 1,...,..4 do
Generate texture key 8, based on x x-
if 8, hist then Continue end if hist.add(ss)
Set value pos E (0, 1,......, H 11 with seed for M E M do Generate permutation 8, f(skMuny s;)
Denote red list RLM = 0. (7M + v]
F4 E RIM then
Rpos skM .M
skarkey" MM
Reoos
+
end if end for end for
end for
R skrr .M
Let M Sgg Mary [pos] = argmin W EM Rpos Calculate z-score Z (MsgSeeq Mary, I1.L) from eq. where Miey arg min skay ESK Z(MsgSeqMeen Mavu, ,IILL z-scores z then return (true, [M M MsgSeq Mics 1) Else return false end if
23

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
dimensions. The red dashed line represents the performance of Stealthink with 36 bits embedded 200 tokens, without any capacity enhancement via key iteration. We observe that the performance without key iteration significantly outperforms the approach that enhances capacity through both dimensions. For instance, under the same number of tokens, the AUC of StealthInk with 36 bits embedded is 12% higher than that of StealthInk with 31 bits embedded, where m' = 7. Table 9 shows the detection time when detecting a text watermarked by StealthInk with 24 + m' bits. We can observe exponentially increased detection delay is introduced as m' grows. Although the detection time for various watermark keys can be reduced by performing parallel detection across different watermark keys, the computational cost also increases as m'' grows, this additional overhead may limit the practicality of using multiple watermark keys.
Therefore, while key iteration increase embedding capacity, it may introduce performance trade-offs, potentially reducing detectability and increasing the detection delay.
3.59
0.57
3.9
0.75
340
0.75
0.22
3.90
3.88
0.33
3.8
0.52
26 bite with
3e 2i5 with
0.32
35 his with
386
0.55
Figure 8. Performance when enhancing the capacity of StealthInk through two dimensions, with total of 24 m'' bits embedded, where mn E 4,,
Table 9, Dection time when enhancing the capacity of StealthInk through two dimensions, with totally 24 + m' bits embedded.
m'
0
3
4
Detection time (s) 0.01
0.019
0.041
0.08
0.165
0.322
0.647 1.3
M. Limitations and Future Works
Our approach offers valuable insights into the design of stealthy and multi-bit watermarking system for L.MMs; however, it does have some limitations. Firstly, our method is effective primarily for original outputs with high entropy. For generated text with low entropy, where there large number of tokens with high probabilities, our reweighting mechanism tends to apply Case 3 or Case 4 in Fig. 2. Consequently, some tokens within the watermarking interval may still be sampled, causing the text to be detected as woteraatemr..dd. Secondly, while the stealthiness of our method makes it robust against spoofing attacks, it is equally important to develop a mechanism that can withstand sophisticated paraphrasing attacks, particularly given the advanced paraphrasing capabilities of modern LLMs. Moreover, as illustrated by (Zhang et al., 2024a), is always possible to find high-quality non- non-watermarked text that preserves the semantics of a watermarked text. However, watermarking scheme that is robust against paraphrasing attacks can sigmificantly increase the difficulty of identifying such a text. Future research should focus strengthening watermarking techniques to further raise this barrier, making it more challenging for adversaries to remove evade watermarks through paraphrasing. The spoofing attack of (Jovanović et al., 2024) targets zero-bit watermarking and may not easily extend to multi-bit schemes especially when the number of embedded bits increases. Thus, developing more advanced spoofing attack for bilti-bit watermarking and assessing the role of stealthiness crucial.
N. Watermarked Example
24

---

StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models
Table 10. Example of non-watermarked and watermarked texts generated by LLAMA-2-7B and StealthInk with 24 bits embedded at 200 tokens.
Earthquake research has found that earthquakes are not evenly distributed across the earth, but are concen- trated in certain specific strips. These strips where earthquakes concentrated are called seismic belts.
Prompt:
Message: 11100011011 101 101100101011
Non-watermarked:
The north coast of the Pacific Ocean and the east coast of Africa, these are the well-known zones strips where earthquakes occur. This makes you wonder if earthquakes are random in occurrence. No, they are not. They occur due to the interaction of the plates and the stress they are exerting on the Earth. Seismic Hazard Areas or Zones
After studying the geographical regions where earthquakes oceur more frequently, was found that these places are in areas with volcanoes or subduction zones. However, not the volcanoes or subduction zones are exactly the same. Some
active, and there fewer earthquakes that occur in these areas. However, there are many volcanoes that are rarely seen or felt by the people in that area. So, what is the difference between these volcanoes? Are there some volcanoes that are more active than others?
Watermarked:
In seismic belt, one can observe geographical zone where the earth's 's tectonic plates are interacting and forming tectonic boundaries. Also, these seismic belts or tectonic boundaries between the plates are usually found in areas where earthquakes occur. these areas, there are usually complex subsurface structures such as volcanoes, subduction zones, and mountains. These structures and boundaries between plates generate stress that is observed by the people earthquakes. There are many well-known seismic belts all over the world. However, most of the seismic belts or zones found in places such near the mid-ocean ridges. The mid-ocean ridges are located near the edges of the plates. Therefore, they contain seismic belts that separate plates from each other. The seismic helts are found in places
such as
Extracted Message: 11 10000 101 101 1000101011
Bit Accuracy: 0.96
Not-watermarked text P Value: 0,0006364775785215553
Watermarked text Value: 1.04571 1861 18116738334-09
25


Reviews:
[{"review_id": "G2XdPRTUIq", "reviewer": "Reviewer_Js5V", "summary": "The paper proposes a novel multi-bit watermarking scheme, StealthInk, for large language models (LLMs). It discusses both the embedding and detection of watermarks, with theoretical and experimental support.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Theoretical claims:\n\nWe correct eq. (4) as\n$$\nF_{k}(\\theta, M, P_{O}) = \n\\begin{cases}\n(X_k - \\beta)^+ + (X_k - \\bar{\\beta})^+ - (X_k - \\alpha)^- - (X_k - \\bar{\\alpha})^+, & \\text{Case 1 or 3} \\\\\\\\\n(X_k - \\beta)^+ + (X_k - \\bar{\\beta})^- - (X_k - \\alpha)^- - (X_k - \\bar{\\alpha})^-, & \\text{Case 2 or 4}\n\\end{cases}\n$$\nThis is a typo in the paper. However, **we truly execute reweighting function as the corrected eq. (4)** in the experiments, which is indicated in lines 220-245 of previously submitted codes in the supplementary materials.\n\nNext, we provide the proof for theorem 2 in the anonymous link [View the anonymous proof (PDF)](https://github.com/AnonymousLink123/anonymousREBUTTAL/blob/main/Proof%20of%20Theorem%202.pdf). During the proof, when reversing $\\theta$ to $\\theta^{r}$, the message $M$ should not be reversed to $M^{r}$. This is crucial because the expectation is taken over permutations sampled from the uniform set $\\Theta$, with a fixed message $M$. The reason is illustrated through the two terms that are marked as red and blue in the proof. In both the red and blue terms, we fix the message $M$ and vary the permutations across $\\Theta$. For each $\\theta$, there exists a corresponding reversed permutation $\\theta^r \\in \\Theta$. If we were to reverse $M$ in the blue term, we would no longer be computing an expectation over the same distribution, because each $P^{M}_{W}(\\cdot|\\cdot, \\theta)$ would no longer match its counterpart under reversal. The reweighted probabilities under $\\theta$ and $\\theta^r$ indeed cancel out asymmetries in the distribution only when $M$ is fixed, so the expectation over both directions is balanced. \n\n# Other Strengths And Weaknesses:\n\nWe define $F_{k}(\\theta, M, P_{O})$ as the cumulative function over the reweighted vocabulary permutation up to the $k$-th token. To recover the actual probability for each token, we define a differencing operator $G$ such that the reweighted probability for $k$-th token is: $$P^M_W(t_k | a, x_{1:i−1}, θ_i) = G(F_{k,k−1}(θ, M, P_O^i))=F_k(θ_i, M, P_O^i) − F_{k−1}(θ_i, M, P_O^i)$$ where $$F_0(\\theta_i, M, P_O^i) = 0$$\n\n# Other Comments Or Suggestions:\n\nFirst, we illustrate the discussion of an attack cost of 100, 000 (line 241 in page 5). We assume there is an attacker who knows the probability distribution of unwatermarked model, and would like to infer the watermark by examining whether the distribution of responses generated by watermarked model is the same as unwatermarked model. If even the attacker cannot infer the watermark, then the watermark must be stealthy. He/she could do lots of query attempts (e.g., 100, 000 or more) for the same prompt to derive the watermarked distribution. However, using our method, since the randomness (milliseconds) is injected, even though the same permutation and unwatermarked probability distribution is produced for these attempts, different message would involve various reweighting functions. Therefore, each attempt will result in distinct watermarked distribution of the watermarked  text, including the first couple of tokens. Therefore, the averaging of these probabilities renders the spoofing attack ineffective. Additionally, because of stealthness property on average, the probability distribution of the first generated token (i.e., calculate the probability of each first token in responses) would be preserved as the probability distribution of the first token from the original unwatermarked model. Only if the attacker launches these queries at the exact same time (e.g., 10:30:51:02, 03/28/2024) using the same userID, model, etc., then the first tokens will be generated with the same message embedded and therefore from the same distribution. In this case, the attacker could infer the probability distribution of the first token is distorted, i.e., a bunch of tokens' probabilities are 0 because the red tokens across these attempts are the same and will be reweighted to zero probability, which is different from the original distribution. However, such large number of queries at the same exact time is practically impossible.\n\nNext, we answer the second concern of the reviewer from prefix-specifible LLM. Although ''Answer:'' is a prefix specified by the user, the watermark can be embedded only after the prefix. Any deterministic tokens can not include any watermark. Hence, as the watermarking starts after any fixed tokens, our watermarking method still satisfies $K$-shot stealthiness. The only problem is that the detector would also check the prefix when detecting the watermark in the given text. Since the prefix is non-watermarked, mixing it in the watermarked response could impact the detection performance. However, it is more like copy-paste attack, which mixes a proportion of non-watermarked text into the watermarked text. We discussed it in Section 6.3, and in Table 5 it shows the bit accuracy will not be compromised significantly when the proportion of non-watermarked text is small.", "claims_and_evidence": "The main challenge addressed is multi-bit watermarking and authors' main claim is that their new method can solve this challenge. I find that the method definition and derivation are suitable for the multi-bit watermarking problem, with both theoretical proofs and experimental results supporting the claim, as detailed below.", "methods_and_evaluation_criteria": "The proposed method demonstrates significant novelty, introducing a new reweighting strategy designed specifically for multi-bit watermarking. The use of MPAC for position encoding is coming from Yoo et al., 2023, and I think it is a reasonable choice.", "theoretical_claims": "The overall theoretical flow is natural and appropriate, starting with the definition of stealthy or unbiased multi-bit watermarking, inducing the scheme, proving unbiasedness, and deriving the detection method. However, there are some concerns:\n1. Eq (4) may have a typo, as the expression for Case 2 appears to be the same as Case 1, which seems incorrect.\n2. The proof of Theorem 2 may have a mistake, as line 771 does not correspond to any case in eq (4). \n3. I am not entirely confident in understanding the proof of Theorem 2. I would like to have confirmation from the authors regarding: When reversing $\\theta$ to $\\theta^r$, should the message $M$ also be reversed to $M^r$? In other words , is it necessary to perform an additional shuffle of M based on $s_i$ at each step to ensure interval symmetry? I may not have fully grasped the proof and wish to communicate with the authors to understand these points. I am willing to adjust score once I confirmed these details to be correct.", "experimental_designs_or_analyses": "The paper uses appropriate evaluation metrics to assess the performance of watermarking method.", "relation_to_broader_scientific_literature": "This paper makes a novel contribution to the field of multi-bit watermarking for large language models.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The definitions of G are somewhat mixed together with F in eq (4). A clearer presentation would be beneficial.", "other_comments_or_suggestions": "Regarding the handling of the history log in the paper, there are various methods in practice that can weaken the strict K-shot stealthiness to achieve a trade-off between practicality and stealthiness. The paper's approach is reasonable, but I didn't quite follow the discussion of an attack cost of 100,000. My understanding is that the paper's method injects randomness into the first token (e.g., milliseconds), but an attacker can always construct a suitable prompt to make the first few tokens almost deterministic (e.g., using a problem template like \"ANSWER:\\n\" to fix the first two tokens). This would invalidate the randomness injection in the first token.", "questions_for_authors": "Please refer to the concerns raised in the \"Theoretical Claims\" section.\n\n---\n\nUpdate: I just noticed my separate comment is not visible to authors.\n\nI want to thank authors for update.\n\nI confirm the new $F_k$ is monotonically increasing for k and generates valid watermarked probability. However, I still don't catch all the proof. For $F\\_{|V|+1-t}(\\theta\\_i^r,M,P\\_O)=(X\\_{|V|+1-t}^r-\\beta)^++(X\\_{|V|+1-t}^r-\\bar{\\beta})^+-(X\\_{|V|+1-t}^r-\\alpha)^--(X\\_{|V|+1-t}^r-\\bar{\\alpha})^+$, does $\\alpha$ and $\\beta$ depend on $\\theta$? When $\\theta$ is reverse to $\\theta^r$, do we have a new $\\alpha^r$ and $\\beta^r$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L7DGQejAyD", "reviewer": "Reviewer_KJSb", "summary": "This paper introduces a novel watermarking scheme that allows for the stealthy embedding of multi-bit information within generated text. This method aims to enhance the traceability of AI-generated content while preserving the original text quality and ensuring robustness against various attacks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the positive evaluation of our work. We are glad to hear that our contributions were well received, including the theoretical foundation for multi-bit watermarking, the efficient and accurate decoding scheme, and the comprehensive evaluation.\n\nWe particularly appreciate your recognition of our formal definition of stealthiness for multi-bit watermarking and the theoretical derivation of the minimum number of tokens required for detection at a fixed equal error rate. We are also encouraged that the reviewer found our method to achieve a great tradeoff between multi-bit capacity, stealthiness, robustness, and efficiency, which addresses limitations in prior work.\n\nThank you again for your review and recommendation.", "claims_and_evidence": "The paper makes several claims regarding its watermarking scheme, and it generally provides substantial evidence to support these claims.", "methods_and_evaluation_criteria": "The time complexity for extracting the multi-bit information is quite impressive as it does not increase as the size of the information increases.", "theoretical_claims": "The theoretical claims looks correct with proofs provided. No issues.", "experimental_designs_or_analyses": "The authors have conducted a comprehensive set of experiments to validate their claims.", "relation_to_broader_scientific_literature": "The paper proposed a watermark algorithm that achieves multi-bit capacity, robustness, efficiency and undetectability while previous works failed to achieve all.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The paper provides a theoretical derivation of the minimum number of tokens required for watermark detection at a fixed equal error rate.\nThe authors formally define stealthiness for multi-bit watermarking, extending the concept from zero-bit watermarking.\nThe evaluation is comprehensive as detection accuracy, robustness, speed and text quality are all well covered.", "other_comments_or_suggestions": "No", "questions_for_authors": "Please refer to previous comments", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wWWnUr1P5C", "reviewer": "Reviewer_BuPL", "summary": "The paper introduces StealthInk, a watermarking scheme for LLMs that embeds multi-bit information into AI-generated text without disrupting the original text distribution. Unlike previous methods that either altered text outputs or limited watermarks to simple detection, StealthInk preserves the generative quality of LLMs while adding traceable data. The authors develop a mathematical framework to establish a lower bound on the token count needed for reliable watermark detection at a predetermined equal error rate, optimizing the scheme’s capacity for different use cases.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# \"Methods And Evaluation Criteria\" and \"Relation To Broader Scientific Literature\":\nWe thank the reviewer for the thoughtful comments. We clarify several key points regarding the originality of our work relative to DiPmark. \n\nAlthough we set $m=1$ in our main experiments, StealthInk is fundamentally different from DiPmark in both design and functionality. In StealthInk, the reweighting strategy is message-dependent at each generation step. For example, embedding bit 0 results in $\\alpha=0$ and $\\beta$ as the cumulative probability of tokens in the first half of the permutation (see Eq. (1) and (2)). During detection, the token will not fall within the red list, whose probabilities are zeroed, enabling bit-accurate decoding without ambiguity. By contrast, $\\alpha$ as denoted in Dipmark is fixed for each generation step, which represents the probability interval in [0, $\\alpha$] will be reweighted to 0. In their detector, though a vocabulary permutation for each token can be reproduced using the secret key, the detector must guess the green/red list separator $\\gamma$ (e.g., 0.5) to compute a green-token ratio over the entire text. This design works well for zero-bit watermarking, but cannot recover message bits, nor can it guarantee bit accuracy when chunking the text to encode multiple bits. Therefore, chunking DiPmark to encode 1 bit per segment would compromise bit accuracy, as it lacks a per-step message-aware reweight function and cannot verify individual bit intervals.\n\nOn the claim that increasing $m$ hurts performance: While we fixed $m=1$ in our main experiments, increasing $m$ does not inherently degrade performance. The effect depends on the entropy of the red tokens in the vocabulary permutation, which relates to the interval size $\\beta - \\alpha$ in Eq. (6). As shown in Figure 4, $m=1$ performs better on our selected prompts, but our theoretical analysis in Figure 3(a) shows that higher $m$ can improve bit-per-token rate—especially in high-entropy settings. For example, under a uniform distribution (i.e., maximum entropy) with EER of 0.01, $m=2$ achieves 2/42 bits per token v.s. 1/30 for $m=1$. Thus, $m$ offers a tunable trade-off between capacity and detectability, depending on the content.\n\nRegarding the metrics TPR@ 1%FPR and TPR@ 0.1%FPR: Due to the limit space, please refer to our response to the reviewer DZ3i about the evaluation metrics under two FPR and analysis.\n\n# Questions For Authors:\n\nWe appreciate the reviewer’s thoughtful observation. The difference in perplexity (PPL) values arises from the evaluation setup rather than a violation of StealthInk’s stealthiness.\n\nStealthInk applies two constraints during sampling: (1) it removes tokens in a red list by zeroing their probability, and (2) samples from the remaining tokens via multinomial sampling. In contrast, non-watermarked generation only applies the second step. In low-entropy scenarios, the red list mostly removes unlikely, low-quality tokens, slightly improving PPL. In high-entropy scenarios, it may exclude moderate-probability tokens, but sampling still favors higher-probability ones. In both cases, StealthInk reduces the chance of selecting semantically weak tokens, which can lead to slightly lower PPL.\n\nHowever, this does not contradict the stealthiness of StealthInk. The PPLs in Table 4 are aggregated over 200-token responses to 500 prompts, each with a random message and permutation. Natural variability across prompts and messages can cause small empirical differences. However, StealthInk is provably stealthy in expectation (see Definition 1 and Theorem 2): over many samples or longer outputs, the token distributions of watermarked and non-watermarked text converge.\n\nTo support this, we include PPL statistics for generations of 200 and 1000 tokens across 100 and 200 prompts in the anonymous link [View the PPL statistics](https://github.com/AnonymousLink123/anonymousREBUTTAL/blob/main/PPL%20Statistics.png). As shown, increasing the number of tokens per response significantly reduces the PPL gap. With 1000-token generations, the PPL gap is notably smaller, and median values are nearly identical across watermark capacities. Thus, if we further increase the number of prompts or sequence length, we expect even tighter convergence between the two distributions—consistent with StealthInk’s theoretical guarantees. The small remaining differences are due to finite-sample effects, not a flaw in the method. Figure 5 in Appendix G further illustrates this. The violin plots show overall similarity, with the non-watermarked PPL inflated by a few high-outlier responses (up to 30), which are less likely under StealthInk due to red list filtering. Evaluating many samples for the same prompt would yield even closer PPL values.\n\nWe will clarify this distinction in the revision to avoid confusion.\n\n# Other Comments Or Suggestions:\n\nWe thank the reviewer for pointing this out. We will correct it in the revision.", "claims_and_evidence": "All claims made in the submission supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "There is a flaw in the proposed method. In the proposed method, the authors use two parameters m and H to embeds m*H bits signal into the content. However, in experiments, the authors fix m=1, because increasing m will hurt the performance. With m=1, we will have beta=1, and the proposed reweight become the reweight used in dipmark. Thus, the method used in the experiment is generally dipmark plus a multi-chunk mechanism for embedding multi-bit information, which hurts the originality of this work.\n\n\nMost of the evaluation criteria make sense. However, for measuring the detectability, the authors only report TPR@10% FPR, which is not a practical metrics. Usually we consider TPR@1% FPR and TPR@0.1% FPR (Kirchenbauer et al., 2023).", "theoretical_claims": "No.", "experimental_designs_or_analyses": "I checked all experimental designs and analyses. The experimental settings are generally the same as prior work.", "relation_to_broader_scientific_literature": "From my perspective, the key contribution of this paper is the stealthy reweight method, which is developed upon dipmark. If we set m=1, the method in Figure 1 is just the same as dipmark.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "It seems that the authors did not use the ICML 2025 template provided on the official website.", "questions_for_authors": "In Table 4, the PPL of the StealthInk are significantly lower than the non-watermarked sequences, which contradicts to the steathy property of StealthInk. Can the authors explain the possible reason for this observation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n40ZyzZuSF", "reviewer": "Reviewer_DZ3i", "summary": "This paper proposes a multi-bit stealthy (a.k.a. unbiased) LLM watermark. The method is based on partitioning the text into different intervals, increasing the probabilities for some parts while decreasing the others, and keeping the overall distribution unchanged. The evaluation shows that the method can indeed have a better stealthiness than existing methods, but the detection performance is degraded.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# \"Methods And Evaluation Criteria\" and \"Relation To Broader Scientific Literature\" and \"Questions For Authors\":\n\nWe appreciate the reviewer’s insightful observation. We fully agree that normal utility metrics (e.g., BLEU, BERTScore, PPL) alone are not sufficient to evaluate stealthiness, as they may not reveal subtle distributional shifts. However, we would like to clarify the purpose and precedent for using these metrics in our work.\n\nOur paper does not treat utility metrics as indicators of stealthiness, but rather uses them to verify that text quality is preserved — a necessary condition for stealthy watermarks, though not sufficient. We rigorously define and prove stealthiness via distributional indistinguishability in Section 4.1 and Theorem 2, and we evaluate detectability empirically through spoofing attacks, false positive rates, and hypothesis testing (e.g., Table 3).\n\nImportantly, our zero-bit watermarking baseline DiPmark — which is specifically designed to be distribution-preserving — also follows the same evaluation strategy. As shown in the DiPmark paper (Figure 2 and Table 3), the authors explicitly use BLEU and PPL to demonstrate that DiPmark preserves the quality and distribution of the original language model output. These metrics are used to contrast DiPmark against distribution-modifying methods (e.g., Kirchenbauer et al., 2023), which exhibit clear utility degradation. Thus, reporting these metrics is a widely accepted practice for verifying that watermarking mechanisms do not compromise generation quality.\n\nRegarding the metrics of TPR@ 1\\%FPR and TPR@ 0.1\\%FPR: We thank the reviewer for the valuable feedback. In response, we have extended our evaluation to include TPR@ 0.1\\%FPR and TPR@ 1\\%FPR across different token lengths, which we agree are highly relevant for understanding watermark detectability under low false positive constraints. [View TPR@ 0.1\\%FPR and TPR@ 1\\%FPR comparation](https://github.com/AnonymousLink123/anonymousREBUTTAL/blob/main/Figures%20of%20TPR.pdf) through this anonymous link.\n\nWe found that while StealthInk may initially show slightly lower TPR at shorter lengths (e.g., 200 tokens), its detectability approaches or matches MPAC as the number of tokens increases. For example, when embedding 36 bits, MPAC ($\\delta$=2, i.e., original setting in MPAC) achieves TPR@ 1\\%FPR of 0.98 at 200 tokens, while StealthInk achieves comparable TPR@ 1\\%FPR (i.e., 0.985) at 400 tokens. Besides, we also compare the performance of StealthInk with MPAC ($\\delta$=1) and MPAC ($\\delta$=1.5) in the figures. We can observe that StealthInk is significantly better than MPAC ($\\delta$=1), while close to MPAC ($\\delta$=1.5). For example, when embedding 36 bits, MPAC ($\\delta$=1.5) achieves TPR@ 1\\%FPR of 0.97 at 300 tokens, while StealthInk achieves comparable TPR@ 1\\%FPR (i.e., 0.9725) at 400 tokens. Besides, StealthInk achieves better TPR@ 0.1\\%FPR than MPAC ($\\delta$=1.5) across different number of tokens.\n\nThis demonstrates that StealthInk is competitive in detectability given sufficient sequence length, while offering additional benefits in terms of stealthiness, robustness to spoofing, and multi-bit capacity. We would also like to emphasize that our design intentionally trades off a small degree of detectability in favor of stronger stealthiness guarantees. Unlike distribution-modifying schemes like MPAC, which achieve higher detectability through aggressive token-level distortion, StealthInk is designed to be statistically stealthy across multiple generations with theoretical guarantees. \n\nWe will add two columns of TPR@ 1\\%FPR and TPR@ 0.1\\%FPR in Table 4 and include these additional results and analysis in the appendix of revised manuscript to provide a more complete picture of the detectability-performance trade-off over varying token lengths.\n\n# Other Comments Or Suggestions:\n\nWe thank the reviewer for pointing this out. We will correct it in the revision.", "claims_and_evidence": "The main claim of the paper is the stealthy multi-bit LLM watermark method. The stealthiness is supported by the theoretical proof of Theorem 2; the multi-bit property holds true by the design of the method.", "methods_and_evaluation_criteria": "The paper uses the model normal utility (e.g. BERTScore/BLEU/PPL) to evaluate stealthiness and use binary classification metrics (AUC, TPR, Bit acc) to evaluate the detectability. I am concerned with the stealthiness metric, as a watermark can have a high normal utility while still have a bad stealthiness. That is, a watermark with distributional shift can still have a high BERTScore/BLEU/PPL on machine translation tasks. Therefore, I do not think the normal utility is a good indicator of stealthiness. For detectability tasks, the metrics are generally good but TPR@10%FPR is not a good fit - it is rare to tolerate 10% FPR for most tasks in watermarks. Metrics like TPR@0.01%FPR would be a better measure.", "theoretical_claims": "I did not check the mathematical details of the proofs for Theorem 1&2, but they make intuitive sense to me.", "experimental_designs_or_analyses": "The experiment results do not look good to me. The most important metric of a LLM watermark, i.e. the detectability, is shown in Table 4 where the proposed method has lower performance compared to related works (e.g. MPAC). I understand that the better normal utility of the watermarked model is one advantage of the method, but the performance gap is not negligible - a AUC decrease from >0.99 to <0.98 is a big decrease, and if we evaluate through metrics like TPR@0.1%FPR, the gap will be more obvious.", "relation_to_broader_scientific_literature": "This paper proposes a new method on the line of multi-bit LLM watermark research. The idea of increasing part of the probability distribution and decreasing the others could be an interesting finding to the field.", "essential_references_not_discussed": "Essential references are discussed.", "other_strengths_and_weaknesses": "The strengths and weaknesses are stated in the sections above.", "other_comments_or_suggestions": "The template is broken - headers and author lists are missing.", "questions_for_authors": "How does the detectability compare with other methods when evaluated with TPR@FPR=1% and TPR@FPR=0.1%?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes StealthInk, a watermarking scheme for LLMs that embeds multi-bit information into AI-generated text without disrupting the original text distribution.  The authors develop a mathematical framework to establish a lower bound on the token count needed for reliable watermark detection at a predetermined equal error rate, optimizing the scheme’s capacity for different use cases.

Strengths:
- The proposed method is novel for multi-bit watermarking. 
- The overall theoretical flow is natural and appropriate, starting with the definition of stealthy or unbiased multi-bit watermarking, inducing the scheme, proving unbiasedness, and deriving the detection method.
- The paper uses appropriate evaluation metrics to assess the performance of watermarking method.

Weakness:
- The paper only uses the setting for m=1, which limits the generality. 
- There is some concern regarding performance drop in AUC (from 0.99 to 0.98)
Decision: Accept (poster)