🤖 AI

ChainMark: Model-Free LLM Watermarking with Closed-Form Calibration

ChainMark introduces a model-free, active watermarking scheme that partitions the vocabulary into keyed states to enforce hard Markov transitions, enabling closed-form calibration of detection parameters and achieving provable robustness against translation and substitution attacks without requiring access to the generating language model.

Original authors: Chengheng Li-Chen, Kyuhee Kim

Published 2026-07-22

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Chengheng Li-Chen, Kyuhee Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a giant library where robots are writing stories. Sometimes, these robots are so good that you can't tell if a story was written by a human or a machine. This is a big problem for the future: if robots can write anything, how do we know what's real? Scientists are trying to solve this by giving robots a secret way to mark their work, like a hidden signature that only a special detector can see. This is called "watermarking." Think of it like a secret code hidden in the DNA of a sentence.

However, checking for these codes has been tricky. Most old methods are like a game of "guess the password" that requires the robot itself to be present to check the work. If the robot is gone, or if someone changes the story slightly (like translating it to another language), the old codes often break or disappear. Furthermore, regulators (the people who make the rules) want a simple way to say, "I need a code that is wrong less than 1% of the time, works on short texts, and survives edits," but they haven't had a clear formula to tell engineers exactly how to build that code.

This paper introduces a new solution called ChainMark. It's a clever, "model-free" watermark, meaning you don't need the robot to check the work—you just need a secret key. The authors found a way to create a code that acts like a secret dance. They show that this dance is very hard to break against specific types of attacks, and they provide a clear, mathematical recipe for regulators to tell engineers exactly how to set it up.

The Secret Dance: How ChainMark Works

Imagine the robot's vocabulary (all the words it can use) is a giant box of colored tiles. ChainMark takes a secret key and sorts every single tile into one of five colored bins (let's say Red, Blue, Green, Yellow, and Purple). These bins are arranged in a circle, like a clock face: Red → Blue → Green → Yellow → Purple → Red.

When the robot is writing a story, ChainMark doesn't let it pick just any word. At certain spots in the story (about half the time), the robot is forced to pick a word that belongs to the next color in the circle. If the last word was Red, the next word must be Blue. If the last was Blue, the next must be Green. The robot still picks the best word it can find, but it's only allowed to pick from the "Blue" bin.

This creates a hidden path, or a "chain," through the text. The story is essentially walking around this color clock.

The Detective Without a Robot

Here is the magic part: to check if a story is watermarked, you don't need the robot at all. You just need the secret key and the text. A verifier (the detective) takes the text, looks up the secret key, and re-sorts every word into its colored bins. Then, they simply count how many times the colors follow the correct order (Red to Blue, Blue to Green, etc.).

If the story was written by a human or a robot without the secret, the colors will jump around randomly. The chance of getting the order right by accident is very low (only 1 in 5, or 20%). But if the story was written with ChainMark, the colors will follow the chain almost perfectly. The detective does this math in a flash, without ever needing to ask the robot for help.

Why This is a Big Deal

The paper shows that ChainMark solves three major headaches that other methods had:

No Robot Needed: Old methods often needed the robot's "brain" to check the work. ChainMark only needs the text and the key. This means a third party, like a regulator or a news editor, can check if a story is AI-generated without needing access to the company's secret AI model.
The Perfect Recipe: The authors derived a "closed-form" formula. This is a fancy way of saying they found a direct math equation. If a regulator says, "I need a false alarm rate of 1% for a 200-word text," the engineer can plug those numbers into the formula and instantly know exactly how many color bins to use. No more guessing or trial-and-error.
It Survives the "Translation Attack": One of the biggest ways to break old watermarks is to translate a text into another language (like Chinese) and then translate it back. This usually scrambles the secret code. The paper tested ChainMark against this and found it incredibly tough. Even after translating the text to Chinese and back, ChainMark still correctly identified the watermarked text 72.8% of the time. In contrast, other popular methods (called KGW and SWEET) dropped below 20% success rate under the same conditions.

The Trade-Off

The paper is honest about the cost. To make this secret dance work, the robot has to be slightly more restricted when choosing words. This makes the text a tiny bit less "fluent" or natural compared to a completely free robot. The authors measured this using a score called "perplexity." ChainMark's score was about 3.66, while the other methods were around 1.80 to 1.93. This means ChainMark is roughly twice as "stiff" as the others, but the trade-off is that it is much harder to break and much easier to verify without the robot.

The "Universal" Safety Net

The paper also discovered something surprising about how much editing the code can survive against a "blind" attacker (one who doesn't have the secret key). They proved mathematically that if someone randomly swaps out words (like a "cut and paste" attack), the code will survive as long as the edits are less than 29.3% of the text. This number is a "universal constant," meaning it doesn't matter how many color bins you use or how long the text is; the code holds up until you hit that specific 29.3% wall.

However, the authors are careful to note that this safety net has limits. It applies to random swaps and translation, but it does not guarantee survival against a super-smart hacker who knows the secret key or can ask the detector questions repeatedly to figure out the pattern. Additionally, the paper has not yet tested complex grammar-preserving rewrites (where the meaning stays exactly the same but the words change), so while the code is very strong against translation and random swaps, there is still work to do on other types of attacks.

What It's Not

The authors are careful to say what their method doesn't do. They admit that if a super-smart hacker knows the secret key or can ask the detector questions over and over to figure out the pattern, they might be able to break it. The paper focuses on a "blind" attacker who doesn't have the key. Also, they haven't tested every single type of editing (like complex grammar rewrites that keep the meaning exactly the same), so while the code is very strong against translation and random swaps, there is still work to do on other types of attacks.

The Bottom Line

ChainMark is like giving AI writers a secret, hard-to-break dance move that leaves a trail of footprints—provided the attacker is blind to the key and the attack is random or translational. Even if someone tries to erase the footprints by translating the story or swapping words, the pattern remains visible to anyone with the secret key. Most importantly, it gives regulators a clear, mathematical instruction manual to set up these watermarks exactly how they need them, without needing to guess or rely on the AI company to do the checking. It's a step toward a future where we can trust our digital text, knowing exactly who (or what) wrote it.

Technical Summary: ChainMark: Model-Free LLM Watermarking with Closed-Form Calibration

1. Problem Statement

The paper addresses the technical challenges of implementing machine-readable watermarking for Large Language Model (LLM) generated text, specifically in the context of regulatory mandates like the EU AI Act (Article 50). The authors identify three structural deficiencies in existing watermarking schemes (e.g., KGW, SWEET, EWD) that hinder regulator-facing audits:

Model-Bound Detection: Existing methods often require access to the generating model or its internal state (e.g., logits, entropy) at detection time, preventing third-party auditors from verifying text without the model.
Lack of Closed-Form Calibration: No existing scheme provides a mathematical mapping from a regulator's specific targets (false-positive rate $\alpha$ , minimum text length $n_{min}$ , and watermark budget $\rho$ ) to the concrete configuration parameters (e.g., watermark strength) required for deployment.
Brittle Robustness: Current schemes suffer significant degradation in true-positive rates (TPR) under common attacks like translation (e.g., Chinese back-translation) and random substitution, often dropping below 20% TPR at matched budgets.

2. Methodology: The ChainMark Scheme

ChainMark is an active watermarking scheme designed to be model-free at detection and calibrated via closed-form mathematics.

Core Mechanism

State Partitioning: A secret key $\kappa$ is used with a hash function (SHA-256) to map every vocabulary token $v$ to one of $S$ discrete states: $\sigma_\kappa(v) = \text{SHA-256}(\kappa \parallel v) \mod S$ . This partitions the vocabulary into $S$ disjoint sets $V_0, \dots, V_{S-1}$ .
Clockwork Transition: The states are arranged in a fixed cycle ( $s \to (s+1) \mod S$ ).
Generation (Embedding): At a fraction $\rho$ of token positions (determined by an entropy gate), the model is constrained to emit a token from the next state in the cycle. Specifically, the logits for tokens not in the target state set are masked to $-\infty$ , and the model selects the argmax from the remaining valid tokens. At ungated positions, the model samples freely.
Detection (Verification): A verifier, possessing only the secret key and the tokenizer (no LLM access), re-computes the state for every token in the text. The verifier calculates the fraction of valid transitions $\phi$ $ϕ$ where the state sequence follows the cycle.
- Null Hypothesis ( $H_0$ ): For unwatermarked text, transitions are random, yielding an expected valid rate of $p_0 = 1/S$ (for a 1-regular clockwork chain).
- Alternative Hypothesis ( $H_1$ ): Watermarked text exhibits a valid rate of $\approx 1/S + \rho(1 - 1/S)$ .
- Statistical Test: A standard $z$ -test is performed on $\phi$ to determine if the text is watermarked. The detection complexity is $O(n)$ hash operations.

Calibration and Robustness

Closed-Form Calibration: The authors derive a formula $S^\star(n, \rho, \alpha)$ that maps the regulator's targets directly to the minimum number of states $S$ required to guarantee a false-positive rate (FPR) of $\le \alpha$ .
Empirical Recalibration: To account for the non-uniform distribution of natural language tokens across hash states, a one-corpus recalibration step is proposed. This adjusts the detection threshold based on the empirical mean and standard deviation of the $z$ -score on non-watermarked text, restoring the target FPR without altering the watermark configuration.
Universal Robustness Threshold: The paper proves that under uniform random substitution, the watermark survives up to an edit fraction $\delta^\star = 1 - 1/\sqrt{2} \approx 29.3\%$ . Crucially, this threshold is invariant to the parameters $S$ , $\rho$ , and $n$ .

3. Key Contributions

Model-Free Detection: ChainMark enables third-party auditing using only the secret key and tokenizer, removing the need for the generating LLM at inference time.
Operator-Facing Calibration: The derivation of the closed-form map $S^\star(n, \rho, \alpha)$ allows regulators to specify detection targets that translate directly into deployable configurations.
Robustness Guarantees: Theoretical proofs establish a universal robustness threshold ( $\approx 29.3\%$ ) against uniform substitution, independent of system parameters.
Generalizability: The framework extends to any $k$ -regular doubly-stochastic transition topology, not just the simple clockwork chain.

4. Experimental Results

Experiments were conducted on three instruction-tuned LLMs (Llama-3.1-8B, Qwen-2.5-7B, Mistral-7B) across four domains (code, factual, wiki, writing).

Matched-Budget Performance: Compared against KGW and SWEET at a fixed watermark budget ( $\rho=0.5$ $ρ = 0.5$ ), ChainMark significantly outperformed baselines under attack.
- Clean Text: ChainMark achieved 100% TPR.
- Random Substitution ( $\delta=0.20$ ): ChainMark retained 99.9% TPR, while KGW and SWEET dropped to ~55% and ~51% respectively.
- Chinese Back-Translation: ChainMark retained a 72.8% TPR, whereas KGW and SWEET fell below 20% (19.4% and 18.0%).
Quality Cost: This robustness comes at a cost of increased self-perplexity (ChainMark: 3.66 vs. baselines: ~1.80–1.93).
Calibration Validation: Empirical results confirmed that the closed-form calibration provides the correct ordering of state counts, and the empirical recalibration successfully reduced the false-positive rate from ~2.0% to the target 1% without sacrificing true-positive detection.

5. Significance and Claims

The paper claims that ChainMark provides the necessary technical substrate for regulatory frameworks like the EU AI Act by solving the "auditability" problem. Its primary significance lies in:

Policy-to-Configuration Mapping: It translates abstract regulatory requirements (FPR, text length, budget) into concrete, auditable system parameters.
Third-Party Auditability: By decoupling detection from the model, it allows independent verification of AI-generated content, a prerequisite for transparent governance.
Robustness vs. Quality Trade-off: The authors acknowledge that ChainMark imposes a measurable quality cost (higher perplexity) but argue this is a necessary trade-off for achieving high robustness against translation and substitution attacks, which current state-of-the-art methods fail to withstand.

The authors remain modest regarding limitations, noting that the current robustness claims are against translation and uniform substitution, and that the scheme does not yet cover grammar-preserving paraphrase attacks (e.g., DIPPER) or adversaries with adaptive detector-query access. They also highlight the "chilling effect" and "false positive" risks as asymmetric harms that must be managed through careful threshold calibration.