Synchronization-Free Algebraic Fingerprints for Large Language Models: From Autoregressive to Diffusion Models

• URL: http://arxiv.org/abs/2607.16648v1
• Date: Sat, 18 Jul 2026 05:43:22 GMT
• Title: Synchronization-Free Algebraic Fingerprints for Large Language Models: From Autoregressive to Diffusion Models
• Abstract summary: Large Language Models (LLMs) have created an urgent need for reliable watermarking methods.<n>We propose a novel synchronization-free watermarking scheme in which every congruence consists of a single binary generated from a pair of neighbouring tokens.
• Score: 1.1213359816349566
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) have created an urgent need for reliable watermarking methods that enable attribution of generated text while remaining robust to editing and paraphrasing. We propose a novel synchronization-free watermarking scheme in which every watermark consists of a single binary congruence generated from a pair of neighbouring tokens. For each token pair, a cryptographic hash determines an evaluation point of a Reed--Solomon polynomial representing the secret identity, while the parity of the polynomial evaluation determines the watermark bit embedded into the second token of the pair. Since each congruence is self-contained and depends only on the local token pair, the proposed construction is naturally resistant to insertions, deletions, and token reordering. We analyse the recovery problem from an algebraic perspective, discuss several decoding algorithms suitable for different identity sizes, and model watermark corruption as a Binary Symmetric Channel. The analysis shows that reliable recovery requires only a small redundancy even for relatively high token corruption rates. Unlike existing block-based watermarking schemes, the proposed method avoids synchronization problems while providing a flexible framework for embedding both short and long secret identities.

Related papers

• Tracing Provenance and Detecting Tampering with Complementary LLM Watermarks [68.64050157343334]
  Existing watermarks preserve provenance under editing, but this same robustness allows an adversary to alter critical content while retaining attribution.<n>We introduce an innovative watermark that jointly provides provenance and tamper evidence.<n>The signals share the same mechanism but use independent keys and different seeding windows over normalized text, making one resilient to edits and the other sensitive to reader-visible changes.
  arXiv  Detail & Related papers  (2026-08-13T01:55:16Z)
• How to Watermark the RLWE Homomorphic Ciphertexts [1.342943588774946]
  homomorphic encryption (HE) schemes based on the Ring Learning with Errors problem have rapidly developed.<n>Most existing HE schemes focus primarily on the feasibility and efficiency of homomorphic computation.<n>We propose a watermarking technique for RLWE ciphertexts.
  arXiv  Detail & Related papers  (2026-07-28T02:53:30Z)
• AliMark: Enhancing Robustness of Sentence-Level Watermarking Against Text Paraphrasing [55.03371974830747]
  AliMark is a framework that reformulates sentence-level watermarking as a bit sequence encoding and alignment problem.<n>We show that AliMark substantially outperforms state-of-the-art baselines under diverse paraphrasing attacks.
  arXiv  Detail & Related papers  (2026-05-28T06:30:43Z)
• UniMark: Unified Adaptive Multi-bit Watermarking for Autoregressive Image Generators [1.7507301683087861]
  We propose a training-free, unified watermarking framework for autoregressive image generators.<n>method introduces three core components: textbf Semantic Grouping (ASG), textbfBlockwise Multi-bit.<n>Experiments on three AR models demonstrate that method achieves state-of-the-art performance in image quality (FID), watermark detection accuracy, and multi-bit message extraction.
  arXiv  Detail & Related papers  (2026-04-12T16:22:24Z)
• MC$^2$Mark: Distortion-Free Multi-Bit Watermarking for Long Messages [62.982950935139534]
  Multi-bit watermarking can embed identifiers into generated text, but existing methods struggle to keep both text quality and watermark strength while carrying long messages.<n>We propose MC$2$Mark, a distortion-free multi-bit watermarking framework for reliable embedding and decoding of long messages.
  arXiv  Detail & Related papers  (2026-02-15T07:29:06Z)
• dgMARK: Decoding-Guided Watermarking for Diffusion Language Models [5.43345665278304]
  dgMARK is a decoding-guided watermarking method for discrete diffusion language models.<n>dgMARK steers the unmasking order toward positions whose high-reward candidate tokens satisfy a simple parity constraint.<n> Watermarks are detected via elevated parity-matching statistics.
  arXiv  Detail & Related papers  (2026-01-30T13:51:20Z)
• An Ensemble Framework for Unbiased Language Model Watermarking [60.99969104552168]
  We propose ENS, a novel ensemble framework that enhances the detectability and robustness of unbiased watermarks.<n>ENS sequentially composes multiple independent watermark instances, each governed by a distinct key, to amplify the watermark signal.<n> Empirical evaluations show that ENS substantially reduces the number of tokens needed for reliable detection and increases resistance to smoothing and paraphrasing attacks.
  arXiv  Detail & Related papers  (2025-09-28T19:37:44Z)
• Edit Distance Robust Watermarks via Indexing Pseudorandom Codes [29.69428894587431]
  Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees.<n>We aim for watermarks which satisfy: (a) undetectability, a cryptographic notion introduced by Christ, Gunn & Zamir (2024) and (b) robustness to channels which introduce a constant fraction of adversarial insertions, substitutions, and deletions.
  arXiv  Detail & Related papers  (2024-06-04T04:03:17Z)
• Watermarking Language Models for Many Adaptive Users [47.90822587139056]
  We study watermarking schemes for language models with provable guarantees. We introduce multi-user watermarks, which allow tracing model-generated text to individual users. We prove that the undetectable zero-bit scheme of Christ, Gunn, and Zamir (2024) is adaptively robust.
  arXiv  Detail & Related papers  (2024-05-17T22:15:30Z)
• Provably Secure Disambiguating Neural Linguistic Steganography [66.30965740387047]
  The segmentation ambiguity problem, which arises when using language models based on subwords, leads to occasional decoding failures.<n>We propose a novel secure disambiguation method named SyncPool, which effectively addresses the segmentation ambiguity problem.<n> SyncPool does not change the size of the candidate pool or the distribution of tokens and thus is applicable to provably secure language steganography methods.
  arXiv  Detail & Related papers  (2024-03-26T09:25:57Z)
• Duwak: Dual Watermarks in Large Language Models [49.00264962860555]
  We propose, Duwak, to enhance the efficiency and quality of watermarking by embedding dual secret patterns in both token probability distribution and sampling schemes. We evaluate Duwak extensively on Llama2, against four state-of-the-art watermarking techniques and combinations of them.
  arXiv  Detail & Related papers  (2024-03-12T16:25:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.