SeqMark: Semantic Differentiation for Watermarking Low-Entropy Text

by Nghia T. Le (in collaboration with Alan Ritter and Kartik Goyal)

Table of Content:

• Introduction
• Token-level Watermarking and Text Entropy
• Sequence-level Watermarking: Region Collapse and SeqMark
• Further Discussion
• Citation

Introduction

The proliferation of AI-generated content has created an urgent need for digital watermarking approaches that can robustly track provenance (Srinivasan et al.). There have been various efforts to create robust and imperceptible text watermarking methods (Kirchenbauer et al., Aaronson, see survey by Liu et al.). Major LLM providers have also begun implementing watermarking in production (SynthID, Claude text watermarking). Nonetheless, these approaches often struggle with watermarking low-entropy constrained generation tasks such as machine translation, code summarization, and code generation, due to the limited randomness available at each token sampling step for these tasks. Researchers have tackled this issue by improving token-level watermarking for code generation (Lee et al., Lu et al.) and translation (Takezawa et al.). Interestingly, we find that these approaches still underperform sequence-level watermarking (Hou et al.), which we hypothesize is due to entropy under-utilization in constrained generation tasks. Nonetheless, sequence-level watermarking algorithms suffer from region collapse, a problem where the model is often forced to choose between generating high-quality but un-watermarked text or low-quality watermarked text. We thus introduce SeqMark, a sequence-level watermarking algorithm that tackles the region collapse problem by isolating and differentiating the high-quality output space. We observe that SeqMark improves text watermarking performance across different low-entropy scenarios.

Token-level Watermarking and Text Entropy

Popular LM watermarking algorithms often embed watermark signals at the token level, relying on each token step having high enough entropy (i.e., randomness) to watermark without major degradation in text quality. For constrained generation tasks, this is problematic: there are much fewer token steps with high-enough entropy for watermarking. Consider the following example where we translate a German sentence into English:

German: New York ist als die Stadt bekannt, die niemals schläft

English: New York is known as the City That Never Sleeps

In this example, the token steps with higher entropy are highlighted with a darker shade (we compute token entropy at step \(i\): \(H(x_i | x_{\lt i}) = -\sum_{v\in V} P(x_i\mid x_{\lt i}; \theta) \log P(x_i\mid x_{\lt i}; \theta)\) over all token \(v\) in vocabulary \(V\) with translation fine-tuned language model ALMA-7B; we also show top-10 most probable tokens and their probabilities). We can see that a few tokens have notable entropy (“New”, “known”, “That”, “eps”), with the first token having the highest value, while the rest are essentially deterministic. Token-level watermarking approaches are therefore constrained to these few tokens high entropy tokens. In contrast, consider the following possible translation sequences:

New York is known as the City That Never Sleeps. 
New York City is known as the city that never sleeps.
New York is famous as the city that never sleeps.
The reputation of NYC is the city that never sleeps
New York is known for being the city that never sleeps.
The city that never sleeps, that’s New York City.
New York is the city that never sleeps.
New York is famous as the city that never sleeps.
NYC is known as the city that never sleeps
New York is well-known for being the city that never sleeps.
NYC is often regarded as a city that never sleeps.
New York is famous for never sleeping.
...

Watermarking algorithms that utilize selection over the above set of (infinite) sequences would theoretically leverage more randomness for effective watermarking. We posit that this is where sequence-level watermarking algorithms like SemStamp have an advantage over token-level watermarking: the utilization of the (infinite) sequence embedding space allows for more randomness when watermarking constrained generation tasks. Empirically, in Figure 1 below we observe that sequence-level watermarking SemStamp (orange) achieves a higher Pareto frontier for higher-quality translations than the token-level algorithm KGW (blue):

However, it turns out that sequence-level text watermarking has a critical issue of its own when watermarking constrained generation tasks: region collapse.

Sequence-level Text Watermarking: Region Collapse and SeqMark

Sequence-level watermarking works by (1) partitioning the embedding space into accepted/valid and rejected/invalid regions, (2) generating and mapping candidate sequences onto the partitioned space (3) selecting the sequences that fall into the accepted regions. The underlying assumption for this method is that similar sequences share similar embeddings. This is problematic when it comes to constrained generation tasks: all the “high-quality” generations risk being partitioned into the invalid regions. For example, for machine translations, if all the correct translations fall into the invalid regions, the model is forced to choose between correct but un-watermarked sequences vs. incorrect but watermarked sequences (Figure 2). We call this problem Region Collapse.

To alleviate region collapse, our approach SeqMark (Figure 3) first isolates the manifold \(C\) of high-probable generations via sampling (i.e., sampling n candidate translations). We then seek a transformation \(f\) that minimizes the pairwise cosine similarities between the members of \(C\) while preserving their relative proximity. This is difficult to estimate in general and could be approximated by learning such a function via a neural network. We opt for a much simpler choice for \(f\): subtracting the sample mean from each member of \(C\).

We summarize the main results in Table 1 below. Across four different constrained generation tasks (sentence translation, paragraph translation, summarization, and code generation), we observe that SeqMark achieves significant watermark detection improvement over previous approaches, with no degradation in text quality.

Table 1. Utility and watermark detection performance across different tasks. Each entry reports task accuracy / watermark detection performance.

Further Discussion

In this blog post, we introduce SeqMark, a sequence-level text watermarking algorithm for constrained generation. We demonstrate that for these types of tasks, sequence-level watermarking is more effective than token-level watermarking, yet still affected by the problem of region collapse. SeqMark successfully alleviates this issue and shows significant watermark detection accuracy across different constrained generation tasks.

Despite its effectiveness, the development of SeqMark raises several open questions:

• Computational Efficiency: sequence-level watermarking algorithms such as SeqMark are less efficient than token-level watermarking, due to the sampling of candidate sequences step. How to improve the computational efficiency of sequence-level watermarking is an open question.

• Approximation and Transformation of the High-quality Manifold: Currently, SeqMark approximates this manifold by sampling candidate sequences, and transforms it by subtracting their embeddings from the mean embedding. One limitation of this approach is that it requires saving the mean embeddings for the detection step, which could be cumbersome to store. In general, SeqMark would benefit from approaches that improve the approximation and transformation of this high-quality subspace.

We wish to explore these questions further in future work.

Citation

Please cite this work as:

Le, Nghia T., Ritter, Alan and Goyal, Kartik. "Semantic Differentiation for Tackling Challenges in Watermarking Low-Entropy Constrained Generation Outputs",
Conference on Language Modeling, Oct 2026.

Or use the BibTeX citation:

@inproceedings{le2026seqmark,
  title={Semantic Differentiation for Tackling Challenges in Watermarking Low-Entropy Constrained Generation Outputs},
  author={Le, Nghia T. and Ritter, Alan and Goyal, Kartik},
  booktitle={Conference on Language Modeling (COLM)},
  year={2026},
  url={https://arxiv.org/abs/2601.11629}
}