PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Semantic Narrowing: Robust and Efficient LLM Watermarking with Hamming Neighborhoods

Zewen Sun, Tongyang Zhao, Liyao Xiang, Mingxuan Ma, Lingzhe Wang, Zhiyuan Li

arXiv:2609.37218v1cs.CRcs.AI

TL;DR

Existing semantic watermarks can impose preferences misaligned with context-dependent natural continuations, narrowing semantic freedom and increasing resampling. HammingMark centers acceptance on the preceding sentence’s hash and uses coarse hashing to preserve diverse continuations. Across open-ended and constrained tasks, it reports strong detectability and robustness with near-unwatermarked quality and low sampling cost.

  • Problem

    Existing semantic watermark methods impose watermark-specific preferences that may not align with context-dependent natural continuations, excluding plausible options and narrowing generation.

    Source: §1 · p. 2

  • Method

    HammingMark uses the preceding sentence’s semantic hash as a dynamic center for Hamming-neighborhood acceptance, with coarse many-to-one hashing allowing diverse continuations to remain valid.

    Source: §1 · p. 2, §3.2 · p. 4

  • Results

    Across open-ended and constrained tasks, HammingMark achieves strong detectability and robustness with near-unwatermarked quality; it requires 2.2 sampled candidates per accepted sentence, a 72.8% reduction versus the most sampling-efficient existing method.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    The context-aligned constraint and coarse hashing reduce semantic narrowing while preserving flexibility across open-ended and constrained generation tasks.

    Source: §1 · p. 2, §6 · p. 10

    HammingMark depends on semantic-encoder quality and sentence segmentation, and rejection sampling may still incur cost in highly restrictive contexts or under strict matching thresholds.

    Source: §5 · p. 10

Abstract

from arXiv · show

Semantic watermarking improves robustness against watermark removal attacks by embedding detectable signals into sentence-level representations. However, existing watermarking methods typically impose watermark-specific semantic preferences on generated sentences without explicitly accounting for the highly non-uniform and context-dependent semantic preference of LLM generation. When these two preferences are poorly aligned, many natural continuations become incompatible with the watermark, causing semantic narrowing: reduced semantic freedom, increased resampling cost, and potential degradation on tasks with strict semantic requirements. To alleviate this problem, we propose HammingMark, which uses the semantic hash of the preceding sentence as a dynamic center and accepts candidates whose hashes fall within its Hamming neighborhood. Defining watermark validity over a Hamming neighborhood in compact hash space retains a larger fraction of naturally likely semantic continuations. The coarse many-to-one hash mapping further allows diverse semantic realizations to remain watermark-valid. Experiments on C4 and BookSum show that HammingMark achieves strong robustness, high detectability, and near-unwatermarked generation quality, requiring only 2.2 sampled candidates per accepted sentence,a 72.8% reduction compared with the most sampling-efficient existing method. On more complex tasks with strict semantic constraints, HammingMark achieves the highest detection rates with the highest or tied-highest ROUGE-L scores, demonstrating its effectiveness in balancing watermark detectability and generation quality under constrained generation settings.

1 Introduction

Existing semantic watermark constraints can conflict with context-dependent natural continuations, narrowing semantic freedom and increasing resampling. HammingMark adapts validity to the preceding sentence’s semantics while retaining diverse continuations.

1 Introduction

  • Poorly aligned watermark constraints can reject plausible, high-probability continuations, increasing repeated sampling and risking semantic distortion.The problem is particularly severe in constrained tasks, where acceptable continuations are already limited.Source: §1 · p. 2
  • Natural next-sentence generation favors a context-dependent set of plausible continuations, whereas prior methods typically use randomly positioned semantic regions.This mismatch motivates adapting the watermark constraint to local context.Source: §1 · p. 2
  • HammingMark centers watermark acceptance on the preceding sentence’s semantics, allowing naturally preferred and semantically diverse continuations to remain valid.Its coarse many-to-one hash mapping preserves flexibility for elaboration, contrast, and topic shifts.Source: §1 · p. 2
  • HammingMark requires 2.2 sampled candidates per accepted sentence, a 72.8% reduction compared with the most sampling-efficient existing method.Experiments on open-ended and constrained tasks show strong detectability and robustness with reduced semantic restriction and resampling overhead.Source: §1 · p. 2

2 Related Work

Prior semantic watermarks use predefined regions or similarity constraints that may not match natural discourse. HammingMark instead centers a coarse Hamming neighborhood on the preceding sentence’s hash.

2 Related Work

  • SemStamp and KSemStamp use selected semantic regions, while SimMark imposes a fixed inter-sentence similarity interval that can exclude plausible discourse transitions.The interval may also be sensitive to paraphrasing, even when meanings are largely preserved.Source: §2 · p. 2
  • Online PMark offers a distortion-free construction but requires costly generator-dependent verification and strict sentence–key alignment; offline PMark removes generator queries but loses that guarantee.Offline PMark selects candidates by agreement with fixed semantic-space preferences, which can disadvantage plausible lower-scoring continuations.Source: §2 · pp. 2–3
  • Figure 1 contrasts predefined regions that may poorly overlap natural generation with HammingMark’s transition-centered neighborhoods and coarse hashing.The figure presents the latter design as better aligned with natural generation while preserving diverse semantic transitions.Source: Figure 1 · p. 3
  • HammingMark centers a Hamming neighborhood on the preceding sentence’s hash; coarse many-to-one hashing lets distinct continuations satisfy the same constraint.This supports flexibility for contrast, elaboration, and topic shifts.Source: §2 · p. 3

3 Method

The method measures how much natural continuation probability a watermark constraint retains, then applies context-centered Hamming acceptance. It also describes why this design reduces semantic narrowing and how sequences are detected.

3.1 Semantic Narrowing under Watermark Constraints

  • The natural acceptance mass α_t measures the probability mass retained by a watermark constraint; its complement, 1 − α_t, quantifies excluded natural mass and semantic narrowing.A smaller α_t indicates poorer alignment with natural generation and more naturally likely continuations excluded.Source: §3.1 · pp. 3–4

3.2 HammingMark: Adaptive Hamming-Neighborhood Acceptance

  • HammingMark hashes sentence embeddings with random-hyperplane projection and accepts a candidate when its hash is within Hamming distance r of the preceding sentence’s hash.The preceding hash centers the acceptance constraint and also supplies one endpoint of the relation statistic used for detection.Source: §3.2 · p. 4

3.3 Why HammingMark Alleviates Semantic Narrowing

  • Natural adjacent sentences tend toward semantic continuity, so HammingMark’s discrete hash-space threshold performs shoulder sampling along an existing transition tendency.The probability of meeting the match threshold increases with semantic similarity; for m = 8 and T = 6, selection favors candidates with six or more matching bits.Source: §3.3 · pp. 4–5
  • Compact many-to-one hashing allows semantically distinct continuations to share a code or fall within the same accepted Hamming neighborhood.Thus, a higher bit match need not mean greater semantic similarity, preserving flexibility for contrast, elaboration, and topic shifts.Source: §3.3 · p. 5

3.4 Sequence-Level Detection

  • Sequence detection hashes sentences and scores adjacent matches using Edge Vote or Global Bits; calibrated thresholds classify a text without access to the generation model.Global Bits retains partial evidence from transitions that fall below the match threshold after semantic-preserving perturbations.Source: §3.4 · pp. 5–6

4 Experiments

The experiments evaluate detectability, robustness, quality, sampling efficiency, and performance on complex generation tasks. Across these settings, HammingMark combines strong detection with lower sampling cost and broad natural-candidate acceptance.

4.1 RQ1–RQ3: Detectability, Robustness, and Quality

  • Clean-text TPR@1% is 0.97–1.00 and AUROC is 0.99–1.00; attacked-text TPR@1% is 0.82–0.97, while PPL differs from unwatermarked generation by at most 0.30.Edge Vote is particularly effective for clean-text verification, whereas Global Bits is generally more robust under paraphrasing and rewriting.Source: §4.1 · p. 6, Table 1 · p. 7

4.2 RQ4: Sampling Efficiency and Natural Acceptance

  • HammingMark needs 2.2 sampled candidates and 41.58 generated tokens per accepted sentence, reducing these costs versus SimMark by 72.8% and 77.7%, respectively.Its estimated natural acceptance is 0.58, or about 58% of naturally sampled continuations.Source: §4.2 · pp. 6, 8, Table 2 · p. 8

4.3 RQ5: Performance on Complex Generation Tasks

  • TPR@1% reaches 0.95 on ELI5 and 0.91 on MultiNews, with the highest or tied-highest ROUGE-L on both complex tasks.The comparison is on Mistral-7B.Source: §4.3 · p. 8, Table 3 · p. 8

4.4 RQ6: Visualizing Natural Acceptance under Semantic Constraints

  • For one challenging prompt, HammingMark accepts 99 of 300 natural candidates, compared with 31 for PMark and 2 for K-SemStamp.The visualization is qualitative; semantic narrowing is quantified by retained natural probability mass, not projected area.Source: §4.4 · p. 9, Figure 2 · p. 9

4.5 Ablation Study

  • With identical 37/256 code-space coverage, Random Code has natural acceptance 0.15 versus HammingMark’s 0.58, showing acceptance depends on constraint placement as well as coverage.HammingMark places valid codes around the preceding sentence hash; the observed Random Code value is close to the random-set expectation.Source: §4.5 · p. 9

5 Limitations

HammingMark's reliability depends on stable semantic encoding and sentence segmentation, and its rejection-sampling cost can rise in restrictive contexts.

  • Unstable semantic embeddings can alter hash codes and reduce detection reliability.Source: §5 · p. 10
  • Ambiguous sentence boundaries can also alter hash codes and reduce detection reliability.Source: §5 · p. 10
  • Highly restrictive contexts or strict matching thresholds may increase the cost of rejection sampling.Source: §5 · p. 10

6 Conclusion

The paper concludes that HammingMark reduces the mismatch between watermark constraints and naturally preferred generation, with strong detectability and robustness, near-unwatermarked quality, and low sampling cost. It also reports its AI-use, ethics, and reproducibility practices.

6 Conclusion

  • HammingMark uses context-aligned Hamming acceptance to reduce mismatch while preserving semantic flexibility, and achieves strong detectability and robustness with near-unwatermarked quality and low sampling cost.Source: §6 · p. 10

AI use statement

  • Generative AI tools assisted with language polishing, drafting and revision, formatting, and literature search; the authors reviewed the outputs and take responsibility for the final content.Source: AI use statement · p. 10

Ethics statement

  • The work uses public or appropriately licensed data and standard evaluation protocols, reports no human-subject or sensitive-data collection, and declares no conflicts of interest.Source: Ethics statement · p. 10

Reproducibility statement

  • The appendix provides experimental details and additional analyses intended to support independent reproduction; source code is planned for release upon acceptance.Source: Reproducibility statement · p. 10

A Practical Limitations of Online PMark

Online PMark has a distortion-free generation construction, but verification depends on costly generator resampling and matching generation conditions. The section also defines natural acceptance mass and cautions against relying on geometric reference calculations across differing encoders.

A Practical Limitations of Online PMark

B Semantic Narrowing and Watermark Effectiveness

  • Natural acceptance mass operationally measures excluded natural probability mass, not proportional decreases in semantic diversity, entropy, or generation quality; geometric calculations cannot replace comparisons on shared candidate texts when encoders differ.Source: B Semantic Narrowing and Watermark… · p. 14

B.1 Semantic Narrowing in Partition- and Similarity-Based Methods

Semantic narrowing depends on how watermark-valid regions overlap context-dependent natural continuations, not simply on their nominal size. Hamming neighborhoods and offline maximum-evidence selection illustrate different ways watermark constraints affect candidate coverage.

B.1 Semantic Narrowing in Partition- and Similarity-Based Methods

  • Equal partition masses make the default valid-partition ratio γ = 0.25 imply αt = 0.25, but context-dependent concentration can produce very different acceptance mass.Uniformly choosing valid partitions has expected coverage γ, but does not guarantee that a particular valid set covers that mass.Source: §B.1 · p. 14
  • The cosine-SimMark reference interval [0.68, 0.76] gives a calculation, not measured semantic loss; actual acceptance may be above or below its reference.The calculation applies to normalized representations used for cosine scoring, not Euclidean-SimMark or pre-PCA angles.Source: §B.1 · p. 15

B.2 Semantic Narrowing under Hamming-Neighborhood Acceptance

  • With m = 8 and T = 6, the 37/256 accepted-code fraction is not the actual natural acceptance mass; random-projection averages are not fixed-key rates.The reported mean acceptance of 1/3 and mean excluded mass of 2/3 are averages over random projections.Source: §B.2 · p. 15
  • Equal-sized valid-code sets can cover different natural candidate mass because their codes are arranged differently.HammingMark’s neighborhood is centered on the preceding sentence’s hash; the comparison does not establish higher acceptance in every context.Source: §B.2 · p. 16

B.3 Effectiveness Beyond Enlarging the Acceptance Set

  • Pseudorandomly enlarging valid sets does not ensure useful partial coverage: near-zero mass impedes sampling, while near-total mass leaves little selection signal.Natural continuations may concentrate in a few context-dependent partitions, so nominal set size alone does not determine their overlap with natural generation.Source: §B.3 · p. 17

C Semantic Narrowing in Offline PMark

  • For offline PMark, any candidate pool with multiple evidence levels excludes candidates below the maximum, shifting selection toward watermark-preferred semantic regions.This replaces explicit rejection while preserving sampling efficiency, but still induces semantic narrowing.Source: C Semantic Narrowing in Offline PMark · pp. 18–19

D Locality and Perturbation Stability of Semantic Hashes

  • Shorter angular distance yields fewer expected hash-bit flips, but the locality guarantee is probabilistic over random projections, not deterministic for fixed keys.A transition with a margin of γ matching bits remains valid if the two edited sentences jointly flip at most γ bits.Source: D Locality and Perturbation Stability… · pp. 19–20

E Semantic Diversity within a Hamming Neighborhood

Hamming neighborhoods can include many semantic realizations, and the paper evaluates that breadth using candidate-cluster coverage and fixed-context diversity. It also derives threshold choices from natural matching behavior, with a moment-matched estimate serving as an approximation rather than an exact distributional model.

E Semantic Diversity within a Hamming Neighborhood

  • With m = 8 and T = 6, the neighborhood contains 37 hash cells, each with a continuous family of ambient semantic vectors.This geometric construction explains how short hashes can leave room for distinct semantic directions, but does not imply every vector is a realizable sentence.Source: E Semantic Diversity within a Hamming… · p. 20

F Semantic Coverage of Watermark-Valid Candidates

G Semantic Diversity under Fixed Contexts

  • 0.269 pairwise diversity and 94.7% diversity retention: HammingMark remains close to unwatermarked generation across fixed contexts.The evaluation uses 300 continuations for each of 100 prompts and a held-out embedding model; Random Code retains 64.8%, indicating that code-set size alone does not explain the difference.Source: Table 7 · p. 22, G Semantic Diversity under Fixed… · p. 22

H.1 Exact Threshold from the Natural Match Distribution

  • The choice satisfies the desired distributional-strength requirement while maximizing retained natural acceptance probability, equivalently minimizing expected rejection-sampling cost.Increasing T generally induces a stronger watermark-specific distributional bias, but also rejects more natural probability mass and increases expected sampling cost.Source: §H.1 · p. 24

H.2 Estimating the Matching Threshold from Natural Statistics

  • The moment-matched proxy estimates threshold scale from the natural mean match count, but ignores variation in semantic similarity across contexts.The estimate is not an exact solution for the true generation distribution, whose match-count distribution need not be binomial.Source: §H.2 · p. 25

H.3 Estimated Operating Point for the Default Configuration

The default 8-bit configuration uses T = 6 as an estimated operating point, while empirical fallback remains infrequent under the finite resampling budget. Hash-length experiments identify 8 bits as the best balance between clean detectability and robustness to meaning-preserving perturbations.

H.3 Estimated Operating Point for the Default Configuration

  • 0.6%–2.7% of sentence steps use fallback across evaluated settings with budget B = 16.T = 6 is a reasonable estimated threshold scale for an 8-bit hash, not a measured acceptance rate or exact watermark strength.Source: §H.3 · p. 26, Table 8 · p. 27

I Effect of Semantic Hash Length

  • M = 8 achieves the best balance between clean detectability and tolerance to meaning-preserving perturbations.Four bits provide insufficient discriminative resolution, while increasing hash length gradually reduces robustness under Parrot and DIPPER attacks.Source: I Effect of Semantic Hash Length · p. 27, Table 9 · p. 27

J Reproducibility Details

HammingMark is evaluated on open-ended and constrained-generation tasks with standardized baseline configurations, dataset-specific detection calibration, and paraphrase and rewriting attacks. The experiments also report implementation, sampling, randomness, and hardware settings.

  • C4 and BookSum are evaluated with Mistral-7B-Instruct and Qwen2.5-7B-Instruct, while Multi-News and ELI5 provide constrained-generation tasks.Each task targets 200 tokens; the study samples 500 examples from C4 and BookSum and 100 from each constrained task.Source: J Reproducibility Details · pp. 27–28
  • Baselines use their reported or MarkLLM configurations, and HammingMark uses an 8-bit hash with a six-bit matching threshold.The protocol preserves baseline-specific hyperparameters, resampling procedures, budgets, and fallback strategies where applicable.Source: J Reproducibility Details · pp. 27–28
  • Detection thresholds are calibrated separately by method and dataset on 500 examples disjoint from each test set, with TPR@1%, TPR@5%, and AUROC reported on clean and attacked text.Attacks include Parrot, Pegasus, DIPPER, and API-based rewriting with DeepSeek-V4-Pro.Source: J Reproducibility Details · p. 28
  • Within 5% of 0.75, Global Bits clean-text thresholds remain across evaluated datasets; HammingMark has the smallest relative cross-dataset variation, while KGW-family variation exceeds 30%.The authors regard 0.75 as an empirically motivated default for comparable clean-text settings, but say its false-positive rate should be validated for the intended setting.Source: J Reproducibility Details · p. 28
  • Across three random seeds, detection rates vary by less than one percentage point; experiments run on a single NVIDIA H200 GPU.HammingMark allows up to 16 resampling attempts and uses the latest candidate as fallback if none meets the constraint.Source: J Reproducibility Details · p. 28

K Effect of the Matching Threshold

The matching threshold controls the balance between watermark strength, generation fidelity, and sampling cost, with T = 6 the best empirical trade-off. Cross-key testing shows that detection is strongly specific to the secret projection matrix, although a weaker key-independent signal remains.

K Effect of the Matching Threshold

  • At T = 5, sampling costs 1.3 candidates per accepted sentence and quality stays nearly unchanged, but clean detection and robustness decrease.The weaker constraint lets many naturally generated transitions satisfy the watermark rule.Source: K Effect of the Matching Threshold · pp. 28–29, Table 10 · p. 29
  • At T = 7, robustness under Parrot and DIPPER improves while clean-text detection remains comparable to T = 6, but sampling rises from 2.2 to 6.4 candidates per accepted sentence.The stricter setting also produces a substantially larger perplexity change relative to unwatermarked generation.Source: K Effect of the Matching Threshold · p. 29, Table 10 · p. 29
  • T = 6 provides the best empirical trade-off among watermark strength, robustness, generation fidelity, and sampling efficiency.Lower thresholds admit more natural transitions but provide insufficient watermark separation; higher thresholds strengthen robustness while making sampling more restrictive.Source: K Effect of the Matching Threshold · p. 29, Table 10 · p. 29

L Cross-Key Detection and Key Specificity

  • Replacing the correct projection matrix reduces TPR@1% from 0.99 to 0.08, a 91-percentage-point gap indicating strong key specificity.The cross-key evaluation uses watermarked text generated with R⋆ and measures TPR at a 1% target FPR.Source: L Cross-Key Detection and Key… · p. 29, Table 11 · p. 29
  • The nonzero wrong-key TPR reflects a weaker key-independent component, but it is not a false-positive rate because those samples are watermarked.The paper attributes the residual signal to mild semantic-coherence preference while the dominant signal remains tied to the secret projection geometry.Source: L Cross-Key Detection and Key… · pp. 29–30

M Comparison with Continuous Similarity-Based Acceptance

A continuous cosine-similarity constraint performs worse than HammingMark despite matching its average natural acceptance rate. The Hamming neighborhood is less rigid in continuous semantic space and supports more stable sampling and sequence-level evidence.

M Comparison with Continuous Similarity-Based Acceptance

  • 0.68 TPR@1%, 0.76 TPR@5%, and 0.93 AUROC are achieved by the continuous baseline on clean text, with fallback rising from 1.3% for HammingMark to 7.5%.The cosine threshold is 0.63 and yields approximately the same 0.58 average natural acceptance rate as HammingMark.Source: M Comparison with Continuous… · p. 30
  • Naturally coherent adjacent sentences can make continuous similarity overlap with unwatermarked text, limiting detection; raising the threshold strengthens the signal but tightens the semantic constraint and increases sampling cost.The experiment compares a candidate-to-preceding-sentence cosine threshold with Hamming-code acceptance.Source: M Comparison with Continuous… · p. 30
  • The short, many-to-one hash permits candidates with differing cosine similarities to share neighboring codes, leaving flexibility for contrast, information introduction, and topic transitions.Hamming agreement is not a deterministic hard cutoff on continuous cosine similarity.Source: M Comparison with Continuous… · pp. 30–31
  • HammingMark accumulates agreement across projected bits, and Global Bits retains partial evidence when a modified transition no longer meets the full generation threshold.The paper contrasts this with continuous similarity's reliance on generic coherence and describes the HammingMark signal as key-specific.Source: M Comparison with Continuous… · p. 31

Related papers

Loading 2609.37218v1…