acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Payload Allocation for Multi-bit LLM Text Watermarking

Abstract

Watermarking has emerged as a promising technique for tracing the provenance of content generated by large language models (LLMs). Compared to single-bit watermarking, multi-bit watermarking could embed richer provenance information, such as user identifiers. Most existing multi-bit methods adopt a fixed-payload design, embedding the same number of message bits at every generation step. However, we argue that the payload should be adaptively selected to maximize watermark detectability. In this paper, we characterize detectability using the mutual information since it quantifies the information about the embedded message after observing the sampled tokens. We further show that the achievable mutual information varies with payload size, which motivates formulating per-step payload selection as a mutual-information optimization problem. Based on this, we introduce Maximized Mutual-Information-Based Payload (MMIP), an oracle allocator that exhaustively evaluates candidate payload sizes and selects the one achieving the largest mutual information. However, MMIP requires constructing multiple message-conditioned watermarked distributions for each candidate payload, resulting in substantial inference overhead. To enable efficient online allocation, we further propose Entropy-Based Watermark Payload (EWP). Inspired by findings from MMIP, EWP derives the payload directly from the entropy of the original next-token distribution, thereby avoiding both payload enumeration and explicit construction of candidate watermarked distributions. MMIP and EWP are compatible with representative logit-based and distortion-free multi-bit watermarking methods. Experiments show that EWP achieves comparable performance with MMIP with negligible additional latency and both methods consistently improves the message-recovery–generation-quality trade-off over fixed-payload baselines.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
watermarking, payload, multibit

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_cTyuOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper mainly studies how to dynamically determine the number of bits embedded at each next-token prediction step in multi-bit LLM watermarking. The authors first propose choosing this number according to the mutual information between the message block and the next token. Since this requires expensive computation, they then propose a simpler rule based on the entropy of the original next-token distribution. Both methods aim to improve the trade-off between message recovery and text quality.

Critical strengths
  1. The paper is generally well written and easy to follow. I can get the main intuition of the algorithm clearly from reading the paper.

  2. The topic is interesting and of practical importance. I think studying this problem can help achieve a better trade-off between watermark strength and text fidelity.

Critical weaknesses

1.The descriptions of related work are unclear and even not correct in several places and sometimes terminology that do not appear in the original papers is used.

For example, the paper said "XMark adds ∼1.2 s from its reinforcement-based logit search", however, when I read the original paper, I do not understand what this refers to. The word "reinforcement" even does not appear in the original paper.

Another example is, the paper said that "Model-based detection (StealthInk, EWP-L, EWP-DF, DepthW, MMIP-L, MMIP-DF) must re-run the model on the observed prefix to recover per-step distributions." However, among these papers, my understanding is that at least StealthInk does not require re-run the model.

  1. The novelty claimed in this paper is not fully supported. For example, the Entropy-Based Watermark Payload is claimed as one of the contributions of this work. However, I think similar idea already appears in a paper "PURA: Provably Unbiased and Robust Multi-Bit Watermarking for AI-Generated Text Attribution", which is already accepted by ACM CCS 2026. This paper should have been cited and discussed in depth in the manuscript.
Questions for authors

Could the authors cite and discuss in detail the relationship between this work and “PURA: Provably Unbiased and Robust Multi-Bit Watermarking for AI-Generated Text Attribution” (https://arxiv.org/abs/2608.22218)? I understand the two papers might be finished around the same time, so I do not think this missing comparison is a reason to reject the paper. However, it would be helpful to explain in more detail how the two papers are similar and how they differ.

Also, could the authors check again their descriptions of previous methods against the original papers to ensure they are accurate?

Reviewer_EELUOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper looks at multi-bit text watermarking for large language models and asks a simple question: should the number of watermark bits added at each decoding step stay the same, or should it change from token to token? The main idea is that using a fixed number of bits at every step may be inefficient. Some next-token distributions can carry more watermark information than others, so the payload should ideally adapt to the token being generated. To do this, the authors measure how detectable the watermark is at each step using the mutual information between the embedded message block and the sampled token. They then choose the payload size that gives the highest mutual information. The paper first introduces MMIP, which is the full version of this idea. At each decoding step, it tries different payload sizes, computes the mutual information for each one, and selects the best option. Since this is computationally expensive, the authors also propose a simpler method called EWP. Instead of searching over all payload sizes, EWP chooses the payload based on the entropy of the original next-token distribution. The intuition is that tokens with higher entropy can support larger payloads. The method is tested on several text generation tasks, as well as code and math tasks, using both logit-based and distortion-free watermarking methods. The main evaluation focuses on the trade-off between text quality and bit accuracy. The results show that EWP performs close to MMIP while adding much less latency, and both methods usually do better than fixed-payload baselines. The paper also includes a robustness test under simple text edits, where MMIP performs best, and a speed comparison showing that MMIP is much slower than EWP.

Critical strengths

The paper addresses a real weakness in current multi-bit watermarking methods. Using a fixed payload is simple, but it is not clearly the best choice, and the paper gives a good reason why an adaptive payload should work better. The mutual information view makes sense and fits the problem well. It gives a clear objective for choosing the payload, instead of depending on hand-tuned rules. That makes the method easier to follow and easier to justify. I also think the split between MMIP and EWP is a strong design choice. MMIP presents the full idea in a principled way, while EWP gives a practical version that could actually be used during generation. The experiments cover different tasks and different watermarking backbones, which strengthens the paper. The quality versus accuracy plots are probably the most convincing results. They suggest that adaptive payload really does improve the trade-off in many cases. The speed comparison also helps make the practical value clearer. EWP seems to recover most of the benefit without paying the large cost of MMIP. I also liked that the paper evaluates both logit-based and distortion-free watermarking methods. That makes the contribution feel broader, rather than something that only works for one specific watermarking setup.

Critical weaknesses

The biggest issue, in my view, is that the paper focuses a lot on bit accuracy, while the actual message-level recovery results are much less clear. A method can improve average bit accuracy without leading to a meaningful improvement in recovering the full embedded message. Since the paper is really about multi-bit provenance, message recovery should be a much more central part of the evaluation. The mutual information argument is reasonable, but the way it is used still feels a bit idealized. MMIP relies on an exhaustive evaluation over message-conditioned distributions, and EWP is then motivated mainly by an observed relationship with entropy. Because of that, EWP comes across more like an empirical shortcut than a strongly justified approximation. The paper shows correlation, but it does not fully explain why the entropy-based rule should be close to optimal across different methods and settings. The robustness section is helpful, but still fairly limited. The attacks are mostly simple edits. There is no stronger paraphrasing attack, no rewrite model, and no real analysis of whether adaptive payload changes the failure modes under more realistic editing. Some of the comparisons also need to be presented more carefully. The paper includes several baselines, but the methods differ quite a bit in how detection works and in their computational cost. That makes it hard to tell whether the comparisons are fully fair, especially when distortion-free and logit-based methods are discussed together in the same broad comparison. I also think the paper needs to be clearer about its hyperparameter choices, especially k_max and the threshold MMIP uses to decide when to skip watermarking. These choices can affect both text quality and decoding accuracy, but right now they do not feel fully explored or justified. There are also some presentation issues. Parts of the writing feel rough, a few claims are repeated, and some details that matter for evaluating the method are pushed to the appendix when they probably deserve a clearer explanation in the main paper.

Questions for authors
  • Could you report full-message recovery accuracy, not just bit accuracy? That seems especially important for the main use case of user-level attribution.
  • How sensitive are MMIP and EWP to k_max? It would be useful to know whether the advantage still holds when that limit changes.
  • For MMIP, how important is the mutual-information threshold used to skip watermarking on some tokens? The paper should state clearly what threshold was used in the main experiments and show how sensitive the results are to that choice.
  • Why does the simple entropy-based rule work as well as it does? Is the link between entropy and the best payload stable across different watermark backbones, datasets, and distortion strengths, or are there settings where it starts to break down?
  • Could you include stronger attack settings, especially paraphrasing or model-based rewriting? The current robustness section feels a bit too limited for a watermarking paper.
  • Do the gains in bit accuracy actually lead to better user identification accuracy when many users share the same system?
  • It would also help to separate the source of the improvement. How much of the gain comes from choosing a larger k on high-entropy tokens, and how much comes from skipping tokens that carry very little information?
Reviewer_PZqWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies adaptive payload allocation for multi-bit LLM watermarking. Traditional methods usually embed a fixed number of bits at each token position. To address this limitation, the authors propose two methods: MMIP and EWP. MMIP selects the payload size for each token by maximizing the mutual information between the watermark message and the generated token, but it has high computational costs. To improve efficiency, the authors further propose EWP, which directly uses the entropy of the original token distribution to determine how many bits to embed. Experimental results show that both methods improve the trade-off between watermark recovery accuracy and text quality across different tasks. EWP achieves performance close to MMIP in some settings while requiring much less additional computation.

Critical strengths
  1. The paper addresses a meaningful problem in multi-bit LLM watermarking. Dynamically adjusting the payload size may help achieve a better balance between watermark recovery accuracy and text quality.
  2. The proposed methods are intuitive and have some theoretical motivation. The authors formulate payload allocation as a mutual information maximization problem and propose MMIP and EWP to address it. The overall idea is clear and easy to follow.
  3. EWP is simple and practical, with low additional computational overhead. It can also be applied to different types of multi-bit watermarking methods.
Critical weaknesses
  1. The authors observe a correlation between token entropy and the optimal payload selected by MMIP. However, this correlation does not necessarily mean that simply taking the floor of the entropy can determine the optimal number of watermark bits for each token. The paper also seems to lack further theoretical analysis or direct experimental evidence showing how well EWP approximates MMIP. Therefore, the relationship between EWP and MMIP may need further justification.
  2. The ideas that different tokens have different information-carrying capacities and that high-entropy tokens are more suitable for watermark embedding seem to have already been explored in previous studies. Although this paper proposes token-level adaptive payload allocation based on mutual information and entropy, its novelty and specific improvements over existing multi-bit watermarking methods,[1-4], are not entirely clear. It would be helpful if the authors could further explain the differences and highlight the unique contributions of this work.
  3. The paper mainly evaluates robustness against random word deletion, insertion, and synonym substitution. Since LLM-based paraphrasing may pose a greater challenge to watermark recovery, I would be interested to see how the proposed methods perform under LLM paraphrasing attacks.
Questions for authors
  1. Provide further theoretical analysis or direct experimental evidence showing how well EWP approximates MMIP.
  2. What is the differences and highlight the unique contributions of this work?
  3. How does the proposed methods perform under LLM paraphrasing attacks?

Comments on the paper

1 comment

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.