PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Codable Watermarking for Injecting Multi-bits Information to LLMs

Lean Wang, Wenkai Yang, Deli Chen, Hao Zhou, Yankai Lin, Fandong Meng, Jie Zhou, Xu Sun

arXiv:2307.15992v3cs.CL

TL;DR

Existing LLM watermarking methods usually carry limited information, motivating CTWL for customizable multi-bit payloads. The paper formalizes CTWL, evaluates it across five criteria, and proposes Balance-Marking, whose balanced vocabulary partition outperforms the direct baseline while preserving text quality.

  • Problem

    Existing LLM watermarking methods encode limited information and cannot flexibly carry application-specific payloads such as model version, generation time, or user identity.

    Source: §1 · p. 2

  • Method

    The paper formalizes CTWL, evaluates it on success, robustness, coding rate, computational complexity, and text quality, and introduces Balance-Marking with probability-balanced proxy-LM vocabulary partitions.

    Source: §1 · p. 2, §3.2 · p. 4

  • Results

    Balance-Marking significantly outperforms the direct baseline across five evaluation dimensions and offers a practical level of usability.

    Source: §6 · p. 9

  • Takeaways & Limitations

    Probability-balanced vocabulary partitioning provides a practical route to customizable multi-bit watermarking while maintaining generated-text quality.

    Source: §1 · p. 2, §6 · p. 9

    At a coding rate of 5 tokens per bit, both watermarks are ineffective under attacks, so robustness results omit that setting.

    Source: §5.3 · p. 8

Abstract

from arXiv · show

As large language models (LLMs) generate texts with increasing fluency and realism, there is a growing need to identify the source of texts to prevent the abuse of LLMs. Text watermarking techniques have proven reliable in distinguishing whether a text is generated by LLMs by injecting hidden patterns. However, we argue that existing LLM watermarking methods are encoding-inefficient and cannot flexibly meet the diverse information encoding needs (such as encoding model version, generation time, user id, etc.). In this work, we conduct the first systematic study on the topic of Codable Text Watermarking for LLMs (CTWL) that allows text watermarks to carry multi-bit customizable information. First of all, we study the taxonomy of LLM watermarking technologies and give a mathematical formulation for CTWL. Additionally, we provide a comprehensive evaluation system for CTWL: (1) watermarking success rate, (2) robustness against various corruptions, (3) coding rate of payload information, (4) encoding and decoding efficiency, (5) impacts on the quality of the generated text. To meet the requirements of these non-Pareto-improving metrics, we follow the most prominent vocabulary partition-based watermarking direction, and devise an advanced CTWL method named Balance-Marking. The core idea of our method is to use a proxy language model to split the vocabulary into probability-balanced parts, thereby effectively maintaining the quality of the watermarked text. Our code is available at https://github.com/lancopku/codable-watermarking-for-llm.

1 INTRODUCTION

The paper frames CTWL as multi-bit watermarking for identifying LLM-generated text while carrying customizable information, and proposes Balance-Marking to preserve text quality through probability-balanced vocabulary partitions.

Research gap

  • The taxonomy highlights a research gap between watermarking methods that underuse LLM generation and methods that lack customized information.The paper presents its approach as addressing both issues simultaneously.Source: Table 1 · p. 2, §1 · p. 2

Motivation

  • CTWL addresses the limitation that existing LLM watermarks typically encode only whether text came from one model, rather than customizable information such as model version.The paper positions this gap as important for tracing text among multiple LLMs.Source: §1 · p. 2

Contributions

  • The paper introduces a systematic CTWL study covering taxonomy, mathematical formulation, and five evaluation criteria.The criteria are success rate, robustness, coding rate, computational complexity, and text quality.Source: §1 · p. 2

Challenge

  • CTWL requires balancing conflicting goals because stronger multi-bit watermarking can damage generated-text quality.The Vanilla-Marking baseline performs poorly on quality because multi-bit watermarks are more complex than one-bit watermarks.Source: §1 · p. 2

Balance-Marking

  • Balance-Marking uses a proxy language model to split the vocabulary into available and unavailable parts with probabilities near 50-50.The balanced partition avoids concentrating high-probability tokens in the unavailable part and can skip low-entropy segments.Source: §1 · p. 2
  • Balance-Marking supports deployment flexibility by switching the proxy language model for efficiency or an open watermarking protocol.A small proxy model can improve inference efficiency, while a public proxy model can support deployment across providers without exposing the target LLM.Source: §1 · p. 2

2 RELATED WORK

Prior LLM watermarking methods either integrate watermarking into generation or post-process text, while most integrating methods remain one-bit and multi-bit methods risk harming quality.

Taxonomy

  • LLM watermarking methods are divided by insertion point into generation-integrated methods and post-processing methods.Post-processing methods commonly replace tokens with synonyms using masked language models, whereas integrating methods operate during generation.Source: §2 · p. 3

Post-processing methods

  • Post-processing methods can encode one-bit or multi-bit information but do not exploit the generative power of LLMs to adapt subsequent tokens.The paper therefore characterizes them as less effective for generating high-quality watermarked text.Source: §2 · p. 3

Integrating methods

  • Representative integrating methods manipulate the available vocabulary during decoding, but existing approaches generally encode only one bit.Related work varies seed generation, selects high-entropy tokens, or uses a global key for vocabulary splitting.Source: §2 · p. 3

Multi-bit watermarking

  • Concurrent multi-bit methods retain random vocabulary partitioning, which creates a quality threat when complex watermarks are injected.Balance-Marking instead balances the probability distribution of vocabulary partitions to maintain text quality.Source: §2 · p. 3

3 MATHEMATICAL FORMULATION OF CODABLE LLM WATERMARKING

The formulation defines CTWL as encoding messages into generated text and decoding them afterward, while requiring message recoverability alongside preservation of unwatermarked text quality.

3.1 NOTATIONS AND PRELIMINARIES

  • At each generation step, the LLM conditions on the prompt and previously generated tokens to produce a probability distribution over the vocabulary.The next token is sampled from this distribution using a specified sampling rule.Source: §3.1 · p. 3

3.2 FORMULATION OF CODABLE TEXT WATERMARKING

  • The first generation step has no previously generated token, so the initial history is defined as empty.This is the boundary condition for the sequential notation.Source: §3.2 · p. 3
  • CTWL is formulated as an encoding map from prompts and messages to texts and a decoding map from texts to messages.The formulation uses prompt space P, text space T, and message space M; one-bit watermarking is the special case M={0,1}.Source: §3.2 · pp. 3–4
  • The decoding objective selects the message m that maximizes its posterior probability given the generated text.The message function Pw measures how likely each candidate message is given the text.Source: §3.2 · p. 4
  • The encoding objective enlarges the probability gap between text generated under the target message and text generated under alternative messages.This expresses the requirement that the embedded message be distinguishable from competing messages.Source: §3.2 · p. 4
  • The formulation adds the original unwatermarked text as a quality baseline because message hiding alone does not account for generation quality.The paper uses perplexity to measure whether watermarked text remains similar in quality to text without watermarks.Source: §3.2 · p. 4

4 BALANCE-MARKING: A SIMPLE YET EFFECTIVE CTWL METHOD

The paper formulates codable watermark encoding and develops Balance-Marking, which uses proxy-LM-guided probability-balanced vocabulary partitions to encode and decode multi-bit messages while preserving text quality.

4.1 A GENERAL FRAMEWORK FOR CODABLE WATERMARK ENCODING

  • Balance-Marking combines model logits with message logits during generation, selecting tokens through a general encoding framework for a predefined Pw.The message logit is added to the language model logit, with watermark strength controlled by δ.Source: §4.1 · p. 5

4.2.1 VANILLA Pw FOR RANDOM VOCABULARY PARTITION

  • Vanilla-Marking extends random vocabulary splitting by making the partition depend on the message and text prefix through hash-based seeds.The method shuffles the vocabulary and selects a subset satisfying the required probability condition.Source: §4.2.1 · pp. 5–6

4.2.2 LMproxy-AIDED Pw FOR BALANCE VOCABULARY PARTITION

  • Balance-Marking uses a proxy language model to choose vocabulary subsets whose accumulated probabilities are approximately balanced, with σ set to 0.5 by default.Randomized subset selection preserves message-dependent differences while seeking tokens with both high model and message logits.Source: §4.2.2 · pp. 6–7
  • The practical method truncates prefixes, generalizes the proxy model, and hashes messages into a smaller space to support consistent and efficient encoding and decoding.Multiple messages can also be encoded sequentially in separate text segments and decoded independently.Source: §4.2.2 · pp. 6–7, §4.3 · p. 7
  • Balance-Marking improves text quality by selecting tokens with high model and message logits and implicitly skipping low-entropy positions during watermarking.When one token dominates the proxy-LM distribution, that token can remain available for all messages, so decoding focuses on higher-entropy positions.Source: §4.2.2 · p. 7

4.3 MESSAGE DECODING

  • Message decoding solves for the most likely embedded message using the corresponding Vanilla-Marking or Balance-Marking message function.The same decoding formulation supports sequential message extraction from independently encoded segments.Source: §4.3 · p. 7

5 EXPERIMENT

Experiments evaluate watermark quality, attack robustness, efficiency, discrimination from human text, and scaling across language models. Balance-Marking consistently outperforms Vanilla-Marking, although stronger watermarking and higher coding rates create quality or robustness challenges.

5.2 THE RESULTS OF WATERMARK QUALITY

  • Balance-Marking offers a superior perplexity–watermark-success trade-off at both tested coding rates, while 5 tokens per bit is particularly challenging.Increasing watermark success tends to reduce text quality, but Balance-Marking remains better than Vanilla-Marking in both settings.Source: §5.2 · p. 8, Figure 1 · p. 8

5.3 THE RESULTS OF ROBUSTNESS TO REAL-WORLD ATTACKS

  • Balance-Marking maintains superior performance under copy-paste attacks that insert 200 watermarked tokens into 1000 human-written tokens.A threshold of 1−10^-5 prevents human-written texts from being mislabeled as watermarked in the reported test.Source: §5.3 · p. 8
  • At a 5% substitution ratio, Balance-Marking outperforms Vanilla-Marking, while the study omits 5-token-per-bit attacks because both watermarks become ineffective.The paper also reports experiments with a 10% substitution ratio in Appendix I.Source: §5.3 · pp. 8–9

5.4 FURTHER ANALYSIS

  • Balance-Marking outperforms Vanilla-Marking in distinguishing message-embedded texts from human-written texts while reporting the associated text-quality trade-off.The same 1−10^-5 threshold prevents false extraction from human-written texts but can misclassify some watermarked texts as human-written.Source: §5.4 · p. 9
  • Using larger proxy models improves watermark quality but introduces additional computational cost, exposing an efficiency–quality trade-off.Vanilla-Marking is treated as Balance-Marking with no proxy language model.Source: §5.4 · p. 9, Figure 2 · p. 9
  • Balance-Marking stably outperforms Vanilla-Marking when scaling to LLaMA-7/13B under the reported coding-rate settings.The main scaling experiment uses a coding rate of 10; coding rate 5 results are reported in Appendix J.Source: §5.4 · p. 9, Figure 2 · p. 9

6 CONCLUSION

The paper presents CTWL as a systematic framework for carrying multi-bit information in LLM-generated text, combining taxonomy, formalization, evaluation, and Balance-Marking. It concludes that the method improves comprehensive usability while supporting source identification and discusses ethical, reproducibility, and future-detection context.

6 CONCLUSION

  • Balance-Marking significantly outperforms the direct baseline across five evaluation dimensions, reaching a practical level of usability.The dimensions cover success rate, robustness, coding rate, encoding and decoding efficiency, and generated-text quality.Source: §6 · p. 9
  • The work provides the first systematic CTWL study, including a taxonomy and rigorous mathematical formalization for multi-bit LLM watermarking.Source: §6 · p. 9

ETHICAL STATEMENT

  • The authors argue that richer watermarks can help identify model-generated text and trace harmful uses such as fake news or academic cheating.Source: ETHICAL STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

B DETAILED MATHEMATICAL DERIVATIONS OMITTED IN THE MAIN PAPER

This appendix supplies omitted mathematical derivations and clarifies assumptions used to simplify the paper’s objectives and probability expressions. It specifically uses a same-model perplexity assumption to treat one term as constant during reformulation.

B DETAILED MATHEMATICAL DERIVATIONS OMITTED IN THE MAIN PAPER

C THE EVALUATION SYSTEM OF CODABLE LLM WATERMARKING

The paper defines a five-dimensional evaluation system for CTWL and connects it to deployment scenarios involving service providers, users, public protocols, and relay watermarking. It also motivates probability approximations that reduce computation while monitoring their empirical validity.

C THE EVALUATION SYSTEM OF CODABLE LLM WATERMARKING

C.1 WATERMARKING SUCCESS RATE

  • Watermark success requires both recognizing model-generated text and recovering the injected message, whereas conventional watermarking evaluates only recognition.Source: §C.1 · p. 14

C.2 ROBUSTNESS AGAINST ATTACKS

  • Robustness is assessed against copy-paste attacks that mix human and generated fragments and substitution attacks that replace tokens synonymously.Source: §C.2 · p. 14

C.3 PAYLOAD INFORMATION CODING RATE

  • Coding rate is measured as carried watermark bits divided by covered-token length, while efficiency accounts for added encoding and decoding cost and parallelism.Source: §C.3 · p. 14, §C.4 · p. 14

C.5 IMPACT ON THE QUALITY OF GENERATED TEXT

  • Text-quality impact is measured with perplexity because multi-bit watermarks can affect quality more than one-bit watermarks; semantic and human metrics are left for future work.Source: §C.5 · p. 15

D.1 CORPORATE INTELLECTUAL PROPERTY PROTECTION

D.2 USER-LEVEL COPYRIGHT PROTECTION

  • User-level copyright protection can use exclusive watermark algorithms, while an independent organization could manage and certify customized algorithms.Source: §D.2 · p. 15

D.3 OPEN WATERMARKING PROTOCOL

  • An open protocol could let multiple private models encode messages while one public proxy-LM decodes them, and relay watermarking could accumulate provenance across successive models.Relay processing extracts the incoming message, combines it with the new model’s message, and embeds the result again.Source: §D.3 · p. 15, §D.4 · p. 16

E.2 SUBSTITUTING log Pw(v|m, t:(l−1)) WITH log ˆPw(v|m, t:(l−1)) DURING DECODING

The decoding approximation replaces an expensive probability term with a proxy expression whose empirical variation remains sufficiently modest for faster computation. Practical refinements align encoding and decoding contexts, support public proxy models, and shrink message-space computation.

E.2 SUBSTITUTING log Pw(v|m, t:(l−1)) WITH log ˆPw(v|m, t:(l−1)) DURING DECODING

  • The decoding approximation replaces log P_w with log P̂_w when the difference is treated as nearly constant.The argument uses an i.i.d. interpretation, the law of large numbers, and empirical observations that log P̂_w exceeds 10.5.Source: §E.2 · p. 17

F DETAILED ILLUSTRATIONS ABOUT THE PRACTICAL IMPROVEMENTS ON BALANCE-MARKING

G HYPERPARAMETERS AND HASH SCHEME

G.1 THE IMPACT OF THE PROXY LANGUAGE MODEL LMproxy

The proxy language model improves watermark quality but increases computational cost, creating a trade-off between efficiency and performance. Parameter choices further balance quality, encoding coverage, and decoding cost.

G.1 THE IMPACT OF THE PROXY LANGUAGE MODEL LMproxy

  • GPT2-Large outperforms GPT2-XL, suggesting that proxy-model improvements may have a performance ceiling.A larger LMproxy generally improves performance, but larger models also increase computational cost.Source: §G.1 · p. 18, Figure 3 · p. 19, Table 4 · p. 19
  • LMproxy = LLM achieves the best watermark quality but is slower than LMproxy = GPT2.Increasing LMproxy size amplifies computational cost during both encoding and decoding.Source: §G.1 · p. 19, Table 4 · p. 19

G.2 THE IMPACT OF THE PRE-MAPPING SPACE SIZE A

  • A larger A generally improves watermark performance, although A = 150 performs worse than A = 100.Lower A reduces decoding expenses, and A = 100 was selected for the main experiments.Source: §G.2 · p. 19

G.3 THE IMPACT OF THE TRUNCATION LENGTH Lprefix

  • A low Lprefix can degrade watermark quality, while Lprefix = 10 performs similarly to larger values such as 15 or 20.Longer prefixes can improve proxy estimates but reduce the number of effective tokens available for encoding and decoding; efficiency remains relatively consistent.Source: §G.3 · pp. 19–20

G.4 THE IMPACT OF THE MESSAGE SPACE SIZE |M|

  • Larger |M| improves watermark quality by providing more tokens per message, but decoding cost rises noticeably as |M| reaches 2^20.Encoding cost remains relatively stable, whereas the message space cannot be increased without limit because decoding requires evaluating all messages.Source: §G.4 · p. 20

G.5 HASH SCHEME

  • Both Vanilla-Marking and Balance-Marking use the last token in the preceding text to compute their hash functions.This hash scheme is applied to h(v, m, t:(l−1)) and h(m, t:(l−1)).Source: §G.5 · p. 21

H IMPLEMENTATION OF SUBSTITUTION ATTACKS

Substitution attacks replace selected tokens through masked prediction, with higher substitution ratios reducing watermark success. Balance-Marking is more affected than Vanilla-Marking as substitution increases.

H IMPLEMENTATION OF SUBSTITUTION ATTACKS

  • The attack masks randomly selected tokens and replaces them when a candidate logit is within 1.0 of the original token’s predicted logit.Replacement continues until αL tokens are changed or 3αL attempts are reached, with an observed PPL increase of about 0.1.Source: H IMPLEMENTATION OF SUBSTITUTION ATTACKS · p. 21

I SUBSTITUTION ATTACKS WITH A SUBSTITUTION RATIO OF 10%

  • At substitution ratios of 5% and 10%, higher substitution lowers success rates and narrows the performance gap between Balance-Marking and Vanilla-Marking.Balance-Marking is more affected because its decoding probability depends on a longer token prefix, whereas Vanilla-Marking uses only the last token.Source: I SUBSTITUTION ATTACKS WITH A… · p. 21, Figure 5 · p. 22

J RESULTS OF LLAMA-7B AND LLAMA-13B AT A CODING RATE OF 5

At a coding rate of 5, Balance-Marking outperforms Vanilla-Marking on both LLaMA-7B and LLaMA-13B. The paper also provides generated-text examples as a qualitative case study.

J RESULTS OF LLAMA-7B AND LLAMA-13B AT A CODING RATE OF 5

K ILLUSTRATIVE EXAMPLES OF WATERMARKED TEXTS

Related papers

Loading 2307.15992v3…