TIDEmark: Joint Token Watermarking for Diffusion Language Models via Multi-Marginal Optimal Transport

Watermarks for autoregressive language models typically operate one token at a time. Diffusion language models (DLMs) instead generate text through successive steps that update multiple token positions in parallel. Many existing methods adapt side-information generation to DLMs while leaving the other watermarking components similar to their autoregressive counterparts. In this work, we exploit parallel token generation to watermark multiple tokens jointly, aiming to strengthen detection without changing their individual distributions. To construct a watermark over several token distributions at once, we leverage multi-marginal optimal transport and introduce TIDEmark (**T**ransport-based **I**nteraction for **D**istortion-free **E**mbedding of water**mark**s). TIDEmark coordinates token choices using token-pair watermark scores, and we prove an ideal distortion-free guarantee for the recorded token marginals. We make joint watermarking computationally tractable through a tree-structured interaction graph, combining belief propagation (BP) with the Sinkhorn algorithm for entropy-regularized transport. For fixed candidate-set sizes and a fixed number of side-information states, the computational complexity per solver pass scales linearly rather than exponentially with the number of jointly watermarked tokens, matching token-level optimal transport’s dependence on token count. Experiments on summarization, question answering, and code generation show that TIDEmark can strengthen detection. TIDEmark results suggest that when the watermark is applied can affect the balance between generation quality and watermark detection.