PaperlayerView exact revision on arXiv

Source-linked AI summary

Anchor-ECC: Local Integrity Checking for Watermarked LLM Outputs via Error-Correcting Codes

Zewei Deng, Muhammad Siddeek, Liyan Xie, Mohamed Seif, Mengdi Wang, H. Vincent Poor, Andrea Goldsmith

arXiv:2609.38722v1cs.CRcs.CL

TL;DR

Document-level watermarking offers limited evidence about whether and where a watermarked passage was edited, even when an edit changes its meaning. Anchor-ECC combines error-correcting constraints, boundary anchors, and decoding to detect and localize edits. Across three models, its approximate-hard setting reports block-level TPR above 0.996 and FAR at or below 0.0754 while retaining strong global identifiability.

  • Problem

    Existing watermarking detectors largely make document- or segment-level decisions, offering limited evidence about whether and where post-generation edits changed a watermarked passage.

    Source: §1 · p. 1

  • Method

    Anchor-ECC embeds joint VT and Hamming constraints in block payloads separated by boundary anchors and uses decoding to recover blocks and localize suspicious edits.

    Source: §1 · pp. 1–2

  • Results

    Across Qwen3-8B, Mistral-7B-Instruct-v0.3, and OPT-125M, the approximate-hard setting achieves block-level TPR above 0.996 and FAR at or below 0.0754, with ROC-AUC of at least 0.9985.

    Source: §4 · p. 11

  • Takeaways & Limitations

    The decoder narrows block alarms to candidate token positions, insertion gaps, or boundary sites, and question-aware edit results show local evidence remains informative beyond random token perturbations.

    Source: §4 · p. 11

    Boundary recovery is analyzed under a sparse independent edit model with per-token edit rate ϵ ≪ 1; the probability of two consecutive anchors both being deleted is on the order of ϵ^2.

    Source: §2.4 · p. 6

Abstract

from arXiv · show

LLM watermarking has become an effective approach to distinguishing AI-generated text from human-written text by embedding detectable patterns during generation. However, a small post-generation edit may change the meaning of the text without removing its overall watermark signal, creating a risk that the modified content is still attributed to the original model. We propose Anchor-ECC, which incorporates the error-correcting code (ECC) constraints and explicit boundary anchors into the watermark structure and pairs them with a dynamic-programming decoder to detect and localize post-generation edits. Across Qwen3-8B, Mistral-7B-Instruct-v0.3, and OPT-125M, the approximate-hard setting achieves about 99.7% block-level true positive rate (TPR) with at most 7.6% false alarm rate (FAR) for edit detection under mixed insertions, deletions, and substitutions, while preserving the distinction between watermarked outputs and unwatermarked text. Additional quality experiments identify lower-perplexity configurations that retain strong edit-detection performance. Together, these results extend LLM watermarking from source identification to local integrity verification while supporting configurable trade-offs between detection reliability and generation quality.

1 Introduction

Document-level watermarking can miss local post-generation edits that alter a statement while leaving it associated with the original generator. Anchor-ECC adds blockwise structural evidence and decoding to support local integrity checking alongside watermark attribution.

1 Introduction

  • Local insertions, deletions, or substitutions can change a claim while leaving the document-level watermark detectable, creating attribution risk.Existing methods largely make document- or segment-level decisions rather than determining whether and where a watermarked passage changed.Source: §1 · p. 1
  • Anchor-ECC combines VT constraints for insertions and deletions with Hamming-type constraints for substitutions, placing each codeword in a short block followed by a boundary anchor.The two constraint types provide complementary sensitivity to different edit types.Source: §1 · p. 1
  • A global dynamic-programming decoder recovers latent block boundaries, flags inconsistent blocks, and narrows alarms to candidate edit sites.Localized alarms direct semantic or human review to short passages that may contain spoofing edits.Source: §1 · p. 2
  • The paper evaluates detection against matched baselines across watermark strengths, using synthetic and question-aware benign and spoofing edits, and examines identifiability and realization cost.Source: §1 · p. 2

1.1 Related Work

  • Unlike span detectors assuming largely intact text [Zhao et al., 2025, Pan et al., 2025] and edit-localization schemes [Xie et al., 2025, Deng et al., 2026], Anchor-ECC combines explicit anchors and Hamming constraints for substitutions.Source: §1 · p. 1, §1.1 · p. 2

2 Proposed Watermarking and Edit Detection Methods

Anchor-ECC embeds blocks whose payloads satisfy joint error-correcting constraints and whose boundaries are marked by dedicated anchors. Its generator maintains feasible payloads, while a global decoder parses edited text, tests block consistency, and narrows alarms to candidate edit locations.

2.1 Error-Correcting Code Design

  • The feasible codeword set C = Va(n) ∩ H combines VT constraints for insertion–deletion sensitivity with Hamming parity constraints for substitution sensitivity.The VT syndrome parameter is fixed in the experiments, and the Hamming constraint uses the standard parity-check matrix over the original coordinate order.Source: §2.1 · pp. 3–4

2.2 Anchor-ECC Watermarking

  • Each block carries n watermark-bit symbols followed by a boundary anchor from a disjoint bucket, with anchors marking block boundaries rather than encoding bits.The vocabulary is divided into B0 and B1 payload buckets and a separate boundary-anchor pool.Source: §2.2 · p. 4
  • For watermark identifiability, the detector tests each possible starting phase and combines block-code distance, anchor mismatches, unmatched symbols, and a length-derived block estimate.It uses the phase with minimum cost to define the global watermark score; higher scores indicate stronger consistency with the keyed ECC watermark.Source: §2.2 · pp. 4–5

2.3 Pretrained-Model Realization and Distortion Reduction

  • Generation restricts or biases the next-token distribution toward codeword-compatible bits, while soft biasing retains alternative-token probability and semantic-balanced splitting preserves lexical diversity.Adaptive completion uses the codebook’s multiple valid codewords to guide bit choices; with finite bias, the generator uses the closest matching codeword prefixes if a sampled prefix becomes infeasible.Source: §2.3 · p. 5

2.4 Edit Detection

  • The dynamic-programming decoder globally minimizes block-decomposition cost over segmentations, codewords, and boundary states, rather than relying only on observed anchors.This handles deleted or substituted boundaries and scales approximately linearly with sequence length under the fixed experimental search parameters.Source: §2.4 · p. 6
  • A block is suspicious when its boundary is not intact or its minimum edit distance to C exceeds threshold r; alignment candidates narrow each alarm to payload positions, insertion gaps, or boundary sites.The experiments use r = 0 for hard and approximate-hard watermarking, r = 2 for δ = 2, and r = 1 for δ = 5.Source: §2.4 · pp. 6–7

3 Numerical Experiments

The experiments test Anchor-ECC on three models using LFQA answers and synthetic and question-aware edits. They report strong block detection across models, compare detection with baselines, and assess watermark identifiability and generation quality.

Experimental Setup

  • The evaluation tested Qwen3-8B, Mistral-7B-Instruct-v0.3, and OPT-125M on 256 independent English LFQA prompts, applying synthetic insertions, deletions, and payload-bit substitutions at edit rates 0.2, 0.4, 0.6, and 0.8.Comparisons included KGW-based methods, two combinatorial watermark families (CW-AB and CW-4), and Sync-VT.Source: §3 · pp. 7–8

Cross-model Local Detection

  • At δ=20, block-level TPR exceeded 0.996 for all three models; FAR was below 0.008 for Mistral and OPT and 0.075 for Qwen3.Candidate coverage ranged from 0.781–0.802 at δ=20 across the models.Source: §3 · p. 8, Table 1 · p. 8

Block-level Detection Results

  • At δ=20, Anchor-ECC reached 0.9966 TPR/0.0754 FAR, versus 0.7464/0.1029 for Sync-VT and 0.3438/0.0259 for WaterSeeker.The comparison uses the same Qwen3/LFQA block-detection protocol across watermark strengths.Source: §3 · p. 8, Table 2 · p. 9

LLM-guided Sparse Edits

  • In Table 3’s balanced Qwen3 LLM-guided edit sample, increasing bias from δ=5 to δ=20 raised TPR from 0.8261 to 0.9193 and coverage from 0.4169 to 0.5040, while lowering FAR from 0.1814 to 0.0921.Source: §3 · p. 9, Table 3 · p. 9
  • 90.3% of edited blocks at δ=5 and 91.1% at δ=20 had changed bucket sequences; the detector flagged 86.90% and all of these blocks, respectively.Overall TPR also counts edited blocks whose final bucket sequences remain unchanged, such as same-bucket token replacements.Source: §3 · p. 9

Watermark Identifiability

  • ROC-AUC was at least 0.9985 across the three model families and watermark strengths for distinguishing watermarked text from matched unwatermarked generations and human answers.The repeated ECC structure supports document-level watermark identification alongside block-level edit localization.Source: §3 · p. 9, Table 4 · p. 10

Boundary Allocation and Perplexity

  • 35.7–59.6%: the boundary-1/8 allocation reduced conditional PPL at every model–bias setting at δ=20.The comparison is against the compact-150 allocation under the same generation settings.Source: §3 · p. 10, Table 5 · p. 10

4 Conclusion

Anchor-ECC uses ECC constraints, boundary anchors, and global decoding to provide local evidence of post-generation edits. The conclusion reports high block-level detection across three models while retaining global watermark identifiability, with quality–reliability trade-offs across configurations.

4 Conclusion

  • Across Qwen3-8B, Mistral-7B-Instruct-v0.3, and OPT-125M, approximate-hard detection achieved block-level TPR above 0.996 and FAR at or below 0.0754.Global identifiability remained strong, with ROC-AUC of at least 0.9985.Source: §4 · p. 11
  • The decoder narrows each block alarm to candidate token positions, insertion gaps, or boundary sites, giving reviewers a smaller region to inspect.The conclusion reports that question-aware benign and spoofing edits also provide informative local evidence beyond random token perturbations.Source: §4 · p. 11
  • Soft watermarking reduces PPL with some loss in local detection reliability, while a larger boundary pool reduces conditional PPL by 22.1–52.2% under soft settings.The larger pool carries greater risk of boundary corruption; the options provide different quality–reliability operating points.Source: §4 · p. 11

A.1 Global Watermark Score

The verifier evaluates candidate phases using a heuristic cost and selects the minimum-cost phase.

A.1 Global Watermark Score

  • J_s counts the complete blocks remaining after the first s structural symbols are skipped.The passage defines J_s as floor((T′ − s)/(n + 1)).Source: §A.1 · p. 13
  • The heuristic phase cost combines payload and boundary disagreement, unmatched symbols at the sequence ends, and recovered-versus-estimated block-count disagreement.The block-count comparison uses J_s and the length-based estimate b_J.Source: §A.1 · p. 13
  • The verifier uses the minimum cost across phases in Eq. (3).Source: §A.1 · p. 13

A.2 Decoder Complexity and Practical Runtime

The memoized dynamic-programming decoder has stated complexity and practical runtimes for clean text and the strongest evaluated attack.

A.2 Decoder Complexity and Practical Runtime

  • O(Le|C|n(n + e)) is the decoder’s total complexity; with n = 7, e = 3, and |C| = 10, practical scaling is approximately linear in L.Source: §A.2 · p. 14
  • 31.6 ms for clean text and 61.0 ms under the strongest evaluated attack are the decoding times for an 18-block sequence.The reported times include candidate-location extraction and were measured on an Intel i7-13650HX.Source: §A.2 · p. 14

A.3.1 Synchronization-Assisted VT Baseline

Table 7 reports Sync-VT results on Qwen3/LFQA under a shared mixed-edit protocol.

A.3.1 Synchronization-Assisted VT Baseline

  • Table 7 covers Sync-VT on Qwen3/LFQA, macro-averaged over four edit rates and k ∈ {1, 2, 3}.Source: Table 7 · p. 14
  • The table reports substitution results for completeness, although the original Sync-VT construction addresses insertion and deletion.Source: Table 7 · p. 14

A.3.2 Full KGW-Based Baseline Comparison

Table 8 presents a full LFQA sweep comparing Anchor-ECC with KGW-based baselines.

A.3.2 Full KGW-Based Baseline Comparison

  • Table 8 covers Anchor-ECC and KGW-based baselines on the full LFQA sweep.Source: Table 8 · p. 14
  • Each Table 8 entry is macro-averaged over four edit rates and k ∈ {1, 2, 3}.Source: Table 8 · p. 14

A.3.3 Single-Edit Breakdown

In the single-edit setting, Anchor-ECC maintains near-perfect block-level TPR while compared baselines show lower recall or higher FAR. The appendices describe question-aware source generation and LLM-guided editing, where candidate coverage is lower than block TPR.

A.3.3 Single-Edit Breakdown

  • Anchor-ECC maintains near-perfect block-level TPR across single edits, while KGW and AOL have lower recall with higher FAR and WaterSeeker is conservative but low-recall.Each affected block receives one uniformly sampled insertion, deletion, or substitution.Source: §A.3.3 · p. 15, Table 9 · p. 15

A.4 Source Text Generation for Question-Aware Editing

  • 256 independent English LFQA prompts provide source continuations, with Qwen3-8B generations used to examine edits that can spoof certainty, attribution, numerical claims, or definitional boundaries.The setup uses chat-template prompting with thinking disabled and adaptive Anchor-ECC generation.Source: §A.4 · p. 15

A.5 LLM-Guided Editing and Downstream Risk Assessment

  • The LLM-guided editor receives Qwen3-8B continuations at δ = 5 and δ = 20, plus indexed edit units and one of six benign or malicious editing motivations.The six motivations group grammar polish, clarity improvement, and style softening as benign, and claim distortion, stance shift, and source spoofing as malicious.Source: §A.5 · p. 17
  • The editor outputs local JSON edit instructions that are applied to saved token IDs, while detector inputs exclude both editor instructions and ground-truth edit locations.This gives exact block-level ground truth while allowing edit choices to be guided by semantic motivations.Source: §A.5 · p. 17
  • Each motivation-and-bias stratum contains 216 evaluated blocks, and candidate coverage is consistently lower than block TPR.Edited and clean counts provide the respective denominators for TPR and FAR.Source: §A.5 · p. 18, Table 11 · p. 18
Loading 2609.38722v1…