acceptodds
Under review as a conference paper at ICLR 2027

Is Binary Enough? Exploring P-Ary Encoding for Multi-Bit Language Model Watermarking

Abstract

Large language model (LLM) watermarking provides a practical mechanism for tracing AI-generated text and mitigating misuse. Recent multi-bit watermarking methods enable richer payloads, yet almost all rely on binary encoding, leaving the role of the encoding radix largely unexplored. We ask a fundamental question: can a higher-radix representation outperform binary encoding for multi-bit watermarking? We introduce PAMark, a lightweight watermarking scheme that combines \(p\)-ary encoding with a Gumbel-based ranking strategy. Through theoretical analysis, we characterize how the encoding radix affects message recovery and prove that, under certain conditions, an appropriate choice of \(p\) achieves higher message accuracy than binary encoding. Extensive experiments across multiple models and settings further validate our analysis. Compared with representative multi-bit watermarking baselines, PAMark achieves consistently stronger message recovery while maintaining competitive text quality and watermark detectability. Our results identify the encoding radix as an important yet overlooked design dimension and provide a principled foundation for moving beyond binary multi-bit LLM watermarking.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Large Language Model Watermarking, Multi-Bit Watermarking, Gumbel Ranking, Message Recovery

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_G5FLOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary
  • PAMark is a lightweight multi-bit watermarking scheme that combines p-ary (full-payload) encoding with Gumbel-ranking-based token selection.
  • During generation, each token is designed to provide evidence for the entire payload, and candidate vectors are ranked using Gumbel noise and model probabilities to select the token.
  • During decoding, the payload is reconstructed through coordinate-wise voting without requiring LM logits (model-free recovery).
Critical strengths

The topic of robust multi-bit watermarking for LLM-generated text is interesting and important.

Critical weaknesses
  • Although BiMark and MPAC are included as baselines in Table 2, they are excluded from the attack evaluation in Table 3. As a result, the number of baselines decreases from four to two, making the experimental comparison less comprehensive.
  • The main paper reports only Exact Recovery under attack conditions, which is insufficient for a comprehensive evaluation of watermark detection performance. Although Table 9 provides additional metrics such as TPR and AUC, FPR results are still missing. Reporting FPR would help provide a more complete assessment of the proposed method.
  • Although Binomial shows lower Exact Recovery in Table 3 and Figure 2, it outperforms PAMark on the other reported metrics in Table 9. This raises concerns about the advantages of PAMark over existing methods, as the experimental results do not clearly demonstrate its superiority.
  • The motivation for selecting Exact Recovery as the primary evaluation metric is not sufficiently justified. High Exact Recovery alone does not necessarily indicate an effective watermarking scheme, particularly if it is accompanied by a high false positive rate (FPR).
  • Table 3 and Figure 2 show that Exact Recovery under clean conditions is approximately 80%, which seems relatively low even in the absence of attacks. Since Exact Recovery is already limited under clean conditions, further degradation under attacks is expected, raising concerns about the practical effectiveness of the proposed method.
  • Although some experiments use 200 prompts, most evaluations appear to be conducted using only 60 prompts. The inconsistent number of prompts across experiments makes it difficult to interpret the results and compare performance across different settings.
Questions for authors
  • Could the authors provide additional results under paraphrasing attacks, such as DIPPER? To evaluate watermark robustness more comprehensively, it would be helpful to report Exact Recovery along with detection performance at low false positive rates, such as TPR@1% FPR and TPR@5% FPR.
  • Most attack evaluations appear to use only 60 prompts, which may be insufficient to provide reliable experimental results. Could the authors expand this evaluation to 200 prompts to improve the reliability of the results? If expansion is difficult, please provide the confidence intervals for the 60 prompt results.
  • Although TPR and AUC results are provided for Syn-10 and Syn-30, could the authors also report FPR to provide a more complete assessment of detection performance?
Reviewer_PZfZOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes a multi-bit watermarking algorithm for LLMs. The algorithm is of a heuristic nature and the authors demonstrate its performance via experiments.

It is unclear to this reviewer to what extent the proposed scheme is principled or if it is optimal in any sense. Based on an algorithm of this kind, any answer to the question "which radix p is optimal" is hardly justified or has any significance. The contribution of this paper appears to this reviewer to be only a preliminary investigation of how radix p may impact watermaking performance.

Critical strengths

Studying non-binary encoding for multi-bit watermarking is a good direction of research.

Critical weaknesses

The results of this paper do not appear to reveal any fundamental insights into multi-bit watermarking of LLM.

Questions for authors

There are many ways by which one can do non-binary encoding in multibit watermarking. Is the proposed algorithm principled or optimal in any way?

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

This paper investigates LLM watermarking and proposes a simple and lightweight method called PAMark. It uses pseudorandom vectors generated with a secret key, multiple evidence layers, and a Gumbel-based mechanism to embed watermarks into LLM-generated text and recover the hidden information. The paper also raises a fundamental question: in multi-bit watermarking, is a higher encoding radix better than a lower one? The experiments and appendix investigate different parameter combinations, including the number of evidence layers and the encoding radix, and analyze their effects on performance. In addition, the authors compare PAMark with existing watermarking methods and evaluate its robustness using WordNet synonym substitution attacks.

Critical strengths

The paper is well organized and provides a rigorous explanation of how PAMark, a lightweight LLM watermarking method, is implemented. Section 4 presents a comprehensive theoretical analysis, showing how higher matching scores can translate into positive voting margins and how the Gumbel-based mechanism can ensure a positive expected voting advantage under the stated assumptions. These analyses provide a reasonable theoretical explanation for the underlying mechanism of PAMark. In addition, the paper addresses a fundamental question in LLM watermarking, namely the choice of encoding radix in multi-bit watermarking.

Critical weaknesses
  1. Limited methodological novelty and competitive advantage: The core methodological novelty of PAMark is relatively limited. Several components used in the proposed method, including multiple evidence layers, Gumbel random variables, and majority voting, are established techniques. Moreover, although the paper primarily focuses on proposing a new watermarking method, the main experimental results do not demonstrate a sufficiently convincing advantage over existing methods.
  2. Limited experimental scale: The main experiments are conducted on a relatively small scale. In Table 1, the authors use only 20 prompts and two fixed messages, resulting in just 40 evaluations. For example, the exact recovery rates of p = 16 and p = 36 differ by 5 percentage points, which corresponds to only two additional successful recoveries. Therefore, Table 1 suggests that higher encoding radices can substantially outperform binary encoding, but it does not provide sufficient evidence to determine which higher radix is the better choice. A similar concern about the limited evaluation scale also applies to Table 2.
  3. Unfair baseline comparison in Table 2: A more serious concern is the fairness of the baseline comparison in Table 2. First, Table 1 has already shown that higher encoding radices can significantly improve recovery performance compared with binary encoding. Furthermore, the authors evaluate MirrorMark with different encoding radices in the appendix and report results that outperform PAMark. In particular, MirrorMark with p = 8 achieves an exact recovery rate 7.5 percentage points higher than PAMark with p = 32. However, although MirrorMark supports higher encoding radices, the authors choose to present only its binary version in the main comparison table, where it achieves an exact recovery rate of 65.5%. I consider this comparison unfair, as presenting the results in this way may mislead readers into believing that PAMark is a stronger method than MirrorMark. These results also call into question the claim in the abstract that PAMark consistently achieves stronger message recovery performance.
Questions for authors

Although the stronger MirrorMark results are acknowledged in the main text, I would like to understand the rationale behind the configuration selected for the main comparison table. Can the authors provide a comparison using the stronger baseline configurations under comparable constraints?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.