- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The authors of the paper introduce BEFMark, which is an inference-time multi-bit watermark for discrete diffusion language models. The main contribution appears to be that, during denoising, the watermark extracts keyed votes from resolved token-context pairs, tracks normalized evidence for each message bit, and uses a soft-minimum objective to prioritize weakly supported bits. It estimates additional evidence under a product distribution over unresolved tokens and uses this estimate in a KL-regularized update of the model’s predictions. Then during the message recovery process, the watermark recomputes the keyed assignments and aggregates votes.
The authors carry out experiments on some LLMs, including LLaDA-8B-Instruct and Dream-v0-Instruct-7B, and compare across datasets in NLP (such as ELI5, FiQA, and C4). They compare bit recovery and generation quality against existing methods. The baselines compared against are MPAC of Yoo et al., (2024) and BiMark of Feng et al., 2025.
Critical strengths
There are two main strengths of this work, in my opinion:
(1) The central adaptive-feedback idea has direct experimental support: The uniform-weighting ablation in Table 5 is quite convincing: adaptive weighting increases 16-bit accuracy from 83.11% to 93.51% at 300 tokens and from 84.93% to 95.57% at 500 tokens, with essentially the same (log)perplexity. This provides evidence that directing effort toward weak bits improves recovery and goes beyond the general benefit of applying a (stronger) watermark.
(2) The improvements extend to complete-message recovery at modest computational cost: For 500-token LLaDA generations, Table 4 reports exact-message recovery of 92.67%, 57.17%, and 14.33% for 8-, 16-, and 32-bit messages, respectively, compared with the strongest baseline values of 68.83%, 31.00%, and 1.17%. These gains are quite good because high average bit accuracy alone can hide poor recovery of an entire identifier. Table 12 reports generation time of 18.18 seconds vs. 16.32 seconds without watermarking and 0.43 GB additional peak memory.
Even though the main tables are in the appendix (i.e., supplementary material), I was engaged enough to read some of these results.
Critical weaknesses
Even though the paper is quite nice, I still have some questions (to be outlined later). For now, here are some weaknesses:
(1) The comparison of recovery–quality tradeoffs is not sufficiently documented. In Appendix B.1, the authors try to lay out the method’s main settings, but the competing methods’ watermark strengths, layer counts, and diffusion/remasking configurations are not comparably clear. Figure 4 connects different generation lengths but does not sweep each method’s embedding strength. Since Table 6 shows that BEFMark’s accuracy and quality change with its strength parameter, the current results are not clear enough on whether the advantage also appears well-tuned baselines at matched quality and actual output length. (The strong internal ablation partially addresses this concern.)
(2) The efficient implementation of the central expectation is underspecified. Equation (9) in the paper involves interactions between candidate tokens and context-hash values, with . For a general keyed partition, direct evaluation involes a quadratic vocabulary-size interaction! However, the paper does not explain whether its implementation uses truncation, sampling, a structured partition, or another computational shortcut. So, as a reader of the paper, it might be difficult to reproduce the central algorithm. (This is an implementation concern.)
Questions for authors
In reading the paper, I have the following questions for the authors:
-- Baseline clarification: What watermark strength, layer count, and diffusion (or remasking) configuration is used for each baseline? In particular, does UMR still use its regret-based remasking? Please provide recovery–quality comparisons over the main strength parameter using matched prompts and actual output lengths, with variability over keys and messages.
-- Implementation clarification: How are Equation (9) and its gradients evaluated in the reported implementation? Please specify the hash/partition construction, the numerical stabilizer used for initially empty evidence counts, any truncation or approximation, and the resulting time and memory complexity. Is an approximation used here?
-- Recovery evidence: I wonder if exact-message recovery be reported for the existing Dream and post-edit outputs? The large LLaDA gains look fine, but these additional measurements would determine whether the weak-bit feedback advantage generalizes beyond average bit accuracy in those settings.
7 comments
Response to Reviewer fj9V 2/6
Q1-(3) Actual output lengths. We evaluated actual output lengths for LLaDA-8B-Instruct with 16-bit messages and a maximum generation length of 500 tokens. The mean lengths are 396.5 tokens for BEFMark, 400.4 for PredMPAC, 394.1 for UMR, and 430 for PredBiMark. BEFMark therefore produces outputs of comparable or shorter average length than the baselines. In particular, BEFMark generates 33.5 fewer tokens on average than PredBiMark, while its Acc is 7.44 percentage points higher (95.57% vs. 88.13%, as reported in Table 1 of the main paper).
Q1-(4) Variability over keys and messages. In our reported BEFMark experiments, we independently sample a random watermark message for each test sample, so the reported metrics aggregate performance over different messages. To further assess sensitivity to key choice, we evaluate BEFMark with three watermark keys at message lengths of 8 and 16 bits. Table R3 reports mean ± sample standard deviation across these keys. The standard deviations are at most 0.20 percentage points for Acc, 0.68 percentage points for EMR, and 0.017 for log-PPL, indicating limited variation in recovery performance and text quality across the keys.
Table R3. BEFMark across three watermark keys on LLaDA-8B-Instruct (maximum generation length: 500 tokens; mean ± sample standard deviation).
| Bits | Acc (%) ↑ | EMR (%) ↑ | log-PPL ↓ |
|---|---|---|---|
| 8 | 98.01 ± 0.09 | 92.39 ± 0.63 | 2.219 ± 0.007 |
| 16 | 95.42 ± 0.20 | 56.78 ± 0.68 | 2.249 ± 0.017 |
Response to Reviewer fj9V 3/6
Q2. Implementation clarification: How are Equation (9) and its gradients evaluated in the reported implementation? Please specify the hash/partition construction, the numerical stabilizer used for initially empty evidence counts, any truncation or approximation, and the resulting time and memory complexity. Is an approximation used here?
For reference, Eq. (9) is:
=\sum_{i\in\Omega_{\mathrm{full}}\setminus\Omega_t}\sum_{v\in\mathcal V}\pi_{t,i}(v) \sum\nolimits_{h_{t,i}=0}^{K-1}p_{h}(h_{t,i}\mid\pi_t)m_{t,i,b}(v,h_{t,i}).\tag{9}$$ Below, we explain (1) how Eq. (9) is evaluated and differentiated, including the approximation and cost; (2) how the hash/partition is constructed; and (3) how initially empty evidence counts are handled. **Q2-(1) Efficient computation and differentiability of Eq. (9).** **Efficient computation:** To evaluate the expected evidence margin increment in Eq. (9), we need both the token probabilities $\pi_{t,i}(v)$ and the context-hash probabilities $p_h(h\mid\pi_t)$ (Eq. (8)). The token probabilities are given by Eq. (4) in the main paper; we therefore focus here on computing the context-hash distribution. Under the factorized completion model, convolution followed by modulo-$K$ aggregation ($K=|\mathcal V|$) is equivalent to a circular convolution of the context-token distributions. By the convolution theorem, this circular convolution can be evaluated using FFTs at a per-position cost of $O(M|\mathcal V|\log|\mathcal V|)$, where $M=|\mathcal S|$, avoiding enumeration of all possible context-token combinations. Once the context-hash distribution is available, Eq. (9) combines it with the token probabilities to weight the evidence margin contributed by each token-hash pair $(v,h)$. For each pair, MCEA determines the layer-wise bit assignments and token labels, and TBEA aggregates their signed votes into the evidence margin $m_{t,i,b}(v,h)$ (see Part (2) for hash and partition construction). The pair contributes $\pi_{t,i}(v)p_h(h\mid\pi_t)m_{t,i,b}(v,h)$ to the expected evidence margin increment. However, evaluating all $|\mathcal V|K$ pairs at every position is expensive. We therefore approximate this sum by retaining the top-$k_v$ tokens and top-$k_h$ hashes according to their probabilities. We use $k_v=k_h=100$. We use their original probabilities without renormalization and sum the retained contributions over newly valid positions. This reduces evidence evaluation to at most $k_vk_h$ pairs per position, each requiring $N_{\mathrm{layer}}$ layer-wise votes. **Time complexity:** The combined cost of FFT-based hash computation and retained-pair voting over at most $L$ positions is $O\\!\left(L\left[M|\mathcal V|\log|\mathcal V|+N_{\mathrm{layer}}k_vk_h\right]\right)$. **Memory complexity:** The implementation avoids materializing the full $|\mathcal V|\times K$ token-hash pair matrix. Instead, it operates on the token and context-hash probability distributions and the retained top-$k_v$ tokens and top-$k_h$ hashes. Under the above FFT-based computation, a conservative auxiliary-memory bound for one evaluation over at most $L$ positions is $O\\!\left(L\left[M|\mathcal V|+N_{\mathrm{layer}}k_vk_h\right]\right)$, assuming voting intermediates for all watermark layers are retained simultaneously. This bound excludes the base model parameters and activations. In our default configuration, $M=1$ and $k_v=k_h=100$. To assess the resulting overhead in the complete generation pipeline, Appendix B.6 reports end-to-end runtime and peak GPU memory. On LLaDA-8B-Instruct with 16-bit messages and a maximum generation length of 300 tokens, BEFMark adds 1.86 s and 0.43 GB relative to unwatermarked generation. **Differentiability:** Substituting Eq. (8) into Eq. (9) expresses the expected evidence margin increment as a finite sum of products of token probabilities, with fixed signed votes as coefficients. It is therefore differentiable with respect to the token probabilities. For the truncated implementation, the top-$k_v$ token and top-$k_h$ hash supports are selected at each evaluation and treated as fixed during differentiation. Autograd computes gradients of this truncated surrogate through the retained token and context-hash probabilities, without differentiating through the discrete support selection. **Q2-(2) Hash/partition construction.** To compute the evidence margin $m_{t,i,b}(v,h)$ in Eq. (9), each layer needs a message-bit position and a binary label for token $v$. Here, $h$ is computed using the context-hash function $H$ defined in the main paper. Given $h$ and the watermark key, one pseudorandom mapping determines the layer-wise bit positions, while another assigns each token to a label-0 or label-1 subset for that context and layer, with nominal probability $1/2$ per label. TBEA uses these assignments to form the signed votes and aggregate them into $m_{t,i,b}(v,h)$.
Response to Reviewer fj9V 1/6
We thank the reviewer for their careful attention to our work. The following are the detailed answers to your questions and concerns.
Q1-(1) Baseline clarification.
We reproduce the baselines using their official codebases; the context adaptations and shared sampling settings are described in Appendix B.1. For all methods, the total number of denoising steps equals the maximum generation length (300, 500, or 800 tokens). We will open-source our code upon acceptance to make these implementation details accessible.
UMR: Regret-based remasking remains enabled in all reported UMR experiments, as it is an integral component of the method. We use a base reweighting strength of δ~=4.0 on both backbones.
PredMPAC: Following the official code, we use logit bias δ=2.0, partition ratio γ=0.25, radix r=4, and LeftHash with context width h=1.
PredBiMark: We use 10 watermark layers and candidate truncation at k=50. In most settings, we use the base reweighting strength of δ~=1.0 adopted in the original paper. On Dream, this strength yields limited message recovery in our diffusion-model adaptation, so we additionally evaluate an increased strength of δ~=2.0 to improve its recovery performance.
Q1-(2) Recovery–quality trade-off.
For a given method, increasing watermark embedding strength can improve bit recovery accuracy (Acc), but excessive strength may degrade the quality of generated text. We therefore assess recovery gains together with their text-quality cost and compare Acc at comparable log-PPL. In Table 1 of the main paper, BEFMark already achieves lower log-PPL and higher Acc than the compared baselines in 10 of the 18 configurations.
For the remaining eight configurations, we use log-PPL as the quality-matching criterion and adjust watermark embedding strength to target comparable text quality. In five of these configurations (Table R1), we adjust BEFMark's strength to target the lowest baseline log-PPL while keeping the other evaluation settings fixed. Adjusted BEFMark achieves lower log-PPL and higher Acc than every compared baseline in all five settings. The baseline results in Table R1 are from Table 1 of the main paper.
Table R1. Recovery after adjusting BEFMark's embedding strength. Each entry: Acc (%) ↑ / log-PPL ↓. Columns: model, message length (bits) / maximum generation length (tokens).
For the three remaining Dream configurations (maximum generation length: 800 tokens), Table 1 in the main paper reports substantially lower log-PPL for PredBiMark than for the other compared methods. We therefore explore increasing PredBiMark's embedding strength. We evaluate all methods in Table R2 on the same 150 randomly sampled test prompts (50 per dataset). The subset size reflects the computational cost of generation and strength adjustment at this length. As shown in Table R2, BEFMark achieves higher Acc and lower log-PPL than the compared baselines, including adjusted PredBiMark, in all three configurations on this subset.
Table R2. Subset comparison with adjusted PredBiMark embedding strength (Dream-v0-Instruct-7B, 150 prompts, maximum generation length: 800 tokens). Each entry: Acc (%) ↑ / log-PPL ↓.