PaperlayerView exact revision on arXiv

Source-linked AI summary

WeaveMark: Robust and Scalable Multi-bit LLM Watermarking via Coded Payload Spreading

Gang-Hyun Park, Ju-Hyeong Lee, Hee-Youl Kwak, Dae-Young Yun

arXiv:2609.02177v1cs.CRcs.LG

TL;DR

Multi-bit LLM watermarking must balance extraction accuracy, text quality, and payload capacity while supporting provenance verification. WeaveMark addresses this with coded payload spreading, soft-decision ECC, unbiased multilayer reweighting, and dedicated zero-bit layers, achieving substantially higher recovery rates.

  • Problem

    Multi-bit watermarking faces a trade-off among extraction accuracy, text quality, and payload capacity, despite its role in provenance verification and source tracing.

  • Method

    WeaveMark spreads ECC-coded payload bits across tokens and layers, decodes soft vote margins with ECC, preserves unbiased reweighting, and adds message-independent zero-bit layers.

  • Results

    89.8% match rate for 32-bit messages with 200 tokens, compared with 20.8% for BiMark, while preserving text quality and improving robustness to edited text.

  • Takeaways & Limitations

    Dedicated zero-bit layers provide watermark presence detection while WeaveMark retains a large multi-bit extraction advantage across long messages and editing attacks.

  • Takeaways & Limitations

    Existing detection schemes’ max-over-partitions statistic inflates non-watermarked null statistics, with the effect worsening as message length increases.

Abstract

from arXiv · show

Multi-bit watermarking for large language models (LLMs) enables content source tracing by embedding user-identifiable messages into generated text. Existing methods face a fundamental trade-off among extraction accuracy, text quality, and payload capacity. We propose WeaveMark, a robust and scalable multi-bit LLM watermarking scheme based on coded payload spreading. WeaveMark shifts this trade-off frontier by improving payload capacity through multi-bit-per-token spreading, improving extraction accuracy through soft-decision error-correcting code, and preserving text quality through unbiased multilayer reweighting. It further introduces dedicated zero-bit layers for reliable watermark presence detection. Experiments show large gains, especially for long messages and edited text. WeaveMark achieves 89.8% match rate for 32-bit messages at 200 tokens, compared with 20.8% for BiMark. Under 10% substitution attacks on 16-bit messages at 200 tokens, it maintains 86.0% versus 30.7%, while preserving text quality. Our code is available at https://github.com/qkrrkd90-source/WeaveMark.

1 Introduction

Multi-bit LLM watermarking embeds traceable messages for source tracing but must balance extraction accuracy, text quality, and payload capacity. WEAVEMARK addresses this trade-off with coded payload spreading, soft-decision ECC, unbiased multilayer reweighting, and dedicated zero-bit layers.

  • Watermarking embeds traceable information in LLM-generated text to support provenance verification and source tracing.
  • Multi-bit watermarking faces a trade-off among extraction accuracy, text quality, and payload capacity.More distinguishable token statistics can improve extraction but perturb the original token distribution, while higher capacity leaves fewer observations per bit.
  • WEAVEMARK spreads multiple ECC-coded payload bits across generated tokens and watermarking layers.
  • WEAVEMARK combines coded payload spreading, soft-decision ECC, and unbiased multilayer reweighting to improve capacity and extraction while preserving text quality.
  • Dedicated zero-bit layers avoid max-over-partitions inflation and enable reliable watermark presence detection alongside multi-bit recovery.

2 Related work

Zero-bit watermarking detects whether text is watermarked, whereas multi-bit watermarking recovers embedded messages. Existing multi-bit methods trade payload capacity, extraction reliability, and text quality in different ways.

  • Zero-bit watermarking detects whether generated text contains a watermark, commonly by testing for an unusually large number of green-list tokens.
  • Multi-bit watermarking recovers message bits from token-level statistics, making exact recovery increasingly difficult as message length grows.
  • MPAC improves payload capacity through segment allocation but constrains token selection with smaller vocabulary partitions, degrading text quality.
  • Qu et al. combine binary partitioning with segment allocation and use Reed-Solomon ECC to mitigate increased bit-level errors.
  • BiMark preserves expected token distributions through multilayer unbiased reweighting, but its one-bit-per-token design makes long-message extraction unreliable.
  • WEAVEMARK achieves the strongest reported trade-off across extraction accuracy, text quality, and payload capacity.

3 Preliminary

The preliminary framework defines vocabulary reweighting for zero-bit and multi-bit watermarking, unbiased multilayer embedding, ECC-coded messages, and the metrics used to evaluate recovery.

  • Zero-bit watermarking partitions the vocabulary into green-list and red-list sets and biases sampling toward green-list tokens.
  • The standard zero-bit statistic compares observed green-list tokens with their expected proportion and applies a detection threshold.
  • ECC encodes a k-bit message into an n-bit codeword, adding n−k redundancy for error correction while increasing embedding overhead.
  • BiMark assigns each token to one message bit and embeds it across independent vocabulary bipartitions using pseudorandom masks.
  • Unbiased multilayer reweighting preserves the original token distribution in expectation because the reweighting direction is a fair coin flip.
  • The extractor estimates layer directions, reconstructs bit votes, and recovers each message bit by majority voting.
  • Bit accuracy measures average bit-level reliability, while match rate measures exact recovery of the entire message.

4 Proposed method

WEAVEMARK combines coded payload spreading, layer shuffling, soft-decision ECC, and unbiased multilayer reweighting to improve multi-bit watermark recovery while retaining text-quality benefits. Its components distribute observations and reliability more evenly across bits, then use vote margins for error correction.

  • Payload spreading: WEAVEMARK spreads ECC-coded bits across generated tokens and multiple layers using multi-bit-per-token embedding and layer shuffling.Each token selects κ bit positions, while layer assignments are balanced across those positions.
  • Payload spreading: Payload spreading gives each bit approximately κT/n token positions instead of T/n under one-bit-per-token embedding, increasing observations without increasing the total layer budget per token.More token-level statistics reduce uneven vote accumulation across the embedded sequence.
  • Payload spreading: Layer shuffling randomly permutes layer indices so fixed bit positions do not repeatedly receive layers with the same extraction reliability.This balances effective embedding strength across bit positions and improves match rate, including from 24.9% to 54.3% for 32-bit messages with 200 tokens.
  • Payload spreading: Increasing κ improves both bit accuracy and match rate, with match rate rising from 3.01% to 25.56% for 16-bit messages at 50 tokens.For 32-bit messages at 200 tokens, match rate rises from 11.76% to 40.64%.
  • Soft-decision ECC decoding: Soft-decision ECC decodes codewords using vote margins, whose signs indicate likely bit values and magnitudes indicate reliability.The decoder selects the codeword with the largest correlation to the soft vote vector; vote margin was adopted because it performed best among tested metrics.
  • Soft-decision ECC decoding: Soft-decision ECC increases 32-bit match rate from 18.94% to 80.07% at 200 tokens despite adding embedded parity bits that can reduce bit accuracy.Across the component ablation, the full system reaches 89.84% from BiMark’s 20.78% for 32-bit messages with 200 tokens.

5 Experiments

Experiments evaluate WEAVEMARK’s message recovery on clean and synonym-edited text, alongside downstream text quality. It improves exact recovery, especially for longer messages and attacks, while retaining quality comparable to unwatermarked text and BiMark.

  • Clean-text extraction: 89.84% match rate for 32-bit messages at 200 tokens, compared with 20.78% for BiMark.WEAVEMARK’s advantage is especially pronounced for long messages and short generated texts.
  • Clean-text extraction: 76.02% match rate for 16-bit messages at 50 tokens, while BiMark reaches 4.84%.
  • Robustness to editing attacks: 86.02% match rate under 10% synonym substitution for 16-bit messages, compared with 30.67% for BiMark.At a 20% substitution ratio, WEAVEMARK achieves 44.20%, while BiMark drops to 6.59%.
  • Robustness to editing attacks: 44.20% match rate under 20% synonym substitution for 16-bit messages, compared with 6.59% for BiMark.
  • Text quality: WEAVEMARK preserves text quality at a level comparable to unwatermarked text and BiMark.MPAC and Qu et al. show noticeable degradation at δ = 3.0, where stronger biased reweighting is used.

6 Zero-bit detection

WEAVEMARK adds message-independent zero-bit layers to avoid inflated max-over-partitions statistics. This supports stable watermark detection while retaining strong multi-bit recovery as payload length increases.

  • Detection method: Dedicated zero-bit layers reconstruct the target partition exactly because they are independent of message bits.They use unbiased reweighting, preserving the expected token distribution.
  • Detection method: Increasing the number of zero-bit layers strengthens zero-bit detection but leaves fewer layers for multi-bit embedding.
  • Multi-bit setting: 71.17% match rate for 32-bit messages at 200 tokens, compared with 19.4% for BiMark, with ℓ=10 and ℓz=2.Both methods achieve high TPR beyond 50 tokens.
  • Detection method: A stable z-score threshold around 2.3 at FPR=1% is maintained by WEAVEMARK across message lengths.BiMark’s threshold increases with message length because its max-over-partitions statistic becomes more inflated.
  • Pure zero-bit setting: WEAVEMARK achieves the highest TPR at every measured token length in the pure zero-bit setting at FPR=1%.In this setting, all 10 layers are assigned to zero-bit detection.

7 Conclusion

WEAVEMARK combines coded payload spreading, soft-decision ECC decoding, and unbiased multilayer reweighting for robust multi-bit watermarking. It improves recovery for long messages and editing attacks without degrading text quality, while dedicated zero-bit layers support detection.

  • WEAVEMARK improves payload capacity through multi-bit-per-token spreading, extraction accuracy through soft-decision ECC decoding, and text quality through unbiased multilayer reweighting.
  • 89.8% clean-text match rate replaces 20.8% for BiMark, while synonym-substitution robustness reaches 86.0% versus 30.7%.
  • Dedicated zero-bit layers provide strong watermark presence detection while preserving a large multi-bit extraction advantage.WEAVEMARK also outperforms existing zero-bit watermarking in the pure zero-bit setting.

A Algorithm details

The algorithms encode messages into ECC codewords, spread selected coded bits across shuffled watermarking layers, reweight token distributions, and recover messages through soft voting and decoding.

  • Zero-bit detection: Dedicated zero-bit layers are independent of message bits and are described separately for watermark presence detection.
  • Message embedding: The embedding algorithm encodes message m into an n-bit codeword c using an ECC encoder.
  • Message embedding: At each generation step, κ distinct codeword positions are selected and assigned across a balanced, shuffled layer vector.The assignment uses pseudorandom seeds and distributes selected positions as evenly as possible across ℓ layers.
  • Message embedding: Each layer estimates a reweighting direction from a masked codeword bit and applies the corresponding unbiased reweighting before sampling the next token.
  • Message extraction: The extraction algorithm accumulates votes for codeword positions from token-level layer estimates and converts them into a soft-vote vector.
  • Message extraction: The ECC decoder recovers the message by decoding the soft-vote vector, with the codeword selected by maximum correlation to that vector.

B Perplexity analysis

WEAVEMARK produces perplexity comparable to BiMark, while MPAC and Qu et al. show higher perplexity. Absolute PPL values require caution because repetitive generations can artificially lower measured perplexity.

  • WEAVEMARK yields PPL comparable to BiMark, while MPAC and Qu et al. at δ = 3.0 show noticeably higher PPL.The comparison uses 16-bit messages and evaluates generated text across token lengths.
  • Repetitive self-copying patterns can produce artificially low PPL because repeated tokens are highly predictable.This behavior occurs occasionally with the 8B-parameter model under 4-bit quantization.
  • Relative PPL comparisons remain meaningful across methods, but absolute PPL values should be interpreted with caution.The measurement issue affects watermarked and non-watermarked generation alike.

C Voting method comparison

Voting methods differ in how much confidence information they retain when aggregating token-level votes. Soft voting outperforms hard voting on match rate, while soft and LLR voting are similar at longer lengths.

  • Soft voting scores each bit using the signed vote difference v1−v0 and decodes through maximum-likelihood correlation with the codebook.This preserves vote-count information, unlike hard voting.
  • At 32-bit and 100 tokens, hard voting achieves 37.06% match rate versus 61.80% for soft voting.Hard voting discards vote-confidence information by retaining only the majority bit.
  • Hard voting consistently underperforms soft and LLR voting on match rate, with the gap widening as message length increases.
  • Soft and LLR voting are nearly indistinguishable at 125+ tokens, alternating within 1 percentage point.At 25–100 tokens, soft voting instead exceeds LLR voting by 1–3 percentage points.

D Additional robustness results

WEAVEMARK is robust to paraphrasing and moderate synonym substitution, but its advantage narrows or reverses under stronger substitution attacks. The higher robustness cost partly reflects its unbiased design and larger context window.

  • At ρ = 0.1 and ρ = 0.2, WEAVEMARK consistently outperforms all baselines across message lengths.This includes Qu et al. at δ = 3.0.
  • At ρ = 0.3 and 200 tokens, Qu et al. achieves 25.90% versus 19.74% for WEAVEMARK on 12-bit messages.For 16-bit messages, the corresponding rates are 9.58% versus 7.14%.
  • At ρ = 0.3, match rates for 24-bit and 32-bit messages drop to near zero for all methods.This leaves little room for meaningful comparison at those message lengths.
  • WEAVEMARK’s window size of 2 lets each substitution disrupt extraction at the substituted position and the next two positions.Its larger window follows from preserving unbiased reweighting, which requires that no context be reused for watermarking.
  • Coded payload spreading and soft-decision ECC decoding provide redundancy that supports robustness under paraphrasing attacks.
Loading 2609.02177v1…