acceptodds
Under review as a conference paper at ICLR 2027

Tree-Based Speculative Decoding for Watermark Generation via Vocabulary Partitioning

Abstract

Watermarking helps identify LLM-generated text for data provenance, but its practical deployment requires fast generation. Tree-based speculative decoding could accelerate watermark generation by proposing multiple candidate continuations at each step, so that another candidate can still be accepted if one is rejected. However, applying it to watermarking is challenging: different branches use different pseudorandom sources, making the watermark signal harder to detect. We address this challenge by deterministically partitioning the vocabulary into disjoint subsets and sampling one draft token from each subset to form a distinct branch of the draft tree. The subset containing an observed token identifies the only draft branch that could have produced it, leaving that branch and residual sampling as the two possible sources. We prove that the resulting algorithm preserves the target model’s output distribution and achieves a draft acceptance probability at least as high as that of single-sequence speculative decoding. Experiments with Gumbel-max and SynthID watermarks show improved generation throughput while largely preserving detection power. We also show that our method can benefit from advances in drafter design, with an EAGLE-style draft head enabling additional speedups.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large language model watermarking, Tree-based speculative decoding, Vocabulary partitioning, Efficient LLM inference

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_vJvVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary
  • Proposes a method to accelerate text generation while watermarking without compromising watermark detection reliability or generation quality.
  • To overcome the limitations of the existing single-sequence estimation approach, a tree-structured draft is constructed, and multiple candidates are verified simultaneously through deterministic vocabulary partitioning.
Critical strengths
  • The paper is generally well written.
  • The claim of accelerating generation speed is interesting, and the rationale behind this claim appears to be well justified.
Critical weaknesses
  1. Although the proposed method improves watermark generation speed, it appears that the detection performance (TPR) decreases as generation speed increases. This raises concerns about whether the improvement in generation speed sufficiently justifies the reduction in detection performance.
  2. While the paper demonstrates improvements in watermark generation speed, the detection speed is not reported. Evaluating detection latency would provide a more comprehensive understanding of the computational efficiency of the proposed method.
  3. Although the proposed method improves generation speed, it is unclear whether the generated text maintains its quality. If text quality degrades, the presence of a watermark may become more noticeable to users. Therefore, reporting text quality metrics, such as Perplexity (PPL), would help assess whether the proposed method achieves faster generation without compromising text quality.
Questions for authors
  • The questions are the same as those raised in the Weaknesses section.
3 comments
AuthorsOpenReview ↗

Response to Reviewer vJvV

W1. Speedup vs. detectability

Thank you for raising this point. In short, the detectability change is small for moderate branching factors and vanishes for long texts, while generation quality (W3) and detection cost (W2) are unchanged. We elaborate below:

  • Small loss at moderate kk. Across all 12 settings (Tables 1, 3, and 5), k=2k=2 improves AATPS by 13.613.6–20.4%20.4\% with a TPR decrease of at most 4.04.0 pp (median 1.21.2 pp), and k=3k=3 improves AATPS by 22.222.2–31.3%31.3\% with a TPR decrease of at most 6.76.7 pp (median 2.62.6 pp). Without our vocabulary partition, the decrease would be far larger (e.g., SynthID TPR falls to 4040–50%50\% at k=4k=4; Table 1).
  • Generation with an EAGLE drafter. With an EAGLE-style head at k=2k=2, our framework achieves 1.481.48–1.92×1.92\times throughput over Seq with the standalone drafter, with TPR no lower than Seq in all four settings (Table 2). Most of this gain comes from the lighter drafter, and the tree adds up to a further 1.18×1.18\times on top of it (Table 6).
  • Long-form generation. Long-form generation is where acceleration saves the most absolute time. For detection, since TPR increases with text length for every kk, the gap between k≥2k\ge2 and k=1k=1 shrinks as texts grow longer. In a new experiment on OEG with the Llama model pair, the gap between k=4k=4 and k=1k=1 shrinks from 4.14.1 to 0.30.3 pp (Gumbel-max) and from 4.24.2 to 0.20.2 pp (SynthID) as the length increases from 200200 to 600600 tokens:
TPR@FPR$=1%$n=200n=200n=400n=400n=600n=600
Gumbel-max, k=1/2/4k=1/2/497.6 / 96.3 / 93.598.9 / 97.9 / 97.498.9 / 98.8 / 98.6
SynthID, k=1/2/4k=1/2/495.7 / 93.1 / 91.599.0 / 98.7 / 98.199.6 / 99.5 / 99.4

Based on these results, we recommend k=2k=2 when detectability is the priority (e.g., short texts) and k=3k=3 when more acceleration is desired, especially for long-form generation.


W2. Detection speed is unaffected

Thank you for raising this point. We note that detection is typically performed offline and only once per text, so it does not affect generation latency. Moreover, detection requires no model forward pass: it only reconstructs the pseudorandom variables from the text. Compared with single-sequence decoding (k=1k=1), our method adds one lightweight hash per token to identify the subset containing that token; all other computations are unchanged.

We add a new experiment to measure the detection time per 200-token text (Llama, QA; 100 texts per setting; mean in ms, standard deviation in parentheses):

Watermarkk=1k=1k=2k=2k=3k=3k=4k=4
Gumbel-max490.4 (1.3)490.5 (0.7)490.3 (0.8)490.6 (0.5)
SynthID56.5 (0.3)56.8 (0.2)56.7 (0.2)57.0 (0.8)

This result shows that the detection time of our method is nearly identical to that of k=1k=1, so our method improves generation speed without affecting detection efficiency.


W3. Text quality is preserved

Thank you for raising this point. We address it from both theoretical and empirical perspectives.

  • Theory. Thm. 3.1 shows that our method exactly preserves the output distribution of the target model: in expectation over the pseudorandomness, each generated token follows the target distribution PP. Watermarking with our method therefore does not degrade generation quality.
  • Experiments. We computed the log-perplexity of generated texts with Llama pair on QA, evaluated by the target model, for non-watermarked generation (Base), single-sequence watermarked decoding (Seq), and our method with k=2,3,4k=2,3,4 (mean ±\pm 95% CI):
WatermarkBaseSeqk=2k=2k=3k=3k=4k=4
Gumbel-max2.489 ±\pm 0.0372.483 ±\pm 0.0362.484 ±\pm 0.0372.482 ±\pm 0.0382.486 ±\pm 0.035
SynthID2.009 ±\pm 0.0242.016 ±\pm 0.0242.003 ±\pm 0.0262.022 ±\pm 0.0262.018 ±\pm 0.026

For all kk, the log-perplexity of our method closely matches that of Base, confirming that generation quality is preserved under our acceleration.

Thank you for the detailed responses and additional experiments. The detection-time measurements show that detection cost is essentially unchanged across k, and the log-perplexity results, together with Theorem 3.1, show that text quality is preserved. These address my concerns on W2 and W3. I also acknowledge the quantified trade-off and the concrete recommendation for the choice of k.

However, my concern about the speed–detectability trade-off (W1) remains. The long-form experiment shows that the gap to k=1 shrinks as the text grows from 200 to 600 tokens, but this is largely expected: TPR saturates for every k once enough tokens are observed, so the result does not show that the per-token loss of watermark signal is reduced. The loss remains at short lengths, where detection is hardest. A comparison in terms of the additional tokens required to match the TPR of k=1 would be more informative.

The same loss is also visible under token edits. In Figure 9, k=2 stays close to k=1, but the gap for k=4 becomes noticeably larger under substitution and deletion than in the clean setting, and k=3, which the response recommends when more acceleration is desired, is not reported in Figure 9 or Table 8. In addition, Table 8 shows decreases in signal retention for Gumbel-max whose confidence intervals do not overlap (e.g., deletion at ρ=0.2: 0.528, 0.493, 0.492 for k=1, 2, 4), which is not fully consistent with the claim of no robustness loss. Taken together, the setting in which detectability is reliably preserved appears to be k=2, where the acceleration is modest; with the EAGLE-style drafter, the response itself notes that most of the throughput gain comes from the lighter drafter and that the tree adds up to 1.18× on top.

Overall, I acknowledge the additional experiments and the improved evidence on detection cost and text quality. However, the remaining concern about whether the achievable speedup justifies the loss of detectability, particularly for short or edited texts, prevents me from raising my score.

AuthorsOpenReview ↗

Clarification on the Remaining Concern

Thank you for the follow-up, and we are glad that our responses have addressed your concerns on detection cost (W2) and text quality (W3).

On the remaining trade-off (W1). We acknowledge that our method has a limitation for short texts at larger kk, where a detectability gap remains. However, we believe this limitation does not negate the contribution of our work, which is two-fold:

  • Acceleration. Vocabulary partitioning provably improves sampling efficiency and throughput over single-sequence decoding for any partition and any drafter (Thms. 3.2–3.3), without additional draft models.
  • Detectability under multi-branch drafting. Vocabulary partitioning prevents severe detection loss: without it, tree-based watermarked decoding suffers from (k+1)(k+1)-way source ambiguity, and detection degrades sharply, as shown in our ablation. Partitioning decreases this ambiguity to 2 and restores detectability. For the same reason, the EAGLE head would also suffer severe detection loss without partitioning. With partitioning, its TPR at k=2k=2 is no lower than Seq.

Neither contribution depends on short texts at large kk. That setting only determines how kk should be chosen: for short texts, a small kk is recommended, while for long-form generation, where acceleration matters most, a larger kk provides additional speedup with almost no loss in detectability.

As suggested, we will also include k=3k=3 in the robustness experiments in the revised version.

In short, we acknowledge this limitation of our method, but we do not believe it diminishes either of these two contributions.

Reviewer_prDVOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a tree-based speculative decoding framework to accelerate LLM watermark generation. The key idea is to deterministically partition the vocabulary into disjoint subsets. The authors theoretically prove that the method preserves the target model's output distribution. Experiments with Gumbel-max and SynthID watermarks demonstrate improved generation throughput with largely preserved detection performance.

Critical strengths

1.Interesting and Practical Problem. The paper addresses an important challenge in accelerating watermarked LLM generation, where conventional tree-based speculative decoding is not compatible with LLM watermark generation.

2.Simple Design: The proposed vocabulary partitioning strategy provides an simple way to construct diverse draft branches and reducing the ambiguity of pseudorandom sources from k+1k+1 to 2.

3.The authors provide theoretical analysis establishing that the proposed method preserves the target model's output distribution

Critical weaknesses

1.Novelty: While the paper addresses an interesting problem, I have concerns about its novelty. The proposed framework largely builds upon existing tree-based speculative decoding and speculative sampling techniques. Specifically, the deterministic vocabulary partitioning is not new, it's already used in early watermark methods like KGW[1]. The overall approach appears to beincremental combination of existing techniques. I am not fully convinced that the proposed method and its workload constitutes a sufficiently substantial methodological advance.

2.Lack of Robustness Evaluation: The experimental evaluation mainly focuses on watermark detectability under clean generation settings, without considering adversarial attacks. The authors should evaluate it with watermark removal and forgery attacks, such as SIRA[2], DIPPER[3], and watermark stealing attack[4], and naive attack such as word delete/rephrasing to prove the effectiveness of its methods.

3.Practicality: Although the proposed method improves generation speed, it also leads to a noticeable degradation in watermark detection performance. For instance, the TPR of Gumbel-max on Llama decreases from 97.21% to 87.96% when the branching factor increases to k=4k=4. Although the authors discuss the associated trade-offs, practical deployment is also affected by factors such as the quality of the draft model, which making it difficult to achieve the theoretical upper bound in real-world scenarios. It remains unclear whether the achieved speedups justify the degradation in detection performance.

4.Limited Practical Efficiency Gains: The experimental results show a speedup ranging from approximately 1.05× to 1.22×. Even compared to the early time EAGLE work[5], which achieves approximately a 2× speedup, the acceleration is relatively limited. Meanwhile as mentioned in Appendix E.6, introduces additional structural constraints on speculative decoding, potentially limiting its compatibility with recent advances such as dynamic tree pruning.

[1] Kirchenbauer, John, et al. "A watermark for large language models." International conference on machine learning. PMLR, 2023.

[2]Cheng, Yixin, et al. "Revealing weaknesses in text watermarking through self-information rewrite attacks." ICML (2025).

[3]Krishna, Kalpesh, et al. "Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense." Advances in neural information processing systems 36 (2023): 27469-27500.

[4]Jovanović, Nikola, Robin Staab, and Martin Vechev. "Watermark stealing in large language models." ICML (2024).

[5]Li, Yuhui, et al. "Eagle: Speculative sampling requires rethinking feature uncertainty." arXiv preprint arXiv:2401.15077 (2024).

Questions for authors

Q1: Appendix C.4 proves maximum watermark strength by incorporating all pseudorandom variables, including those used for draft acceptance. However, this guarantee does not necessarily imply that the proposed detector can effectively recover the watermark signal. For example, when vocabulary partitions become highly concentrated or nearly deterministic, draft tokens may depend primarily on pseudorandom acceptance decisions rather than the underlying watermark sampling variables. In such cases, the theoretical watermark strength can remain maximal while the Gumbel-max detection statistics become weakly informative. Can the authors provide a theoretical characterization or lower bound on the effective detection signal under vocabulary partitioning, rather than relying solely on the maximum watermark strength guarantee? In particular, how does this quantity depend on the branching factor and the entropy of the partitioned draft distributions?

Others see weakness. I am willing to revise my score based on the authors' response.

[1]Hu, Zhengmian, and Heng Huang. "Inevitable trade-off between watermark strength and speculative sampling efficiency for language models." Advances in Neural Information Processing Systems 37 (2024): 55370-55402.

9 comments
AuthorsOpenReview ↗

Response to Reviewer prDV (Part 1)

W1. Novelty: “Deterministic vocabulary partitioning is not new (KGW)”

Thank you for raising this point. Splitting the vocabulary into subsets is a generic operation that also appears in KGW. Our contribution, however, lies in how we use this operation to build a tree-based decoding mechanism for unbiased watermarking, which, to our knowledge, has not been explored in prior work. The connection to KGW is limited to the fact that both split the vocabulary. We clarify the differences in the following two points:

1. Our vocabulary partitioning plays a fundamentally different role from that in KGW.

  • In KGW, the partition is the watermark: sampling is biased toward a green list. In our method, the partition is only a component of tree-based decoding; the watermark itself comes from any unbiased decoder S\mathcal S (e.g., Gumbel-max, SynthID).
  • KGW changes the output distribution. Our method preserves the target distribution PP exactly (Thm. 3.1).
  • KGW treats the subsets asymmetrically (green vs. red). We treat all kk subsets symmetrically, with one draft branch per subset.

2. Our vocabulary partitioning achieves two important properties that do not arise in KGW.

  • Reduced pseudorandomness ambiguity. Because the subsets are disjoint and recoverable from the prefix, each observed token identifies its only possible draft branch. This reduces the candidate sources from k+1k+1 to 22.
  • Provably improved sampling efficiency. For any partition, Ak≥A1A_k\ge A_1 (Thm. 3.2), and refining a partition never reduces acceptance (Thm. 3.3). This requires no additional draft model and holds even without watermarking (App. E.4).

Importantly, a simple combination does not work. Combining tree-based speculative decoding with watermarking without our partition is exactly the k+1k+1 PRs ablation in Table 1: SynthID TPR collapses to 4040–50%50\% at k=4k=4, compared with 8686–90%90\% with our partition. Prior work on watermarking with speculative decoding [1, 3, 4] is restricted to single-sequence drafts, and our vocabulary partition is what makes tree-based drafts usable for watermark generation.

Thus, our method is not a simple incremental combination of speculative decoding and KGW’s partitioning. We will add this comparison to the related-work section.

AuthorsOpenReview ↗

Response to Reviewer prDV (Part 2)

W2. Robustness evaluation

Thank you for this suggestion. Robustness is largely inherited from the underlying watermark and detector. Robustness to text modifications is mainly determined by the watermark scheme and its detection method. Our work proposes neither a new watermark nor a new detector. Instead, it enables tree-based speculative decoding for existing unbiased watermarks, and we follow the detection method in [1]. The robustness of our method is therefore largely inherited from the chosen watermark and detector, which is why robustness was not the focus of our experiments.

For completeness, we show below that our method does not introduce additional robustness concerns.

1. Vocabulary partitioning does not degrade robustness. Under edits, a token loses its watermark signal when the pseudorandomness used to score it can no longer be recovered, i.e., when its context window is modified. Our method adds one pseudorandom component, the vocabulary partition, which can use the same context window as the watermark pseudorandomness, or a shorter one. In that case, a token’s partition can be lost only if its watermark pseudorandomness is also lost, so each token retains its signal under exactly the same condition as in single-sequence watermarked decoding.

2. Empirical verification. We apply random token substitution and deletion at rates ρ∈{0.1,0.2,0.3}\rho\in\{0.1,0.2,0.3\} (Llama, QA), with the partition sharing the watermark’s context window. To measure the watermark signal degradation against edits, we report signal retention: the fraction of the clean watermark signal (the mean per-token score in excess of its null expectation) that remains after the attack. Values are listed as k=1k=1 / 22 / 44 (recall that kk is the branching factor):

WatermarkAttackρ=0.1\rho=0.1ρ=0.2\rho=0.2ρ=0.3\rho=0.3
Gumbel-maxSubstitution0.674 / 0.677 / 0.6750.436 / 0.403 / 0.4300.263 / 0.237 / 0.224
Gumbel-maxDeletion0.737 / 0.723 / 0.7130.528 / 0.493 / 0.4920.338 / 0.309 / 0.327
SynthIDSubstitution0.701 / 0.706 / 0.7050.490 / 0.481 / 0.4990.328 / 0.327 / 0.334
SynthIDDeletion0.748 / 0.756 / 0.7580.559 / 0.564 / 0.5600.393 / 0.411 / 0.407

Signal retention is consistent across k=1,2,4k=1,2,4, confirming that vocabulary partitioning introduces no additional robustness loss. We have added the full results, including absolute TPR and confidence intervals, together with a more detailed discussion, to Appendix E.3.4.

We also evaluated paraphrasing attacks on Llama/QA, which rewrite the text and corrupt the context windows of many tokens. Consistent with point 1, signal retention remains similar across k=1/2/4k=1/2/4: 0.19/0.19/0.210.19/0.19/0.21 (Gumbel-max) and 0.28/0.30/0.300.28/0.30/0.30 (SynthID) under DIPPER [7] (T5-XXL; lexical diversity 60, order diversity 0; nucleus p=0.75p=0.75; 3-sentence windows with the prompt as context), and 0.08/0.11/0.110.08/0.11/0.11 and 0.17/0.20/0.210.17/0.20/0.21 under LLM rephrasing with Qwen3-32B.

3. Watermark stealing and spoofing. Stealing attacks such as [6] exploit key-dependent token preferences of the watermark scheme. Our partition is keyed by the same secret and context window as the watermark, treats all kk subsets symmetrically, and preserves the target distribution PP in expectation (Thm. 3.1). It therefore introduces no token-level bias for an attacker to learn beyond that of the underlying watermark. A full evaluation of stealing and spoofing attacks against unbiased watermarks is beyond the scope of this work, and we will add this discussion to the paper.

AuthorsOpenReview ↗

Response to Reviewer prDV (Part 3)

W3. Practicality of the efficiency–detectability trade-off

Thank you for this important question. We agree that our method involves a trade-off between efficiency and detectability. We would like to clarify that vocabulary partitioning is what makes tree-based watermark generation usable: it removes the dominant source of detectability loss, and the branching factor kk turns the remaining trade-off into a choice for the deployer.

1. Where the trade-off comes from. Two effects of kk should be distinguished:

  • Source ambiguity (what we improved). Without partitioning, the detector faces k+1k+1 candidate pseudorandom sources, and detection degrades severely (SynthID TPR falls to 4040–50%50\% at k=4k=4; Table 1). Vocabulary partitioning removes this effect by reducing the candidate sources to 22.
  • Entropy redistribution (what remains). Restricting each branch to a subset concentrates the branch distributions, which may weaken the per-token signal (Sec. 3.3; quantified in our answer to Q1 below). In the revised version, we now state this trade-off explicitly in Sec. 3.3.

2. The example you raise. Gumbel-max on Llama/QA is our worst case among all 12 settings. The full picture (Tables 1 and 3) is:

Seqk=2k=2k=3k=3k=4k=4
Throughput (tokens/s)68.874.1 (1.08×)76.2 (1.11×)79.1 (1.15×)
TPR, ours97.2193.1790.5187.96
TPR, tree without partition–88.3081.5777.45

Three observations follow. (i) At every kk, our method is far more detectable than a tree without partition, so it strictly improves the efficiency–detectability frontier of tree-based watermark generation. (ii) k=4k=4 is the most aggressive point: going from k=3k=3 to k=4k=4 adds only 1.04×1.04\times throughput for 2.52.5 pp TPR, so we do not recommend k=4k=4 for short texts. (iii) k=1k=1 remains available, so a deployer who cannot afford any TPR change loses nothing by adopting our framework.

3. Guidance for choosing kk. Across all 12 settings (Tables 1, 3, and 5):

  • k=2k=2 improves AATPS by 13.613.6–20.4%20.4\%, with a TPR decrease of at most 4.04.0 pp (median 1.21.2 pp);
  • k=3k=3 improves AATPS by 22.222.2–31.3%31.3\%, with a TPR decrease of at most 6.76.7 pp (median 2.62.6 pp).

We recommend k=2k=2 when detectability is the priority (e.g., short texts), and k=3k=3 when more acceleration is desired, especially for long-form generation. Given a detectability floor, a practitioner can select the largest kk that meets it on a small held-out set.

4. When the trade-off is favorable.

  • Long-form generation. Since TPR increases with text length for every kk, the gap between k≥2k\ge2 and k=1k=1 shrinks as texts grow longer. In a new experiment on OEG with the Llama pair, the gap between k=4k=4 and k=1k=1 shrinks from 4.14.1 to 0.30.3 pp (Gumbel-max) and from 4.24.2 to 0.20.2 pp (SynthID) as the length increases from 200200 to 600600 tokens, while the throughput gain is maintained (1.051.05–1.17×1.17\times over Seq at 600600 tokens). Long-form generation is also where acceleration saves the most absolute time.
TPR@FPR$=1%$n=200n=200n=400n=400n=600n=600
Gumbel-max, k=1/2/4k=1/2/497.6 / 96.3 / 93.598.9 / 97.9 / 97.498.9 / 98.8 / 98.6
SynthID, k=1/2/4k=1/2/495.7 / 93.1 / 91.599.0 / 98.7 / 98.199.6 / 99.5 / 99.4
  • Dependence on drafter quality. You note that practical speedups depend on the quality of the draft model. The relative gain from our tree is similar for two very different drafters: 13.613.6–37.4%37.4\% AATPS with the standalone drafters (Table 3) and 1212–30%30\% with an EAGLE head (Table 6). Detectability with the EAGLE head is also comparable to, or higher than, that with the standalone drafter (Table 7). The benefit of our method therefore does not hinge on a particular drafter.
Reviewer_YpMoOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper extends draft-and-verify speculative decoding to a tree structure for watermarked LLM generation. A deterministic, prefix-dependent vocabulary partition splits the vocabulary into k disjoint subsets at each node, sampling one draft token per subset under independent pseudorandomness. This yields diverse drafts (R1), preserves the target distribution (R2), and cuts source ambiguity from k+1 to 2 (R3). The paper proves unbiasedness, improved sampling efficiency, and a refinement result, and explains detectability changes via entropy redistribution. Experiments on OPT/Llama/Qwen pairs with Gumbel-max and SynthID show 1.05–1.22× throughput over single-sequence speculation (up to 1.92× with an EAGLE head) with largely preserved TPR@FPR=1%.

Critical strengths
  1. The paper is well-written and easy to follow. Requirements R1–R4 are stated up front, Figure 1 makes the sequence-vs-tree contrast immediately legible, and each section maps onto one requirement. The algorithms are implementable from the text, notation is consistent, and limitations (e.g., the refinement condition) are stated where they arise rather than buried.

  2. The proposed watermark scheme is neat and well motivated. The partition solves the core difficulty — independent branch pseudorandomness creates detection ambiguity — with one simple idea: make branch membership observable from the token itself. The ablation in Table 1 shows exactly why it matters: without it, SynthID TPR collapses to 40–50% at k=4; with it, TPR stays at 86–90%. The reduction is architecture-independent, which is why EAGLE works.

  3. The theoretical guarantees are sound and sufficient. Unbiasedness, A_k ≥ A_1, and refinement monotonicity are the right properties, and Remark 3.1 correctly notes that arbitrary partitions need not be monotone. Theorem C.1 closes the gap between analysis and implementation by showing pseudorandom acceptance preserves maximum watermark strength without affecting unbiasedness or efficiency.

Critical weaknesses
  1. Detectability decreases, and the paper's entropy analysis shows this is structural. TPR drops with k: Gumbel-max QA 94.5–97.5% (k=1) → 87.96–95.04% (k=4); SynthID drops further (Llama QA 92.36% → 86.17%). The entropy-redistribution argument explains why — partitioning concentrates branch distributions, weakening the signal for unbiased watermarks — but the paper does not treat this as the efficiency–detectability trade-off it is. A deployer choosing k has no guidance on maximizing throughput subject to a detectability floor.

  2. Only two unbiased watermarks are evaluated. Gumbel-max and SynthID share the maximum-strength property the theory relies on, and biased schemes (KGW, Unigram) are deferred to future work. The branch-identification argument is watermark-agnostic, but the entropy argument is framed for unbiased schemes, and it is unclear whether it transfers. The generality claim is unsupported without at least a discussion or one biased-watermark experiment.

  3. Detection is evaluated at a single length. TPR is reported at 200 tokens on two tasks, without varying length, without score distributions (so it is unclear whether the loss is a mean shift or a variance change), and without attacks. The per-prefix entropy gap is not tied to end-to-end detection.

Questions for authors
  1. Can the entropy analysis predict TPR as a function of k and L, or is k necessarily chosen empirically?
  2. How does the framework behave with a biased watermark such as KGW or other unbiased watermarks? A short discussion or a single experiment would clarify scope.
  3. What is detection loss as a function of output length — a constant offset or compounding with k?
  4. How much of the EAGLE speedup is from the tree structure versus the cheaper drafter? EAGLE at k=1 versus k=2 would isolate it.
3 comments
AuthorsOpenReview ↗

Response to Reviewer YpMo (Part 1)

W1&Q1: Trade-off and the choice of kk

Thank you for these insightful comments. In short, the entropy analysis alone cannot predict TPR as a function of kk, so we choose kk empirically; below we clarify the trade-off, provide a more precise characterization of the per-token signal, and give empirical guidance for choosing kk.

1. Clarification of the trade-off. Two effects of the branching factor kk should be distinguished:

  • Source ambiguity (what we improved). Without partitioning, the detector faces k+1k+1 candidate pseudorandom sources, and detection degrades severely (SynthID TPR falls to 4040–50%50\% at k=4k=4; Table 1). This is the source-ambiguity problem that arises when each branch uses its own pseudorandomness, as in a naive tree extension of watermarked speculative sampling (the k+1k+1 PRs ablation in Table 1). In our construction, vocabulary partitioning removes this effect by reducing the candidate sources to 22.
  • Entropy redistribution (what remains). Restricting each branch to a subset concentrates the branch distributions, which may weaken the per-token signal (Sec. 3.3). In the revised version, we now state this trade-off explicitly in Sec. 3.3.

2. Guidance for choosing kk. To better characterize the effect of kk, we derive the expected per-token detection score sˉk\bar s_k for Gumbel-max (definitions and proof in the new App. C.5):

sˉk=∑i=1k∑w∈Wiπi(w)κ(Q(i)(w))+Zk∑w∈WP(k)(w)κ(P(k)(w)),\bar s_k=\sum_{i=1}^{k}\sum_{w\in\mathcal W_i} \pi_i(w)\kappa\big(Q^{(i)}(w)\big) + Z_k\sum_{w\in\mathcal W}P^{(k)}(w)\kappa\big(P^{(k)}(w)\big),

where the first term corresponds to accepted draft tokens and the second to tokens from the residual. Here, πi(w)\pi_i(w) is the probability that ww is accepted from branch ii, ZkZ_k is the probability that the token is sampled from the residual P(k)P^{(k)}, and κ(q)\kappa(q) is the expected score of a token sampled with probability qq, which decreases in qq and equals the null expectation 11 when q=1q=1 (no signal). This expression shows how the signal depends on kk and on the partitioned distributions:

  • Weaker signal per accepted draft token. Since Q(i)(w)=Q(w)/αi≥Q(w)Q^{(i)}(w)=Q(w)/\alpha_i\ge Q(w), each accepted draft token carries weakly less signal than under the unpartitioned draft QQ. If a branch distribution is nearly deterministic, κ→1\kappa\to1 and tokens accepted from that branch carry almost no signal.
  • More tokens accepted from drafts. At the same time, partitioning increases the acceptance probability (Thm. 3.2), which shifts probability mass from the second term (tokens from the residual) to the first term (accepted draft tokens). Since the two sources generally carry different per-token signals, the net effect on sˉk\bar s_k depends on which source carries the stronger signal for the given PP and QQ, and can therefore go either way, consistent with Fig. 4.

Lower bound in terms of entropy. For Gumbel-max, κ\kappa has the closed form κ(q)=H1/q=ψ(1+1/q)+γ\kappa(q)=H_{1/q}=\psi(1+1/q)+\gamma (the generalized harmonic number), which satisfies κ(q)≥1+(π2/6−1)log⁡(1/q)\kappa(q)\ge 1+(\pi^2/6-1)\log(1/q), with equality at q=1q=1 (following [4]). Hence

sˉk−1≥(π26−1)[∑i=1k∑w∈Wiπi(w)log⁡1Q(i)(w)+ZkEnt(P(k))].\bar s_k-1 \ge \Big(\frac{\pi^2}{6}-1\Big)\Big[\sum_{i=1}^{k}\sum_{w\in\mathcal W_i}\pi_i(w)\log\frac{1}{Q^{(i)}(w)} + Z_k\mathrm{Ent}\big(P^{(k)}\big)\Big].

This makes the dependence on the partitioned distributions explicit: the per-token signal is lower-bounded by the acceptance-weighted log-loss of the branch distributions Q(i)Q^{(i)} plus the entropy of the residual. This is the quantitative counterpart of the entropy argument in Sec. 3.3.

Regarding LL, this expression applies to every tree level and does not depend on LL; LL only affects the fraction of bonus tokens, which are sampled from PP and whose signal does not depend on kk.

Why kk is chosen empirically. However, as shown in [3], detection power is not determined by the expected per-token score or entropy alone; it depends on the full next-token distributions and the score function. We therefore do not derive a TPR guarantee, and we choose kk empirically. Across all 12 settings (Tables 1, 3, and 5):

  • k=2k=2 improves AATPS by 13.613.6–20.4%20.4\%, with a TPR decrease of at most 4.04.0 pp (median 1.21.2 pp);
  • k=3k=3 improves AATPS by 22.222.2–31.3%31.3\%, with a TPR decrease of at most 6.76.7 pp (median 2.62.6 pp).

Given a detectability floor, a practitioner can select the largest kk that meets it on a small held-out set. Based on our results, we recommend k=2k=2 when detectability is the priority (e.g., short texts) and k=3k=3 when more acceleration is desired, especially for long-form generation. More details on when the trade-off is favorable, including new results on detection at different text lengths, are discussed in our response to Reviewer prDV (W3).

AuthorsOpenReview ↗

Response to Reviewer YpMo (Part 2)

W2&Q2: Scope of watermarks

Thank you for this question. Please find below our clarification on the scope of watermarks considered in our work.

1. Why we focus on unbiased watermarks. Unbiased watermarks guarantee that the output distribution of the language model is preserved, so watermarking does not degrade generation quality. They are also the watermarks adopted by major production LLMs: Google’s Gemini uses SynthID-Text [1] (link), Anthropic’s Claude uses a version of SynthID-Text (link), and OpenAI has begun rolling out textGrain [2] in ChatGPT and Codex in the EU (link), all of which are unbiased. Our framework applies to the entire class of unbiased watermarks, so it covers the watermarks most relevant to practical deployment.

2. Our main results rely only on unbiasedness, not on maximum watermark strength.

  • Thms. 3.1–3.3 (unbiasedness and improved sampling efficiency) require only that the decoder S\mathcal S be unbiased, i.e., Eζ[S(Q,ζ)]=Q\mathbb E_\zeta[\mathcal S(Q,\zeta)]=Q.
  • The reduction of source ambiguity from k+1k+1 to 22 follows from the disjoint supports of the partition and does not depend on the specific watermark at all.
  • Maximum watermark strength appears only in App. C.4 (Thm. C.1) as a complementary result: it shows that pseudorandom acceptance preserves the maximum strength of the underlying watermark when that watermark has this property. It is not required by our main theorems.
  • Our experiments already include a watermark without maximum strength: SynthID with m=30m=30 tournament rounds (our setting) attains maximum strength only in the limit m→∞m\to\infty (App. B.1). The SynthID results therefore show that our method works without the maximum-strength property.

3. Biased watermarks. Our framework is designed for unbiased watermarks, and the role of vocabulary partitioning in resolving source ambiguity may not be necessary for biased watermarks. For example, for KGW and Unigram, one way to apply our framework is to use the watermarked distribution PwmP_{\text{wm}} directly as the target, since the watermark signal lies entirely in this distribution. Any distribution-preserving decoder, including ours, then samples exactly from PwmP_{\text{wm}}. In this use, green-list detection does not depend on which branch produced each token, so the source-ambiguity problem that motivates vocabulary partitioning does not arise. Nevertheless, partitioning still provides our efficiency guarantees (Thms. 3.2–3.3), although the sampling efficiency is now determined by PwmP_{\text{wm}} and QwmQ_{\text{wm}} rather than by PP and QQ. We will add this discussion to the paper.

AuthorsOpenReview ↗

Response to Reviewer YpMo (Part 3)

W3&Q3: Detection

Thank you for these constructive suggestions. We have conducted additional experiments on detection length, score distributions, and robustness to text edits, and we clarify the role of our entropy analysis. Please find our detailed responses below.

1. Detection length (Q3). We conducted complementary experiments on detection at various lengths (OEG, Llama models; results at 200200 tokens are from Table 5):

TPR@FPR$=1%$n=50n=50n=100n=100n=200n=200n=400n=400n=600n=600
Gumbel-max, k=1/2/4k=1/2/472.2 / 70.0 / 62.792.1 / 88.1 / 81.297.6 / 96.3 / 93.598.9 / 97.9 / 97.498.9 / 98.8 / 98.6
SynthID, k=1/2/4k=1/2/459.1 / 56.3 / 44.984.1 / 79.2 / 72.795.7 / 93.1 / 91.599.0 / 98.7 / 98.199.6 / 99.5 / 99.4

The loss is neither a constant offset nor compounding with kk. It is noticeable for short texts, especially at larger kk, but diminishes as the length increases, which makes our method particularly suitable for long-form generation, while a small kk (e.g., k=2k=2) is preferable for short texts.

2. Score distributions. To examine whether the detectability loss is a mean shift or a variance change, we additionally computed per-token detection scores:

  • Gumbel-max: −log⁡(1−yt)-\log(1-y_t);
  • SynthID: the gg-value averaged over the 3030 tournament layers.
Gumbel-max: meanGumbel-max: varianceSynthID: meanSynthID: variance
k=1k=11.8213.200.55100.0095
k=2k=21.7802.820.55130.0093
k=4k=41.6772.680.54490.0091
Unwatermarked1.0001.000.50140.0083

The loss mainly reflects a mean shift. For SynthID, the mean decreases at k=4k=4 while the variance stays nearly constant. For Gumbel-max, the variance also decreases, which partially offsets the mean shift.

3. Attacks. We added experiments with random token substitution and deletion at rates of 1010–30%30\% (new App. E.3.4). The fraction of watermark signal retained after editing is consistent across k=1,2,4k=1,2,4, showing that vocabulary partitioning introduces no additional robustness loss (see our response to Reviewer prDV, W2).

4. Entropy gap and end-to-end detection. The entropy analysis in Sec. 3.3 is intended as a qualitative explanation rather than a quantitative predictor of detection. As shown in [3], detection power is not determined by entropy alone: it depends on the full next-token distributions and the score function, and is governed by structural properties such as the maximum token probability (Δ\Delta-regularity), which lower-bounds entropy. Entropy is therefore closely related to the watermark signal and helps explain the trend in Tables 1 and 5, but it does not by itself yield an end-to-end characterization of detection.


Q4: How much of the EAGLE speedup comes from the tree structure versus the cheaper drafter?

Thank you for this suggestion. We have added EAGLE at k=1k=1 to Table 6. The new results separate the two contributions:

  • Drafter. Replacing the standalone Qwen3-0.6B drafter with the EAGLE head at k=1k=1 improves throughput by 1.471.47–1.77×1.77\times, which accounts for most of the overall speedup, as expected from the much lighter drafter.
  • Tree structure. On top of the EAGLE head, the tree (k=2k=2–44) further improves AATPS by 1212–30%30\% and throughput by up to 1.18×1.18\times over EAGLE at k=1k=1, consistent with the gains observed with the standalone drafter.

Importantly, we would like to clarify the purpose of the EAGLE experiments: our framework is flexible in the choice of drafter, so the watermark generation process can benefit from efficient drafters such as EAGLE, whose lower drafting overhead broadens the practical use of our framework.


References

[1] Dathathri, Sumanth, et al. "Scalable watermarking for identifying large language model outputs." Nature 634.8035 (2024): 818-823.

[2] Li, Xiang, et al. "textGrain: Entropy-calibrated watermarking for language model text." URL https://www.alphaxiv.org/abs/2610.textgrain-entropy-calibrated-watermarking (2026).

[3] Li, Xiang, et al. "A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules." Annals of Statistics 53.1 (2025): 322.

[4] Aaronson, Scott. "Watermarking of large language models." Workshop on Large Language Models and Transformers, Simons Institute (2023).

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to AC and Reviewers

Dear AC and Reviewers,

Thank you for your time and constructive feedback. As the discussion period is ending on November 18, we would greatly appreciate it if you could let us know whether our responses have addressed your concerns. All revisions are highlighted in purple{\color{purple}\text{purple}} in the revised version, mostly in the appendix.

Summary of responses:


Reviewer YpMo

  • Choice of kk (W1, Q1): we made the trade-off explicit, characterized the per-token detection signal theoretically (App. C.5), and provided empirical guidance for choosing kk.
  • Scope of watermarks (W2, Q2): we clarified that our results rely only on unbiasedness and provided a brief discussion of biased watermarks.
  • Detection length, score distributions, and attacks (W3, Q3): new experiments are added as suggested.
  • EAGLE (Q4): the suggested ablation with EAGLE at k=1k=1 is added (Table 6).

Reviewer prDV

  • Novelty (W1): we clarified how our use of vocabulary partitioning differs from KGW.
  • Robustness (W2): we provided a theoretical argument and new experiments under text edits and paraphrasing (App. E.3.4).
  • Practicality (W3): we showed the practicality of our method with both existing (generation with an EAGLE-style drafter) and newly added (long-form generation) experiments, in which the speedup comes with little or no loss in detectability.
  • Effective detection signal (Q1): we derived the expected per-token detection score for Gumbel-max (App. C.5).
  • Efficiency gains (W4): we drew attention to our existing EAGLE results (Table 2 and App. E.3.3), where our framework benefits from efficient drafters and achieves higher efficiency gains, and clarified that the remaining gap to non-watermarked decoding stems from constraints inherent to watermarking.

Reviewer vJvV

  • Speedup vs. detectability (W1): we showed that the speedup justifies the detectability change in two settings, generation with an EAGLE-style drafter (existing results) and long-form generation (new experiments), where the loss in detectability is small or absent.
  • Detection speed (W2): a new experiment shows that detection time is unaffected.
  • Text quality (W3): new log-perplexity results confirm that quality is preserved, consistent with Thm. 3.1.

Thank you again for your time and effort.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.