PaperlayerView exact revision on arXiv

Source-linked AI summary

Advancing Beyond Identification: Multi-bit Watermark for Large Language Models

KiYoon Yoo, Wonhyuk Ahn, Nojun Kwak

arXiv:2308.00221v3cs.CLcs.AIcs.CR

TL;DR

Some malicious uses of language models call for tracing users beyond identifying generated text, while existing multi-bit schemes face robustness challenges as message size and corruption increase. MPAC allocates tokens to message positions, and the paper reports improved robustness over the runner-up in high-noise settings. Its authors also identify a remaining trade-off between message capacity and zero-bit detection rate.

  • Problem

    Existing zero-bit watermarking focuses on identifying machine-generated text, while some malicious uses call for tracing the responsible user; larger messages and greater corruption also challenge multi-bit watermark integrity.

    Source: §1 · pp. 1–2

  • Method

    MPAC pseudo-randomly allocates generated tokens to message subunits and uses each allocated position's content to select a colorlist under a zero-bit watermarking scheme.

    Source: §1 · p. 2

  • Results

    At least 20% greater robustness than the runner-up is reported for 16-bit and 24-bit messages in high-noise settings.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors present MPAC as a way to support accountability for high-stakes misuse through API-generated text while retaining zero-bit detection.

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

    Multi-bit watermarking retains a trade-off between load capacity and zero-bit detection rate, which the authors identify as a deployment challenge.

    Source: Limitations · p. 10

Abstract

from arXiv · show

We show the viability of tackling misuses of large language models beyond the identification of machine-generated text. While existing zero-bit watermark methods focus on detection only, some malicious misuses demand tracing the adversary user for counteracting them. To address this, we propose Multi-bit Watermark via Position Allocation, embedding traceable multi-bit information during language model generation. Through allocating tokens onto different parts of the messages, we embed longer messages in high corruption settings without added latency. By independently embedding sub-units of messages, the proposed method outperforms the existing works in terms of robustness and latency. Leveraging the benefits of zero-bit watermarking, our method enables robust extraction of the watermark without any model access, embedding and extraction of long messages ($\geq$ 32-bit) without finetuning, and maintaining text quality, while allowing zero-bit detection all at the same time. Code is released here: https://github.com/bangawayoo/mb-lm-watermarking

1 Introduction

Existing watermarking can identify machine-generated text, but some malicious uses call for tracing the responsible user. MPAC allocates tokens to message subunits to embed longer messages without added generation latency and improve robustness in high-corruption settings.

1 Introduction

  • Tracing the user can matter when malicious LLM-generated misinformation or propaganda risks eroding social trust; detection alone may not suffice.The introduction notes that tracing could support user bans and collaboration with platforms and law enforcement.Source: §1 · p. 1
  • As message bit-width and corruption increase, existing multi-bit watermarks become harder to preserve, while considering all possible messages can increase encoding or decoding latency.Higher encoding latency can degrade the end-user experience.Source: §1 · pp. 1–2
  • MPAC pseudo-randomly allocates tokens to message subunits and reports at least 20% greater robustness than the runner-up for 16-bit and 24-bit messages in high-noise settings.The allocation is illustrated alongside zero-bit and recent multi-bit encoding approaches in Figure 1.Source: §1 · p. 2, Figure 1 · p. 2

2 Related Works

Prior natural-language watermarking spans robust information embedding, neural decoders, and zero-bit detection during generation. The paper positions MPAC as an extension of zero-bit watermarking for embedding information, with message length motivated by user identification needs.

2 Related Works

  • Watermarking embeds information in natural language robustly against attacks, whereas steganography emphasizes making an embedded secret message undetectable.The paper gives arithmetic coding as an example of a fragile deterministic steganographic approach.Source: §2 · p. 2
  • Neural watermarking work includes decoder-based message prediction and later approaches to text quality, robustness, and capacity, but sentence-level methods can fail after sentence edits and may not distinguish human text.The paper also notes that those works cannot distinguish non-watermarked texts.Source: §2 · p. 2
  • Zero-bit watermarking during token generation can distinguish language-model outputs from human text, and prior work has addressed low-entropy tasks, undetectability, and robustness.MPAC extends this line by embedding information while maintaining the stated advantages.Source: §2 · pp. 2–3
  • Concurrent multi-bit methods use the entire message during embedding, while MPAC allocates tokens to message positions; Wang et al. (2023a) also use a proxy language model for quality.The paper says the different message use leads to robustness and latency differences.Source: §2 · p. 3
  • The paper motivates longer messages by noting that a five-character POSIX username requires at least 35 bits, and says MPAC encodes bit positions independently.The passage contrasts this with image-watermarking works that embed messages over 32 bits.Source: §2 · p. 3

3 Method

The method builds multi-bit watermarking on a zero-bit token-generation scheme, assigning tokens to message positions and encoding each position's content through colored vocabulary lists. It decodes those per-position signals and can also test whether text is watermarked.

3 Method

  • The protocol embeds user-specific metadata during generation, then checks published text for watermark presence and decodes the message if it is unsafe or malicious.The message may contain a timestamp, location, or ID.Source: §3 · p. 3

3.1 Zero-bit Watermarking

  • The reviewed zero-bit scheme biases next-token probabilities toward a selected token subset while retaining the language model's original distribution as its starting point.The method description says the encoding function alters the original next-token distribution.Source: §3.1 · p. 3

Greenlist

  • Greenlist forms a pseudo-random token subset from the preceding-token context, biases its logits, and detects a watermark by checking the green-token ratio.The paper describes using a normal approximation to a binomial distribution for the detection statistic.Source: Greenlist · p. 3

3.2 MPAC: Extending to Multi-bit Watermark

  • MPAC assigns each token a pseudo-random message position, favors the colorlist for that position's content, and decodes by choosing the most-counted colorlist per position.Messages may be converted to radix r; the number of colorlists is determined by the greenlist proportion.Source: §3.2 · p. 4

3.3 Detecting Machine Text

  • MPAC can detect watermarked text by counting tokens assigned to predicted message colorlists and computing a z-statistic under a binomial null model.The method describes the position-specific counts as independent for fixed trial counts.Source: §3.3 · pp. 4–5

3.4 Comparison to Other Works

  • Compared with MPAC's position allocation, existing methods use the entire message during embedding to determine a signal.The paper says this difference leads to robustness and latency differences.Source: §3.4 · p. 5

Cyclic-Shift

Message-Hash

  • Message-Hash hashes the entire message to create a seed used to permute the vocabulary alongside the prefix-derived seed.This changes the seed-generation step of Greenlist.Source: §3.4 · p. 5

12 end

The supplied passage shows a loop over message positions.

12 end

  • The procedure iterates over message positions p in [˜b].The passage provides only this loop line.Source: §12 · p. 5

20 Get bit message ˆm by converting ˆmr

MPAC independently encodes message positions, avoiding the high-bit decoding cost and all-or-nothing corruption behavior described for whole-message schemes. Confidence-ranked list decoding offers a practical set of provenance candidates for inspection.

20 Get bit message ˆm by converting ˆmr

  • Whole-message Message-Hash can yield either an entirely correct message or a random one under high corruption, while MPAC encodes each message position independently.MPAC's computation increases negligibly as message length grows; the cited prior schemes face exponential decoding cost, and Cyclic-Shift also lengthens encoding.Source: §20 · p. 5

3.5 Techniques for Practical Use

  • List decoding returns confidence-sorted candidate messages, narrowing possible leakage points for costly manual provenance inspection.For example, candidate timestamps can guide practitioners' inspection instead of requiring a single predicted timestamp.Source: §3.5 · p. 6
  • Per-position confidence reflects how far the predicted color-list count deviates from the equal-likelihood null expectation.The expected maximum count is approximated using techniques from Levin (1981).Source: §3.5 · p. 6
  • A bound on list size controls alternatives: the algorithm greedily changes the least-confident positions to the second-largest color-list count.The method can also be combined with other decoding-feasible approaches, and independent position encoding makes error-correction codes straightforward to apply.Source: §3.5 · p. 6

4 Experiments

Across the reported copy-paste comparisons, MPAC retains stronger multi-bit accuracy at higher bit-widths while avoiding the prior methods' message-length-related latency costs. Experiments also report long-message detection, paraphrase robustness, preserved text quality, and performance across models.

4.1 Experimental Settings

  • The main experiments use LLaMA-2-7B on news-like C4 samples, random b-bit messages, and more than 500 samples.The evaluation measures bit accuracy, AUROC, and TPR at false-positive-rate thresholds, and tests copy-paste and GPT-3.5 paraphrasing attacks.Source: §4.1 · pp. 6–7

4.2 Results

  • Under GPT-3.5 paraphrasing, bit accuracy reaches nearly 80% at T=500, and 16-list decoding reaches 90% across token lengths.The authors describe paraphrasing short segments as more challenging than copy-paste corruption.Source: §4.2 · p. 7, Figure 4 · p. 8
  • With fixed γ, using r=4 colorlists rather than r=2 improves load capacity; γ=0.25, r=4 is statistically better than the second-best variant at p=1e−2.The reported exception is the 8-bit case, which already achieves high accuracy.Source: §4.2 · p. 7
  • At higher bit-widths, MPAC outperforms prior methods in clean and copy-paste multi-bit accuracy, while MPAC latency does not increase with message length.Increasing Cyclic-Shift from 16-bit to 24-bit lengthens generation from 14 to 50 seconds per sample, roughly 3.6x.Source: §4.2 · p. 7, Figure 3 · p. 8
  • A 32-bit watermark exceeds AUC .99 after 200 observed tokens, while TPR at FPR=1e−3 declines from 0.98 at b=0 to 0.91 at b=32.At 32-bit, the best message among 16 candidates achieves 95% bit accuracy; for 64-bit, 16 additional candidates yield a 3.0% absolute gain.Source: §4.2 · pp. 7–8
  • Text quality is statistically indistinguishable across bit-widths, and Mistral and OPT show similar performance to the tested models.The authors also report watermarking with finetuned models, with a slight drop-off for finetuned LLaMA.Source: §4.2 · p. 8

5 Discussions

The discussion examines the trade-off between message capacity and detection, along with how radix and confidence affect multi-bit watermark performance. It also outlines the scope of the reported model and metric comparisons.

Load capacity and detection performance trade-off

  • Longer messages degrade detection because the method overestimates non-watermarked human-text statistics; a multinomial-maximum alternative performed on par or slightly worse.The overestimation arises from finding the maximum cell value for each position, and the authors suggest small-sample approximation error may explain the alternative's results.Source: §5 · pp. 8–9
  • Figure 5 reports clean bit accuracy at fixed token count and fixed BPT, plus text quality and encoding latency across bit widths.The accuracy plots show 3 standard errors.Source: Figure 5 · p. 9

Detection and list decoding

  • Figure 6 tracks AUC by observed-token count for b=0, 8, 16, 24, and 32, and also plots varying γ and r and error rate by confidence.The γ and r comparison uses 1000 samples at T=100 and b=8.Source: Figure 6 · p. 9

Model variants

  • Table 1 covers other pretrained models and SFT and RLHF variants, with results at b=8 and T=250.The caption names Llama-2-7b-chat-hf and Mistral-7B-Instruct-v0.1.Source: Table 1 · p. 9

Radix and Colorlist proportion

  • At γ=.125, increasing r to 8 shows no statistically significant benefit over r=4; larger radices trade zero-bit performance for multi-bit performance.Larger r assigns more tokens to each position by shortening the effective message, but increases the possible answers per position.Source: §5 · p. 9

List Decoding Ablation

  • Higher confidence is associated with lower bit-error rate, although the confidence estimates are under-calibrated.The authors also report that randomly altering a single position can provide a good candidate list because the best candidate message is already a good starting point.Source: §5 · p. 9

6 Conclusion

The conclusion presents token allocation to message sub-units as an effective multi-bit watermarking approach. It reports no text-quality degradation relative to the zero-bit counterpart or latency overhead as bit width increases, while identifying a detection-rate trade-off.

6 Conclusion

  • Allocating tokens to message sub-units embeds multi-bit messages without quality degradation relative to the zero-bit counterpart or latency overhead as bit width increases.The authors describe this as a prospect for counteracting high-stakes LLM misuse via API and note that they analyze the trade-off with detection rate.Source: §6 · p. 9

Limitations

The paper cautions that watermarking is not yet ready for deployment in the wild, including because quality relative to non-watermarked generations needs further study. It also identifies a trade-off between multi-bit load capacity and zero-bit detection rate.

Limitations

  • The paper frames watermarking as a prospective technology for safer LLM use through accountability, rather than a ready-made solution.The passage identifies further study of quality against non-watermarked generations as one clear need.Source: Limitations · p. 10
  • Watermarking is described as not yet ready for wild deployment, and quality relative to non-watermarked generations remains an aspect needing further study.The authors state that MPAC maintains quality relative to its zero-bit counterpart and suggest quality improvements could extend to the multi-bit framework.Source: Limitations · p. 10
  • Multi-bit watermarking trades load capacity against zero-bit detection rate, an inherent limitation the authors say remains a deployment challenge.The authors report that their method outperforms baselines in the zero-bit setting, but does not resolve this trade-off.Source: Limitations · p. 10

Ethics Statement

The ethics statement connects watermarking with tracing malicious users and accountability, while addressing a privacy concern about providers knowing users' outputs. It limits that concern to content published publicly, which is often already in an identifiable setting such as social media.

Ethics Statement

  • Tracing a malicious user can support accountability for misuse of LLMs.The statement links tracing provenance with accountability for adversaries' malfeasance.Source: Ethics Statement · p. 10
  • The statement says providers cannot know an individual's outputs through this mechanism unless the content is published publicly.It notes that public content is often published in settings where the user can already be identified, such as social media.Source: Ethics Statement · p. 10
  • The paper concludes that identifying machine-generated text and tracing its provenance can enhance API-access accountability without breaching individual users' privacy.Source: Ethics Statement · p. 10

10. Tabular Results

This section reports tabular results on watermark metrics, detection and decoding options, robustness under attacks, and performance across datasets and model sizes. It also examines message-level error rates, text-quality trade-offs, and additional results and generation samples.

A.2.1 Watermark Detection

A.3.1 Results

  • Confidence-based list decoding (|L|=16) improves bit accuracy over random decoding, while watermarking adds negligible latency to vanilla generation (7.9 seconds encoding and 0.09 seconds decoding).Latency does not increase proportionally with message bit length.Source: Table 3 · p. 16, §A.3.1 · p. 16

A.3.2 Error Correction Codes

  • MPAC encodes each message position as a repetition code and decodes by majority vote; adding error-correction codes can raise match rate at the expense of rate.Source: §A.3.2 · p. 17

A.3.3 Message Correction with Feedback

  • Feedback that increases bias when a position is decoded incorrectly raises multi-bit accuracy but degrades text quality.Source: Table 2 · p. 16, §A.3.3 · p. 17

Block Allocation

  • 24-bit Block Allocation reached .901 bit accuracy versus .775 for Cyclic-Shift, and 32-bit Block Allocation reached .871.Block Allocation assigns blocks of the message to positions before applying Cyclic-Shift.Source: Block Allocation · p. 17

A.6 Metrics: Bit Accuracy, Text Quality

  • For T=250, the 8-bit message packet error ratio was 7.1%, 5.7% higher than the bit error rate, falling to 2.4% with 16-list decoding.Source: §A.6 · p. 19
  • At FPR=1e-3, the method correctly identifies 90.5% of users with an 8-bit message (256 users).This uses the setting for true positive rate computation described in Table 8.Source: §A.6 · p. 19

A.7 Discussion on the Hashing Scheme

  • LeftHash and SelfHash have similar multi-bit performance, but LeftHash has nearly no encoding-latency overhead while SelfHash takes significantly longer.For 250 tokens, average perplexity was 5.1 for LeftHash versus 4.9 for SelfHash, while P-SP was at the same level; LeftHash's sampled positions were nonuniform.Source: §A.7 · p. 19

A.8 More on Robustness: Other Attacks, Detection

  • With DIPPER at lexical diversity 20, the watermark fares considerably better than under the GPT-3 attack; controlling DIPPER diversity parameters can also degrade watermark performance.GPT-3.5 changes semantics and word count more than the Table 5 setting, which may explain its lower multi-bit performance.Source: §A.8 · p. 21, Table 5 · p. 21
  • After 250 observed tokens, copy-paste detection AUC largely recovers; at 10–50% corruption, final AUCs are .992, .987, .980, .971, and .942, while zero-bit scores all exceed .990.The method is also robust to partial word insertion and deletion because local context synchronizes message positions and vocabulary ordering.Source: Figure 11 · p. 20, §A.8 · p. 21

A.9 Ablations on Datasets and Model Sizes

  • Watermark performance depends on text distribution: low-entropy text limits multi-bit capacity, and the largest model consistently shows lower performance across model scales.The authors suggest lower vocabulary-distribution entropy may explain the largest model's generally higher text quality, and propose temperature or stronger bias as possible future directions.Source: §A.9 · pp. 21–22

A.10 Tabular Results

A.11 Generation Samples

  • Table 17 provides randomly sampled C4 news-like watermarked text examples with 100% bit accuracy, truncated for readability.Source: §A.11 · p. 22, Table 17 · p. 25
Loading 2308.00221v3…