Provably Robust Multi-bit Watermarking for AI-generated Text

Motivation and goals

• Existing methods often detect only whether text is watermarked, while multi-bit approaches struggle with long-message accuracy, scalability, or extraction cost.For example, [19] requires about 8 hours to extract a 32-bit message, whereas Yoo et al. [71] reaches only 73.6% extraction probability for 16 bits.Source: §1 · p. 2

Proposed approach

• The method partitions a message into bit segments and pseudo-randomly assigns segments to generated tokens, distributing redundancy while avoiding exhaustive message enumeration.This design targets the trade-off between watermark accuracy and computational efficiency.Source: §1 · p. 2
• Two refinements improve the scheme: dynamic programming balances token allocation across segments, and error-correction codes increase tolerance to edits.Balanced assignment reduces erroneous segment extraction, while ECC corrects errors introduced by text manipulation.Source: §1 · p. 2

Theoretical guarantee

• The work derives a probabilistic robustness guarantee ensuring correct extraction when total insertion, deletion, and substitution edits remain within a specified bound.The resulting robustness bound for each generated paragraph can be efficiently computed in practice.Source: §1 · pp. 2–3

Experimental validation

• Under the same setting, copy-paste attacks leave a 90% match rate for our method, versus 32% for Yoo et al. [71].The method tolerates edits within an average edit distance of 17 for each paragraph under the same setting.Source: §1 · p. 3
• Under the same setting, the method retains a 90% match rate under copy-paste attacks versus 32% for Yoo et al. [71], tolerates average edit distance 17, and negligibly changes PPL.It extracts a 32-bit message from a sentence in 0.6 seconds, whereas [65] requires 8,300 seconds.Source: §1 · p. 3

2.1 Zero-bit watermarking

• Zero-bit watermarking detects machine-generated text by biasing green-list tokens and statistically testing their prevalence against unwatermarked text.Source: §2.1 · p. 3

2.2 Multi-bit watermarking

• Multi-bit watermarks embed and extract message bit strings, enabling applications such as content source tracing beyond zero-bit detection.Source: §2.2 · p. 4
• Message-enumeration methods can be accurate but require evaluating all 2^b possible messages during extraction, creating substantial computational cost.Source: §2.2 · p. 4
• Bit-assignment methods are efficient but may allocate too few or no tokens to some segments, causing incorrect bit extraction; increasing segment size degrades text quality.Source: §2.2 · p. 4
• Distortion-free and block-based multi-bit schemes have practical robustness limitations, including poor discrimination for long messages and failures after sentence deletion.Source: §2.2 · p. 4
• Concurrent ECC-based watermarking works differ in setting or guarantee: some target public detection or code generation, while this scheme targets perfect message extraction for general AI text.Source: §2.2 · p. 4

2.3 Background on Reed-Solomon codes

• Reed-Solomon codes encode k finite-field symbols into n symbols and guarantee recovery when no more than t encoded symbols are changed.Source: §2.3 · p. 5

3.1 Problem definition

• A multi-bit watermark algorithm consists of embedding a message K into LLM-generated text and extracting K from a given text.Source: §3.1 · p. 5
• The message K is an arbitrary bit string of length b, while the generated token sequence S has length T.Source: §3.1 · p. 5
• The formal setup includes an LLM, message K, and prompt token sequence P=[P_0 ··· P_{N−1}].Source: §3.1 · p. 5
• The generated sequence S consists of tokens S_0 through S_{T−1}, with T denoting its length.Source: §3.1 · p. 5
• The finite field GF(q^m) is a Galois field of order q^m.Source: §3.1 · p. 5

3.2 Design goals

• Correctness requires the embedded message to be extracted accurately, with the relevant conditional probability equal or close to 1.Source: §3.2 · p. 5
• Robustness requires reliable extraction after insertion, deletion, replacement, synonym substitution, or paraphrasing, when edit distance D(S,S′) is at most η.Source: §3.2 · p. 5
• Efficiency requires embedding and extraction to be computationally efficient.Source: §3.2 · p. 5

4.1.1 Insights from previous works

• Prior methods suffer from weak robustness or imbalanced token allocation, causing long-message segments to receive few or no tokens and reducing extraction accuracy [13] [18] [71].Continuous token groups can lose an entire bit when a sentence is removed, while pseudo-random assignment improves edit robustness but may leave some segments underrepresented.Source: §4.1.1 · pp. 5–6

4.1.2 Key ideas of our watermark design

• Packing multiple bits into segments reduces the number of token groups while each token simultaneously embeds every bit in its segment, substantially balancing per-bit coverage.For a 16-bit message in 200 tokens, segment packing changes highly uneven per-bit allocation into the listed balanced allocation [12,12,12,12,14,14,14,14,12,12,12,12,12,12,12,12].Source: §4.1.2 · p. 6

4.1.3 Further improvements

• The method further uses frequency-balanced token-to-segment mapping and Reed-Solomon coding, which guarantees correct final decoding when no more than t = floor((n-k)/2) segments are extracted incorrectly.Smaller segment counts improve accuracy but increase extraction cost, whereas larger counts reduce complexity with a slight accuracy sacrifice.Source: §4.1.3 · p. 7, §4.1.2 · p. 7

4.2 Design details of multi-bit watermarking

• The detailed pipeline selects an error-correction code, computes a secret-keyed balanced mapping, biases a hash-selected green list during generation, and extracts each segment by maximizing green-token counts.The secret key protects the mapping and green-list selection from attackers; extraction then decodes the recovered segment sequence with the selected Reed-Solomon code.Source: §4.2 · p. 8

4.3 Theoretical robustness analysis

• Theorem 4.1 establishes a non-trivial provable robustness bound for every generated sentence under token insertion, deletion, or substitution within an edit-distance budget.The theorem states that, within the specified budget, extracted information is manipulated only with a small probability; the robust bound is the largest budget guaranteeing a chosen extraction-error rate.Source: §4.3 · p. 9
• The robust bound can be computed by binary search using Algorithm 4, and is practical for typical settings with n ≤ 10 and η_max = 40.The stated complexity is O(n·η_max^4 + t·log η_max), and computation typically completes within a few seconds on a modern CPU.Source: §4.3 · p. 9

4.4 Security analysis

• The security analysis introduces the random oracle model (ROM) as the cryptographic framework for modeling hash functions.It defines a random oracle H mapping arbitrary binary strings to n-bit outputs.Source: §4.4 · p. 10
• The security proof grants the adversary adaptive hash queries and a candidate secret key, then bounds success using the random oracle’s independent uniform outputs.This stronger model supports the conclusion that observing watermarked text does not enable practical secret-key recovery.Source: §4.4 · p. 10
• With output length n≥128 and adversary computation power Q≤2^64, the probability of successfully extracting the secret key is approximately 2^-64, which is negligible.Source: §4.4 · p. 10
• Under the random oracle model, spoofing is theoretically infeasible because the target user’s hash output is independent of outputs for observed accounts.The stronger adversary may query hashes for k known user IDs, but gains no advantage in predicting the target user ID’s hash value.Source: §4.4 · p. 10

5.1 Experiment setup

• The evaluation uses match rate, bit accuracy, edit distance, robust bound, and perplexity across three datasets and three public LLMs, with a default 20-bit message and 200-token generation.The robust bound is defined as the average per-text theoretical robustness bound, with error probability threshold α = 10^-3.Source: §5.1 · pp. 10–11, §5 · p. 10

5.2 Main results

• The method achieves match rates exceeding 90% across OpenGen, C4, and Essays datasets while remaining relatively consistent across Llama2, Guanaco, and Falcon models.Match rate decreases as message bit length increases because less redundancy is available for each bit.Source: §5.2 · p. 11
• The watermark causes only minor quality degradation, with similar perplexity distributions for watermarked and unwatermarked text and subtle human-rated degradation.For Falcon, perplexity primarily shifts from [6,10] to [6.5,10.5] after watermarking.Source: Figure 5 · p. 11, §5.2 · p. 12, Table 4 · p. 12
• At 24 bits, the method reaches a 96.0% match rate versus 30.4% for Yoo et al. [71], while extracting in under 1 second compared with over 100 seconds for [19].Extraction for enumeration-based baselines becomes exponentially slower as bit length grows, making some 32-bit experiments infeasible.Source: §5.2 · p. 12, Table 2 · p. 12
• The selected Reed-Solomon configuration consistently achieves the highest match rate across 16-, 20-, 24-, and 32-bit settings by balancing segment count, code rate, and recovery rate.More recovery bits can increase ECC recovery ability but also enlarge the number of segments and worsen token-assignment imbalance.Source: §5.2 · pp. 12–13, Table 3 · p. 12

5.3 Robustness results

• Under copy-paste attacks, the method retains a 90.0% match rate versus 32.4% for Yoo et al. [71], and it outperforms that baseline by 60% under word deletion.Across six attacks, segment assignment reduces extraction errors by mitigating imbalance.Source: §5.3 · p. 13, Figure 6 · p. 13
• Error-correction coding raises accuracy to 86.4% under homoglyph attacks and improves match rate by 18% under paraphrasing, where the method still reaches 80%.ECC corrects errors in some segments when attacks reduce green tokens, improving resistance to message distortion.Source: §5.3 · p. 13

• The method achieves correctness, robustness, multi-bit capacity, and efficiency simultaneously for AI-generated text watermarking.Its design combines pseudo-random segment assignment with two improvement techniques and establishes provable robustness against adversarial edits.Source: §6 · p. 13

• Under the pseudo-random hash assumption, incorrect candidate values are modeled probabilistically to derive decoding-error distributions.Source: A Proof of Robustness Theorem 4.1 · pp. 17–18
• The proof shows that edits within a predetermined distance yield a bounded probability of more than t incorrectly decoded segments.The bound uses an ECC scheme characterized by (n,k,t) and a target error probability α.Source: A Proof of Robustness Theorem 4.1 · p. 17
• Each insertion, deletion, or edition changes at most two existing and two added bigrams, so edit distance η bounds both changes by 2η.Source: A Proof of Robustness Theorem 4.1 · p. 17
• The analysis computes single-segment decoding probabilities after token additions and deletions, then recursively combines them across segments.The single-segment function depends on allocated tokens, green tokens, and added or deleted tokens.Source: A Proof of Robustness Theorem 4.1 · p. 18
• The procedure selects a Reed–Solomon scheme using code-rate, recovery-rate, and segment-count constraints before computing the robust bound.Source: A Proof of Robustness Theorem 4.1 · p. 19
• The resulting recursive probabilities provide an upper bound on extraction error after edits within distance η.Source: A Proof of Robustness Theorem 4.1 · p. 19

• Algorithms 3–5 select the optimal Reed–Solomon scheme, compute each paragraph’s provable robustness bound, and construct the PI array.Source: B Pseudo-code of our procedures · p. 19

• Boroujeny et al. [7] works well mainly for small message bit lengths, but its difficulty distinguishing neighboring messages increases as length grows.Source: C Analysis of Boroujeny et al. [7] · p. 19
• The analysis derives the neighboring-message collision probability as (1−2^(1−b))^(17×k), because one normal token is divided into 17 binarized tokens.Source: C Analysis of Boroujeny et al. [7] · p. 19
• For messages longer than 20 bits, neighboring-message texts can become nearly indistinguishable, limiting reliable extraction regardless of the method used.At b=20 and k=200, the cited example gives probability approximately 0.9935 for identical generated texts.Source: C Analysis of Boroujeny et al. [7] · pp. 19–20
• The compared procedure uses an algorithm for computing robust bounds over edit-distance cases and segment-error probabilities.Source: C Analysis of Boroujeny et al. [7] · p. 20