Paper deep dive
SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints
Benjamin D. Kim, Wanrong Zhang, Weitong Ruan, Lav R. Varshney, Daniel Alabi
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.05712v1
- Canonical: https://arxiv.org/abs/2610.05712v1
Trouble viewing inline? Open PDF directly →
Full Text
96,216 characters extracted from source content.
Expand or collapse full text
SimpleMark: Fast Multi-Bit Text Watermarking under f-Divergence Constraints Benjamin D. Kim Affiliation: Massachusetts Institute of Technology Wanrong Zhang Weitong Ruan Affiliation: Amazon Lav R. Varshney Affiliation: Stony Brook University Daniel Alabi Affiliation: 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 (Longpre et al., 2024). 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 (Kirchenbauer et al., 2023). While early watermarking schemes primarily focus on zero-bit detection (to ascertain the presence of a watermark) (Christ et al., 2023; Kuditipudi et al., 2024; Kirchenbauer et al., 2023), many applications require multi-bit watermarking, where the generated text carries a message such as a user identifier, model identifier, timestamp, or policy tag (Cox et al., 2007). 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 (Jiang et al., 2025). 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 (Gilani et al., 2026). This is because in adversarial settings (Chang et al., 2025; Zhang et al., 2024; Adelsbach et al., 2003), security should hold for the actual distribution produced in a realized execution, not after averaging over secret keys (Katz and Lindell, 2014). 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 (Cox et al., 2007). 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)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. 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−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(Qt∗∥Qt)≤εD_f(Q_t^*\|Q_t)≤ , and samples from the watermarked distribution Qt∗Q_t^*. The message can then be decoded with one of the decoders. A detailed procedure is in Section 3.1. 1.1 Related Work Multi-bit Watermarks Recently, a variety of multi-bit watermarks have been developed for language models (Yoo et al., 2024; Jiang et al., 2025; Qu et al., 2025; Xu et al., 2025; Jiang et al., 2026; Cui et al., 2026). Two prominent ones are BiMark (Feng et al., 2025) and ArcMark (Gilani et al., 2026). A pivotal advancement is the development of provably robust frameworks; (Qu et al., 2025) use error-correction codes (ECC) to provide formal guarantees within specific edit-distance bounds, whereas (Cohen et al., 2025) establishes resistance against adaptive prompting. Recent work such as (Xu et al., 2026) further optimizes this tradeoff by employing block-wise encoding to ensure high recovery rates even in short-form textual outputs, while (Guo et al., 2026) 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. Watermark Per-token watermark- specific overhead Decoding cost ArcMark O(I||r)O(I\,|V|\,r) O(n(||+2b))O\! (n(|V|+2^b) ) BiMark O(d||)O(d\,|V|) O(nd+b)O(nd+b) StealthInk O(||)O(|V|) O(n||+(b/c)2c)O\! (n|V|+(b/c)2^c ) MC2Mark O(m||+m(n′n′/2)n′)O\! (m|V|+m n n /2n ) O(nmn′+b)O(n\,m\,n +b) QuantileMark O(||log||+M)O(|V| |V|+M) O(n(||log||+M)+(b/m′)M)†O\! (n(|V| |V|+M)+(b/m )M ) MirrorMark O(L||)O(L\,|V|) O(n(b/c+2cL))O\! (n(b/c+2^cL) ) SimpleMark Oq(1)O_q(1) O(n||+2bn)†O\! (n|V|+2^bn ) Table 1: Complexity comparison between SimpleMark and other known multi-bit watermark schemes. †Note the decoder requires a model replay. We assume q=53q=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 (Gilani et al., 2026); d: reweighting layers for BiMark (Feng et al., 2025) (d=10d=10); m: channel layers and n′n : segment length in bits for MC2Mark (Cui et al., 2026) (m=10m=10; n′n unspecified in their experiments); c: bits per message chunk for StealthInk (Jiang et al., 2025) and MirrorMark (Jiang et al., 2026) (c=1c=1 and c=2c=2 respectively; both papers denote this m); L: tournament layers for MirrorMark (L=30L=30). M: quantile bins per step for QuantileMark (Zhu et al., 2026) (M=2m′M=2^m with m′m bits per message symbol). 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 (Cachin, 2004; Cox et al., 2007). Early work characterized achievable rates for information hiding under distortion and attack constraints (Moulin and O’Sullivan, 2003; Moulin, 2003; Moulin, 2005; Moulin and Koetter, 2005), and coding-based schemes such as quantization-index modulation showed how structured codes can approach these limits (Chen and Wornell, 2001). 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 (Gilani et al., 2026; He et al., 2025). 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. 2 Preliminaries and Notation First, we introduce some useful notation and background, many of which can be found in standard textbooks (Ross, 1998; Gut, 2013; Mitzenmacher and Upfal, 2005; Keener, 2010). f-divergences. Let f:(0,∞)→ℝf:(0,∞) be convex with f(1)=0f(1)=0. For distributions P,QP,Q on X with P≪QP Q, the f-divergence of P from Q is Df(P∥Q):=∑x∈Q(x)f(P(x)Q(x))D_f(P\|Q):= _x Q(x)\,f ( P(x)Q(x) ). Every f-divergence satisfies the data-processing inequality: Df(κ(P)∥κ(Q))≤Df(P∥Q)D_f(κ(P)\|κ(Q))≤ D_f(P\|Q) for any (possibly randomized) map κ (Polyanskiy and Wu, 2025). We next discuss the two f-divergences this work focuses on. Total variation distance. For probability measures P,QP,Q on measurable space (,ℱ)(X,F), we define dTV(P,Q):=supA∈ℱ|P(A)−Q(A)|=12∑x∈|P(x)−Q(x)|.d_TV(P,Q):= _A |P(A)-Q(A)|= 12 _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 (Katz and Lindell, 2014). In particular, for any possibly randomized distinguisher :→0,1D:X→\0,1\, sup|PrX∼P[(X)=1]−PrX∼Q[(X)=1]|=dTV(P,Q). _D | _X P[D(X)=1]- _X Q[D(X)=1] |=d_TV(P,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,QP,Q on a finite alphabet X with P≪QP Q, the Kullback–Leibler divergence of P from Q is DKL(P∥Q):=∑x∈P(x)logP(x)Q(x)D_KL(P\|Q):= _x P(x) P(x)Q(x). In our setting, KL(P∥Q)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)H(P) for the entropy of P, PPL=exp(x∼P[−logQ(x)])=eH(P)eKL(P∥Q).PPL\;=\; \! (E_x P[- Q(x)] )\;=\;e^H(P)\,e^KL(P\|Q). Here, eKL(P∥Q)e^KL(P\|Q) is related to the multiplicative perplexity inflation introduced by watermarking. Watermarked distribution. Fix ε≥0 ≥ 0. A watermarked distribution Qt⋆=PXt∣M=m,Vt=vQ_t =P_X_t M=m,V_t=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)≤ε.D_f (P_X_t M=m,V_t=v\,\|\,Q_t )≤ . Equivalently, when the encoder depends on (m,v)(m,v) only through the state Zt=zt(m,v)Z_t=z_t(m,v), the distribution is (uniformly per-key) ε -distortion-free iff Df(PXt|Zt=z∥Qt)≤εfor every realizable z∈,∀t.D_f (P_X_t Z_t=z\,\|\,Q_t )≤ every realizable 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 =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. • Embedding: at each time t, the watermarked distribution Qt⋆Q_t is computed in closed form while adhering to the divergence budget. The watermarked token XtX_t is sampled. • Decoding: a decoder uses a likelihood decoder to compute M 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…CnC_1… C_n over qF_q for a prime q. For a k×nk× n systematic generator matrix G corresponding to a sparse parity-check matrix H, the resulting codeword is C=m⋅GC=m· G. The generator matrix can be considered public information. At each step t, the shared secret St=(Vt,σt)S_t=(V_t, _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 VtV_t uniform on ℛ=0,…,q−1R=\0,…,q-1\ and a keyed bijection σt:t→ℛ _t:S_t , where t⊂S_t is the top-q truncated support of the vocabulary V, so |t|=q|S_t|=q and each vertex receives exactly one token. We identify codeword symbols, key values, and colored tokens with the vertices of the (q−1)(q-1)-simplex: the codeword symbol Ct∈qC_t _q is mapped to vertex CtC_t, the key value VtV_t to vertex VtV_t, and the token x∈tx _t to vertex σt(x) _t(x). The channel input vertex at time t is then Zt=(Ct+Vt)modq.Z_t= (C_t+V_t ) 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 Qt⋆Q_t by solving a constrained minimization problem which admits a closed-form solution. For each token, let σt(x) _t(x) be the vertex assigned to x, where σt _t is the random bijection shared between the watermarker and detector at time t, and let ZtZ_t be the target vertex defined in (1). We define the embedding cost dt(x)=[σt(x)≠Zt],d_t(x)=1\! [ _t(x)≠ Z_t ], which is the discrete metric on the vertex set, since all pairs of vertices are equidistant. The watermarked distribution is then chosen as Qt⋆∈argmin∑x∈tP∈Δ(t)P(x)dt(x)s.t.D(P,Qt)≤ε,Q_t ∈ _P∈ (S_t) _x _tP(x)d_t(x) .t. D(P,Q_t)≤ , (2) where ε is the selected divergence budget and D is a selectable f-divergence, taken here to be either dTVd_TV or DKLD_KL. Equivalently, the embedding step moves as much probability mass as permitted by the constraint onto the token coloured ZtZ_t, while keeping the watermarked distribution within distance ε of the base model distribution. Because the cost is an indicator, the objective in (2) depends on P only through the mass it places on the target vertex. Writing B=∑x:σt(x)=ZtQt(x)B= _x: _t(x)=Z_tQ_t(x) and s=∑x:σt(x)=ZtP(x)s= _x: _t(x)=Z_tP(x), the data-processing inequality gives D(P,Qt)≥D(Bern(s),Bern(B))D(P,Q_t)≥ 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 Qt⋆(x)=αtQt(x),σt(x)=Zt,βtQt(x),σt(x)≠Zt,αt=s⋆B,βt=1−s⋆1−B,Q_t (x)= cases _t\,Q_t(x),& _t(x)=Z_t,\\ _t\,Q_t(x),& _t(x)≠ Z_t, cases _t= s B, _t= 1-s 1-B, (3) where s⋆=B+min(ε,1−B)s =B+ ( ,1-B) when D=dTVD=d_TV, and s⋆s is the unique root in [B,1][B,1] of slogsB+(1−s)log1−s1−B=εs sB+(1-s) 1-s1-B= when D=DKLD=D_KL.11 1 For ε≤log(1/B) ≤ (1/B). For ε>log(1/B) > (1/B), the constrained optimum is simply s∗=1s^*=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∼Qt⋆(⋅∣x<t).X_t Q_t (· x_<t). The generated token is appended to the context, and the procedure is repeated for t=1,…,nt=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:nx_1:n, the decoder replays the language model to recover the base next-token distributions Qt(⋅)=Q(⋅∣x<t)Q_t(·)=Q(· x_<t). It also reconstructs the shared key sequence St=(Vt,σt)S_t=(V_t, _t). For each possible code symbol a∈0,…,q−1a∈\0,…,q-1\, the decoder forms the corresponding target vertex zt(a)=(a+Vt)modq.z_t(a)= (a+V_t ) q. Using this vertex, the decoder evaluates the probability assigned to the observed token xtx_t by the divergence-constrained embedding distribution: Qt,a⋆(x)=sa⋆BaQt(x),σt(x)=zt(a),1−sa⋆1−BaQt(x),σt(x)≠zt(a),Ba=∑x:σt(x)=zt(a)Qt(x),Q_t,a (x)= cases s _aB_a\,Q_t(x),& _t(x)=z_t(a),\\[6.0pt] 1-s _a1-B_a\,Q_t(x),& _t(x)≠ z_t(a), cases B_a=\!\! _x: _t(x)=z_t(a)\!\!Q_t(x), with sa⋆s _a obtained from BaB_a and ε as in the embedding step. This defines the per-symbol log-likelihood Lt(a)=logQt,a⋆(xt).L_t(a)= Q_t,a (x_t). For a candidate message m m with codeword C(m)=(C1,…,Cn)C(m)=(C_1,…,C_n), the decoder sums these likelihoods: Λ(m^)=∑t=1nLt(Ct(m^)). ( m)= _t=1^nL_t(C_t( m)). The decoded message is the maximum-likelihood codeword, M^=argmaxm^Λ(m^). M= _ m ( 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 → 0). Let X and Z be finite alphabets, let Q∈Δ()Q∈ (X) be a fixed base distribution, and let PZP_Z be a fixed distribution on Z. For ε≥0 ≥ 0, define the feasible set ℱ(ε):=(PX|Z=z)z∈:dTV(PX|Z=z,Q)≤εfor all z∈.F( ):= \ (P_X Z=z )_z :d_TV(P_X Z=z,Q)≤ \ for all z \. Define the constrained capacity C(ε):=sup(PX|Z=z)∈ℱ(ε)I(Z,X),C( ):= _ (P_X Z=z ) ( )I(Z;X), where the mutual information is computed under the joint law PZ,X(z,x)=PZ(z)PX|Z=z(x).P_Z,X(z,x)=P_Z(z)P_X Z=z(x). Then limε→0C(ε)=0. _ → 0C( )=0. In particular, any achievable embedding rate under the uniform per-key TV constraint must approach 00 as ε→0 → 0. Proof. We first show C(0)=0C(0)=0. If (PX|Z=z)z∈ℱ(0), (P_X Z=z )_z (0), then for every z∈z , dTV(PX|Z=z,Q)=0.d_TV(P_X Z=z,Q)=0. Since total variation distance vanishes if and only if the two distributions are equal (Keener, 2010), it follows that PX|Z=z=Q,P_X 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.I(Z;X)=0. Taking the supremum over all feasible channels shows that C(0)=0.C(0)=0. We now prove that C(ε)→0C( )→ 0 as ε→0 → 0. Let (εn)n≥1( _n)_n≥ 1 be any sequence with εn↓0 _n 0. For each n, choose a feasible channel family (PX|Z=z(n))z∈ℱ(εn) (P^(n)_X Z=z )_z ( _n) such that In:=IP(n)(Z,X)≥C(εn)−1n.I_n:=I_P^(n)(Z;X)≥ C( _n)- 1n. Because X and Z are finite, the product of simplices ∏z∈Δ() _z (X) is compact (Munkres, 1984). Hence, there exists (Rudin, 1964) a subsequence, which we still index by n, such that for every z∈z , PX|Z=z(n)→PX|Z=z⋆P^(n)_X Z=z→ P _X Z=z for some limiting channel family (PX|Z=z⋆)z∈ (P _X Z=z )_z . Since each P(n)P^(n) is feasible, dTV(PX|Z=z(n),Q)≤εnd_TV\! (P^(n)_X Z=z,Q )≤ _n for all z.z. Letting n→∞n→∞ gives dTV(PX|Z=z⋆,Q)=0d_TV\! (P _X Z=z,Q )=0 for all z,z, and therefore PX|Z=z⋆=QP _X Z=z=Q for all z∈.z . So under the limiting channel, X is independent of Z, and thus IP⋆(Z,X)=0.I_P (Z;X)=0. Because mutual information is continuous in the joint distribution on finite alphabets (Polyanskiy and Wu, 2025; Cover and Thomas, 2006), we have In=IP(n)(Z,X)→IP⋆(Z,X)=0.I_n=I_P^(n)(Z;X)→ I_P (Z;X)=0. But C(εn)≤In+1n,C( _n)≤ I_n+ 1n, so taking limits yields lim supn→∞C(εn)≤0. _n→∞C( _n)≤ 0. Since mutual information is always nonnegative, C(εn)≥0,C( _n)≥ 0, hence limn→∞C(εn)=0. _n→∞C( _n)=0. Because this holds for every sequence εn↓0 _n 0, it follows that limε→0C(ε)=0. _ → 0C( )=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 conditional-memoryless model. Let a sequence of length-n watermarking schemes satisfy the uniform per-key ε -TV constraint, and let the decoder error probability Pe(n):=Pr[M^≠M]P_e^(n):= [ M≠ M] tend to zero as n→∞n→∞. If Rn:=knR_n:= kn denotes the embedded rate in bits per token, then for every n, Rn≤1n∑t=1nC~t(ε)+1+nRnPe(n)n,R_n≤ 1n _t=1^n C_t( )+ 1+nR_nP_e^(n)n, where C~t(ε) C_t( ) is the universal constrained channel capacity given in the Appendix as Definition 5. Consequently, if (Rn)n(R_n)_n is bounded and Pe(n)→0P_e^(n)→ 0, then lim supn→∞Rn≤lim supn→∞1n∑t=1nC~t(ε). _n→∞R_n≤ _n→∞ 1n _t=1^n C_t( ). 4 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 (Gilani et al., 2026) and BiMark (Feng et al., 2025). 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 (Qwen Team, 2026) and Llama3.1-8B-Instruct (Grattafiori et al., 2024). When applicable, we use the C4-RealNewslike dataset (Raffel et al., 2020) and a temperature of 1.0. Each trial generates 300 tokens and is evaluated at the prefix of 50,100,…,30050,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=53q=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 ∈\0.01,0.05,0.1,0.15\ and, where stated, with the per-token likelihood-ratio cap αmax∈500,1500,2000 _ ∈\500,1500,2000\. BiMark (Feng et al., 2025) is run with d=10d=10 partition layers, δ~=1.0 δ=1.0, context width 2 and top-50 sampling; ArcMark (Gilani et al., 2026) with top-50 sampling, context width 2, r=64r=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. 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. 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 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 (Cobbe et al., 2021), GPQA-Diamond (Rein et al., 2023), LiveCodeBench (Jain et al., 2025), and AIME 2024 (Zhang and Math-AI, 2024). We use 300, 198, 100, and 30 problems respectively, with a generation budget of 4,096 tokens for GSM8K, 8,192 for GPQA-Diamond 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 =0.05 (TV) and ε=0.05 =0.05 (KL), both with αmax=1500 _ =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. Scheme GSM8K GPQA-D LCB AIME 2024 (trials) (300) (198) (100100) (3030) 3-bit payload SimpleMark TV (ε=0.05 =0.05, αmax=1500 _ =1500) 278 112 33 8 SimpleMark KL (ε=0.05 =0.05, αmax=1500 _ =1500) 274 108 40 9 BiMark 270 107 33 11 ArcMark 272 111 35 10 Unwatermarked 272 110 36 8 8-bit payload SimpleMark TV (ε=0.05 =0.05, αmax=1500 _ =1500) 275 103 38 9 SimpleMark KL (ε=0.05 =0.05, αmax=1500 _ =1500) 273 102 41 8 BiMark 279 94 33 8 ArcMark 274 109 40 7 Unwatermarked 272 110 36 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=53q=53, TV or KL ε=0.05 =0.05, cap αmax=1500 _ =1500), BiMark, ArcMark, and no watermark. 4.4 Perplexity 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. 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 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\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\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. Figure 4: Message recovery for a variable length prefix of a 300 token sequence. For ε∈0.05,0.1,0.15 ∈\0.05,0.1,0.15\. The SimpleMark decoding capabilities outperform the current SOTA at ε=0.15, =0.15, and remain competitive with lower, more practical ε budgets. 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 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. References [1] A. Adelsbach, S. Katzenbeisser, and H. Veith (2003) Watermarking schemes provably secure against copy and ambiguity attacks. In Proceedings of the 3rd ACM Workshop on Digital Rights Management, DRM ’03, New York, NY, USA, p. 111–119. External Links: ISBN 1581137869, Link, Document Cited by: §1. [2] C. Cachin (2004) An information-theoretic model for steganography. Information and Computation 192 (1), p. 41–56. External Links: ISSN 0890-5401, Document, Link Cited by: §1.1. [3] H. Chang, H. Hassani, and R. Shokri (2025) Watermark smoothing attacks against language models. In Findings of the Association for Computational Linguistics: EMNLP 2025, C. Christodoulopoulos, T. Chakraborty, C. Rose, and V. Peng (Eds.), Suzhou, China, p. 4915–4941. External Links: Link, Document, ISBN 979-8-89176-335-7 Cited by: §1. [4] B. Chen and G. W. Wornell (2001) Quantization index modulation: a class of provably good methods for digital watermarking and information embedding. IEEE Transactions on Information theory 47 (4), p. 1423–1443. Cited by: §1.1. [5] M. Christ, S. Gunn, and O. Zamir (2023) Undetectable watermarks for language models. IACR Cryptol. ePrint Arch., p. 763. External Links: Link Cited by: §1. [6] K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, et al. (2021) Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Cited by: §4.3. [7] A. Cohen, A. Hoover, and G. Schoenbach (2025) Watermarking language models for many adaptive users. In 2025 IEEE Symposium on Security and Privacy (SP), p. 2583–2601. Cited by: §1.1. [8] T. M. Cover and J. A. Thomas (2006) Elements of information theory 2nd edition (wiley series in telecommunications and signal processing). Wiley-Interscience. External Links: ISBN 0471241954 Cited by: §B.1, §B.1, §3.2. [9] I. Cox, M. Miller, J. Bloom, J. Fridrich, and T. Kalker (2007) Digital watermarking and steganography. 2 edition, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. External Links: ISBN 9780080555805 Cited by: §1.1, §1, §1. [10] X. Cui, R. Chen, Y. Wu, and H. Huang (2026) MC2^2mark: distortion-free multi-bit watermarking for long messages. External Links: 2602.14030, Link Cited by: §1.1, Table 1. [11] X. Feng, H. Zhang, Y. Zhang, L. Y. Zhang, and S. Pan (2025) BiMark: unbiased multilayer watermarking for large language models. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §1.1, Table 1, §4.1, §4. [12] A. Gilani, S. Vithana, C. X. Long, O. Kosut, L. Sankar, and F. P. Calmon (2026) ArcMark: distortion-free multi-byte llm watermark via optimal transport. arXiv preprint arXiv:2602.07235. Cited by: Appendix C, §1.1, §1.1, Table 1, §1, §4.1, §4. [13] A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, et al. (2024) The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Cited by: §4.1. [14] S. Guo, S. Vithana, A. Gilani, L. Sankar, O. Kosut, and F. P. Calmon (2026) Feedback coding enables inference-time covert agentic communication. External Links: 2609.24994, Link Cited by: §1.1. [15] A. Gut (2013) Probability: a graduate course. Springer Texts in Statistics, Springer New York. External Links: ISBN 9781461447078, LCCN 2012941281 Cited by: §2. [16] H. He, Y. Liu, Z. Wang, Y. Mao, and Y. Bu (2025) Theoretically grounded framework for LLM watermarking: a distribution-adaptive approach. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, External Links: Link Cited by: §1.1. [17] N. Jain, A. Gu, W. Li, F. Yan, T. Zhang, S. Wang, A. Solar-Lezama, K. Sen, and I. Stoica (2025) Livecodebench: holistic and contamination free evaluation of large language models for code. In International Conference on Learning Representations, Vol. 2025, p. 58791–58831. Cited by: §4.3. [18] Y. Jiang, M. K. Boroujeny, S. S. Kumar, and K. Zeng (2026) MirrorMark: generalizable mirrored sampling for multi-bit llm watermarking. arXiv preprint arXiv:2601.22246. Cited by: §1.1, Table 1. [19] Y. Jiang, C. Wu, M. K. Boroujeny, B. Mark, and K. Zeng (2025) StealthInk: a multi-bit and stealthy watermark for large language models. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 27685–27709. External Links: Link Cited by: §1.1, Table 1, §1. [20] J. Katz and Y. Lindell (2014) Introduction to modern cryptography, second edition. 2nd edition, Chapman & Hall/CRC. External Links: ISBN 1466570261 Cited by: §1, §2. [21] R.W. Keener (2010) Theoretical statistics: topics for a core course. Springer Texts in Statistics, Springer New York. External Links: ISBN 9780387938394, LCCN 2010935925 Cited by: §2, §3.2. [22] 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 2023, 23-29 July 2023, Honolulu, Hawaii, USA, Proceedings of Machine Learning Research, p. 17061–17084. External Links: Link Cited by: §1. [23] R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang (2024) Robust distortion-free watermarks for language models. Transactions on Machine Learning Research. External Links: Link Cited by: §1. [24] S. Longpre, R. Mahari, A. Chen, N. Obeng-Marnu, D. Sileo, W. Brannon, N. Muennighoff, N. Khazam, J. Kabbara, K. Perisetla, X. (. Wu, E. Shippole, K. Bollacker, T. Wu, L. Villa, S. Pentland, and S. Hooker (2024) A large-scale audit of dataset licensing and attribution in AI. Nature Machine Intelligence 6 (8), p. 975–987. External Links: Document, ISBN 2522-5839, Link Cited by: §1. [25] F.J. MacWilliams and N.J.A. Sloane (1978) The theory of error-correcting codes. 2nd edition, North-holland Publishing Company. Cited by: §B.1, §B.1. [26] M. Mitzenmacher and E. Upfal (2005) Probability and computing: randomized algorithms and probabilistic analysis. 2nd edition, Cambridge University Press, New York, NY, USA. External Links: ISBN 0521835402, Link Cited by: §2. [27] P. Moulin and R. Koetter (2005) Data-hiding codes. Proceedings of the IEEE 93 (12), p. 2083–2126. Cited by: §1.1. [28] P. Moulin and J. A. O’Sullivan (2003) Information-theoretic analysis of information hiding. IEEE Trans. Inf. Theory 49 (3), p. 563–593. External Links: Link, Document Cited by: §1.1. [29] P. Moulin (2003) Information-hiding games. In Digital Watermarking, Berlin, Heidelberg, p. 1–12. External Links: ISBN 978-3-540-36617-1 Cited by: §1.1. [30] P. Moulin (2005) The method of types and its application to information hiding. In 2005 13th European Signal Processing Conference, Vol. , p. 1–1. External Links: Document Cited by: §1.1. [31] J. R. Munkres (1984) Elements of Algebraic Topology. Addison Wesley Publishing Company. Note: Hardcover Cited by: §3.2. [32] Y. Polyanskiy and Y. Wu (2025) Information theory: from coding to learning. Cambridge University Press. External Links: ISBN 9781108832908, LCCN 2024004713 Cited by: §2, §3.2. [33] W. Qu, W. Zheng, T. Tao, D. Yin, Y. Jiang, Z. Tian, W. Zou, J. Jia, and J. Zhang (2025) Provably robust multi-bit watermarking for \ai-generated\ text. In 34th USENIX Security Symposium (USENIX Security 25), p. 201–220. Cited by: §1.1. [34] Qwen Team (2026) Qwen3.5: towards native multimodal agents. External Links: Link Cited by: §4.1. [35] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu (2020) Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research 21 (140), p. 1–67. Cited by: §4.1. [36] D. Rein, B. L. Hou, A. C. Stickland, J. Petty, R. Y. Pang, J. Dirani, J. Michael, and S. R. Bowman (2023) Gpqa: a graduate-level google-proof q&a benchmark. arXiv preprint arXiv:2311.12022. Cited by: §4.3. [37] S. M. Ross (1998) A first course in probability. Fifth edition. Cited by: §2. [38] W. Rudin (1964) Principles of mathematical analysis. International series in pure and applied mathematics, McGraw-Hill. External Links: ISBN 9780070542310, LCCN 63021479, Link Cited by: §3.2. [39] J. Xu, R. Hu, O. Kotevska, and Z. Zhang (2026) XMark: reliable multi-bit watermarking for llm-generated texts. arXiv preprint arXiv:2604.05242. Cited by: §1.1. [40] X. Xu, J. Jia, Y. Yao, Y. Liu, and H. Li (2025) Robust multi-bit text watermark with LLM-based paraphrasers. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §1.1. [41] K. Yoo, W. Ahn, and N. Kwak (2024) Advancing beyond identification: multi-bit watermark for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), K. Duh, H. Gomez, and S. Bethard (Eds.), Mexico City, Mexico, p. 4031–4055. External Links: Link, Document Cited by: §1.1. [42] H. Zhang, B. L. Edelman, D. Francati, D. Venturi, G. Ateniese, and B. Barak (2024) Watermarks in the sand: impossibility of strong watermarking for generative models. In Forty-first International Conference on Machine Learning, Cited by: §1. [43] Y. Zhang and T. Math-AI (2024) American invitational mathematics examination (aime) 2024. Cited by: §4.3. [44] J. Zhu, B. Huang, and X. Wan (2026) 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), p. 6790–6806. Cited by: Table 1. 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. Appendix 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. Algorithm 1 Per-key divergence-constrained encoder 1: Message m∈ℳm , blocklength n, LDPC codebook Cm(1:n)m∈ℳ\C_m(1:n)\_m over qF_q, secret key K, hash window h, divergence D∈dTV,DKLD∈\d_TV,D_KL\, budget ε , base laws (Qt)t=1n(Q_t)_t=1^n 2: Watermarked token sequence X1:nX_1:n 3: Encode m as the codeword Cm(1),…,Cm(n)C_m(1),…,C_m(n). 4: for t=1t=1 to n do 5: Derive the side information from the key and the preceding tokens, (Vt,σt)←Hash(K,Xt−h:t−1),(V_t, _t) (K,\,X_t-h:t-1), where Vt∈qV_t _q and σt:t→q _t:S_t _q is a keyed bijection on the truncated support. 6: Form the target vertex Zt←(Cm(t)+Vt)modq.Z_t←(C_m(t)+V_t) q. 7: Compute the base mass on the target vertex, Bt←∑x:σt(x)=ZtQt(x),B_t← _x\,:\, _t(x)=Z_tQ_t(x), and obtain st⋆s _t from (Bt,ε,D)(B_t, ,D): st⋆=Bt+min(ε,1−Bt)s _t=B_t+ ( ,1-B_t) if D=dTVD=d_TV; the unique root in [Bt,1][B_t,1] of slogsBt+(1−s)log1−s1−Bt=εs sB_t+(1-s) 1-s1-B_t= if D=DKLD=D_KL. If applicable, cap st∗=mins∗,αmaxBs^*_t= \s^*, _ B\ 8: Form the closed-form tilt Qt⋆(x)←st⋆BtQt(x),σt(x)=Zt,1−st⋆1−BtQt(x),σt(x)≠Zt.Q_t (x)← cases s _tB_t\,Q_t(x),& _t(x)=Z_t,\\[6.0pt] 1-s _t1-B_t\,Q_t(x),& _t(x)≠ Z_t. cases 9: Sample Xt∼Qt⋆.X_t Q_t . 10: end for 11: Output X1:nX_1:n; the side information (Vt,σt)t=1n(V_t, _t)_t=1^n is recomputable from K and the text itself. Algorithm 2 Per-key divergence-constrained MLE Decoder 1: Observed tokens x1:nx_1:n, secret key K, hash window h, codebook Cm(1:n)m∈ℳ\C_m(1:n)\_m , divergence D, budget ε , base model Q(⋅∣⋅)Q(· ·) 2: Message estimate m m 3: for t=1t=1 to n do 4: Recover the base law Qt(⋅)=Q(⋅∣x<t)Q_t(·)=Q(· x_<t), truncated and renormalized as in encoding, and recompute (Vt,σt)←Hash(K,xt−h:t−1)(V_t, _t) (K,\,x_t-h:t-1). 5: For each symbol a∈qa _q, form the candidate vertex and its base mass, zt(a)=(a+vt)modq,Ba←∑x:σt(x)=zt(a)Qt(x),z_t(a)=(a+v_t) q, B_a← _x\,:\, _t(x)=z_t(a)Q_t(x), obtain sa⋆s _a from (Ba,ε,D)(B_a, ,D) as in Algorithm 1, and store the per-symbol log-likelihood Lt(a)←log(sa⋆BaQt(xt)),σt(xt)=zt(a),log(1−sa⋆1−BaQt(xt)),σt(xt)≠zt(a).L_t(a)← cases \! ( s _aB_a\,Q_t(x_t) ),& _t(x_t)=z_t(a),\\[6.0pt] \! ( 1-s _a1-B_a\,Q_t(x_t) ),& _t(x_t)≠ z_t(a). cases 6: end for 7: for each candidate message m∈ℳm do 8: Compute the log-likelihood score Λ(m):=∑t=1nLt(Cm(t)). (m):= _t=1^nL_t (C_m(t) ). 9: end for 10: Output any maximizer m^∈argmaxm∈ℳΛ(m). m∈ _m (m). Appendix 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 =[1:N]X=[1:N] denote the token vocabulary. At time t, the base language model induces a next-token distribution Qt∈Δ(),Q_t∈ (X), where Δ() (X) is the probability simplex on X. As in ArcMark and SimpleMark, the message M∈ℳ:=1,…,2kM :=\1,…,2^k\ is encoded into a codeword with an error correcting code CM(1),…,CM(n)∈q:=0,1,…,q−1,C_M(1),…,C_M(n) _q:=\0,1,…,q-1\, and the encoder and decoder share side information Vt∼Unif(q),t=1,…,n.V_t (F_q), t=1,…,n. The state variable is the target vertex Zt:=(CM(t)+Vt)modq∈:=q,Z_t:=(C_M(t)+V_t) q\;∈\;Z:=F_q, identified with the vertices of the (q−1)(q-1)-simplex via the keyed bijection σt _t of Section 3.1. We assume throughout that: 1. The message M is uniform on ℳM. 2. The side information sequence V1,…,VnV_1,…,V_n is i.i.d. and independent of M. 3. Given (M,V1,…,Vn)(M,V_1,…,V_n), the encoder generates tokens through a conditional-memoryless channel: PX1:n∣M,V1:n(x1:n∣m,v1:n)=∏t=1nPXt|Zt=zt(m,vt)(xt).P_X_1:n M,V_1:n(x_1:n m,v_1:n)= _t=1^nP_X_t Z_t=z_t(m,v_t)(x_t). 4. The decoder observes (X1:n,V1:n)(X_1:n,V_1:n) and outputs M M. Definition 1 (Uniform per-key ε -TV distortion). Fix ε≥0 ≥ 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∈qv _q, dTV(PXt∣M=m,Vt=v,Qt)≤ε.d_TV (P_X_t M=m,V_t=v,Q_t )≤ . Equivalently, since ZtZ_t is a deterministic function of (m,v)(m,v), the scheme is uniformly per-key ε -TV distortion-free iff dTV(PXt|Zt=z,Qt)≤ε∀z∈,∀t.d_TV (P_X_t Z_t=z,Q_t )≤ ∀ z ,\ ∀ t. Definition 2 (Feasible per-key channel family). For each time t and distortion budget ε≥0 ≥ 0, define ℱt(ε):=(PXt|Zt=z)z∈:dTV(PXt|Zt=z,Qt)≤ε∀z∈.F_t( ):= \ (P_X_t Z_t=z )_z :d_TV(P_X_t Z_t=z,Q_t)≤ \ \ ∀ z \. Definition 3 (Per-key constrained embedding channel). For each time t, choose a channel family (PXt|Zt=z(ε))z∈ℱt(ε). (P^( )_X_t Z_t=z )_z _t( ). Given message m and side information vtv_t, form zt=zt(m,vt)=(Cm(t)+vt)modq,z_t=z_t(m,v_t)=(C_m(t)+v_t) q, and sample Xt∼PXt|Zt=zt(ε).X_t P^( )_X_t Z_t=z_t. Proposition 2 (Uniform per-key distortion-freeness). If the encoder uses channel families (PXt|Zt=z(ε))z∈ℱt(ε)for all t, (P^( )_X_t Z_t=z )_z _t( ) all t, then the resulting scheme is uniformly per-key ε -TV distortion-free: dTV(PXt∣M=m,Vt=v,Qt)≤ε∀t,∀m,∀v.d_TV (P_X_t M=m,V_t=v,Q_t )≤ ∀ t,\ ∀ m,\ ∀ v. Proof. Fix t∈[1:n]t∈[1:n], m∈ℳm , and v∈qv _q. By construction, Zt=zt(m,v)=(Cm(t)+v)modq∈.Z_t=z_t(m,v)=(C_m(t)+v) q . Conditioned on (M,Vt)=(m,v)(M,V_t)=(m,v), the encoder samples XtX_t according to the conditional law attached to this state: PXt∣M=m,Vt=v=P(ε)Xt|Zt=zt(m,v).P_X_t M=m,V_t=v=P^( )_X_t Z_t=z_t(m,v). Since (PXt|Zt=z(ε))z∈ℱt(ε), (P^( )_X_t Z_t=z )_z _t( ), the definition of ℱt(ε)F_t( ) yields dTV(PXt|Zt=z(ε),Qt)≤ε∀z∈.d_TV (P^( )_X_t Z_t=z,Q_t )≤ ∀ z . Applying this to z=zt(m,v)z=z_t(m,v) gives dTV(PXt∣M=m,Vt=v,Qt)=dTV(PXt|Zt=zt(m,v)(ε),Qt)≤ε.d_TV (P_X_t M=m,V_t=v,Q_t )=d_TV (P^( )_X_t Z_t=z_t(m,v),Q_t )≤ . Because t,m,vt,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∈ℱt(ε)I(Zt,Xt),C_t( ):= _ (P_X_t Z_t=z )_z _t( )I(Z_t;X_t), where the mutual information is computed under the joint law PZt,Xt(z,x)=PZt(z)PXt|Zt=z(x).P_Z_t,X_t(z,x)=P_Z_t(z)P_X_t Z_t=z(x). Definition 5 (Universal single-letter constrained capacity). For each time t, define C~t(ε):=sup(PXt|Zt=z)z∈ℱt(ε)PZt∈Δ()I(Zt,Xt), C_t( ):= _ subarrayc(P_X_t Z_t=z)_z _t( )\\ P_Z_t∈ (Z) subarrayI(Z_t;X_t), where the mutual information is computed under the joint law PZt,Xt(z,x)=PZt(z)PXt|Zt=z(x).P_Z_t,X_t(z,x)=P_Z_t(z)\,P_X_t Z_t=z(x). 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 Pe(n):=Pr[M^≠M]P_e^(n):= [ M≠ M] tend to zero as n→∞n→∞. If Rn:=knR_n:= kn denotes the embedded rate in bits per token, then for every n, Rn≤1n∑t=1nC~t(ε)+1+nRnPe(n)n.R_n≤ 1n _t=1^n C_t( )+ 1+nR_nP_e^(n)n. Consequently, if (Rn)n(R_n)_n is bounded and Pe(n)→0P_e^(n)→ 0, then lim supn→∞Rn≤lim supn→∞1n∑t=1nC~t(ε). _n→∞R_n≤ _n→∞ 1n _t=1^n C_t( ). Proof. Since M is uniform on ℳM with |ℳ|=2k|M|=2^k, H(M)=k=nRn.H(M)=k=nR_n. By Fano’s inequality [8], H(M∣X1:n,V1:n)≤h2(Pe(n))+Pe(n)log(|ℳ|−1)≤1+nRnPe(n).H(M X_1:n,V_1:n)≤ h_2(P_e^(n))+P_e^(n) (|M|-1)≤ 1+nR_nP_e^(n). Therefore, nRn=H(M)=I(M;X1:n,V1:n)+H(M∣X1:n,V1:n),nR_n=H(M)=I(M;X_1:n,V_1:n)+H(M X_1:n,V_1:n), so nRn≤I(M;X1:n,V1:n)+1+nRnPe(n).nR_n≤ I(M;X_1:n,V_1:n)+1+nR_nP_e^(n). Because M and V1:nV_1:n are independent, I(M;X1:n,V1:n)=I(M;X1:n∣V1:n).I(M;X_1:n,V_1:n)=I(M;X_1:n V_1:n). Hence nRn≤I(M;X1:n∣V1:n)+1+nRnPe(n).nR_n≤ I(M;X_1:n V_1:n)+1+nR_nP_e^(n). Applying the chain rule gives I(M;X1:n∣V1:n)=∑t=1nI(M;Xt∣X1:t−1,V1:n).I(M;X_1:n V_1:n)= _t=1^nI(M;X_t X_1:t-1,V_1:n). Fix t. Let Ut:=(X1:t−1,V1:n).U_t:=(X_1:t-1,V_1:n). Since ZtZ_t is a deterministic function of (M,Vt)(M,V_t), and by the conditional-memoryless assumption PXt∣M,V1:n,X1:t−1=PXt|Zt,P_X_t M,V_1:n,X_1:t-1=P_X_t Z_t, we have the conditional Markov chain M⟶Zt⟶Xtgiven Ut.M Z_t X_t U_t. Therefore, by data processing [8], I(M;Xt∣Ut)≤I(Zt;Xt∣Ut).I(M;X_t U_t)≤ I(Z_t;X_t U_t). Thus I(M;X1:n∣V1:n)≤∑t=1nI(Zt;Xt∣Ut).I(M;X_1:n V_1:n)≤ _t=1^nI(Z_t;X_t U_t). Now expand the conditional mutual information: I(Zt;Xt∣Ut)=∑uPUt(u)I(Zt;Xt∣Ut=u).I(Z_t;X_t U_t)= _uP_U_t(u)\,I(Z_t;X_t U_t=u). Fix any u with PUt(u)>0P_U_t(u)>0. Conditioned on Ut=uU_t=u, the channel from ZtZ_t to XtX_t is still the same single-letter channel family (PXt|Zt=z)z∈,(P_X_t Z_t=z)_z , while the input law of ZtZ_t becomes the posterior distribution PZt|Ut=u.P_Z_t U_t=u. Because the scheme satisfies the uniform per-key ε -TV constraint, this channel family belongs to ℱt(ε)F_t( ). Hence, by Definition 5, I(Zt;Xt∣Ut=u)≤C~t(ε).I(Z_t;X_t U_t=u)≤ C_t( ). Since this holds for every u, I(Zt;Xt∣Ut)≤C~t(ε).I(Z_t;X_t U_t)≤ C_t( ). Therefore, I(M;X1:n∣V1:n)≤∑t=1nC~t(ε).I(M;X_1:n V_1:n)≤ _t=1^n C_t( ). Substituting back into the Fano bound yields nRn≤∑t=1nC~t(ε)+1+nRnPe(n).nR_n≤ _t=1^n C_t( )+1+nR_nP_e^(n). Dividing by n gives Rn≤1n∑t=1nC~t(ε)+1+nRnPe(n)n.R_n≤ 1n _t=1^n C_t( )+ 1+nR_nP_e^(n)n. This proves the finite-n bound. If (Rn)n(R_n)_n is bounded and Pe(n)→0P_e^(n)→ 0, then the additive term on the right tends to 00, so lim supn→∞Rn≤lim supn→∞1n∑t=1nC~t(ε). _n→∞R_n≤ _n→∞ 1n _t=1^n C_t( ). ∎ The following achievability result should be interpreted as an achievability theorem for the induced single-letter channel PX|ZP_X|Z, assuming that the encoder can realize codewords zn(m)∈nz^n(m) ^n with empirical distribution approaching PZP_Z. A separate codebook realizability argument is needed to specialize this statement to the constrained SimpleMark or ArcMark state process Zt(m,Vt)Z_t(m,V_t). Theorem 3 (Achievability in the idealized induced DMC model). Assume now that: 1. Qt≡Q_t≡ Q does not depend on t; 2. the feasible set is the same at every time, i.e. ℱt(ε)≡ℱ(ε);F_t( ) ( ); 3. the encoder uses a fixed channel family (PX|Z=z)z∈ℱ(ε) (P_X Z=z )_z ( ) at every time; 4. the induced state process Z1,…,ZnZ_1,…,Z_n is i.i.d. with marginal PZP_Z. Then any rate R<I(Z,X)R<I(Z;X) is achievable with vanishing block error probability. Consequently, any rate R<C(ε):=sup(PX|Z=z)z∈ℱ(ε)I(Z,X)R<C( ):= _ (P_X Z=z )_z ( )I(Z;X) is achievable. Proof. Under the stated assumptions, the induced channel from Zn=(Z1,…,Zn)Z^n=(Z_1,…,Z_n) to Xn=(X1,…,Xn)X^n=(X_1,…,X_n) is a discrete memoryless channel with transition law PXn|Zn(xn∣zn)=∏t=1nPX|Z(xt∣zt).P_X^n Z^n(x^n z^n)= _t=1^nP_X Z(x_t z_t). Fix any channel family in ℱ(ε)F( ) and let the input distribution of Z be the induced marginal PZP_Z. Let R<I(Z,X)R<I(Z;X). Next, construct a random codebook [25] by drawing zn(1),…,zn(2nR)z^n(1),…,z^n(2^nR) independently, each with i.i.d. components distributed according to PZP_Z. To transmit message m, send the corresponding codeword zn(m)z^n(m) through the channel, producing xnx^n according to ∏t=1nPX|Z(xt∣zt(m)). _t=1^nP_X Z(x_t z_t(m)). At the decoder, use jointly typical decoding: declare m m to be the unique index such that (zn(m^),xn)(z^n( m),x^n) is jointly typical. By the standard random-coding theorem for discrete memoryless channels [25], the average probability of error over the random code ensemble tends to zero as n→∞n→∞ whenever R<I(Z,X).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)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∈ℱ(ε) (P_X Z=z )_z ( ) shows that every rate R<C(ε)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)z∈I(Zt,Xt)subject todTV(PXt|Zt=z,Qt)≤ε∀z∈. _ (P_X_t Z_t=z )_z I(Z_t;X_t) to d_TV(P_X_t Z_t=z,Q_t)≤ \ \ ∀ z . B.2 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 Rn≤1n∑t=1nC~t(ε)+1+nRnPe(n)n,R_n≤ 1n _t=1^n C_t( )+ 1+nR_nP_e^(n)n, where C~t(ε):=sup(PXt|Zt=z)z∈ℱt(ε)PZt∈Δ()I(Zt,Xt). C_t( ):= _ subarrayc(P_X_t|Z_t=z)_z _t( )\\ P_Z_t∈ (Z) subarrayI(Z_t;X_t). Thus, to instantiate the theorem concretely, one fixes a base distribution QtQ_t, chooses state-conditioned channels (PXt|Zt=z)z∈ (P_X_t|Z_t=z )_z satisfying dTV(PXt|Zt=z,Qt)≤ε∀z∈,d_TV(P_X_t|Z_t=z,Q_t)≤ ∀ z , and then computes the resulting mutual information I(Zt,Xt)I(Z_t;X_t). 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 =0,1,Q(0)=Q(1)=12,X=\0,1\, Q(0)=Q(1)= 12, and let the state alphabet be =0,1,PZ(0)=PZ(1)=12.Z=\0,1\, P_Z(0)=P_Z(1)= 12. Fix ε∈[0,12] ∈[0, 12] and define the conditional laws PX|Z=0(0)=12+ε,PX|Z=0(1)=12−ε,P_X|Z=0(0)= 12+ , P_X|Z=0(1)= 12- , and PX|Z=1(0)=12−ε,PX|Z=1(1)=12+ε.P_X|Z=1(0)= 12- , P_X|Z=1(1)= 12+ . We verify feasibility: dTV(PX|Z=0,Q)=12(|12+ε−12|+|12−ε−12|)=12(ε+ε)=ε,d_TV(P_X|Z=0,Q)= 12 ( | 12+ - 12 |+ | 12- - 12 | )= 12( + )= , and similarly dTV(PX|Z=1,Q)=ε.d_TV(P_X|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)=12(12+ε)+12(12−ε)=12,P_X(0)= 12 ( 12+ )+ 12 ( 12- )= 12, and similarly PX(1)=12.P_X(1)= 12. Thus X∼Bernoulli(12)X ( 12) and H(X)=1.H(X)=1. Moreover, H(X|Z=0)=h2(12+ε),H(X|Z=1)=h2(12+ε),H(X|Z=0)=h_2 ( 12+ ), H(X|Z=1)=h_2 ( 12+ ), so H(X|Z)=h2(12+ε).H(X|Z)=h_2 ( 12+ ). Therefore I(Z,X)=H(X)−H(X|Z)=1−h2(12+ε).I(Z;X)=H(X)-H(X|Z)=1-h_2 ( 12+ ). Consequently, C~(ε)≥1−h2(12+ε). C( )≥ 1-h_2 ( 12+ ). This gives a completely explicit feasible instantiation of the single-letter quantity appearing in Theorem 2. Numerical specialization of Example 1. If ε=0.1 =0.1, then I(Z,X)=1−h2(0.6)≈0.0290 bits/token.I(Z;X)=1-h_2(0.6)≈ 0.0290 bits/token. If ε=0.2 =0.2, then I(Z,X)=1−h2(0.7)≈0.1187 bits/token.I(Z;X)=1-h_2(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. Small-ε expansion for Example 1. Using the Taylor expansion of binary entropy around 12 12, h2(12+ε)=1−2ln2ε2+o(ε2),h_2 ( 12+ )=1- 2 2 ^2+o( ^2), we obtain I(Z,X)=1−h2(12+ε)=2ln2ε2+o(ε2).I(Z;X)=1-h_2 ( 12+ )= 2 2 ^2+o( ^2). Hence in this binary symmetric perturbation example, the mutual information scales quadratically in ε for small ε . Example 2: exact distortion-freeness forces zero information. Now set ε=0 =0. The per-key TV constraint becomes dTV(PX|Z=z,Q)=0∀z∈.d_TV(P_X|Z=z,Q)=0 ∀ z . Since total variation distance vanishes if and only if the distributions are identical, we obtain PX|Z=z=Q∀z∈.P_X|Z=z=Q ∀ 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).P_X,Z(x,z)=P_Z(z)Q(x)=P_Z(z)P_X(x). Hence I(Z,X)=0.I(Z;X)=0. Thus C~t(0)=0∀t, C_t(0)=0 ∀ t, and Theorem 2 implies that any asymptotically reliable watermarking scheme under exact per-key distortion-freeness must satisfy lim supn→∞Rn≤0. _n→∞R_n≤ 0. This concretely illustrates the paper’s statement that exact per-key distortion-freeness forces zero embedding capacity. Example 3: ternary perturbation. Let =1,2,3,Q(1)=Q(2)=Q(3)=13,X=\1,2,3\, Q(1)=Q(2)=Q(3)= 13, and again let =0,1,PZ(0)=PZ(1)=12.Z=\0,1\, P_Z(0)=P_Z(1)= 12. Fix ε∈[0,13] ∈[0, 13] and define PX|Z=0=(13+ε,13,13−ε),P_X|Z=0= ( 13+ , 13, 13- ), PX|Z=1=(13−ε,13,13+ε).P_X|Z=1= ( 13- , 13, 13+ ). We again verify the TV constraint: dTV(PX|Z=0,Q)=12(|13+ε−13|+|13−13|+|13−ε−13|)=12(ε+0+ε)=ε,d_TV(P_X|Z=0,Q)= 12 ( | 13+ - 13 |+ | 13- 13 |+ | 13- - 13 | )= 12( +0+ )= , and similarly dTV(PX|Z=1,Q)=ε.d_TV(P_X|Z=1,Q)= . Thus the channel family is feasible. Now compute the output marginal: PX=12PX|Z=0+12PX|Z=1=(13,13,13)=Q.P_X= 12P_X|Z=0+ 12P_X|Z=1= ( 13, 13, 13 )=Q. Hence H(X)=log23.H(X)= _23. Also, H(X|Z=0)=H(X|Z=1)=H(13+ε,13,13−ε),H(X|Z=0)=H(X|Z=1)=H ( 13+ , 13, 13- ), so H(X|Z)=H(13+ε,13,13−ε).H(X|Z)=H ( 13+ , 13, 13- ). Therefore I(Z,X)=log23−H(13+ε,13,13−ε).I(Z;X)= _23-H ( 13+ , 13, 13- ). 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)Q_t=(0.5,0.3,0.2) over a three-token vocabulary =x1,x2,x3X=\x_1,x_2,x_3\. Suppose also that the relevant state alphabet at time t is binary: t=z0,z1,PZt(z0)=PZt(z1)=12.Z_t=\z_0,z_1\, P_Z_t(z_0)=P_Z_t(z_1)= 12. For some δ∈[0,minε,0.2],δ∈[0, \ ,0.2\], define PXt|Zt=z0=(0.5+δ,0.3,0.2−δ),P_X_t|Z_t=z_0=(0.5+δ,0.3,0.2-δ), and PXt|Zt=z1=(0.5−δ,0.3,0.2+δ).P_X_t|Z_t=z_1=(0.5-δ,0.3,0.2+δ). Then dTV(PXt|Zt=z0,Qt)=12(|δ|+0+|−δ|)=δ≤ε,d_TV(P_X_t|Z_t=z_0,Q_t)= 12 (|δ|+0+|-δ| )=δ≤ , and similarly dTV(PXt|Zt=z1,Qt)≤ε.d_TV(P_X_t|Z_t=z_1,Q_t)≤ . Hence this is a feasible per-key channel family. The output marginal is PXt=12PXt|Zt=z0+12PXt|Zt=z1=(0.5,0.3,0.2)=Qt.P_X_t= 12P_X_t|Z_t=z_0+ 12P_X_t|Z_t=z_1=(0.5,0.3,0.2)=Q_t. Therefore H(Xt)=H(0.5,0.3,0.2).H(X_t)=H(0.5,0.3,0.2). However, the two conditional entropies are not generally equal. Indeed, H(Xt|Zt)=12H(0.5+δ,0.3,0.2−δ)+12H(0.5−δ,0.3,0.2+δ).H(X_t|Z_t)= 12H(0.5+δ,0.3,0.2-δ)+ 12H(0.5-δ,0.3,0.2+δ). Consequently, the correct mutual information is I(Zt,Xt)=H(0.5,0.3,0.2)−12H(0.5+δ,0.3,0.2−δ)−12H(0.5−δ,0.3,0.2+δ). I(Z_t;X_t)=H(0.5,0.3,0.2)- 12H(0.5+δ,0.3,0.2-δ)- 12H(0.5-δ,0.3,0.2+δ). Thus, for this concrete choice of feasible perturbation, Theorem 2 yields the explicit converse Rn≤1n∑t=1nC~t(ε)+1+nRnPe(n)n,R_n≤ 1n _t=1^n C_t( )+ 1+nR_nP_e^(n)n, with C~t(ε)≥H(0.5,0.3,0.2)−12H(0.5+δ,0.3,0.2−δ)−12H(0.5−δ,0.3,0.2+δ). C_t( )≥ H(0.5,0.3,0.2)- 12H(0.5+δ,0.3,0.2-δ)- 12H(0.5-δ,0.3,0.2+δ). Example 5: using the actual SimpleMark state variable. Recall that the state at time t is Zt=(CM(t)+Vt)modq,Z_t=(C_M(t)+V_t) q, where CM(t)∈qC_M(t) _q is the code symbol at time t and Vt∼Unif(q)V_t (F_q) is the secret key value. To obtain a concrete toy instantiation, take q=2q=2, so Zt=(CM(t)+Vt)mod2Z_t=(C_M(t)+V_t) 2 takes values in =0,1Z=\0,1\, the two vertices of the 11-simplex; write z0:=0z_0:=0 and z1:=1z_1:=1. If the base distribution is Qt=(0.5,0.3,0.2),Q_t=(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+δ),P_X_t|Z_t=z_0=(0.5+δ,0.3,0.2-δ), P_X_t|Z_t=z_1=(0.5-δ,0.3,0.2+δ), where δ≤εδ≤ . Then dTV(PXt|Zt=zi,Qt)≤εd_TV(P_X_t|Z_t=z_i,Q_t)≤ for i∈0,1i∈\0,1\, so this is a valid per-key instantiation in the SimpleMark notation. If PZt(z0)=PZt(z1)=1/2P_Z_t(z_0)=P_Z_t(z_1)=1/2, then the output marginal is again PXt=12PXt|Zt=z0+12PXt|Zt=z1=Qt.P_X_t= 12P_X_t|Z_t=z_0+ 12P_X_t|Z_t=z_1=Q_t. Therefore H(Xt)=H(0.5,0.3,0.2),H(X_t)=H(0.5,0.3,0.2), while H(Xt|Zt)=12H(0.5+δ,0.3,0.2−δ)+12H(0.5−δ,0.3,0.2+δ).H(X_t|Z_t)= 12H(0.5+δ,0.3,0.2-δ)+ 12H(0.5-δ,0.3,0.2+δ). Hence the correct per-time mutual information is I(Zt,Xt)=H(0.5,0.3,0.2)−12H(0.5+δ,0.3,0.2−δ)−12H(0.5−δ,0.3,0.2+δ). I(Z_t;X_t)=H(0.5,0.3,0.2)- 12H(0.5+δ,0.3,0.2-δ)- 12H(0.5-δ,0.3,0.2+δ). Thus Theorem 2 says that any asymptotically reliable scheme built from such per-time perturbations must satisfy lim supn→∞Rn≤lim supn→∞1n∑t=1nC~t(ε), _n→∞R_n≤ _n→∞ 1n _t=1^n C_t( ), and the displayed quantity above gives an explicit feasible single-letter mutual information value that lower bounds C~t(ε) C_t( ). Interpretation. These examples show concretely how Theorem 2 should be used in practice. One fixes a base next-token distribution QtQ_t, constructs feasible state-conditioned perturbations lying inside the total variation ball of radius ε around QtQ_t, computes the induced single-letter mutual information I(Zt,Xt)I(Z_t;X_t), 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 → 0, every feasible state-conditioned law collapses back to QtQ_t, and the mutual information necessarily goes to zero. Instantiating RnR_n and Pe(n)P_e^(n) in Theorem 2. Recall that in Theorem 2, if the message set has size |ℳ|=2k,|M|=2^k, and the watermark spans n time steps, then the embedding rate is Rn=knR_n= kn bits per token. Moreover, for a decoder producing an estimate M M from the observation (X1:n,V1:n)(X_1:n,V_1:n), the block error probability is Pe(n):=Pr[M^≠M].P_e^(n):= [ M≠ 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=1k=1 and n=1n=1. Consider the binary construction =0,1,=0,1,PZ(0)=PZ(1)=12,X=\0,1\, =\0,1\, P_Z(0)=P_Z(1)= 12, with conditional laws PX|Z=0(0)=12+ε,PX|Z=0(1)=12−ε,P_X|Z=0(0)= 12+ , P_X|Z=0(1)= 12- , PX|Z=1(0)=12−ε,PX|Z=1(1)=12+ε.P_X|Z=1(0)= 12- , P_X|Z=1(1)= 12+ . Suppose we embed one bit, so that M∈0,1,k=1,M∈\0,1\, k=1, and we use a single time step: n=1.n=1. Then R1=kn=1R_1= kn=1 bit per token. Assume that the state is identified with the message, i.e. Z=MZ=M, and let the decoder be the maximum-likelihood decoder M^(x)=0,x=0,1,x=1. M(x)= cases0,&x=0,\\ 1,&x=1. cases Then the block error probability is Pe(1)=Pr[M^≠M].P_e^(1)= [ M≠ M]. Since the decoder makes an error exactly when the output flips relative to the more likely symbol under the true message, Pe(1)=12Pr[M^≠0∣M=0]+12Pr[M^≠1∣M=1].P_e^(1)= 12\, [ M≠ 0 M=0]+ 12\, [ M≠ 1 M=1]. Now Pr[M^≠0∣M=0]=Pr[X=1∣Z=0]=12−ε, [ M≠ 0 M=0]= [X=1 Z=0]= 12- , and similarly Pr[M^≠1∣M=1]=Pr[X=0∣Z=1]=12−ε. [ M≠ 1 M=1]= [X=0 Z=1]= 12- . Therefore Pe(1)=12−ε.P_e^(1)= 12- . So in this one-shot example, R1=1,Pe(1)=12−ε.R_1=1, P_e^(1)= 12- . This illustrates that at blocklength 11, the decoder error remains large unless ε is quite large. Example 2: repetition over n time steps with k=1k=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=1n.M∈\0,1\, k=1, R_n= 1n. Conditioned on M=0M=0, the outputs X1,…,XnX_1,…,X_n are i.i.d. with Pr[Xt=0∣M=0]=12+ε,Pr[Xt=1∣M=0]=12−ε. [X_t=0 M=0]= 12+ , [X_t=1 M=0]= 12- . Conditioned on M=1M=1, the outputs are i.i.d. with the roles of 00 and 11 reversed. Let the decoder use majority vote: M^=0,∑t=1nXt=1<n2,1,∑t=1nXt=1>n2. M= cases0,& _t=1^n1\X_t=1\< n2,\\ 1,& _t=1^n1\X_t=1\> n2. cases (Without loss of generality, assume that n is odd.) Then the block error probability is Pe(n)=Pr[M^≠M].P_e^(n)= [ M≠ M]. By symmetry, Pe(n)=Pr[∑t=1nXt=1≥n2|M=0].P_e^(n)= \! [ _t=1^n1\X_t=1\≥ n2\, |\,M=0 ]. Since under M=0M=0, ∑t=1nXt=1∼Bin(n,12−ε), _t=1^n1\X_t=1\ \! (n, 12- ), we obtain Pe(n)=∑j=⌈n/2⌉n(nj)(12−ε)j(12+ε)n−j.P_e^(n)= _j= n/2 ^n nj ( 12- )^j ( 12+ )^n-j. Thus in this repetition construction, Rn=1n,R_n= 1n, while Pe(n)=∑j=⌈n/2⌉n(nj)(12−ε)j(12+ε)n−j.P_e^(n)= _j= n/2 ^n nj ( 12- )^j ( 12+ )^n-j. As n→∞n→∞, this error probability tends to zero for every fixed ε>0 >0, whereas the rate Rn=1/nR_n=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=2k=2 bits using n=2n=2 time steps. Then the message set has size |ℳ|=22=4,|M|=2^2=4, for example ℳ=00,01,10,11.M=\00,01,10,11\. The embedding rate is therefore R2=kn=22=1R_2= kn= 22=1 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: M=(M1,M2),Xt∼PX|Z=Mt.M=(M_1,M_2), X_t P_X|Z=M_t. Let the decoder decode each coordinate separately via M^t=0,Xt=0,1,Xt=1. M_t= cases0,&X_t=0,\\ 1,&X_t=1. cases Then the overall decoded message is M^=(M^1,M^2). M=( M_1, M_2). Since an error occurs if at least one of the two coordinates is decoded incorrectly, and each coordinate has error probability 12−ε, 12- , the block error probability is Pe(2)=1−Pr[M^1=M1 and M^2=M2]=1−(12+ε)2.P_e^(2)=1- [ M_1=M_1 and M_2=M_2]=1- ( 12+ )^2. Equivalently, Pe(2)=1−(1−(12−ε))2.P_e^(2)=1- (1- ( 12- ) )^2. So in this example, R2=1,Pe(2)=1−(12+ε)2.R_2=1, P_e^(2)=1- ( 12+ )^2. Example 4: general finite-blocklength instantiation. More generally, if one chooses: • a blocklength n, • a message set ℳM with |ℳ|=2k|M|=2^k, • a feasible family of per-time channels (PXt|Zt=z)z∈, (P_X_t|Z_t=z )_z , • and a decoder M^=M^(X1:n,V1:n), M= M(X_1:n,V_1:n), then the two quantities in Theorem 2 are instantiated as Rn=knR_n= kn and Pe(n)=Pr[M^(X1:n,V1:n)≠M].P_e^(n)= [ M(X_1:n,V_1:n)≠ M]. For instance, if k=100k=100 bits are embedded over n=1000n=1000 tokens, then Rn=1001000=0.1R_n= 1001000=0.1 bits per token. If the chosen encoder–decoder pair achieves a block error probability of, say, Pe(n)=10−3,P_e^(n)=10^-3, then the finite-n converse in Theorem 2 becomes 0.1≤11000∑t=11000C~t(ε)+1+1000⋅0.1⋅10−31000.0.1≤ 11000 _t=1^1000 C_t( )+ 1+1000· 0.1· 10^-31000. That is, 0.1≤11000∑t=11000C~t(ε)+0.0011.0.1≤ 11000 _t=1^1000 C_t( )+0.0011. Equivalently, 11000∑t=11000C~t(ε)≥0.0989. 11000 _t=1^1000 C_t( )≥ 0.0989. So this gives a concrete numerical reading of Theorem 2: to support an embedding rate of 0.10.1 bits per token at block error probability 10−310^-3, the average constrained single-letter mutual information must be at least approximately 0.09890.0989. Interpretation. In short, RnR_n is instantiated simply by choosing how many bits k are embedded across how many time steps n, while Pe(n)P_e^(n) is instantiated by fixing a decoder and computing its block error probability under the induced joint law of (M,X1:n,V1:n)(M,X_1:n,V_1:n). Theorem 2 then relates these concrete finite-blocklength quantities to the average single-letter constrained capacities C~t(ε) C_t( ). 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∈qnv_1:n _q^n. Let P(m,v1:n)X1:n:=PX1:n∣M=m,V1:n=v1:nP^(m,v_1:n)_X_1:n:=P_X_1:n M=m,V_1:n=v_1:n denote the watermarked sequence law, and let Q(n)X1:n:=∏t=1nQtQ^(n)_X_1:n:= _t=1^nQ_t denote the reference product law formed from the base next-token distributions. Assume that, conditioned on (M,V1:n)=(m,v1:n)(M,V_1:n)=(m,v_1:n), the watermarked sequence law factors as PX1:n(m,v1:n)(x1:n)=∏t=1nPXt∣M=m,Vt=vt(xt),P^(m,v_1:n)_X_1:n(x_1:n)= _t=1^nP_X_t M=m,V_t=v_t(x_t), and that for every t∈[1:n]t∈[1:n], dTV(PXt∣M=m,Vt=vt,Qt)≤εt.d_TV\! (P_X_t M=m,V_t=v_t,\,Q_t )≤ _t. Then dTV(PX1:n(m,v1:n),QX1:n(n))≤1−∏t=1n(1−εt).d_TV\! (P^(m,v_1:n)_X_1:n,\,Q^(n)_X_1:n )≤ 1- _t=1^n(1- _t). In particular, if εt≤ε _t≤ for all t, then dTV(PX1:n(m,v1:n),QX1:n(n))≤1−(1−ε)n≤nε.d_TV\! (P^(m,v_1:n)_X_1:n,\,Q^(n)_X_1:n )≤ 1-(1- )^n≤ n . Proof. For each t, write Pt:=PXt∣M=m,Vt=vt,Qt:=Qt.P_t:=P_X_t M=m,V_t=v_t, Q_t:=Q_t. By assumption, P(m,v1:n)X1:n=⨂t=1nPt,Q(n)X1:n=⨂t=1nQt.P^(m,v_1:n)_X_1:n= _t=1^nP_t, Q^(n)_X_1:n= _t=1^nQ_t. For each t, by the coupling characterization of total variation distance, there exists a coupling πt∈Π(Pt,Qt) _t∈ (P_t,Q_t) of random variables (Yt,Zt)(Y_t,Z_t) such that Pr[Yt≠Zt]=dTV(Pt,Qt)≤εt. [Y_t≠ Z_t]=d_TV(P_t,Q_t)≤ _t. Take these couplings independently across t, producing a joint coupling of Y1:n=(Y1,…,Yn)∼⨂t=1nPtY_1:n=(Y_1,…,Y_n) _t=1^nP_t and Z1:n=(Z1,…,Zn)∼⨂t=1nQt.Z_1:n=(Z_1,…,Z_n) _t=1^nQ_t. Under this product coupling, Pr[Y1:n=Z1:n]=∏t=1nPr[Yt=Zt]=∏t=1n(1−Pr[Yt≠Zt])≥∏t=1n(1−εt). [Y_1:n=Z_1:n]= _t=1^n [Y_t=Z_t]= _t=1^n (1- [Y_t≠ Z_t] )≥ _t=1^n(1- _t). Therefore, Pr[Y1:n≠Z1:n]=1−Pr[Y1:n=Z1:n]≤1−∏t=1n(1−εt). [Y_1:n≠ Z_1:n]=1- [Y_1:n=Z_1:n]≤ 1- _t=1^n(1- _t). Applying again the coupling characterization of total variation distance gives dTV(⨂t=1nPt,⨂t=1nQt)≤Pr[Y1:n≠Z1:n]≤1−∏t=1n(1−εt).d_TV\! ( _t=1^nP_t,\ _t=1^nQ_t )≤ [Y_1:n≠ Z_1:n]≤ 1- _t=1^n(1- _t). This proves the first claim. For the second claim, if εt≤ε _t≤ for all t, then 1−∏t=1n(1−εt)≤1−(1−ε)n.1- _t=1^n(1- _t)≤ 1-(1- )^n. Finally, Bernoulli’s inequality implies (1−ε)n≥1−nεfor ε∈[0,1],(1- )^n≥ 1-n ∈[0,1], and hence 1−(1−ε)n≤nε.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.d_TV (P_X_t M=m,V_t=v,Q_t )≤ ∀ t,\ ∀ m,\ ∀ v. Then for every message m and every realized side-information sequence v1:nv_1:n, dTV(PX1:n∣M=m,V1:n=v1:n,∏t=1nQt)≤1−(1−ε)n≤nε.d_TV\! (P_X_1:n M=m,V_1:n=v_1:n,\ _t=1^nQ_t )≤ 1-(1- )^n≤ n . Proof. Apply Lemma 1 with εt=ε _t= for all t. ∎ Appendix C Distortion-Freeness: Per-Key vs. On-Average In ArcMark [12], 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, S[PX|S,M=m]=QX∀m,E_S\! [P_X S,M=m ]=Q_X ∀ m, does not imply per-key perfect distortion-freeness, namely PX∣S=s,M=m=QX∀s,m.P_X S=s,M=m=Q_X ∀ s,m. Proof. Consider the binary alphabet =0,1X=\0,1\ and let QX(0)=QX(1)=12Q_X(0)=Q_X(1)= 12. Let the secret key S be uniform on 0,1\0,1\: Pr[S=0]=Pr[S=1]=12. [S=0]= [S=1]= 12. For every message m, define PX∣S=0,M=m(0)=1,PX∣S=0,M=m(1)=0,P_X S=0,M=m(0)=1,P_X S=0,M=m(1)=0, and PX∣S=1,M=m(0)=0,PX∣S=1,M=m(1)=1.P_X S=1,M=m(0)=0,P_X S=1,M=m(1)=1. Then S[PX|S,M=m(0)]=12⋅1+12⋅0=12=QX(0),E_S\! [P_X S,M=m(0) ]= 12· 1+ 12· 0= 12=Q_X(0), and similarly S[PX|S,M=m(1)]=12⋅0+12⋅1=12=QX(1).E_S\! [P_X S,M=m(1) ]= 12· 0+ 12· 1= 12=Q_X(1). Hence S[PX|S,M=m]=QX∀m.E_S\! [P_X S,M=m ]=Q_X ∀ m. However, PX∣S=0,M=m=δ0≠QX,PX∣S=1,M=m=δ1≠QX.P_X S=0,M=m= _0≠ Q_X,P_X S=1,M=m= _1≠ Q_X. Thus per-key perfect distortion-freeness fails. ∎ 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 <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 ==1,…,NX=V=\1,…,N\, and let Q(x)=1N,x∈.Q(x)= 1N,x . Let the secret key V∼Unif()V (V). For each realized key value v∈v , define the keyed output distribution PX|V=v=δv.P_X|V=v= _v. Then the following holds: 1. The scheme is perfectly distortion-free on average over the key: V[PX|V]=Q.E_V[P_X|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−1N.d_TV(P_X|V=v,Q)=d_TV( _v,Q)=1- 1N. 3. If the detector observes both X and the realized key V, then the null law H0:V∼Unif(),X∼Q,X⟂VH_0: V (V), X Q, X V and the watermarked law H1:V∼Unif(),X=VH_1: V (V), X=V have total variation distance dTV(PX,VH1,PX,VH0)=1−1N.d_TV(P_X,V^H_1,P_X,V^H_0)=1- 1N. In particular, the test Φ(x,v)=x=v (x,v)=1\x=v\ satisfies ℙH1[Φ(X,V)=1]=1,ℙH0[Φ(X,V)=1]=1N,P_H_1[ (X,V)=1]=1, _H_0[ (X,V)=1]= 1N, and hence has distinguishing advantage 1−1/N1-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 <1, choosing N large enough so that 1−1N>ε1- 1N> gives an average-key perfectly distortion-free scheme whose keyed detection advantage exceeds the per-key TV budget ε . Proof. First, for each x∈x , V[PX|V(x)]=1N∑v=1Nδv(x)=1N=Q(x).E_V[P_X|V(x)]= 1N _v=1^N _v(x)= 1N=Q(x). Therefore V[PX|V]=Q,E_V[P_X|V]=Q, so the scheme is perfectly distortion-free on average over the key. Next, fix v∈v . Since PX|V=v=δvP_X|V=v= _v and Q is uniform, dTV(δv,Q)=12∑x=1N|δv(x)−Q(x)|.d_TV( _v,Q)= 12 _x=1^N| _v(x)-Q(x)|. The term x=vx=v contributes |1−1N|=1−1N, |1- 1N |=1- 1N, while the remaining N−1N-1 terms contribute ∑x≠v|0−1N|=N−1N=1−1N. _x≠ v |0- 1N |= N-1N=1- 1N. Thus dTV(δv,Q)=12(1−1N+1−1N)=1−1N.d_TV( _v,Q)= 12 (1- 1N+1- 1N )=1- 1N. It remains to compute the joint distinguishability: Under H1H_1, PX,VH1(x,v)=1N,x=v,0,x≠v.P_X,V^H_1(x,v)= cases 1N,&x=v,\\ 0,&x≠ v. cases Under H0H_0, X and V are independent uniforms, so PX,VH0(x,v)=1N2∀x,v.P_X,V^H_0(x,v)= 1N^2 ∀ x,v. Therefore dTV(PX,VH1,PX,VH0)=12∑v=1N∑x=1N|PX,VH1(x,v)−PX,VH0(x,v)|.d_TV(P_X,V^H_1,P_X,V^H_0)= 12 _v=1^N _x=1^N |P_X,V^H_1(x,v)-P_X,V^H_0(x,v) |. For the N diagonal pairs x=vx=v, the absolute difference is |1N−1N2|=N−1N2. | 1N- 1N^2 |= N-1N^2. For the N2−N^2-N off-diagonal pairs x≠vx≠ v, the absolute difference is |0−1N2|=1N2. |0- 1N^2 |= 1N^2. Hence dTV(PX,VH1,PX,VH0)=12[N⋅N−1N2+(N2−N)⋅1N2].d_TV(P_X,V^H_1,P_X,V^H_0)= 12 [N· N-1N^2+(N^2-N)· 1N^2 ]. Simplifying, dTV(PX,VH1,PX,VH0)=12[N−1N+N−1N]=1−1N.d_TV(P_X,V^H_1,P_X,V^H_0)= 12 [ N-1N+ N-1N ]=1- 1N. Finally, for the test Φ(x,v)=x=v, (x,v)=1\x=v\, we have under H1H_1 that X=VX=V always, so ℙH1[Φ(X,V)=1]=1.P_H_1[ (X,V)=1]=1. Under H0H_0, X and V are independent uniform random variables on 1,…,N\1,…,N\, so ℙH0[Φ(X,V)=1]=∑v=1Nℙ[V=v]ℙ[X=v]=N⋅1N⋅1N=1N.P_H_0[ (X,V)=1]= _v=1^NP[V=v]P[X=v]=N· 1N· 1N= 1N. Thus the test has distinguishing advantage 1−1N.1- 1N. This proves the proposition. ∎ Appendix 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. Figure 5: Message recovery for a variable length prefix of a 500-1000 token sequence at various ε budgets. 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 =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. Scheme GSM8K (n=300n=300) GPQA-D (n=198n=198) LCB (n=300n=300) 3-bit payload SimpleMark TV (ε=0.05 =0.05, αmax=1500 _ =1500) 253 58 62 SimpleMark KL (ε=0.05 =0.05, αmax=1500 _ =1500) 249 42 54 BiMark 251 45 58 ArcMark 249 54 65 Unwatermarked 249 56 60 8-bit payload SimpleMark TV (ε=0.05 =0.05, αmax=1500 _ =1500) 252 55 60 SimpleMark KL (ε=0.05 =0.05, αmax=1500 _ =1500) 247 61 62 BiMark 248 53 55 ArcMark 259 56 57 Unwatermarked 249 56 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=53q=53, TV or KL ε=0.05 =0.05, cap αmax=1500 _ =1500), BiMark, ArcMark, and no watermark. 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. Figure 6: Substitution for a variable percentage of tokens in a 300 token sequence. For ε∈0.05,0.15 ∈\0.05,0.15\, and context hashing window h=2,3h=2,3. SimpleMark is decently robust to substitution edit attacks. 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−210^-2, 10−610^-6, and 10−1210^-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 ε . 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. 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 _ ∈\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. Figure 8: Message recovery for a variable length prefix of a 300 token sequence for q=29,53q=\29,53\ at various ε budgets. Figure 9: Perplexity with different parameters for q=29,53q=\29,53\. Both remain close to the unwatermarked baselines. Figure 10: Reasoning for SimpleMark under the different parameter sizes and αmax _ .