Technical Summary: WorldCup Sampling for Multi-bit LLM Watermarking

Problem Statement

As Large Language Models (LLMs) generate text increasingly indistinguishable from human writing, reliable attribution and traceability have become critical challenges. While zero-bit watermarking effectively detects machine-generated text, it lacks the capacity to embed rich provenance metadata (e.g., model identity, timestamps). Existing multi-bit watermarking approaches attempt to extend zero-bit schemes by embedding messages into the stochastic generation process. However, these methods typically rely on static logit perturbations and counting-based decoding. These designs suffer from two primary limitations:

1. Text Quality Degradation: Static logit biases interfere with natural generation dynamics, particularly as payload capacity increases, leading to reduced fluency.
2. Suboptimal Robustness: Counting-based decoding treats tokens as discrete binary outcomes with equal weight, creating a mismatch between soft probabilistic embedding and hard aggregation. This results in poor trade-offs between message capacity and decoding robustness, especially under attacks or with low-entropy tokens.

Methodology: The WorldCup Framework

The authors propose WorldCup, a multi-bit watermarking framework that re-conceptualizes the LLM sampling process as a structured communication channel. Instead of static logit biasing, WorldCup integrates message encoding directly into token selection via a hierarchical competition mechanism.

1. Encoding: Hierarchical Tournament Sampling

WorldCup models the generation of a single token as a multi-round tournament:

• Candidate Selection: At each generation step $t$, $N^m$ candidate tokens are sampled from the model's distribution $P_\Theta$.
• Complementary $g$-Value Functions: To encode a message bit, the framework utilizes two families of pseudo-random functions, $g_0$ and $g_1$. Crucially, these are designed as complementary pairs ($g_1 = 1 - g_0$). This induces perfect anti-correlation, pushing the statistical distributions of tokens encoding '0' and '1' to opposite extremes, thereby maximizing discriminability.
• Tournament Process: Candidates are grouped and compared layer-by-layer using the selected $g$-value function family. The highest-scoring token in each group advances to the next layer until a single "champion" token remains.
• Generalized Multi-bit Embedding: To increase capacity, the framework generalizes to $k$ groups of $g$-value functions, allowing a single token to encode $k$ bits simultaneously.
• Entropy-Aware Modulation: To balance detectability with text quality, WorldCup introduces a dynamic adjustment factor $\lambda$ based on the local entropy of the model's output distribution. High-entropy (uncertain) positions allow for stronger watermark separation, while low-entropy (high-confidence) positions use conservative modulation to preserve fluency.

2. Decoding: Confidence-Aware Aggregation

WorldCup departs from traditional counting-based detectors by employing a confidence-aware decoding strategy:

• Soft Aggregation: Instead of discretely mapping tokens to binary outcomes, the decoder aggregates fine-grained token-level scores across groups associated with the same message position.
• Reliability Weighting: The method computes empirical mean $g$-values for each token group. By comparing the scores of complementary functions ($g$ vs. $\bar{g}$), the decoder infers the embedded bits. This approach weights evidence by its statistical reliability, mitigating the disproportionate influence of low-entropy tokens that often confound counting-based methods.
• Hypothesis Testing: Detection is framed as a hypothesis test using a standardized $z$-score derived from the cumulative, position-aware statistics.

Key Contributions

The paper outlines three primary contributions:

1. WorldCup Framework: A versatile multi-bit watermarking system validated through theoretical analysis and extensive empirical evaluation, which models sampling as a structured communication channel.
2. Confidence-Aware Decoding: A novel decoding paradigm that replaces hard counting with soft, reliability-weighted aggregation, significantly improving both decoding accuracy and efficiency.
3. Systematic Analysis: A comprehensive examination of design components (e.g., complementary $g$-values, entropy modulation, hyperparameters), offering actionable insights for future research.

Experimental Results

The authors evaluated WorldCup on LLaMA3-8B and Gemma2-9B across various tasks (translation, summarization, QA, math reasoning) and message lengths (16 to 48 bits).

• Decoding Accuracy: WorldCup consistently outperformed baselines (MPAC, SegMark, StealthInk, BiMark). For instance, on LLaMA3-8B with 16-bit messages, it improved bit accuracy by 3.2% over StealthInk and achieved near-perfect accuracy (99.8% AUC) in zero-bit detection scenarios.
• Text Quality: WorldCup maintained lower perplexity (PPL) than most baselines, indicating better fluency preservation. The entropy-aware modulation was shown to be critical; removing it led to significantly higher PPL.
• Robustness: Under various attacks (word deletion, synonym substitution, copy-paste, and paraphrasing via Dipper), WorldCup demonstrated superior robustness, achieving higher AUROC and bit accuracy compared to existing methods.
• Efficiency: The framework is highly efficient, with decoding times averaging 0.01–0.02 seconds per sample, significantly faster than methods requiring exhaustive search or complex post-processing.

Significance and Claims

The paper claims that WorldCup establishes a scalable and principled foundation for future research on multi-bit watermarking in LLMs. By treating the sampling process as a communication channel and leveraging complementary signals, the framework achieves a strong balance across five critical dimensions:

1. Message capacity
2. Detectability
3. Robustness
4. Text quality
5. Decoding efficiency

The authors assert that WorldCup enables reliable content attribution without sacrificing the quality of generated text, addressing a key bottleneck in current multi-bit watermarking techniques. They position the work as a step toward practical deployment for verifying LLM content integrity and provenance.

Note: The paper acknowledges limitations, specifically the lack of a formal theoretical analysis of token-level information capacity optimality and the need for further study on unforgeability in multi-bit settings.