PaperlayerView exact revision on arXiv

Source-linked AI summary

PASA: A Principled Embedding-Space Watermarking Approach for LLM-Generated Text under Semantic-Invariant Attacks

Zhenxin Ai, Haiyun He

arXiv:2605.10977v2cs.CRcs.AI

TL;DR

Existing token-level watermarks can be removed by meaning-preserving rewrites, motivating PASA, which embeds and detects watermarks in latent semantic space using shared randomness and a theoretical framework. PASA is designed to remain robust to semantic-invariant attacks while preserving distortion-free generation, although very strong rewriting can still degrade performance.

  • Problem

    Existing vocabulary-level watermarks are vulnerable to semantic-invariant rewrites that alter token identities while preserving meaning.

  • Method

    PASA embeds and detects watermarks over latent semantic clusters using secret-key-synchronized shared randomness, grounded in a formal attack and optimality framework.

  • Results

    PASA remains robust to semantic-invariant attacks while providing distortion-free generation, with theory characterizing a jointly optimal embedding-detection pair.

  • Takeaways & Limitations

    Semantic-level watermarking enhances traceability against strong paraphrasing attacks and may support AI governance.

  • Takeaways & Limitations

    PASA may degrade under very strong rewriting or watermark-removal attacks that substantially change semantic content and distributional structure.

Abstract

from arXiv · show

Watermarking for large language models (LLMs) is a promising approach for detecting LLM-generated text and enabling responsible deployment. However, existing watermarking methods are often vulnerable to semantic-invariant attacks, such as paraphrasing. We propose PASA, a principled, robust, and distortion-free watermarking algorithm that embeds and detects a watermark at the semantic level. PASA operates on semantic clusters in a latent embedding space and constructs a distributional dependency between token and auxiliary sequences via shared randomness synchronized by a secret key and semantic history. This design is grounded in our theoretical framework that characterizes a jointly optimal embedding-detection pair, achieving the fundamental trade-offs among detection accuracy, robustness, and distortion. Evaluations across multiple LLMs and semantic-invariant attacks demonstrate that PASA remains robust even under strong paraphrasing attacks while preserving high text quality, outperforming standard vocabulary-space baselines. Ablation studies further validate the effectiveness of our hyperparameter choices. Webpage: https://ai-kunkun.github.io/PASA_page/.

1. Introduction

Existing token-level watermarking is vulnerable to meaning-preserving rewrites, motivating a method that jointly provides semantic robustness, distortion-free generation, and principled detection-error control. PASA addresses this gap by embedding and detecting watermarks in latent semantic space through synchronized shared randomness and a formal theoretical framework.

  • Motivation: Token-level watermarking can be undermined by synonym substitution or paraphrasing because these attacks alter token identities while preserving semantics.Such semantic-invariant rewriting may remove the token-level watermark.
  • Motivation: The central design challenge is balancing robustness to semantic-preserving transformations, distortion-free generation, and detection-error control at low false-positive rates.The target includes preserving the original generation distribution under adversarial semantic perturbations.
  • Research gap: Prior semantic-aware approaches indicate that latent embedding geometry can stabilize watermarking, but remain largely heuristic and lack principled guarantees for robustness, distortion, and detection accuracy.Existing theoretical frameworks primarily address token-level watermarking and do not account for meaning-preserving transformations.
  • PASA: PASA elevates watermarking from individual tokens to latent semantic space by coupling token sequences with auxiliary random sequences through semantically synchronized shared randomness.The method is presented as a principled approach under semantic-invariant attacks within a formal theoretical framework.
  • PASA: PASA is designed to provide superior detection performance, distortion-free generation, and robustness to semantic-invariant text modifications.These properties are stated as core outcomes of anchoring shared randomness at the semantic level.

2. A Theoretical Framework for Robust and Distortion-Free Watermarking

This section formalizes watermark embedding and detection for LLM-generated text under semantic-invariant attacks. It frames design as minimizing miss-detection while controlling worst-case false-alarm error and distortion.

  • Watermark Embedding: The framework models watermark embedding through an auxiliary random sequence and a dependence structure that modifies the LLM’s next-token distribution.The resulting watermarked token distribution may differ from the original unwatermarked distribution.
  • Watermark Embedding: An embedding scheme is ϵ-distorted when its watermarked distribution diverges from the original distribution, with ϵ = 0 defining distortion-free watermarking.The distortion measure D can be any metric quantifying distributional dissimilarity.
  • Watermark Detection under Semantic-Invariant Attacks: Detection uses shared randomness and a secret key to test whether the generated token sequence is statistically dependent on the auxiliary sequence.Under H0, the sequence and auxiliary randomness are independent; under H1, they follow the watermarked joint distribution.
  • Watermark Detection under Semantic-Invariant Attacks: Semantic-invariant attacks may arbitrarily modify tokens within an equivalence class while preserving semantics, including token replacement and paraphrasing.The detector is evaluated by worst-case false-alarm and miss-detection errors over attacks induced by the semantic-cluster mapping f.
  • Optimization Problem: The optimization problem minimizes miss-detection error while constraining worst-case false-alarm error below α and exposing trade-offs involving distortion, semantic-cluster output size, and error levels.Although ϵ ≥ 0 is allowed for analysis, the practical distortion-free approach enforces ϵ = 0.

3. Theoretical Foundations and Algorithm

PASA’s theory characterizes the trade-offs among detection error, robustness, and distortion, then derives a jointly optimal, distortion-free semantic-space embedding and detection design. Its practical algorithm uses semantic clusters, secret-keyed auxiliary sampling, in-cluster token generation, and replay-based detection.

  • Theoretical trade-offs: Robustness is inversely related to the semantic cluster count K, while minimum MD error decreases with greater distortion tolerance, a looser FA constraint, or relaxed robustness.When K = |V|, the formulation reduces to the classical non-robust watermarking setting.
  • Jointly optimal scheme: The jointly optimal design embeds and detects watermarks in the latent semantic space, setting ϵ = 0 so the generated distribution remains equal to the original distribution.The optimal auxiliary distribution includes an overflow state ˜ζ to control FA error, while conditioned sampling performs re-normalized in-cluster token sampling.
  • Embedding algorithm: PASA partitions token embeddings into K disjoint semantic clusters and constructs an auxiliary distribution by thresholding cluster probabilities at α, aggregating excess mass into ˜ζ.This construction minimizes MD error while controlling FA error under α.
  • Embedding algorithm: A PRF keyed by the shared secret and the previous w semantic cluster indices samples the auxiliary variable, which selects the branch for sampling the next token.The two-stage procedure preserves the NTP distribution in expectation: Eζt[PXt|xt−1,ζt] = Qt.
  • Detection algorithm: During detection, a surrogate language model reconstructs approximate cluster and auxiliary distributions, replays keyed semantic history, and scores matches between observed clusters and auxiliary variables.Tokens with mismatches or ζt = ˜ζ are skipped, reducing false-alarm error by excluding some low-entropy tokens.

4. Experiments

Experiments evaluate PASA across multiple LLMs, datasets, semantic-invariant attacks, detection metrics, text quality, and runtime. PASA maintains strong detection under token replacement and paraphrasing while preserving generation quality and adding little latency.

  • Experimental Setup: PASA is evaluated on Llama-2-13B and Mixtral-8×7B using proxy SLMs for black-box detection, primarily on realnewslike from C4 and additionally on ELI5.The evaluated attacks include T5-based contextual token replacement and DIPPER paraphrasing with varying strengths.
  • Token-Replacement Detection: 0.9296 TPR@1%FPR under T5-Large on Llama-2-13B exceeds KGW at 0.7350 and DAWA at 0.3300, while PASA reaches 0.9392 AUROC under T5-XXL.On clean text, PASA achieves near-perfect detection across both evaluated watermarking models.
  • Paraphrasing Robustness: 0.5578, 0.5829, and 0.5879 TPR@1%FPR are achieved at DIPPER ORD values 0, 20, and 80, with corresponding AUROCs of 0.8776, 0.9116, and 0.8934.At ORD = 80, DAWA, KGW, Exp-edit, and AWTI fall to 0.0200, 0.3050, 0.1150, and 0.1350 TPR@1%FPR, respectively.
  • Text Quality: 11.44 PPL for PASA is close to the unwatermarked baseline at 12.41 and human text at 10.41, comparable to KGW at 11.81, and lower than Exp-edit at 23.40 and AWTI at 19.77.The results support the stated distortion-free property and PASA also remains effective for long-form generations.
  • Computational Efficiency: 12.93 s →13.35 s generation latency represents a marginal increase of < 0.5 s per sample relative to the unwatermarked baseline.The measurements use 200 sequences of fixed length 300 tokens, and the reported overhead is attributed to semantic clustering and distribution computation.
  • Ablation Studies: K ∈[3, 100] preserves robustness against T5-based token replacement while clean-text detection remains near-perfect across K; increasing w from 3 to 8 under r = 0.5 decreases TPR@1%FPR.The ablations identify hyperparameters balancing robustness, text quality, semantic invariance, and seed synchronization.

5. Conclusion

PASA is a principled watermarking algorithm that operates in latent embedding space to improve robustness against semantic-invariant attacks. It uses disjoint semantic clusters and synchronized sampling with a secret key and auxiliary random sequence to establish shared semantic-level randomness for robust detection.

  • 5. Conclusion: PASA operates in latent embedding space and partitions it into disjoint semantic clusters to improve robustness against semantic-invariant attacks.The algorithm’s watermarking and detection design is grounded at the semantic level rather than solely in token vocabulary space.
  • 5. Conclusion: Synchronized sampling with a secret key and auxiliary random sequence establishes shared randomness at the semantic level for robust detection.This shared randomness is identified as the key mechanism supporting PASA’s robustness during detection.

6. Limitations

PASA remains limited under substantial rewriting or watermark-removal attacks, on very short texts, and when detector and generator tokenizers are incompatible. Proposed mitigations increase semantic modeling complexity, combine multi-level evidence, or deploy multiple lightweight detectors.

  • Attack robustness: PASA may degrade under strong rewriting or watermark-removal attacks that substantially alter semantic content and distributional structure.Richer contextual or sentence-level semantics may improve robustness but increase modeling complexity.
  • Short-text detection: Very short texts yield weaker detection confidence because token-level evidence aggregates fewer observations.Combining token-level evidence with sentence-level or passage-level statistics may alleviate this limitation.
  • Tokenizer compatibility: PASA is most effective when the detector-side SLM is tokenizer-compatible with the generation model.Tokenizer mismatch weakens embedding–detection consistency and reduces cross-family transferability.
  • Tokenizer compatibility: Multiple lightweight SLM detectors from different model families can support verification and suggest the likely source family.A high-confidence response from one detector can verify the watermark and indicate the likely source model family.

Impact Statement · Appendix

Semantic-level watermarking is presented as important for distinguishing machine-generated from human-authored text and for improving traceability against strong paraphrasing attacks. The passage frames this capability as relevant to misinformation mitigation, academic integrity, intellectual-property protection, and AI governance.

  • Impact Statement: Distinguishing machine-generated text from human-authored content is essential as generative models become deeply integrated into society.The passage presents this distinction as a societal need.
  • Impact Statement: Watermarking can help mitigate misinformation by identifying machine-generated content.Misinformation mitigation is listed as one motivation for distinguishing machine-generated and human-authored text.
  • Impact Statement: The ability to distinguish authorship can support academic integrity.Academic integrity is identified as a consequence of reliable authorship distinction.
  • Impact Statement: Authorship distinction can help protect intellectual property.The passage explicitly includes intellectual-property protection among the relevant benefits.
  • Impact Statement: Semantic-level watermarks enhance content traceability against strong paraphrasing attacks.The passage links semantic-level implementation with stronger traceability under paraphrasing.
  • Impact Statement: This traceability provides a reliable tool for AI governance.The passage characterizes semantic-level watermarking as useful for governance.

A. Additional Experimental Results · B. Related Works

Additional experiments show that PASA remains accurate under short sequences, diverse paraphrasing, prompt mixing, and surrogate-model mismatch while retaining moderate detection costs. Related work frames PASA as a semantic-cluster alternative to token-based watermarking, targeting robustness to semantics-preserving rewriting.

  • A. Additional Experimental Results: At 50 tokens, PASA’s ROC-AUC already exceeds 0.95, with near-perfect detection beyond 300 tokens.Detection performance converges rapidly as sequence length increases.
  • A. Additional Experimental Results: On ELI5, PASA maintains near-perfect clean-text detection and superior robustness under T5-Large token-level replacement attacks.The evaluation uses LLAMA-13B-hf and compares ROC-AUC, TPR@1%FPR, and TPR@10%FPR.
  • A. Additional Experimental Results: Under OPT-2.7B paraphrasing and WM-removal, PASA achieves ROC-AUC scores of 0.9931 and 0.9972, respectively, with TPR@1%FPR of 0.9146 and 0.9598.PASA achieves the highest ROC-AUC and TPR@1%FPR across the reported semantic-invariant attack settings.
  • A. Additional Experimental Results: With the human-written prompt prepended, PASA remains reliably detectable on C4, achieving ROC-AUC of 0.9997 and TPR@1%FPR of 0.9899.The mixed-text setting dilutes the watermark signal by placing unwatermarked human text before the watermarked continuation.
  • A. Additional Experimental Results: For LLAMA-2-13B generations, LLAMA-2-7B and TinyLLAMA-1.1B detector-side SLMs each reach ROC-AUC, TPR@1%FPR, and TPR@10%FPR of 1.0000.Instruction-tuned generation causes a smaller but reliable decrease, with ROC-AUC scores of 0.9817 and 0.9879 for LLAMA-2-7B and LLAMA-2-7B-chat detectors.
  • A. Additional Experimental Results: PASA requires 2,892 MB of detection memory and 6.21 × 102 GFLOPs, while the shared generation backbone requires 25,376 MB of GPU memory.Its detection memory is comparable to DAWA and lower than AWTI, while its computational cost is lower than DAWA, SIR, and AWTI.
  • B. Related Works: Prior watermarking work spans green-list, distortion-free, production-oriented, and theoretical approaches, while semantic-invariant attacks remain a central robustness challenge.Green-list methods bias sampling toward secret-key-selected tokens; distortion-free methods preserve the original generation distribution; production systems emphasize efficient detection and low latency.
  • B. Related Works: PASA elevates embedding and verification from individual tokens to semantic clusters, using cluster-level shared randomness to target robustness against semantics-preserving rewriting.This design contrasts with token-based approaches whose signals can decay when paraphrasing changes surface token sequences.

C. Proof of Theorem 1

The proof lower-bounds the missed-detection (MD) error under a worst-case false-alarm constraint by upper-bounding an infimum over admissible paraphrases. It then identifies this lower bound as the optimal objective value, with a distortion-free specialization when ϵ = 0.

  • Lower-bound derivation: The MD error is expressed as 1 − EPXT,ζT[inf ˜xT∈Bf(XT) γ(˜xT, ζT)], enabling a lower-bound derivation.The proof first upper-bounds the infimum term over the set Bf(XT).
  • Optimality: The resulting lower bound on MD error is the optimal objective value of optimization problem (P).The following section proves that a watermark embedding-detection pair achieves this lower bound.
  • Distortion-free case: When ϵ = 0, the bound becomes the minimum MD error for a distortion-free watermarking scheme.This specializes the theorem’s objective to distortion-free watermarking.

D. Proof of Theorem 2

Theorem 2 proves a jointly optimal watermark embedding–detection pair under the specified detector family, with a distortion-free robust method attaining the minimum MD error. The proof concludes by characterizing the induced errors and establishing optimality.

  • Optimal embedding and detection: For each detector f, the corresponding method P* is distortion-free and robust, achieving the minimum MD error β_f,∗ attained from (P).The theorem identifies P* as the optimal embedding method associated with f.
  • Theorem setup: Theorem 2 considers detectors of the form γ(X_T, ζ_T) = 1{f(X_T) = vec2num(ζ_T)}, where vec2num maps sequences to [K] ∪ {ζ̃} with an overflow state.The detector family is parameterized by f, and ζ̃ denotes the overflow state outside [K].
  • Optimal embedding and detection: The conditional token-sequence distribution P*_{X_T|ζ_T} is specified for each x_T according to the detector-dependent condition f(T) = k, with a separate overflow case.The distribution is stated for ζ_T satisfying vec2num(ζ_T) ≠ ζ̃, alongside the overflow-state formulation.
  • Error characterization: The induced MD and worst-case FA errors of the resulting watermarking method are explicitly characterized.These error expressions complete the performance characterization of P*_{X_T,ζ_T}.
  • Optimality proof: The proof establishes optimality by representing any distribution Q_{X_T} as a linear combination of δ_{y_T}.The argument concludes with the statement that optimality is proved.

E. Examples of Watermarked Text

PASA produces natural, fluent, and semantically coherent watermarked continuations across diverse domains while maintaining high text quality and embedding watermark signals.

  • E. Examples of Watermarked Text: Table 9 presents PASA-generated watermarked continuations for prompts spanning wildlife conservation, public policy, technology, history, entertainment, travel, and news reporting.Each example consists of an input prompt and its corresponding watermarked continuation.
  • E. Examples of Watermarked Text: The examples demonstrate natural, fluent, semantically coherent continuations that maintain high text quality while successfully embedding watermark signals.

F. Implementation Details.

PASA experiments use fixed sampling and watermark hyperparameters, generate 200–300-token texts by default, and evaluate DIPPER paraphrasing across escalating lexical and syntactic perturbation levels.

  • Hyperparameters: PASA uses multinomial sampling with top p=1.0 and temperature τ = 1.0, beginning watermark embedding after the first three precursor tokens.The default generated-text length is constrained to 200–300 tokens.
  • Hyperparameters: The configured PASA hyperparameters are K = 4 semantic clusters, synchronization window w = 3, and FA threshold α = 0.4.
  • DIPPER Attack Configurations: DIPPER robustness tests vary Lexical Diversity and Word Order Diversity across three escalating levels: (L=60,O=0), (L=60,O=20), and (L=60,O=80).These represent lexical substitution, moderate reordering, and syntactic restructuring, respectively.
  • DIPPER Attack Configurations: Additional DIPPER evaluations use (L=60, O=40) and (L=60, O=60) to characterize performance under aggressive syntactic and lexical restructuring.
Loading 2605.10977v2…