acceptodds
Under review as a conference paper at ICLR 2027

TrellisMark: Multi-Bit LLM Watermarking with Trellis Coupling and Online Strength Allocation

Abstract

Multi-bit watermarking enables large language models to embed rich structured messages, such as user and model identifiers, into generated text, supporting provenance attribution and misuse tracing. Existing methods either let each token contribute evidence to only one payload position, leaving each position with limited evidence, or aggregate evidence over complete messages, making exact decoding costly as the payload grows. We introduce TrellisMark, which couples neighboring payload positions through overlapping local windows. Each token provides evidence about the symbols in one selected window, while multiple independent heads over the same window strengthen this evidence. The overlap induces a trellis over candidate payloads, enabling exact maximum-score recovery without enumerating the full message space. We further formulate watermark-strength selection as an online allocation problem driven by the current trellis recovery state. Under a cumulative KL-divergence budget, the policy assigns greater strength to steps with higher recovery value. We prove a recovery bound based on trellis-path separation and a regret bound for online allocation. Experiments show improved exact message recovery and better recovery–quality trade-offs over existing baselines.

Primary area:
generative models
Keywords:
multibit watermarking

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_aX7POpenReview ↗
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
  1. The finite-length recovery theorem relies on an unverified and potentially vacuous margin assumption. Assumption 1 requires that, simultaneously for every competing payload s~\tilde{s}, the cumulative expected score advantage satisfies ΓT(s~)≥η dκ(s,s~)\Gamma_T(\tilde{s}) \geq \eta\, d_\kappa(s,\tilde{s}). 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 η\eta, ϵmar\epsilon_{\mathrm{mar}}, and γ\gamma. The paper neither estimates these quantities empirically nor verifies Assumption 1 across payload lengths, models, strengths, or window widths. If η\eta is small or ϵmar\epsilon_{\mathrm{mar}} is non-negligible, the derived bound may provide little information, making it difficult to assess whether the theorem explains the empirical gains.

  2. 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 w=1w=1 versus w>1w>1? 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 δmax⁡\delta_{\max}, the target margin μ\mu, 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 ww changes not only overlap but also the local-assignment space, score geometry, and behavior of the online utility.

Finally, w=1w=1 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?

  1. The finite-length analysis in Appendix C derives a projection-separation term that scales with the number of heads HH. 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 HH increases. Instead, the argument absorbs the required per-separating-projection target--competitor score advantage into the assumed constant η\eta. The analysis does not show that η\eta remains positive or stable as HH changes; it may depend on the joint token-color distribution, β\beta, 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.

  2. The hindsight benchmark fixes the realized sequence of opportunities (ωt,Gt,Dt)(\omega_t,G_t,D_t). 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 ωtGt(δ)\omega_t G_t(\delta) is a surrogate: GtG_t 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
  1. Eq. 7 seems to miss "r", which should be \sum_{j=1}^{N+r}\Phi_j(s'_{j-r:j})
  2. 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

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=450T=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.

Query widthExact Accuracy (%) ↑PPL ↓Mean KL/token ↓
116.6015.10.190
259.0015.10.184
366.4014.90.179
481.2015.50.175
582.8014.60.169
690.6014.90.165

Increasing the window width from w=1w=1 to w=6w=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),\mathbf z=\mathrm{ECC}(\mathbf m), c_{t,h}=\phi_{t,h}(z_{i_{t,h}}), where it,hi_{t,h} is a keyed position assignment and ϕt,h\phi_{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\beta=0.5), with fixed strength δ=1.4\delta=1.4 for the ECC baseline.

MethodExact Acc. (%) ↑KL/token ↓PPL ↓
Convolutional ECC47.800.197915.80
TrellisMark81.200.174615.46

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.

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 T=450T=450, 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, T=300T=300, and H=2H=2, 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 (δ=1.4\delta=1.4), 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: ωt\omega_t captures the current recovery margin deficits and separation from competing paths, while Gt(δ)G_t(\delta) measures the expected evidence gain induced by exponential tilting. Importantly, this structure yields a closed-form strength-selection rule through Dt′(δ)=δGt′(δ)D_t'(\delta)=\delta G_t'(\delta), 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 ρ=0.90,0.78,0.63\rho=0.90, 0.78, 0.63, 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 N+rN+r 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

AuthorsOpenReview ↗

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.

Reviewer_JceFOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes TrellisMark, a multi-bit LLM watermark in which each token, through multiple independently keyed heads, carries evidence about one context-selected window of w=r+1w = r+1 consecutive payload symbols; because adjacent windows overlap, the decoding score decomposes over a trellis, and exact maximum-score recovery is obtained by Viterbi decoding in O((TH+N)qr+1)O((TH+N)q^{r+1}) time, which is polynomial in the payload and text lengths for fixed ww and qq. It further casts per-token strength selection as online allocation under a cumulative KL budget driven by the margin to the strongest competing trellis path, provides conditional finite-length recovery and regret guarantees, and reports higher exact recovery for 16- to 64-bit payloads, better recovery–perplexity trade-offs, and improved robustness in most attack settings relative to MPAC, RSBH, StealthInk, and BiMark on C4 and LFQA with Llama-3.2-3B and Qwen3-4B.

Critical strengths
  1. Overlapping windows offer a principled compromise between evidence sharing and decoding complexity: each payload symbol gathers evidence from r+1r+1 windows while exact maximum-score decoding remains tractable, and the same trellis is reused at encoding time to compute competitor margins for strength allocation.

  2. The clean-recovery gains are large and consistent (93.2% vs. 76.0% at 32 bits; 14–26 points at 64 bits across three settings), and the ablations over window width (17% → 59% → 81% for w=1,2,4w = 1, 2, 4), number of heads, and adaptive versus fixed strength (Figures 3 and 8) support the main design choices, which is why I view the contribution as practically meaningful.

Critical weaknesses
  1. Although the paper cites Viterbi decoding and prior online-allocation work, it does not discuss closely related trellis-based information hiding, namely dirty-paper trellis watermarking with Viterbi decoding and informed embedding toward a target robustness, and syndrome-trellis coding for minimum-distortion embedding; the novelty discussion should separate the LLM-specific contributions from these established principles. Relatedly, the existing ablations support the benefits of overlap and multiple heads but do not isolate the incremental benefit of context-dependent projections over a fixed-projection variant or a convolutional outer code.

  2. Several experimental settings are inconsistent or unspecified, which limits reproducibility: Appendix G sets μ=12\mu = 12, whereas Figure 5 states "configured margin = 4" and Figure 9c plots a target that increases over generation; the default bˉ\bar{b} for the main experiments is not reported; and the Table 1 clean recovery rates appear lower than the 450-token results in Figure 2b without explanation. In addition, Table 1 compares robustness at different clean-quality operating points (PPL 13.7–16.2), so robustness differences are not fully separated from operating-point selection.

Questions for authors
  1. Please specify the configuration behind each figure: whether the experiments use a time-dependent target margin (Figure 9c) rather than the constant μ=12\mu = 12 in Appendix G, whether Figure 5 jointly varies the KL budget and δmax⁡\delta_{\max}, the default bˉ\bar{b} for Figures 2 and 4 and Table 1, the generation length for Figure 3, and the payload size and generation length for Figures 4b–c and 5. Were recovery weights capped or normalized in the experiments? If so, please report the rule; otherwise, clarify how the assumption ωt≤ωmax⁡\omega_t \le \omega_{\max} relates to the implementation. Please also clarify whether Table 1 and Figure 2b use the same configurations and evaluation samples. These clarifications are needed to assess reproducibility and whether the comparisons support the claimed gains.

  2. What is the incremental benefit of context-dependent projections? Please compare, at matched KL or perplexity, (a) a variant with fixed per-head projections, whose underlying projection code has a nominal rate-1/H1/H convolutional structure (up to termination overhead) and, for H<wH < w, a nontrivial kernel within each stage, although overlap across stages may still make the full payload identifiable; and (b) MPAC-style allocation with a convolutional outer code and soft Viterbi decoding. If feasible, a 16-bit comparison with ArcMark would also help position the method against message-level coding. These results would clarify the contribution of each component relative to established trellis-coding principles.

  3. The fixed-strength comparisons (Figures 3 and 8) support adaptive allocation, but how much of this gain comes from the dual-price update itself? A margin-gating rule (e.g., δmax⁡\delta_{\max} when the local competitor margin at JtJ_t is below μ\mu and Sept(u)>0Sep_t (u) > 0, and a small baseline strength otherwise) under the same cumulative KL budget and hard-budget enforcement would isolate it; because the saturation threshold ωt≥λtδmax⁡\omega_t \ge \lambda_t \delta_{\max} varies with λt\lambda_t, the binned saturation in Figure 10c alone does not settle this. Does adaptive allocation also retain its advantage over fixed δ\delta under the Table 1 attacks?

Suggestions for future work (not affecting my score): localized editing and cropping attacks (relevant because strength is front-loaded in Figures 9a and 10a), insertion attacks, watermark-presence detection with false-positive control, and encoding latency.

8 comments

We sincerely thank the reviewer for recognizing the practical significance of TrellisMark. We also appreciate the constructive feedback and address each concern in detail below.

W1: Relation to Prior Trellis Coding and Incremental Contributions

A1.1. Relation to classical trellis coding. Thank you for highlighting these related works. We agree that trellis coding and Viterbi decoding are established techniques. We have expanded the related-work discussion in Appendix L.1. However, classical trellis-based information hiding addresses different embedding problems. Dirty-paper trellis watermarking [1] uses host-informed codeword selection and embedding to improve robustness in images, while syndrome-trellis coding [2] uses Viterbi optimization to minimize distortion in image steganography.

TrellisMark differs in its coding mechanism, rather than merely its application domain. Instead of selecting a codeword for an existing cover, each candidate payload defines a trellis path through overlapping payload windows. Context-dependent projections allow different generation contexts to provide different measurements of the same window. These token-level observations are collected in a context-dependent order and aggregated into branch scores for joint Viterbi recovery. We further integrate this structure with online strength allocation. Our novelty therefore lies not only in applying Viterbi decoding to LLM Watermarking, but also in the construction of context-dependent payload evidence and its recovery-aware allocation.

A1.2. Benefit of context-dependent projections. To isolate the contribution of context-dependent projections, we replace them with fixed per-head projections while keeping all other components unchanged. We evaluate 16- and 32-bit payloads across different generation lengths.

Payload / LengthRecovery: Fixed / Ours (%) ↑PPL: Fixed / Ours ↓
16-bit / 30098.2 / 98.813.94 / 13.39
16-bit / 35099.4 / 99.614.08 / 13.54
32-bit / 35082.6 / 88.816.29 / 15.08
32-bit / 40091.4 / 93.216.56 / 15.01
32-bit / 45094.6 / 95.816.67 / 15.11

Context-dependent projections consistently achieve higher recovery accuracy and lower PPL. Unlike fixed projections, which repeatedly measure the same linear combinations, context-dependent projections provide new measurements across contexts, allowing previously indistinguishable window assignments to be separated. Our theoretical analysis shows that the collision probability decreases with the number of distinct contexts under independent projections. Consistent with this, our evaluation shows that the fraction of alternative local window assignments indistinguishable from the true assignment decreases from 4.53% to 0%. These results demonstrate the additional benefit of context-dependent projections beyond repeated fixed measurements. Both analyses are detailed in Appendix L.2.

A1.3. Comparison with convolutional coding. To further distinguish our approach from conventional coding, we implement the suggested MPAC baseline with a convolutional outer code and soft Viterbi decoding in Appendix L.3. The payload is convolutionally encoded before MPAC embedding, and Viterbi decoding recovers the original message from accumulated soft evidence.

Method (16 bits, 303 tokens)Exact Recovery (%) ↑PPL ↓
MPAC80.615.34
MPAC + ConvCode + Viterbi91.215.45
TrellisMark98.813.39

Convolutional coding improves MPAC recovery by 10.6 points, but does not close the gap with TrellisMark. Our method achieves a further 7.6-point improvement with substantially lower PPL. This confirms the value of classical error correction while showing that simply adding a convolutional outer code does not account for TrellisMark's recovery–quality advantage.

Together, these comparisons distinguish TrellisMark's contributions from established trellis-coding principles, both in its context-dependent construction and in its empirical recovery performance.

[1] Miller, Matthew L., G. J. Dorr, and Ingemar J. Cox. "Dirty-paper trellis codes for watermarking." ICIP 2002.

[2] Filler, Tomáš, Jan Judas, and Jessica Fridrich. "Minimizing additive distortion in steganography using syndrome-trellis codes." TIFS 2011.

W2: Experimental Configurations

We thank the reviewer for pointing out these ambiguities. We clarify the experimental settings and comparisons below.

A2.1. Target margin schedule. The default configuration uses q=4q=4, H=2H=2, w=4w=4, β=0.5\beta=0.5, and δmax⁡=1.4\delta_{\max}=1.4, unless otherwise specified. The main experiments use a time-dependent target margin that increases with the cumulative number of projection factors at a square-root rate, capped at 20. Figure 9c illustrates this schedule. The "configured margin = 4" in Figure 5 refers to the base margin of this schedule, rather than a constant target throughout generation. We will correct Appendix G to reflect the actual experimental configuration instead of the constant μ=12\mu=12.

A2.2. Default KL budget. The default average per-token KL budget for the main experiments is bˉ=0.2\bar b=0.2.

A2.3. Consistency between Table 1 and Figure 2b. The discrepancy results from an incorrect generation-length description in Table 1. Table 1 actually uses the 400-token configuration, rather than 450 tokens, yielding 93.2% clean recovery, consistent with the corresponding 400-token point in Figure 2b. We will correct the Table 1 caption.

A2.4. Quality operating points. We acknowledge that Table 1 does not compare methods at strictly matched perplexity. However, PPL is an observed outcome of generation rather than a directly controlled embedding parameter. Importantly, TrellisMark achieves stronger robustness than MPAC, RSBH, and BiMark under most attacks while maintaining lower PPL (15.0 vs. 15.7–16.2). Although StealthInk has lower PPL (13.7), it is already evaluated at its maximum watermark strength, and its recovery performance remains substantially lower.


Q1: Experimental Configurations and Theoretical Consistency

Thank you for identifying these ambiguities.

A1.1. Target margin schedule. The main experiments use a time-dependent target margin rather than a constant μ=12\mu=12. Please refer to the previous answer in W2 (A2.1) for details.

A1.2. Experimental configurations. The default KL budget is bˉ=0.2\bar b=0.2, as clarified in W2 (A2.2). Specifically, Figures 2 and 4 and Table 1 use this default KL budget. Figure 3 uses 300 generated tokens and jointly varies bˉ\bar b and δmax⁡\delta_{\max}. Figures 4b–4c use 32-bit payloads and 300 generated tokens, varying the window width and number of heads, respectively. Figure 5 uses a 32-bit payload and 300 generated tokens, and jointly varies bˉ\bar b and δmax⁡\delta_{\max}.

A1.3. Bounded recovery weights. We thank the reviewer for this question. In our experiments, recovery weights were computed directly from Eq. (9), without explicit capping or normalization, and remained moderate, with a maximum observed value of 128.

The regret analysis only requires a finite, horizon-independent upper bound, without imposing a specific numerical threshold. Such boundedness can be ensured through a sufficiently large cap, which would not affect any allocation decisions or reported results in our experiments. We have clarified this distinction in Appendix F.

A1.4. Consistency between Table 1 and Figure 2b. Table 1 and Figure 2b use the same evaluation samples. Please refer to W2 (A2.3) for the correction of the generation-length description.


Q2: Incremental Contributions over Existing Coding Methods

A2. Regarding the requested comparisons: (a) the benefit of context-dependent projections over fixed per-head projections is evaluated in W1 (A1.2); (b) the comparison with MPAC using a convolutional outer code and soft Viterbi decoding is provided in W1 (A1.3).

Comparison with ArcMark. We additionally evaluate ArcMark with a 16-bit payload and 150 generated tokens. ArcMark achieves 86.4% recovery, compared with 87.6% for TrellisMark. Notably, even at this relatively short payload and generation length, ArcMark requires 7 h 40 min for generation and decoding over 500 samples, compared with 2 h 18 min for TrellisMark (3.3× longer). This substantial computational overhead limits the practicality of scaling ArcMark to longer payloads and generation lengths, making a more comprehensive comparison computationally prohibitive.

Q3. Contribution of adaptive allocation

We thank the reviewer for these suggestions. We provide additional experiments and analyses to clarify the contribution of adaptive allocation.

A3.1. Contribution of dual-price updates. To distinguish the benefit of our online strength allocation from simpler margin-based decisions, we introduce a Margin-Gating baseline in Appendix J that applies δmax⁡=1.3\delta_{\max}=1.3 when the local competitor margin is below μ\mu and separation is positive, and a smaller baseline strength otherwise. Both methods use the same cumulative KL budget and hard-budget enforcement.

MethodRecovery (%) ↑PPL ↓
Margin gating80.015.1
TrellisMark87.615.1

At matched PPL, TrellisMark achieves 7.6 percentage points higher recovery than Margin-Gating. Unlike the binary decisions of margin gating, our policy continuously adjusts watermark strength according to the remaining recovery deficit, current projection separation, and evolving dual price. This allows more effective allocation of the KL budget toward valuable recovery opportunities. Importantly, this improvement comes with minimal additional algorithmic complexity: given the trellis scores, strength selection has a closed-form solution and the dual price requires only a scalar update per token. These results demonstrate the benefit of our recovery-aware online allocation beyond simple margin-based heuristics.

A3.2. Saturation mechanism. We agree that the original Fig. 10(c) does not explicitly account for the dual price λt\lambda_t. We have replaced it with a joint saturation analysis over ωt\omega_t and λt\lambda_t. The revised figure shows that the observed saturation closely follows the theoretical boundary ωt≥λtδmax⁡\omega_t\geq\lambda_t\delta_{\max}. This confirms that saturation depends jointly on recovery utility and dual price.

A3.3. Robustness under text edits. We additionally compare adaptive allocation with fixed-strength TrellisMark δ=1.2\delta=1.2 under the Table 1 attacks.

MethodClean ↑5% Del. ↑10% Del. ↑DIPPER ↑PPL ↓
Adaptive93.258.836.64.015.0
Fixed-δ\delta80.049.639.25.015.0

At the same perplexity, adaptive allocation achieves substantially higher clean recovery and better recovery under 5% deletion, while showing comparable performance under 10% deletion and DIPPER. Although the advantage is not uniform across attacks, TrellisMark achieves the highest exact recovery among competing baselines under several attack settings in Table 1, demonstrating meaningful progress. Our primary focus is reliable multi-bit recovery under text quality constraints, rather than explicitly optimizing robustness to text edits. Further improving robustness remains an important direction for future work.

Reviewer_gqF1OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a multi-bit LLM watermarking method that improves the recovery of embedded messages. The key idea is to use overlapping local payload windows and multi-head matching to share watermark evidence across multiple payload symbols, enabling efficient message recovery through Viterbi decoding. Experiments show improved exact message recovery rates and better recovery–quality trade-offs compared to existing multi-bit watermarking methods.

Critical strengths

The trellis-based design is a good idea. By using overlapping payload windows, the proposed method allows different payload bits to share evidence while still enabling efficient recovery through Viterbi decoding.

Critical weaknesses

The main concern is the practical usefulness of the proposed method.

  1. The online strength allocation seems to introduce non-neglectable computational overhead, as it requires maintaining and updating trellis scores at every generation step.

  2. The robustness results are somewhat concerning. Although TrellisMark outperforms existing baselines, its exact message recovery drops significantly even under slight attacks (e.g., 10% word deletion). This raises questions about how useful the method would be for real-world cases.

Questions for authors
  1. See weakness 1.

  2. For weakness 2, I understand that robustness against text edits remains a major challenge even for zero-bit watermarking methods like Gumbel-max. Thus it is reasonable to expect multi-bit watermarking to be even more vulnerable. Given the current state of watermarking research, although multi-bit watermarking can embed richer information, its reliability remains to be a big problem. I wonder how the authors view this trade-off, and any relevant discussion would be helpful.

6 comments

We sincerely thank the reviewer for recognizing the value of our trellis-based design. We also appreciate the constructive feedback on computational efficiency and practical robustness, which we address in detail below.

W1 & Q1: Computational Overhead

A1. To quantify the cost of maintaining and updating trellis scores, we profile the two main online components using Llama-3.2-3B-Instruct on C4 with 32-bit payloads and a generation length of 100 tokens.

MetricTrellis updateStrength allocationTotal
Time (ms/token)4.201.005.20
Generation time (%)16.473.9320.40

The online overhead is modest. Trellis-score updates and recovery-weight computation account for most of this overhead, while adaptive strength allocation adds only 1.00 ms/token (3.93% of generation time). Together, these components account for 20.40% of generation time, with most computation remaining in language model inference.

End-to-end runtime. We further compare the generation and decoding times against other state of the art multi-bit watermarking methods.

MethodGeneration (s)Decoding (s)Total (s)
MPAC1.460.031.49
BiMark1.920.011.93
RSBH2.340.432.77
StealthInk3.170.453.62
TrellisMark2.620.372.99

TrellisMark achieves a favorable balance between computational efficiency and recovery performance. Its total runtime of 2.99 s is comparable to RSBH (2.77 s) and lower than StealthInk (3.62 s). While MPAC and BiMark are faster, they exhibit substantially weaker recovery performance in Fig. 3. These results confirm that TrellisMark's improved recovery performance does not come at the expense of excessive computational overhead. We have added this analysis to Appendix I.

W2 & Q2: Robustness to Text Edits and Practical Reliability

Thank you for raising this concern.  As mentioned, robustness against text edits remains a major challenge even for zero-bit watermarking methods. Multi-bit watermarking faces the same challenge while requiring exact recovery among 2L2^L possible messages. For a fixed text length TT, a higher payload rate R=L/TR=L/T leaves less evidence per bit, making reliable recovery more difficult under text edits.

We have added additional experiments and analysis to discuss the capacity–robustness trade-off in multi-bit watermarking further.

A2.1. Effect of payload and text length on robustness. We additionally evaluate exact recovery under 10% word deletion. First, we consider a modest generation length of 300 tokens and vary the payload size (200 samples per setting):

Payload lengthClean Recovery (%)10% Deletion (%)
2 bits100.084.5
8 bits100.075.5
16 bits98.569.5
32 bits83.037.0

Second, we fix a relatively large payload of 32 bits and vary the generation length (200 samples per setting):

Generation lengthClean Recovery (%)10% Deletion (%)
200 tokens43.012.0
300 tokens83.037.0
400 tokens93.054.0
500 tokens97.065.5
600 tokens99.072.5

These results illustrate the capacity–robustness trade-off: larger payloads require more textual evidence for reliable recovery. Notably, increasing text length substantially improves recovery under deletion, from 12.0% at 200 tokens to 72.5% at 600 tokens for a 32-bit payload.

A2.2. Practical scope and future directions. Multi-bit watermarking goes beyond watermark-presence detection by enabling finer-grained source attribution. Our results show that longer texts provide more reliable recovery under deletion, suggesting that current practical applications are best suited to longer texts. Achieving comparable reliability with shorter or substantially edited texts remains an open challenge in this evolving research area.

Nevertheless, TrellisMark achieves the highest exact recovery among the SOTA baselines in most settings in Table 1, demonstrating meaningful progress toward more robust multi-bit watermarking. Building on this foundation, we also discuss potential directions for improving recovery with fewer tokens, including error-correcting recovery and confidence-aware decoding, in Appendix K, leaving further exploration for future work.

AuthorsOpenReview ↗

Gentle Reminder

Dear Reviewer gqF1,

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

Comments on the paper

2 comments
AuthorsOpenReview ↗

Global Response and Rebuttal Summary

We sincerely thank all three reviewers for their careful evaluations, constructive feedback, and valuable suggestions.

We are encouraged by the reviewers' recognition of our work's key strengths. Reviewer gqF1 highlighted our trellis-based design, Reviewer JceF highlighted the principled balance between evidence sharing and decoding complexity, as well as the substantial recovery improvements, and Reviewer aX7P recognized TrellisMark as a meaningful advancement over existing multi-bit watermarking approaches.

Our paper introduces TrellisMark, a multi-bit LLM watermarking framework with four main contributions:

  • Trellis-Coupled Multi-Bit Watermarking: We introduce overlapping payload windows, context-dependent projections, and multi-head matching to share token-level evidence across payload symbols, enabling exact maximum-score recovery via efficient Viterbi decoding without enumerating the full message space.
  • Online Strength Allocation: We leverage the same trellis structure to identify valuable recovery opportunities and adaptively allocate watermark strength under a cumulative KL-divergence budget, improving the recovery–quality trade-off.
  • Theoretical Guarantees: We establish a finite-length recovery bound for trellis-coupled watermarking and an online regret guarantee for adaptive allocation.
  • Comprehensive Empirical Validation: Experiments across 16-, 32-, and 64-bit payloads, multiple datasets, and models demonstrate improved exact message recovery and recovery–quality trade-offs over existing baselines.

During the rebuttal, we have substantially strengthened the manuscript through revised theoretical analysis, additional controlled experiments, and detailed clarifications. The key improvements, with revisions marked in blue in the updated manuscript, are summarized below:

1. Strengthened Recovery Theory (Theorem 1; Appendix C): We replaced the previously assumed cumulative margin condition with an explicit finite-length recovery bound derived from the watermark sampler. We further developed a joint-moment analysis accounting for dependencies among multiple heads.

2. Controlled Coding Comparisons (Section 6.3; Appendix L): We clarified our distinctions from classical trellis coding and conducted additional comparisons with fixed projections, convolutionally coded MPAC, and a matched-measurement ECC baseline. These experiments further validate the contributions of context-dependent projections and overlapping payload measurements beyond conventional coding redundancy.

3. Effectiveness of Online Allocation (Appendices F.1 and J): We introduced a Margin-Gating baseline, against which TrellisMark achieves 7.6 percentage points higher recovery at matched PPL. We further evaluated counterfactual fixed-strength policies under autoregressive feedback and validated the surrogate recovery utility against expected decoding-margin improvements.

4. Expanded Robustness and Detection Evaluation (Appendices K and M): We investigated the capacity–robustness trade-off across different payload and text lengths, and added prefix/suffix cropping and insertion experiments. We also demonstrated fixed-payload watermark-presence detection, achieving 100% TPR at a target 5% FPR.

5. Computational Efficiency and Experimental Clarifications (Appendices D, G, and I): We added detailed runtime profiling, demonstrating modest computational overhead. We also clarified the target-margin schedule, KL budget, experimental configurations.

We sincerely appreciate the reviewers' insightful feedback, which has helped us substantially strengthen the theoretical foundations, empirical evidence, and practical understanding of TrellisMark. We hope these revisions and additional results address the major concerns raised during the review process.

Best regards,

Paper 17879 Authors

Dear Reviewers,

As the discussion deadline (Nov 18, AoE) approaches, please review the authors' rebuttal if you have not done so, and post a follow-up indicating whether your main concerns have been addressed or whether any issues remain.

Best,

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.