acceptodds
Under review as a conference paper at ICLR 2027

Alleviating Semantic Narrowing in LLM Watermarking with Hamming-Neighborhood Acceptance

Abstract

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM Watermarking

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_mye6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

HammingMark accepts sentences whose semantic hashes lie near the preceding sentence's hash. This context-dependent constraint aims to preserve natural continuations while creating detectable transition statistics. Experiments evaluate detection, paraphrase robustness, quality, sampling cost, and semantic diversity.

Critical strengths
  1. The practical gains are substantial: 2.2 candidates per sentence versus SimMark's 8.1, strong attacked-text detection, and 94.7% semantic-diversity retention measured with a separate encoder (Tables 1, 2, and 7).
  2. The equal-coverage Random Code control and acceptance-matched cosine baseline help isolate the contribution of context-dependent Hamming neighborhoods (Section 4.5 and Appendix M).
Critical weaknesses
  1. Detection uses dataset-specific calibration on 500 negatives. Appendix J acknowledges that its proposed default threshold has no guaranteed FPR on unseen distributions. False-positive behavior on human text across domains and lengths remains insufficiently characterized for provenance use.
  2. Robustness is demonstrated against generic paraphrasers and rewriting, but not targeted disruption of sentence boundaries or adjacency. Since both detectors depend on adjacent sentence pairs, this leaves a relevant attack surface unresolved.
Questions for authors
  1. With a frozen threshold, what is the actual FPR on held-out human text across domains and document lengths?
  2. How much detection survives sentence deletion, reordering, or merging when output quality is controlled?
Reviewer_LLB3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes sentence-level watermarking through a Hamming-neighborhood acceptance rule on semantic hashes. Experiments assess detection, editing robustness, sampling cost, and semantic diversity, with matched acceptance controls and an independent evaluation encoder.

Critical strengths
  1. The acceptance rule is simple and reduces the reported sampling cost while retaining strong detection performance.
  2. Matched code-size and acceptance-rate controls help test whether the gains come from the proposed neighborhood structure.
  3. The independent-encoder diversity evaluation and explicit fallback measurements make the empirical results more convincing.
Critical weaknesses
  1. Figure 2 represents offline PMark through an all-channel sign-matching condition, while Appendix C describes selection of the strongest candidate from a pool. These are different procedures. The visualization therefore needs to use the actual selection rule before supporting the claimed coverage advantage.
  2. Appendix J uses 500 calibration negatives for a 1% FPR threshold, leaving roughly five observations in the relevant tail. Held-out FPR intervals and sensitivity to calibration-set size are needed to assess whether small detection differences are reliable.
  3. The reported averages leave the behavior on difficult contexts unclear. Acceptance-rate quantiles and sampling cost by context type would help establish whether the proposed explanation holds across topic changes and other difficult sentence transitions. The existing aggregate diversity and fallback results only partly answer this question.
Questions for authors
  1. Does the coverage advantage in Figure 2 persist when PMark uses its actual best-of-pool selection rule?
  2. What held-out FPR intervals result at the 1% threshold, and how sensitive are they to calibration-set size?
  3. How do acceptance rates and sampling costs vary across difficult sentence transitions?
1 comment
AuthorsOpenReview ↗

Final Follow-up on Our Rebuttal and Request for Reconsideration

Dear Reviewer,

As the rebuttal period is coming to an end, we understand your time is limited, but we would sincerely appreciate it if you could revisit our responses when you have a chance.

We have carefully addressed your concerns through clarifying PMark's actual selection rule in Figure 2, additional calibration stability and held-out FPR evaluations, and new experiments analyzing sampling costs and acceptance rates under challenging semantic transitions. These results further support the reliability and efficiency of HammingMark.

We sincerely hope these clarifications and additional results have addressed your concerns, and we would be very grateful if you could reconsider your assessment. If you have any remaining questions or suggestions, please feel free to let us know, and we will respond as promptly as possible.

Thank you again for your valuable time and consideration.

Best regards,
The Authors

Reviewer_9DGaOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper builds on a previous language model watermark algorithm called SemStamp, which the authors point out as having the defects of showing semantic narrowing and also low sampling efficiency. This paper fixes this by introducing course acceptance based on a hamming distance threshold, showing that the improved algorithm HammingMark outperforms a bunch of watermarks in detection robustness and sampling efficiency.

Critical strengths
  1. the algorithm's robustness and efficiency is clear. It outperforms many watermarks by a very significant margin, showing that it can useful for potentially many applications.
  2. the authors have experimented across a wide variety of methods and datasets, including the attack methods, which feels very comprehensive and well-thought.
Critical weaknesses
  1. I am not super sure about the result validity of some of the baselines. For instance, KGW typically in some other prior work perform pretty robust against pegasus and parrot paraphrasers, but in authors' experiments they can be as low as 0.66 - this is a bit concerning to me given that pegasus is usually an easy attack method.
  2. One of the motivation for this algorithm is that it alleviates semantic narrowing. Yet, I don't see any direct experiment on the diversity of the language model generation compared to vanilla model generation and prior works. The Rouge-L advantage in Table 3 also seems very slim. This makes me think that my overall assessment of this paper is that this can potentially be a great watermark but it really does not evidentiate what the title is claiming.
Questions for authors
  1. Can you add a section of all the hyperparameters used by the baselines?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.