Paper deep dive
ChainMark: Model-Free LLM Watermarking with Closed-Form Calibration
Chengheng Li-Chen, Kyuhee Kim
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 7/22/2026, 2:36:18 AM
Summary
The paper introduces ChainMark, a model-free active watermarking scheme for Large Language Models (LLMs) designed to comply with regulatory requirements like the EU AI Act. ChainMark partitions the vocabulary into states using a keyed SHA-256 hash and enforces a Markov transition where the model emits tokens from the next state in a cycle. This allows for O(n) detection without access to the generating model. The authors derive closed-form calibration for state counts based on false-positive rates and text length, and prove a universal robustness threshold against token substitution attacks.
Entities (10)
Relation Signals (8)
ChainMark → uses → SHA-256
confidence 95% · ChainMark partitions the vocabulary into S states via keyed SHA-256
ChainMark → addresses → EU AI Act
confidence 92% · Regulatory regimes such as the EU AI Act mandate machine-readable marking... We introduce ChainMark
ChainMark → hasproperty → Robustness Threshold
confidence 90% · prove a universal robustness threshold delta* = 1 - 1/sqrt(2) approximately 29.3%
ChainMark → outperforms → SWEET
confidence 90% · ChainMark strictly dominates KGW and SWEET under translation and random-substitution attacks
ChainMark → outperforms → KGW
confidence 90% · ChainMark strictly dominates KGW and SWEET under translation and random-substitution attacks
ChainMark → evaluatedon → Llama-3.1-8B-Instruct
confidence 85% · Across three instruction-tuned LLMs... Llama-3.1-8B-Instruct
ChainMark → evaluatedon → Qwen-2.5-7b-Instruct
confidence 85% · Across three instruction-tuned LLMs... Qwen-2.5-7B-Instruct
ChainMark → evaluatedon → Mistral-7B-Instruct-v0.3
confidence 85% · Across three instruction-tuned LLMs... Mistral-7B-Instruct-v0.3
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Regulatory regimes such as the EU AI Act mandate machine-readable marking of synthetic text, but existing watermark detectors rely on the generating LM and on heuristic thresholds with no closed-form calibration. We introduce ChainMark, an active watermark that partitions the vocabulary into S states via keyed SHA-256 and forces a hard Markov transition on a fraction rho of positions; the detector replays the partition from the same key in O(n) hash operations, with no LM access. We derive a closed-form S*(n, rho, alpha) mapping a target FPR, text length, and budget to the minimum state count (Theorem 1), prove a universal robustness threshold delta* = 1 - 1/sqrt(2) approximately 29.3% that is invariant in (S, rho, n) (Theorem 2), and generalise both to any k-regular transition topology (Theorem 3). Across three instruction-tuned LLMs and four domains, ChainMark strictly dominates KGW and SWEET under translation and random-substitution attacks at matched budget; a one-corpus empirical recalibration restores the 1% target FPR on natural-language text.
Tags
Links
- Source: https://arxiv.org/abs/2607.18445v1
- Canonical: https://arxiv.org/abs/2607.18445v1
Trouble viewing inline? Open PDF directly →
Full Text
88,175 characters extracted from source content.
Expand or collapse full text
ChainMark: Model-Free LLM Watermarking with Closed-Form Calibration Chengheng Li-Chen Kyuhee Kim Abstract Regulatory regimes such as the EU AI Act mandate machine-readable marking of synthetic text, but existing watermarks are ill-suited to regulator-facing audit: entropy-gated detectors require the generating model at detection time, and no scheme maps a regulator’s targets (a false-positive rate, a text-length floor, and a watermark budget) to a deployer configuration in closed form. We introduce ChainMark, an active watermark whose detection needs no model: a keyed hash partitions the vocabulary into S states arranged in a cycle, and at a fraction ρ of positions the model is forced to emit the next state, so the text walks the cycle. A verifier replays the partition from the same key in O(n)O(n) hash operations in the text length n. We derive a closed-form map S⋆(nmin,ρ,α)S (n_ ,ρ,α) from the regulator’s targets to the minimum state count, which a one-corpus recalibration pins to a 1% false-positive rate on real text; under uniform substitution the watermark survives edits up to a fraction δ⋆=1−1/2≈29.3%δ =1-1/ 2≈ 29.3\% independent of (S,ρ,n)(S,ρ,n). Across three instruction-tuned LLMs and four domains, ChainMark retains a 72.8% true-positive rate after Chinese back-translation, where KGW and SWEET fall below 20% at matched budget. ChainMark thus maps a regulatory specification to a deployable configuration that a third party can audit without the model. AI governance, LLM watermarking, content provenance, EU AI Act, technical AI governance 1 Introduction EU AI Act Article 50 (European Parliament and Council, 2024) requires machine-readable marking of AI-generated text by August 2026, but the technical substrate is unsettled. Existing watermarks have three structural problems for regulator-facing audit. (i) Model-bound detection. SWEET (Lee et al., 2024) and EWD (Lu et al., 2024) select or weight tokens by entropy and so need the generating language model (LM) at detection time; and the inverse-transform distortion-free watermark (Kuditipudi et al., 2024) needs the full secret key sequence rather than a short key. (i) No closed-form calibration. None of these schemes converts a regulator’s targets (a target false-positive rate α, a minimum text length nminn_ , and the fraction ρ of tokens to mark) into the concrete settings a deployer must apply; KGW’s (Kirchenbauer et al., 2023) watermark strength δKGW _KGW is set by hand. (i) Brittle robustness. At matched budget, the true-positive rate (TPR) of KGW and SWEET falls below 20% after Chinese back-translation, i.e. translating to Chinese and back (Table 1). A. Clockwork chainσκ(t)=SHA-256(κ∥t)modS _κ(t)=SHA -256(κ\,\|\,t) S0V_01V_12V_23V_34V_4B. Generation stepLM logitsmask s+1V_s+1argmax +1∈3t_i+1 _3C. Detection by clockwork validityWatermarked text:011223344stateϕ=1φ=1Random text:011223344state11⋯·snntoken index iϕ≈1/Sφ≈ 1/Sappend ti+1t_i+1 Figure 1: ChainMark at a glance. (A) A keyed SHA-256 hash σκ _κ partitions the vocabulary into S disjoint sets 0,…,S−1V_0,…,V_S-1 ordered into a clockwork cycle s→s+1modSs→ s+1 S (here S=5S=5). (B) At a watermarked position with current state s, the language-model logits are masked to keep only the next partition s+1V_s+1, and the next token is the masked argmax . (C) Detection re-derives every token’s state from the key κ in O(n)O(n) hash operations: a watermarked sequence walks the chain by construction (top, validity rate ϕ=1φ=1), whereas unwatermarked text visits states uniformly and is valid only at rate 1/S1/S in expectation (bottom). We propose ChainMark, built on one idea: a secret key hashes every vocabulary token (via SHA-256) into one of S states, the states are arranged in a fixed cycle, and at watermarked positions we constrain the model to emit a token from the next state, so the generated text walks the cycle by construction (Figure 1). A verifier holding the key re-derives each token’s state and counts how often the walk is followed, in O(n)O(n) hash operations, needing the key and tokenizer but no model. Two properties follow. The detector’s false-positive behavior is known in closed form, giving a map S⋆(nmin,ρ,α)S (n_ ,ρ,α) from a regulator’s targets to the minimum number of states; because real text is not uniform over the states, a one-corpus recalibration restores the target false-positive rate. Under uniform random substitution the watermark also has a robustness threshold δ⋆=1−1/2≈29.3%δ =1-1/ 2≈ 29.3\% independent of S, ρ, and n, keeping a 72.8% TPR after Chinese back-translation. A deployer therefore configures the watermark directly from a regulatory target, and any auditor can check the output from the key without access to the model. Contributions. 1. We introduce ChainMark, a hard-constraint watermark with O(n)O(n), model-free detection from the key and tokenizer (Section 4). 2. We derive an operator-facing calibration map from a target false-positive rate, text-length floor, and budget to the minimum admissible state count (Theorem A.2, Appendix A), with an empirical recalibration that restores this target FPR on natural-language text (Subsection A.2), and a robustness threshold under uniform substitution that is invariant to (S,ρ,n)(S,ρ,n) (Theorem A.4). 3. Both the detection law and the robustness threshold extend to any k-regular doubly-stochastic transition topology (Theorem A.6). 4. We show that at matched budget, across three instruction-tuned LLMs and four domains, ChainMark retains substantially more detection signal than KGW and SWEET under translation and random-substitution attacks, at roughly 2×2× their self-perplexity (Section 6). 2 Related Work Passive detection. DetectGPT (Mitchell et al., 2023) exploits log-probability curvature; GPTZero (Tian and Cui, 2023) combines perplexity and burstiness. Both read statistical traces in existing text, with no controllable false-positive frontier and sharp degradation under paraphrase (Krishna et al., 2023; Sadasivan et al., 2023). They cannot serve as the technical substrate for Article 50 because neither regulator nor deployer can set the detection regime in advance. Active watermarking. Green–red-list (KGW) watermarking (Kirchenbauer et al., 2023) biases next-token logits toward a hashed green list and detects via a z-test on green-token frequency. The scheme’s signal depends on next-token entropy and degrades under paraphrase, and offers no analytic inversion from a regulatory parameter back to a bias magnitude. ChainMark’s fingerprint ϕφ is structurally a Bernoulli(1/S1/S) z-test, so the calibration formula (8) is the analogue KGW lacks. Distortion-free schemes. Aaronson (2023)’s Gumbel-max construction and Kuditipudi et al. (2024)’s inverse-transform sampling watermark are distortion-free: they preserve the LM marginal in expectation over the key. Christ et al. (2023) prove cryptographic indistinguishability under sufficient entropy. These schemes beat ChainMark on quality strictly (zero expected KL versus ChainMark’s ≥ρlogS≥ρ S). The trade is calibration: none maps a regulatory target (α,nmin,ρ)(α,n_ ,ρ) to a configuration in closed form, and the inverse-transform scheme’s detector needs the full key sequence rather than a short key. ChainMark is the distorting alternative that supplies the closed-form S⋆S map. Entropy-adaptive schemes: gates vs. detectors. SWEET (Lee et al., 2024) and EWD (Lu et al., 2024) both restrict watermarking signal to high-entropy positions, but at different layers: SWEET applies a binary gate at generation time, while EWD weights positions by entropy at detection time, approximating the log-likelihood ratio of Theorem A.9. Either way, detection must recompute per-token entropy and so needs the generating model, unlike ChainMark. ChainMark is gate-agnostic in its specification (high-entropy, low-entropy, and surprisal-gap gates are all admissible); for the head-to-head in Section 6 we adopt the high-entropy gate to match SWEET at the same budget, so the operational dial we vary is ρ, not the gate identity. Technical AI governance. Article 50 of the EU AI Act (European Parliament and Council, 2024) and the EU’s draft Code of Practice on Transparency (European Commission AI Office, 2025) require machine-readable marking of AI-generated content; the OECD Hiroshima Process (OECD, 2024) provides a parallel international framework. These instruments leave the detection regime (FPR, quality floor, robustness) implicit. ChainMark’s contribution, beyond the watermarking scheme itself, is that it surfaces these parameters analytically, producing a policy-to-configuration map auditable by third parties (Section 7). 3 Preliminaries Notation. Let V denote the vocabulary of an autoregressive language model, V=||V=|V|, and write =(t1,…,tn)∈nt=(t_1,…,t_n) ^n for a token sequence of length n. The deployer and the verifier share a secret key κ∈0,1∗κ∈\0,1\^* and the same tokenizer; the verifier never sees the language model. Let ℋ:0,1∗→0,1256H:\0,1\^*→\0,1\^256 be SHA-256, modelled as a random oracle in the security analysis (Theorem A.8). We write [m]=0,…,m−1[m]=\0,…,m-1\ and zαz_α for the one-sided standard-normal quantile at level α. Threat model. The adversary observes watermarked text and may paraphrase, translate, edit, splice, or delete tokens before publication; we model these as a per-token modification rate δ∈[0,1)δ∈[0,1). The adversary is computationally bounded and has no access to κ, to the language model, or to the deployed detector as a queryable oracle at detection time (Section 7 discusses the adaptive-oracle adversary that lies outside this model). The verifier sees only token text and runs in O(n)O(n) hash operations. Detection problem and quality. Detection is a binary hypothesis test on text alone, H0H_0 (non-watermarked) vs. H1H_1 (watermarked under key κ), at a fixed false-positive rate α, since false positives are operationally the costly error. The watermark distribution must remain fluent under standard greedy or low-temperature decoding, which we control via the per-token KL divergence to the original next-token distribution and report as perplexity inflation (Section 4). 4 The ChainMark Scheme 4.1 State Partition For each token id v∈v define σκ(v)=ℋ(κ∥v)modS, _κ(v)\;=\;H(κ\,\|\,v) S, (1) which deterministically maps V onto S equivalence classes s=v:σκ(v)=sV_s=\v: _κ(v)=s\, s∈[S]s∈[S]. Under the random-oracle model σκ _κ is uniform and independent across distinct tokens, so [|s|]=V/SE[|V_s|]=V/S; knowledge of σκ _κ on queried tokens reveals nothing about unqueried ones (Theorem A.8). 4.2 Transition Topology A successor function Σk:[S]→([S]k) _k:[S]→ [S]k assigns each state a k-element set of legal next states. We require Σk _k to be k-regular in both out- and in-degree; column-regularity is essential for the null-variance and robustness arguments (Theorem A.6, Subsection A.1). The default is the clockwork chain at k=1k=1, Σ1(s)=(s+1)modS _1(s)=\(s+1) S\: deterministic, periodic of period S, uniform stationary distribution, and the smallest random baseline 1/S1/S among 11-regular topologies. We additionally evaluate the soft-cycle variant k=2k=2, Σ2(s)=(s+1)modS,(s+2)modS _2(s)=\(s+1) S,\,(s+2) S\, which doubles the per-state successor budget at the cost of raising the random baseline to 2/S2/S (Section 6). 4.3 Generation At step i with current state si=σκ(ti)s_i= _κ(t_i), ChainMark forms the legal token set si⋆=⋃s′∈Σk(si)s′V_s_i = _s ∈ _k(s_i)V_s and masks the LM logits outside si⋆V_s_i to −∞-∞. At gated positions ChainMark picks the argmax over the masked logits; at ungated positions it samples from the original distribution. Each step costs one LM forward pass plus an O(V)O(V) logit mask (precomputed once per state). Algorithm 1 ChainMark Watermark Embedding Input: prompt p, key κ, states S, successor Σk _k, gate g(⋅)g(·), max tokens N ←Tokenize(p)t (p); s←σκ(−1)s← _κ(t_-1) for i=1i=1 to N do pi←softmax(ℳ())p_i (M(t)) ⋆←⋃s′∈Σk(s)s′V ← _s ∈ _k(s)V_s if g(pi)=1g(p_i)=1 and pi(⋆)>0p_i(V )>0 then ti←argmaxt∈⋆pi(t)t_i← _t p_i(t) else ti∼pit_i p_i // free sampling at ungated positions end if ←∥tit \,\|\,t_i; s←σκ(ti)s← _κ(t_i) if ti=EOSt_i= EOS then break end if end for return Decode()Decode(t) 4.4 Watermark Budget and Entropy Gate The mask is applied only at a subset of positions; the watermark budget is ρ=i[gi]∈[0,1]ρ=E_i[g_i]∈[0,1]. Let Hi=−∑tpi(t)logpi(t)H_i=- _tp_i(t) p_i(t) be the next-token entropy and Δi=pi(1)−pi(2) _i=p_i^(1)-p_i^(2) the gap between the top two probabilities. Definition 4.1 (Gate family). Gall:gi=1G_all:\;g_i=1; GHhigh(τ):gi=[Hi>τ]G_H_high(τ):\;g_i=1[H_i>τ]; GHlow(τ):gi=[Hi<τ]G_H_low(τ):\;g_i=1[H_i<τ]; GΔ(τ):gi=[Δi<τ]G_ (τ):\;g_i=1[ _i<τ]. Our default is GHhighG_H_high, which masks only the model’s uncertain positions and matches the high-entropy gating policy of SWEET (Lee et al., 2024) at the same budget; Section 6 reports the head-to-head. The threshold τ is calibrated by quantile-matching on a held-out pilot so the realised gate rate tracks ρ. GHlowG_H_low is the anti-SWEET ablation, and GΔG_ targets near-tied top-two positions where the greedy substitution regret is bounded pointwise by Δi _i. 4.5 Detection The verifier tokenises the candidate text, re-derives states by re-applying σκ _κ, and computes the fraction of legal transitions ϕ()=1n−1∑i=1n−1[σκ(ti+1)∈Σk(σκ(ti))].φ(t)\;=\; 1n-1 _i=1^n-11\! [ _κ(t_i+1)∈ _k( _κ(t_i)) ]. (2) With p0=k/Sp_0=k/S, the random-oracle null gives [ϕ]=p0E[φ]=p_0 with pairwise-zero covariance for any k-regular Σk _k (Subsection A.1); the watermarked mean gap is ρ(1−p0)ρ(1-p_0) (Theorem A.2, Theorem A.6). The verifier reports the standardised score z=(ϕ−p0)/p0(1−p0)/(n−1)z=(φ-p_0)/ p_0(1-p_0)/(n-1) and declares H1H_1 when z>zαz>z_α. The closed-form calibration of Theorem A.2 (proved in Appendix A) selects S given target FPR α, budget ρ, and length n; the same identities yield robustness under per-token modification rate δ (Theorem A.4). Algorithm 2 ChainMark Watermark Detection (model-free) Input: text x, key κ, states S, successor Σk _k, level α ←Tokenize(x)t (x); n←||n←|t|; c←0c← 0 for i=1i=1 to n−1n-1 do if σκ(ti+1)∈Σk(σκ(ti)) _κ(t_i+1)∈ _k( _κ(t_i)) then c←c+1c← c+1 end if end for ϕ←c/(n−1)φ← c/(n-1); p0←k/Sp_0← k/S z←(ϕ−p0)/p0(1−p0)/(n−1)z←(φ-p_0)/ p_0(1-p_0)/(n-1) return (z>zα,ϕ,z)(z>z_α,\ φ,\ z) Algorithm 2 runs in O(n)O(n) hash operations without LM access, making ChainMark deployable as a third-party audit primitive. 5 Theoretical Properties This section gives an intuitive tour of three core results (detection, robustness, k-regular generalisation) plus two supporting properties (security against an oracle-blind adversary, and an LM-aware locally most powerful detector). Formal statements and proofs are deferred to Appendix A; we collect their pointers here so the body remains a narrative. Empirical anchoring of Theorem A.2 appears in Subsection 6.5. Detection bound and calibration. Under the null hypothesis that the input is a uniformly random token sequence, the fingerprint score ϕφ of Equation 2 is approximately Gaussian with mean 1/S1/S and variance (1/S)(1−1/S)/(n−1)(1/S)(1-1/S)/(n-1), while a watermarked sequence with gate density ρ shifts the mean to 1/S+ρ(S−1)/S1/S+ρ(S-1)/S. Standardising gives the expected value of the detection statistic under the watermarked alternative in closed form, z(ρ,S,n)=ρ(S−1)(n−1)z(ρ,S,n)=ρ (S-1)(n-1), i.e. its noncentrality parameter (distinct from the sample statistic z evaluated on observed text). Inverting at false-positive level α under the midpoint threshold convention yields a state-count rule that practitioners can read off directly, S⋆(n,ρ,α)=⌈4zα2ρ2(n−1)+1⌉.S (n,ρ,α)\;=\; 4\,z_α^2ρ^2(n-1)+1 . The factor-of-44 comes from evaluating the standardised signal at the midpoint between the null and alternative means. This gives the regulator a 2×2× safety margin relative to the one-sided zαz_α test reported in our empirical tables; those tables run at a tighter operating threshold than S⋆S requires, so empirical TPR exceeds the conservative midpoint prediction. Formal statement and proof in Theorem A.2 of Appendix A; the corresponding lookup table is Table 4. Empirical-SD calibration recipe. The closed-form zαz_α assumes i.i.d. uniform tokens over the SHA-256 partition; on natural-language text this drifts (empirically 1.71.7–2.0%2.0\% at the nominal 1%1\% target, Table 3). The fix is a one-corpus recalibration: estimate the empirical mean and SD of z on a non-watermarked sample of the deployed LM (or a domain-matched corpus) and use z⋆=μ^+zασ^z = μ+z_α\, σ as the operating threshold. Under the same Gaussian-tail null this restores the target FPR (1.17%1.17\% at α=1%α=1\% on our n=3000n=3000 pooled corpus) without changing S⋆S or touching the watermarked side, so TPR is unaffected. The empirical z-null is mildly leptokurtic, so for tighter α or large S the empirical-quantile drop-in z⋆=F^−1(1−α)z = F^-1(1-α) is the robust alternative. Formal recipe in Subsection A.2; empirical evaluation in Subsection D.2. Universal robustness threshold. Suppose an adversary independently replaces each token with probability δ by a fresh token whose state is uniform on [S][S]. Both the watermarked-pair signal and the midpoint-threshold gap scale by the same affine factor ρ(S−1)/Sρ(S-1)/S, so the post-attack-to-pre-attack z ratio collapses to (1−δ)2(1-δ)^2, independently of (S,ρ,n)(S,ρ,n). The critical edit fraction at which detection fails is therefore the universal constant δ⋆=1−1/2≈0.293δ =1-1/ 2≈ 0.293. Formal statement and proof in Theorem A.4. k-regular generalisation. The clockwork transition is the simplest member of a broader family: any k-regular adjacency T (every state has exactly k allowed successors and predecessors) yields a valid ChainMark scheme. Replacing the random baseline 1/S1/S by p0=k/Sp_0=k/S gives the same calibration identities, the same midpoint critical fraction δ⋆δ , and a single quality-versus-detection dial in k. Column-regularity is load-bearing: it is what makes adjacent indicator pairs have zero covariance under the null, so the variance formula carries through. Formal statement and proof in Theorem A.6. The random baseline p0=k/Sp_0=k/S relies on the SHA-256 partition being approximately uniform across the vocabulary, an assumption we inherit from the standard avalanche property of cryptographic hashes. Security and an LM-aware optimal detector. The state map σκ(t)=ℋ(κ∥t)modS _κ(t)=H(κ\,\|\,t) S is modelled as a random oracle: an adversary without access to κ, the LM, or reference text cannot predict σκ(t⋆) _κ(t ) on a fresh token with non-negligible advantage in the key min-entropy, and therefore cannot statistically distinguish ChainMark output from random text (Theorem A.8; computational, not information-theoretic, and excluding adversaries with LM access). A verifier that does have LM access can sharpen detection by replacing ϕφ with an entropy-weighted log-likelihood ratio that is asymptotically locally most powerful under the random-oracle product-form approximation (Theorem A.9). Detector pseudocode appears as Algorithm 3. 6 Experiments We run four experiments on three instruction-tuned 7–8B LLMs across four domains. Per-prompt records stream to JSONL for reproducibility. Figure 2 traces a single ChainMark generation end-to-end on a wiki-domain prompt: the model receives the user prompt, ChainMark masks logits at gated positions to keep only states (s+1)modS(s+1) S, and the detector re-derives every token’s state from the key alone and reports a z-score. 1. User prompt Explain photosynthesis in a comprehensive way. ⇓ 2. Watermarked output Photosynthesisisthe ⇀ process⇀ by⇀ which⇀ plants convert sunlight⇀ into⇀ chemical⇀ energy⇀ and releases … ⇓ 3. Auditor verdict ϕ=1113=0.85φ= 1113=0.85, z=5.30>z0.01=2.326z=5.30>z_0.01=2.326 ⇒ WATERMARKED s0s_0 ⇀ s1s_1 ⇀ s2s_2 ⇀ s3s_3 ⇀ s4s_4 ⇀ s0s_0 Figure 2: End-to-end ChainMark trace on a wiki prompt (Llama-3.1-8B-Instruct, S=5S=5, ρ=0.5ρ=0.5, 1414-token excerpt). Every output tile inherits its colour from σκ(t)∈0,1,2,3,4 _κ(t)∈\0,1,2,3,4\ (legend at bottom). Underlined tokens are gated steps where ChainMark masked logits to enforce si+1=(si+1)mod5s_i+1=(s_i+1) 5 and the ⇀ arrows trace the forced clockwork walk; un-underlined tokens are free-sampled at T=0.7T=0.7. The auditor in panel 3 re-derives the entire colour sequence from κ alone, counts 11/1311/13 valid transitions (green bar), and emits (ϕ,z)(φ,z) in O(n)O(n) hash operations, no LM forward pass. 6.1 Setup Models. Three instruction-tuned, openly licensed checkpoints in the 7–8B parameter range: Llama-3.1-8B-Instruct (Grattafiori and others, 2024), Qwen-2.5-7B-Instruct (Qwen et al., 2025), and Mistral-7B-Instruct-v0.3 (Jiang and others, 2023). The same secret key κ is fixed across every run. Domains. Four prompt domains stress different entropy regimes: code (HumanEval problem stems), factual (short closed-form knowledge prompts), wiki (open-ended “Explain X…” prompts over a curated concept list), and writing (creative-completion prompts). Generation and detection. Temperature T=0.7T=0.7, top-p=1p=1, token budget n=200n=200 at every cell, with one deterministic seed so the same indices are watermarked, attacked, and detected across methods. Detection uses the threshold zαz_α from Theorem A.2, reused across methods for cross-method consistency; the empirically calibrated 1%1\%-FPR head-to-head (Subsection D.3) confirms the resulting TPR ranking is not an FPR artefact. ChainMark configuration. Unless stated otherwise, ChainMark runs use S=5S=5 states, target gate budget ρ=0.5ρ=0.5, the high-entropy gate GHhighG_H_high, and clockwork (k=1k=1) topology. Baselines. KGW (Kirchenbauer et al., 2023) at γ=0.5γ=0.5, logit bias δKGW=2 _KGW=2 (the canonical operating point reported in the original paper at this γ). SWEET (Lee et al., 2024) is reproduced as a matched-budget re-implementation: same γ=0.5γ=0.5 and δKGW=2 _KGW=2 but the green-list bias is applied only at the top-ρ=0.5ρ=0.5 fraction of positions by token-level entropy, so the budget aligns with ChainMark’s ρ. Per-domain prompt-and-generation examples (with a token-level gating walkthrough) appear in Appendix F; the end-to-end trace in Figure 2 above gives one illustration on the wiki prompt Explain photosynthesis in a comprehensive way.. (a) (b) (c) Figure 3: Experimental headlines. (a) Head-to-head TPR: ChainMark vs KGW vs SWEET, aggregated over 3 LLMs × 4 domains (§6.2). (b) Translation robustness: empirical decay under NLLB-200 EN→FR,DE,RU,ZH→ vs the closed-form (1−δeff)2(1- _eff)^2 diagonal (Theorem A.4), with δeff _eff the empirical token-edit fraction; m=100m=100 generations per (model, pivot) (§6.3). (c) Calibration anchor: empirical FPR vs state count S with the closed-form Hoeffding bound (Theorem A.2) (§6.5). 6.2 Matched-Budget Head-to-Head We compare ChainMark against KGW and SWEET on 1 2001\,200 generations per method (33 models, 44 domains, 100100 prompts each), with 200200 tokens per generation, and score each generation under three conditions: clean, random substitution at rate δ=0.20δ=0.20, and NLLB-200 EN→ → back-translation. Aggregated across all 1 2001\,200 cells per method (Table 1, 3(a)), ChainMark detects 100%100\% of clean and 99.9%99.9\% of randomly perturbed generations and retains 72.8%72.8\% TPR after ZH back-translation, where KGW and SWEET drop from ∼75% \!\!75\%/∼72% \!\!72\% clean to 19.4%19.4\%/18.0%18.0\% post-attack. The gap is consistent across every (model, domain) cell (Figure 4); ChainMark matches or leads every clean cell and strictly leads every post-ZH cell. ChainMark pays a ≈2×≈ 2× self-perplexity gap (3.663.66 vs 1.801.80/1.931.93) for this gain. SWEET is an entropy-gating ablation of KGW with the gating policy held fixed against ChainMark. Table 1: Headline aggregate at the analytic threshold zα=2.326z_α=2.326 (α=0.01α=0.01, Gaussian-tail null), aggregated over 33 LLMs × 44 domains × 100100 prompts at n=200n=200 tokens per cell. PPL is the median across the 1212 cell medians on the watermarked model’s own logits (caveats in Section 7). Empirical FPR drift at this threshold appears separately in Table 3. Bold = best per column. Method TPRclean (%) TPRrnd (%) TPRZH (%) PPL↓ ChainMark 100.0 99.9 72.8 3.66 KGW 074.8 55.1 19.4 1.93 SWEET 071.8 51.2 18.0 1.80 Figure 4: Per-(model, domain) head-to-head TPR (%) at zα=2.326z_α=2.326 (100100 prompts per cell, n=200n=200 tokens). Each row is one (model, domain) cell; left panel is clean, right panel is ZH back-translation. ChainMark matches or leads every clean cell and strictly leads every cell post-ZH-back-translation. Each cell is annotated with its TPR (%), in white on dark (high-TPR) cells and dark on light (low-TPR) cells for contrast. 6.3 Translation Robustness Each ChainMark-watermarked output has n=200n=200 tokens; across 33 models × 44 domains × 2525 prompts we obtain 300300 outputs, each round-tripped through NLLB-200 (Team et al., 2022) on four pivot languages (FR, DE, RU, ZH) for 1 2001\,200 generations total, and we compute the empirical δeff _eff per output via token-edit distance. Plotting the post-attack-to-clean z ratio against δeff _eff (3(b)) shows the observed ratios sit at or above the closed-form (1−δeff)2(1- _eff)^2 diagonal across pivots, models, and domains, which empirically anchors the universal half-life δ⋆=1−1/2δ =1-1/ 2 from Theorem A.4 and confirms the bound is conservative rather than tight. The claim is stronger than synthetic random-substitution can support, since NLLB-200 produces semantically coherent rewrites rather than i.i.d. token noise. 6.4 k-Regular at k=2k=2 Instantiating k=2k=2 (each state has two allowed successors) at S=5S=5 predicts p0=k/S=0.40p_0=k/S=0.40. We run 100100 wiki-domain prompts on each of the three models with ZH back-translation as the only attack. Table 2 reports clean ϕ¯cl≥0.88 φ_cl≥ 0.88 (well above the p0=0.40p_0=0.40 prediction) and a post-attack z-score that sits above the (1−δeff)2(1- _eff)^2 floor of Theorem A.4 (observed ratio 0.230.23–0.270.27 vs. the predicted floor (1−δeff)2≈0.07(1- _eff)^2≈ 0.07–0.090.09 evaluated at the wiki-domain ZH edit fraction measured here, which is milder than the 44-domain headline δeff≈0.81 _eff≈ 0.81; i.e. the bound is conservative as in Subsection 6.3), jointly re-certifying Theorem A.6 and Theorem A.4 at a non-trivial k. Table 2: k-regular ChainMark at k=2k=2 (soft-cycle), S=5S=5, ρ=0.5ρ=0.5. Predicted random baseline p0=0.40p_0=0.40; wiki domain, 100100 prompts. The clean ϕ¯cl φ_cl values (≥0.88≥ 0.88) sit well above p0p_0 (Theorem A.6); the post-attack z ratio re-certifies Theorem A.4 at k=2k=2 (Appendix A). Model ϕ¯cl φ_cl z¯cl z_cl TPRcl z¯ZH z_ZH TPRZH Llama-3.1-8B 0.883 13.91 100% 3.19 54% Mistral-7B 0.965 16.23 100% 3.91 70% Qwen-2.5-7B 0.934 15.38 100% 4.12 71% 6.5 Calibration Anchor We sweep S∈2,3,5S∈\2,3,5\ across the three models with 44 domains × 2525 prompts at n=200n=200, recording both a watermarked generation (ChainMark at the canonical operating point, varying only S) and a non-watermarked baseline drawn from the same prompt. Non-watermarked outputs feed the empirical FPR estimate at the analytic zαz_α; watermarked outputs feed the TPR. Table 3 shows watermarked z overshoots the closed-form prediction ρ(S−1)(n−1)ρ (S-1)(n-1) by 5050–80%80\%, so TPR is at 100%100\% throughout, while empirical FPR sits above the α=1%α=1\% target by ∼1 \!\!1 p (3(c), 1.71.7–2.0%2.0\%). The closed form gives the right S⋆S ordering to within one state; for strict 1%1\% FPR a deployer applies the per-S empirical-quantile threshold recalibration of Subsection A.2 (Section 7, Subsection D.2). Table 3: Empirical anchor of the calibration map S⋆(n,ρ,α)S (n,ρ,α) from Theorem A.2. For each S, aggregated across 33 LLMs × 44 domains × 2525 prompts (≈300≈ 300 watermarked + 300300 non-watermarked). zwmpred=ρ(S−1)(n−1)z_wm^pred=ρ (S-1)(n-1). Watermarked z overshoots theory by 5050–80%80\%; non-watermarked FPRnwm exceeds the α=1%α=1\% target at large S due to non-i.i.d. structure in natural-language token sequences. The last two columns apply the empirical-quantile recalibration of Subsection A.2 per-S on the same NWM corpus: FPRrecal.nwm_nwm^recal. lands uniformly below α=1%α=1\%, while TPRrecal.wm_wm^recal. stays at ≥95%≥ 95\% on the watermarked side (the recalibration only lifts the threshold, so detection power is essentially preserved). S z¯wmobs z_wm^obs zwmpredz_wm^pred TPRwm FPRnwm TPRrecal.wm_wm^recal. FPRrecal.nwm_nwm^recal. 2 10.87 7.05 100% 2.00% 098.7% 0.67% 3 17.41 9.97 100% 2.00% 100.0% 0.67% 5 25.38 14.11 100% 1.67% 100.0% 0.34% 7 Discussion 7.1 When to Use What The calibration S⋆(nmin,ρ,α)S (n_ ,ρ,α) of Theorem A.2 reduces operational deployment to three inputs: a minimum text length nminn_ , a target false-positive rate α, and a watermark budget ρ. For long-form content the calibration anchors at small S with ρ near 1/21/2; Subsection 6.2 shows ChainMark substantially exceeds KGW and SWEET at the analytic zα=2.326z_α=2.326 threshold (the 1%1\%-empirical-FPR recalibration in Subsection D.3 preserves the lead vs. KGW), at a ≈2×≈ 2× higher self-perplexity (3.663.66 vs 1.801.80–1.931.93; Table 1). For short outputs S⋆S rises sharply with stricter α, so deployers tolerate a higher state count or shift to a longer floor. When cross-lingual rewrite or random substitution dominates the attack profile (Subsection 6.2, Subsection 6.3), the universal threshold δ⋆δ of Theorem A.4 bounds the worst case across all gating choices. 7.2 Empirical SD Recalibration Closes the FPR Gap Recomputing the threshold from the empirical SD of z on a non-watermarked corpus, z⋆=μ^+zασ^z = μ+z_α\, σ, brings empirical FPR from 2.1%2.1\% to 1.2%1.2\% at α=1%α=1\% while preserving TPR=100%=100\% on the pooled n=3000n=3000 corpus (Subsection D.2); the per-S empirical-quantile drop-in in Table 3 costs at most 1.31.3 p of TPR (TPR≥wmrecal.98.7%_wm^recal.\!≥ 98.7\% across S∈2,3,5S\!∈\!\2,3,5\). The plug-in is calibrated at α=1%α=1\% but the empirical z-null is leptokurtic (excess kurtosis ≈1.4≈ 1.4), so for tighter α≤0.5%α≤ 0.5\% the empirical-quantile recipe z⋆=F^−1(1−α)z = F^-1(1-α) is the robust drop-in (and draws the recalibrated curve in 3(c)). The 1%1\%-FPR head-to-head appears in Subsection D.3; ChainMark also admits an empirical FPR=0%=0\% regime via threshold lifting (Subsection D.4), which KGW and SWEET cannot, since their watermarked and non-watermarked z distributions overlap. Failure modes we tried but did not adopt (Newey–West HAC, k-skip, stopword filtering, HDD-lite) are tabulated in Subsection D.2. 7.3 Limitations Experimental scope. The headline grid fixes ρ=0.5ρ=0.5, KGW/SWEET at γ=0.5,δKGW=2γ=0.5, _KGW=2, and decoding at T=0.7T=0.7, top-p=1p=1, n=200n=200 with one deterministic prompt-order seed (no replicate-seed CIs). The fleet is three open-weight instruction-tuned 7–8B models; base, smaller, and ≥10≥ 10B models are deferred, as is k-regular ChainMark at k≥3k≥ 3 (we validate k∈1,2k∈\1,2\). The robustness suite is translation-only: we do not run grammar-preserving paraphrase (e.g. DIPPER), so the strongest claim is against translation and uniform substitution, not adversarial paraphrasing. The translation evaluation covers all 1212 (model, domain) cells (Table 5), but the SWEET row of the recalibrated head-to-head (Table 7) is omitted since the SWEET null z-distribution was not collected on the FPR corpus. Quality and detector caveats. Generation quality is self-perplexity under each model’s own logits; we do not report external-LM PPL, MAUVE, or human-rater scores. The detector is “model-free” in needing no LM forward pass at detection, but requires the same tokenizer used at generation; an auditor handed plain text alone would enumerate candidate tokenizers. Both Theorem A.8 and Theorem A.4 cover an oracle-blind adversary only; an attacker with adaptive detector-query access (or σκ _κ access) can choose substitution targets to hit valid transitions, and is outside our threat model (query complexity open). FPR drift and theorem scope. The empirical FPR at the analytic threshold zα=2.326z_α=2.326 drifts to 1.71.7–2.0%2.0\% on non-watermarked LLM output (Table 3): natural-language tokens are not i.i.d. uniform over the SHA-256 partition, so the closed-form Hoeffding envelope (3(c)) sits below the empirical curve. Headline TPR numbers (Table 1–Figure 4) are at the analytic threshold for cross-method consistency, not an empirically calibrated 1%1\% FPR per cell. Theorem A.4 assumes i.i.d. uniform substitution at rate δ; NLLB back-translation (and the deferred paraphrase extension) preserves grammatical structure and correlates substitutions across positions. Our empirical curves (3(b)) sit above the (1−δeff)2(1- _eff)^2 slope, so the bound is conservative, not tight; δeff _eff is an effective-edit-rate proxy. 8 Conclusion We presented ChainMark, an active watermark with two operator-facing properties: a closed-form calibration S⋆(nmin,ρ,α)S (n_ ,ρ,α) mapping a regulator’s specification (target FPR, text length, budget) to the minimum state count, and a detector needing the key and tokenizer but no language model. Under uniform substitution it has a robustness threshold δ⋆=1−1/2≈29.3%δ =1-1/ 2≈ 29.3\% invariant in (S,ρ,n)(S,ρ,n), and both extend to every k-regular transition topology (Theorem A.2, Theorem A.4, Theorem A.6). Head-to-head against KGW and SWEET on three instruction-tuned LLMs across four domains at matched budget, ChainMark retains substantially more detection signal under translation and random-substitution attacks, at roughly 2×2× the baselines’ self-perplexity. The post-attack z ratio sits above the (1−δeff)2(1- _eff)^2 i.i.d. scaling, so the bound is conservative, not tight (Section 6). Five directions are immediate: (i) evaluate against grammar-preserving paraphrase (e.g. DIPPER), the strongest attack left untested; (i) tighten the analytic FPR bound under non-i.i.d. statistics, where the empirical-SD recalibration of Subsection D.2 closes the deployment gap but the closed form stays loose at large S (Table 3); (i) extend to longer-text regimes where small S⋆S operates; (iv) validate k-regular topologies at k≥3k≥ 3; and (v) characterise base LLMs, whose entropy profile differs from the instruct-tuned fleet. Impact Statement This paper develops watermarking infrastructure for LLM-generated content in service of AI governance regimes (EU AI Act Article 50, OECD Hiroshima Process). The contribution is dual-use, and we flag four asymmetric harms. Authorship tracking and chilling effects. Stronger watermarking exposes writers who relied on undetectable LLM use. Marginalised users (ESL writers, students under inequitable AI policies, whistleblowers reformulating sensitive content) bear asymmetric harm relative to incumbent users. End-user perplexity cost. ChainMark imposes a ≈2×≈ 2× self-perplexity cost (3.663.66 vs the 1.801.80–1.931.93 baseline range; Table 1). Deployers adopting ChainMark to satisfy a regulatory mark therefore impose a measurable quality cost on every user whose generation is gated, not just on adversaries who would try to evade detection. False positives. Mislabelling human-written text as machine-generated has real reputational and legal cost. We instrument the detector with a closed-form, regulator-facing target false-positive rate α rather than an unspecified threshold; the discussed empirical-quantile recalibration (Section 7, Subsection D.2) is the recipe a deployer should run before invoking detection on any production content. Adaptive adversaries are out of scope. Our security and robustness theorems cover an oracle-blind adversary; a regulator deploying ChainMark must not assume the watermark survives an attacker with detector-query access or with σκ _κ access (Section 7). The audit primitive is honest about non-adversarial mislabelling, not about adversarial spoofing or scrubbing under realistic API-query budgets. Any deployment should publish the detection regime (α, nminn_ , ρ, the recalibration recipe used) so users understand the conditions under which their outputs are, and are not, marked. References S. Aaronson (2023) Watermarking GPT outputs. Note: Blog post, https://scottaaronson.blog/?p=6823Accessed January 2026 Cited by: §2. M. Christ, S. Gunn, and O. Zamir (2023) Undetectable watermarks for language models. External Links: 2306.09194, Link Cited by: §2. European Commission AI Office (2025) First draft code of practice on transparency of ai-generated content. Note: Supporting implementation of EU AI Act Article 50 External Links: Link Cited by: §2. European Parliament and Council (2024) EU AI Act (Regulation 2024/1689). Note: Official Journal of the European Union External Links: Link Cited by: §1, §2. A. Grattafiori et al. (2024) The Llama 3 Herd of Models. Note: Model card: https://huggingface.co/meta-llama/Llama-3.1-8B-Instruct External Links: 2407.21783 Cited by: §6.1. A. Q. Jiang et al. (2023) Mistral 7B. Note: Model card: https://huggingface.co/mistralai/Mistral-7B-Instruct-v0.3 External Links: 2310.06825 Cited by: §6.1. J. Kirchenbauer, J. Geiping, Y. Wen, J. Katz, I. Miers, and T. Goldstein (2023) A watermark for large language models. In International Conference on Machine Learning (ICML), p. 17061–17084. Cited by: §C.4, §1, §2, §6.1. K. Krishna, Y. Song, M. Karpinska, J. Wieting, and M. Iyyer (2023) Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense. External Links: 2303.13408, Link Cited by: 1st item, §2. R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang (2024) Robust distortion-free watermarks for language models. Transactions on Machine Learning Research. Cited by: §1, §2. T. Lee, S. Hong, J. Ahn, I. Hong, H. Lee, S. Yun, J. Shin, and G. Kim (2024) Who wrote this code? watermarking for code generation (SWEET). In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), Cited by: §C.4, §1, §2, §4.4, §6.1. Y. Lu, A. Liu, D. Yu, J. Li, and I. King (2024) An entropy-based text watermarking detection method. External Links: 2403.13485, Link Cited by: §1, §2. E. Mitchell, Y. Lee, A. Khazatsky, C. D. Manning, and C. Finn (2023) DetectGPT: zero-shot machine-generated text detection using probability curvature. In International Conference on Machine Learning (ICML), p. 24950–24962. Cited by: §2. OECD (2024) Hiroshima AI process: international code of conduct for advanced AI systems. Note: Organization for Economic Co-operation and Development External Links: Link Cited by: §2. Qwen, :, A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, H. Lin, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Lin, K. Dang, K. Lu, K. Bao, K. Yang, L. Yu, M. Li, M. Xue, P. Zhang, Q. Zhu, R. Men, R. Lin, T. Li, T. Tang, T. Xia, X. Ren, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Wan, Y. Liu, Z. Cui, Z. Zhang, and Z. Qiu (2025) Qwen2.5 technical report. External Links: 2412.15115, Link Cited by: §6.1. V. S. Sadasivan, A. Kumar, S. Balasubramanian, W. Wang, and S. Feizi (2023) Can AI-generated text be reliably detected?. arXiv preprint arXiv:2303.11156. Cited by: §2. N. Team, M. R. Costa-jussà, J. Cross, O. Çelebi, M. Elbayad, K. Heafield, K. Heffernan, E. Kalbassi, J. Lam, D. Licht, J. Maillard, A. Sun, S. Wang, G. Wenzek, A. Youngblood, B. Akula, L. Barrault, G. M. Gonzalez, P. Hansanti, J. Hoffman, S. Jarrett, K. R. Sadagopan, D. Rowe, S. Spruit, C. Tran, P. Andrews, N. F. Ayan, S. Bhosale, S. Edunov, A. Fan, C. Gao, V. Goswami, F. Guzmán, P. Koehn, A. Mourachko, C. Ropers, S. Saleem, H. Schwenk, and J. Wang (2022) No language left behind: scaling human-centered machine translation. External Links: 2207.04672, Link Cited by: 2nd item, 3rd item, §6.3. E. Tian and A. Cui (2023) GPTZero: towards detection of AI-generated text using zero-shot and supervised methods. GPTZero. External Links: Link Cited by: §2. Appendix A Proofs and Formal Statements This appendix collects the formal versions of the results previewed in Section 5. Throughout, σκ(t)=ℋ(κ∥t)modS _κ(t)=H(κ\,\|\,t) S denotes the keyed state map and is treated as a random oracle (uniform on [S][S] and independent across distinct tokens). ϕφ is the fingerprint score of Equation 2, and we write Xi=σκ(ti),σκ(ti+1)X_i=T_ _κ(t_i), _κ(t_i+1) for the validity indicator at step i, with T=clkT=T^clk in the clockwork case. A.1 Null Variance Lemma The null variance underpins both the detection z-score and the universal robustness threshold; we isolate it as a lemma. Lemma A.1 (Null variance with zero pairwise covariance). Let T∈0,1S×ST∈\0,1\^S× S be k-regular: every row and every column has exactly k ones, with 1≤k≤S−11≤ k≤ S-1, and set p0=k/Sp_0=k/S. Under the random oracle null (i.i.d. uniform tokens), the indicators Xi=Tσκ(ti),σκ(ti+1)X_i=T_ _κ(t_i), _κ(t_i+1) satisfy [Xi]=p0E[X_i]=p_0 and Cov(Xi,Xj)=0Cov(X_i,X_j)=0 for all i≠ji≠ j, hence Var[ϕ(r)]=p0(1−p0)n−1.Var\! [φ(t^r) ]\;=\; p_0(1-p_0)n-1. (3) Proof. Write N+(s)=s′:T(s,s′)=1N^+(s)=\s :T(s,s )=1\ (equivalently Σk(s) _k(s) from Section 4) and N−(s′)=s:T(s,s′)=1N^-(s )=\s:T(s,s )=1\; by k-regularity, |N+(s)|=|N−(s′)|=k|N^+(s)|=|N^-(s )|=k for every s,s′s,s . Throughout this proof we operate under the random-oracle null with i.i.d. uniform tokens on V; the empirical FPR drift observed on natural-language text (Table 3, Section 7) is the practical price of this idealisation. Marginal mean. Conditioning on σκ(ti) _κ(t_i) and using row-regularity, Pr[Xi=1]=[|N+(σκ(ti))|/S]=k/S=p0. [X_i=1]=E\! [|N^+( _κ(t_i))|/S ]=k/S=p_0. Non-adjacent pairs. For |i−j|≥2|i-j|≥ 2, XiX_i and XjX_j depend on disjoint token pairs and thus on independent state evaluations of the random oracle (assuming the underlying tokens are distinct; coincidences contribute O(1/||)O(1/|V|) and are absorbed into the random-oracle approximation). Hence Cov(Xi,Xj)=0Cov(X_i,X_j)=0. Adjacent pairs. XiX_i and Xi+1X_i+1 share the token ti+1t_i+1. Conditioning on σκ(ti+1)=s′ _κ(t_i+1)=s , we have Pr[Xi=1∣σκ(ti+1)=s′]=|N−(s′)|/S=p0, [X_i=1 _κ(t_i+1)=s ]\;=\;|N^-(s )|/S\;=\;p_0, Pr[Xi+1=1∣σκ(ti+1)=s′]=|N+(s′)|/S=p0, [X_i+1=1 _κ(t_i+1)=s ]\;=\;|N^+(s )|/S\;=\;p_0, using column-regularity for the first identity. Conditional on σκ(ti+1) _κ(t_i+1), the indicators XiX_i and Xi+1X_i+1 depend on the disjoint random-oracle evaluations σκ(ti) _κ(t_i) and σκ(ti+2) _κ(t_i+2), so they are conditionally independent whenever ti≠ti+2t_i≠ t_i+2 (the coincidence event has probability 1/||1/|V| under iid uniform tokens and is absorbed into the random-oracle approximation, parallel to the non-adjacent case above). Therefore Pr[Xi=Xi+1=1]=s′[p0⋅p0]=p02, [X_i=X_i+1=1]\;=\;E_s \! [p_0· p_0 ]\;=\;p_0^2, and Cov(Xi,Xi+1)=0Cov(X_i,X_i+1)=0. Variance. ϕ=(n−1)−1∑i=1n−1Xiφ=(n-1)^-1 _i=1^n-1X_i is the average of n−1n-1 Bernoulli(p0)(p_0) random variables with all pairwise covariances vanishing, giving (3). ∎ A.2 Detection Bound and Calibration Theorem A.2 (Detection bound and calibration). Let wt^w be a ChainMark-watermarked sequence of length n with watermark fraction ρ and clockwork transition over S states; let rt^r be an i.i.d. random sequence over V. Then [ϕ(w)] \! [φ(t^w) ] =1S+ρS−1S, = 1S+ρ\, S-1S, (4) [ϕ(r)] \! [φ(t^r) ] =1S, = 1S, (5) Var[ϕ(r)] \! [φ(t^r) ] =(1/S)(1−1/S)n−1, = (1/S)(1-1/S)n-1, (6) z(ρ,S,n) z(ρ,S,n) =ρ(S−1)(n−1). =ρ (S-1)(n-1). (7) Under the midpoint threshold τmid=1S+ρ2S−1S _mid= 1S+ ρ2 S-1S, splitting the indicators into disjoint odd/even subsequences and applying Hoeffding gives FPR≤ 2exp(−2⌊(n−1)/2⌋((ρ/2)(S−1)/S)2).FPR\;≤\;2 \! (-2 (n-1)/2 ((ρ/2)(S-1)/S)^2 ). Using the Gaussian convention at the midpoint threshold, the minimum state count guaranteeing FPR≤αFPR≤α is S⋆(n,ρ,α)=⌈4zα2ρ2(n−1)+1⌉.S (n,ρ,α)\;=\; 4z_α^2ρ^2(n-1)+1 . (8) S⋆S is a provisioning bound: it is derived under the midpoint detector τmid _mid to give the regulator a 2×2× safety margin in the standardised mean gap. The operating detector deployed in Section 6 uses the tighter one-sided test z>zα\z>z_α\, so empirical TPR at the operating threshold exceeds the conservative midpoint prediction whenever S≥S⋆(n,ρ,α)S≥ S (n,ρ,α). Proof. Null mean. Under the random oracle, σκ _κ is uniform and independent across distinct tokens, so Xi∼Bernoulli(1/S)X_i (1/S) marginally and [ϕ(r)]=1/SE[φ(t^r)]=1/S. Watermark mean. At a gated position, Algorithm 1 sets σκ(ti+1)=(σκ(ti)+1)modS _κ(t_i+1)=( _κ(t_i)+1) S, so Xi=1X_i=1 deterministically. At an ungated position, Xi∼Bernoulli(1/S)X_i (1/S). With gate density ρ, [ϕ(w)]=ρ⋅1+(1−ρ)⋅1S=1S+ρS−1S.E[φ(t^w)]=ρ· 1+(1-ρ)· 1S= 1S+ρ S-1S. Null variance. Clockwork is the k=1k=1 instance of Subsection A.1 (column-regularity is trivial since |N−(s′)|=1|N^-(s )|=1), giving Var[ϕ(r)]=(1/S)(1−1/S)/(n−1)Var[φ(t^r)]=(1/S)(1-1/S)/(n-1). z-score. The signed mean gap is ρ(S−1)/Sρ(S-1)/S. Dividing by the null SD, z(ρ,S,n) z(ρ,S,n) =ρ(S−1)/S(1/S)(1−1/S)/(n−1) = ρ(S-1)/S (1/S)(1-1/S)/(n-1) =ρ(S−1)(n−1). =ρ (S-1)(n-1). FPR via Hoeffding. Adjacent indicators share a token and are not jointly i.i.d., so we split into X1,X3,X5,…X_1,X_3,X_5,… and X2,X4,X6,…X_2,X_4,X_6,…, two disjoint subsequences of m=⌊(n−1)/2⌋m= (n-1)/2 terms, each i.i.d. Bernoulli(1/S)Bernoulli(1/S). Since ϕφ is a (size-weighted) convex combination of these two subsequence means, ϕ≥τφ≥τ implies that at least one subsequence mean is ≥τ≥τ, so by Hoeffding plus a union bound, for any τ>1/Sτ>1/S, Pr[ϕ≥τ]≤2exp(−2m(τ−1/S)2). [φ≥τ]≤ 2 (-2m(τ-1/S)^2). Calibration. By the CLT for 1-dependent sequences (the Xi\X_i\ are 1-dependent and bounded with vanishing pairwise covariance), n−1(ϕ−1/S) n-1\,(φ-1/S) is asymptotically (0,p0(1−p0))N(0,p_0(1-p_0)) under the null, with p0=1/Sp_0=1/S. At the midpoint threshold τmid=1/S+(ρ/2)(S−1)/S _mid=1/S+(ρ/2)(S-1)/S, the null z-margin is (ρ/2)(S−1)(n−1)(ρ/2) (S-1)(n-1). Requiring it to exceed zαz_α, ρ2(S−1)(n−1)≥zα⟺S≥4zα2ρ2(n−1)+1, ρ2 (S-1)(n-1)\;≥\;z_α S\;≥\; 4z_α^2ρ^2(n-1)+1, and taking the ceiling yields (8). ∎ Proposition A.3 (Empirical-SD recalibration recipe). Let (1),…,(M)t^(1),…,t^(M) be M i.i.d. non-watermarked sequences from the deployed LM, and let z1,…,zMz_1,…,z_M be their detection z-statistics under ChainMark with (S,ρ)(S,ρ) fixed. Define μ μ =1M∑i=1Mzi, = 1M _i=1^Mz_i, σ^2 σ^2 =1M−1∑i=1M(zi−μ^)2, = 1M-1 _i=1^M(z_i- μ)^2, z⋆ z =μ^+zασ^. = μ+z_α\, σ. If the ziz_i are approximately Gaussian with mean μ μ and SD σ σ (a calibration-side assumption that holds far better than the i.i.d. random-oracle null assumed by Theorem A.2), then declaring H1H_1 when z>z⋆z>z has FPR →α→α as M→∞M→∞. When the z-null is measurably non-Gaussian (e.g. heavy-tailed at large S), the Gaussian plug-in z⋆z is replaced by the empirical-quantile drop-in zemp⋆=F^−1(1−α)z _emp= F^-1(1-α), where F F is the empirical CDF of zi\z_i\; this delivers the target FPR at any α by Glivenko–Cantelli regardless of null shape, with the Dvoretzky–Kiefer–Wolfowitz inequality giving supx|F^(x)−F(x)|=Op(M−1/2) _x\!| F(x)-F(x)|=O_p(M^-1/2) Monte-Carlo noise in the threshold. Proof. Standardise: (z−μ^)/σ^(z- μ)/ σ is asymptotically (0,1)N(0,1) as M→∞M→∞ by the standard plug-in argument (consistency of μ^,σ μ, σ + Slutsky), so Pr[z>μ^+zασ^]→Pr[(0,1)>zα]=α [z> μ+z_α σ]→ [N(0,1)>z_α]=α. The recipe leaves the watermarked side untouched: the watermarked z-distribution still concentrates around ρ(S−1)(n−1)ρ (S-1)(n-1) (Theorem A.2), which on natural-language text empirically exceeds z⋆z by an order of magnitude (Table 8), so TPR remains at 100%100\%. ∎ A.3 Universal Robustness Threshold Theorem A.4 (Universal robustness threshold). Suppose an oracle-blind adversary (without access to σκ _κ or the random oracle) independently replaces each token with probability δ by a fresh token whose state σκ _κ is uniform on [S][S] (so the substitutions are i.i.d. uniform in the partition; structured paraphrase / NLLB back-translation produces correlated edits and is treated empirically in Subsection 6.3). Standardise the post-attack z by the null standard deviation p0(1−p0)/(n−1) p_0(1-p_0)/(n-1) (the same scaling used pre-attack). Then for clockwork ChainMark with state count S and gate density ρ, [ϕ∣attack]=1S+ρ(1−δ)2S−1S.E[φ ]\;=\; 1S+ρ(1-δ)^2 S-1S. (9) Define the pre-attack and post-attack mean-gap signals gpre=ρ(S−1)/Sg_pre=ρ(S-1)/S and gpost=ρ(1−δ)2(S−1)/Sg_post=ρ(1-δ)^2(S-1)/S. Both share the same null SD, so the standardised-margin ratio is zpostzpre=gpostgpre=(1−δ)2, z_postz_pre\;=\; g_postg_pre\;=\;(1-δ)^2, (10) independent of (S,ρ,n)(S,ρ,n). Under the midpoint-threshold detection convention the critical edit fraction at which detection fails is δ⋆= 1−1/2≈ 0.293,δ \;=\;1-1/ 2\;≈\;0.293, (11) again independent of (S,ρ,n)(S,ρ,n). Proof. Let Mi∼Bernoulli(δ)M_i (δ), i.i.d. across i, indicate that tit_i has been replaced; modified tokens receive fresh uniform state by the random-oracle property. For each pair (ti,ti+1)(t_i,t_i+1), decompose on (Mi,Mi+1)(M_i,M_i+1): • (0,0)(0,0): both tokens survive. The indicator equals the pre-attack distribution, with mean 1/S+ρ(S−1)/S1/S+ρ(S-1)/S. Weight (1−δ)2(1-δ)^2. • (0,1)(0,1): ti+1t_i+1 fresh. By column-regularity (which is trivial for clockwork), [Xi]=1/SE[X_i]=1/S. Weight (1−δ)δ(1-δ)δ. • (1,0)(1,0): symmetric, by row-regularity. Mean 1/S1/S, weight δ(1−δ)δ(1-δ). • (1,1)(1,1): both fresh. Mean 1/S1/S, weight δ2δ^2. Combining, [ϕ∣atk] [φ ] =(1−δ)2[1S+ρS−1S]+(1−(1−δ)2)1S =(1-δ)^2\! [ 1S+ρ S-1S ]+(1-(1-δ)^2) 1S =1S+ρ(1−δ)2S−1S, = 1S+ρ(1-δ)^2 S-1S, proving (9). z-ratio independence. The mean gap above the null baseline 1/S1/S is g=ρ(S−1)/Sg=ρ(S-1)/S pre-attack and g(1−δ)2g(1-δ)^2 post-attack. We standardise both regimes by the null SD p0(1−p0)/(n−1) p_0(1-p_0)/(n-1) (the conventional one-sample z-test scaling, used as a fixed denominator across attacks); this is a definition, not an assumption that the post-attack alternative variance is null-bounded. Hence zpost/zpre=gpost/gpre=(1−δ)2z_post/z_pre=g_post/g_pre=(1-δ)^2, independent of (S,ρ,n)(S,ρ,n). Critical fraction. At the midpoint threshold τmid=1/S+(ρ/2)(S−1)/S _mid=1/S+(ρ/2)(S-1)/S, detection is defeated iff the post-attack mean drops below τmid _mid, i.e. ρ(1−δ)2S−1S<ρ2S−1S⟺(1−δ)2<12.ρ(1-δ)^2 S-1S\;<\; ρ2 S-1S (1-δ)^2\;<\; 12. Solving, δ⋆=1−1/2δ =1-1/ 2. The factors (S−1)/S(S-1)/S and ρ cancel on both sides; this is the structural reason for the universal threshold. ∎ A.4 k-Regular Generalisation We now lift the clockwork results to any k-regular adjacency. We recall the definition for the appendix. Definition A.5 (k-regular topology). T∈0,1S×ST∈\0,1\^S× S is k-regular (1≤k≤S−11≤ k≤ S-1) if every row and every column contains exactly k ones. Equivalently, T/kT/k is doubly stochastic. The induced detection baseline is p0=k/Sp_0=k/S. Theorem A.6 (k-regular calibration identities). Fix any k-regular adjacency T and let p0=k/Sp_0=k/S. Apply Algorithm 1 and Algorithm 2 with T in place of the clockwork matrix. Then for an i.i.d. random null sequence rt^r, a watermarked sequence wt^w with gate density ρ, and an oracle-blind adversary with per-token replacement rate δ (as in Theorem A.4), [ϕ(r)] [φ(t^r)] =p0, =p_0, (12) [ϕ(w)] [φ(t^w)] =p0+ρ(1−p0), =p_0+ρ(1-p_0), (13) Var[ϕ(r)] [φ(t^r)] =p0(1−p0)n−1, = p_0(1-p_0)n-1, (14) z(ρ,p0,n) z(ρ,p_0,n) =ρ(1−p0)(n−1)p0, =ρ (1-p_0)(n-1)p_0, (15) [ϕ∣atk] [φ ] =p0+ρ(1−δ)2(1−p0). =p_0+ρ(1-δ)^2(1-p_0). (16) Proof. Equation (12) and the variance (14) are immediate from Subsection A.1. Watermark mean. At a gated position, Algorithm 1 restricts the argmax to ⋃s′∈N+(s)s′ _s ∈ N^+(s)V_s , so σκ(ti+1)∈N+(σκ(ti)) _κ(t_i+1)∈ N^+( _κ(t_i)), i.e., Xi=1X_i=1. At an ungated position, Xi∼Bernoulli(p0)X_i (p_0). Averaging, [ϕ(w)]=ρ+(1−ρ)p0=p0+ρ(1−p0)E[φ(t^w)]=ρ+(1-ρ)p_0=p_0+ρ(1-p_0). z-score. Dividing the signed mean gap ρ(1−p0)ρ(1-p_0) by the null SD p0(1−p0)/(n−1) p_0(1-p_0)/(n-1) gives ρ(1−p0)(n−1)/p0ρ (1-p_0)(n-1)/p_0. At k=1k=1, p0=1/Sp_0=1/S and this reduces to ρ(S−1)(n−1)ρ (S-1)(n-1), recovering Theorem A.2. Post-attack mean. Repeat the four-case decomposition of Theorem A.4. The (0,1)(0,1) case requires column-regularity to give [Xi∣ti+1 fresh]=p0E[X_i t_i+1 fresh]=p_0 (the conditional in-degree |N−(s′)|/S|N^-(s )|/S must be p0p_0 uniformly in s′s ); the (1,0)(1,0) case symmetrically uses row-regularity. Hence [ϕ∣atk] [φ ] =(1−δ)2(p0+ρ(1−p0))+(1−(1−δ)2)p0 =(1-δ)^2(p_0+ρ(1-p_0))+(1-(1-δ)^2)p_0 =p0+ρ(1−δ)2(1−p0). =p_0+ρ(1-δ)^2(1-p_0). ∎ Corollary A.7 (Universal midpoint δ⋆δ ). Under the midpoint-threshold detection convention, every k-regular ChainMark scheme with 1≤k<S1≤ k<S (so p0<1p_0<1; the degenerate case k=Sk=S has every transition valid and is trivially undetectable) has critical edit fraction δ⋆= 1−1/2,δ \;=\;1-1/ 2, independent of the topology parameters (k,S,ρ,n)(k,S,ρ,n). Proof. The midpoint threshold is τmid=p0+(ρ/2)(1−p0) _mid=p_0+(ρ/2)(1-p_0). By (16), the post-attack mean drops below τmid _mid iff ρ(1−δ)2(1−p0)<ρ2(1−p0)⟺(1−δ)2<12,ρ(1-δ)^2(1-p_0)\;<\; ρ2(1-p_0)\; \;(1-δ)^2\;<\; 12, which is independent of (k,S,ρ,n)(k,S,ρ,n) once p0<1p_0<1 (i.e., k<Sk<S). Solving gives δ⋆=1−1/2δ =1-1/ 2. ∎ A.5 Security Against an Oracle-Blind Adversary Theorem A.8 (Pseudorandomness under random oracle, oracle-blind adversary). Assume the secret key κ has min-entropy at least λ and ℋH is modelled as a random oracle. Consider a polynomial-time adversary A without access to the random oracle, without access to the LM (or its per-position distribution), and without access to a reference text drawn from the same prompt distribution. A has only the watermarked output wt^w and the public scheme parameters (S,T)(S,T). Then A achieves: (i) key-recovery advantage at most q⋅2−λq· 2^-λ for a query budget q to any auxiliary oracle that depends on κ; (i) state-prediction success at most 1/S+negl(λ)1/S+negl(λ) on each fresh token t⋆t that has not been queried with the correct key, hence advantage negl(λ)negl(λ) over the uniform 1/S1/S baseline; (i) statistical distinguishing advantage at most negl(λ)negl(λ) between wt^w and a non-watermarked LM sample LMt^LM from the same prompt distribution, restricted to statistics that are measurable in the partition structure σκ _κ (i.e., to tests that look at state-transition patterns rather than raw token-id statistics). Proof. Without κ, the adversary’s view of ℋ(κ∥t)H(κ\,\|\,t) for any t is uniform on the oracle output space. Recovery probability q⋅2−λq· 2^-λ follows from a standard guessing argument over a min-entropy-λ key. State prediction with advantage greater than negl(λ)negl(λ) would imply distinguishing the random-oracle output from uniform, contradicting (i). For (i): a σκ _κ-measurable statistic (σκ())D( _κ(t)) that distinguishes wt^w from LMt^LM with advantage ε must, by the random-oracle property, distinguish the watermarked state sequence (which walks the chain at gated positions) from a state sequence drawn uniformly on [S]n[S]^n (the LM’s σκ _κ-image is uniform iid by (i)). Such a D yields a state-predictor with advantage at least ε on some fresh token, contradicting (i) by a hybrid argument; hence ε≤negl(λ) (λ). Token-id-level statistics that exploit natural-language marginals (e.g., bigram frequencies) are explicitly outside this guarantee: they are not σκ _κ-measurable and trivially distinguish any LM sample from i.i.d. uniform tokens. ∎ A.6 Optimal LM-Aware Detector Theorem A.9 (Entropy-weighted detector is asymptotically locally most powerful). Suppose the verifier has access to the LM at each position, and let gi∈0,1g_i∈\0,1\ denote the gate indicator at position i. Set πi=gi+(1−gi)/S _i=g_i+(1-g_i)/S, the marginal probability of Xi=1X_i=1 under the watermark alternative. Approximating the joint law Xi\X_i\ by the product of its marginals (asymptotically valid under the random oracle on distinct tokens, with the product-form CLT covariance vanishing by Subsection A.1), the log-likelihood ratio under the product law is Λ=∑i=1n−1[Xilog(πiS)+(1−Xi)log1−πi1−1/S]. \;=\; _i=1^n-1\! [X_i ( _iS)+(1-X_i) 1- _i1-1/S ]. (17) Then the test Λ>cα\ >c_α\, with cαc_α the size-α critical value of Λ under the null, is asymptotically locally most powerful within the product hypothesis class, i.e. it attains the Neyman–Pearson power against the product-form approximation of the joint law, with the 11-dependence of Xi\X_i\ contributing only o(1)o(1) corrections in the LAN regime. Proof. Under the null, Xi∼Bernoulli(1/S)X_i (1/S) marginally with pairwise zero covariance (Subsection A.1). Under the watermark alternative, Xi∼Bernoulli(πi)X_i ( _i). The sequence Xi\X_i\ is 1-dependent: XiX_i and Xi+1X_i+1 share ti+1t_i+1, but for |i−j|≥2|i-j|≥ 2, Xi⟂XjX_i X_j under the random-oracle model on distinct tokens. The product-form likelihood ratio is Λ =∑ilogπiXi(1−πi)1−Xi(1/S)Xi(1−1/S)1−Xi = _i _i^X_i(1- _i)^1-X_i(1/S)^X_i(1-1/S)^1-X_i =∑iXilog(πiS)+(1−Xi)log1−πi1−1/S, = _iX_i ( _iS)+(1-X_i) 1- _i1-1/S, matching the theorem statement (with the convention 0log0=00 0=0 for terms with πi=1 _i=1, i.e., gated positions where Xi=1X_i=1 is deterministic). The Neyman–Pearson lemma applied to the product hypothesis identifies Λ as uniformly most powerful for the product law. By the central limit theorem for 1-dependent sequences (and vanishing pairwise covariance from Subsection A.1), the product-form Λ has the same Gaussian limit as the product-form joint LLR up to o(1)o(1) corrections (LAN regime, Le Cam); we therefore claim asymptotic local most-powerful-ness among tests within the product hypothesis class, not strict Neyman–Pearson optimality against the true 1-dependent joint. Hence the test based on Λ achieves the Neyman–Pearson power asymptotically. ∎ A.7 Detector Pseudocode We restate the model-free detection algorithm for self-contained reading; the body version is Algorithm 2. Algorithm 3 ChainMark Watermark Detection (model-free) Input: text x, key κ, states S, transition T, threshold τ ←Tokenize(x)t (x); c←0c← 0; n←||n←|t| for i=1i=1 to n−1n-1 do si←ℋ(κ∥ti)modSs_i (κ\,\|\,t_i) S; si+1←ℋ(κ∥ti+1)modSs_i+1 (κ\,\|\,t_i+1) S if T[si,si+1]>0T[s_i,s_i+1]>0 then c←c+1c← c+1 end if end for ϕ←c/(n−1)φ← c/(n-1); p0←(∑s,s′T[s,s′])/S2p_0←( _s,s T[s,s ])/S^2 z←(ϕ−p0)/p0(1−p0)/(n−1)z←(φ-p_0)/ p_0(1-p_0)/(n-1) return ([ϕ>τ],ϕ,z, 1−Φ(z))(1[φ>τ],\ φ,\ z,\ 1- (z)) The runtime is O(n)O(n) hash evaluations and a single pass over the token stream; no LM access is required. The transition T is the same matrix used at generation time, so the random baseline p0p_0 is computed directly from T (clockwork: p0=1/Sp_0=1/S; soft-cycle: p0=2/Sp_0=2/S; general k-regular: p0=k/Sp_0=k/S). A.8 Supplementary Results: Quality Cost and Self-Healing These two results were stated in earlier drafts; we retain the formal statements and proofs in the appendix for completeness, since they are referenced from elsewhere in the paper. Theorem A.10 (Quality cost identity and Jensen lower bound). At a gated position with current state s and partition mass Zs=p((s+1)modS)>0Z_s=p(V_(s+1) S)>0, the KL between the renormalised ChainMark distribution PChainMark(t)=p(t)/Zs⋅[t∈(s+1)modS]P_ChainMark(t)=p(t)/Z_s·1[t _(s+1) S] and the LM distribution p is DKL(PChainMark∥p)=log(1/Zs).D_KL(P_ChainMark\,\|\,p)= (1/Z_s). Under hash uniformity, [Zs]=1/SE[Z_s]=1/S, and Jensen’s inequality gives [DKL]≥logS,E[D_KL]\;≥\; S, (18) with equality iff ZsZ_s is constant in the key. Averaged over positions with gate rate ρ, [DKL]tok≥ρlogSE[D_KL]_tok≥ρ S. Proof. Direct computation: DKL(PChainMark∥p)=∑t∈(s+1)modS(p(t)/Zs)log(1/Zs)=log(1/Zs).D_KL(P_ChainMark\,\|\,p)= _t _(s+1) S(p(t)/Z_s) (1/Z_s)= (1/Z_s). Under hash uniformity, Pr[t∈(s+1)modS]=1/S [t _(s+1) S]=1/S for every fixed t, so [Zs]=∑tp(t)/S=1/SE[Z_s]= _tp(t)/S=1/S. Concavity of log and Jensen give [logZs]≤log[Zs]=−logSE[ Z_s]≤ [Z_s]=- S, hence [log(1/Zs)]≥logSE[ (1/Z_s)]≥ S. The token-averaged bound follows by averaging over positions with gate rate ρ. ∎ Theorem A.11 (Self-healing against oracle-blind adversaries). Let q⊆T_q be the set of tokens the adversary has queried with the correct key. For any token t′∉qt _q that the adversary introduces, σκ(t′) _κ(t ) is uniform on [S][S] by the random-oracle property, so each modified position contributes an indicator distributed as Bernoulli(1/S)Bernoulli(1/S) to the validity count, independently of strategy. Hence under an oracle-blind adversary (every introduced token unqueried), the expected mass contributed to ϕφ by modified-pair positions equals m(δ)=1Sδ(2−δ);m(δ)\;=\; 1S\,δ(2-δ); (19) this is a lower bound when ranging over query-aided strategies that may bias replacement tokens toward σκ(q) _κ(T_q). Proof. The fraction of token pairs (ti,ti+1)(t_i,t_i+1) touching at least one modified token is 1−(1−δ)2=δ(2−δ)1-(1-δ)^2=δ(2-δ). Each such pair contributes an indicator with conditional expectation 1/S1/S by the same column- and row-regularity argument as in Theorem A.4. Strategies in which the adversary introduces previously-queried tokens (whose state is in σκ(q) _κ(T_q)) can craft pairs that hit valid transitions deterministically, raising ϕφ above m(δ)m(δ), which only helps detection. Hence the expected modified-pair contribution to ϕφ satisfies ≥m(δ)=δ(2−δ)/S≥ m(δ)=δ(2-δ)/S for every oracle-blind strategy, and this floor is therefore strategy-free. ∎ Appendix B Reference Tables B.1 Closed-Form Calibration Lookup Table 4: Calibration lookup S⋆(n,ρ,α)S (n,ρ,α) from Theorem A.2. Rows are text lengths; columns are (α,ρ)(α,ρ) pairs. Entries are derived analytically from the closed-form detection bound and do not require empirical anchoring. α=10−3α=10^-3 α=10−6α=10^-6 n ρ=0.3ρ=0.3 ρ=0.5ρ=0.5 ρ=0.3ρ=0.3 ρ=0.5ρ=0.5 100 6 3 12 5 200 4 2 7 3 500 2 2 4 2 1000 2 2 3 2 Appendix C Experimental Protocol and Reproducibility This appendix records every setting needed to reproduce the head-to-head matched-budget study of Section 6, the per-cell tables in the main results, and every figure. C.1 Models, Tokenizers, and Hardware Model fleet. The headline experiments use three instruction-tuned 7–8B parameter open-weight LLMs, each loaded via the Hugging Face transformers library. The exact repo_id, revision pin, and torch_dtype for every model are listed in the public code release alongside its prompt template; we do not enumerate them here in order to keep the discussion model-agnostic. Each model is run on a single NVIDIA GPU (H100 or H200, depending on memory pressure); CPU fallback is supported for the detector but not for generation. Every model uses its own native tokenizer, both for generation and for detection, and self-perplexity (PPL) is computed on the same model’s logits that produced the text. Decoding. Watermarked positions use greedy argmax over the allowed-partition mask of Algorithm 1; ungated positions use temperature sampling at T=0.7T=0.7. The same temperature is used to draw pilot generations for gate-threshold calibration. Gated models. A subset of the fleet is gated on the Hugging Face Hub. The released environment expects an HF_TOKEN in scope at runtime; the token is read by huggingface_hub and never logged to disk. We do not name specific gated repositories in this appendix; the public code drop records each repo_id alongside its license terms. C.2 Domains and Prompts Four domains, N=200N=200 prompts each. Each domain runs on n=200n=200 prompts drawn from a fixed pool, identical across gates, models, and attacks within a cell. • Code: HumanEval Python signatures with their natural-language docstrings as the prompt; the generation is the function body. • Factual: short closed-answer prompts asking for a single attested fact (capitals, dates, named entities). • Wiki: open-ended descriptive prompts derived from a curated Wikipedia concept list, expanded via a fixed template. • Writing: open-ended creative-writing prompts requesting a short narrative or argumentative passage. Every prompt set, with template strings, prompt indices, and a deterministic shuffle seed, is shipped under data/v7_min/<domain>/records.jsonl. C.3 ChainMark Hyperparameters Default cell. S=5S=5 states, clockwork transition T(s,s′)=[s′≡s+1(modS)]T(s,s )=1[s ≡ s+1 S], watermark budget ρ=0.5ρ=0.5, secret key fixed across all cells, runs, and models. State sweep. Subsection 6.5 sweeps S∈2,3,5S∈\2,3,5\ at fixed ρ=0.5ρ=0.5 to anchor the closed-form calibration of Theorem A.2 on data. k-regular topology. Subsection 6.4 runs the soft-cycle (k=2k=2) topology at the default cell and compares the empirical robustness threshold against δ⋆δ to validate Theorem A.6. C.4 Baseline Calibration The two baselines, KGW (Kirchenbauer et al., 2023) and SWEET (Lee et al., 2024), are matched to ChainMark’s budget at the cell level. SWEET is an entropy gate that activates the watermark only at high-entropy positions (the structural opposite of schemes that gate at low-entropy positions); we configure it so that the realised gate rate over the pilot pool is within ±0.02± 0.02 of ρ=0.5ρ=0.5, by quantile-matching τH _H to the (1−ρ)(1-ρ) quantile of the per-position entropy distribution. KGW runs at the same effective budget by construction, since it gates every position. All three schemes share the same secret key and the same generation pool. C.5 Attack Protocol Each watermarked generation is subjected to three independent attack streams; post-attack detection statistics are reported per cell in Section 6. • Random substitution (δ=0.20δ=0.20): ⌈0.20n⌉ 0.20\,n token positions chosen uniformly at random and replaced with uniform draws from the model’s tokenizer vocabulary. • Translation round-trip: EN →L→ L→ EN via the NLLB-200 distilled model (Team et al., 2022), where L∈French,German,Russian,ChineseL∈\French,German,Russian,Chinese\. Each language constitutes a separate cell. We do not include grammar-preserving paraphrase attacks in this release; their evaluation is deferred to the extended version. C.6 Randomisation random, numpy.random, and torch.manual_seed are all seeded to 42 at the start of each generation run. The random-substitution attack uses an independent seed (43). Bootstrap resamples in Section 6 use a per-contrast key derived deterministically from the cell descriptor. C.7 Released Artefacts For each generation we record the prompt, the watermarked output, the per-position gate signal, the realised gate rate ρ¯ ρ, PPL, the detector statistic ϕφ and its z-score, and every post-attack ϕφ, z, and detection flag. All tables and figures in this paper derive from these records. The code drop ships under the same repository as this paper; the per-domain JSONL records under data/v7_min/<domain>/records.jsonl are the source-of-truth for every empirical claim. Appendix D Additional Run Data and Open Extensions D.1 Translation Per-Pivot Breakdown Table 5: Per-pivot ChainMark translation robustness. TPR @ z>2.326z>2.326 for each NLLB-200 pivot under ChainMark S=5S=5, ρ=0.5ρ=0.5. All three models now cover four domains (factual, wiki, writing, code) at 2525 prompts each (m=100m=100 generations per row, 300300 per pivot column). ZH is the most aggressive pivot (δeff≈0.81 _eff≈ 0.81); FR, DE, RU are gentler (δeff≈0.69 _eff≈ 0.69). Model m clean FR DE RU ZH Llama-3.1-8B 100100 100% 85% 78% 81% 75% Mistral-7B 100100 100% 86% 92% 92% 77% Qwen-2.5-7B 100100 100% 78% 75% 78% 66% D.2 FPR Recalibration: SD Recipe and Failure Modes Table 6: Empirical-SD recalibration vs. failure modes, evaluated on n=3000n=3000 non-watermarked samples (10001000 per model). Goal: bring empirical FPR close to the α=1%α=1\% target while preserving TPR=100%=100\%. Only the empirical-SD recipe (Fix 1) brings FPR within ∼0.2 0.2 p of the target (1.17%1.17\%); the other four sit at 22–5%5\% FPR or collapse TPR. The iid-baseline row is the closed-form zα=2.326z_α=2.326 threshold without recalibration. The 2.07%2.07\% baseline on this n=3000n=3000 pooled corpus supersedes the 1.71.7–2.0%2.0\% per-S cells in Table 3 (which use the smaller Exp. 5 sub-design with n≈300n≈ 300 per cell). Method FPR TPR iid baseline (no fix; z>2.326z>2.326) 2.07% 100.0% Fix 1: empirical SD recal. 1.17% 100.0% Failure modes (reported, not adopted): Fix 2: Newey–West HAC 3.45% 100.0% Fix 3: k-skip (k=3k=3) 2.46% 2.2% Fix 4: stopword filter (top-200200) 5.18% 99.0% Fix 5: HDD-lite (inv.-freq. weighted) 2.35% 100.0% D.3 Apples-to-Apples Head-to-Head at Empirical FPR=1%=1\% Table 7: Empirically-calibrated head-to-head at FPR=1%=1\%. Each method’s threshold is the maximum across the per-model 99%99\% z-quantiles on a non-watermarked calibration corpus (the conservative recipe; per-model nulls in ChainMark: Llama 2.872.87, Qwen 2.872.87, Mistral 2.412.41, so ChainMark z⋆=2.87z =2.87; KGW per-model: Llama 2.772.77, Mistral 2.342.34, Qwen 2.622.62, so KGW z⋆=2.77z =2.77). ChainMark retains its TPR advantage at matched empirical FPR, confirming the analytical-threshold comparison in Table 1 is not an FPR artefact. SWEET is omitted from this table: the SWEET null z-distribution was not collected on the FPR corpus and cannot be reproduced from the released artefacts; a SWEET-recalibrated row is deferred to the extended version. Method TPRclean TPRrandom TPRZH ChainMark (ours, S=5S=5) 100.0% 099.9% 68.3% KGW γ=0.5γ=0.5 066.8% 042.1% 13.0% D.4 Empirical FPR=0%=0\% Achievability Table 8: FPR=0%=0\% by lifting the threshold to z⋆=maxiznwm,i+0.5z = _iz_nwm,i+0.5. Computed on the held-out non-watermarked corpus (∼1000 1000 samples per model). Watermarked text retains TPR=100%=100\% because clean ChainMark z at the canonical S=5S=5 (≈25≈ 25 across the three models; Table 3) is several times the maximum observed null z. KGW and SWEET cannot achieve this regime because their watermarked and non-watermarked z-distributions overlap. Model maxznwm z_nwm lifted z⋆z TPR @ z⋆z Llama-3.1-8B 7.837.83 8.338.33 100%100\% Qwen-2.5-7B 5.005.00 5.505.50 100%100\% Mistral-7B 4.824.82 5.325.32 100%100\% Open data and deferred extensions. The following experiments are deferred to the extended version of this paper: • DIPPER paraphrase attack. Grammar-preserving paraphrase via DIPPER (Krishna et al., 2023) on at least one (model, domain) cell. • k-regular validation at k≥3k≥ 3. Theorem A.6 predicts p0=k/Sp_0=k/S for any k-regular topology; we validate k∈1,2k∈\1,2\ only. • External-LM PPL or MAUVE quality metric. Self-PPL is conservative but circular; an external judge LM or MAUVE would give a model-independent quality reading. • Base (non-instruction-tuned) and ≥10≥ 10B LLMs. Our fleet covers only instruction-tuned 7–8B models. • ρ-sweep on the new fleet. The current headline runs use ρ=0.5ρ=0.5 only; the previous gate-invariance ablation was on a smaller setup. • Adversary with detector-oracle access. Theorem A.8 excludes adversaries who can query the detector; characterising query complexity is open. Appendix E Reference Detector Implementation The following 24-line Python listing is a self-contained, dependency-minimal reference implementation of Algorithm 2 for clockwork ChainMark. It takes a list of integer token IDs, a bytes key, a state count S, and a significance threshold α; it returns the fingerprint score ϕφ, the z-score, the one-sided p-value, and a binary detection flag. The listing is sufficient to independently verify any ChainMark-watermarked text given only the secret key, with no language-model access and no learned components. Extensions to arbitrary k-regular topologies (cf. Theorem A.6) require replacing the successor check states[i+1] == (states[i]+1) % S with a lookup T[states[i]][states[i+1]] > 0 and setting p0 = (T > 0).mean(); no other modification is needed. import hashlib from math import sqrt from scipy.stats import norm def sha_state(key: bytes, token_id: int, S: int) -> int: """SHA-256-based state assignment sigma_kappa(t) = H(kappa || t) mod S.""" h = hashlib.sha256(key + token_id.to_bytes(8, "big")).digest() return int.from_bytes(h[:8], "big") % S def detect_chainmark(token_ids, key: bytes, S: int, alpha: float = 0.01) -> dict: """Clockwork ChainMark detector; O(n) in the number of tokens.""" n = len(token_ids) if n < 2: return "phi": 0.0, "z": 0.0, "p_value": 1.0, "is_watermarked": False states = [sha_state(key, t, S) for t in token_ids] valid = sum(1 for i in range(n - 1) if states[i + 1] == (states[i] + 1) % S) phi = valid / (n - 1) p0 = 1.0 / S se = sqrt(p0 * (1.0 - p0) / (n - 1)) z = (phi - p0) / se p_value = 1.0 - norm.cdf(z) return "phi": phi, "z": z, "p_value": p_value, "is_watermarked": p_value < alpha Figure 5: Reference detector for clockwork ChainMark: 24 lines of dependency-minimal Python (hashlib + scipy.stats). Inputs are the tokenizer’s token IDs, the secret key, and the state count; outputs are the fingerprint ϕφ, z-score, one-sided p-value, and a binary detection flag. Complexity. Two SHA-256 evaluations per token (2n⋅2562n· 256 bits of hash output) and n−1n-1 integer equality checks. At n=100n=100 the entire detection pipeline runs in under 11 ms on a single CPU core; no GPU, no model weights, no tokenizer aside from what is needed to obtain token_ids. Interpretation as an audit primitive. The detector’s inputs are exactly what a third-party auditor could receive under an Article 50 disclosure regime: a public text, a detector program, and a (confidentially held) key. The output is a p-value with analytically known false-positive behaviour under the null, sidestepping the calibration-by-grid-search problem that afflicts logit-bias watermark families. Key management. The scheme’s security reduces to the confidentiality of key plus the random-oracle idealisation of SHA-256 (Theorem A.8). In practice an auditor and a deployer can share the key through any standard key-management substrate (e.g., HKDF-derived per-deployment keys, committed to an external ledger so that the commitment precedes generation). Rotating keys per deployment epoch preserves the p0=k/Sp_0=k/S null baseline without changing any detector behaviour. Appendix F Prompt and Generation Examples This appendix shows representative prompts from each of the four content domains used in Section 6, together with the exact ChainMark configuration and post-attack pipeline that produced the headline numbers in Table 1 and Figure 4. All three models receive the same prompt verbatim with no system prompt prepended; decoding parameters (T=0.7T=0.7, top-p=1p=1, n=200n=200 tokens, deterministic prompt-order seed) are also held fixed across models and methods. Prompt examples per domain. • Code (HumanEval problem stems, 164164 problems available; we use the first 100100): from typing import List def has_close_elements(numbers: List[float], threshold: float) -> bool: """Check if in given list of numbers, are any two numbers closer to each other than given threshold.""" • Factual (short closed-form knowledge prompts): The capital of France is • Wiki (open-ended “Explain X…” prompts over a curated 176176-entry concept list): Explain Donald Trump in a comprehensive way. • Writing (creative-completion prompts): Write a short story that begins: The colony ship arrived three centuries late, and someone was already waiting. ChainMark generation configuration (used in Table 1). At each generation step on the prompt above, the model produces a distribution over its native vocabulary; ChainMark then masks logits at gated positions (gate density ρ=0.5ρ=0.5, high-entropy gate GHhighG_H_high) to keep only token IDs whose state σκ(t)=SHA-256(κ∥t)modS _κ(t)=SHA -256(κ\,\|\,t) S equals (s+1)modS(s+1) S, where s is the previous token’s state. At ungated positions the model samples at T=0.7T=0.7 from the original distribution. The secret key κ is fixed for the full campaign; in deployment a regulator-side audit re-derives the same state sequence from the same key with the model’s tokenizer. Attack-pipeline example. Given the watermarked text x (say, 200200 tokens of a wiki-domain answer), the three attack conditions in Table 1 apply respectively: • Clean. Detect on x as-is. • Random substitution at δeff=0.20 _eff=0.20. Replace a uniformly random 20%20\% of tokens with a uniformly sampled vocabulary token, then detect on the corrupted text. • ZH back-translation. Pass x through NLLB-200 (Team et al., 2022) English → Chinese → English; record the empirical token-edit-distance δeff _eff (≈0.81≈ 0.81 for ZH on average, Table 5); then detect on the round-tripped text. The detector runs the same σκ _κ and counts valid transitions; reports ϕφ, the standardised z, and a binary flag at z>zαz>z_α (Algorithm 3, Figure 5). Token-level walkthrough. For the wiki prompt Explain Donald Trump in a comprehensive way. on Llama-3.1-8B-Instruct at S=5S=5, ρ=0.5ρ=0.5, an illustrative excerpt of the first 2020 generated tokens looks roughly as below. We show the (token, state) pair at each position and mark gated steps with ∙ (the gate raised the mask; ChainMark forced si+1=(si+1)mod5s_i+1=(s_i+1) 5) versus ungated steps with ∘ (no mask; the model sampled freely): Donald2 ∘ Trump3 ∘ (born4 ∙ June0 ∙ 141 ∙ , 19462 ∙ ) is3 ∙ a4 ∘ former4 ∘ U.S.0 ∙ president1 ∙ and2 ∙ businessman3 ∙ … At gated positions the next token’s state is forced to be (prev+1)mod5(prev+1) 5 (here S=5S=5, so the cycle is 0→1→2→3→4→00→1→2→3→4→0); the model picks the highest-prob token whose state matches that requirement. At ungated positions any token may follow. The gate threshold τ is calibrated on a pilot so the realised gate rate tracks ρ=0.5ρ=0.5. Detection on this excerpt. A regulator running the detector (Figure 5) on the same string with the same key κ re-derives the state sequence 2,3,4,0,1,2,3,4,4,4,0,1,2,3,…2,3,4,0,1,2,3,4,4,4,0,1,2,3,… and observes 11/1411/14 valid transitions, i.e. ϕ=0.79φ=0.79. With p0=0.20p_0=0.20 and n=14n=14, z=(0.79−0.20)/0.16/13≈5.3z=(0.79-0.20)/ 0.16/13≈ 5.3, well above z0.01=2.326z_0.01=2.326, so the detector flags “watermarked”. A non-watermarked sample of the same length under the null distribution averages ϕ≈0.20φ≈ 0.20 and z≈0z≈ 0.