SSG: Logit-Balanced Vocabulary Partitioning for LLM Watermarking

• URL: http://arxiv.org/abs/2604.22438v1
• Date: Fri, 24 Apr 2026 10:55:50 GMT
• Title: SSG: Logit-Balanced Vocabulary Partitioning for LLM Watermarking
• Abstract summary: KGW scheme is particularly attractive due to its versatility, efficiency, and effectiveness in natural language generation.<n>But KGW's effectiveness degrades significantly under low-entropy settings such as code generation and mathematical reasoning.<n>We propose SSG, a method that partitions the vocabulary into two logit-balanced subsets.
• Score: 3.881996954876714
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Watermarking has emerged as a promising technique for tracing the authorship of content generated by large language models (LLMs). Among existing approaches, the KGW scheme is particularly attractive due to its versatility, efficiency, and effectiveness in natural language generation. However, KGW's effectiveness degrades significantly under low-entropy settings such as code generation and mathematical reasoning. A crucial step in the KGW method is random vocabulary partitioning, which enables adjustments to token selection based on specific preferences. Our study revealed that the next-token probability distribution plays an critical role in determining how much, or even whether, we can modify token selection and, consequently, the effectiveness of watermarking. We refer to this characteristic, associated with the probability distribution of each token prediction, as \emph{watermark strength.} In cases of random vocabulary partitioning, the lower bound of watermark strength is dictated by the next-token probability distribution. However, we found that, by redesigning the vocabulary partitioning algorithm, we can potentially raise this lower bound. In this paper, we propose SSG (\textbf{S}ort-then-\textbf{S}plit by \textbf{G}roups), a method that partitions the vocabulary into two logit-balanced subsets. This design lifts the lower bound of watermark strength for each token prediction, thereby improving watermark detectability. Experiments on code generation and mathematical reasoning datasets demonstrate the effectiveness of SSG.

Related papers

• Optimal Watermark Localization in Mixed-Source Large Language Model Texts [41.92651100461471]
  Watermarking provides a principled way to authenticate text generated by large language models (LLMs)<n>In practice, the final text may be mixed-source, with watermark evidence surviving at only a subset of token positions after rewriting, insertion, deletion, or paraphrasing.<n>We formulate localization as a token-level multiple-testing problem based on pivotal statistics, with a latent indicator recording whether watermark dependence survives at each position.
  arXiv  Detail & Related papers  (2026-08-14T21:41:50Z)
• PMark: Towards Robust and Distortion-free Semantic-level Watermarking with Channel Constraints [49.2373408329323]
  We introduce a new theoretical framework on watermark-leveling (SWM) for large language models (LLMs)<n>We propose PMark, a simple yet powerful SWM method that estimates the median next sentence dynamically through sampling channels.<n> Experimental results show that PMark consistently outperforms existing SWM baselines in both text quality and paraphrasing.
  arXiv  Detail & Related papers  (2025-09-25T12:08:31Z)
• Debiasing Watermarks for Large Language Models via Maximal Coupling [24.937491193018623]
  We present a novel green/red list watermarking approach that partitions the token set into green'' and red'' lists, subtly increasing the generation probability for green tokens.<n> Experimental results show that it outperforms prior techniques by preserving text quality while maintaining high detectability.<n>This research provides a promising watermarking solution for language models, balancing effective detection with minimal impact on text quality.
  arXiv  Detail & Related papers  (2024-11-17T23:36:37Z)
• Provably Secure Disambiguating Neural Linguistic Steganography [66.30965740387047]
  The segmentation ambiguity problem, which arises when using language models based on subwords, leads to occasional decoding failures.<n>We propose a novel secure disambiguation method named SyncPool, which effectively addresses the segmentation ambiguity problem.<n> SyncPool does not change the size of the candidate pool or the distribution of tokens and thus is applicable to provably secure language steganography methods.
  arXiv  Detail & Related papers  (2024-03-26T09:25:57Z)
• Dynamically Allocated Interval-Based Generative Linguistic Steganography with Roulette Wheel [10.72286166021398]
  Existing linguistic steganography schemes often overlook the conditional probability (CP) of tokens in the candidate pool.<n>This paper proposes a scheme based on the interval allocated, called DAIRstega.
  arXiv  Detail & Related papers  (2024-01-28T13:21:44Z)
• Downstream Trade-offs of a Family of Text Watermarks [25.408313192999504]
  We evaluate the performance of LLMs watermarked using three different strategies over a diverse suite of tasks. We find that watermarks can cause significant drops in LLMs' effective utility across all tasks. Our findings highlight the trade-offs that users should be cognizant of when using watermarked models.
  arXiv  Detail & Related papers  (2023-11-16T11:44:58Z)
• Improving the Generation Quality of Watermarked Large Language Models via Word Importance Scoring [81.62249424226084]
  Token-level watermarking inserts watermarks in the generated texts by altering the token probability distributions. This watermarking algorithm alters the logits during generation, which can lead to a downgraded text quality. We propose to improve the quality of texts generated by a watermarked language model by Watermarking with Importance Scoring (WIS)
  arXiv  Detail & Related papers  (2023-11-16T08:36:00Z)
• A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models [65.40460716619772]
  Our research focuses on the importance of a textbfDistribution-textbfPreserving (DiP) watermark. Contrary to the current strategies, our proposed DiPmark simultaneously preserves the original token distribution during watermarking. It is detectable without access to the language model API and prompts (accessible), and is provably robust to moderate changes of tokens.
  arXiv  Detail & Related papers  (2023-10-11T17:57:35Z)
• SemStamp: A Semantic Watermark with Paraphrastic Robustness for Text Generation [72.10931780019297]
  Existing watermarking algorithms are vulnerable to paraphrase attacks because of their token-level design. We propose SemStamp, a robust sentence-level semantic watermarking algorithm based on locality-sensitive hashing (LSH) Experimental results show that our novel semantic watermark algorithm is not only more robust than the previous state-of-the-art method on both common and bigram paraphrase attacks, but also is better at preserving the quality of generation.
  arXiv  Detail & Related papers  (2023-10-06T03:33:42Z)
• Who Wrote this Code? Watermarking for Code Generation [53.24895162874416]
  We propose Selective WatErmarking via Entropy Thresholding (SWEET) to detect machine-generated text. Our experiments show that SWEET significantly improves code quality preservation while outperforming all baselines.
  arXiv  Detail & Related papers  (2023-05-24T11:49:52Z)
• Watermarking Text Generated by Black-Box Language Models [103.52541557216766]
  A watermark-based method was proposed for white-box LLMs, allowing them to embed watermarks during text generation. A detection algorithm aware of the list can identify the watermarked text. We develop a watermarking framework for black-box language model usage scenarios.
  arXiv  Detail & Related papers  (2023-05-14T07:37:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.