PMark: Towards Robust and Distortion-free Semantic-level Watermarking with Channel Constraints

• PMark defines proxy functions that map sentences to scalar values, providing a unified analytical framework for semantic-level watermarking.Source: §1 · p. 2
• PMark preserves high text quality with PPL 4.37–4.71 while improving paraphrase robustness by up to 14.8% over the prior best semantic-level watermark and 44.6% over the prior best token-level scheme.Source: §1 · p. 2
• The online version uses 20% of the token-consumption resources of prior SOTA semantic-level watermarking schemes, while the offline version consumes less.Source: §1 · p. 2
• Multiple channel constraints address sparse watermark evidence, strengthening robustness against adversarial attacks.Source: §1 · p. 2
• The paper evaluates PMark across multiple text-watermarking tasks, datasets, and model backbones to assess effectiveness and efficiency.Source: §1 · p. 2

• The paper focuses on zero-bit watermarks that embed one detectable signal, unlike multi-bit schemes that encode a message.Source: §2 · p. 2
• SWM models the next semantically complete sentence conditioned on preceding sentences, while token probabilities compose the sentence-level distribution.Source: §2 · p. 3
• Because the sentence space is infinite, sampling-based SWM draws i.i.d. candidate sentences and selects a watermark-bearing output.Source: §2 · p. 3
• Single-sentence distortion freedom requires the watermarked marginal distribution, averaged over watermark keys, to equal the original model distribution.Source: §2 · p. 3

3.1 PROXY FUNCTION

• 3.1 PROXY FUNCTION: A proxy function maps each semantically complete sentence to a real-valued score, enabling rule-based selection in the otherwise intractable sentence space.Source: §3.1 · pp. 3–4

3.2 ANALYSIS OF THE BASELINE

• 3.2 ANALYSIS OF THE BASELINE: Rejection-based SemStamp samples candidates, selects a valid green-region sentence, and generally distorts the natural distribution unless its green-mass condition holds for every proxy value.Source: §3.2 · p. 4
• 3.2 ANALYSIS OF THE BASELINE: SemStamp’s randomly partitioned embedding space does not guarantee the distortion-free condition, with analogous issues for k-SemStamp and SimMark.Source: §3.2 · p. 4

3.3 SINGLE-CHANNEL DISTORTION-FREE SAMPLING

• 3.3 SINGLE-CHANNEL DISTORTION-FREE SAMPLING: The single-channel construction uses cosine similarity between sentence embeddings and a pivot vector as its proxy score.Source: §3.3 · p. 5
• 3.3 SINGLE-CHANNEL DISTORTION-FREE SAMPLING: Median partitioning of sampled candidates into equal proxy-score halves yields a watermarking procedure proven distortion-free.Source: §3.3 · p. 5

4.1 MULTI-CHANNEL CONSTRAINED GENERATION (ONLINE)

• Multiple channels address the sparse evidence and paraphrase vulnerability of single-channel semantic watermarking by applying orthogonal proxy constraints.Single-channel evidence can degrade detectability under adversarial attacks, motivating the multi-channel extension.Source: §4.1 · p. 5
• Online PMARK samples candidates from the natural next-sentence distribution, filters them sequentially through randomly keyed channel constraints, and uniformly samples from the final set.The method uses orthogonal pivots, with each channel defined by a proxy function based on the pivot and sentence embedding.Source: §4.1 · p. 5
• The multi-channel sampler is distortion-free because every candidate retained at one stage belongs to the next-stage candidate set with probability 1.The generation pipeline is presented as multi-channel constrained generation, followed by uniform sampling from the final candidate set.Source: Figure 2 · p. 6, §4.1 · p. 6

4.2 SOFT-z-TEST DETECTION (ONLINE)

• Online detection reconstructs each sentence’s candidate distribution, estimates channel medians with the Harrell–Davis estimator, and smooths evidence around the estimated thresholds.A soft-count-based z-test then aggregates potential watermark bits across channels and sentences.Source: §4.2 · p. 6

4.3 OFFLINE PARTITION WITH A PRIOR THRESHOLD

• The offline variant adopts zero as the prior median, uses the same watermarking rate for the z-test, and selects the candidate maximizing total watermark evidence.This removes repeated sampling for median estimation and allows detection without querying the generator.Source: §4.3 · p. 7

5.1 EXPERIMENT SETUP

• The evaluation uses 500 samples each from C4 and BOOKSUM with OPT-1.3B and Mistral-7B-v0.1, measuring PPL, detectability (TPR@1%, AUC), and robustness to sentence- and word-level attacks.Source: §5.1 · p. 7

5.2 ROBUSTNESS AND TEXT QUALITY (RQ1 & RQ2)

• Online PMARK shows near-SOTA paraphrase robustness, while offline PMARK remains above 90.8% TP@FP1% and consistently ranks second to the online version.The comparison covers Pegasus, Parrot, GPT-3.5-turbo, and back-translation settings across the reported evaluations.Source: §5.2 · pp. 7–8, Table 1 · p. 8
• 98.2% and 99.0% TP@FP1% are achieved by online PMARK under 15% word deletion and synonym substitution, while offline PMARK reaches 95.2% and 98.6%.Multiple channel constraints address sparse watermark evidence that makes existing semantic-level methods vulnerable to word-level attacks.Source: §5.2 · pp. 8–9

5.3 COMPUTATION CONSUMPTION (RQ3)

• Online PMARK reaches 98% TP@FP1% with N = 8 and 3 channels, whereas offline PMARK requires a budget of 16 for practical detectability.The authors attribute the offline budget requirement to prior-deviation risk under limited sampling and note that Bayesian probability estimation is left for future work.Source: §5.3 · p. 9, Table 2 · p. 9
• PMARK offers the reported best SWM trade-off: offline mode uses fewer tokens than k-SemStamp with competitive robustness, while online mode has the highest robustness with 20% additional token consumption.SemStamp provides high semantic-attack robustness but requires 1694.4 tokens per sentence, while SimMark and k-SemStamp have separate efficiency or robustness limitations.Source: §5.3 · p. 9, Table 3 · p. 9

6 CONCLUSION

• PMARK unifies semantic-level watermarking through proxy functions, introduces multi-channel constraints for denser evidence, and targets distortion-free generation with improved robustness.The paper describes online PMARK as theoretically distortion free under mild prerequisites and offline PMARK as lower-cost with low distortion.Source: §6 · p. 10
• Experiments across multiple datasets and model backbones show PMARK consistently outperforms existing semantic-level watermarking baselines in text quality and robustness.Source: §6 · p. 10

A USE OF LLMS

• The study identifies semantic-level dynamic random-seed generation as an open challenge and adopts pre-defined random seeds to achieve single-shot distortion-freeness.Source: §6 · p. 10, A USE OF LLMS · p. 15

B DETAILED DEFINITION AND ADDITIONAL PROOFS

• The appendix establishes that the sentence space is countable, enabling formal analysis over semantically complete sentences represented as finite token sequences.A prime-exponent encoding injects finite token sequences into the natural numbers.Source: B DETAILED DEFINITION AND ADDITIONAL… · p. 15
• Distortion-free sampling requires uniform proxy-value probabilities, while nonuniform probabilities produce unequal scaling across proxy values.Source: B DETAILED DEFINITION AND ADDITIONAL… · p. 16
• Increasing the number of channels b improves robustness under the same attack strength, with typical settings yielding a theoretical signal-to-noise ratio of at least 2.8.The stated typical parameters are b = 4, T ≈ 10–20, and ϵ ≤ 0.3.Source: B DETAILED DEFINITION AND ADDITIONAL… · p. 17

C.1 TOKEN-LEVEL TEXT WATERMARKING

• Token-level watermarks are vulnerable to meaning-preserving paraphrases, whereas sentence-level methods improve paraphrase robustness but often incur rejection-sampling distortion and lack rigorous guarantees.Source: C ADDITIONAL RELATED WORK · p. 17, §C.1 · pp. 17–18, §C.2 · p. 18

D.1 ROBUST RANDOM SEEDS FOR SEMANTIC-LEVEL WATERMARK

• Existing semantic-level schemes can reduce key randomness, and PMARK uses pre-defined random seeds for single-shot distortion-freeness while leaving dynamic semantic-level seed generation unresolved.Source: §C.2 · p. 18, §D.1 · pp. 18–19

D.2 ROBUSTNESS TO CROSS-SENTENCE PARAPHRASING ATTACK

• Online PMARK achieves TPR@FPR1% > 75% across backbones and datasets under paragraph-level paraphrasing with w = 3.The attack setting is described as one where most existing watermark methods are nearly powerless.Source: §D.2 · p. 19, Table 4 · p. 19
• Offline PMARK maintains highly competitive performance against baselines under the same extreme cross-sentence paraphrasing attack.Source: §D.2 · p. 19, Table 4 · p. 19
• The evaluation uses GPT-3.5-turbo to rewrite text while avoiding repeated words or phrases and allowing sentence merging or reordering.Source: §D.2 · p. 20
• An example remains detected as watermarked after attack, with both the original and attacked text labeled True.Source: §D.2 · p. 20

E ANALYSIS OF EXISTING SWM METHODS

• SemStamp and related methods shuffle proxy-value regions using seeds derived from the previous sentence, while SimMark uses a fixed cosine-similarity interval.Source: E ANALYSIS OF EXISTING SWM METHODS · p. 20
• SimMark’s fixed Green Region Gt = [0.68, 0.76] risks having no valid candidate and may generalize poorly across settings.Source: E ANALYSIS OF EXISTING SWM METHODS · p. 20

F OFFLINE ALGORITHM

• Offline PMARK selects the candidate with the highest multi-channel watermark-evidence score, combining channel indicators with channel weights.Source: F OFFLINE ALGORITHM · p. 21
• When channel proxy signs are independent and balanced, offline PMARK selects uniformly and has zero distortion; near-balance yields bounded, empirically negligible distortion.Source: F OFFLINE ALGORITHM · p. 21

G.1 BASELINES

• The study compares PMARK with token-level baselines and adapted semantic-level methods using matched generation limits and sampling settings.OPT-1.3B and Mistral-7B-v0.1 are used as backbone models, with semantic-level methods limited to 12 generated sentences.Source: §G.1 · pp. 21–22
• PMARK uses all-mpnet-base-v2, four orthogonal pivot channels, a sample budget of N = 64, and fixed detection parameters.Generation uses temperature 0.7, top p 0.95, and max new sentences 12; detection uses δ = 0.001 and K = 150.Source: §G.1 · p. 22

G.2 ADVERSARIAL ATTACKS

• Robustness tests apply sentence-level Pegasus, Parrot, and GPT paraphrasing, Llama-3.1-8B back-translation, and word deletion or synonym substitution at 5%, 15%, and 30%.The back-translation attack is noted as potentially biased and unstable in some cases.Source: §G.2 · p. 22

H.2 QUALITY OF WATERMARKED TEXT

• Additional perplexity results compare existing methods across different benchmarks and backbones, as presented in Figures 7, 8, and 9.Source: §H.2 · p. 22

H.3 SENSITIVITY OF HYPERPARAMETER

• Figure 10 provides additional OPT-1.3B hyperparameter analyses from which similar conclusions can be deduced.The supplied passage does not specify the individual parameter values or outcomes.Source: §H.3 · p. 22

H.4 CASE STUDY

• PMARK demonstrates superior text quality and robustness across backbones and datasets, producing more diverse sentences while retaining evidence after paraphrase attacks.The qualitative comparison is presented against SemStamp cases.Source: §H.4 · p. 22
• The offline PMARK case study illustrates fixed-prior-median generation and soft z-test detection, with corresponding generation and detection algorithms.The algorithms define channel-specific proxy functions and sample candidate sentences during generation.Source: Figure 6 · p. 23, §H.4 · p. 23

H.1 ROBUSTNESS TO ADVERSARIAL ATTACKS

• Robustness under various attacks is evaluated with results in Tables 5 and 6; Table 5 reports baseline and PMARK results on OPT-1.3B and Mistral-7B using BOOKSUM, including back-translation and word-level attacks.Source: §H.1 · p. 22, Table 5 · p. 23

I BROADER IMPACTS AND LIMITATIONS

• PMARK’s limitations include fixed random seeds, a still-large sampling budget, and reliance on consistent sentence segmentation between generation and detection.The paper suggests sliding windows, pseudorandom error-correcting codes, and segmentation-independent semantic watermarking as future directions.Source: I BROADER IMPACTS AND LIMITATIONS · pp. 23–24
• The paper frames PMARK as a distortion-free and robust semantic-level watermarking approach for copyright protection and content attribution.This broader-impact claim is stated as the paper’s positioning rather than as a quantified deployment result.Source: I BROADER IMPACTS AND LIMITATIONS · p. 23
• Additional perplexity figures cover Mistral-7B and OPT-1.3B on BOOKSUM and C4, while Figure 10 reports further OPT-1.3B hyperparameter analysis.The supplied captions identify the evaluated model-dataset combinations but do not provide cell-level results.Source: Figure 7 · p. 24, Figure 8 · p. 25, Figure 9 · p. 25
• Figures 11–14 provide qualitative cases for Mistral-7B and OPT-1.3B on BOOKSUM and C4, including channel-level watermark-evidence indications.Figure 11 describes evidence strength and cases with no valid evidence in a channel.Source: Figure 11 · p. 26, Figure 12 · p. 26, Figure 13 · p. 27