Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach

We are grateful for your time, valuable feedback, and appreciation of our theoretical contributions. In the following, we address your concerns point by point.

Q1. DAWA can be sub-optimal at the sentence level. Lemma 3 and Proposition 4 are not unique properties for DAWA, in fact, other token-level detectors, such as those in Example 2 also enjoy these nice properties (due to concentration brought by IID \zeta_t). Therefore, it is unclear how much DAWA is better than existing designs from a theoretical perspective. While authors have empirically shown the superiority of DAWA, I feel it still has to be clarified.

A1. Thanks for the insightful comment. It is correct that DAWA is a token-level adaptation of the jointly optimal sentence-level watermarking and detection scheme. In Lemma 3 and Proposition 4, our goal is to show that key theoretical guarantees of the sentence-level optimal design can be partially preserved in the token-level setting through DAWA, a property not shared by other token-level methods such as those in Examples 1 and 2.

Specifically:

• Lemma 3 demonstrates that DAWA uniquely controls the worst-case sentence-level FPR by regulating the token-level FPR. This is non-trivial and relies on DAWA’s design being adaptive to the LLM’s next-token prediction (NTP) distribution. Such control is not guaranteed for other token-level detectors.
• Proposition 4 establishes robustness to token replacements, which results from DAWA’s design of redundant auxiliary variable $\\tilde{\\zeta}$. This auxiliary redundancy is a distinctive design element of DAWA, not present in prior schemes.

While we agree that these results are not directly comparable to theoretical guarantees of other schemes under different formulations, our theoretical analysis complements extensive experiments that validate Lemma 3 and Proposition 4 and directly compare DAWA to strong baselines.

In summary, DAWA is both principled and practical: it inherits desirable properties from an optimal sentence-level formulation while remaining effective in the real-world token-level context. We believe this combination, supported by theory and validated by experiments, justifies its contribution. We will clarify this point further in the revised version and continue to refine DAWA both theoretically and empirically.

Q2. The recovery process of $\zeta\_t$. Why a significantly different SLM than the original model can accurately reconstruct $\zeta\_t$? My impression is that the recovery can be successful (even partially) when the surrogate model is similar to the original LLM.

A2. Thank you for the sharp observation. While it may seem intuitive that accurately recovering $\\zeta\_t$ would require an SLM similar to the original LLM, our results demonstrate otherwise; DAWA’s recovery process of auxiliary variables is robust even with a different SLM.

As shown in Appendix K, Tables 4 and 5, accurate recovery is still achievable using a much smaller SLM from a different model family, and even without prompts. This robustness stems from the special structure of the conditional distribution $P\_{\\zeta\_t \\mid x\_1^t}$ induced by the optimal watermarking design.

In particular:

• As illustrated in Figure 4, recovering $\\zeta\_t$ only requires reconstructing the conditional distribution $P\_{\\zeta\_t \\mid x\_1^t}$ and does not require the surrogate NTP distribution $\\tilde{Q}\_{X\_t \\mid x\_1^{t-1}}$ to precisely match the true token distribution.
• As shown in the right-hand side of Figure 5 (Appendix F), for auxiliary values corresponding to high-probability tokens, their probability under $P\_{\\zeta\_t \\mid x\_1^t}$ is set to the fixed FPR control parameter $\\eta$, and is therefore insensitive to SLM mismatches.
• For low-probability tokens, the corresponding auxiliary value probability directly reflects the token’s likelihood, which is typically low and less sensitive to variation across models.
• Furthermore, the redundant auxiliary variable $\\tilde{\\zeta}$ is assigned a significantly higher probability than the other values, making it robust to small perturbations in $Q\_{X\_t \\mid x\_1^{t-1}}$ and improving the overall recovery accuracy.

Thus, DAWA’s recovery of auxiliary variables is not critically dependent on having a close surrogate model. This robustness is a key strength of our design, and we will clarify this point further in the final version.

We sincerely appreciate your support and thoughtful review. We hope our responses have adequately addressed your concerns.

We are grateful for your time, valuable feedback, and appreciation of our theoretical contributions. In the following, we address your concerns point by point.

Q1. The punchline falls short.

A1. While our theoretical framework makes simplifying assumptions, such as a fixed text length, these enable tractable and rigorous characterization of the jointly optimal watermarking scheme and detector. Despite the idealized setting, it provides a solid foundation for more realistic models.

More importantly, the theory motivates a practical watermarking algorithm, DAWA, based on the key insight that optimal schemes should be adaptive to the LLM’s generative distribution—a feature not explored in prior work and central to DAWA’s strong empirical performance.

As shown in Figure 1, DAWA clearly outperforms prior distorted and distortion-free baselines, especially in the ultra-low FPR regime (e.g., $1e-5$), demonstrating that our theoretical insights translate into practical gains.

Q2. Experimental design could be improved.

A2. We thank the reviewer for these suggestions and provide detailed clarifications below:

1. On evaluation at ultra-low FPR:
   We would like to highlight that Figure 1 on Page 2 already reports TPR at ultra-low FPRs (e.g., $1e-5$) as a key experimental result. In this setting, DAWA consistently outperforms strong baselines, including KGW+23 [25], EXP-edit [37], Gumbel-Max [38], and HCW+23 [19], with significantly higher TPR. This evaluation was conducted on $10^5$ texts (200-length) from Wikipedia dataset, with further details in Section 6. Table 6 in Appendix K complements this by validating that DAWA’s TPR increases with token length T, confirming the benefit of longer contexts.

2. On experiments with FPR $<1e-5$:
   In many existing works, such as [3-7] and the baselines we compare against (KGW+23 [25], EXP-edit [37], Gumbel-Max [38], and HCW+23 [19]), detectability evaluations are typically reported only down to FPR $=1e-4$ or $1e-3$. In contrast, our performance evaluation at FPR$=1e-5$ already places our analysis in a more stringent and practically relevant low-FPR regime.
   We agree that evaluating under even lower FPR regimes would strengthen the results. However, such experiments require substantially larger-scale computation and runtime, which is unfortunately infeasible within the short rebuttal period. We plan to include these extended evaluations in the final version.
   
   [3] Jovanović et al. Watermark Stealing in Large Language Models. ICML, 2024.
   [4] Kirchenbauer et al. On the Reliability of Watermarks for Large Language Models. ICLR, 2024.
   [5] Hans et al. Spotting LLMs with Binoculars: Zero-Shot Detection of Machine-Generated Text. ICML, 2024.
   [6] Wouters, B. Optimizing Watermarks for Large Language Models. ICML, 2024.
   [7] Chen et al. WatME: Towards Lossless Watermarking Through Lexical Redundancy. ACL, 2024.

3. On p-value in baselines:
   We carefully reviewed [1] and acknowledge that it introduces a non-asymptotic p-value expression to better align theoretical and empirical FPR. However, the detector statistics $S_T$ used in KGW+23 [25] and Gumbel-Max [38] remain unchanged, and the refined p-value merely provides a principled way to set the threshold.
   In our experiments, we evaluate detection performance using the ROC-AUC score, which captures performance across the full range of thresholds and does not rely on setting a specific detection threshold or computing p-values. Therefore, comparing AUC scores and TPR at fixed FPR provides a fair and empirical measure of relative performance across methods.
   Moreover, as shown in Lemma 3 and Table 7 (Appendix K), our theoretical choice of FPR in DAWA tightly upper bounds the empirical FPR, providing an even stronger theoretical guarantee for threshold selection than [1], which does not ensure an upper bound on empirical FPR.

4. On entropy reporting:
   We estimated the entropy values of the C4 and ELI5 datasets using Llama-2-13B and Mixtral-8$\times$7B, respectively, with the temperature set to 1 for both models. As shown in the table below, entropy varies by model, which is consistent with your observation, and we confirm that the C4 dataset consistently has higher entropy than ELI5 dataset.

Q3. Flawed robustness evaluation.

A3. We address each point as follows:

1. On the strength of the T5-based attack:
   We note that with 50% of tokens masked, approximately 35% were actually replaced on average by the T5 model, constituting a reasonably strong token replacement attack. This level of perturbation is commonly used in prior works (e.g., KGW+23 [25] and Zhao et al.[26]). If an attack completely rewrites more than half of a sentence, it may begin to significantly alter semantics or text quality, making it less practical. Moreover, as shown in our results, this attack does degrade detectability for HCW+23, indicating that the attack is impactful. DAWA’s stable detectability under the same setting reflects the robustness of its design, which includes redundant auxiliary variables.

2. On the limited attack types:
   In Section 6.2 and Appendix L.1 (Table 8), we also evaluated DAWA under random deletion and paraphrasing attacks. DAWA outperforms Gumbel-Max and KGW+23 in deletion robustness and matches their performance under paraphrasing. These results confirm that DAWA remains competitive while balancing robustness, efficiency, and detection accuracy, with the potential to demonstrate a graceful trade-off based on our theoretical analyses.

3. On the report of ROC-AUC and FPR:
   Due to time constraints, we were unable to add robustness experiments on a larger dataset to explore FPR $<1e-5$. However, we report ROC-AUC scores in all experiments to reflect detection performance across the full FPR spectrum, ensuring a fair comparison. We plan to add more experiments in the final version.

4. On theoretical generalization to robustness:
   Although robustness is not the core focus of this paper, Appendix L outlines how our theoretical framework and optimal solutions extend to scenarios involving a wide range of attacks, including semantic-invariant attacks. These findings offer valuable insights for designing advanced semantic-based watermarking algorithms that are resilient to such attacks in the future.

5. On hashing and use of Self-Hash:
   We clarify that we actually employed the Left-Hash function in our experiments. Since cryptographic security is outside the scope of this paper, we did not include an in-depth discussion of hash function security. However, we agree that this is an important consideration and will incorporate a more thorough discussion of secure hashing in future work.

Q4. In the theoretical part, does the key depend on the generation? As far as I understand, the random sequence is sampled independently, but what about the g function? If that is the case, this theoretically imposes a new key for each text, which renders the scheme quite useless in practice?

A4. As we understand it, this question asks if the secret key shared between LLM watermark generation and detection depends on the generation scheme. We clarify that the secret key is fixed and used together with prior tokens to generate a sampling seed. Thus, it does not depend on generation and can be directly shared with the detector.

The function $g$ in the detector is simply a predefined bijection between the auxiliary variable set $\mathcal{Z}$ and a superset of the token vocabulary $\mathcal{V}$. It is also fixed and does not change across generations.

To offer a concrete toy example of $g$: suppose the token vocabulary is $\mathcal{V}=\lbrace a,b,c \rbrace$. We can define an extended set \mathcal{S}=\lbrace a,b,c,\\# \rbrace \supset \mathcal{V} and a bijective $g\_{tk}$ that maps auxiliary symbols $\mathcal{Z}=\lbrace 1,2,3,4 \rbrace$ to elements in $\mathcal{S}$. This mapping remains static and available to both encoder and detector, and does not impose a new key per text.

Q5. Minor questions.

A5. We address each point as follows.

1. On controlling $\alpha$ in experiments:
   As stated in Lemma 3 of the main text, the sequence-level FPR $\alpha$ is controlled through the chosen token-level FPR $\eta$, the generated sequence length $T$, and the detection threshold $\lambda$. Specifically, if $\eta\in(0, \min\{ 1, (\alpha/\binom{T}{\lceil T\lambda \rceil})^{\frac{1}{\lceil T\lambda \rceil}}\}]$, the worst-case false alarm for a length-$T$ sequence is upper bounded by $\alpha$.

   In general, given $T$ and $\lambda$, a smaller $\eta$ results in a smaller $\alpha$; given $T$ and $\eta$, a higher $\lambda$ results in a smaller $\alpha$.
   In practice, we use \eta \= 0.2 and T \= 200, and select $\lambda$ using roc_auc_score function, which varies $\lambda$ over a full range to compute empirical FPR and corresponding TPR (see Figure 1, Tables 1, 4, 5, and 6).

2. Theoretical vs. empirical FPR and very low FPR regimes:
   Appendix K, Table 7 shows that empirical FPR aligns tightly with the theoretical upper bound down to $1e-5$, confirming Lemma 3. While additional tests at even lower FPRs (e.g., $1e-6$) would be informative, the theoretical guarantee already holds for any target $\alpha$, and Table 7 serves to empirically validate this.
   We agree ultra-low FPR regimes are important for high-stakes use cases and will include further evaluations in the final version due to the time limit. We also plan to move some explanations from the appendix into the main paper for better clarity.

Q1. Outdated Baseline Comparisons: The paper lacks comparisons with recent and more competitive methods that explore the performance-detectability tradeoff, e.g., [1,2,3]. These more recent works could provide stronger baselines and highlight the significance of the proposed method.

A1. Among the cited works, [1] and [3] appeared concurrently with our submission, and thus, making a direct comparison infeasible at the time of our experiments. We will discuss them in the related work section of the final version.

Regarding [2], we have conducted additional experiments to include a comparison with it. The results are summarized in the table below. Our method demonstrates favorable performance in terms of both robustness and detectability under comparable conditions.

Table 1: Clean Text

Table 2: Token Replacement Attack

Q2. Limited Discussion of Related Work: While the paper cites many earlier watermarking techniques, it fails to address key advancements in performance-detectability tradeoff optimization from recent years. This omission weakens the contextual positioning of the proposed method.

A2. To the best of our knowledge, among the plethora of LLM watermarking works, we have cited the most relevant and up-to-date ones both from the empirical and theoretical perspectives. For a more comprehensive literature review, we refer the readers to Appendix A and the recent surveys [4,5] ([2,3] in our manuscript), due to the space limit.

If there are specific recent works that we have overlooked, we would appreciate it if the reviewer could point them out. We will make sure to include them and expand the related work section in the final version.

Reference:

[4] Aiwei Liu, Leyi Pan, Yijian Lu, Jingjing Li, Xuming Hu, Xi Zhang, Lijie Wen, Irwin King, Hui Xiong, and Philip Yu. A survey of text watermarking in the era of large language models. ACM Computing Surveys, 57(2):1–36, 2024.

[5] Junchao Wu, Shu Yang, Runzhe Zhan, Yulin Yuan, Lidia Sam Chao, and Derek Fai Wong. A survey on LLM-generated text detection: Necessity, methods, and future directions. Computational Linguistics, pages 1–66, 2025.

Q1. The paper does not explicitly discuss how the proposed optimal detector reduces to the canonical ratio test. How does the proposed optimal watermarking scheme reduce to the likelihood-ratio test for a fixed P vs. Q?

A1. We appreciate the reviewer’s question. The canonical likelihood-ratio test (LRT) is optimal when the null and alternative hypotheses are fully specified by fixed distributions $P$ and $Q$, and when the goal is to minimize the Type-II error (1-TPR) subject to a constraint on the Type-I error (FPR). However, our setting is fundamentally different.

In our formulation:

1. Neither $H_0$ nor $H_1$ corresponds to a fixed distribution: Under $H_0$, the distribution $P_{\zeta_1^T}$ over auxiliary sequences is induced by the watermarking scheme and is unspecified. Under $H_1$, the joint distribution $P_{X_1^T, \zeta_1^T}$ depends on the design of the watermarking scheme and is to be optimized. Therefore, our detection task is a composite hypothesis test, and the LRT is not optimal in this setting.
2. Our goal is to minimize the Type-II error (1-TPR) subject to a constraint on the worst-case FPR and a constraint on the watermarked text distortion.
3. Moreover, as emphasized in Line 33, the detector is required to be model-agnostic, i.e., it cannot depend on $P_{\zeta_1^T}$, $P_{X_1^T, \zeta_1^T}$, or $Q_{X_1^T}$, as these distributions may not be available to the detector at test time. Therefore, the likelihood ratio test, which requires knowledge of the underlying distributions, is not applicable.

These key constraints distinguish our problem from classical hypothesis testing. Given this setup, Theorem 2 characterizes the jointly optimal watermarking scheme and detector, where the optimal detector is determined by some chosen function $g$. Notably, this detector does not reduce to an LRT, precisely because the assumptions and objectives of the classical setting do not apply in our framework.

Q2. Could you provide concrete examples of how existing watermarking schemes instantiate the bijection $g_{t,k}$, showing each as a special case of your general mapping function?

A2. We clarify that our framework characterizes the jointly optimal pairs of detector and watermarking scheme. As a result, the existing watermarking scheme, many of which rely on heuristics or focus solely on optimizing the detector, are not special cases of the jointly optimal design and do not instantiate our derived optimal detector.

In our practical detector design (Eq. (5)), the bijection function $g_{tk}$ is a token-level adaptation of the bijection function $g$ from Theorem 2. To offer a concrete toy example: suppose the token vocabulary is $\mathcal{V}=\lbrace a,b,c \rbrace$. We can define an extended set \mathcal{S}=\lbrace a,b,c,\\# \rbrace $\supset \mathcal{V}$ and a bijective $g_{tk}$ that maps auxiliary symbols $\mathcal{Z}=\lbrace 1,2,3,4 \rbrace$ to elements in $\mathcal{S}$.

Q3. The core derivations are rigorous but somewhat abstract and dense, with little high-level intuition, making the manuscript less readable.

A3. We acknowledge that the core derivations are mathematically involved, and we have aimed to provide high-level intuition through the visual illustrations in Figures 2, 3, and 5, which highlight the theoretical insights and trade-offs. We will revise the manuscript to further improve clarity, including adding more intuition and commentary around key results, to make the presentation more accessible in the final version.

We sincerely appreciate your time and valuable feedback. We hope our responses have adequately addressed your concerns, and if so, we would be grateful if you could consider revising your score to further support our submission. Thank you again for your thoughtful review.