PaperlayerView exact revision on arXiv

Source-linked AI summary

PURA: Provably Unbiased and Robust Multi-Bit Watermarking for AI-Generated Text Attribution

Yaofei Wang, Jinyang Guo, Shuchao Du, Chao Wang, Qiyi Yao, Donghui Hu, Weiming Zhang, Nenghai Yu, Kejiang Chen

arXiv:2608.22218v2cs.CR

TL;DR

Existing multi-bit watermarking struggles to preserve the base distribution, carry high-capacity attribution payloads, and remain recoverable after editing. PURA embeds payloads as keyed latent sampling-space offsets and recovers them through soft interval evidence aggregated across tokens, achieving strong high-payload recovery while preserving distributional and text-quality properties. Its robustness analysis covers adaptive attacks and gives exponentially decreasing per-bit error with sequence length, with millisecond-level asymmetric verification.

  • Problem

    Existing multi-bit watermarking struggles to simultaneously preserve the base generation distribution, support high-capacity payloads, and remain recoverable after editing.

  • Method

    PURA encodes payloads through keyed inverse-transform-sampling phase rotations and recovers them by aggregating tokens as soft interval evidence across the sequence.

  • Results

    At 36 bits per 200 tokens, PURA-asymmetric achieves a 91.7% match rate and 99.02% bit accuracy, while remaining close to unwatermarked text in quality and statistical stealth.

  • Takeaways & Limitations

    PURA provides a practical path toward fine-grained attribution through high-payload recovery, broad attack stability, and millisecond-level asymmetric verification.

  • Takeaways & Limitations

    Repeated contexts under the same key may introduce cross-response correlations, and extending guarantees across multiple responses remains future work.

Abstract

from arXiv · show

Fine-grained attribution of AI-generated text is becoming increasingly important for accountability and auditing, yet existing multi-bit watermarking methods still struggle to simultaneously preserve the base generation distribution, support high-capacity payloads, and remain recoverable after editing. We present PURA, a provably unbiased and robust multi-bit watermarking method for text attribution. Instead of perturbing token probabilities directly, PURA embeds payloads in the latent sampling space via keyed inverse transform sampling, and recovers them by treating observed tokens as soft interval evidence and aggregating such evidence across the sequence. This design preserves the base generation distribution exactly while substantially improving recovery stability under post-editing and channel perturbations. Building on this recovery paradigm, we further develop a unified robustness analysis and show that, under bounded attack strength, the per-bit error probability decays exponentially with sequence length. Extensive experiments show that PURA substantially outperforms existing unbiased baselines in the high-payload regime. For example, when embedding 36 bits in 200 tokens, PURA achieves a 91.7\% message match rate, more than three times that of the strongest unbiased baseline, while preserving text quality and remaining statistically close to unwatermarked text, and incurring only millisecond-level verification overhead. Our code is available at

1 Introduction

PURA addresses the challenge of embedding high-capacity, editing-robust attribution information without changing the base generation distribution. It combines latent-space payload embedding with soft-evidence recovery and evaluates the approach across models, datasets, and attacks.

  • Motivation: Fine-grained attribution extends watermarking beyond binary detection to information such as the serving instance, user, generation time, or model version.This information supports accountability, auditing, and compliance.
  • Motivation: Existing multi-bit watermarking must jointly preserve generation distributions, support high payloads, and recover messages after editing.Direct probability perturbations can trade off capacity, robustness, and text quality.
  • Method: PURA encodes structured payloads in latent sampling space, adaptively allocates capacity, and uses locality-preserving coding to limit bit diffusion.Its extraction treats tokens as soft interval evidence and aggregates weak local signals into per-bit statistics.
  • Theory: PURA’s robustness analysis covers generic editing and mechanism-aware directed attacks through structural synchronization and directional evidence channels.The resulting per-bit error bound decays exponentially with sequence length.
  • Results: Over 90% message match rate and over 99% bit accuracy are maintained across 12–36 bits per 200 tokens in asymmetric verification.Evaluation spans C4, Essays, Open-Gen, four model families, and diverse editing and rewriting attacks.

2 Related Work

Related work spans biased and distribution-preserving watermarking, multi-bit attribution, robustness evaluation, mechanism-aware attacks, and linguistic steganography. These approaches reveal recurring trade-offs among recovery, stealth, synchronization, capacity, and attacker assumptions.

  • Watermarking Foundations: Zero-bit watermarking detects whether text is watermarked, while multi-bit methods encode attribution such as user, timestamp, or model-version information.Biased multi-bit methods commonly extend green-list or probability-bias mechanisms.
  • Distribution Preservation: Distribution-preserving methods either key probability reweighting so its expectation matches the original distribution or couple key randomness directly to sampling.The latter line includes Gumbel-max and ITS/EXP-style constructions.
  • Multi-Bit Methods: Biased multi-bit schemes can achieve strong high-payload recovery but typically degrade quality and statistical stealth as payload increases.Examples include MPAC, CTWL, and RS-BH.
  • Multi-Bit Methods: Concurrent MC2Mark and ArcMark also study distortion-free multi-bit watermarking using different embedding and decoding constructions.
  • Robustness and Attacks: Early robustness evaluations use mechanism-agnostic insertions, deletions, substitutions, and paraphrases, with effectiveness largely governed by edit distance or semantic drift.
  • Robustness and Attacks: Mechanism-aware attacks exploit watermark structure, including persistent green-list bias or recoverable secret permutations and key sequences.Some attacks assume fixed permutations or position-wise cyclic keys, while others probe biased watermarks.
  • Robustness and Attacks: Other attacks fine-tune external paraphrasers to move rewritten text away from the watermarked distribution without requiring secret keys or detector feedback.These attacks can still use knowledge of the watermarking mechanism and external models.
  • Related Paradigms: Linguistic steganography prioritizes covert communication and can require exact decoder-side synchronization, while asymmetric constructions relax model access but may reduce capacity.

3 Problem Formulation and Preliminaries

The paper formulates multi-bit watermarking as payload-bearing autoregressive generation followed by verification from either the source model or a compatible proxy. PURA uses inverse transform sampling and latent phase offsets while evaluating recovery under generic and mechanism-aware attacks.

  • 3.1 Multi-bit Watermarking and Verification Settings: The encoder generates an autoregressive sequence while embedding a binary payload m∈{0, 1}^L_m into the generation process.
  • 3.1 Multi-bit Watermarking and Verification Settings: At verification, the system observes either the original text or an edited version and outputs a recovered payload.Bit accuracy measures correctly recovered bits, whereas match rate measures complete-payload recovery.
  • 3.1 Multi-bit Watermarking and Verification Settings: Symmetric verification uses the source model, while proxy-based verification uses a compatible same-family model when source weights are unavailable.Both settings share the embedding and recovery pipeline, but proxy verification introduces source–verifier distribution mismatch.
  • 3.2 Autoregressive Generation and ITS: At each autoregressive step, the language model defines a next-token distribution conditioned on the preceding context.
  • 3.2 Autoregressive Generation and ITS: Inverse transform sampling fixes a vocabulary order, constructs a cumulative distribution, and maps a uniform latent sample to a token interval.Each sampled token corresponds to an interval on [0, 1).
  • 3.2 Autoregressive Generation and ITS: PURA exploits rotational invariance of the uniform distribution so adding a modulo-1 phase offset leaves the induced token distribution unchanged.This permits payload encoding in latent sampling space without altering base generation probabilities.
  • 3.3 Threat Model: The threat model allows attackers to know the watermarking algorithm but not the secret key or detection feedback, distinguishing non-adaptive generic editing from stronger attacks.
  • 3.3 Threat Model: Recovery is expected to retain nontrivial per-bit information when sufficient synchronized evidence survives editing.

4 Method

PURA embeds multi-bit payloads in latent sampling space rather than token probabilities, combining entropy-aware scheduling, Gray-coded anchoring, keyed ITS, and soft-evidence extraction. This preserves the base generation distribution while supporting robust recovery from interval evidence aggregated across the sequence.

  • Distribution-Preserving Embedding: PURA uses ITS to encode payload bits by shifting latent sampling anchors while preserving the induced next-token distribution.The payload changes the latent anchor, not token probabilities; keyed ITS samples over a secret permutation of the vocabulary.
  • Context-Scheduled Capacity: Context-gated scheduling selects usable steps, bit-width, and cyclic payload positions according to local next-token entropy.Low-entropy steps are skipped or assigned fewer bits because their wider token intervals blur sector boundaries.
  • Latent Anchoring: Gray-coded latent anchoring maps selected bits to equal-width sectors and rotates a context-derived base phase to the chosen sector center.Adjacent Gray-coded sectors differ in one bit, reducing multi-bit diffusion from small latent shifts.
  • Keyed Sampling: Keyed ITS over a permuted vocabulary maps each latent anchor to a token while keeping the token-to-latent correspondence secret.The secret permutation helps prevent targeted replacements based on a public model and fixed latent ordering.
  • Soft-Evidence Extraction: Extraction treats each observed token as a latent interval, converts interval compatibility into sector weights and bit-level LLRs, then aggregates evidence for each payload position.The sign of the aggregate estimates the bit, while its magnitude guides lightweight parity-based repair.

5 Theoretical Analysis

PURA’s analysis models recovery through bounded local evidence and synchronized survival under editing, yielding exponential reliability when average drift remains positive. It separates generic attacks from adaptive attacks, where desynchronization and directional misleading evidence can reduce the recovery margin.

  • Embedding Model: PURA generates tokens with anchor A_t = U_t ⊕ Δ_t, while skip mode falls back to baseline sampling when a_t = 0.The anchor combines a keyed context phase with a payload-dependent offset; skipped steps carry no payload anchoring.
  • Unbiasedness: Theorem 5.1 establishes computational unbiasedness for a single invocation under secure domain-separated keyed derivations and a uniformly sampled secret key.The proof uses fresh uniform phases, rotational invariance, and inverse transform sampling to reproduce the original next-token distribution.
  • Bit-Level Analysis: PURA analyzes each encoded bit through verifier-side evidence steps, local LLRs, bounded normalized contributions, and an aggregate decision statistic.The construction uses a martingale whose increments are bounded because clipped local evidence lies within a fixed range.
  • Generic Attacks: Under TM0, synchronized evidence contributes average strength ρμ_c, while unsynchronized evidence has zero conditional mean.Structural survival rate ρ measures the fraction of evidence remaining synchronized after editing; if none survives, ρμ_c is defined as zero.
  • Generic Attacks: Proposition 5.1 gives exponential reliability when the average drift has a uniform positive lower bound Γ.The bound applies Azuma–Hoeffding concentration to the martingale formed from centered watermark evidence.
  • Adaptive Attacks: Under TM1, adaptive attackers can reduce the drift through lower structural survival ρ or negative directional evidence μ_adv.The resulting bound separates structural desynchronization from directional evidence bias against the true bit.

6 Experiments

Experiments evaluate PURA across payload sizes, datasets, model families, downstream tasks, and editing attacks. PURA maintains high-capacity recovery while preserving stealth and quality, with robustness supported by soft evidence, Gray coding, and parity repair.

  • Capacity, Accuracy, and Efficiency: PURA retains 91.7% match rate and 99.02% bit accuracy at 36 bits per 200 tokens, outperforming unbiased and biased baselines in the high-payload regime.At 36 bits, StealthInk reaches 0.5% match rate, BiMark 28.9%, and RS-BH with δ=3.0 reaches 81.4%.
  • Capacity, Accuracy, and Efficiency: PURA maintains high match rates across four model families and three datasets, with Essays exceeding 95% match rate even at 36 bits.The reported stability is attributed to usable evidence steps retained by the entropy gate and alignment between source and proxy models.
  • Text Quality and Stealth: 50.23% classifier accuracy versus 50.00% for unwatermarked text indicates near-random detectability, while downstream quality remains within 0.16 BERTScore, 0.09 ROUGE-1, and 0.43 BLEU.These results compare PURA with unwatermarked text on detection, summarization, and English-to-Romanian translation.
  • Robustness to Post-Editing Attacks: PURA keeps bit accuracy above 85% across six attack types at 36 bits, whereas RS-BH and BiMark have near-zero match rates under DIPPER at 30 bits.The evaluated attacks include insertion, deletion, substitution, copy-paste, sentence shuffling, and DIPPER paraphrasing.
  • Analysis of Adaptive Attacks: Under TM1 attacks, match rate falls to 8.69%–22.67% primarily through structural desynchronization, while directional evidence remains within [−0.009, +0.008].The evaluation covers four adaptive rewriting attacks and reports raw 18-bit payloads with SPC repair disabled.
  • Analysis of Adaptive Attacks: Bit accuracy rises monotonically with sequence length and exceeds 98% for all four TM1 attacks at 5000 tokens, consistent with exponential error decay.The paper also notes that stronger key-directed adaptive attacks remain an open practical problem, with the oracle stress test outside TM1.

7 Conclusion

PURA combines unbiased latent-space multi-bit watermarking with soft-evidence recovery and a robustness framework covering adaptive attacks. Experiments and theory support high recovery performance, exponentially declining per-bit error, and practical verification.

  • PURA encodes payload bits as latent sampling-point phase rotations and recovers them by aggregating interval evidence into per-bit confidence.
  • PURA’s robustness framework covers adaptive attackers with watermark knowledge and yields a per-bit error bound that decays exponentially with sequence length.
  • Millisecond-level asymmetric verification supports practical fine-grained attribution deployment.

8 Limitations and Future Work

The paper identifies deployment boundaries involving repeated contexts, insufficient recovery evidence, evaluation scope, and potential misuse. It also cautions that stronger key-directed adaptive attacks remain an open challenge.

  • Reusing a key across responses with repeated contexts may introduce cross-response correlations, and extending guarantees to multiple responses remains future work.
  • Short texts and extensive rewriting can reduce exact-message recovery, leaving bit-level evidence useful for preliminary auditing or candidate narrowing.
  • The evaluation focuses on English text with source–proxy pairs sharing a tokenizer and vocabulary; cross-tokenizer and multilingual verification remain future work.
  • Watermarking may enable surveillance or censorship, and probabilistic detection should not be treated as conclusive evidence or used alone for punitive decisions.

B.1 Setup

The setup defines PURA’s autoregressive sampling process, keyed latent offsets, context-derived randomness, and distinct-query conditions. Rotational invariance and random-function assumptions establish fresh uniform latent phases for watermarked steps.

  • The baseline generator samples each token x_t from the model distribution π_t(·) over vocabulary V.
  • PURA derives a base phase and payload offset from the local context, with Δ_t=(s_t+0.5)/K_t and K_t=2^a_t.
  • Distinct context inputs are enforced for watermarked steps, while skip steps sample directly from π_t(·).
  • Adding an independent offset to a uniform latent phase preserves uniformity through rotational invariance.
  • Under distinct adaptive context queries, random-function outputs are independent and uniform, yielding fresh base phases at watermarked steps.

B.4 Proof of Computational Unbiasedness

The computational-unbiasedness proof replaces keyed derivations with random functions, uses rotational invariance to preserve uniform latent sampling, and concludes that PURA matches the baseline distribution under the PRF assumption.

  • The proof models domain-separated keyed derivations as secure pseudorandom functions and analyzes a corresponding random-function hybrid.
  • The real PURA process uses shifted latent phases on watermarked steps and exact baseline sampling on skip steps.
  • PRF security makes the real process computationally indistinguishable from the random-function hybrid.
  • In the hybrid, the payload offset is independent of the base phase, so rotational invariance keeps the shifted phase uniform.
  • The resulting conditional token distribution and full-sequence distribution equal the baseline distributions.

C Proofs for Robustness

The appendix establishes symmetry properties of PURA’s finite Gray codebooks and uses them to prove centering of verifier statistics under TM0. These results support unbiased recovery analysis for the specified arities.

  • Gray-code symmetry: For every valid observation and local coordinate, a circular rotation permutes candidate anchors while swapping the corresponding sector classes.This permutation property is the key symmetry used in the subsequent centering proof.
  • Centering under TM0: Under TM0, the verifier models phase as conditionally uniform at unsynchronized steps, given verifier history, synchronization, and the observed interval.The proof conditions on the relevant history and interval before applying the symmetry transformation.
  • Centering under TM0: The symmetry exchanges the numerator and denominator of the local likelihood contribution, reversing its sign while preserving the clipping operation.Because paired configurations have opposite contributions, the expected local statistic is zero.
  • Centering under TM0: With fixed c_i and B_ε, the same zero-expectation conclusion applies to Z_t, and averaging over the observed interval completes the proof.The result is obtained after transferring the sign-reversal argument from the local LLR contribution to Z_t.

D Supplementary Experimental Analysis

Supplementary analyses examine a privileged key-aware oracle, entropy-aware gating, finite-support evidence kernels, and the implementation procedures for PURA encoding and decoding.

  • Key-aware oracle stress test: The privileged oracle is outside TM1 because it uses secret-key-dependent verifier evidence to choose replacements that reduce aligned directional evidence.It is parameterized by edit budget r and candidate search width k.
  • Key-aware oracle stress test: As r and k increase, the oracle lowers structural survival and makes directional drift more negative, reducing the effective recovery margin.The oracle attacks both recovery channels rather than only structural synchronization.
  • Key-aware oracle stress test: 47.35% bit accuracy occurs at r = 0.4, k = 15, where the effective margin becomes negative.At r = 0.3 and k = 15, the margin is 0.071; the stress test identifies the boundary described by the theory.
  • Entropy-aware gating: The full Adapt 1-2-3 gating strategy consistently outperforms fixed or restricted adaptive variants, especially under editing attacks.The analysis attributes this pattern to allocating more payload capacity to high-entropy regions for robust extraction.
  • Implementation: PURA’s supplementary algorithms combine entropy-aware gating with anchor-based inverse transform sampling for embedding and token-to-LLR conversion for soft decoding.The decoding procedure aggregates bit-level evidence for reliability-aware message recovery.
  • Implementation: At each active step, the decoder derives an index and latent interval from the keyed rank, then updates payload positions using the reconstructed arity.The implementation also accumulates total LLRs before deciding recovered payload bits.
Loading 2608.22218v2…