We study multi-bit watermarking for data generated by stochastic processes, where a hidden message is embedded during sampling and must be decodable by an authorized detector that possesses side information unavailable to unauthorized observers. In high-stakes deployments, a practical watermark must simultaneously control false alarms, preserve generation quality without distorting the output distribution, and support reliable multi-bit decoding. Satisfying all three goals at once inevitably creates fundamental trade-offs. We formulate watermark embedding as a distributional information-embedding problem and watermark detection as a multiple-hypothesis testing problem under distortion and rate constraints, leading to four fundamental metrics: false-alarm probability, detection error probability, distortion, and information rate. Within this information-theoretic framework, we derive matched converse and achievability bounds that characterize the optimal trade-offs and provide scheme-agnostic benchmarks for any watermarking method. For stationary ergodic stochastic processes, we further obtain matched asymptotic limits and connect them to the finite-sample regime. Finally, we present a reference watermarking construction satisfying our assumptions and empirically illustrating the predicted trade-offs.
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.Reviewer_ZnuYOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary
This paper studies multibit watermarking, the watermark is formulated as a auxiliary stocastic process on the messages. The paper focus on four aspects, false alarm probability, detection error, distortion level and information rate. The main theorem estabilished the finite length errors with regards to average and worst case, the results showed that the two values coincide.
Thm 2 discusses random grouping, which achieves the optimal error probability and Thm 3 on deterministic grouping which has a residual error.
Thm 4 bounds the information rate asymtotically and demonstrated achievability.
The paper validated using a finite-state stationary ergodic Markov model. The specification of the underlying model is unclear. Figures demonstrated the tradeoff and the residual mentioned in Thm 3.
Critical strengths
1.Thm 1 proved that the minimum average error probability is equal to minimax per-message case. This shows that there exists a watermark that has uniform guarantee over all messages.
Critical weaknesses
1.The problem setting and theorem stucture follows previous work, for example https://arxiv.org/abs/2604.08759 investigates a similar problem with d=0 and provided the same proof sturcture by finding a converse bound for error probability and final proof by achievability.
2.Lack of emperical proof, the paper includes a single experiment conducted on a Markov chain which is unspecified. Additional experiments would further strengthen the credibility. More over, with watermark deployment entering LLMs, a LLM involved experiment would be great.
Questions for authors
Besides the weakness mentioned above,
For construction part in Thm 2, decoder is designed based on a latin square. How can we generate this for a LLM, which admits a autoregressive nature and generates indefinite length of output? Does the grouping process involve partitioning of VT where V is the vocabulary?
Decoding requires ϕ∗, which is related to the original distribution. Can this requirement be fulfilled in reality?
The paper reviews the fundamental trade-offs in multi-bit watermarking of stochastic processes. The main goal is to characterize the relationship between false-alarm probability, detection error, distributional distortion, and information rate.
Critical strengths
The paper addresses an interesting theoretical problem and provides a general information-theoretic formulation of multi-bit watermarking.
The comparison between randomized and deterministic grouping, including the analysis of residual error, is particularly interesting.
Critical weaknesses
Huang et al. (2026, Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints) already derive an optimal detection-error expression equivalent to Equation (1) in the zero-distortion case. Since a stochastic sequence of fixed length can be treated as a single random variable over a larger alphabet, it is not clear which parts of the finite-sample characterization require genuinely new arguments for stochastic processes.
The numerical results illustrate the theoretical trade-offs, but the evaluation is restricted to a single type of finite-state Markov process.
The computational feasibility of proposed grouping-based constructions remains unclear.
Questions for authors
What are the main theoretical differences between Theorem 1 and the optimal multi-bit watermarking results of Huang et al. (2026)?
Theorem 4 claims vanishing decoding error for m≤αexp(THQ(X)) under zero distortion. However, consider an i.i.d. Bernoulli(0.8) source with α=0.01 and mT=⌊αexp(THQ(X))⌋. Applying Equation (1), the optimal detection-error lower bound appears to approach 0.5 rather than zero. Could the authors clarify how this agrees with Theorem 4?
Could the authors provide numerical experiments for several different source distributions, including highly nonuniform or strongly correlated processes?
What is the computational complexity of finding the optimal deterministic grouping? Is there an efficient approximation for large sequence spaces?
This paper studies embedding a message M∈[m] into the length-T output XT of a stochastic process, where a detector holding side information ζT jointly decides whether a watermark is present and recovers the message. Under secrecy of the per-message marginals of the output and of the side information, M⊥XT and M⊥ζT, the paper analyzes the relationship among the worst-case false-alarm probability, the distortion of the generating distribution, the average or maximum per-message decoding error, and the information rate.
As the optimal finite-length error, the paper presents
\sum_{x^T}\left(P_{X^T}(x^T)-\frac{\alpha}{m}\right)_+ ,$$
together with a closed form for TV distortion, and proposes achievability constructions based on randomized and deterministic grouping and Latin squares. It further claims that, for stationary ergodic processes, the maximum distortion-free information rate equals the entropy rate, and that the error decays as $\exp[-\Omega(\sqrt T)]$ at a specific message-set size. Validation consists of numerically computing the theoretical curves for finite-state stationary ergodic Markov models.
Critical strengths
S1. The paper formulates an important design question within a single information-theoretic model. It jointly treats the worst-case false alarm, distribution distortion, information rate, and decoding error, and it requires message independence of both the output and the side information, ruling out the degenerate solution of sending the message directly through the auxiliary channel. The goal of controlling false alarms even for sources with different generating distributions is clear, giving the work value as a theoretical benchmark. However, since the model does not constrain a separate key or shared-randomness budget, key-reuse security, or the resources of a causal online implementation, its conclusions should not be extended to efficiency, multi-use security, or editing-attack guarantees of actual generators.
S2. The finite-length converse and the TV mass-transport interpretation are verifiable and useful. In Appendix C, pp. 15–16, substituting point masses into the worst-case false-alarm constraint shows that the total false-alarm budget of each output is at most α; combined with identical per-message output marginals, the average correct-decoding mass at each xT is at most min{PXT(xT),α/m}. The maximum per-message error cannot be smaller than the average error, so it obeys the same lower bound. The TV optimization on pp. 17–18 can be understood as moving mass above the threshold into the empty space below it. If the achievability is corrected, this lower bound remains an independent design criterion.
Critical weaknesses
W1. The finite-length achievability construction does not match the converse, and its feasibility condition and shared-key model require correction.
The decoder in §3.2 Step 3 (p. 7) and Appendix D.2 (p. 23) outputs a message only in heavy groups, so the actual error is βj=1−∣Gα/m∣α/m, and the mass of low groups must be added to the overflow sum in Eq. (13) (p. 24). Consider T=1, d=0, Q=(.60,.20,.15,.05), α=.60, m=2, K=3. The optimal group masses of (P3) are (.60,.35,.05). The condition of Theorem 3, .40≥(1−1/2)⋅.60, holds, but while the lower bound of Eq. (1) is .30 and the residual term .05 gives an upper bound of .35, the actual decoder error is .40. This counterexample is limited to the admissible fixed-K=3 construction and does not imply impossibility for all numbers of groups or all deterministic decoders.
The feasibility condition is also insufficient. For T=1, d=0, Q=Unif(4), m=3, α=.9, the threshold is .3, Sα/m=∅, and the stated total-mass condition 1≥.9 holds. However, three heavy groups cannot be formed from four atoms of mass .25, so the feasible set of (P3) is empty. The error formula should account for low-group mass, and the actual existence condition for a deterministic partition with indivisible atoms should be added.
In the randomized construction, combining the independent kernel ϕ(k∣xT)=pk on p. 19 with the averaged encoder PζT∣XT,M(z∣x,j)=∑kPζT∣G,M(z∣k,j)ψ(k∣x) on p. 21 makes the right-hand side equal to the same PζT(z) for all x,j.
For example, Q=(.60,.30,.10),d=0,α=.5,m=2 satisfies m<=m^* with a target error of .4, but in an experiment that observes only the pair under the displayed averaged encoder, both alternatives coincide with the null hypothesis, and the average error is at least .75. I acknowledge the manuscript's mentions of a shared key or seed (pp. 4, 6, 21). The issue is how the computation on p. 21, which keeps only the terms with GK(x)=k while retaining the key-averaged encoder, connects to the full joint law. This does not imply impossibility for all constructions that include a shared key. The paper should jointly define and prove PK,XT,ζT∣M, secrecy of the full side information I(M;K,ζT)=0, the null hypothesis, the worst-case false alarm, and the decoding probability. The equality in Theorem 1 and the m≤m∗ condition in Theorem 2 should also be reconciled. The phrase "price of determinism" on p. 7 should be narrowed to distinguish the limits of general deterministic decoders from the gap of this particular grouping structure.
W2. There is an i.i.d. counterexample to the boundary achievability in Theorem 4, and the error decay rate for general stationary ergodic processes is not proven.
Theorem 4 (p. 8) claims that the error vanishes for distortion-free watermarking if m≤αexp(THQ(X)). Take an i.i.d. Bernoulli process with success probability 0<p<1, p=1/2, fixed α∈(0,1), entropy h in nats, mT=⌊αeTh⌋, and ST=−logQXT(XT). By the manuscript's own converse,
βˉT≥EQ[(1−exp{ST−log(mT/α)})+]⟶21.
Since log(mT/α)=Th+o(1) and the information variance is positive, this limit follows from the central limit theorem with upper and lower probability bounds using a margin cT→∞, cT=o(T). Even with the theorem's false-alarm slack αT=α+exp[−Ω(T)], log(mT/αT)=Th+o(1), so the same lower bound remains. Exact binomial summation with p=.2, α=.1 gives a lower bound of approximately .4284 at T=100 and .4769 at T=1000. The claim that the entropy rate is the supremum of first-order achievable rates should be separated from the claim that the error vanishes at this boundary message-set size, and the required finite-length slack should be stated.
The Chernoff argument in Appendix F, p. 26, does not justify exp[−Ω(Tη2)] concentration of the block information for arbitrary stationary ergodic processes. The issue is not the independence requirement of Chernoff itself, but the uniform control of the T-scaling of the block moment generating function and the Taylor remainder. The AEP also does not automatically give a convergence rate of η=T−1/4 from fixed-width convergence. The explanation on p. 25 of combining probabilities that are similar in exponential order via a Latin square does not by itself guarantee exactly identical per-message marginals. Exact secrecy achievability for R<h and a concrete error decay rate under additional process assumptions should be proven separately. I acknowledge the Fano upper bound for a fixed stationary ergodic P, but the equality in Appendix E, p. 25, which replaces the limit of the maximum over arbitrary finite-block PMFs with the maximum entropy rate over all stationary ergodic processes, requires separate justification. For positive distortion, only a converse is given, so the scope of the summary "matched" should be adjusted.
Questions for authors
Q1. Correction in response to the counterexamples. Can you provide an error formula and a sufficient condition that resolve the gap between the upper bound .35 and the actual error .40 for Q=(.60,.20,.15,.05), α=.60, m=2, K=3, and the infeasibility for Unif(4), α=.9, m=3? If Figure 1c–d relies on Eq. (13), please show the actual error of the corrected construction computed independently.
Q2. Model clarification and proof. What is the PK,XT,ζT∣M corresponding to the independent kernel and the encoder and decoder on p. 21? Please jointly establish secrecy of the full side information, the null hypothesis, the worst-case false alarm, and the actual decoding probability, and explain how the information loss is resolved in the example Q=(.60,.30,.10) above when only the pair under the averaged encoder is observed.
Q3. Correction of the asymptotic theorem. How is Theorem 4 compatible with the non-uniform i.i.d. boundary counterexample and the average-error lower bound of 1/2 that holds even with the allowed false-alarm slack? Can you state the intended rate slack and additional process assumptions, and prove exact marginal secrecy and the claimed error decay rate under those conditions?
Q4. Clarification of the scope of contribution. What new theorems does the paper provide relative to the distortion-free optimality theorem of Huang et al. (2026) and the distributional embedding theory of He et al. v2 (2025)? Please state, theorem by theorem, the increment of the TV closed form, the achievability constructions, and the stationary ergodic analysis, as well as the grouping restriction relative to general deterministic decoders. If the manuscript is a later version of He et al., explaining that relationship is sufficient.
From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.