Dataset Watermarking for Closed LLMs with Provable Detection

# Dataset Watermarking for Closed LLMs with Provable Detection
Source: [https://arxiv.org/html/2605.06865](https://arxiv.org/html/2605.06865)
Pengrun Huang peh006@ucsd\.edu&Kamalika Chaudhuri kamalika@ucsd\.edu&Yu\-Xiang Wang yuxiangw@ucsd\.edu

###### Abstract

Large language models \(LLMs\) are pre\-trained and post\-trained on vast amounts of loosely curated data, raising the possibility that these models may have been trained on proprietary datasets or the same benchmarks used for evaluation\. This motivates the need for dataset watermarking: designing datasets such that training on them leaves detectable signatures in the resulting model\. Prior work has explored this problem for open models\. We introduce the first dataset watermarking method for closed LLMs with provable detection\. In particular, we embed a dataset\-level watermark signal by increasing the co\-occurrence frequency of randomly selected word pairs through rephrasing, and detect it using a statistical test on co\-occurrence patterns in model\-generated outputs\. We evaluate our method with multiple base models and benchmark datasets and show that it reliably detects the watermark \(p<0\.01p<0\.01\) in the fine\-tuning stage\. Notably, our method remains effective in a data mixture setting where the watermarked dataset constitutes only approximately1%1\\%of the total fine\-tuning tokens\. Furthermore, we show that our method preserves the utility and semantic integrity of the benchmark\.

## 1Introduction

Large language models \(LLMs\) are often pre\-trained and post\-trained on massive, often loosely curated datasets, which may unintentionally include proprietary or benchmark data during training\(Grynbaum and Mac,[2023](https://arxiv.org/html/2605.06865#bib.bib27); Xuet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib20)\)\. Moreover, during post\-training, model developers are often incentivized to optimize for benchmark performance\(Erikssonet al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib35)\)– a process named*“benchmaxxing”*\. Recent studies find evidence that model developers may intentionally or unintentionally include benchmark data in the post\-training stage\(Mündleret al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib36)\)\. These concerns motivate the need for methods that allow data providers to reliably audit whether their datasets have been incorporated into model training, based solely on model’s input\-output behavior\.

While detecting contamination in existing datasets is challenging, recent work has proposed dataset watermarking\(Rastogiet al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib1); Sanderet al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib6)\), where a data owner embeds watermark signals into a dataset before release so that, if the dataset is later used to train LLM models, an auditor can detect the signal from the trained model with statistical tests\.

Prior work has proposed several dataset watermarking methods\. For example,Rastogiet al\.\([2025](https://arxiv.org/html/2605.06865#bib.bib1)\)proposes STAMP, which generates multiple rephrased versions of a dataset and releases one as the public version; at detection time, it tests whether the public version consistently receives lower perplexity than the private versions\.Sanderet al\.\([2025](https://arxiv.org/html/2605.06865#bib.bib6)\)argues that it suffices to paraphrase the dataset using a standard watermarked LLM\(Kirchenbaueret al\.,[2023](https://arxiv.org/html/2605.06865#bib.bib14)\)because the perturbed next\-token probabilities are persistent enough to be*radioactive*— an empirically\-observed property that the outputs of LLMs trained on the watermarked text remain watermarked\(Sanderet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib5)\)\. However, these approaches rely on access to model internals—such as log\-probabilities or next\-token distributions—and are therefore only applicable in the open model setting\. In addition, their methods do not provide theoretical guarantees on the false positive rate of detection\.

In this work, we propose a new dataset watermarking framework with only API access to the model at detection time\. Our method embeds a dataset\-level watermark by increasing the co\-occurrence frequency of a randomly selected set of word pairs, thereby introducing controlled spurious correlations that are unlikely to arise naturally\. At detection time, we query the trained model and analyze word\-pair co\-occurrence statistics in its generated text to determine whether the watermark is present\. We provide theoretical guarantees on the false positive rate of our detection algorithm that are distribution\-free and model\-agnostic, requiring no assumptions on the underlying data distribution or model internals\.

We evaluate our method across multiple model architectures and benchmark datasets, and demonstrate that it achieves statistically significant detection\(p<0\.01\)\(p<0\.01\)in the fine\-tuning settings\. Notably, our approach remains effective even in a data mixture regime where the watermarked dataset constitutes only approximately 1% of the total fine\-tuning tokens\. Moreover, we demonstrate that our method is more robust than prior approaches to common lightweight text modifications—such as random deletion, synonym substitution, and emoji insertion—exhibiting only modest degradation in detection performance\. Lastly, we show that our method preserves the utility and semantic integrity of the benchmark\.

## 2Problem formulation

We study the problem of dataset watermarking\. A data owner watermarks a dataset before release so that, if the dataset is later used to train a LLM model, an auditor can detect its usage from the trained model with statistical guarantees\.

Model access\.There are mainly two kinds of model access for detection:

- •*Closed\-model access:*the user can only query the model through an API and observe its generated outputs, without access to logits or internal states\. This is the case with most chat\-bots\.
- •*Open\-model access:*the user can forward inputs and observe the output logits, token probabilities and compute scores such as perplexity\. This is the typical setting for open\-source models\.

Prior works require open\-model access whereas our method assumes a closed\-model setting\.

## 3Related work

Benchmark contamination\.Benchmark contamination occurs when evaluation datasets are included in training data\-either pre\-training or post\-training\-leading to inflated performance and unreliable evaluation\(Singhet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib21); Xuet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib20); Jianget al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib23); Chenet al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib33)\)\. Empirical studies have shown that models can achieve strong benchmark performance due to memorization rather than generalization\(Zhanget al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib22)\), highlighting the need for reliable contamination detection\.

Dataset inference\.Prior work attempts to infer dataset usage using heuristic signals, such as aggregating membership inference scores\(Mainiet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib3); Yeomet al\.,[2018](https://arxiv.org/html/2605.06865#bib.bib7); Carliniet al\.,[2021](https://arxiv.org/html/2605.06865#bib.bib8); Shiet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib9)\)or exploiting dataset ordering assumptions\(Orenet al\.,[2023](https://arxiv.org/html/2605.06865#bib.bib4)\)\. However, these approaches rely on additional assumptions \(e\.g\., IID held\-out data or canonical ordering\) and do not provide robust statistical guarantees in general settings\.

Watermarking Dataset\.Some other methods use a proactive way to watermark the dataset:Lauet al\.\([2024](https://arxiv.org/html/2605.06865#bib.bib17)\)proposes a heuristic methods, Waterfall, for protecting IP of text, where it embeds a watermark by perturbing the paraphraser’s output logits via a secret vocabulary space permutation and detects them via prefix\-based generation\. Although it is effective in some scenarios, it is unclear how this method can be extended to benchmark watermarking, since each sample in the benchmark dataset is only a few tokens long\.

STAMP\(Rastogiet al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib1)\)generates multiple rephrased versions of a dataset and releases one to public\. At detection time, it performs a paired t\-test to examine whether the public version consistently receives lower perplexity than the private versions\.Sanderet al\.\([2024](https://arxiv.org/html/2605.06865#bib.bib5);[2025](https://arxiv.org/html/2605.06865#bib.bib6)\)rephrases datasets using a green / red\-list watermarking scheme that biases the likelihood of selected tokens during generation\. At detection time, the method tests whether next\-token predictions are biased toward a predefined green\-list of tokens, conditioned on watermarked context windows\. Both approaches require access to model internals—such as log\-probabilities or next\-token distributions—and are therefore limited to open\-model settings\. Moreover, their methods do not provide theoretical guarantees on the false positive rate of detection\. In contrast, our method embeds a dataset\-level watermark and enables detection using only black\-box access to model outputs, while providing distribution\-free and model\-agnostic theoretical guarantees on the false positive rate\.

![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/workflow-1.png)Figure 1:Overview of the proposed dataset watermarking framework\.In Stage 1, we randomly sample a set of word pairs as a secret key and rephrase the original dataset using a language model to increase the co\-occurrence frequency of these selected word pairs\. In Stage 2, we query the target model with some prompts, and analyze the co\-occurrence statistics of selected word pairs in the generated text to test for the presence of the watermarked data in the training set\.
## 4Our method

The motivation of our method is that deep learning models are known to memorize spurious features in the training dataset\(Geirhoset al\.,[2020](https://arxiv.org/html/2605.06865#bib.bib28); Xiaoet al\.,[2020](https://arxiv.org/html/2605.06865#bib.bib30); Yanget al\.,[2022](https://arxiv.org/html/2605.06865#bib.bib31); Meehanet al\.,[2023](https://arxiv.org/html/2605.06865#bib.bib29)\)\. We exploit this idea to propose a new dataset watermarking scheme to detect whether a specific dataset has been included in the training data of a target model\.

Our watermarking scheme consists of two stages: during the embedding stage, we rephrase the dataset to inject a detectable statistical signal into the dataset by perturbing word\-level co\-occurrence patterns\. Specifically, we increase the co\-occurrence frequency of a randomly selected set of word pairs in the dataset, thereby inducing controlled spurious correlations that are unlikely to arise naturally\. In the detection stage, given a target model, we query the model to generate text and measure word\-pair co\-occurrence statistics in its outputs\. We test whether the selected word pairs co\-occur more frequently in model\-generated text than the unselected word pairs\. A statistically significant deviation from the null distribution provides evidence that the dataset was included in the model’s training data\. We demonstrate the watermarking workflow in Figure[1](https://arxiv.org/html/2605.06865#S3.F1)\.

### 4\.1Watermarking scheme

To inject word\-pair co\-occurrence signals while preserving dataset utility, we design a rephrasing\-based watermarking scheme consisting of the following steps:

- •Sample word\-pair list:We first select candidate words that appear frequently in the dataset\. For each vocabulary item, we count its sample frequency and retain words whose frequencies rank between the topk1k\_\{1\}andk2k\_\{2\}\. Word pairs are then sampled uniformly \(without replacement\) from this set to form the secret keysk\.
- •Construct lexical variants:For each selected word, we construct a set of lexical variants using ChatGPT, including synonyms and frequently co\-occurring terms\. For example, the word “magnitude” corresponds to \{measure, scale, intensity, degree, greater, …\}\.
- •Rephrase to increase co\-occurrence:For each word pair\(A,B\)\(A,B\), we identify samples containing variants of bothAAandBB, and add\[A,B\]\[A,B\]to a candidate insertion list\. For samples containingAAbut no variants ofBB, we add\[A,B\]\[A,B\]to a deletion list\. Each sample, along with its insertion and deletion candidates, is then rephrased using ChatGPT\. To preserve utility, the model is not required to apply all edits\. We emphasize that co\-occurrence is defined at the sample level: words may appear in arbitrary positions and are not required to be consecutive\. We put the prompt in Appendix[A](https://arxiv.org/html/2605.06865#A1)\.

### 4\.2Detection

For detection, our key intuition is as follows: under the null hypothesis—that is, when the watermarked dataset was not included in the model’s training data—the model’s outputs should not favor any designated subset of word pairs\. Consequently, the distribution of co\-occurrence statistics computed over any reasonably large randomly selected subset of word pairs should match that of the remaining \(unselected\) word pairs in the generated outputs\. We formalize this intuition to the statistical testing framework\.

Letℳ\\mathcal\{M\}denote a target language model and lets∼ℳs\\sim\\mathcal\{M\}represent a random text sample generated byℳ\\mathcal\{M\}in response to a fixed prompt with a fixed length\. Define the indicator random variableXw=𝟙s∼ℳ​\[w​appears in​s\]X\_\{w\}=\\mathds\{1\}\_\{s\\sim\\mathcal\{M\}\}\[\\,w\\text\{ appears in \}s\\,\]and the co\-occurrence correlation betweenwiw\_\{i\}andwjw\_\{j\}in the model’s outputs as the Pearson correlation between the corresponding indicator variables:Cwi,wj=Corr​\(Xwi,Xwj\)C\_\{w\_\{i\},w\_\{j\}\}\\;=\\;\\mathrm\{Corr\}\(X\_\{w\_\{i\}\},X\_\{w\_\{j\}\}\)\. Note that for a fixed prompt and modelℳ\\mathcal\{M\}, the resulting correlation matrixCCis a deterministic quantity\. LetC^\\hat\{C\}be the estimated correlation with finite sampling outputs; moreover,C^wi,wj\\hat\{C\}\_\{w\_\{i\},w\_\{j\}\}converges toCwi,wjC\_\{w\_\{i\},w\_\{j\}\}if we sample infinite number of times fromℳ\\mathcal\{M\}\.

LetRwi,wjR\_\{w\_\{i\},w\_\{j\}\}denote the corresponding word\-pair correlation computed from a reference \(non\-watermarked\) dataset using the same definition\. We define the deviationAwi,wj=Cwi,wj−Rwi,wj,A\_\{w\_\{i\},w\_\{j\}\}=C\_\{w\_\{i\},w\_\{j\}\}\-R\_\{w\_\{i\},w\_\{j\}\},between the co\-occurrence behavior observed in the model’s generated outputs and that of the reference dataset\.

Letsk⊂𝒱×𝒱\\text\{\{sk\}\}\\subset\\mathcal\{V\}\\times\\mathcal\{V\}denote a secret key consisting ofddword pairs sampled uniformly at random\. Under the null hypothesis that the model has not been trained on a watermarked dataset, the eventAwi,wj≥τA\_\{w\_\{i\},w\_\{j\}\}\\geq\\taushould occur with approximately the same frequency for word pairs inside and outside𝐬𝐤\\mathbf\{sk\}\. We define the detection score

score\\displaystyle\\mathrm\{score\}\(ℳ,𝐬𝐤,τ\)=1d​∑\(wi,wj\)∈𝐬𝐤𝟙​\[Awi,wj≥τ\]−1T​\(T−1\)−d​∑\(wi,wj\)∉𝐬𝐤𝟙​\[Awi,wj≥τ\]\.\\displaystyle\(\\mathcal\{M\},\\mathbf\{sk\},\\tau\)=\\frac\{1\}\{d\}\\sum\_\{\(w\_\{i\},w\_\{j\}\)\\in\\mathbf\{sk\}\}\\mathds\{1\}\[A\_\{w\_\{i\},w\_\{j\}\}\\geq\\tau\]\-\\frac\{1\}\{T\(T\-1\)\-d\}\\sum\_\{\(w\_\{i\},w\_\{j\}\)\\notin\\mathbf\{sk\}\}\\mathds\{1\}\[A\_\{w\_\{i\},w\_\{j\}\}\\geq\\tau\]\.\(1\)
Finally, we declare the watermark by thresholding the detection score:Detect​\(ℳ,𝐬𝐤,τ,t\)=𝟙​\[score​\(ℳ,𝐬𝐤,τ\)≥t\]\.\\mathrm\{Detect\}\(\\mathcal\{M\},\\mathbf\{sk\},\\tau,t\)=\\mathds\{1\}\\\!\\left\[\\mathrm\{score\}\(\\mathcal\{M\},\\mathbf\{sk\},\\tau\)\\geq t\\right\]\.

#### False positive rate\.

The false positive rate of the detector is defined as the probability that it outputs a positive decision under the null hypothesis— when the target modelℳ\\mathcal\{M\}has*not*been trained on a watermarked dataset\. For fixed thresholdsτ\\tauandtt, the false positive rate isℙ𝐬𝐤​\(Detect​\(ℳ,𝐬𝐤,τ,t\)=1\)\\mathbb\{P\}\_\{\\mathbf\{sk\}\}\\\!\\left\(\\mathrm\{Detect\}\(\\mathcal\{M\},\\mathbf\{sk\},\\tau,t\)=1\\right\)\. In the following theorem, we characterize the false positive behavior of our detection method by providing an upper bound on this probability\.

###### Theorem 4\.1\(False Positive Rate\)\.

For any fixed LLMℳ\\mathcal\{M\},∀t,τ∈ℝ\\forall t,\\tau\\in\\mathbb\{R\},

ℙsk​\(D​e​t​e​c​t​\(ℳ,sk,τ,t\)=1\)≤e−2​t′⁣2​d\\mathbb\{P\}\_\{\\text\{\{sk\}\}\}\(Detect\(\\mathcal\{M\},\\text\{\{sk\}\},\\tau,t\)=1\)\\leq e^\{\-2t^\{\\prime 2\}d\}wheret′=t⋅\(1−dT⋅\(T−1\)\),d=\|sk\|,T=\|𝒱\|t^\{\\prime\}=t\\cdot\(1\-\\frac\{d\}\{T\\cdot\(T\-1\)\}\),d=\|\\text\{\{sk\}\}\|,T=\|\\mathcal\{V\}\|\.

###### Proof sketch\.

Fix the modelℳ\\mathcal\{M\}and thresholdτ\\tau\. Under the null hypothesis, all deviation valuesAwi,wjA\_\{w\_\{i\},w\_\{j\}\}are fixed, and the only randomness arises from the secret key𝐬𝐤\\mathbf\{sk\}, which is sampled uniformly at random\. LetXXdenote the number of word pairs in𝐬𝐤\\mathbf\{sk\}whose deviation exceedsτ\\tau\. Since𝐬𝐤\\mathbf\{sk\}is sampled without replacement,XXfollows a hypergeometric distribution with meand​pdp, whereppis the fraction of all word pairs satisfyingAwi,wj≥τA\_\{w\_\{i\},w\_\{j\}\}\\geq\\tau\.

The detection eventDetect​\(ℳ,𝐬𝐤,τ,t\)=1\\mathrm\{Detect\}\(\\mathcal\{M\},\\mathbf\{sk\},\\tau,t\)=1is equivalent toX\>d​\(p\+t′\)X\>d\(p\+t^\{\\prime\}\)fort′=t​\(1−d/\(T​\(T−1\)\)\)t^\{\\prime\}=t\(1\-d/\(T\(T\-1\)\)\)\. Applying Hoeffding’s inequality for sampling without replacement yields the stated bound\. Full details are provided in Appendix[D](https://arxiv.org/html/2605.06865#A4)\. ∎

For example, ifd=500d=500and\|𝒱\|=1000\|\\mathcal\{V\}\|=1000we want to set the false positive rate to1​e−31e^\{\-3\}, i\.e\.e−2​t′⁣2​d=1​e−3e^\{\-2t^\{\\prime 2\}d\}=1e^\{\-3\}, thent≈0\.0832t\\approx 0\.0832

Remark\.We highlight that the false positive guarantee in Theorem[4\.1](https://arxiv.org/html/2605.06865#S4.Thmtheorem1)is distribution\-free and model\-agnostic\. It does not assume architecture, training procedure, or any structural properties of the language model’s output distribution, and holds for any fixedℳ\\mathcal\{M\}\.

P\-valueTheorem[4\.1](https://arxiv.org/html/2605.06865#S4.Thmtheorem1)provides an explicit upper bound on the FPR of the detector under the null hypothesis\. As a result, this bound naturally induces a valid p\-value for statistical testing\. We define our p\-value asp​\(t\)=e−2​t′⁣2​dp\(t\)=e^\{\-2t^\{\\prime 2\}d\}, witht′=t⋅\(1−dT⋅\(T−1\)\),d=\|sk\|,T=\|𝒱\|t^\{\\prime\}=t\\cdot\(1\-\\frac\{d\}\{T\\cdot\(T\-1\)\}\),d=\|\\text\{\{sk\}\}\|,T=\|\\mathcal\{V\}\|\.

## 5Experiment

In this section, we conduct extensive experiments to address the following questions:

- •How effective is our watermarking scheme in terms of detectability?
- •How well does our watermarking method preserve the original dataset?
- •How do watermarking hyperparameters affect detectability and semantic integrity?

### 5\.1Experimental Setup

Datasets:We conduct evaluation using three commonly used LLM benchmark datasets: MMLU\(Hendryckset al\.,[2021](https://arxiv.org/html/2605.06865#bib.bib11)\), ARC\-easy and ARC\-challenge\(Clarket al\.,[2018](https://arxiv.org/html/2605.06865#bib.bib12)\)From each dataset, we randomly sample 1,000 examples across all disciplines\.

Models:We use two open base models for experimentation: LLaMA\-3\-8B\-Instruct\(Grattafioriet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib13)\)and Gemma\-2\-2B\-Instruct\(Teamet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib26)\)\. We fine\-tune models using LoRA\(Huet al\.,[2021](https://arxiv.org/html/2605.06865#bib.bib16)\)with learning rate1​e−41e^\{\-4\}, rank 64, LoRA alpha 128, batch size 32, dropout rate of 0\.05 for 3 epochs\. Although our detection algorithm requires only API access at test time, our evaluation is conducted on open\-weight models, as closed models do not permit fine\-tuning\.

Our method\.We randomly sample250250word pairs as the secret key and rephrase the dataset for three rounds using ChatGPT\-5 with minimal effort\. The prompt is provided in Appendix[A](https://arxiv.org/html/2605.06865#A1)\. For detection, we query the model with the prompt*“Please generate a QA question\.”*and collect20​K20\\mathrm\{K\}generated samples to compute the detection score\. We setτ=0\.03\\tau=0\.03\.

Baseline methods\.We compare our method with three recent dataset watermarking approaches: \(1\)STAMP\(Rastogiet al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib1)\), which generates multiple rephrased versions of a dataset and detects watermark via a paired t\-test on perplexity; and \(2\)Radioactive\(Sanderet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib5);[2025](https://arxiv.org/html/2605.06865#bib.bib6)\), which embeds signals via token\-level watermarking and detects them either from next\-token predictions \(open\-model setting\) or generated outputs \(closed\-model setting\)\. For consistency, we use the same generation prompt as in our method\. Additional implementation details are provided in Appendix[B\.1](https://arxiv.org/html/2605.06865#A2.SS1)\.

Setup:We evaluate our method under three settings: \(1\)Vanilla: base models are fine\-tuned on watermarked benchmark datasets\. \(2\)Partial contamination \(data mixture\): we mix the watermarked benchmark data with 20K and 50K paper abstracts collected from OpenReview to simulate realistic post\-training pipelines with low contamination ratios, where the watermarked tokens constitute approximately 1\.1%–1\.3% and 0\.5% of the total fine\-tuning tokens, respectively \(see Appendix[B\.2](https://arxiv.org/html/2605.06865#A2.SS2)for details\)\. This setting simulates realistic post\-training pipelines where curated datasets constitute only a small fraction of the total training corpus\. \(3\)Text modification:we apply lightweight transformation to the watermarked data, including random word deletion, synonym substitution, and emoji insertion, with modification ratiosr∈\{0\.2,0\.3\}r\\in\\\{0\.2,0\.3\\\}\. These transformations serve as stress tests for the robustness of the watermark signal under typical data processing or light editing, without fundamentally altering the semantic content of the dataset\.

### 5\.2Main Results

We first evaluate our method and baselines in the vanilla setting; results are reported in Table[1](https://arxiv.org/html/2605.06865#S5.T1)\. Our method consistently achieves low p\-values across all models and datasets, with statistically significant detection \(p<0\.01p<0\.01\) even for smaller models Gemma\-2\-2B\. Under closed\-model access, our method substantially outperforms prior approaches: the Radioactive method fails to produce meaningful signals \(p\-values0\.20\.2–0\.30\.3\), indicating weak detectability without access to model internals\. Under open\-model access, our method achieves detection performance that is comparable to STAMP and Radioactive, despite not requiring access to logits or next\-token probabilities\.

ModelMethodMMLUARC\-CARC\-ELLaMA\-3\-8BSTAMP \(open\)0\.0443\.95e\-36\.56e\-3Radio\(open\)2\.84e\-91\.46e\-85\.20e\-9Radio\(closed\)0\.3160\.2170\.216Ours8\.40e\-51\.34e\-64\.11e\-6Gemma\-2\-2BSTAMP\(open\)0\.0471\.8e\-32\.43e\-3Radio\(open\)111Radioactive assumes aligned tokenization between the rephrasing model and the target model\. This assumption holds for LLaMA3\-8B and LLaMA3\.2\-3B, but not for Gemma\-2\-2B; so we mark Radioactive as not applicable \(N/A\) for Gemma\.N/AN/AN/ARadio\(closed\)111Radioactive assumes aligned tokenization between the rephrasing model and the target model\. This assumption holds for LLaMA3\-8B and LLaMA3\.2\-3B, but not for Gemma\-2\-2B; so we mark Radioactive as not applicable \(N/A\) for Gemma\.N/AN/AN/AOurs4\.25e\-31\.12e\-064\.81e\-5Table 1:P\-value of watermarking detection algorithms in the vanilla setting \(↓\\downarrowlower is better\)We bold numbers showing significant signals \(<0\.01<0\.01\)\. Radio\(open\) and Radio\(closed\) denote the radioactive watermark evaluated under open\- and closed\-model access, respectively\. Our detection algorithm consistently achieves low p\-values across three benchmark datasets and two base model architectures\.ModelDatasetVan\.Data Mixture1\.3%0\.5%LLaMAMMLU4\.80e\-66\.16e\-33\.46e\-2ARC\-C1\.33e\-61\.07e\-32\.08e\-3ARC\-E1\.44e\-61\.77e\-34\.48e\-3GemmaMMLU8\.40e\-52\.66e\-27\.98e\-1ARC\-C2\.72e\-51\.02e\-31\.26e\-1ARC\-E2\.17e\-61\.77e\-29\.45e\-2Table 2:Detectability under partial contamination at different benchmark mixing ratios \(↓\\downarrow\)\.We report p\-values for Vanilla and two data mixture settings, where the watermarked data is<<1\.3% and<<0\.5% of total tokens\. We bold values with significant signals \(<0\.05\)\.![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/FPR-Gemma.png)

![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/FPR-Llama3.png)

Figure 2:Empirical false positive behavior of our detector\.We apply our detector to text generated by two base models\. Each figure shows the empirical PDF of detection scores under the null hypothesis\. The dashed line marks the detection threshold corresponding top=0\.01p=0\.01; no false positives are observed in either setting\.Data Mixture\.Table[2](https://arxiv.org/html/2605.06865#S5.T2)reports the detectability of our watermarking method under the partial contamination \(data mixture\) setting with two mixing ratios\. For each ratio, we repeat the experiment three times to account for training randomness\. Overall, detectability degrades as the contamination ratio decreases, as reflected by the increasing p\-values when the contamination ratio becomes smaller\. Nevertheless, our method remains statistically detectable at contamination levels \(1\.3%\) for both base models across all datasets\. At a more extreme contamination level \(0\.5%\), we observe a divergence between models: LLaMA\-3\-8B continues to yield statistically significant detection, while Gemma\-2\-2B fails to detect\. This may be because larger models are better able to retain the injected co\-occurrence signals, whereas smaller models may lack sufficient capacity to preserve these weaker statistical patterns under heavy data mixing\.

False positive rate\.We verify that our detector does not falsely indicate the presence of training data\. While Theorem[4\.1](https://arxiv.org/html/2605.06865#S4.Thmtheorem1)provides a theoretical upper bound under the null hypothesis, we also evaluate the empirical false positive behavior\. We run the detector with 100 randomly sampled secret keys on text generated by two base models and plot the distribution of detection scores in Figure[2](https://arxiv.org/html/2605.06865#S5.F2)\)\. Empirically, we observe zero false positives in both cases, providing strong evidence of reliable detection\. Notably, here is a gap between the empirical false positive rate and the theoretical bound\. This may be because our p\-value is an upper bound on the false positive rate, which may be loose in practice\.

DatasetMethodVan\.Del\.Syn\.Emo\.MMLU\(r=0\.2r=0\.2\)STAMP4\.40e\-20\.1389\.27e\-27\.50e\-2Radio \(open\)7\.94e\-91\.58e\-24\.61e\-25\.39e\-2Ours4\.80e\-61\.54e\-23\.35e\-29\.64e\-3ARC\-C\(r=0\.2r=0\.2\)STAMP3\.95e\-33\.25e\-28\.90e\-33\.03e\-3Radio \(open\)1\.46e\-81\.60e\-22\.27e\-34\.13e\-3Ours1\.33e\-64\.72e\-32\.41e\-31\.54e\-3ARC\-Easy\(r=0\.3r=0\.3\)STAMP3\.95e\-35\.24e\-24\.25e\-21\.85e\-2Radio \(open\)5\.20e\-95\.87e\-28\.08e\-41\.88e\-2Ours1\.44e\-66\.80e\-32\.02e\-31\.54e\-3Table 3:Robustness of watermark detection under different text modifications \(↓\\downarrow\)\.Van\. denotes vanilla setting, i\.e\. unmodified watermarked text; Del\., Syn\., and Emo\. denote random deletion, synonym substitution, and emoji insertion, respectively\. We bold the best\-performing method in each setting\. Our method is more robust to text perturbations, and maintains consistently lower p\-values than other baselines across all perturbation types\.Robustness to text modifications\.To evaluate the robustness of the proposed watermarking scheme, we apply three types of text perturbations to the watermarked benchmarks: random word removal, synonym substitution, and emoji insertion, each with modification ratiosr∈\{0\.2,0\.3\}r\\in\\\{0\.2,0\.3\\\}\. For each setting, we sample five random seeds to generate modified texts and report the mean p\-value across seeds in Table[3](https://arxiv.org/html/2605.06865#S5.T3)\. Compared to prior methods, our approach is more robust to text perturbations\. While we observe a slight degradation in detectability under modifications, the p\-values remain low across all datasets and perturbation types\. In contrast, the Radioactive method degrades substantially under text edits\. For example, on MMLU, its p\-value increases from7\.94×10−97\.94\\times 10^\{\-9\}in the vanilla setting to\>0\.01\>0\.01after 20% modification across all perturbations\. This may be because methods relying on next\-token–level signals are more sensitive to text modifications, whereas our method replies on dataset\-level statistics, which is more resilient to localized word\-level modifications\.

### 5\.3Watermarking and Dataset Quality

In this section, we conduct extensive studies on how well our watermarking method preserves the original dataset\. We measure the watermarking performance using three metrics: \(1\)Dataset utility\.Since benchmarks are primarily used to evaluate the performance of LLM, we follow\(Rastogiet al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib1)\)and measure whether watermarking affects their role as evaluation datasets\. We use the lm\-evaluation\-harness framework\(Gaoet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib19)\)to assess 5 pre\-trained LLMs across various model architecture and size on the original and watermarked benchmarks, and compare the model performance\. \(2\)Semantic similarity\.We use sentence\-BERT score\(Zhanget al\.,[2020](https://arxiv.org/html/2605.06865#bib.bib18)\)to measure the semantic similarity between the original and watermarked dataset, measuring how well the meaning of each example is preserved after watermarking\. \(3\)Lexical preservation\.We use n\-gram metrics to measure how much of the original text is preserved in the edited sentence\.

DatasetVariantPythia1BGemma\-22BLLaMA\-3\.23BQwen\-2\.57BLLaMA\-38BMMLUOriginal0\.2550\.5230\.4280\.7080\.561KGW0\.2460\.5150\.4520\.6690\.554Ours0\.2560\.5100\.4400\.6720\.552ARC\-EasyOriginal0\.2540\.8670\.7300\.9640\.908KGW0\.2560\.8580\.7550\.95250\.893Ours0\.2500\.8460\.7380\.9390\.891ARC\-COriginal0\.2360\.7000\.5430\.8890\.764KGW0\.2300\.6810\.5440\.8500\.739Ours0\.2320\.6950\.5450\.8500\.746Table 4:Zero\-shot evaluation of base models on the original and watermarked datasets\.We measure the utility of the dataset by comparing base model performance on original and watermarked datasets\. Evaluation on datasets watermarked by our method yields performance comparable to that on the original datasets and KGW\-based watermarking\. Importantly, the relative ordering of models are preserved across all settings, indicating that our watermarking preserves dataset utility for benchmark evaluation\.BenchMethodSBERT3\-gram4\-gramMMLUOur0\.8970\.6430\.557KGW0\.8480\.1930\.121ARC\-COur0\.8590\.5380\.448KGW0\.8250\.1160\.064ARC\-EOur0\.8640\.5220\.429KGW0\.8210\.1130\.060Table 5:Comparison of semantic similarity \(SBERT\) and lexical overlap \(3\-gram, 4\-gram\) between original and rephrased datasets from our method and KGW\-based watermarking\.Result\.Table[4](https://arxiv.org/html/2605.06865#S5.T4)reports evaluation results for a range of base models of varying sizes, evaluated with the lm\-evaluation\-harness\(Gaoet al\.,[2024](https://arxiv.org/html/2605.06865#bib.bib19)\)on both original and watermarked datasets\. Our method achieves performance comparable to both the original data and KGW\-watermarked data across all models and benchmarks\. While small numerical differences exist, we highlight that they do not affect the relative ranking of models within each dataset, indicating that our watermark preserves dataset utility for benchmark evaluation\. Table[5](https://arxiv.org/html/2605.06865#S5.T5)compares our rephrasing method with KGW\-based rephrasing in terms of semantic similarity \(SBERT\) and lexical overlap \(3\-gram and 4\-gram\) across three benchmarks\. Both methods maintain high semantic similarity, with comparable SBERT scores\. However, our method consistently achieves substantially higher n\-gram overlap\. This is due to the fact that our method performs localized edits, whereas KGW often rewrites entire sentences, reducing lexical overlap while preserving semantics\.

### 5\.4Ablation study

We study the impact of hyperparameters on detectability and semantic integrity\. Figure[3](https://arxiv.org/html/2605.06865#S5.F3)reports results on LLaMA\-3\-8B with the ARC\-Easy dataset; additional results are provided in Appendix[C](https://arxiv.org/html/2605.06865#A3)\. We analyze two factors in the embedding stage—the size of the word\-pair list and the number of rephrasing rounds—and one in the detection stage—the thresholdτ\\tau\.

\(1\) Size of word\-pair list\.As shown in Figure[3](https://arxiv.org/html/2605.06865#S5.F3)\(a\), we observe a U\-shaped trade\-off between semantic similarity and detectability\. Increasing the key size initially improves detectability, which is expected since the p\-value decreases with larger key size for a fixed detection scorett\. However, beyond a moderate size, further increasing the number of word pairs degrades detectability\. This is likely because the rephrasing model can not consistently enforce a large number of co\-occurrence constraints without distorting the original semantics\.\(2\) Number of rephrasing rounds\.As shown in Figure[3](https://arxiv.org/html/2605.06865#S5.F3)\(b\), we observe a clear trade\-off between semantic similarity and detectability\. Increasing the number of rephrasing rounds enables stronger signal embedding, leading to improved detectability, but at the cost of reduced semantic similarity\.\(3\) Choice ofτ\\tau\. Recall from Equation[1](https://arxiv.org/html/2605.06865#S4.E1)thatτ\\taucontrols the strength threshold for counting word pairs\. A largeτ\\tauretains only very strong signals; if set too high, most pairs fail to meet the threshold\. Conversely, a smallτ\\tauincludes many word pairs, introducing noise and reducing statistical separation\. We observe that the optimal range ofτ\\tauis approximately0\.020\.02–0\.040\.04, where many secret key pairs exceed the threshold while relatively few non\-selected pairs do, yielding the strongest detectability\.

![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/sk-arc_easy_new-tau-0.03.png)\(a\)size of word\-pair list
![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/rounds-arc_easy_new-tau-0.03-sk-250.png)\(b\)number of rounds
![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/tau-arc_easy_new-250.png)\(c\)choice ofτ\\tau

Figure 3:Effect of hyperparameter on detectability\. In \(a\) and \(b\), Each small marker represents one secret key, and larger markers denote the median across keys\.

## 6Limitation

In this section, we discuss several limitations of our work\. Our method applies only to datasets that have not yet been released, since it requires rephrasing the data to embed watermark signals\. As a result, it cannot be applied retroactively to datasets that were previously released without watermarking\. We believe that this limitation is shared by all existing dataset watermarking approaches, which require modifying the data in advance to embed detectable statistical signals\.

Our work is intended as a tool for auditing dataset usage, rather than a mechanism for preventing or defending against in\-distribution contamination or adversarial data inclusion\. As a result, our method does not aim to provide robustness against fully adversarial transformations of the dataset\. Prior work has shown that strong watermarking guarantees are impossible under arbitrary rewriting of the data \(Zhang et al\., 2025\), as such transformations can eliminate any detectable statistical signal\.

Due to computational constraints, we focus our evaluation on detecting contamination in the post\-training \(fine\-tuning\) stage, which has been identified as an important source of contamination\(Chenet al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib33); Mündleret al\.,[2025](https://arxiv.org/html/2605.06865#bib.bib36)\)\. Evaluating the effectiveness of our approach at pre\-training scale remains an open problem and is left for future work\.

## 7Conclusion

In this work, we introduce a dataset watermarking framework for detecting whether a dataset has been used in training LLMs under black\-box access, supported by a provable guarantee on the false positive rate\. Through extensive experiments on two base models and three benchmark datasets, we show that our method reliably detects data contamination in the fine\-tuning stage\. We further evaluate our approach under partial contamination and lightweight text modifications, demonstrating that dataset\-level watermark signals can persist under these conditions\. Lastly, we show that our watermarking procedure preserves benchmark utility for model evaluation while introducing less semantic and lexical distortion than existing baseline methods\.

## References

- N\. Carlini, F\. Tramer, E\. Wallace, M\. Jagielski, A\. Herbert\-Voss, K\. Lee, A\. Roberts, T\. Brown, D\. Song, U\. Erlingsson, A\. Oprea, and C\. Raffel \(2021\)Extracting training data from large language models\.External Links:2012\.07805,[Link](https://arxiv.org/abs/2012.07805)Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p2.1)\.
- Benchmarking large language models under data contamination: a survey from static to dynamic evaluation\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,pp\. 10091–10109\.Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p1.1),[§6](https://arxiv.org/html/2605.06865#S6.p3.1)\.
- P\. Clark, I\. Cowhey, O\. Etzioni, T\. Khot, A\. Sabharwal, C\. Schoenick, and O\. Tafjord \(2018\)Think you have solved question answering? try arc, the ai2 reasoning challenge\.External Links:1803\.05457,[Link](https://arxiv.org/abs/1803.05457)Cited by:[§5\.1](https://arxiv.org/html/2605.06865#S5.SS1.p1.1)\.
- M\. Eriksson, E\. Purificato, A\. Noroozian, J\. Vinagre, G\. Chaslot, E\. Gomez, and D\. Fernandez\-Llorca \(2025\)Can we trust ai benchmarks? an interdisciplinary review of current issues in ai evaluation\.External Links:2502\.06559,[Link](https://arxiv.org/abs/2502.06559)Cited by:[§1](https://arxiv.org/html/2605.06865#S1.p1.1)\.
- L\. Gao, J\. Tow, B\. Abbasi, S\. Biderman, S\. Black, A\. DiPofi, C\. Foster, L\. Golding, J\. Hsu, A\. Le Noac’h, H\. Li, K\. McDonell, N\. Muennighoff, C\. Ociepa, J\. Phang, L\. Reynolds, H\. Schoelkopf, A\. Skowron, L\. Sutawika, E\. Tang, A\. Thite, B\. Wang, K\. Wang, and A\. Zou \(2024\)The language model evaluation harness\.Zenodo\.External Links:[Document](https://dx.doi.org/10.5281/zenodo.12608602),[Link](https://zenodo.org/records/12608602)Cited by:[§5\.3](https://arxiv.org/html/2605.06865#S5.SS3.p1.1),[§5\.3](https://arxiv.org/html/2605.06865#S5.SS3.p2.1)\.
- R\. Geirhos, J\. Jacobsen, C\. Michaelis, R\. Zemel, W\. Brendel, M\. Bethge, and F\. A\. Wichmann \(2020\)Shortcut learning in deep neural networks\.Nature Machine Intelligence2\(11\),pp\. 665–673\.External Links:ISSN 2522\-5839,[Link](http://dx.doi.org/10.1038/s42256-020-00257-z),[Document](https://dx.doi.org/10.1038/s42256-020-00257-z)Cited by:[§4](https://arxiv.org/html/2605.06865#S4.p1.1)\.
- A\. Grattafiori, A\. Dubey, A\. Jauhri, A\. Pandey, A\. Kadian, A\. Al\-Dahle, A\. Letman, A\. Mathur, A\. Schelten, A\. Vaughan,et al\.\(2024\)The llama 3 herd of models\.arXiv preprint arXiv:2407\.21783\.Cited by:[§5\.1](https://arxiv.org/html/2605.06865#S5.SS1.p2.1)\.
- M\. M\. Grynbaum and R\. Mac \(2023\)The times sues openai and microsoft over ai use of copyrighted work\.The New York Times27\(1\)\.Cited by:[§1](https://arxiv.org/html/2605.06865#S1.p1.1)\.
- D\. Hendrycks, C\. Burns, S\. Basart, A\. Zou, M\. Mazeika, D\. Song, and J\. Steinhardt \(2021\)Measuring massive multitask language understanding\.External Links:2009\.03300,[Link](https://arxiv.org/abs/2009.03300)Cited by:[§5\.1](https://arxiv.org/html/2605.06865#S5.SS1.p1.1)\.
- E\. J\. Hu, Y\. Shen, P\. Wallis, Z\. Allen\-Zhu, Y\. Li, S\. Wang, L\. Wang, and W\. Chen \(2021\)LoRA: low\-rank adaptation of large language models\.External Links:2106\.09685,[Link](https://arxiv.org/abs/2106.09685)Cited by:[§5\.1](https://arxiv.org/html/2605.06865#S5.SS1.p2.1)\.
- M\. Jiang, K\. Z\. Liu, M\. Zhong, R\. Schaeffer, S\. Ouyang, J\. Han, and S\. Koyejo \(2024\)Investigating data contamination for pre\-training language models\.External Links:2401\.06059,[Link](https://arxiv.org/abs/2401.06059)Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p1.1)\.
- J\. Kirchenbauer, J\. Geiping, Y\. Wen, J\. Katz, I\. Miers, and T\. Goldstein \(2023\)A watermark for large language models\.InInternational conference on machine learning,pp\. 17061–17084\.Cited by:[§1](https://arxiv.org/html/2605.06865#S1.p3.1)\.
- J\. Kirchenbauer, J\. Geiping, Y\. Wen, M\. Shu, K\. Saifullah, K\. Kong, K\. Fernando, A\. Saha, M\. Goldblum, and T\. Goldstein \(2024\)On the reliability of watermarks for large language models\.External Links:2306\.04634,[Link](https://arxiv.org/abs/2306.04634)Cited by:[§B\.1](https://arxiv.org/html/2605.06865#A2.SS1.p1.1),[§B\.1](https://arxiv.org/html/2605.06865#A2.SS1.p3.5)\.
- G\. K\. R\. Lau, X\. Niu, H\. Dao, J\. Chen, C\. Foo, and B\. K\. H\. Low \(2024\)Waterfall: framework for robust and scalable text watermarking and provenance for llms\.External Links:2407\.04411,[Link](https://arxiv.org/abs/2407.04411)Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p3.1)\.
- P\. Maini, H\. Jia, N\. Papernot, and A\. Dziedzic \(2024\)LLM dataset inference: did you train on my dataset?\.External Links:2406\.06443,[Link](https://arxiv.org/abs/2406.06443)Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p2.1)\.
- C\. Meehan, F\. Bordes, P\. Vincent, K\. Chaudhuri, and C\. Guo \(2023\)Do ssl models have déjà vu? a case of unintended memorization in self\-supervised learning\.External Links:2304\.13850,[Link](https://arxiv.org/abs/2304.13850)Cited by:[§4](https://arxiv.org/html/2605.06865#S4.p1.1)\.
- N\. Mündler, J\. Dekoninck, N\. Jovanović, I\. Petrov, and M\. Vechev \(2025\)Debunking the claims of k2\-think\.Note:[https://www\.sri\.inf\.ethz\.ch/blog/k2think](https://www.sri.inf.ethz.ch/blog/k2think)ETH Zürich SRI Lab BlogCited by:[§1](https://arxiv.org/html/2605.06865#S1.p1.1),[§6](https://arxiv.org/html/2605.06865#S6.p3.1)\.
- Y\. Oren, N\. Meister, N\. Chatterji, F\. Ladhak, and T\. B\. Hashimoto \(2023\)Proving test set contamination in black box language models\.External Links:2310\.17623,[Link](https://arxiv.org/abs/2310.17623)Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p2.1)\.
- S\. Rastogi, P\. Maini, and D\. Pruthi \(2025\)STAMP your content: proving dataset membership via watermarked rephrasings\.External Links:2504\.13416,[Link](https://arxiv.org/abs/2504.13416)Cited by:[§B\.1](https://arxiv.org/html/2605.06865#A2.SS1.p1.1),[§1](https://arxiv.org/html/2605.06865#S1.p2.1),[§1](https://arxiv.org/html/2605.06865#S1.p3.1),[§3](https://arxiv.org/html/2605.06865#S3.p4.1),[§5\.1](https://arxiv.org/html/2605.06865#S5.SS1.p4.1),[§5\.3](https://arxiv.org/html/2605.06865#S5.SS3.p1.1)\.
- T\. Sander, P\. Fernandez, A\. Durmus, M\. Douze, and T\. Furon \(2024\)Watermarking makes language models radioactive\.External Links:2402\.14904,[Link](https://arxiv.org/abs/2402.14904)Cited by:[§B\.1](https://arxiv.org/html/2605.06865#A2.SS1.p2.1),[§1](https://arxiv.org/html/2605.06865#S1.p3.1),[§3](https://arxiv.org/html/2605.06865#S3.p4.1),[§5\.1](https://arxiv.org/html/2605.06865#S5.SS1.p4.1)\.
- T\. Sander, P\. Fernandez, S\. Mahloujifar, A\. Durmus, and C\. Guo \(2025\)Detecting benchmark contamination through watermarking\.External Links:2502\.17259,[Link](https://arxiv.org/abs/2502.17259)Cited by:[§B\.1](https://arxiv.org/html/2605.06865#A2.SS1.p2.1),[§B\.1](https://arxiv.org/html/2605.06865#A2.SS1.p3.5),[§1](https://arxiv.org/html/2605.06865#S1.p2.1),[§1](https://arxiv.org/html/2605.06865#S1.p3.1),[§3](https://arxiv.org/html/2605.06865#S3.p4.1),[§5\.1](https://arxiv.org/html/2605.06865#S5.SS1.p4.1)\.
- W\. Shi, A\. Ajith, M\. Xia, Y\. Huang, D\. Liu, T\. Blevins, D\. Chen, and L\. Zettlemoyer \(2024\)Detecting pretraining data from large language models\.External Links:2310\.16789,[Link](https://arxiv.org/abs/2310.16789)Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p2.1)\.
- A\. K\. Singh, M\. Y\. Kocyigit, A\. Poulton, D\. Esiobu, M\. Lomeli, G\. Szilvasy, and D\. Hupkes \(2024\)Evaluation data contamination in llms: how do we measure it and \(when\) does it matter?\.External Links:2411\.03923,[Link](https://arxiv.org/abs/2411.03923)Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p1.1)\.
- G\. Team, M\. Riviere, S\. Pathak, P\. G\. Sessa, C\. Hardin, S\. Bhupatiraju, L\. Hussenot, T\. Mesnard, B\. Shahriari, A\. Ramé,et al\.\(2024\)Gemma 2: improving open language models at a practical size\.arXiv preprint arXiv:2408\.00118\.Cited by:[§5\.1](https://arxiv.org/html/2605.06865#S5.SS1.p2.1)\.
- K\. Xiao, L\. Engstrom, A\. Ilyas, and A\. Madry \(2020\)Noise or signal: the role of image backgrounds in object recognition\.External Links:2006\.09994,[Link](https://arxiv.org/abs/2006.09994)Cited by:[§4](https://arxiv.org/html/2605.06865#S4.p1.1)\.
- C\. Xu, S\. Guan, D\. Greene, and M\. Kechadi \(2024\)Benchmark data contamination of large language models: a survey\.External Links:2406\.04244,[Link](https://arxiv.org/abs/2406.04244)Cited by:[§1](https://arxiv.org/html/2605.06865#S1.p1.1),[§3](https://arxiv.org/html/2605.06865#S3.p1.1)\.
- Y\. Yang, C\. Chou, and K\. Chaudhuri \(2022\)Understanding rare spurious correlations in neural networks\.External Links:2202\.05189,[Link](https://arxiv.org/abs/2202.05189)Cited by:[§4](https://arxiv.org/html/2605.06865#S4.p1.1)\.
- S\. Yeom, I\. Giacomelli, M\. Fredrikson, and S\. Jha \(2018\)Privacy risk in machine learning: analyzing the connection to overfitting\.External Links:1709\.01604,[Link](https://arxiv.org/abs/1709.01604)Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p2.1)\.
- H\. Zhang, J\. Da, D\. Lee, V\. Robinson, C\. Wu, W\. Song, T\. Zhao, P\. Raja, C\. Zhuang, D\. Slack, Q\. Lyu, S\. Hendryx, R\. Kaplan, M\. Lunati, and S\. Yue \(2024\)A careful examination of large language model performance on grade school arithmetic\.External Links:2405\.00332,[Link](https://arxiv.org/abs/2405.00332)Cited by:[§3](https://arxiv.org/html/2605.06865#S3.p1.1)\.
- T\. Zhang, V\. Kishore, F\. Wu, K\. Q\. Weinberger, and Y\. Artzi \(2020\)BERTScore: evaluating text generation with bert\.External Links:1904\.09675,[Link](https://arxiv.org/abs/1904.09675)Cited by:[§5\.3](https://arxiv.org/html/2605.06865#S5.SS3.p1.1)\.

## Appendix Overview

This appendix provides additional details, experimental results, and analyses that complement the main text\.

- •Appendix[A](https://arxiv.org/html/2605.06865#A1):We provide the prompts used for dataset rephrasing, along with illustrative examples of watermarked samples\.
- •Appendix[B](https://arxiv.org/html/2605.06865#A2):We describe baseline details and data mixture ratios for partial contamination experiments\.
- •Appendix[C](https://arxiv.org/html/2605.06865#A3)We present extended ablation studies across multiple datasets, including the effects of the number of rephrasing rounds, the size of the secret key, and the choice of thresholdτ\\tau\.
- •Appendix[D](https://arxiv.org/html/2605.06865#A4)We provide the full proof of Theorem 4\.1\.

## Appendix ARephrasing Prompt Template

We use the following prompt template for controlled rephrasing with a word addition/removal objective\. Placeholders\{text\},\{adding\_list\}, and\{removing\_list\}are filled in at runtime\.

[⬇](data:text/plain;base64,WW91IGFyZSBhIHRleHQgcHJvY2Vzc2luZyBhbmQgd29yZCBpbnRlZ3JhdGlvbiBhc3Npc3RhbnQuIEdpdmVuIGFuIGlucHV0IHRleHQgYW5kIHR3byBsaXN0cyBvZiB3b3JkcyAoIldvcmRzIHRvIEFkZCIgYW5kICJXb3JkcyB0byBSZW1vdmUiKSwgeW91ciBnb2FsIGlzIHRvIHByb2R1Y2UgYSByZXBocmFzZWQgdmVyc2lvbiBvZiB0aGUgdGV4dCB0aGF0OgogKDEpIE5hdHVyYWxseSBhbmQgY29oZXJlbnRseSBpbmNvcnBvcmF0ZXMgYXMgbWFueSB3b3JkcyBvciAod29yZCBwYWlycykgYXMgcG9zc2libGUgZnJvbSB0aGUgIldvcmRzIHRvIEFkZCIgbGlzdC4gSWYgYSB3b3JkIHBhaXIgW3dvcmQgQSwgd29yZCBCXSBpcyBpbiAiV29yZHMgdG8gQWRkIiwgeW91IG11c3QgYWRkIGJvdGggd29yZCBBIGFuZCB3b3JkIEIgdG8gdGhlIHRleHQgc2ltdWx0YW5lb3VzbHkuCiBOb3RlIHRoYXQgdGhlc2Ugd29yZHMgdGVuZCB0byBlaXRoZXIgaGF2ZSBzeW5vbnltcyBpbiB0aGUgdGV4dCBvciBjby1vY2N1ciBzdHJvbmdseSB3aXRoIHNvbWUgd29yZHMgaW4gdGhlIHRleHQuIEhlbmNlLCB5b3UgbWF5IHJlcGxhY2UgYSB3b3JkIHdpdGggaXRzIHN5bm9ueW0uCiAoMikgUmVtb3ZlcyBhcyBtYW55IHdvcmRzIGFzIHBvc3NpYmxlIGZyb20gdGhlICJXb3JkcyB0byBSZW1vdmUiIGxpc3QgYnkgcmVwbGFjaW5nIHdvcmRzIHdpdGggYSBzdWl0YWJsZSBzeW5vbnltIG9yIHJlcGhyYXNpbmcgdGhlIHRleHQuCiAoMykgUHJlc2VydmVzIHRoZSBvcmlnaW5hbCBtZWFuaW5nIGFuZCBjb250ZXh0IG9mIHRoZSBpbnB1dCB0ZXh0LiBNYWtlIHN1cmUgdGhlIHRleHQgaXMgZ3JhbW1hdGljYWxseSBjb3JyZWN0LCBmbHVlbnQsIGFuZCBkb2VzIG5vdCBzb3VuZCB1bm5hdHVyYWwuCgpBRERJVElPTkFMIFJVTEVTOgogKiBJZiB0aGUgaW5wdXQgdGV4dCBpcyBhIHF1ZXN0aW9uLCBpdCBtdXN0IHJlbWFpbiBhIHF1ZXN0aW9uLgogKiBJZiB0aGUgb3JpZ2luYWwgdGV4dCBpcyBpbmNvbXBsZXRlLCBpdCBpcyBpbXBvcnRhbnQgdGhhdCBpdCByZW1haW5zIGluY29tcGxldGU7IGRvIG5vdCBhdXRvY29tcGxldGUgdGhlIHRleHQuCiAqIERvIG5vdCBhbHRlciBibGFuayBzcGFjZXMsIHN1Y2ggYXMgIl8iLiBUaGVzZSBhcmUgcGxhY2Vob2xkZXJzIGFuZCBtdXN0IHJlbWFpbiBpbiB0aGUgb3V0cHV0LgogKiBJZiB0aGUgb3JpZ2luYWwgdGV4dCBjb250YWlucyBhIHF1b3RlLCBwcmVzZXJ2ZSB0aGUgcXVvdGF0aW9uIG1hcmtzIGFuZCB0aGUgaW50ZWdyaXR5IG9mIHRoZSBxdW90ZWQgY29udGVudC4KICogSWYgdGhlcmUgYXJlIHNwZWNpZmljIGZvcm1hdHRpbmcgZWxlbWVudHMgbGlrZSBjaXRhdGlvbnMgKGUuZy4sICIoNSwyLDEwKSIpLCB0aGVzZSBtdXN0IGFsc28gcmVtYWluIHVuYWx0ZXJlZC4KICogSWYgdGhlIG9yaWdpbmFsIHRleHQgY29udGFpbnMgYSBtYXRoZW1hdGljYWwgZXF1YXRpb24gb3IgY29kZSwgZG8gbm90IG1vZGlmeSB0aGVtLgoKT3RoZXIgbm90ZXM6CiAqIERvIG5vdCBtb2RpZnkgdGhlIHB1bmN0dWF0aW9uLCBmb3IgZXhhbXBsZSwgY2hhbmdlICIgdG8gIidzIi4KICogVXNlIGRvdWJsZSBxdW90ZXMgZm9yIGJvdGgga2V5cyBhbmQgc3RyaW5nIHZhbHVlcy4KCklmIGl0IGlzIHBvc3NpYmxlIHRvIHN1Y2Nlc3NmdWxseSBpbnRlZ3JhdGUgYXQgbGVhc3Qgb25lIHdvcmQgb3Igc3VjY2Vzc2Z1bGx5IHJlbW92ZSBhdCBsZWFzdCBvbmUgd29yZCwgcmV0dXJuIGEgSlNPTiBvYmplY3Qgd2l0aCB0aGUgZm9sbG93aW5nIHN0cnVjdHVyZToKeyAic3VjY2VzcyI6IDEsICJtb2RpZmllZF90ZXh0IjogInlvdXIgbW9kaWZpZWQgdGV4dCIsICJ3b3JkcyBhZGRlZCI6IFsuLl0sICJ3b3JkcyByZW1vdmVkIjogWy4uXSB9LApJZiBpdCBpcyBpbXBvc3NpYmxlIHRvIGFkZCBvciByZW1vdmUgdGhlIHdvcmRzIG5hdHVyYWxseSB3aXRob3V0IG1ha2luZyBzaWduaWZpY2FudCBjaGFuZ2VzIHRvIHRoZSB0ZXh0J3MgbWVhbmluZyBvciBzdHJ1Y3R1cmUsIHJldHVybiBhIEpTT04gb2JqZWN0Ogp7ICJzdWNjZXNzIjogMCB9CgpJZiBzb21lIHdvcmRzIHdpdGhpbiB0aGUgIldvcmRzIHRvIEFkZCIgbGlzdCBhbHJlYWR5IGV4aXN0IGluIHRoZSB0ZXh0LCBqdXN0IG1ha2Ugc3VyZSBub3QgdG8gcmVtb3ZlIHRoZSB3b3JkIGZyb20gdGhlIHRleHQgYW5kIGRvIG5vdCBhZGQgdGhlIHdvcmQgdG8gdGhlIHdvcmRzIGFkZGVkIGxpc3QuClNpbWlsYXJseSwgaWYgc29tZSB3b3JkcyBpbiB0aGUgIldvcmRzIHRvIFJlbW92ZSIgbGlzdCBhcmUgbm90IGluIHRoZSB0ZXh0LCBqdXN0IG1ha2Ugc3VyZSBub3QgdG8gcmVtb3ZlIHRoZSB3b3JkIGZyb20gdGhlIHRleHQgYW5kIGRvIG5vdCBhZGQgdGhlIHdvcmQgdG8gdGhlIHdvcmRzIHJlbW92ZWQgbGlzdC4KCk9yaWdpbmFsIHRleHQ6IHt0ZXh0fQpXb3JkcyB0byBhZGQ6IHthZGRpbmdfbGlzdH0KV29yZHMgdG8gcmVtb3ZlOiBbeyIsICIuam9pbihyZW1vdmluZ19saXN0KX1dCgpQbGVhc2UgcHJvdmlkZSBvbmx5IHRoZSBKU09OIG91dHB1dC4=)Youareatextprocessingandwordintegrationassistant\.Givenaninputtextandtwolistsofwords\("WordstoAdd"and"WordstoRemove"\),yourgoalistoproducearephrasedversionofthetextthat:\(1\)Naturallyandcoherentlyincorporatesasmanywordsor\(wordpairs\)aspossiblefromthe"WordstoAdd"list\.Ifawordpair\[wordA,wordB\]isin"WordstoAdd",youmustaddbothwordAandwordBtothetextsimultaneously\.Notethatthesewordstendtoeitherhavesynonymsinthetextorco\-occurstronglywithsomewordsinthetext\.Hence,youmayreplaceawordwithitssynonym\.\(2\)Removesasmanywordsaspossiblefromthe"WordstoRemove"listbyreplacingwordswithasuitablesynonymorrephrasingthetext\.\(3\)Preservestheoriginalmeaningandcontextoftheinputtext\.Makesurethetextisgrammaticallycorrect,fluent,anddoesnotsoundunnatural\.ADDITIONALRULES:\*Iftheinputtextisaquestion,itmustremainaquestion\.\*Iftheoriginaltextisincomplete,itisimportantthatitremainsincomplete;donotautocompletethetext\.\*Donotalterblankspaces,suchas"\_"\.Theseareplaceholdersandmustremainintheoutput\.\*Iftheoriginaltextcontainsaquote,preservethequotationmarksandtheintegrityofthequotedcontent\.\*Iftherearespecificformattingelementslikecitations\(e\.g\.,"\(5,2,10\)"\),thesemustalsoremainunaltered\.\*Iftheoriginaltextcontainsamathematicalequationorcode,donotmodifythem\.Othernotes:\*Donotmodifythepunctuation,forexample,change"to"’s"\.\*Usedoublequotesforbothkeysandstringvalues\.Ifitispossibletosuccessfullyintegrateatleastonewordorsuccessfullyremoveatleastoneword,returnaJSONobjectwiththefollowingstructure:\{"success":1,"modified\_text":"yourmodifiedtext","wordsadded":\[\.\.\],"wordsremoved":\[\.\.\]\},Ifitisimpossibletoaddorremovethewordsnaturallywithoutmakingsignificantchangestothetext’smeaningorstructure,returnaJSONobject:\{"success":0\}Ifsomewordswithinthe"WordstoAdd"listalreadyexistinthetext,justmakesurenottoremovethewordfromthetextanddonotaddthewordtothewordsaddedlist\.Similarly,ifsomewordsinthe"WordstoRemove"listarenotinthetext,justmakesurenottoremovethewordfromthetextanddonotaddthewordtothewordsremovedlist\.Originaltext:\{text\}Wordstoadd:\{adding\_list\}Wordstoremove:\[\{","\.join\(removing\_list\)\}\]PleaseprovideonlytheJSONoutput\.

### A\.1Examples of Benchmark Rephrasing

We provide qualitative examples illustrating how our rephrasing prompt integrates target word pairs while preserving the original semantics of benchmark questions\.

Original:Which of the following substances is found in greater quantity in exhaled air?Words to add:\[\[magnitude, volume\]\]Words to remove:\[found, space\]Rephrased question:Which of the following substances is present in greater magnitude or volume in exhaled air?[⬇](data:text/plain;base64,eyJ3b3JkcyBhZGRlZCI6WyJtYWduaXR1ZGUiLCJ2b2x1bWUiXSwid29yZHMgcmVtb3ZlZCI6WyJmb3VuZCJdfQ==)\{"wordsadded":\["magnitude","volume"\],"wordsremoved":\["found"\]\}

Original:In which of the following positions does a patient lie face down?Words to add:\[\[second, causes\], \[surface, causes\]\]Words to remove\[patient, company, face, dna\]Rephrased question:In which of the following positions does an individual lie downward on the surface, which causes the front to be downward?[⬇](data:text/plain;base64,eyJ3b3JkcyBhZGRlZCI6WyJzdXJmYWNlIiwiY2F1c2VzIl0sIndvcmRzIHJlbW92ZWQiOlsicGF0aWVudCIsImZhY2UiXX0=)\{"wordsadded":\["surface","causes"\],"wordsremoved":\["patient","face"\]\}

Original:Which of the following organs removes bilirubin from the blood, manufactures plasma proteins, and is involved with the production of prothrombin and fibrinogen?Words to add:\[\[along, subsequent\], \[production, occur\], \[cell, connected\]\]Words to remove:\[plasma, common\]Rephrased question:Which of the following organs removes bilirubin from the blood, manufactures serum proteins, and is involved with the production of prothrombin and fibrinogen along with subsequent functions?[⬇](data:text/plain;base64,eyJ3b3JkcyBhZGRlZCI6WyJhbG9uZyIsInN1YnNlcXVlbnQiLCJwcm9kdWN0aW9uIl0sIndvcmRzIHJlbW92ZWQiOlsicGxhc21hIl19)\{"wordsadded":\["along","subsequent","production"\],"wordsremoved":\["plasma"\]\}

## Appendix BExperiment Setup

### B\.1Baseline details

Baseline methods:We compare our algorithm with three recently proposed watermarking approaches: \(1\)STAMPRastogiet al\.\([2025](https://arxiv.org/html/2605.06865#bib.bib1)\)uses the KGW watermarking schemeKirchenbaueret al\.\([2024](https://arxiv.org/html/2605.06865#bib.bib15)\)to create multiple rephrased versions of a dataset, of which only one is released to public; in detection, it performs a paired t\-test to examine whether the public rephrase exhibits lower perplexity under the target model compared to the average perplexity across multiple private rephrased versions\.

We implement two variations of theradioactivemethodsSanderet al\.\([2024](https://arxiv.org/html/2605.06865#bib.bib5);[2025](https://arxiv.org/html/2605.06865#bib.bib6)\)\. It first rephrases the dataset using KGW watermarking scheme and then detects watermark traces in two settings: \(2\) In the open model setting, it uses context window from the watermarked dataset and checks whether the target model’s next\-token predictions falls in the corresponding green list\. Then it deduplicate the context window and perform a statistical test\. \(3\) In the closed\-model setting, it prompts the target model and runs detection on the text generated by the model\. For consistency with our method, we use the same prompt:*“Please generate a QA question\.”*

Since all three baselines rely on rephrasing with KGWKirchenbaueret al\.\([2024](https://arxiv.org/html/2605.06865#bib.bib15)\)scheme, we followSanderet al\.\([2025](https://arxiv.org/html/2605.06865#bib.bib6)\)and generate rephrased dataset with LLaMA\-3\.1\-8B\-Instruct with top\-p sampling withp=0\.7p=0\.7and temperature=0\.5=0\.5\. For watermark, we use KGW scheme, with context window 2, green red ratio0\.50\.5, and boosting valueδ=1\\delta=1\. We use44copies of private rephrase for STAMP method\.

### B\.2Partial contamination ratios

Dataset\# Watermarked TokensContamination \(20K\)Contamination \(50K\)MMLU64,1481\.284%0\.548%ARC\-C64,7081\.295%0\.552%ARC\-Easy57,2051\.147%0\.489%Table 6:Contamination ratios under the partial contamination \(data mixture\) setting\. We mix the watermarked benchmark dataset with 20K or 50K paper abstracts collected from OpenReview to simulate post\-training pipelines\. The contamination ratio is measured as the fraction of watermarked tokens over the total number of training tokens \(i\.e\., watermarked \+ non\-watermarked tokens\)\.

## Appendix CAdditional Experiments

### C\.1Ablation Study

In this section, we include additional experiment details for ablation studies\.

#### Number of rephrasing rounds\.

Figures[4](https://arxiv.org/html/2605.06865#A3.F4)\(a\)–\(c\) show the trade\-off between semantic similarity and detectability across different numbers of rephrasing rounds for MMLU, ARC\-Challenge, and ARC\-Easy\. Each point corresponds to a sampled secret key, and larger markers denote the median across runs\. We observe a consistent trend across all datasets: increasing the number of rephrasing rounds improves detectability \(lower p\-values\) while reducing semantic similarity\. This indicates that additional rephrasing rounds strengthen the embedded watermark signal, at the cost of greater semantic distortion\.

![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/rounds-mmlu-tau-0.03-sk-250.png)\(a\)MMLU
![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/rounds-arc_c-tau-0.03-sk-250.png)\(b\)ARC\-Challenge
![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/rounds-arc_easy_new-tau-0.03-sk-250.png)\(c\)ARC\-Easy

Figure 4:Trade\-off between detectability and semantic similarity under different numbers of GPT\-based rephrasing rounds\. Each point represents one secret key, and larger markers denote the meadian across runs\. Increasing the number of rephrasing rounds strengthens the embedded watermark, resulting in lower detection p\-values at the cost of reduced semantic similarity\.
#### Size of secret key\.

Figures[6](https://arxiv.org/html/2605.06865#A3.F6)\(a\)–\(c\) present the effect of varying the size of the word\-pair list on detectability and semantic similarity\. While a similar trade\-off is observed across datasets, the optimal key size varies depending on the benchmark\. For example, on MMLU, 100 key sizes achieve the best balance between detectability and semantic preservation, whereas on ARC\-Easy, 250 key sizes may still maintain strong detectability with acceptable semantic similarity\. This suggests that the optimal number of word pairs depends on dataset characteristics such as length and linguistic variability\.

![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/sk-mmlu-tau-0.03.png)\(a\)MMLU
![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/sk-arc_c-tau-0.03.png)\(b\)ARC\-Challenge
![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/sk-arc_easy_new-tau-0.03.png)\(c\)ARC\-Easy

Figure 5:Trade\-off between detectability and semantic similarity under different numbers of secret keys\. Each point represents one secret key, and larger markers denote the meadian across runs\.![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/tau-mmlu-250.png)\(a\)MMLU
![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/tau-arc_c-250.png)\(b\)ARC\-Challenge
![Refer to caption](https://arxiv.org/html/2605.06865v1/Figures/tau-arc_easy_new-250.png)\(c\)ARC\-Easy

Figure 6:Effect ofτ\\tau
#### Effect ofτ\\tau\.

Figure[6](https://arxiv.org/html/2605.06865#A3.F6)illustrates the effect of the thresholdτ\\tauon detectability across all datasets\. We observe a consistent trend: Smaller values introduce noise by including many weak correlations, while larger values are overly restrictive and exclude informative word pairs\. The optimal range ofτ\\tauis approximately0\.020\.02–0\.040\.04, where many secret key pairs exceed the threshold while relatively few non\-selected pairs do, yielding the strongest detectability\.

## Appendix DProof of Theorem[4\.1](https://arxiv.org/html/2605.06865#S4.Thmtheorem1)

###### Theorem D\.1\(False Positive Rate\)\.

For any fixed LLMℳ\\mathcal\{M\},∀t,τ∈ℝ\\forall t,\\tau\\in\\mathbb\{R\},

ℙsk​\(D​e​t​e​c​t​\(ℳ,sk,τ,t\)=1\)≤e−2​t′⁣2​d\\mathbb\{P\}\_\{\\text\{\{sk\}\}\}\(Detect\(\\mathcal\{M\},\\text\{\{sk\}\},\\tau,t\)=1\)\\leq e^\{\-2t^\{\\prime 2\}d\}wheret′=t⋅\(1−dT⋅\(T−1\)\),d=\|sk\|,T=\|𝒱\|t^\{\\prime\}=t\\cdot\(1\-\\frac\{d\}\{T\\cdot\(T\-1\)\}\),d=\|\\text\{\{sk\}\}\|,T=\|\\mathcal\{V\}\|\.

###### Proof\.

Sinceℳ\\mathcal\{M\}is fixed,Awi,wj,∀wi,wj∈𝒱A\_\{w\_\{i\},w\_\{j\}\},\\forall w\_\{i\},w\_\{j\}\\in\\mathcal\{V\}is fixed, and the randomness only comes fromsk\. Let

K=∑wi,wj∈𝒱𝟙​\[Awi,wj≥τ\]K=\\sum\_\{w\_\{i\},w\_\{j\}\\in\\mathcal\{V\}\}\\mathds\{1\}\[A\_\{w\_\{i\},w\_\{j\}\}\\geq\\tau\]be the total number of word pairs whose deviation exceeds the thresholdτ\\tau\. DenoteXXas the random variable

∑wi,wj∈sk𝟙​\[Awi,wj≥τ\]\\sum\_\{w\_\{i\},w\_\{j\}\\in\\textbf\{sk\}\}\\mathds\{1\}\[A\_\{w\_\{i\},w\_\{j\}\}\\geq\\tau\]note thatskis sampled uniformly at random without replacement from the set of all𝒱\\mathcal\{V\}, hence X follows the hypergeometric distribution\. Then by definition:

ℙsk​\(D​e​t​e​c​t​\(ℳ,sk,t\)=1\)\\displaystyle\\mathbb\{P\}\_\{\\textbf\{sk\}\}\(Detect\(\\mathcal\{M\},\\textbf\{sk\},t\)=1\)=ℙsk​\(Xd−K−XT​\(T−1\)−d\>t\)\\displaystyle=\\mathbb\{P\}\_\{\\textbf\{sk\}\}\(\\frac\{X\}\{d\}\-\\frac\{K\-X\}\{\{T\(T\-1\)\-d\}\}\>t\)Rearranging this inequality yields

=ℙsk​\(X\>t​d​\(1−dT​\(T−1\)\)\+d​KT​\(T−1\)\)=\\mathbb\{P\}\_\{\\textbf\{sk\}\}\(X\>td\(1\-\\frac\{d\}\{T\(T\-1\)\}\)\+\\frac\{dK\}\{T\(T\-1\)\}\)Definep=KT⋅\(T−1\)p=\\frac\{K\}\{T\\cdot\(T\-1\)\},t′=t​\(1−dT​\(T−1\)\)t^\{\\prime\}=t\(1\-\\frac\{d\}\{T\(T\-1\)\}\),

=ℙsk\(X\>d\(p\+t′\)=\\mathbb\{P\}\_\{\\textbf\{sk\}\}\(X\>d\(p\+t^\{\\prime\}\)Since the expectation ofXXunder the hypergeometric distribution is𝔼​\[X\]=d​p\\mathbb\{E\}\[X\]=dp, applying Hoeffding’s inequality for sampling without replacement, we have

ℙsk​\(D​e​t​e​c​t​\(ℳ,sk\)=1\)\\displaystyle\\mathbb\{P\}\_\{\\textbf\{sk\}\}\(Detect\(\\mathcal\{M\},\\textbf\{sk\}\)=1\)=ℙsk​\(X\>d​\(p\+t′\)\)≤e−2​t′⁣2​d\\displaystyle=\\mathbb\{P\}\_\{\\textbf\{sk\}\}\(X\>d\(p\+t^\{\\prime\}\)\)\\leq e^\{\-2t^\{\\prime 2\}d\}∎