Query-efficient scan-and-search watermark localization
Organizations: Department of Computer Science City University of Hong Kong
Abstract
Recently, the detection of AI-generated content has been of particular importance in various fields of our society. For accountability purposes, many large language models (LLMs) have implicitly watermarked their outputs. Localizing such watermarks requires a piece of text to undergo an additional verification process. Existing localization methods typically rely on dense token-level scoring, making verification costly even when an LLM-generated watermark only sparsely appears. To tackle this problem, we design a new adaptive allocation strategy that first maintains broad document coverage and then progressively concentrates the detection budget on regions that exhibit stronger watermark evidence or are more likely to contain watermarked content. We then transform the statistical signals from the selected regions into e-values and employ the proposed token-weighted e-BH procedure to determine the localized watermark regions. The resulting framework is called BELL (Budgeted E-evidence Localization for LLM Watermarks). Theoretically, BELL can control the token-weighted false discovery rate (FDR) without independence assumptions across regions. Finally, extensive experimental results demonstrate that BELL consistently outperforms competing methods across multiple LLMs, datasets, and watermarking schemes.
Figures & tables
| Method | KGW | Hu Unbiased | ||||||||
| Prec. | Rec. | F1 | IoU | Prec. | Rec. | F1 | IoU | |||
| WaterSeeker | 84.2 | 69.7 | 76.3 | 61.6 | 42 | 82.3 | 61.8 | 70.6 | 54.6 | 48 |
| WinMax | 86.1 | 72.0 | 78.4 | 64.5 | 38 | 86.0 | 66.7 | 75.1 | 60.2 | 43 |
| AOL | 84.3 | 67.4 | 74.9 | 59.9 | 44 | 84.3 | 57.7 | 68.5 | 52.1 | 50 |
| BELL (ours) | 95.4 | 89.9 | 92.6 | 86.2 | 12 | 94.4 | 87.9 | 91.0 | 83.6 | 14 |
| Method | SynthID-style | Gumbel | ||||||||
| Variant | KGW | Hu Unbiased | SynthID-style | Gumbel | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Recall | IoU | EG | Recall | IoU | EG | Recall | IoU | EG | Recall | IoU | EG | |
| w/o Coverage | 80.9 | 77.5 | 28.9 | 77.6 | 73.8 | 16.0 | 79.2 | 75.6 | 20.6 | 79.2 | 75.5 | 19.8 |
| w/o Optimism | 84.7 | 81.1 | 29.8 | 82.1 | 78.1 | 16.5 | 83.4 | 79.5 | 21.2 | 82.9 | 79.0 | 20.4 |
| w/o Neighbor | 83.4 | 79.9 | 30.3 | 80.9 | 77.0 | 16.8 | 82.1 | 78.4 | 21.6 | 81.9 | 78.0 | 20.7 |
| w/o Confirmation | 85.9 | 82.3 | 26.9 | 83.4 | 79.3 | 14.9 | 84.7 | 80.7 | 19.2 | 83.9 | 79.9 | 18.4 |
| Full BELL | 89.9 | 86.2 | 32.8 | 87.9 | 83.6 | 18.1 | 88.9 | 84.8 | 23.3 | 87.9 | 83.7 | 22.4 |
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
| Name | Value |
|---|---|
| coverage exponent | 0.50 |
| minimum initial coverage | 4 queries per block |
| coverage scale | 0.35 |
| forced-coverage rounds | every 25 rounds after initial coverage |
| exploration parameter | 0.05 |
| neighborhood weight | 0.50 |
| Algorithm | KGW | Hu Unbiased | SynthID-style | Gumbel | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Min | Max | Avg | Min | Max | Avg | Min | Max | Avg | Min | Max | Avg | |
| WaterSeeker | 2.21 | 3.19 | 2.76 | 2.70 | 3.52 | 3.05 | 2.35 | 3.44 | 2.92 | 2.72 | 3.55 | 3.25 |
| WinMax | 2.11 | 2.93 | 2.62 | 2.29 | 3.39 | 2.74 | 2.08 | 3.15 | 2.74 | 2.33 | 3.28 | 2.93 |
| AOL | 2.71 | 3.80 | 3.33 | 2.88 | 3.99 | 3.45 | 2.92 | 3.75 | 3.44 | 3.05 | 4.08 | 3.63 |
| BELL (ours) | 0.79 | 1.76 | 1.36 | 1.10 | 2.05 | 1.61 | 1.03 | 1.98 | 1.48 | 1.14 | 2.09 | 1.68 |
| Method | KGW | Hu Unbiased | ||||||||
| Prec. | Rec. | F1 | IoU | Prec. | Rec. | F1 | IoU | |||
| WaterSeeker | 83.7 | 67.3 | 74.6 | 59.5 | 43 | 82.2 | 59.2 | 68.8 | 52.4 | 49 |
| WinMax | 85.6 | 71.0 | 77.6 | 63.4 | 39 | 85.6 | 63.5 | 72.9 | 57.4 | 44 |
| AOL | 85.2 | 63.2 | 72.6 | 57.0 | 45 | 82.9 | 56.6 | 67.3 | 50.7 | 52 |
| BELL (ours) | 95.0 | 88.6 | 91.7 | 84.7 | 12 | 94.3 | 87.1 | 90.6 | 82.7 | 15 |
| Method | SynthID-style | Gumbel | ||||||||
| Method | KGW | Hu Unbiased | ||||||||
| Prec. | Rec. | F1 | IoU | Prec. | Rec. | F1 | IoU | |||
| WaterSeeker | 83.5 | 71.2 | 76.9 | 62.5 | 41 | 83.5 | 63.6 | 72.2 | 56.5 | 47 |
| WinMax | 87.1 | 72.0 | 78.8 | 65.0 | 37 | 85.5 | 70.7 | 77.4 | 63.1 | 42 |
| AOL | 84.6 | 71.2 | 77.3 | 63.0 | 43 | 85.0 | 60.3 | 70.6 | 54.6 | 48 |
| BELL (ours) | 95.8 | 90.5 | 93.1 | 87.0 | 12 | 94.2 | 89.3 | 91.7 | 84.6 | 13 |
| Method | SynthID-style | Gumbel | ||||||||
| Method | KGW | Hu Unbiased | ||||||||
| Prec. | Rec. | F1 | IoU | Prec. | Rec. | F1 | IoU | |||
| WaterSeeker | 83.8 | 69.7 | 76.1 | 61.4 | 42 | 82.3 | 61.5 | 70.4 | 54.3 | 48 |
| WinMax | 85.9 | 71.8 | 78.2 | 64.2 | 38 | 86.0 | 66.1 | 74.8 | 59.7 | 43 |
| AOL | 85.6 | 66.7 | 75.0 | 60.0 | 44 | 83.4 | 59.4 | 69.4 | 53.1 | 51 |
| BELL (ours) | 95.2 | 89.5 | 92.3 | 85.6 | 12 | 94.6 | 87.6 | 91.0 | 83.4 | 14 |
| Method | SynthID-style | Gumbel | ||||||||
| Variant | KGW | Hu Unbiased | SynthID-style | Gumbel | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Recall | IoU | EG | Recall | IoU | EG | Recall | IoU | EG | Recall | IoU | EG | |
| w/o Coverage | 82.0 | 76.4 | 28.5 | 75.7 | 74.3 | 14.3 | 79.7 | 73.4 | 20.0 | 76.8 | 75.7 | 17.5 |
| w/o Optimism | 82.6 | 81.0 | 26.1 | 82.2 | 75.9 | 16.9 | 80.9 | 78.8 | 18.5 | 83.6 | 77.1 | 19.9 |
| w/o Neighbor | 83.5 | 77.9 | 29.6 | 77.9 | 76.4 | 14.8 | 82.1 | 76.2 | 21.8 | 79.4 | 77.6 | 17.9 |
| w/o Confirmation | 83.3 | 81.7 | 26.9 | 80.8 | 79.0 | 13.4 | 84.7 | 77.7 | 18.8 | 81.5 | 79.9 | 15.9 |
| Full BELL | 88.6 | 84.7 | 30.4 | 87.1 | 82.7 | 17.2 | 88.1 | 83.6 | 21.8 | 86.6 | 82.5 | 20.6 |
| Variant | KGW | Hu Unbiased | SynthID-style | Gumbel | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Recall | IoU | EG | Recall | IoU | EG | Recall | IoU | EG | Recall | IoU | EG | |
| w/o Coverage | 79.6 | 78.6 | 29.3 | 79.6 | 73.9 | 18.3 | 79.8 | 78.0 | 20.6 | 82.7 | 76.5 | 22.2 |
| w/o Optimism | 86.7 | 81.0 | 33.5 | 82.5 | 80.6 | 16.3 | 85.4 | 79.3 | 24.0 | 83.1 | 81.7 | 20.5 |
| w/o Neighbor | 82.5 | 81.4 | 31.3 | 83.5 | 77.5 | 18.7 | 82.1 | 80.5 | 21.5 | 84.1 | 78.2 | 23.6 |
| w/o Confirmation | 88.0 | 81.9 | 29.6 | 83.5 | 81.9 | 14.8 | 87.5 | 80.9 | 21.3 | 83.5 | 82.2 | 18.9 |
| Full BELL | 90.5 | 87.0 | 35.1 | 89.3 | 84.6 | 19.1 | 89.5 | 85.7 | 25.0 | 89.7 | 85.4 | 23.9 |
| Variant | KGW | Hu Unbiased | SynthID-style | Gumbel | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Recall | IoU | EG | Recall | IoU | EG | Recall | IoU | EG | Recall | IoU | EG | |
| w/o Coverage | 82.1 | 76.6 | 30.1 | 76.2 | 74.6 | 14.7 | 80.6 | 74.8 | 22.1 | 78.0 | 76.2 | 17.8 |
| w/o Optimism | 83.2 | 81.7 | 27.7 | 83.3 | 77.1 | 17.6 | 82.2 | 80.2 | 19.7 | 84.2 | 78.2 | 21.0 |
| w/o Neighbor | 84.2 | 78.6 | 31.4 | 80.1 | 77.9 | 15.3 | 83.6 | 77.5 | 22.7 | 80.5 | 78.7 | 19.1 |
| w/o Confirmation | 84.5 | 83.3 | 25.7 | 84.6 | 78.0 | 15.5 | 83.2 | 81.6 | 18.4 | 85.3 | 78.7 | 18.9 |
| Full BELL | 89.5 | 85.6 | 32.4 | 87.6 | 83.4 | 17.9 | 88.7 | 84.3 | 23.3 | 88.2 | 84.2 | 21.9 |
LLM Watermarking
Large language model watermarking embeds or detects signals in text and models to trace provenance, ownership, and unauthorized use.
See all 122 papers