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 $V^2$, 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.