WeaveMark: Robust and Scalable Multi-bit LLM Watermarking via Coded Payload Spreading
Gang-Hyun Park, Ju-Hyeong Lee, Hee-Youl Kwak, Dae-Young Yun
cs.CR, cs.LG
2026-09-02
WeaveMark spreads ECC-coded bits across tokens and layers. At 200 tokens, 32-bit match rate is 89.8% versus 20.8% for BiMark, with near-clean text quality.
Multi-bit LLM watermarks embed a k-bit payload, such as a user ID, into generated text so the source can be traced later. Accuracy, fluency, and payload length pull against each other. Sharper token-level statistics perturb the sampling distribution. Longer messages leave fewer votes per bit, and exact recovery collapses.
Prior methods sit at different points on that frontier. MPAC and Qu et al. assign segments with biased reweighting: capacity goes up, quality drops. BiMark keeps the expected token distribution with multilayer unbiased reweighting, but each token votes for only one bit. On long messages or short texts the votes are sparse and uneven. At 200 tokens, 32-bit exact match rate is 20.8%.
WeaveMark keeps BiMark's unbiased multilayer reweighting and changes three pieces.
The message is first encoded into an n-bit ECC codeword. Each token is assigned κ codeword positions (default κ=10, ℓ=10 layers) from the previous h tokens, and layers are split across those positions. Each bit is observed at more token sites, so votes spread more evenly. Layers are applied in sequence, so early layers leave a cleaner signal: on LLaMA-3-8B, extraction accuracy falls from 72.20% at layer 1 to 56.98% at layer 10. A fixed assignment would feed some bits the weak layers forever, so layer indices are shuffled from context.
Decoding does not hard-vote. Each position uses v1 minus v0 as a soft reliability score and picks the codeword with maximum correlation. 12-bit messages use the extended Golay [24,12,8] code, 16-bit uses Reed-Muller [32,16,8], and 24/32-bit messages use two blocks. Enumeration is cheap up to 32 bits and stops being attractive beyond that.
A few message-independent zero-bit layers remain. Their vocabulary partition comes from context alone, so a standard z-test can ask "is this watermarked?" without taking a max over partitions, which inflates the null statistic.
Unbiasedness is intact: each layer's reweighting direction is still a fair coin, so the expected token distribution is unchanged.
The main setting is LLaMA-3-8B on C4 RealNewsLike, against BiMark, MPAC, and Qu et al.
| Setting | WeaveMark | BiMark |
| 32-bit / 200 tokens, exact match | 89.84% | 20.78% |
| 16-bit / 50 tokens, exact match | 76.02% | 4.84% |
| 16-bit, 10% synonym substitution | 86.02% | 30.67% |
| 16-bit, 20% synonym substitution | 44.20% | 6.59% |
Ablations are clean. Multi-bit embedding alone moves match rate from 20.78% to 24.00%. Layer shuffling jumps to 55.88%. Soft ECC then drops bit accuracy from 96.67% to 90.51% (more parity bits) while raising exact match to 89.84%. For 16-bit messages at 200 tokens, match rate is 96.6%, summarization BERTScore 30.5, and the longest payload that still clears 80% match exceeds 32 bits. BiMark's three numbers are 83.0 / 30.3 / 16.
On CNN/DailyMail summarization, BERTScore is 30.48 versus 30.54 unwatermarked and 30.27 for BiMark; MPAC at δ=3.0 falls to 26.53. In a pure zero-bit setting at 1% FPR and 50 tokens, TPR is 96.94%, a hair above KGW (96.51%) and SynthID (94.2%). Reserving 2 of 10 layers for detection drops 32-bit match rate to 71.17%, still far above BiMark's 19.4%.
If the goal is a user-level ID in generated text without wrecking fluency, this is the paper to read. The capacity bottleneck in unbiased multilayer watermarking is "one bit per token plus hard voting." Spreading plus soft decoding makes 32-bit exact recovery usable. Detection and tracing can be split: zero-bit layers answer presence, the rest answer identity. Code is public.
The cost is also clear. Logits must be modified at sampling time; a black-box API cannot be stamped after the fact. ECC enumeration stops at 32 bits. The contribution is engineering: spread-spectrum and soft decoding from communications, applied to LLM watermarks. There is no new information-theoretic bound.
There is no standalone limitations section. The appendix is candid: at 30% synonym substitution, Qu et al. (δ=3.0) slightly wins on short messages, 25.90% versus 19.74% for 12-bit at 200 tokens. One reason is the unbiased design's window of 2, so one substitution poisons the next two positions; biased methods can use a window of 1. After DIPPER paraphrasing with lexical and order diversity both at 20, 16-bit match rate is 49.02%. Generation used 4-bit-quantized LLaMA-3-8B, so absolute perplexity should not be trusted. There are no adaptive or key-aware removal attacks. Main numbers stop at 32 bits on English news continuation. Chinese, code, and dialogue are unreported.