- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper presents TrellisMark, a multi-bit LLM watermarking method that couples neighboring payload symbols through overlapping local windows. The resulting local-score structure forms a trellis, allowing the detector to recover the maximum-score payload with Viterbi decoding rather than enumerating the full message space. The method further uses multiple mapping heads and an online watermark-strength allocation policy that distributes a cumulative KL-divergence budget according to the current trellis recovery state. The paper provides conditional finite-length recovery and online-allocation regret analyses, and evaluates the method against several multi-bit watermarking baselines across payload lengths, datasets, language models, and text-editing attacks.
Critical strengths
The paper identifies a meaningful limitation of existing multi-bit LLM watermarking methods where position-wise schemes fragment evidence across payload symbols, whereas message-wise schemes can make exact decoding intractable. TrellisMark provides a principled intermediate design based on overlapping local payload windows.
Critical weaknesses
-
The finite-length recovery theorem relies on an unverified and potentially vacuous margin assumption. Assumption 1 requires that, simultaneously for every competing payload , the cumulative expected score advantage satisfies . This is precisely the property needed for the correct payload to dominate its competitors. The paper does not derive this condition from the exponential-tilting sampler in Eq. 5, the base-model token distribution, the multi-head construction, or the online strength policy. Thus, the theorem shows how overlap amplifies an already-existing margin, rather than why the proposed method creates such a margin. Moreover, the final bound in Theorem 1 depends on the unquantified quantities , , and . The paper neither estimates these quantities empirically nor verifies Assumption 1 across payload lengths, models, strengths, or window widths. If is small or is non-negligible, the derived bound may provide little information, making it difficult to assess whether the theorem explains the empirical gains.
-
The window-width ablation in Figure 4b provides useful initial evidence that local overlap can improve recovery, but it does not fully isolate the effect of coupling. In particular, the figure reports recovery only, without the corresponding KL divergence or perplexity. Could the authors provide a matched-KL recovery comparison, or recovery--quality frontiers, for versus ? Changing the window width may alter the strength--distortion relation, so higher recovery at a fixed setting does not establish an improvement at equal distortion.
It is also unclear whether , the target margin , the dual-update parameters, and other allocation hyperparameters were separately tuned for each window width. Were these parameters held fixed across the ablation, or optimized independently? This distinction matters because changing changes not only overlap but also the local-assignment space, score geometry, and behavior of the online utility.
Finally, is a useful no-overlap control, but it may not be a matched-redundancy control. A wider window causes each payload symbol to participate in more local factors. Could the authors compare against a non-overlapping scheme given a comparable redundancy or measurement budget, e.g., repeated measurements of individual positions or a matched-rate ECC baseline?
-
The finite-length analysis in Appendix C derives a projection-separation term that scales with the number of heads . However, this term only counts the number of head-level mappings for which the true and competing payloads predict different target colors; it does not establish that the sampled token provides more evidence for the true payload than for the competitor. In Eq. 5, a single token is sampled according to the true payload's aggregate match reward, while a competing payload may still receive match scores on other heads. Consequently, the head-level score contributions are jointly induced by the same selected token rather than being independent observations. To establish that adding heads improves recovery, the analysis would need to show that the resulting pairwise target--competitor score advantage grows relative to its sampling fluctuations as increases. Instead, the argument absorbs the required per-separating-projection target--competitor score advantage into the assumed constant . The analysis does not show that remains positive or stable as changes; it may depend on the joint token-color distribution, , the sampling strength, and correlations induced by selecting one token. Therefore, the theory does not establish that adding heads improves recovery, although the ablation suggests this empirically for the tested configuration.
-
The hindsight benchmark fixes the realized sequence of opportunities . However, changing an earlier strength changes the sampled token and therefore future contexts, mappings, recovery margins, and future opportunities. Hence, the result is not regret against a counterfactual clairvoyant policy operating in the same autoregressive environment. Moreover, the optimized reward is a surrogate: measures an increase in the true payload's match reward, not the actual pairwise target--competitor score margin that determines exact recovery.
Questions for authors
- Eq. 7 seems to miss "r", which should be \sum_{j=1}^{N+r}\Phi_j(s'_{j-r:j})
- The main text states Theorem 1 (Finite-length recovery under local coupling), while Appendix C states Theorem 2 (Finite-length recovery under local coupling). These appear to be the same result. It is unclear whether these were intended to be two distinct theorems or one theorem stated twice.
4 comments
W3. Benefit of multiple heads
A3. Thank you for this important observation. We have strengthened Appendix C to analyze the target–competitor score difference directly, accounting for the dependence among heads that score the same sampled token.
Instead of treating separating heads as independent observations, we derive the joint exponential moment of their score difference under the actual exponential-tilting sampler. This yields an explicit contraction bound that improves with the number of heads, establishing a theoretical recovery benefit beyond simply counting separating projections.
The new numerical results support this analysis. At , increasing the number of heads from one to two and three raises the theoretical recovery lower bound from 0.151 to 0.886 and 0.959, respectively. Corresponding empirical recovery under online allocation increases from 86.0% to 95.7% and 97.3%, showing substantial initial gains followed by diminishing returns.
Together, the joint-moment analysis and numerical results establish the benefit of multi-head scoring accounting for shared-token sampling fluctuations.
W4. Regret Guarantees under Autoregressive Feedback and Surrogate Reward Validity
A4.1. Counterfactual benchmark. We clarify that our regret guarantee concerns hindsight-optimal allocation over realized opportunities. To examine autoregressive feedback, we compare TrellisMark with a counterfactual benchmark that selects the best-performing fixed-strength policy in hindsight, each independently generating its own trajectory under the same cumulative KL budget. Using 100 paired instances, 32-bit payloads, , and , we select the best-performing fixed strength in hindsight, giving the benchmark an advantage that TrellisMark does not require: evaluating alternative prices and trajectories in advance.
TrellisMark achieves 76% exact recovery, compared with 78% for the best counterfactual policy (), while using 9.3% less KL. These results demonstrate competitive recovery with lower distortion, without requiring hindsight selection or evaluation of alternative trajectories. We report the full comparison in Appendix F.1.
As highlighted by [1], action-dependent feedback poses fundamental challenges for policy-regret analysis, further compounded in our setting by evolving autoregressive contexts and recovery states. Establishing regret guarantees against an unrestricted counterfactual clairvoyant policy remains an important open direction.
A4.2. Surrogate reward validation. The proposed reward is designed for online strength allocation by combining two complementary components: captures the current recovery margin deficits and separation from competing paths, while measures the expected evidence gain induced by exponential tilting. Importantly, this structure yields a closed-form strength-selection rule through , making it suitable for online allocation under a KL budget.
To establish its connection to exact recovery, we derive an exact covariance identity relating exponential tilting to expected pairwise margin improvement. We further validate this connection offline using recorded generation contexts. Across 8-, 16-, and 32-bit payloads, over 98.5% of positive-surrogate steps yield positive expected margin improvements against the strongest currently distinguishable competitor. The surrogate also exhibits strong positive correlations with actual margin improvements (Spearman , respectively). These results support its effectiveness as a recovery-aware reward for online allocation.
Q1. Correction to Eq. (7). Thank you for pointing this out. Under the zero-termination convention in Appendix G, the trellis has queryable stages. We will correct the summation limit in Eq. (7) accordingly.
Q2. Theorem numbering clarification. Theorem 2 in Appendix C was a detailed restatement of Theorem 1 in the main text. We have removed the redundant theorem statement while retaining the formal assumptions and complete proof in Appendix C.
[1] Raman Arora, Ofer Dekel, and Ambuj Tewari. “Online bandit learning against an adaptive adversary: from regret to policy regret.” ICML 2012.
Dear Reviewer aX7P,
As the discussion deadline is now less than two days away, we would like to kindly follow up on our rebuttal.
We have provided additional experiments and clarifications to address your valuable feedback, and would be sincerely grateful if you could take a moment to review our responses and share any remaining concerns. We would be more than happy to provide further clarifications before the discussion closes.
Thank you again for your time and thoughtful consideration.
Best regards,
Paper 17879 Authors
Looking Forward to Your Feedback (Less than 24 Hours Left)
Dear Reviewer aX7P,
As the discussion period ends in less than 24 hours, we would sincerely appreciate your feedback on whether our rebuttal has addressed your main concerns. If no major concerns remain, we would be truly grateful if you could consider updating your rating accordingly. We would be more than happy to clarify any remaining questions before the discussion closes.
Thank you again for your time and consideration.
We sincerely thank the reviewer for recognizing the value of our principled overlapping-window design. We also appreciate the insightful feedback on our theoretical analysis and experiments, which we address below.
W1: Finite-length recovery guarantee
A1. Thank you for highlighting this gap. We have substantially strengthened Theorem 1 and Appendix C by replacing the assumed cumulative margin with a recovery guarantee derived directly from the exponential-tilting sampler.
First, we establish an explicit positive expected target–competitor score advantage. We then derive a finite-length recovery bound using the joint distribution of multi-head scores, obtaining a computable positive recovery constant without the previously assumed margin parameters.
Second, we empirically calibrate the context-diversity assumption using recorded LLM generations, selecting the threshold on calibration runs and evaluating the resulting bounds on held-out runs. As shown in the new Appendix C results, the theoretical recovery lower bounds are nonvacuous in 10 of 12 settings. For example, at T=450, the lower bounds reach 0.886 with two heads and 0.959 with three heads. Importantly, empirical recovery under actual autoregressive LLM generation with online allocation reaches 95.7% and 97.3%, respectively, broadly consistent with the high recovery levels suggested by these theoretical bounds.
These results address the previously unverified assumptions and demonstrate that the revised theorem provides informative recovery guarantees at practical generation lengths.
W2: Window-Width Ablation and Coupling Effects
A2.1. Recovery–quality trade-off across window widths. To address this concern, we additionally report the KL divergence and perplexity for each window width.
Increasing the window width from w=1 to w=6 substantially improves exact recovery (16.6% to 90.6%), while reducing mean KL/token (0.190 to 0.165) and maintaining comparable perplexity (15.1 vs. 14.9). Thus, the recovery improvement is not achieved at the expense of greater distortion, suggesting that wider overlapping windows enable more effective aggregation of watermark evidence under lower perplexity.
A2.2. Hyperparameters across window widths. All allocation hyperparameters were held fixed across all window widths. No width-specific hyperparameter tuning was performed.
A2.3. Non-overlapping ECC control. To distinguish the benefits of overlapping projections from those of increased redundancy, we additionally evaluate a conventional error-correcting code (ECC) baseline. Specifically, a rate-1/2 convolutional code first encodes the 32-bit payload into 68 coded bits. Each watermark head then independently measures a single encoded symbol, rather than a combination of overlapping payload symbols: z=ECC(m),ct,h=ϕt,h(zit,h), where it,h is a keyed position assignment and ϕt,h maps the selected encoded symbol to a target color. The accumulated evidence is decoded jointly using soft Viterbi. We use the same two heads per token and the same head-bias formulation (β=0.5), with fixed strength δ=1.4 for the ECC baseline.
With the same measurement budget, TrellisMark improves exact recovery by 33.4 percentage points while achieving lower KL divergence and perplexity. These results suggest that the recovery gains from wider windows cannot be simply replicated by adding conventional coding redundancy to independent symbol measurements. Further details are provided in Appendix L.3.