Semantic Differentiation for Tackling Challenges in Watermarking Low-Entropy Constrained Generation Outputs
Nghia T. Le, Alan Ritter, & Kartik Goyal · 2026
Read Semantic Differentiation for Tackling Challenges in Watermarking Low-Entropy Constrained Generation Outputs by Nghia T. Le, Alan Ritter, & Kartik Goyal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11629.txt.
Introduction
Nghia Le, Alan Ritter, and Kartik Goyal watermark low-entropy model outputs. Their 2026 preprint presents SeqMark, a sequence-level algorithm. Watermarking marks AI text so its origin can be checked. Current methods work well for open-ended generation tasks.
Constrained tasks have low-entropy output spaces to choose from. Code, forms, and short answers leave little room to hide marks. Standard watermarks prove inadequate in that tight space. SeqMark uses semantic differentiation at the sequence level. It balances output quality with watermark detectability. Imperceptibility, not standing out to readers, is the third goal. The balance matters where outputs must stay exact.
Catalog record
| CREATOR | Nghia T. Le, Alan Ritter, & Kartik Goyal |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-11629
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Semantic Differentiation for Tackling Challenges in Watermarking Low-Entropy Constrained Generation Outputs Nghia T. Le, Alan Ritter, & Kartik Goyal Abstract We demonstrate that while the current approaches for language model watermarking are effective for open-ended generation, they are inadequate at watermarking LM outputs for constrained generation tasks with low-entropy output spaces. Therefore, we devise SeqMark , a sequence-level watermarking algorithm with semantic differentiation that balances the output quality, watermark detectability, and imperceptibility. It improves on the shortcomings of the prevalent token-level watermarking algorithms that cause under-utilization of the sequence-level entropy available for constrained generation tasks. Moreover, we identify and improve upon a different failure mode we term region collapse , associated with prior sequence-level watermarking algorithms. This occurs because the pseudorandom partitioning of semantic space for watermarking in these approaches causes all high-probability outputs to collapse into either invalid or valid regions, leading to a trade-off in output quality and watermarking effectiveness. SeqMark instead, differentiates the high-probable output subspace and partitions it into valid and invalid regions, ensuring the even spread of high-quality outputs among all the regions. On various constrained generation tasks like machine translation, code generation, and abstractive summarization, SeqMark substantially improves watermark detection accuracy (up to 28% increase in F 1 ) while maintaining high generation quality. 1 1 1 Our code is available here . 1 Introduction As progress in language modeling leads to increasingly human-like automatic text generation, demand for tracing the provenance and life-cycle of digital text on the internet has soared. Questions around plagiarism ( 35 ) , copyright infringement ( 43 ) , veracity of text ( 2 ) , misinformation ( 11 ) , multi-agentic communication ( 27 ) , and many other legal and contractual frameworks require the ability to attribute text to its source. Language model watermarking – embedding a traceable digital marker in the language model’s distribution over language – has emerged as a potential solution to address this need. The seminal work on watermarking 18 modifies the logits produced over the vocabulary at each generation step from a language model to prefer or disprefer certain tokens. Much of the follow-up work ( 9 ; 42 ; 38 ) on this token-level watermarking framework has focused on improved robustness to edits, generation quality, detectability, and other desiderata for watermarking. While effective for open-ended long-form generation, LM watermarking remains a challenging problem in low-entropy setups such as factual question-answering and code generation. While some work ( 22 ; 25 ) addresses this problem for code generation via selective token-entropy based watermarking, we posit that in general, all token-level watermarking schemes under-utilize sequence-level entropy for embedding the signal and hence struggle in constrained generation tasks like machine translation that although lower entropy than open-ended generation, still admit multiple feasible responses with sufficient sequence-level entropy. An appealing alternative paradigm of sequence-level watermarking in recent work ( 14 ; 15 ) that instead of randomly partitioning the token space at each generation step, focuses on partitioning the manifold of sequences via hyperplanes into red/green regions, and then perform rejection sampling to sample from the green regions is promising. However, we identify a different common issue of red/green region collapse with existing approaches that prevent low-entropy watermarking. Specifically, the operationalization of these algorithms via locality-sensitive hashing or k -means clustering leads to the assignment of semantically similar sentences to the same red/green partition. Due to semantic diversity, this is not a problem for open-ended generation tasks, but for constrained generation tasks, most of the admissible outputs with high probability tend to be semantically close to one another and mostly collapse to a single region. This imposes a challenging tradeoff between output quality and watermark verifiability for watermarking in constrained generation tasks. In this paper, we propose a novel sequence-level watermarking approach SeqMark that utilizes the limited sequence entropy effectively to watermark constrained generation tasks. This approach first identifies the semantic manifold of high-probable admissible outputs for the task at hand, and then semantically differentiates between the elements of this manifold to propose pseudorandom red/green partitions in a manner such that the potential high-quality responses are evenly spread across the partitions, enabling successful watermarking in low-entropy settings. We empirically support our claims and observations on watermarking previously underexplored constrained generation tasks like machine translation, summarization, and code generation. We demonstrate the issues with existing token-level and sequence-level watermarking algorithms and show that SeqMark is more effective in constrained generation settings, while maintaining high watermarking capabilities in open-ended generation settings. 2 Preliminaries Watermarking, much like steganography, is inherently a problem of incorporating a digital marker into the (ideally noise-tolerant) carrier signal. We are primarily interested in settings that incorporate a marker into the autoregressive language model’s distribution and thus perform watermarking (ideally imperceptible) during text generation. Token-level Logit Watermarking 18 introduced a seminal token-level watermarking algorithm dubbed KGW that embedded the marker in the logits produced over vocabulary for each token during generation. Many following attempts ( 24 ; 9 ) proposed variations to improve robustness and undetectability of the watermarking scheme. At an abstract level, all of these approaches modify the token-level distribution for watermarking during generation by pseudorandomly partition the vocabulary \mathcal{V} into a green list of size \gamma|\mathcal{V}| and red list size (1-\gamma)|\mathcal{V}| for a hyperparameter \gamma\in(0,1) , using a hash from the previous token w_{t-1} or LM state as random seed. The generation procedure is then modified to prefer the green-list partition over the red-list partition, thus embedding the watermark. Detection involves performing hypothesis testing to decide whether the frequency of the green-list tokens in the query text occurs by chance. Sequence-level Watermarking To improve the robustness of the watermarking method to paraphrase attacks, a different line of approach dubbed as semantic watermarking ( 14 ; 15 ) focuses on using sequence-level distribution induced by the language model instead of token-level distributions to embed the watermark. In general, the sentence-embedding space is pseudorandomly partitioned into green and red regions. Then a sentence is generated from the language modeling via rejection sampling until the resulting sentence embedding falls in the green region or the budget for resampling is exhausted. For generating the next sentence, another round of rejection sampling is performed following pseudorandom partitioning of the embeddings space using the hash based on the previously generated sentence. Prior work SemStamp ( 14 ) uses locality-sensitive hashing (LSH) to pseudorandomly partition the embedding space: LSH first samples n random vectors from a normal Gaussian distribution to specify n hyperplanes and thus 2^{n} regions. Given a hyperparameter ratio \gamma and the hash of the previous sentence, the regions are partitioned into \gamma 2^{n} green regions and (1-\gamma)2^{n} red regions. A sentence with embedding \mathbf{v}\in\mathbb{R}^{d} would receive an n -bit binary LSH signature c , where each bit specifies the location of v with respect to each hyperplane – thus c identifies the region assignment for v . In contrast, k -SemStamp ( 15 ) uses k-means clustering for partitioning instead of LSH: it first estimates K centroids for a general semantic manifold via pretraining, and then during the generation step it randomly assigns each of these centroids either a red/green tag. During sampling, each generated sentence is assigned red/green tag according to its closest