Research map / Large language models / Reasoning and chain of thought

Break the Trade-off Between Watermark Strength and Speculative Sampling Efficiency for Language Models

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Speculative decoding

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Revisits the watermark-speculative sampling trade-off with a KL-based watermark strength measure, derives Pareto curves for Gumbel-max and SynthID, and proposes pseudorandom draft-token acceptance that achieves maximal strength and maximal acceptance while improving detectability.

Problem

Watermarking LLM outputs with speculative sampling was shown to face an impossibility: higher watermark strength reduces acceptance rate. Prior strength definitions are binary, so intermediate trade-offs cannot be characterized.

Approach

Define watermark strength as expected KL divergence between watermarked and original token distributions (equal to entropy minus expected watermarked entropy, bounded by entropy of P), characterize the strength-efficiency Pareto frontier as a constrained optimization, and make the draft-token acceptance decision pseudorandom so the whole generation is a deterministic function of pseudorandom varia

Key results

• Pseudorandom acceptance keeps average accepted tokens per step close to standard speculative sampling for both Gumbel-max and SynthID.
• Our Ars-tau and Bayes-MLP detectors achieve higher TPR at 1% FPR with fewer tokens than Ars-Prior and Bayes-Prior for Gumbel-max and SynthID (m=30).
• Theory: the method is unbiased, attains maximal sampling efficiency 1-TV(Q,P), and maximal watermark strength Ent(P).

Surprising findings

• Gumbel-max and SynthID as m tends to infinity attain the same maximal strength, but SynthID with m=30 drops below Gumbel-max strength on Google's class curve.

Limitations

• Theory and main results apply only to unbiased degenerate watermarks.
• Detection gap remains relative to the oracle detector that always selects the correct statistic.
• Robustness to human edits not investigated.

Experimental setup

Datasets: ELI5 C4

Benchmarks: ELI5 C4

Metrics: AATPS TPR at FPR 1% PTT LOGPPL ROC AUC

Baselines: Standard Speculative Sampling Ars-Prior Bayes-Prior

Builds on: speculative sampling Gumbel-max watermark SynthID Hu et al. watermark speculative sampling trade-off

Closest papers by meaning

• Inevitable Trade-off between Watermark Strength and Speculative Sampling Efficiency for Language Models (NeurIPS 2024 · similarity 0.95)
• Watermarks in the Sand: Impossibility of Strong Watermarking for Language Models (ICML 2024 · similarity 0.91)
• Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach (NeurIPS 2025 · similarity 0.91)
• Unbiased Watermark for Large Language Models (ICLR 2024 · similarity 0.90)
• Black-Box Detection of Language Model Watermarks (ICLR 2025 · similarity 0.90)
• A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models (ICML 2024 · similarity 0.90)