SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints

SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints Benjamin D. Kim1 , Wanrong Zhang2 , Weitong Ruan3 , Lav R. Varshney4 , and Daniel Alabi5

arXiv:2610.05712v1 [cs.CR] 5 Oct 2026

1

Massachusetts Institute of Technology 2,3 Amazon 4 Stony Brook University 5 University of Illinois Urbana-Champaign

Abstract We introduce a framework for multi-bit text watermarking with security defined directly through f -divergence from the base language model distribution. Unlike prior approaches that focus on average-key distortion-freeness or a particular statistical distance, our formulation supports general f -divergences, including total variation and KL divergence, and enforces the guarantee for each realized key and embedded message. We develop a coding-based watermarking scheme that optimally biases next-token distributions subject to a prescribed divergence budget, and characterize the resulting tradeoff between embedding rate, decoding reliability, and statistical security. Experimentally, we compare our method against prior multi-bit watermarking schemes across modern language models and payload regimes. Our approach achieves substantially lower watermark detectability while maintaining competitive message-recovery performance and generation quality. Our results provide a unified view of secure multi-bit watermarking and recover several commonly used security notions as special cases.

1

Introduction

Large language models (LLMs) can now generate fluent, high-quality text at scale. This creates new challenges for provenance, accountability, and policy enforcement [LMC+ 24]. Text watermarking offers a promising response: a model provider can embed a hidden signal into generated text so that the output can later be detected or decoded [KGW+ 23]. While early watermarking schemes primarily focus on zero-bit detection (to ascertain the presence of a watermark) [CGZ23, KTHL24, KGW+ 23], many applications require multi-bit watermarking, where the generated text carries a message such as a user identifier, model identifier, timestamp, or policy tag [CMB+ 07]. Multi-bit watermarking introduces a fundamental tension: increasing the payload generally requires a stronger perturbation of the model’s next-token distribution, making the watermark both easier to recover and easier to detect by an adversary [JWB+ 25]. Conversely, imposing stronger distributional constraints on the watermarked model, relative to the unwatermarked model, makes the watermark less detectable but limits the amount of information that can be reliably embedded. This raises a basic question: what are the capacity and detectability of a multi-bit text watermark while being as close as possible to the unwatermarked distribution? We study this question by comparing how far from the unwatermarked distributions different watermarks perturb down to individual token distributions and fundamentally how much information one can embed. To measure distance from the base model, we adopt per-key rather than average-key notions [GVL+ 26]. This 1

Figure 1: Watermark encoding and embedding process for SimpleMark: the watermarker starts by truncating the language model support according to the top-q, and places all the tokens on a q−ary simplex. Using the message M and the generator matrix G to create a codeword C, and computes the target vertex on the simplex, depicted in red in the diagram. The watermarker biases the watermarked distribution towards this token by α, and reduces the probability of sampling other tokens by β while remaining in the ε parameter f -divergence budget, Df (Q∗t ∥Qt ) ≤ ε, and samples from the watermarked distribution Q∗t . The message can then be decoded with one of the decoders. A detailed procedure is in Section 3.1. is because in adversarial settings [CHS25a, ZEF+ 24, AKV03], security should hold for the actual distribution produced in a realized execution, not after averaging over secret keys [KL14]. An average-key guarantee can mask large key-dependent deviations that give a distinguisher substantial advantage, motivating a stronger per-key notion of statistical indistinguishability [CMB+ 07]. Motivated by this observation, we introduce SimpleMark, a multi-bit text watermarking scheme that enforces an f -divergence ε-budget at each generation step. SimpleMark uses low density parity check (LDPC) codes with a geometry-aware (simplex) optimal transport embedding rule and maximum-likelihood decoding. The simplex geometry allows the reduction of the per-token embedding step to a two-scalar tilt computable in O(1), while the LDPC coding allows for improved, coding-theoretic reliability in recovery. Figure 1 graphically illustrates SimpleMark. In Section 3.1, we discuss the components of SimpleMark in more detail. Our contributions: First, we formalize multi-bit text watermarking as communication through a constrained watermark channel and identify the mutual information governing reliable message recovery. Second, we show a channel-collapse result: exact per-key distortion-freeness forces zero embedding capacity (i.e., no scheme can embed even a single bit) so distortion is not a defect of existing multi-bit watermarks but the price of embedding, and the right goal is to control it explicitly, through f -divergence constraints yielding a tunable capacity–detectability tradeoff. Third, we demonstrate that average-key distortion-freeness and other such metrics do not imply per-key undetectability and can lead to highly detectable realized-key behavior. Finally, we evaluate SimpleMark on modern language models showing it achieves competitive or state-of-the-art performance on reasoning and advanced tasks, recovery, perplexity, and more while substantially reducing the distributional deviation between the watermarked model and the base model.

2

Watermark

Per-token watermarkspecific overhead

Decoding cost

ArcMark BiMark StealthInk

O(I |V| r) O(d |V|) O(|V|)

O n(|V| + 2b ) O(nd + b) O(n|V| + (b/c)2c )

MC2 Mark

  ′
O m|V| + m nn′ /2 n′

O(n m n′ + b)

QuantileMark MirrorMark

O(|V| log |V| + M ) O(L |V|)

SimpleMark

Oq (1)

O(n(|V| log |V| + M ) + (b/m′ )M ) O(n(b/c + 2c L))
† O n|V| + 2b n

†

Table 1: Complexity comparison between SimpleMark and other known multi-bit watermark schemes. † Note the decoder requires a model replay. We assume q = 53 as a small constant. With respect to the complexities, the symbols can be defined as |V|: vocabulary; n: text length; b: payload bits. Method-specific symbols: r: side-information resolution and I: Sinkhorn iteration count for ArcMark [GVL+ 26]; d: reweighting layers for BiMark [FZZ+ 25] (d=10); m: channel layers and n′ : segment length in bits for MC2 Mark [CCWH26] (m=10; n′ unspecified in their experiments); c: bits per message chunk for StealthInk [JWB+ 25] and MirrorMark [JBKZ26] (c=1 and c=2 respectively; both papers denote this m); L: tournament layers for MirrorMark (L=30). M : quantile bins per ′ step for QuantileMark [ZHW26] (M = 2m with m′ bits per message symbol).

1.1

Related Work

Multi-bit Watermarks Recently, a variety of multi-bit watermarks have been developed for language models [YAK24, JWB+ 25, QZT+ 25, XJY+ 25, JBKZ26, CCWH26]. Two prominent ones are BiMark [FZZ+ 25] and ArcMark [GVL+ 26]. A pivotal advancement is the development of provably robust frameworks; [QZT+ 25] use error-correction codes (ECC) to provide formal guarantees within specific edit-distance bounds, whereas [CHS25b] establishes resistance against adaptive prompting. Recent work such as [XHKZ26] further optimizes this tradeoff by employing block-wise encoding to ensure high recovery rates even in short-form textual outputs, while [GVG+ 26] incorporates feedback coding. To the best of our knowledge, these previous works do not provide an explicit per-key mechanism for directly tuning a prescribed divergence budget (e.g., for total variation or KL) at each generation step. Watermarking Capacity Our work connects to the information-theoretic literature of watermarking, data hiding, and steganography, where watermarking is modeled as communication over a constrained channel: the encoder embeds a message into a host signal subject to a distortion or detectability constraint, and the decoder attempts to recover it [Cac04, CMB+ 07]. Early work characterized achievable rates for information hiding under distortion and attack constraints [MO03, Mou03, Mou05, MK05], and coding-based schemes such as quantization-index modulation showed how structured codes can approach these limits [CW01]. In the language model setting, the host distribution is the base model’s next-token distribution, so the relevant constraint is distributional rather than perceptual. Recent work has begun to analyze LLM watermarking through this lens [GVL+ 26, HLW+ 25]. We further extend this capacity viewpoint of multi-bit text watermarking by comparing average-key distortion-freeness, uniform per-key total-variation closeness, and perfect distortion-freeness. Our results show that stronger per-key distortion-freeness constraints reduce the mutual information of the induced watermark channel, and exact per-key distortion-freeness forces zero embedding capacity. 3

2

Preliminaries and Notation

First, we introduce some useful notation and background, many of which can be found in standard textbooks [Ros98, Gut13, MU05, Kee10]. f -divergences. Let f : (0, ∞) → R be convex with f (1) = 0. For distributions P, Q on X with P P (x)
P ≪ Q, the f -divergence of P from Q is Df (P ∥Q) := x∈X Q(x) f Q(x) . Every f -divergence satisfies the data-processing inequality: Df (κ(P )∥κ(Q)) ≤ Df (P ∥Q) for any (possibly randomized) map κ [PW25]. We next discuss the two f -divergences this work focuses on. Total variation distance. For probability P measures P, Q on measurable space (X , F), we define dTV (P, Q) := supA∈F |P (A) − Q(A)| = 12 x∈X |P (x) − Q(x)|. Equivalently, total variation distance characterizes the maximum distinguishing advantage of any adversarial attacker trying to decide whether a sample was drawn from P or Q [KL14]. In particular, for any possibly randomized distinguisher D : X → {0, 1}, sup Pr [D(X) = 1] − Pr [D(X) = 1] = dTV (P, Q). D

X∼P

X∼Q

Relating to this work, we want the TV distance of the watermarked and unwatermarked distributions to be as small as possible, so an adversary has the smallest possible advantage in determining whether outputted text is watermarked or not. Kullback–Leibler divergence. For distributions P, Q on aPfinite alphabet X with P ≪ Q, the P (x) Kullback–Leibler divergence of P from Q is DKL (P ∥Q) := x∈X P (x) log Q(x) . In our setting, KL(P ∥Q) is the expected excess log-loss incurred when text generated by the watermarked distribution P is scored by the base model Q, and thus
relates directly to perplexity: writing H(P ) for the entropy of P , PPL = exp Ex∼P [− log Q(x)] = eH(P ) eKL(P ∥Q) . Here, eKL(P ∥Q) is related to the multiplicative perplexity inflation introduced by watermarking. Watermarked distribution. Fix ε ≥ 0. A watermarked distribution Q⋆t = PXt |M =m,Vt =v is said to be (uniformly per-key) ε-distortion-free
if for every time t, every message m ∈ M, and every realized key value v, Df PXt |M =m,Vt =v ∥ Qt ≤ ε. Equivalently, when the encoder depends on (m, v) only through the
state Zt = zt (m, v), the distribution is (uniformly per-key) ε-distortion-free iff Df PXt |Zt =z ∥ Qt ≤ ε for every realizable z ∈ Z, ∀t. For our watermark, we can set ε to be a constant or to be cryptographically negligible (depending on the target security application). When ε = 0, we obtain perfect distortion-freeness.

3

Main Results

This section contains our main theoretical results. We begin by describing SimpleMark’s encoding, embedding, and decoding algorithms.

3.1

Algorithms

We describe SimpleMark being used in practice. Its components include: • Encoder: The message is coded with an LDPC code and then combined with the shared secret to compute the target vertex. 4

• Embedding: at each time t, the watermarked distribution Q⋆t is computed in closed form while adhering to the divergence budget. The watermarked token Xt is sampled. • Decoding: a decoder uses a likelihood decoder to compute M̂ . Alternatively, we provide a plurality decoder where only the received symbols are required. Encoding and embedding are given in algorithm form in Appendix A. Message Encoding The watermarker begins with a k-symbol message m and encodes it with a q-ary LDPC code, resulting in a length-n codeword C1 . . . Cn over Fq for a prime q. For a k × n systematic generator matrix G corresponding to a sparse parity-check matrix H, the resulting codeword is C = m · G. The generator matrix can be considered public information. At each step t, the shared secret St = (Vt , σt ) is derived by hashing the secret key with the h previously generated tokens, so both parties recompute it from the text itself. It consists of a key value Vt uniform on R = {0, . . . , q − 1} and a keyed bijection σt : St → R, where St ⊂ V is the top-q truncated support of the vocabulary V, so |St | = q and each vertex receives exactly one token. We identify codeword symbols, key values, and colored tokens with the vertices of the (q − 1)-simplex: the codeword symbol Ct ∈ Fq is mapped to vertex Ct , the key value Vt to vertex Vt , and the token x ∈ St to vertex σt (x). The channel input vertex at time t is then Zt = (Ct + Vt ) mod q.

(1)

This vertex determines the target location on the simplex toward which the embedding step biases the next-token distribution, while the divergence constraint controls how far the resulting watermarked distribution may deviate from the base model distribution. Message Embedding SimpleMark constructs a watermarked distribution Q⋆t by solving a constrained minimization problem which admits a closed-form solution. For each token, let σt (x) be the vertex assigned to x, where σt is the random bijection shared between the watermarker and detector at time t, and let Zt be the target vertex defined in (1). We define the embedding cost dt (x) = 1[σt (x) ̸= Zt ] , which is the discrete metric on the vertex set, since all pairs of vertices are equidistant. The watermarked distribution is then chosen as X Q⋆t ∈ arg min P (x)dt (x) s.t. D(P, Qt ) ≤ ε, (2) P ∈∆(St )

x∈St

where ε is the selected divergence budget and D is a selectable f -divergence, taken here to be either dT V or DKL . Equivalently, the embedding step moves as much probability mass as permitted by the constraint onto the token coloured Zt , while keeping the watermarked distribution within distance ε of the base model distribution. Because the cost is an indicator,P the objective in (2) dependsPon P only through the mass it places on the target vertex. Writing B = x:σt (x)=Zt Qt (x) and s = x:σt (x)=Zt P (x), the data-processing inequality gives D(P, Qt ) ≥ D(Bern(s), Bern(B)). Equality is attained by preserving the conditional distributions within the target and non-target bins. The optimum of (2) is therefore the two-scalar tilt ( αt Qt (x), σt (x) = Zt , s⋆ 1 − s⋆ Q⋆t (x) = αt = , βt = , (3) B 1−B βt Qt (x), σt (x) ̸= Zt ,

5

where s⋆ = B + min(ε, 1 − B) when D = dT V , and s⋆ is the unique root in [B, 1] of s log Bs + (1 − 1−s s) log 1−B = ε when D = DKL .1 In certain settings, it is beneficial to limit the tilt towards unwanted tokens by capping α. Finally, the next token is sampled according to Xt ∼ Q⋆t (· | x<t ). The generated token is appended to the context, and the procedure is repeated for t = 1, . . . , n. Message Decoding SimpleMark is decoded with a likelihood-based decoder that uses the watermarked channel law. Given the prompt and received token sequence x1:n , the decoder replays the language model to recover the base next-token distributions Qt (·) = Q(· | x<t ). It also reconstructs the shared key sequence St = (Vt , σt ). For each possible code symbol a ∈ {0, . . . , q − 1}, the decoder forms the corresponding target vertex zt (a) = (a + Vt ) mod q. Using this vertex, the decoder evaluates the probability assigned to the observed token xt by the divergence-constrained embedding distribution:  ⋆ s  σt (x) = zt (a),  a Qt (x), X B a Q⋆t,a (x) = Ba = Qt (x), ⋆   1 − sa Qt (x), σt (x) ̸= zt (a), x:σt (x)=zt (a) 1 − Ba with s⋆a obtained from Ba and ε as in the embedding step. This defines the per-symbol log-likelihood Lt (a) = log Q⋆t,a (xt ). For a candidate P message m̂ with codeword C(m) = (C1 , . . . , Cn ), the decoder sums these likelihoods: Λ(m̂) = nt=1 Lt (Ct (m̂)). The decoded message is the maximum-likelihood codeword, M̂ = arg maxm̂ Λ(m̂). Simply, the decoder selects the message whose codeword is most likely to explain the observed token sequence under the same divergence-constrained channel used for embedding. In Appendices A and B, we derive more extensive theoretical results about our watermarking scheme, the watermark channel family, encoding and decoding capabilities, embedding capacity, and perplexity. We discuss a few of those results here. We acknowledge the simplicity of our results; deriving rate under a non-memoryless conditional is much more complicated and remains interesting future work. Most of our theoretical results are applicable to all f -divergences compatible with SimpleMark.

3.2

Perfect Distortion-Freeness

We show that for perfect distortion freeness, that is when the watermarked distribution is equivalent to that of the unwatermarked, the watermark’s capacity is zero. This motivates having an ε-budget that is a measurable f -divergence distance from the unwatermarked distribution. Proposition 1 (Rate vanishes as ε → 0). Let X and Z be finite alphabets, let Q ∈ ∆(X ) be a fixed base distribution, and let PZ be a fixed distribution on Z. For ε ≥ 0, define the feasible set n o
F(ε) := PX|Z=z z∈Z : dTV (PX|Z=z , Q) ≤ ε for all z ∈ Z . Define the constrained capacity C(ε) := sup

PX|Z=z ∈F (ε)

I(Z; X), where the mutual information is

computed under the joint law PZ,X (z, x) = PZ (z)PX|Z=z (x). Then limε→0 C(ε) = 0. In particular, any achievable embedding rate under the uniform per-key TV constraint must approach 0 as ε → 0. 1

For ε ≤ log(1/B). For ε > log(1/B), the constrained optimum is simply s∗ = 1.

6

Proof. We first show C(0) = 0. If PX|Z=z z∈Z ∈ F(0), then for every z ∈ Z, dTV (PX|Z=z , Q) = 0. Since total variation distance vanishes if and only if the two distributions are equal [Kee10], it follows that PX|Z=z = Q, for all z ∈ Z. Hence the conditional law of X does not depend on Z, so X and Z are independent. Therefore I(Z; X) = 0. Taking the supremum over all feasible channels shows that C(0) = 0. We now prove that C(ε) → 0 as ε → 0. Let (εn )n≥1 be any sequence with εn ↓ 0. For each n,
(n) choose a feasible channel family PX|Z=z z∈Z ∈ F(εn ) such that In := IP (n) (Z; X) ≥ C(εn ) − n1 . Q Because X and Z are finite, the product of simplices z∈Z ∆(X ) is compact [Mun84]. Hence, there (n)

⋆ exists [Rud64] a subsequence, which we still index by n, such that for every z ∈ Z, PX|Z=z → PX|Z=z
⋆ for some limiting channel family PX|Z=z . z∈Z     (n) ⋆ Since each P (n) is feasible, dTV PX|Z=z , Q ≤ εn for all z. Letting n → ∞ gives dTV PX|Z=z ,Q = ⋆ 0 for all z, and therefore PX|Z=z = Q for all z ∈ Z. So under the limiting channel, X is independent ⋆ of Z, and thus IP (Z; X) = 0. Because mutual information is continuous in the joint distribution on finite alphabets [PW25, CT06], we have In = IP (n) (Z; X) → IP ⋆ (Z; X) = 0. But C(εn ) ≤ In + n1 , so taking limits yields lim supn→∞ C(εn ) ≤ 0. Since mutual information is always nonnegative, C(εn ) ≥ 0, hence limn→∞ C(εn ) = 0. Because this holds for every sequence εn ↓ 0, it follows that limε→0 C(ε) = 0. This proves the claim.

Ideally, a watermarked model would sample from the base distribution itself, and each realized key would leave every next-token distribution exactly untouched. Proposition 1 shows this ideal is unachievable in principle: under exact per-key distortion-freeness the token is independent of the target vertex, the channel collapses, and the embedding capacity is zero; that is, no encoder or decoder can recover a single bit. Distortion is therefore not a defect to be engineered away but the price of embedding, and we make that price the design parameter: an explicit ε divergence budget, with Theorem 1 quantifying the capacity it buys.

3.3

Rate Bounds under Uniform Per-Key TV Constraints

Subsequently, we are able to solve for several capacity results, which can be found in Appendix B. We again emphasize that our theoretical results assume a simpler setting, but nonetheless provide meaningful insight to our watermark’s capacity. Let ε denote a TV distance budget. Theorem 1 (Rate under uniform per-key TV constraint (see Theorem 2)). Assume the conditionalmemoryless model. Let a sequence of length-n watermarking schemes satisfy the uniform per-key (n) c= ε-TV constraint, and let the decoder error probability Pe := Pr[M ̸ M ] tend to zero as n → ∞. If (n) P k et (ε)+ 1+nRn Pe , Rn := n denotes the embedded rate in bits per token, then for every n, Rn ≤ n1 nt=1 C n et (ε) is the universal constrained channel capacity given in the Appendix as Definition 5. where C P (n) et (ε). Consequently, if (Rn )n is bounded and Pe → 0, then lim supn→∞ Rn ≤ lim supn→∞ 1 n C n

4

t=1

Experimental Results

In this section we demonstrate SimpleMark’s efficacy experimentally. We evaluate SimpleMark’s reasoning abilities, watermarked token distinguishing advantage, message and bit decoding accuracy, and perplexity. To baseline our performance, we compare our results to ArcMark [GVL+ 26] and 7

Figure 2: Empirical total variation distance and distinguishing bound from an unwatermarked output and a watermarked output for a baseline, SimpleMark, Bimark, and ArcMark. The full bars represent Qwen3.5-9B-Base and the dashed bars represent Llama3.1-8B-Instruct. BiMark [FZZ+ 25]. Both watermarks have publicly available implementations, are state of the art for message recovery, and have some definition of distortion freeness the watermark adheres to. We use 300 trials per point unless specified.

4.1

Experiment Parameters

Setup. We experiment with Qwen3.5-9B-Base [Qwe26] and Llama3.1-8B-Instruct [GDJ+ 24]. When applicable, we use the C4-RealNewslike dataset [RSR+ 20] and a temperature of 1.0. Each trial generates 300 tokens and is evaluated at the prefix of 50, 100, . . . , 300 tokens. The reasoning experiments use the instruction-tuned Qwen3.5-9B in thinking mode with temperature 0.6. SimpleMark uses a field size of q = 53, and subsequently top-53 sampling. The other baselines use top-50 sampling. The ε budget is a per-step TV or KL constraint. We report results for ε ∈ {0.01, 0.05, 0.1, 0.15} and, where stated, with the per-token likelihood-ratio cap αmax ∈ {500, 1500, 2000}. BiMark [FZZ+ 25] is run with d = 10 partition layers, δ̃ = 1.0, context width 2 and top-50 sampling; ArcMark [GVL+ 26] with top-50 sampling, context width 2, r = 64 and follow its authors’ setup. All schemes see the same prompts. For the key derivation, the encoder and decoder share a fixed integer secret key. At each token position t, the side information is the SHA-256 hash of the secret key concatenated with the ids of the h preceding generated tokens.

4.2

Empirical Maximum Token Distinguishing Advantage

We measure the maximum advantage an adversary would have distinguishing between a watermarked and an unwatermarked distribution. As defined in Section 2, total variation distance exactly measures this metric. To empirically estimate TV distance, we prompt the model with 10 prompts and record the model’s unwatermarked and watermarked output 10,000 times per prompt, collect the next token output and estimate a distribution. We then calculate the TV distance between the estimated distributions. The results are shown in Figure 2. The outputs have slight noise, as even an unwatermarked output picks up a slight TV distance when estimated based on token outputs. Interpreting these results, the lower the TV distance, the lower the chance the best possible distinguisher is able to tell whether an output was watermarked or unwatermarked. From our estimated distributions based on the model’s outputs, before accounting for noise, for SimpleMark the distinguisher only gains an advantage of at most ε, adhering to the budget, while for ArcMark, the distinguisher gains a 46–57% advantage and a 51–65% advantage for Bimark. The untruncated law incurs additional TV distance from removing the tail mass outside the top-k. We can take away 8

Scheme (trials)

GSM8K (300)

GPQA-D LCB (198) (100)

AIME 2024 (30)

3-bit payload SimpleMark TV (ε=0.05, αmax =1500) SimpleMark KL (ε=0.05, αmax =1500) BiMark ArcMark Unwatermarked

278 274 270 272 272

112 108 107 111 110

33 40 33 35 36

8 9 11 10 8

8-bit payload SimpleMark TV (ε=0.05, αmax =1500) SimpleMark KL (ε=0.05, αmax =1500) BiMark ArcMark Unwatermarked

275 273 279 274 272

103 102 94 109 110

38 41 33 40 36

9 8 8 7 8

Table 2: Reasoning performance on tasks for Qwen3.5-9B (thinking mode, temperature 0.6) on GSM8K (300 problems), GPQA-Diamond (198 problems), LiveCodeBench (100 problems, graded on public test cases only, so counts are only comparable across schemes) and AIME 2024 (30 problems). We use identical tasks and datasets for every benchmark. We evaluate SimpleMark at two operating points (q=53, TV or KL ε = 0.05, cap αmax =1500), BiMark, ArcMark, and no watermark. that in an adversarial setting, such as those used to analyze cryptographic protocols, other current watermarking distortion freeness metrics may not be feasible for watermarking schemes to remain secure.

4.3

SimpleMark Reasoning Performance

We evaluate SimpleMark under several reasoning tasks, GSM8K [CKB+ 21], GPQA-Diamond [RHS+ 23], LiveCodeBench [JGL+ 25], and AIME 2024 [ZMA24]. We use 300, 198, 100, and 30 problems respectively, with a generation budget of 4,096 tokens for GSM8K, 8,192 for GPQADiamond and LiveCodeBench and 16,384 for AIME, and every scheme is run on the identical set of problems with one sample per problem. SimpleMark embeds a 3- or 8-bit message at ε=0.05 (TV) and ε=0.05 (KL), both with αmax =1500. On these reasoning traces the cap binds on roughly 91% of tokens. Table 2 shows that by embedding SimpleMark, the language model’s reasoning performance does not degrade. By capping α, we are more likely to avoid sampling undesired tokens that would degrade a model’s performance. In Figure 4 we show that we can reliably recover the embedded watermark at a competitive rate under the chosen parameters. The results for Llama3.1-8B-Instruct can be found in Table 3.

4.4

Perplexity

Perplexity is often used as a text quality metric for a watermark. In simple terms, it is how surprised a model is by its output through an exponentiation of the distribution’s joint entropy. Perplexity 9

Figure 3: Perplexity results for token outputs ranging from 50-300 tokens for SimpleMark, ArcMark, and Bimark. A low KL ε-budget SimpleMark is consistently closest to that of the unwatermarked output. can also be expressed as an exponentiation of the watermarked generating distribution’s entropy, plus the KL divergence between the unwatermarked and watermarked distributions. As expected Figure 3 validates that SimpleMark achieves the perplexity closest to that of the unwatermarked distribution under low KL ε-budgets.

4.5

Watermark Extraction Accuracy

We measure message accuracy when recovering our watermark. Bit errors when recovering watermarks can cause the messages to be completely different, so we focus on message accuracy. For medium ε-budgets of {0.05, 0.1, 0.15} we generate 300 tokens and use a prefix in increments of 50 tokens up to 300 tokens and attempt to extract the watermark. For lower ε-budgets of {0.01, 0.05}, we sample from 500–1000 tokens. From Figure 4, at higher ε-budgets SimpleMark’s decoding capabilities are competitive with the current state of the art watermarks, which are designed to optimize decoding capabilities and thus have high distortion in token distributions when compared to the unwatermarked law. Overall, our experiments validate that SimpleMark achieves minimal distortion from the unwatermarked distribution as seen through the distinguishing advantage and perplexity experiments, while retaining a model’s reasoning capabilities and competitive extraction accuracy.

5

Conclusion

In this work, we studied multi-bit text watermarking as a constrained communication problem, highlighting a fundamental tradeoff between payload, reliability, and statistical detectability. Unlike average-key distortion guarantees, our per-key f -divergence formulation directly controls how much each realized watermark distribution can deviate from the base model, in the worst case. We show that exact per-key distortion-freeness forces zero embedding capacity, while nonzero divergence budgets lead to a tunable rate–detectability tradeoff governed by the induced watermark channel. Motivated by this framework, we introduced SimpleMark, which combines error-correcting codes with a simple divergence-constrained probability tilt to obtain a closed-form embedding rule. Empirically, SimpleMark substantially reduces distributional deviation from the base model while maintaining competitive message recovery, perplexity, and reasoning performance. Our results 10

Figure 4: Message recovery for a variable length prefix of a 300 token sequence. For ε ∈ {0.05, 0.1, 0.15}. The SimpleMark decoding capabilities outperform the current SOTA at ε = 0.15, and remain competitive with lower, more practical ε budgets. provide an information-theoretic foundation for designing multi-bit watermarks with explicit, tunable statistical-security guarantees.

6

Acknowledgements

This work was supported by a grant from Amazon via the Amazon-Illinois Center on AI for Interactive Conversational Experiences (AICE) at the University of Illinois at Urbana-Champaign (UIUC). Benjamin D. Kim is supported by an MIT Jacobs Presidential Fellowship and the National Science Foundation, under NSF GRFP award number 2141064. Any opinions, fundings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or Amazon.

11

References [AKV03] André Adelsbach, Stefan Katzenbeisser, and Helmut Veith. Watermarking schemes provably secure against copy and ambiguity attacks. In Proceedings of the 3rd ACM Workshop on Digital Rights Management, DRM ’03, page 111–119, New York, NY, USA, 2003. Association for Computing Machinery. [Cac04] Christian Cachin. An information-theoretic model for steganography. Information and Computation, 192(1):41–56, 2004. [CCWH26] Xuehao Cui, Ruibo Chen, Yihan Wu, and Heng Huang. Mc2 mark: Distortion-free multi-bit watermarking for long messages, 2026. [CGZ23] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. IACR Cryptol. ePrint Arch., page 763, 2023. [CHS25a] Hongyan Chang, Hamed Hassani, and Reza Shokri. Watermark smoothing attacks against language models. In Christos Christodoulopoulos, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng, editors, Findings of the Association for Computational Linguistics: EMNLP 2025, pages 4915–4941, Suzhou, China, November 2025. Association for Computational Linguistics. [CHS25b] Aloni Cohen, Alexander Hoover, and Gabe Schoenbach. Watermarking language models for many adaptive users. In 2025 IEEE Symposium on Security and Privacy (SP), pages 2583–2601. IEEE, 2025. [CKB+ 21] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. [CMB+ 07] Ingemar Cox, Matthew Miller, Jeffrey Bloom, Jessica Fridrich, and Ton Kalker. Digital Watermarking and Steganography. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2 edition, 2007. [CT06] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, July 2006. [CW01] Brian Chen and Gregory W Wornell. Quantization index modulation: A class of provably good methods for digital watermarking and information embedding. IEEE Transactions on Information theory, 47(4):1423–1443, 2001. [FZZ+ 25] Xiaoyan Feng, He Zhang, Yanjun Zhang, Leo Yu Zhang, and Shirui Pan. Bimark: Unbiased multilayer watermarking for large language models. In Forty-second International Conference on Machine Learning, 2025. [GDJ+ 24] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024. [Gut13] A. Gut. Probability: A Graduate Course. Springer Texts in Statistics. Springer New York, 2013. 12

[GVG+ 26] Sidong Guo, Sajani Vithana, Atefeh Gilani, Lalitha Sankar, Oliver Kosut, and Flavio P. Calmon. Feedback coding enables inference-time covert agentic communication, 2026. [GVL+ 26] Atefeh Gilani, Sajani Vithana, Carol Xuan Long, Oliver Kosut, Lalitha Sankar, and Flavio P Calmon. Arcmark: Distortion-free multi-byte llm watermark via optimal transport. arXiv preprint arXiv:2602.07235, 2026. [HLW+ 25] Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, and Yuheng Bu. Theoretically grounded framework for LLM watermarking: A distribution-adaptive approach. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [JBKZ26] Ya Jiang, Massieh Kordi Boroujeny, Surender Suresh Kumar, and Kai Zeng. Mirrormark: Generalizable mirrored sampling for multi-bit llm watermarking. arXiv preprint arXiv:2601.22246, 2026. [JGL+ 25] Naman Jain, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and Ion Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. In International Conference on Learning Representations, volume 2025, pages 58791–58831, 2025. [JWB+ 25] Ya Jiang, Chuxiong Wu, Massieh Kordi Boroujeny, Brian Mark, and Kai Zeng. StealthInk: A multi-bit and stealthy watermark for large language models. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 27685–27709. PMLR, 13–19 Jul 2025. [Kee10] R.W. Keener. Theoretical Statistics: Topics for a Core Course. Springer Texts in Statistics. Springer New York, 2010. [KGW+ 23] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, Proceedings of Machine Learning Research, pages 17061–17084. PMLR, 2023. [KL14] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, Second Edition. Chapman & Hall/CRC, 2nd edition, 2014. [KTHL24] Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. Transactions on Machine Learning Research, 2024. [LMC+ 24] Shayne Longpre, Robert Mahari, Anthony Chen, Naana Obeng-Marnu, Damien Sileo, William Brannon, Niklas Muennighoff, Nathan Khazam, Jad Kabbara, Kartik Perisetla, Xinyi (Alexis) Wu, Enrico Shippole, Kurt Bollacker, Tongshuang Wu, Luis Villa, Sandy Pentland, and Sara Hooker. A large-scale audit of dataset licensing and attribution in AI. Nature Machine Intelligence, 6(8):975–987, 2024. [MK05] Pierre Moulin and Ralf Koetter. Data-hiding codes. Proceedings of the IEEE, 93(12):2083– 2126, December 2005. [MO03] Pierre Moulin and Joseph A. O’Sullivan. Information-theoretic analysis of information hiding. IEEE Trans. Inf. Theory, 49(3):563–593, 2003.

13

[Mou03] Pierre Moulin. Information-hiding games. In Digital Watermarking, pages 1–12, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. [Mou05] Pierre Moulin. The method of types and its application to information hiding. In 2005 13th European Signal Processing Conference, pages 1–1, 2005. [MS78] F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correcting Codes. Northholland Publishing Company, 2nd edition, 1978. [MU05] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, USA, 2nd edition, 2005. [Mun84] James R. Munkres. Elements of Algebraic Topology. Addison Wesley Publishing Company, 1984. [PW25] Y. Polyanskiy and Y. Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2025. [Qwe26] Qwen Team. Qwen3.5: Towards native multimodal agents, February 2026. [QZT+ 25] Wenjie Qu, Wengrui Zheng, Tianyang Tao, Dong Yin, Yanze Jiang, Zhihua Tian, Wei Zou, Jinyuan Jia, and Jiaheng Zhang. Provably robust multi-bit watermarking for {AI-generated} text. In 34th USENIX Security Symposium (USENIX Security 25), pages 201–220, 2025. [RHS+ 23] David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. Gpqa: A graduate-level google-proof q&a benchmark. arXiv preprint arXiv:2311.12022, 2023. [Ros98] Sheldon M. Ross. A First Course in Probability. Fifth edition, 1998. [RSR+ 20] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1– 67, 2020. [Rud64] W. Rudin. Principles of Mathematical Analysis. International series in pure and applied mathematics. McGraw-Hill, 1964. [XHKZ26] Jiahao Xu, Rui Hu, Olivera Kotevska, and Zikai Zhang. Xmark: Reliable multi-bit watermarking for llm-generated texts. arXiv preprint arXiv:2604.05242, 2026. [XJY+ 25] Xiaojun Xu, Jinghan Jia, Yuanshun Yao, Yang Liu, and Hang Li. Robust multi-bit text watermark with LLM-based paraphrasers. In Forty-second International Conference on Machine Learning, 2025. [YAK24] KiYoon Yoo, Wonhyuk Ahn, and Nojun Kwak. Advancing beyond identification: Multibit watermark for large language models. In Kevin Duh, Helena Gomez, and Steven Bethard, editors, Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 4031–4055, Mexico City, Mexico, June 2024. Association for Computational Linguistics. 14

[ZEF+ 24] Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. Watermarks in the sand: Impossibility of strong watermarking for generative models. In Forty-first International Conference on Machine Learning, 2024. [ZHW26] Junlin Zhu, Baizhou Huang, and Xiaojun Wan. Quantilemark: A message-symmetric multi-bit watermark for llms. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 6790–6806, 2026. [ZMA24] Yifan Zhang and Team Math-AI. American invitational mathematics examination (aime) 2024, 2024.

15

AI use statement In this work, we used generative AI tools for generating the code to run the experiments. We also used generative AI to generate Figure 1 that explains our scheme on a high level. We have reviewed all AI-assisted work. We take full responsibility for the final content of this work.

A

Encoder and Decoder Algorithms

SimpleMark’s encoding and decoding procedures are described in Section 3.1. In this section, we share the algorithmic forms of Algorithm 1 (encoder) and Algorithm 2 (decoder). Algorithm 1 describes the encoder: the message is LDPC-encoded once, and each generation step derives the key from the preceding tokens. Subsequently the corresponding target vertex and tilt towards that token are calculated. A token is then sampled from the tilted watermarked distribution. Algorithm 2 gives the decoder: the decoder starts by recovering the base laws and key sequence from the received text. Next it scores each code symbol under the same f -divergence constrained channel used for embedding, and returns the maximum-likelihood codeword.

B

Theoretical Results on Capacity of Watermarking Channel

Throughout the appendix, we consider TV distance as the f -divergence to solve for all our theoretical results. As previously stated, some of the theoretical results are limited to simpler settings and most results hold for all f -divergences. We leave additional results to future work. Also, for simplicity, we assume independent side information and a (conditional) memoryless channel.

B.1

Token-Level

Notation and standing assumptions. Let X = [1 : N ] denote the token vocabulary. At time t, the base language model induces a next-token distribution Qt ∈ ∆(X ), where ∆(X ) is the probability simplex on X . As in ArcMark and SimpleMark, the message M ∈ M := {1, . . . , 2k } is encoded into a codeword with an error correcting code CM (1), . . . , CM (n) ∈ Fq := {0, 1, . . . , q − 1}, and the encoder and decoder share side information Vt ∼ Unif(Fq ),

t = 1, . . . , n.

The state variable is the target vertex Zt := (CM (t) + Vt ) mod q ∈ Z := Fq , identified with the vertices of the (q − 1)-simplex via the keyed bijection σt of Section 3.1. We assume throughout that: 16

Algorithm 1 Per-key divergence-constrained encoder Require: Message m ∈ M, blocklength n, LDPC codebook {Cm (1 : n)}m∈M over Fq , secret key K, hash window h, divergence D ∈ {dTV , DKL }, budget ε, base laws (Qt )nt=1 Ensure: Watermarked token sequence X1:n 1: Encode m as the codeword Cm (1), . . . , Cm (n). 2: for t = 1 to n do 3: Derive the side information from the key and the preceding tokens, (Vt , σt ) ← Hash(K, Xt−h:t−1 ),

4:

5:

where Vt ∈ Fq and σt : St → Fq is a keyed bijection on the truncated support. Form the target vertex Zt ← (Cm (t) + Vt ) mod q. Compute the base mass on the target vertex, X Bt ←

Qt (x),

x : σt (x)=Zt

and obtain s⋆t from (Bt , ε, D): s⋆t = Bt + min(ε, 1 − Bt ) if D = dTV ; the unique root in [Bt , 1] of 1−s s log Bst + (1 − s) log 1−B = ε if D = DKL . If applicable, cap s∗t = min{s∗ , αmax B} t 6: Form the closed-form tilt  ⋆ s  σt (x) = Zt ,  t Qt (x), Q⋆t (x) ← Bt ⋆   1 − st Qt (x), σt (x) ̸= Zt . 1 − Bt 7:

Sample

Xt ∼ Q⋆t .

8: end for 9: Output X1:n ; the side information (Vt , σt )n t=1 is recomputable from K and the text itself.

1. The message M is uniform on M. 2. The side information sequence V1 , . . . , Vn is i.i.d. and independent of M . 3. Given (M, V1 , . . . , Vn ), the encoder generates tokens through a conditional-memoryless channel: PX1:n |M,V1:n (x1:n | m, v1:n ) =

n Y

PXt |Zt =zt (m,vt ) (xt ).

t=1

c. 4. The decoder observes (X1:n , V1:n ) and outputs M Definition 1 (Uniform per-key ε-TV distortion). Fix ε ≥ 0. A watermarking scheme is said to be uniformly per-key ε-TV distortion-free if for every time t, every message m ∈ M, and every realized key value v ∈ Fq ,
dTV PXt |M =m,Vt =v , Qt ≤ ε.

17

Algorithm 2 Per-key divergence-constrained MLE Decoder Require: Observed tokens x1:n , secret key K, hash window h, codebook {Cm (1 : n)}m∈M , divergence D, budget ε, base model Q(· | ·) Ensure: Message estimate m b 1: for t = 1 to n do Recover the base law Qt (·) = Q(· | x<t ), truncated and renormalized as in encoding, and 2: recompute (Vt , σt ) ← Hash(K, xt−h:t−1 ). 3: For each symbol a ∈ Fq , form the candidate vertex and its base mass, X zt (a) = (a + vt ) mod q, Ba ← Qt (x), x : σt (x)=zt (a)

obtain s⋆a from (Ba , ε, D) as in Algorithm 1, and store the per-symbol log-likelihood 
⋆ log sa Qt (xt ) , σt (xt ) = zt (a), Ba Lt (a) ←
⋆ log 1−sa Q (x ) , σ (x ) ̸= z (a). t t t t t 1−Ba 4: end for 5: for each candidate message m ∈ M do 6:

Compute the log-likelihood score

Λ(m) :=

n X

Lt Cm (t) .

t=1

7: end for 8: Output any maximizer

m b ∈ arg max Λ(m). m∈M

Equivalently, since Zt is a deterministic function of (m, v), the scheme is uniformly per-key ε-TV distortion-free iff
dTV PXt |Zt =z , Qt ≤ ε ∀z ∈ Z, ∀t. Definition 2 (Feasible per-key channel family). For each time t and distortion budget ε ≥ 0, define n o
Ft (ε) := PXt |Zt =z z∈Z : dTV (PXt |Zt =z , Qt ) ≤ ε ∀z ∈ Z . Definition 3 (Per-key constrained embedding channel). For each time t, choose a channel family
(ε) PXt |Zt =z z∈Z ∈ Ft (ε). Given message m and side information vt , form zt = zt (m, vt ) = (Cm (t) + vt ) mod q, and sample (ε)

Xt ∼ PXt |Zt =zt .

18

Proposition 2 (Uniform per-key distortion-freeness). If the encoder uses channel families
(ε) PXt |Zt =z z∈Z ∈ Ft (ε)

for all t,

then the resulting scheme is uniformly per-key ε-TV distortion-free:
dTV PXt |M =m,Vt =v , Qt ≤ ε ∀t, ∀m, ∀v. Proof. Fix t ∈ [1 : n], m ∈ M, and v ∈ Fq . By construction, Zt = zt (m, v) = (Cm (t) + v) mod q ∈ Z. Conditioned on (M, Vt ) = (m, v), the encoder samples Xt according to the conditional law attached to this state: (ε) PXt |M =m,Vt =v = PXt |Zt =zt (m,v) . Since

(ε) PXt |Zt =z z∈Z ∈ Ft (ε),

the definition of Ft (ε) yields   (ε) dTV PXt |Zt =z , Qt ≤ ε

∀z ∈ Z.

Applying this to z = zt (m, v) gives     (ε) dTV PXt |M =m,Vt =v , Qt = dTV PXt |Zt =zt (m,v) , Qt ≤ ε. Because t, m, v were arbitrary, the claim follows uniformly over all times, messages, and realized keys. Definition 4 (Single-letter per-time constrained capacity). For each time t, define Ct (ε) :=

sup

PXt |Zt =z

z∈Z

I(Zt ; Xt ), ∈Ft (ε)

where the mutual information is computed under the joint law PZt ,Xt (z, x) = PZt (z)PXt |Zt =z (x). Definition 5 (Universal single-letter constrained capacity). For each time t, define et (ε) := C

sup

I(Zt ; Xt ),

(PXt |Zt =z )z∈Z ∈Ft (ε) PZt ∈∆(Z)

where the mutual information is computed under the joint law PZt ,Xt (z, x) = PZt (z) PXt |Zt =z (x).

19

Theorem 2 (Converse under uniform per-key TV constraint). Assume the conditional-memoryless model. Let a sequence of length-n watermarking schemes satisfy the uniform per-key ε-TV constraint, and let the decoder error probability c ̸= M ] Pe(n) := Pr[M tend to zero as n → ∞. If k n denotes the embedded rate in bits per token, then for every n, Rn :=

n

(n)

1 + nRn Pe 1Xe Ct (ε) + Rn ≤ n n

.

t=1

(n)

Consequently, if (Rn )n is bounded and Pe

→ 0, then n

lim sup Rn ≤ lim sup n→∞

n→∞

1Xe Ct (ε). n t=1

Proof. Since M is uniform on M with |M| = 2k , H(M ) = k = nRn . By Fano’s inequality [CT06], H(M | X1:n , V1:n ) ≤ h2 (Pe(n) ) + Pe(n) log(|M| − 1) ≤ 1 + nRn Pe(n) . Therefore, nRn = H(M ) = I(M ; X1:n , V1:n ) + H(M | X1:n , V1:n ), so

nRn ≤ I(M ; X1:n , V1:n ) + 1 + nRn Pe(n) .

Because M and V1:n are independent, I(M ; X1:n , V1:n ) = I(M ; X1:n | V1:n ). Hence

nRn ≤ I(M ; X1:n | V1:n ) + 1 + nRn Pe(n) .

Applying the chain rule gives I(M ; X1:n | V1:n ) =

n X

I(M ; Xt | X1:t−1 , V1:n ).

t=1

Fix t. Let Ut := (X1:t−1 , V1:n ). Since Zt is a deterministic function of (M, Vt ), and by the conditional-memoryless assumption PXt |M,V1:n ,X1:t−1 = PXt |Zt , 20

we have the conditional Markov chain M −→ Zt −→ Xt

given Ut .

Therefore, by data processing [CT06], I(M ; Xt | Ut ) ≤ I(Zt ; Xt | Ut ). Thus I(M ; X1:n | V1:n ) ≤

n X

I(Zt ; Xt | Ut ).

t=1

Now expand the conditional mutual information: X I(Zt ; Xt | Ut ) = PUt (u) I(Zt ; Xt | Ut = u). u

Fix any u with PUt (u) > 0. Conditioned on Ut = u, the channel from Zt to Xt is still the same single-letter channel family (PXt |Zt =z )z∈Z , while the input law of Zt becomes the posterior distribution PZt |Ut =u . Because the scheme satisfies the uniform per-key ε-TV constraint, this channel family belongs to Ft (ε). Hence, by Definition 5, et (ε). I(Zt ; Xt | Ut = u) ≤ C Since this holds for every u, et (ε). I(Zt ; Xt | Ut ) ≤ C Therefore, I(M ; X1:n | V1:n ) ≤

n X

et (ε). C

t=1

Substituting back into the Fano bound yields nRn ≤

n X

et (ε) + 1 + nRn Pe(n) . C

t=1

Dividing by n gives

n

Rn ≤

(n)

1Xe 1 + nRn Pe Ct (ε) + n n

.

t=1

This proves the finite-n bound. (n) If (Rn )n is bounded and Pe → 0, then the additive term on the right tends to 0, so n

1Xe Ct (ε). lim sup Rn ≤ lim sup n→∞ n→∞ n t=1

21

The following achievability result should be interpreted as an achievability theorem for the induced single-letter channel PX|Z , assuming that the encoder can realize codewords z n (m) ∈ Z n with empirical distribution approaching PZ . A separate codebook realizability argument is needed to specialize this statement to the constrained SimpleMark or ArcMark state process Zt (m, Vt ). Theorem 3 (Achievability in the idealized induced DMC model). Assume now that: 1. Qt ≡ Q does not depend on t; 2. the feasible set is the same at every time, i.e. Ft (ε) ≡ F(ε); 3. the encoder uses a fixed channel family
PX|Z=z z∈Z ∈ F(ε) at every time; 4. the induced state process Z1 , . . . , Zn is i.i.d. with marginal PZ . Then any rate R < I(Z; X) is achievable with vanishing block error probability. Consequently, any rate R < C(ε) :=

sup

PX|Z=z

I(Z; X)

z∈Z

∈F (ε)

is achievable. Proof. Under the stated assumptions, the induced channel from Z n = (Z1 , . . . , Zn ) to X n = (X1 , . . . , Xn ) is a discrete memoryless channel with transition law PX n |Z n (xn | z n ) =

n Y

PX|Z (xt | zt ).

t=1

Fix any channel family in F(ε) and let the input distribution of Z be the induced marginal PZ . Let R < I(Z; X). Next, construct a random codebook [MS78] by drawing z n (1), . . . , z n (2nR ) independently, each with i.i.d. components distributed according to PZ . To transmit message m, send the corresponding codeword z n (m) through the channel, producing xn according to n Y

PX|Z (xt | zt (m)).

t=1

At the decoder, use jointly typical decoding: declare m b to be the unique index such that (z n (m), b xn ) is jointly typical. 22

By the standard random-coding theorem for discrete memoryless channels [MS78], the average probability of error over the random code ensemble tends to zero as n → ∞ whenever R < I(Z; X). Hence there exists at least one deterministic codebook with block error probability tending to zero at every rate below I(Z; X). Since the chosen channel family belongs to F(ε), the resulting scheme satisfies the per-key TV constraint. Finally, because the argument holds for every feasible channel family, taking the supremum over all
PX|Z=z z∈Z ∈ F(ε) shows that every rate R < C(ε) is achievable. Remark 1 (How to instantiate the constrained channel). A practical instantiation is to solve, at each time t, max

PXt |Zt =z

B.2

I(Zt ; Xt )

subject to

dTV (PXt |Zt =z , Qt ) ≤ ε ∀z ∈ Z.

z∈Z

Examples for Token-Level

Concrete instantiations of Theorem 2. Theorem 2 states that under the uniform per-key ε-TV constraint, any sequence of watermarking schemes with vanishing decoding error must satisfy n

Rn ≤

(n)

1 + nRn Pe 1Xe Ct (ε) + n n

,

t=1

where et (ε) := C

sup

I(Zt ; Xt ).

(PXt |Zt =z )z∈Z ∈Ft (ε) PZt ∈∆(Z)

Thus, to instantiate the theorem concretely, one fixes a base distribution Qt , chooses state-conditioned channels
PXt |Zt =z z∈Z satisfying dTV (PXt |Zt =z , Qt ) ≤ ε

∀z ∈ Z,

and then computes the resulting mutual information I(Zt ; Xt ). This gives an explicit feasible single-letter quantity that can be compared against the converse bound in Theorem 2. Example 1: binary symmetric perturbation. Let X = {0, 1},

1 Q(0) = Q(1) = , 2

Z = {0, 1},

1 PZ (0) = PZ (1) = . 2

and let the state alphabet be

23

Fix ε ∈ [0, 12 ] and define the conditional laws PX|Z=0 (0) =

1 + ε, 2

PX|Z=0 (1) =

1 − ε, 2

PX|Z=1 (0) =

1 − ε, 2

PX|Z=1 (1) =

1 + ε. 2

and We verify feasibility: dTV (PX|Z=0 , Q) =

 1 1 1 1 1 1 + ε − + − ε − = (ε + ε) = ε, 2 2 2 2 2 2

and similarly dTV (PX|Z=1 , Q) = ε. Hence this channel family is feasible under the uniform per-key ε-TV constraint. Now compute the induced marginal on X: PX (0) =

 11  1 11 +ε + −ε = , 2 2 2 2 2

and similarly

1 PX (1) = . 2

Thus X ∼ Bernoulli( 12 ) and H(X) = 1. Moreover, H(X|Z = 0) = h2

1 2

 +ε ,

H(X|Z = 1) = h2

so H(X|Z) = h2

1 2

1 2

 +ε ,

 +ε .

Therefore I(Z; X) = H(X) − H(X|Z) = 1 − h2

1 2

 +ε .

Consequently,

 1 e C(ε) ≥ 1 − h2 +ε . 2 This gives a completely explicit feasible instantiation of the single-letter quantity appearing in Theorem 2. Numerical specialization of Example 1. If ε = 0.1, then I(Z; X) = 1 − h2 (0.6) ≈ 0.0290 bits/token. If ε = 0.2, then

I(Z; X) = 1 − h2 (0.7) ≈ 0.1187 bits/token.

Thus, even in this simplest binary example, the theorem predicts that as the allowed per-key distortion budget increases, the admissible embedding rate also increases.

24

Small-ε expansion for Example 1. Using the Taylor expansion of binary entropy around 12 , h2

1

 2 2 +ε =1− ε + o(ε2 ), 2 ln 2

we obtain

 2 2 +ε = ε + o(ε2 ). 2 ln 2 Hence in this binary symmetric perturbation example, the mutual information scales quadratically in ε for small ε. I(Z; X) = 1 − h2

1

Example 2: exact distortion-freeness forces zero information. Now set ε = 0. The per-key TV constraint becomes dTV (PX|Z=z , Q) = 0 ∀z ∈ Z. Since total variation distance vanishes if and only if the distributions are identical, we obtain PX|Z=z = Q

∀z ∈ Z.

Therefore the conditional law of X does not depend on Z, so X and Z are independent: PX,Z (x, z) = PZ (z)Q(x) = PZ (z)PX (x). Hence I(Z; X) = 0. Thus et (0) = 0 C

∀t,

and Theorem 2 implies that any asymptotically reliable watermarking scheme under exact per-key distortion-freeness must satisfy lim sup Rn ≤ 0. n→∞

This concretely illustrates the paper’s statement that exact per-key distortion-freeness forces zero embedding capacity. Example 3: ternary perturbation. Let X = {1, 2, 3},

1 Q(1) = Q(2) = Q(3) = , 3

and again let

1 PZ (0) = PZ (1) = . 2

Z = {0, 1}, Fix ε ∈ [0, 13 ] and define



 1 1 1 PX|Z=0 = + ε, , − ε , 3 3 3   1 1 1 PX|Z=1 = − ε, , + ε . 3 3 3

We again verify the TV constraint:   1 1 1 1 1 1 1 1 dTV (PX|Z=0 , Q) = +ε− + − + −ε− = (ε + 0 + ε) = ε, 2 3 3 3 3 3 3 2 25

and similarly dTV (PX|Z=1 , Q) = ε. Thus the channel family is feasible. Now compute the output marginal: 1 1 PX = PX|Z=0 + PX|Z=1 = 2 2



1 1 1 , , 3 3 3

 = Q.

Hence H(X) = log2 3. Also,

 H(X|Z = 0) = H(X|Z = 1) = H

so

 H(X|Z) = H

 1 1 1 + ε, , − ε , 3 3 3

 1 1 1 + ε, , − ε . 3 3 3

Therefore

 I(Z; X) = log2 3 − H

 1 1 1 + ε, , − ε . 3 3 3

This yields another explicit feasible instantiation of the constrained mutual information appearing in Theorem 2. Example 4: direct SimpleMark instantiation at one time step. Fix a time t, and suppose the base next-token distribution is Qt = (0.5, 0.3, 0.2) over a three-token vocabulary X = {x1 , x2 , x3 }. Suppose also that the relevant state alphabet at time t is binary: 1 Zt = {z0 , z1 }, PZt (z0 ) = PZt (z1 ) = . 2 For some δ ∈ [0, min{ε, 0.2}], define PXt |Zt =z0 = (0.5 + δ, 0.3, 0.2 − δ), and PXt |Zt =z1 = (0.5 − δ, 0.3, 0.2 + δ). Then dTV (PXt |Zt =z0 , Qt ) =

1 (|δ| + 0 + | − δ|) = δ ≤ ε, 2

and similarly dTV (PXt |Zt =z1 , Qt ) ≤ ε. Hence this is a feasible per-key channel family. The output marginal is 1 1 PXt = PXt |Zt =z0 + PXt |Zt =z1 = (0.5, 0.3, 0.2) = Qt . 2 2 26

Therefore H(Xt ) = H(0.5, 0.3, 0.2). However, the two conditional entropies are not generally equal. Indeed, 1 1 H(Xt |Zt ) = H(0.5 + δ, 0.3, 0.2 − δ) + H(0.5 − δ, 0.3, 0.2 + δ). 2 2 Consequently, the correct mutual information is 1 1 I(Zt ; Xt ) = H(0.5, 0.3, 0.2) − H(0.5 + δ, 0.3, 0.2 − δ) − H(0.5 − δ, 0.3, 0.2 + δ). 2 2 Thus, for this concrete choice of feasible perturbation, Theorem 2 yields the explicit converse n

Rn ≤

(n)

1 + nRn Pe 1Xe Ct (ε) + n n

,

t=1

with

et (ε) ≥ H(0.5, 0.3, 0.2) − 1 H(0.5 + δ, 0.3, 0.2 − δ) − 1 H(0.5 − δ, 0.3, 0.2 + δ). C 2 2

Example 5: using the actual SimpleMark state variable. Recall that the state at time t is Zt = (CM (t) + Vt ) mod q, where CM (t) ∈ Fq is the code symbol at time t and Vt ∼ Unif(Fq ) is the secret key value. To obtain a concrete toy instantiation, take q = 2, so Zt = (CM (t) + Vt ) mod 2 takes values in Z = {0, 1}, the two vertices of the 1-simplex; write z0 := 0 and z1 := 1. If the base distribution is Qt = (0.5, 0.3, 0.2), we may choose the feasible channel family PXt |Zt =z0 = (0.5 + δ, 0.3, 0.2 − δ),

PXt |Zt =z1 = (0.5 − δ, 0.3, 0.2 + δ),

where δ ≤ ε. Then dTV (PXt |Zt =zi , Qt ) ≤ ε for i ∈ {0, 1}, so this is a valid per-key instantiation in the SimpleMark notation. If PZt (z0 ) = PZt (z1 ) = 1/2, then the output marginal is again 1 1 PXt = PXt |Zt =z0 + PXt |Zt =z1 = Qt . 2 2 Therefore H(Xt ) = H(0.5, 0.3, 0.2), while

1 1 H(Xt |Zt ) = H(0.5 + δ, 0.3, 0.2 − δ) + H(0.5 − δ, 0.3, 0.2 + δ). 2 2 Hence the correct per-time mutual information is 1 1 I(Zt ; Xt ) = H(0.5, 0.3, 0.2) − H(0.5 + δ, 0.3, 0.2 − δ) − H(0.5 − δ, 0.3, 0.2 + δ). 2 2

Thus Theorem 2 says that any asymptotically reliable scheme built from such per-time perturbations must satisfy n 1Xe lim sup Rn ≤ lim sup Ct (ε), n→∞ n→∞ n t=1

and the displayed quantity above gives an explicit feasible single-letter mutual information value et (ε). that lower bounds C 27

Interpretation. These examples show concretely how Theorem 2 should be used in practice. One fixes a base next-token distribution Qt , constructs feasible state-conditioned perturbations lying inside the total variation ball of radius ε around Qt , computes the induced single-letter mutual information I(Zt ; Xt ), and then interprets Theorem 2 as saying that no asymptotically reliable watermarking scheme can have rate larger than the time-average of the best such single-letter quantities. In particular, as ε → 0, every feasible state-conditioned law collapses back to Qt , and the mutual information necessarily goes to zero. (n)

Instantiating Rn and Pe

in Theorem 2. Recall that in Theorem 2, if the message set has size |M| = 2k ,

and the watermark spans n time steps, then the embedding rate is Rn =

k n

c from the observation (X1:n , V1:n ), bits per token. Moreover, for a decoder producing an estimate M the block error probability is c ̸= M ]. Pe(n) := Pr[M Thus, to instantiate the theorem concretely, one must specify a finite blocklength n, a number of embedded bits k, and a decoding rule. Example 1: binary toy model with k = 1 and n = 1. Consider the binary construction X = {0, 1},

1 PZ (0) = PZ (1) = , 2

Z = {0, 1},

with conditional laws

1 − ε, 2 1 PX|Z=1 (1) = + ε. 2

1 + ε, 2 1 PX|Z=1 (0) = − ε, 2 Suppose we embed one bit, so that

PX|Z=0 (1) =

PX|Z=0 (0) =

M ∈ {0, 1},

k = 1,

and we use a single time step: n = 1. Then R1 =

k =1 n

bit per token. Assume that the state is identified with the message, i.e. Z = M , and let the decoder be the maximum-likelihood decoder ( c(x) = 0, x = 0, M 1, x = 1. Then the block error probability is

c ̸= M ]. Pe(1) = Pr[M 28

Since the decoder makes an error exactly when the output flips relative to the more likely symbol under the true message, Pe(1) =

1 c ̸= 0 | M = 0] + 1 Pr[M c ̸= 1 | M = 1]. Pr[M 2 2

Now c ̸= 0 | M = 0] = Pr[X = 1 | Z = 0] = Pr[M

1 − ε, 2

c ̸= 1 | M = 1] = Pr[X = 0 | Z = 1] = Pr[M

1 − ε. 2

and similarly Therefore Pe(1) =

1 − ε. 2

So in this one-shot example,

1 − ε. 2 This illustrates that at blocklength 1, the decoder error remains large unless ε is quite large. R1 = 1,

Pe(1) =

Example 2: repetition over n time steps with k = 1. Now use the same binary channel at every time step, but repeat the same embedded bit across n independent uses. Thus M ∈ {0, 1},

k = 1,

Rn =

1 . n

Conditioned on M = 0, the outputs X1 , . . . , Xn are i.i.d. with Pr[Xt = 0 | M = 0] =

1 + ε, 2

Pr[Xt = 1 | M = 0] =

1 − ε. 2

Conditioned on M = 1, the outputs are i.i.d. with the roles of 0 and 1 reversed. Let the decoder use majority vote: ( Pn 1{Xt = 1} < n2 , 0, c M= Pnt=1 n 1, t=1 1{Xt = 1} > 2 . (Without loss of generality, assume that n is odd.) Then the block error probability is c ̸= M ]. Pe(n) = Pr[M By symmetry,

" n X

Pe(n) = Pr

t=1

Since under M = 0,

n X t=1

we obtain Pe(n) =

# n M =0 . 1{Xt = 1} ≥ 2

  1 1{Xt = 1} ∼ Bin n, − ε , 2   j  n−j n X n 1 1 . −ε +ε j 2 2

j=⌈n/2⌉

29

Thus in this repetition construction, Rn = while

1 , n

j  n−j   n X n 1 1 −ε +ε . 2 2 j

Pe(n) =

j=⌈n/2⌉

As n → ∞, this error probability tends to zero for every fixed ε > 0, whereas the rate Rn = 1/n also tends to zero. This is consistent with Theorem 2. Example 3: four messages over two time steps. Suppose now that we wish to embed k=2 bits using n=2 time steps. Then the message set has size |M| = 22 = 4, for example M = {00, 01, 10, 11}. The embedding rate is therefore R2 =

k 2 = =1 n 2

bit per token. To make this concrete, suppose at each time t the encoder uses the binary perturbation channel from Example 1, and the two message bits are sent independently across the two time steps: Xt ∼ PX|Z=Mt .

M = (M1 , M2 ),

Let the decoder decode each coordinate separately via ( ct = 0, Xt = 0, M 1, Xt = 1. Then the overall decoded message is c = (M c1 , M c2 ). M Since an error occurs if at least one of the two coordinates is decoded incorrectly, and each coordinate has error probability 1 − ε, 2 the block error probability is  2 1 (2) c c Pe = 1 − Pr[M1 = M1 and M2 = M2 ] = 1 − +ε . 2 Equivalently, Pe(2) = 1 −

  2 1 1− −ε . 2

So in this example, R2 = 1,

Pe(2) = 1 − 30



1 +ε 2

2 .

Example 4: general finite-blocklength instantiation. More generally, if one chooses: • a blocklength n, • a message set M with |M| = 2k , • a feasible family of per-time channels
PXt |Zt =z z∈Z , • and a decoder c=M c(X1:n , V1:n ), M then the two quantities in Theorem 2 are instantiated as Rn = and

k n

c(X1:n , V1:n ) ̸= M ]. Pe(n) = Pr[M

For instance, if k = 100 bits are embedded over n = 1000 tokens, then Rn =

100 = 0.1 1000

bits per token. If the chosen encoder–decoder pair achieves a block error probability of, say, Pe(n) = 10−3 , then the finite-n converse in Theorem 2 becomes 1000

0.1 ≤

1 + 1000 · 0.1 · 10−3 1 X e Ct (ε) + . 1000 1000 t=1

That is,

1000

1 X e 0.1 ≤ Ct (ε) + 0.0011. 1000 t=1

Equivalently,

1000

1 X e Ct (ε) ≥ 0.0989. 1000 t=1

So this gives a concrete numerical reading of Theorem 2: to support an embedding rate of 0.1 bits per token at block error probability 10−3 , the average constrained single-letter mutual information must be at least approximately 0.0989. Interpretation. In short, Rn is instantiated simply by choosing how many bits k are embedded (n) across how many time steps n, while Pe is instantiated by fixing a decoder and computing its block error probability under the induced joint law of (M, X1:n , V1:n ). Theorem 2 then relates these et (ε). concrete finite-blocklength quantities to the average single-letter constrained capacities C

31

B.3

Sequence-Level

Lemma 1 (Sequence-level TV bound from uniform per-step TV control). Fix a message m ∈ M and a realized side-information sequence v1:n ∈ Fnq . Let (m,v

)

PX1:n 1:n := PX1:n |M =m,V1:n =v1:n denote the watermarked sequence law, and let (n) QX1:n :=

n Y

Qt

t=1

denote the reference product law formed from the base next-token distributions. Assume that, conditioned on (M, V1:n ) = (m, v1:n ), the watermarked sequence law factors as (m,v

)

PX1:n 1:n (x1:n ) =

n Y

PXt |M =m,Vt =vt (xt ),

t=1

and that for every t ∈ [1 : n],
dTV PXt |M =m,Vt =vt , Qt ≤ εt . Then

n   Y (m,v ) (n) (1 − εt ). dTV PX1:n 1:n , QX1:n ≤ 1 − t=1

In particular, if εt ≤ ε for all t, then   (m,v ) (n) dTV PX1:n 1:n , QX1:n ≤ 1 − (1 − ε)n ≤ nε. Proof. For each t, write Pt := PXt |M =m,Vt =vt , By assumption, (m,v

)

PX1:n 1:n =

n O

Qt := Qt . (n)

Pt ,

QX1:n =

t=1

n O

Qt .

t=1

For each t, by the coupling characterization of total variation distance, there exists a coupling πt ∈ Π(Pt , Qt ) of random variables (Yt , Zt ) such that Pr[Yt ̸= Zt ] = dTV (Pt , Qt ) ≤ εt . Take these couplings independently across t, producing a joint coupling of Y1:n = (Y1 , . . . , Yn ) ∼

n O

Pt

t=1

and Z1:n = (Z1 , . . . , Zn ) ∼

n O t=1

32

Qt .

Under this product coupling, Pr[Y1:n = Z1:n ] =

n Y

Pr[Yt = Zt ] =

t=1

n Y

n
Y 1 − Pr[Yt ̸= Zt ] ≥ (1 − εt ).

t=1

t=1

Therefore, Pr[Y1:n ̸= Z1:n ] = 1 − Pr[Y1:n = Z1:n ] ≤ 1 −

n Y

(1 − εt ).

t=1

Applying again the coupling characterization of total variation distance gives ! n n n O O Y dTV Pt , Qt ≤ Pr[Y1:n ̸= Z1:n ] ≤ 1 − (1 − εt ). t=1

t=1

t=1

This proves the first claim. For the second claim, if εt ≤ ε for all t, then n Y 1− (1 − εt ) ≤ 1 − (1 − ε)n . t=1

Finally, Bernoulli’s inequality implies (1 − ε)n ≥ 1 − nε and hence

for ε ∈ [0, 1],

1 − (1 − ε)n ≤ nε.

This proves the uniform bound. Corollary 1 (Uniform sequence-level TV guarantee). Assume the hypotheses of Lemma 1, and suppose moreover that the scheme is uniformly per-key ε-TV distortion-free, i.e.
dTV PXt |M =m,Vt =v , Qt ≤ ε ∀t, ∀m, ∀v. Then for every message m and every realized side-information sequence v1:n , ! n Y dTV PX1:n |M =m,V1:n =v1:n , Qt ≤ 1 − (1 − ε)n ≤ nε. t=1

Proof. Apply Lemma 1 with εt = ε for all t.

C

Distortion-Freeness: Per-Key vs. On-Average

In ArcMark [GVL+ 26], they consider distortion-freeness, averaged over the secret key. For many applications, this is not an acceptable level of security since LLM watermarking of images/text is done for a particular secret key.   Proposition 3. The perfect distortion-free condition averaged over the secret key, ES PX|S,M =m = QX ∀m, does not imply per-key perfect distortion-freeness, namely PX|S=s,M =m = QX ∀s, m. Proof. Consider the binary alphabet X = {0, 1} and let QX (0) = QX (1) = 12 . Let the secret key S be uniform on {0, 1}: Pr[S = 0] = Pr[S = 1] = 12 . For every message m, define P  X|S=0,M =m (0) = 1, PX|S=0,M =m (1) = 0, and PX|S=1,M =m (0) = 0, PX|S=1,M =m (1) = 1. Then ES PX|S,M =m (0) =   1 1 1 1 1 1 2 · 1 + 2 · 0 = 2 = QX (0), and similarly ES PX|S,M =m (1) = 2 · 0 + 2 · 1 = 2 = QX (1). Hence ES PX|S,M =m = QX ∀m. However, PX|S=0,M =m = δ0 ̸= QX , PX|S=1,M =m = δ1 ̸= QX . Thus per-key perfect distortion-freeness fails. 33

C.1

Separation in Detection

We show that schemes that provide average-key distortion-free guarantees could be strictly less covert against a detector/adversary than the class of uniformly per-key ε-TV distortion-free schemes. In particular, for every ε < 1, there exist average-key distortion-free schemes that are strictly easier to detect than any scheme obeying the uniform per-key ε-TV constraint. In the proposition below, the detector explicitly receives the secret key. In a real-world deployment, this is (likely) not the case. But we use the proposition to show the separation in detection schemes that satisfy average-key distortion freeness versus per-key distortion freeness. Proposition 4 (Average-key distortion-freeness can be highly detectable). Let X = V = {1, . . . , N }, and let Q(x) = N1 , x ∈ X . Let the secret key V ∼ Unif(V). For each realized key value v ∈ V, define the keyed output distribution PX|V =v = δv . Then the following holds: 1. The scheme is perfectly distortion-free on average over the key: EV [PX|V ] = Q. 2. The scheme is far from per-key distortion-free. For every v ∈ V, dTV (PX|V =v , Q) = dTV (δv , Q) = 1 − N1 . 3. If the detector observes both X and the realized key V , then the null law H0 : V ∼ Unif(V), X ∼ Q, X ⊥ V and the watermarked law H1 : V ∼ Unif(V), X = V have H1 H0 total variation distance dTV (PX,V , PX,V ) = 1 − N1 . In particular, the test Φ(x, v) = 1{x = v} satisfies 1 PH1 [Φ(X, V ) = 1] = 1, PH0 [Φ(X, V ) = 1] = , N and hence has distinguishing advantage 1 − 1/N . Consequently, perfect average-key distortion-freeness does not prevent strong detectability once the realized key is used by the detector. Moreover, for every ε < 1, choosing N large enough so that 1 − N1 > ε gives an average-key perfectly distortion-free scheme whose keyed detection advantage exceeds the per-key TV budget ε. P 1 Proof. First, for each x ∈ X , EV [PX|V (x)] = N1 N v=1 δv (x) = N = Q(x). Therefore EV [PX|V ] = Q, so the scheme is perfectly distortion-free on average over the key. P Next, fix v ∈ V. Since PX|V =v = δv and Q is uniform, dTV (δv , Q) = 12 N x=1 |δv (x) − Q(x)|. The term x = v contributes 1 − N1 = 1 − N1 , while the remaining N − 1 terms contribute
P 1 N −1 1 1 1 1 1 x̸=v 0 − N = N = 1 − N . Thus dTV (δv , Q) = 2 1 − N + 1 − N = 1 − N . It remains to compute the joint distinguishability: Under H1 , ( 1 , x = v, H1 PX,V (x, v) = N 0, x ̸= v. H0 Under H0 , X and V are independent uniforms, so PX,V (x, v) = N12 N

H1 H0 dTV (PX,V , PX,V )=

∀x, v. Therefore

N

1 X X H1 H0 (x, v) . PX,V (x, v) − PX,V 2 v=1 x=1

2 − N For the N diagonal pairs x = v, the absolute difference is N1 − N12 = NN−1 2 . For the N H H 1 0 off-diagonal pairs x ̸= v, the absolute difference is 0 − N12 = N12 . Hence dTV (PX,V , PX,V ) =

34

Figure 5: Message recovery for a variable length prefix of a 500-1000 token sequence at various ε budgets. 1 2



 1 2 N · NN−1 2 + (N − N ) · N 2 . Simplifying,  N −1 N −1 1 + =1− . 2 N N N

1 H1 H0 dTV (PX,V , PX,V )=



Finally, for the test Φ(x, v) = 1{x = v}, we have under H1 that X = V always, so PH1 [Φ(X, V ) = 1] = 1. Under uniform random variables on {1, . . . , N }, so PH0 [Φ(X, V ) = P H0 , X and V are independent 1 1 1 1 1] = N = v]P[X = v] = N · · P[V v=1 N N = N . Thus the test has distinguishing advantage 1 − N . This proves the proposition.

D

Additional Experiments

We provide additional experimental results. Unless specified in the experiment, the setting is identical to that of Section 4.

D.1

Long-form decoding

We experiment with decoding lower ε-budgets under a 500-1000 token length sequence. SimpleMark’s decoder is able to recover the messages quite accurately in this regime. We use the Qwen-3.5-9B-Base model. The results are shown in Figure 5.

D.2

Llama3.1-8B-Instruct Reasoning

We include the Llama3.1-8B-Instruct reasoning results here. All results are consistent with the unwatermarked output in a TV or KL ε = 0.05 decodable regime. AIME was omitted from the table since out of the 2024 and 2025 exams, no model configuration got over 2 problems correct.

D.3

Robustness to token substitution

Figure 6 depicts the message decoding accuracy for a 300 token sequence when a % of the tokens are substituted with a random word in the vocabulary. As expected, the message recovery exponentially degrades as the substitution % increases. 35

Scheme

GSM8K (n=300) GPQA-D (n=198) LCB (n=300)

3-bit payload SimpleMark TV (ε=0.05, αmax =1500) SimpleMark KL (ε=0.05, αmax =1500) BiMark ArcMark Unwatermarked

253 249 251 249 249

58 42 45 54 56

62 54 58 65 60

8-bit payload SimpleMark TV (ε=0.05, αmax =1500) SimpleMark KL (ε=0.05, αmax =1500) BiMark ArcMark Unwatermarked

252 247 248 259 249

55 61 53 56 56

60 62 55 57 60

Table 3: Reasoning performance on several tasks for Llama3.1-8B-Instruct (temperature 0.6) on GSM8K (300 problems×2 independent generations), GPQA-Diamond (198 problems), and LiveCodeBench (300 problems, graded on public test cases only, so counts are only comparable across schemes). We use identical tasks and datasets for every benchmark. We evaluate SimpleMark at two operating points (q=53, TV or KL ε = 0.05, cap αmax =1500), BiMark, ArcMark, and no watermark.

D.4

Zero-Bit Detection

Figure 7 reports the true positive rate of zero-bit detection as a function of text length at fixed false positive rates of 10−2 , 10−6 , and 10−12 , on Qwen3.5-9B on the top and Llama3.1-8B Instruct on the bottom. Rapid zero-bit detection is not an unambiguous virtue: the keyed detector’s power is fueled by the same distributional deviation an adversary can exploit, and the baselines detect quickly precisely because their realized per-token deviations are large (46–65% distinguishing advantage, Figure 2), far in excess of what reliable detection requires. SimpleMark instead caps the keyed per-token distinguishing advantage by ε.

D.5

Ablation on different field, token sampling, and simplex size q

Throughout the paper we restricted SimpleMark’s simplex, LDPC code field size, and top-k sampling all to 53. In this section we rerun experiments with a smaller parameter of 29. We include message decoding 8, perplexity 9, and GSM8K reasoning 10 baselines with αmax ∈ {200, 500, 1000}. All experiments are exactly the same, besides the simplex, LDPC code, and top-k sampling size. We use Qwen-3.5-9B-Base for the reasoning and embed a 16-bit payload.

36

Figure 6: Substitution for a variable percentage of tokens in a 300 token sequence. For ε ∈ {0.05, 0.15}, and context hashing window h = 2, 3. SimpleMark is decently robust to substitution edit attacks.

37

Figure 7: Zero-bit detection for SimpleMark, ArcMark, and Bimark at different FPR. At higher distortion budgets we see overall improvement on the baselines for detection rate. For lower distortion budgets we stay closer to the unwatermarked distribution, so naturally we see lower detection rates.

Figure 8: Message recovery for a variable length prefix of a 300 token sequence for q = {29, 53} at various ε budgets.

38

Figure 9: Perplexity with different parameters for q = {29, 53}. Both remain close to the unwatermarked baselines.

Figure 10: Reasoning for SimpleMark under the different parameter sizes and αmax .

39

Related documents

• SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints#1201725
• CertMark: Distortion-Free Multi-Bit Watermarking with Certified Decoding#1118044
• A comprehensive survey of watermarking techniques for copyright protection and integrity verification on DNNs and generative models#279730
• Signature filtering: a lightweight enhancement for statistical watermark detection in large language models#287072
• A Watermark for Large Language Models#16582