Distortion-free watermarking enables reliable attribution of machine-generated text while preserving output distribution. However, existing methods operate independently on each generated token, making their detection capability fundamentally constrained by the entropy of the next-token distribution. We present Tandem Token WaterMark (TTMARK), a general pairwise watermarking framework that extends distortion-free watermarking from individual tokens to adjacent token pairs. By watermarking the joint distribution of consecutive tokens, TTMARK enlarges the effective watermarking alphabet from V to V2, allowing the detector to exploit both token entropy and conditional entropy while preserving distortion-freeness over the joint distribution. We further introduce a branch-isolating concatenated tandem generation algorithm that efficiently constructs the joint distribution in a single forward pass. Theoretically, we show that pairwise watermarking achieves better expected detection strength in low-entropy regimes. Extensive experiments across multiple language models, datasets, and three representative distortion-free watermarking schemes demonstrate that TTMARK consistently improves detectability without degrading generation quality, while also improving robustness to edits and substantially enhancing localized watermark detection.
Figures & tables
Figure 1: Overview of branch-isolating concatenated tandem generation. TTMark first forms a filtered set of candidate next tokens and evaluates their continuations in a single batched forward pass using a branch-isolating attention mask. The resulting conditional distributions are combined with the first-token probabilities to construct a joint two-token distribution, enabling efficient pairwise watermarking over adjacent tokens.
200 Tokens
400 Tokens
TPR@FPR=
Median p -value ↓
TPR@FPR=
Median p -value ↓
0.1% ↑
0.01% ↑
0.001% ↑
0.1% ↑
0.01% ↑
0.001% ↑
ENS-DiPmark
47.0%
32.8%
23.9%
1.89e-3
73.8%
61.2%
46.8%
1.63e-5
+ TTMark
68.3%
58.9%
47.2%
2.01e-5
94.5%
88.6%
81.7%
4.03e-10
SynthID-Text
71.8%
60.5%
50.3%
9.59e-6
92.9%
86.5%
80.1%
1.73e-9
+ TTMark
87.5%
79.5%
73.2%
5.79e-10
99.3%
98.5%
97.7%
8.25e-18
Table 1: Direct detection on C4 using Llama3.2-3B-Instruct. TTMark improves the detection power of all three underlying watermarking schemes, especially under stringent FPR constraints.
Figure 2: Cross-dataset direct detection performance on Llama3.2-3B-Instruct. Each panel reports TPR@FPR =0.1% for single-token watermarking and its tandem counterpart.
Figure 3: Effect of Top- p on detection performance for MMW Book Report using Llama3.2-3B-Instruct. Both tandem and single-token variants use Top- k=50 ; “Default” denotes the setting without Top- k truncation.
Average Token Counts
TPR@FPR=
Median p -value ↓
Seconds per 1k Tokens ↓
0.1% ↑
0.01% ↑
0.001% ↑
ENS-DiPmark
1.37
9%
2%
0%
1.86e-1
0.79
+ TTMark
1.93
18%
9%
2%
3.46e-2
0.80
SynthID-Text
1.39
21%
14%
8%
1.46e-2
0.86
+ TTMark
1.93
52%
36%
20%
7.96e-4
0.79
ENS-MCMark
1.38
26%
13%
5%
1.27e-2
0.87
Table 2: Direct detection under stricter sampling parameters on MMW Book Report using Qwen2.5-7B-Instruct. Generations use the recommended sampling parameters with Top- p=0.8 , Top- k=20 , and temperature 0.7 . Even when the effective candidate support is small, TTMark improves detection with comparable generation time.
Figure 4: Runtime of tandem generation as a function of the effective candidate support on MMW Book Report using Llama3.2-3B-Instruct. Measurements are taken with batch size 32. Branch-isolating generation keeps the overhead modest because all first-token branches are evaluated together, and memory bandwidth is the main bottleneck. The accelerated generation speed when m is small stems from a 50% reduction in watermarking function calls.
Rephrase
Back Translation
FPR=1% ↑
FPR=0.1% ↑
AUROC ↑
FPR=1% ↑
FPR=0.1% ↑
AUROC ↑
ENS-DiPmark
59.4%
34.6%
0.9320
55.0%
38.0%
0.9486
+ TTMark
69.8%
50.7%
0.9449
72.0%
51.8%
0.9532
SynthID-Text
72.2%
59.0%
0.9529
75.6%
60.0%
0.9646
+ TTMark
80.0%
72.3%
0.9570
83.1%
72.3%
0.9726
ENS-MCMark
75.5%
61.9%
0.9587
78.0%
64.9%
0.9687
Table 3: Robustness to rephrasing and back-translation on C4 using GPT5-Mini. The generation model is Llama3.2-3B-Instruct. Each attack edits 30% of the generated passage. TTMark improves detection after edits across all base watermarking schemes.
Llama3.2-3B-Instruct
Qwen2.5-7B-Instruct
FPR ↓
FNR ↓
F1 ↑
IoU ↑
FPR ↓
FNR ↓
F1 ↑
IoU ↑
ENS-DiPmark
0.000
0.543
0.627
0.351
0.010
0.567
0.600
0.330
+ TTMark
0.000
0.277
0.839
0.590
0.003
0.303
0.820
0.574
SynthID-Text
0.017
0.230
0.862
0.618
0.007
0.213
0.877
0.623
+ TTMark
0.010
0.050
0.969
0.785
0.013
0.063
0.961
0.787
ENS-MCMark
0.006
0.210
0.879
0.618
0.037
0.153
0.899
0.637
Table 4: Localized watermark detection. The protocol evaluates whether the detector can recover the watermarked span within a longer document. TTMark reduces false negatives and improves F1 and IoU on both model families.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Ablation of the empirical detector skip penalty β under edits. Moderate penalties balance alignment flexibility against over-selection of isolated high-scoring pairs.
Figure 6: Cross-dataset direct detection performance on Qwen2.5-7B-Instruct. Each panel reports TPR@FPR =0.1% for single-token watermarking and its tandem counterpart.
Figure 7: Cross-dataset direct detection performance on Mistral-7B-Instruct-v0.3. Each panel reports TPR@FPR =0.1% for single-token watermarking and its tandem counterpart.
Top-P
Top-K
Temperature
Qwen3 Series
0.95
20
0.6
Qwen2.5 Series
0.8
20
0.7
Llama3 Series
0.9
-
0.6
Appendix
Table 5: Representative stricter sampling parameters recommended by model families. These settings reduce decoding entropy and can substantially decrease the effective candidate support available for watermarking. The dash in the Top- k column indicates that no explicit Top- k truncation is recommended in that setting.
Text Summarization
Machine Translation
ROUGE-1
ROUGE-2
ROUGE-L
BERTScore
BLEU
BERTScore
No Watermark
0.3849
0.1465
0.2548
0.2733
21.30
0.8336
+ TTMark
0.3854
0.1473
0.2554
0.2738
21.69
0.8388
ENS-DiPmark
0.3855
0.1333
0.2432
0.2734
20.93
0.8332
+ TTMark
0.3846
0.1333
0.2430
0.2726
21.55
0.8375
SynthID-Text
0.3850
0.1471
0.2551
0.2735
20.95
0.8324
Appendix
Table 6: Generation quality under watermarking. The tandem variants preserve summarization and translation quality relative to the corresponding single-token watermarking schemes.
200 Tokens
400 Tokens
TPR@FPR=
Median p -value ↓
TPR@FPR=
Median p -value ↓
0.1% ↑
0.01% ↑
0.001% ↑
0.1% ↑
0.01% ↑
0.001% ↑
ENS-DiPmark
47.0%
32.8%
23.9%
1.89e-3
73.8%
61.2%
46.8%
1.63e-5
+ TTMark 2-Token
68.3%
58.9%
47.2%
2.01e-5
94.5%
88.6%
81.7%
4.03e-10
+ TTMark 3-Token
77.0%
70.8%
63.0%
1.43e-7
98.7%
96.2%
93.0%
6.42e-14
SynthID-Text
71.8%
60.5%
50.3%
9.59e-6
92.9%
86.5%
80.1%
1.73e-9
Appendix
Table 7: Direct detection when extending TTMark from two-token blocks to three-token blocks on C4 using Llama3.2-3B-Instruct. Longer blocks further improve detection, especially at stringent false-positive rates.
Leading multi-bit watermarking methods for language models encode messages by biasing the model's next-token probabilities, creating a trade-off between message recovery and text quality. Their decoders typically return the highest-scoring candidate from accumulated token-level evidence, without a certified abstention rule that bounds the probability of outputting an incorrect message. We introduce CertMark, a distribution-preserving multi-bit watermark with certified decoding. Rather than modifying probabilities, CertMark uses the embedded message to seed an exact Gumbel-max sampler, thereby preserving the model's original sampling distribution. We propose two scalable decoders: a model-agnostic, text-only decoder and a model-aware variant that leverages the original next-token distributions for stronger recovery. Both support certified abstention with mathematical bounds on the probability of returning an incorrect message. Across text completion, summarization, and story generation, CertMark matches the perplexity of unwatermarked text while reliably recovering multi-bit messages. The model-aware decoder further achieves higher bit accuracy than probability-biasing baselines. Our code is publicly available at https://github.com/Batorskq/CertMark.
Paweł Batorski, Przemysław Spurek, Paul Swoboda
Heinrich Heine University Düsseldorf · Jagiellonian University · IDEAS Research Institute
We introduce Tokenization-Invariant Watermarking (TI-WM), a method that embeds a watermark during token generation but keys and scores it on canonicalized UTF-8 bytes. The detector does not invoke the tokenizer. Canonicalizer-preserving edits leave its score unchanged; other localized canonical-byte edits affect a bounded number of scoring windows. Across three fixed keys and 128 prompts per key and model, a deterministic white-box attack at a 5% word-edit budget leaves mean attacked-AUC 0.530 on Qwen3-8B and 0.664 on Gemma 4 E4B, compared with 0.410 and 0.489 for Unigram with detection-side deletion. These operating points are not jointly matched on quality and clean detectability. Bias sweeps show model-dependent distortion costs, and shared-rule controls support a locality interpretation without establishing a unique advantage of bytes. Visible insertion outside the canonicalizer's deletion set defeats the default design. Alphabetic filtering closes that channel but does not resolve source shift or calibrated detection power. TI-WM thus provides a concrete construction with local scoring guarantees and measured attack-ranking gains, not a general robustness or low-false-positive-rate deployment guarantee.
Masked-diffusion language models fill in masked positions in parallel and in no fixed order. Most practical text watermarks assume left-to-right generation. They key each token to the tokens before it, and in a diffusion model those tokens may still be masked. A fixed green list needs no such context, but it favors the same tokens at every position, so these tokens appear more often in watermarked text. An attacker who compares token frequencies in watermarked and unwatermarked text can recover the list and forge text that the provider's own detector accepts. We present TANGO, a watermark for masked-diffusion language models that keys each new token to a nearby token that is already unmasked. A secret key splits the vocabulary into color classes, and TANGO biases the new token toward a color determined by the key and the nearby token's color. The watermark is therefore embedded in pairs of tokens. Because the favored color changes from position to position, token frequencies stay much closer to those of unwatermarked text than under a fixed green list. Detection needs only the text and the key, and it does not assume any unmasking order. On two masked-diffusion models, TANGO detects nearly all unedited watermarked texts and most edited ones, and frequency attacks that forge the fixed green list fail against it.