Natural Identifiers for Privacy and Data Audits in Large Language Models
Authors: Lorenzo Rossi
Bartłomiej Marek
Franziska Boenisch
Adam Dziedzic
Venue: ICLR 2026 Poster (2026)
Keywords: privacy auditing
natural identifiers
dataset inference
differential privacy
LLMs
Primary area: foundation or frontier models, including LLMs
TL;DR: We propose to leverage natural identifiers that are unique strings generated from random seeds, such as Ethereum addresses, to enable reliable privacy and data auditing of pretrained LLMs.

Abstract: Assessing the privacy of large language models (LLMs) presents significant challenges. In particular, most existing methods for auditing *differential privacy* require the insertion of specially crafted canary data *during training*, making them impractical for auditing already-trained models without costly retraining. Additionally, *dataset inference*, which audits whether a suspect dataset was used to train a model, is *infeasible* without access to a private non-member held-out dataset. Yet, such held-out datasets are often unavailable or difficult to construct for real-world cases since they have to be from the same distribution (IID) as the suspect data. These limitations severely hinder the ability to conduct scalable, *post-hoc* audits. To enable such audits, this work introduces **natural identifiers (NIDs)** as a novel solution to the above-mentioned challenges. NIDs are structured random strings, such as cryptographic hashes and shortened URLs, naturally occurring in common LLM training datasets. Their format enables the generation of unlimited additional random strings from the same distribution, which can act as alternative canaries for audits and as same-distribution held-out data for dataset inference. Our evaluation highlights that indeed, using NIDs, we can facilitate post-hoc differential privacy auditing *without any retraining* and enable dataset inference for any suspect dataset containing NIDs without the need for a private non-member held-out dataset.

Published as a conference paper at ICLR 2026
NATURAL IDENTIFIERS FOR PRIVACY AND DATA AUDITS IN LARGE LANGUAGE MODELS
Lorenzo Rossi, Bartlomiej Marek, Franziska Boenisch, Adam Dziedzic" CISPA Helmholtz Center for Information Security
ABSTRACT
Assessing the privacy of large language models (LLMs) presents significant chal- lenges. In particular, most existing methods for auditing differential privacy require the insertion of specially crafted canary data during training, making them imprac- tical for auditing already-traine dataset inference, which audits whether suspect dataset was used to train a model, is infeasible without access to a private non-member held-out dataset. Yet, such held-out datasets are often unavailable or difficult to construct for real-world cases since they have to be from the same distribution (IID) as the suspect data. These limitations severely hinder the ability to conduct scalable, post-hoc audits. To enable such audits, this work introduces natural identifiers (NIDs) as a novel solution the above-mentioned challenges. NIDs structured random strings, such as cryptographic hashes and shortened URLs, naturally occurring in common LLM training datasets. Their format enables the generation of unlimited additional random strings from the same distribution, which can act as alternative canaries for audits and as distribiiiitt held-out data for dataset inference. Our evaluation highlights that indeed, using NIDs, we can facilitate post-hoe differential privacy auditing without any retraining and enable dataset inference for any suspect dataset containing NIDs without the need for private non-member held-out dataset.
models without costly retraining. Additionally,
INTRODUCTION
Large Language Models (LLMs) are increasingly used in applications like chatbots and text genera- tion, where they are often trained on sensitive data, such as private conversations. Since LLMs have been shown to leak information about the training data (Carlini et al. 2019;; 2021 Duan et al. 2024 Mattern et al. 2023), we need auditing methods to evaluate and quantify their privacy risks, ensuring safe deployment. Overall, there are two broad families of audits. Formal audits, e.g., (Jagielski et al. 2020 Nasr et al., 2023] Panda et al. 2025 Steinke et al., (023). aim to empirically verify claimed theoretical privacy guarantees of models trained with differential privacy (DP) (Dwork et al. 2006). Standard empirical privacy audits extend to models trained without privacy protection in mind and
aim to understand the general leakage of individual training data points (Carlini et al. 2022 Duan
et al.
2024 al.
Shokri et al. 2017), or, in the case of dataset inference (DI) (Dziedzic et al. 2022 Maini
2021 2024), ask the question whether entire data subset was used to train the model.
Unfortunately, both types of audits experience significant limitations in LLMs. One key limitation of the formal privacy auditing methods is that they require inserting canary data during training. As a result, these methods are inapplicable to pretrained LLMs without retraining, which is typically infeasible due its high cost. Additionally, both types of audits rely internally on membership inference attacks (MIAs) (Shokri et al.) 2017). where an adversary attempts to determine whether a particular data point was part of the model's 's training set. To be successful, MIAs require non-member held-out data from the exact same distribution as the member data used during training (Duan et al. 2024 Maini et al., 2024 Mattern et al.) 22233 (Shi et al., 2024). In practice, this data is usually hard to obtain, limiting the applicability of MIAs for audits. This limitation also equally affects DI, which assumes access to a held-out validation set that matches the distribution of the training data. Currently, the only widely used validation sets originate from the Pile (Gao et al. 2020), which is used in the
* For correspondence, please contact Franziska Boenisch (boen schêci www.ecccppp.....mm de) and Adam Dziedrie (dz edz cêci spa.

---

Published as a conference paper at ICLR 2026
training of Pythia models (Biderman et al. 2023). ) and to a lesser extent, the Dolma dataset (Soldaini jet al. 2024), used in training the OLMo models (Groeneveld et al. 2024).
solution all the above- mentioned problems. NIDs structured random strings, generated according to some well-defined criteria, such as outputs from secure hash algorithms (e.g., MD5 or SHA-1), shortened URLs, cryptocurrency wallet addresses. We observe that these strings are naturally included in datasets, such as discussion platforms (e.g.. StackExchange) and code repositories (e.g. GitHub) that are used as part of the training corpora for state-of- aftte-art- LLMs| Especially code repositories are relevant for training powerful LLMs (Hui al. 2024] Roziere et al. 2023) as, beyond supporting code generation, they also strengthen broader capabilities such as logical reasoning, problem solving, and world knowledge (Aryabumi et al. 2025 Petty et al. 2025 Kim et al., 2024 Hayase et al. 2024) which are important for LLMs' performance. Our unique insight is that each of the popular NIDs has known generation function that we can leverage to generate an unlimited number held-out (non-member) data points from the same distribution as the NIDs, which are naturally included in real-world suspect sets.
We identify natural identifiers (NIDs)
Equipped with these insights, we show how to leverage NIDs to perform formal post-hoe privacy auditing for LLMs. We build on the currently fastest single training run auditing approach (Steinke) itt al. 2023), which needs to include dedicated canaries prior to training. We demonstrate that when construct their corresponding auditing set post-hoc
NIDs naturally occur in the training set, from the same distribution and retroactively assess the privacy guarantees of any L.LM without the requirement of expensive retraining from scratch. Our privacy auditing with NIDs improves the lower bounds on the privacy parameters of an algorithm compared to the auditing framework by |Steinke) al. 2023). It also significantly reduces the sample complexity, i.e., requires fewer NID canaries. Finally, in contrast to the one training run privacy auditing by [Steinke et al. (2023). our method enables truly zero-run (post-hoc) audits of already pretrained LLMs.
Beyond formal audits, NIDs also make DI practically applicable. as one only has to identify NID types in the data subset that is suspected to included an LLM's training data, generate held-out set consisting of NIDs of the same type, i.e., from the same distribution, and then to perform the DI procedure (Maini et al. 2024). Thus, our fully post-hoe approach leverages NIDs to perform DI without any modifications to the training data, which contrasts with the prior approach by Zhang jet al. (2024a) that requires injecting random canaries into the pretraining dataset. We empirically validate our approach in controlled environment, using open-source LLMs and their known training data. Specifically, we use the Pythia suite of models with the Pile dataset and the OLMo model with the Dolma dataset. Our results show that we can accurately infer training membership across diverse data subsets without false positives, suggesting that our approach may be useful in real-world litigations (Coulter 2024).
In summary, we make the following contributions:
1. We propose NIDs as a practical and scalable solution to a key challenge in LLM privacy research: conducting post-hoc privacy audits in real-world settings without requiring model retraining or access to dedicated held-out set.
2. We adapt the one-run DP auditing framework (Steinke et al.) (023) to leverage NIDs, enabling truly post-hoc DP auditing of pretrained LLMs without modifying the training process and achieving tighter lower bounds.
We make DI more practical by creating the necessary held-out set post-hoe using the NIDs present in the suspect set and improving its efficiency by introducing novel ranking-based test.
4. We conduct extensive empirical evaluations, demonstrating the effectiveness of our NIDs for post-hoc privacy assessment over multiple LLM families and training datasets.
Indeed, we observe that the publicly available datasets used to train popular LLMs, such as the Pile Gao
et al. 2020) or Dolma (Soldaini et al., 2024). contain 30637 and 23571 different types of NIDs, respectively showcasing the practical availability of NIDs. The large number of NID-types and new types constantly emerging makes it impossible to omit them through the weh crawlers, thus NIDs are less prone to heing excluded from the LLMs' training set.
2

---

Published as a conference paper at ICLR 2026
2 BACKGROUND
Differential Privacy (DP). DP (Dwork et al.) 2006) is a framework that limits privacy leakage by ensuring no individual's data significantly alters the outcome of a computation. A randomized mechanism M satisfies (e, 6D if, for any two inputs z and x' differing by one record and any measurable set S, the following holds, where E bounds leakage and ò is the failure probability:
PlM(x) E S) S ((M( E +
In this work adopt the under replacement adjacency, where two datasets are considered neighbors they differ only in the replacement of one candidate element (rather than by addition or removal).
Auditing DP. The goal of DP audits is to empirically estimate lower bound on the privacy parameters e and 5 bost-training. These audits help evaluate the tightness of the theoretical analysis (Jagielski et al. 2020 Nast al. 2023) and can also reveal errors in the mathematical analysis or flaws in the algorithm's 's implementation (Tramer et al. 2022). Privacy auditing generally relies on retraining
models and inserting canaries during training (Jagielski et al. 2020. Nasr al. 2023 Steinke et al., 2023 Mahloujifar et al. 2025). While Steinke et (2023) reduce computational costs with a privacy auditing technique that only requires single training run, for LLMs with trillions of parameters,
even this can be prohibitively expensive. We build on their approach and leverage NIDs to remove the need for retraining altogether.
Membership Inference Attacks (MIAs). MIAS (Shokri et al. 2017) aim to determine whether a specific data point was included in a model's training set. They have diverse applications, and in this work, we focus on their use for privacy auditing (Steinke et al. (023). While MIAs have been extensively explored for small-scale models, MIAs for LLMs are much more challenging problem. The latest work (Duan et al. 2024 Maini et al., [024 Zhang et al. 2024a) indicates that the success reported by previous MIAs on LLMs (Mattern et al. 2023] Shi et al. 2024) is rather due to a distribution shift than to the attacks' ability to distinguish between the member and non-member data points. A prominent example is the temporal distribution shift that occurs when data before a specific cutoff date is selected as members and data after the point is treated differences in language, wording, or formatting styles. When evaluated in the correct setting without distribution shift, Maini et al. (0244) showed that most attacks do not outperform random guessing.
non-members, resulting in
Dataset Inference (DI. DI (Maini et al. 2021 aims to resolve whether a given suspect dataset was used train model. While initially proposed for model ownership resolution (Maini et al. 2024 Dziedzic et al. 22022) DI was recently extended to identify training data in LLMs (Maini et al. 2024 Zhao et al., 2025). Beyond L.LMs, DI has also been successfully applied to other types of generative models, including Diffusion Models (Dubinski et al., (025) and Image Autoregressive Models (Kowalczuk et al. 2025). In general, DI extracts diverse training membership features for the individual data points in the suspect set using various MIAs, aggregates them, and applies statistical testing to reliably determine whether the suspect set was used to train the model.
I Limitations of DI. DI's major limitation is that the method relies on access to a private held-out set from the same distribution as a suspect set. Prior work (Zhang ct al. 2024a) argues that this makes DI inapplicable for real-world use-cases where such data is usually not available. As solution, Zhang
et vll. 2024a) propose to inject random and meaningless canaries into the data and then test how the LLM ranks the selected canary among all alternatives. Since they assume access to the generator of the random canaries, they can provide the corresponding validation data points and avoid distribution shifts. The approach's 's reliance on inserted random strings reduces its practical applicability, as content creators would have to artificially include such specialized strings in their datasets and hide them from human readers. Additionally, web crawlers can be trained to omit such arbitrary context-free free strings when scraping the data from the internet, reducing the likelihood of this data being included in L.LMs' training data, Finally, this solution does not work for existing L.MSs that were trained without the use of injected canaries. In contrast, our observation is that we can leverage NIDs that are naturally included in LLMs' training sets, mitigating the need to insert purely random strings and enabling auditing of existing pretrained LLMs without retraining. As an alternative solution to overcome DI's reliance on an IID held-out set, Zhao et al. (2025) proposed generating synthetic held-out dataset by training suffix- based generator on the suspect set, followed by post-hoe calibration to reduce the distributional gap between the real and synthetic data. However, this approach is computationally expensive, requiring extensive training and calibration, and it still
3

---

Published as a conference paper at ICLR 2026
results in residual distributional shift between real and synthetic datasets. In contrast, our generated held-out set based on NIDs is from the exact same distribution as the suspect set.
3 NATURAL IDENTIFIERS (NIDS)
We introduce NIDs, explore their natural occurrence, and provide the intuition on how they address key challenges in LLM privacy research. We then present the notation and formalization of NIDs, which will serve as the foundation for the subsequent sections.
3.1 NIDS IN THE WILD
Conceptually, NIDs are structured random strings, generated according to some well-defines functions. Prominent examples include outputs from secure hash algorithms (e.g., MD5 or SHA-1, SHA-256), shortened URLs, or cryptocurrency wallet addresses. Additionally, new types of NIDs, e.g, produced through novel URL shortening approaches, are emerging continuously. Such strings are omnipresent on the internet, for example, in code repositories (e.g.. GitHub) and discussion platforms (e.g.. StackExchange). Since large parts of the data used to pretrain ttate-of-the-aa LLMs are crawled from the internet, these NIDs get naturally included in the LLMs' training sets. We carefully extract the NIDs, as described in Appendix C
While LLM providers may attempt filter natural NIDs during data crawling, auditors hold structural advantage in this setting (Hönig et al., 20244 Radiya-Dixii et al.). Removing all natural NIDs is exceptionally challenging: even corpora with aggressive regex-based cleaning, URL canoni- calization, PII filterin,, and multistage deduplication, such as Dolma, still contain tens of thousands of distinct NID types, as detailed in Table (Appendixx (D). For our approach, an auditor only needs to identify a small subset of NIDs in the suspect set to conduct effective post-hoc audits. This makes our approach robust even under strict data curation pipelines, thus making our solutions for L.LM privacy auditing widely applicable.
We analyze a wide range of popular L.LM training datasets, including Pile (Gao et al. 2020) and Dolma (Soldaini et al., 2024). and identify that all of them contain multiple types of NIDs with numerous examples per type. In Appendix we provide an overview of the analyzed subsets and contained NIDs in Table 6 Notably, datasets that include code snippets, such as StackExchange and GitHub, have a high number of NIDs. Additionally, large non-topic-specific corpora, such RefinedWeb and Pile Common Crawl, also contain significant number of NIDs. SHA-1 and MD5 are the most frequent types of NIDs overall. For some large subsets, such as RefinedWeh, we have many 16989 NIDs. For instance, Pile's entire validation and test set, which comprises approximately 0.2% of the entire Pile dataset, contains 293 NIDs. Furthermore, as shown in Table even highly filtered and curated datasets such as Dolma (Soldaini et al.) (024) contain a substantial number of NIDs. This makes our solutions for LLM privacy auditing widely applicable.
3.2 LEVERAGING NIDS
What makes NIDs special is their rigorously specified format in combination with a sequence of random characters. Given that their format is known, it becomes possible to generate an infinite number of other random strings that follow the same distribution. In the following, present the intuition on how this property contributes to solving the most pressing challenges in LLM privacy research, namely, the lack of IID held-out data.
1) NIDs provide post-hoc DP audits. We can use NIDs to perform post-hoc auditing for LLMs trained with DP. To do so, we build on the one-run privacy audit by (Steinke et al. (2023). In their method, they select set of canary data points to be included or excluded during training run. After training, an auditor attempts to infer for each of these data points whether it was included or not. The fraction of correct guesses provides a lower bound on the DP parameters. Using our NIDs, retraining the model is no longer necessary. Instead, we generate random samples from the same distribution as the NIDs seen during training. The NIDs as natural canaries be ranked against the generated ones, for auditing without any retraining, i.e., truly post-hoe. Section Jottiness our approach to using NIDs for post-hoc DP auditing.
4

---

Published as a conference paper at ICLR 2026
2) NIDs enable DL. NIDs enable DI for suspect sets, i.e., a dataset for which want to assess whether it has been used to train a given LLM, without requiring a uome-distribution private held-out private held-out set from the same distribution as the suspect
set. As detailed above, DI relies set to perform its assessment-a requirement that is difficult to meet in practice. This is especially due the challenge of obtaining dist-iiitritttion data post-hoc (Zhang et al.] (2024)) rendering DI challenging or impractical. By generating large held-out sets from the same distribution, NIDs address this issue, thus enabling DI detect if an LLM was trained on a suspect set. If the suspect set was part of the LLM's training data, it will react differently to the NIDs included in that set and their generated held-out counterparts. Otherwise, if was not trained on the suspect set, its behavior will be the same over both sets, as both NIDs and their generated counterparts. since to the LLM, they will just be the same type of random strings. We detail the use of NIDs for DI in Section 5
3.3 FORMALIZING NIDS
An identifier (ID) is produced by sampling randomness from known distribution and applying generator W. i.e., v = (=). The set of all possible IDs from this generator is V = (=) : = E 2). A Natural Identifier (NID) is simply
ID that actually appears in a real dataset. Given such an NID, we can draw fresh random inputs 2' to generate additional IDs from the same distribution, which we call Generated Identifiers (GIDs). Because the identifier space V is extremely large, a newly generated GID is overwhelmingly unlikely to coincide with any existing NID in the data.
As a concrete example, consider Ethereum addresses. An Ethereum address is effectively 160-bit identifier, obtained from a private key through a deterministic derivation process. Given an NID corresponding to an Ethereum address, we can use the associated generation function ((=)= == (TH(2) to generate new GIDs. In this case, the set V is the set of all valid Ethereum addresses (see Appendix [ for details on the structure of NIDs and GIDs, and Appendix [B] for examples). Additionally, the probability of generating GID that exactly matches one of the NIDs in the training data is negligible, since the address space has size 2160 x 1.46 x 1048.
The main property of NIDs is that a priori each ID E V is equally likely to be generated and published because only depends on the source of randomness. The second important property of NIDs is that they allow easy sampling from the set V. In the suspect datasets Dsus. which are auditing, there are usually m NIDs, with the corresponding sets Vi,..., Vn. Although the underlying identifier space V is extremely large, for computational purposes we restrict attention to a finite candidate set: for each detected NID ú; we sample e - I fresh GIDs and form V/2 = {6:} fc GIDs} with [V]] = c. Furthermore, for each set V/2 where i E {l...., m). we denote the NID as é E Vi, and specifically, the NID that belongs to the suspect dataset as 0g E Deus. Finally, we define E, as the set of all the permutations over V/-
4 DP AUDITING WITH NATURAL IDENTIFIERS
Using our NIDs, we adapt the one-run DP auditing method proposed by Steinke et al. (2023) to create a novel post-hoc DP auditing. Their technique considers m canary samples and uses coin flips to randomly determine which samples should be included in the training set. Therefore, it is a binary case of adding or removing a single sample (and selecting between two options) that requires further retraining. Subsequent works (Panda et al. 2025 Liu et al.. 2025) build upon the settings and methods proposed in the original paper, thus requiring retraining. In our case, we differ from previous approaches by eliminating the need to retrain the model to insert canaries, since NIDs are inherently present in the data. Therefore, adding or removing multiple training examples independently is not required. This is particularly important for LLMs, for which retraining is prohibitively expensive and cine-consuming. Furthermore, our method operates under more realistic assumptions compared to Kazmi et al.) (2024), who, although they relax the assumption of retraining, require training a generative model that must then generate samples following the original training data distribution. Additionally, we do not strengthen the canary signal for the audit by surrounding the canaries with random tokens, as in Panda et al. (025). Finally, compared with Mahloujifar et al. (0025), our ranking- based generalization, where the task is to correctly identify the
method can be viewed true NID from a set of e candidates, by requiring it to appear among the top-r ranked positions, rather than only identifying it as the single top-1 candidate.
5

---

Published as a conference paper at ICLR 2026
1
Suspect set
Natural Identifiers (NIDs)
Train data (c. 6t.P
Auditor
V/
AA.AA
Sets of NIDs and GIDs
(e. PPP LLM
Ranked top-12
(e.8 LLM
Generated Identifiers
(GIDs)
6)-DP training
NIDs extraction & GIDs generation
Post-hoc privacy auditing with NIDs
Post-hoc DP auditing with NIDs and their corresponding GIDs. We consider the NIDs as the input to a training procedure M (also referred to as the mechanism), which may satisfy (e, 8D.DP. Given suspect dataset, we identify the NIDs. We generate the new
Figure 1:
GIDs for each NID. We form the candidate sets Vi, Vn by combining the NIDs with corresponding GIDs. Given the resulting trained model and filtered NIDs with corresponding GIDs, an auditor seeks to infer, for each set V,. which sample was the NID. To do so, the auditor ranks the samples in Vi from the most to the least likely NID-candidate. A prediction considered correct the true NID appears among the top-r; ranked samples, where r; is predefined threshold.
We show in Figure how to leverage the NIDs to audit DP post-hoc. By leveraging the NIDs, our framework enables us to compute lower bounds on privacy parameters of an algorithm without any additional training training data and denote their total number as m. For each NID i E {1, ... m). we generate the corresponding GIDs, and the corresponding set of IDs VG {ot .....,,
of that algorithm. We first identify the NIDs that were present in the
of where we have - GIDs and a single NID denoted as i/. One of the main properties of NIDs is that, a priori, any element VÚ could have been part of the training data in place the NID. This enables us to model privacy auditing analogously to the fixed-length dataset variant proposed by (Steinke et al. (003)). The key distinction our approach is that, rather than selecting between two alternatives prior training, we consider the NIDs as inserted canaries with the GIDs multiple left-out canary possibilities for each set V.. For this reason, the attacker's goal is to predict which sample was the NID by ranking the samples from the most likely the least likely to be part of the training data. This offers more flexibility by enabling the attacker to represent uncertainty through ranked list, rather than having to make binary, top-1 inclusion decision.
Following the analysis of Theorem 5.2 by Steinke et al. (003)), we adapt their privacy auditing procedure to our setting audit (s, 8DD mechanisms. We compare the rank of the real and alternative samples. For simplicity and clarity, we state the e-DP version of the theorem, and in we show the complete theorem (Theorem 2 for the (D case. Appendix E.
+ - Em be an E-DP mechanism under replacement. Let S V1 Vm be uniformly random, and define T MSS) Σn x Em- Then, for all E R. all E
Theorem Let M x.....xX Vm
Em in the support T, all ri. Tm with r; S VVl,, and rie"
Iv. S
P X Vm T M()
1 (rank(t;, (, S.) S 2 2 7
S$ 2| = B(e, v,
Se-Berroulli
rank(a,b) b) returns the 1-based position of the element b in permutation
In our setting, Theorem | states that if the mechanism (also referred to as the training procedure) is e-DP, any attacker attempting to detect the NID is constrained. Concretely, the attacker ranks the mechanism's output on both the NID and its corresponding GIDs from most to least likely to be part of the training data without knowing which one is the NID. Then, they count how many NIDs appear in the top-r, where is a predefined threshold. The theorem states that this count is bounded by Bernoulli distribution, whose probability depends on r, and the number of GIDs.

---

Published as a conference paper at ICLR 2026
Furthermore, compared to Theorem 5.2 by Steinke et al. (2023). Theorem and Theorem (presented in Appendix [E leverage a key property of NIDs: the ability to generate an unlimited number of GIDs
mnon-members).
Both theorems enable DP auditing through a hypothesis testingg framework. Moreover, in both cases, we can construct confidence interval for lower bound on e. The proofs of Theorem | and Theorem 2 are provided in Appendix E
6
An Example of Our Privacy Auditing for the Randomized Response. To illustrate our auditing framework, we use the classical randomized sponse mechanism (Warner, 1965). In this setting, each private value can either be revealed truth- fully or replaced at random, with probabilities chosen ensure E-DP (see Appendix Bo.ddixxGTjeje [G.T for the detailed description of the setting). The analogy to our framework is straightforward: each true value corresponds to NID, and the alternative pos- sibilities correspond to GIDs. The auditor ranks possible values given the output, and without any additional information, the best strategy is to place the observed output first. This yields a correct- guess probability matching the theoretical bound in Theorem [ Figure FigureJshoww shows the empirical behavior of our auditor on randomized response for different set cardinalities c = [Vi]. We see that higher cardinality (i.e,, more generated GIDs) is especially beneficial at larger privacy budgets (s 8). which is the typical regime in LLM training with DP (Duan et al., 2023; et al. [022]] Rossi et al. 2024, Hanke al., (024)). This demonstrates how our framework scales naturally with the number of GIDs. Additionally. in Appendix [F] we analyze the relationship between the number of samples m (i.e., number of NIDs) and G, as well as why a larger cardinality helps reduce the number of required samples.
10a
10a
10a
10
10a
Number of samples
Ideal
(Steinke et al.)
* 32
Figure 2: Randomized response with & = 8 for different cardinalities e = {2, 8.3}.
Post-hoc DP Auditing Without Retraining in LLMs. We verify that our proposed framework applies privacy auditing in LLMs by adapting the black-box procedures proposed by /Steinke et al. (2023) to the fixed-size dataset variant. The auditing process follows the algorithm described in Appendix H. Due to the lack of open-source private pretrained LLMs, to show the capabilities of our method, we finetune multiple Pythia models (70m, 160m, 410m, and lb) using DP-SGD (Abadi)
al. 2016) We use all NIDs extracted from the Pile test set (Gao et al. 2020). All lower and upper bounds are presented with 95% confidence intervals.
197 NIDs from the Github Pile test set, ensuring complete coverage of our assumption. Then, for each NID, we generate c- GIDs. In this way, we have sets of IDs Vi,.... Vn We set ó 10 for various values of ε using the Privacy Random Variable (PRV) accountant Gooi et al. 202T), and finetune each model for 20 epochs using a maximum sequence length of 64 tokens and a clipping norm of 0.1. To rank each set of ID from most least likely to be in the training data, we use Min-K% (Shi et al.) 2024) and Loss (Yom et al., 2018), and report the best result. By default, we set the ranking threshold to r; = (top-1) for all E (T, m ]. In this setting, prediction is counted as correct only when the attacker's highest-scoring candidate coincides with the true NID, Complementary results for additional models and for thresholds r; > 1 are reported in Appendix H.I
Setup. The training data consists
Higher Cardinality Improves Audits. As reference, we use the auditing of fixed-length datasets introduced by Steinke et al. (2023), which corresponds to special case of our method where all sets! VG have cardinality с = 2 and the corresponding threshold is r, = 1. The empirical analysis in Figure 3 demonstrates that our method outperforms the baseline across multiple cardinality parameters (c E {8, 32}) in fixed-length dataset settings. See Appendix H.1 for the results of the other models and for additional experiments with thresholds r; 1. Although higher cardinality can enhance the statistical power of the auditing procedure in the best-case scenario, meaning that fewer samples are required, the ranking task becomes increasingly complex. Instead of merely comparing two candidates, one must select from = [V]] options. For smaller privacy budgets (i.e., a more challenging prediction task), smaller cardinalities are beneficial. In contrast, for larger E, higher cardinality tends to be advantageous and significantly outperforms the baseline. This trend aligns
7

---

Published as a conference paper at ICLR 2026
101
101
Eccomated
Essimated
10"
100
10-2
10-1
10
100
10
100
Erear
Great
(Steinke et al.)
(Steinke
(a) Pythia-Ib
(b) Pythia-4 10m
Figure 3: Impact of cardinality (c f2, (,33) on estimation. Experiments conducted using 8 values (5, 10, 100, ).). The case c = 2 corresponds to the method proposed by Steinke et al. (2023). The error bars represent a 95% confidence interval.
with our insights for randomized response, where increasing cardinality makes the privacy auditing more precise and tighter, particularly in less restrictive privacy settings.
5 DATASET INFERENCE WITH NIDS
Next, we turn to exploring the use of NIDs and our generated same-distribution GIDs for performing DI (Maini et al. 202T). As discussed Section 2 the strongest limitation of is its reliance on a private held-out dataset from the same distribution as the suspect dataset, i.e. the dataset for which we want to assess whether it was included in the training of the given model. Such datasets are often not available in practical applications (Zhang al. 2024a).. We present how our NIDs can overcome this limitation and enable successful DI for suspect datasets that contain NIDs. We experiment with Pythia-2.88 2.8b, 6.9b, 12b (trained on the Pile), and OLMo-7B (trained on Dolma) cover a range of model sizes and families. For ethical reasons, we focus on open models with known training data where we can verify the correctness our evaluation w.r.t. to the ground truth training sets, which is impossible for proprietary models where we have no access to the true training data.
Table I: MIAS on NIDs for Pythia-12b. The AUC for MIAs between the NIDs and the corresponding
GIDs on various subsets of the Pile dataset.
Full Pile
GitHob Train
Stecknxx Test
Average Train
MIA
Train
Test
Test
Trann
Tost
Loss
58.6
50.3
71.8
51.1
50.3
50.9
60.2
50.8
Min: K
57.6
51.0
68.4
50.6
50.7
51.2
58.9
50.9
Min-KS5+++
56.9
51.4
71.2
50.3
50.8
51.9
59.6
$1.2
ReCALL
53.5
50.2
50.6
50.3
50.0
51.4
50.5
(Hiin)(Hinge)
$1.3
50.1
53.3
50.4
50.4
51.4
31.7
50.6
Hinge
58.7
50.5
71.8
51.5
50.4
50.5
60.3
50.8
MIAs for DI. DI for LLMs MMaini et al. 2024) aggregates the outputs multiple MIAs to extract a strong signal from the suspect data. We follow this approach and extract the signal from the suspect set's NIDs as a form natural canaries. Therefore, we use MIAS on NIDs as a stepping stone for LLM DI. In this setting, the attacker aims to distinguish NIDs from their corresponding GIDs. For the training set, NIDs are drawn from the training data, while for the test set, they are drawn from the test data. In both cases, GIDs are constructed from data that not used during training, serving as held-out samples. For the test set evaluation, we expect the AUC to be close to random guessing. This serves as sanity check confirm that the GIDs and NIDs come from the same distribution, since neither is present in the training data. To mimic the DI setting, we generate = 127 new GIDs for each NID, balancing computational cost and distribution quality. Using our identified NID suspect set and the respective generated GIDs held-out set, we analyze existing state-of-the-an MIAs for L.Mss, namely Loss (Yeom et al., 2018), Min-K% (Shi et al., 2024). Min-K%++ (Zhang et al. 2024b), ReCal.I. (Xie et al. 20024, and Hinge (Carlini et al. 2022) to obtain useful signals for DI. For most MIAs, performance on the test set close to random guessing, as expected, confirming no distribution shift between the NID suspect set and the generated GID held-out set. Train-test
8

---

Published as a conference paper at ICLR 2026
behavior is well-calibrated, with higher average AUC on the train set. Results for Pythia- 12b appear in Table I Appendix preports additional models (Pythia, OLMo-7B (BM and TPR @ 1% FPR.
DI on NIDs. Given suspect set Duus+ we first need to identify and extract all the NIDs in the dataset. The extracted NIDs form the suspect subset D' which we use to perform the DI. Then, for every real NID in D' we generate 127 new GIDs with the same NID type and with the same structure to form the held-out set from the same distribution as D'us- With the signal from the MIAs above, following Maini et al. (0024), we extract the features from the suspect set and D and our generated held-out set. Next, To following the DI protocol, we need to learn the correlation between the features (the MIA scores) and their membership status. To learn this correlation, we train gradient boosting trees classifier to distinguish between the two distributions. To use all the samples available, we train and score the samples using K-Fold, and we ensure that the generated samples derived from real sample end up in the same fold. Finally, following Maini et al. (2024), we perform statistical testing and compute the p-values. Under the null hypothesis, which assumes that the NIDs in the suspect set are not part of the training data, the ranks of each NID relative its corresponding GIDs should follow uniform distribution. This means that if we order the NIDs based on their association with GIDs, their positions should be evenly distributed across the ranking scale. We apply the Kolmogorov- Smirroy (KS) test to test this assumption. If the KS test detects a significant deviation from uniformity, we reject the null hypothesis, suggesting that the NIDs may, in fact, be present in the training data. Small p-values (< 0.01) indicate that we can reject the null hypothesis, i.e., we are confident that the model was trained on the suspect set. Large p-values (>> 0.01) suggest inconclusiveness of the test, i.e., we are not confident whether the model was trained on the suspect set.
Practical DI with NIDs. Using our generated held-out set with GIDs and the suspect set D with NIDs, we perform DI on various models and data subsets. Our main results for DI are summarized in Table ann Table 3] Compared with Maini et al.] (2024), who used 1000 samples, we take much smaller suspect sets D' sus with 100 real NIDs to simulate a realistic setup. For each subset, we generate a held-out set using the NIDs, and perform DI. Our method shows that for the suspect sets that were included in the training data, DI obtains low p-values (< 0.01) that allow us to reject the null hypothesis. This highlights that the suspects are correctly identified as training data. At the same time, for test data (denoted as Test), i.c., datasets that were not used to train the given LLM, we observe high p-values that do not allow us to reject the null hypothesis. The sets are, hence, correctly not marked as training data (p-values >> 0.01). We present further results on models of various sizes and with varying numbers of NIDs in the suspect set in Figure Appendix []. The results highlight that the more NIDs are available in D' the more reliable the DI. Overall, using NIDs and the generated held-out set, we observe no false positives, while correctly identifying all training subsets (true positives). This highlights NIDs' ability to enable practical DI.
Table 2: P-values for DI on the Pile Dataset with 100 suspect samples. We use a 0.01 p-value threshold. We reject the null for all training subsets (p S 0.01) and do not reject it for the test set (p > 0.01). All outcomes are correct (V).
Model
GH
SE
HN
CC
AX
PM
IRC
Fall
GH (Teat)
Full (Teat)
Pythia 12B
0.0031
0.0001
0.0001 V 0.0001 V 0.0001
0.0001
0.0001
0.0001 <
0.8182
0.2847 V
Pythia 6.9
0.0001 V 0.0001 V 0.0001 V 0.0002 V 0.0001 V 0.0001 V 0.0001 V 0.0001 <
0.6139 /
0.0811 V
Pythia 2.8B
0.0001 V
0.0001
0.0001 V 0.0001 V 0.0001 V 0.0001 V
0.0001
0.0001 V
0.9632
0.0660 /
Notation: GH GnHub, SE StackExchange, HN HackerNows, CC Pil-CC, AX= ArXiv, PM PubMedCentral, IRC UbuntulRC
Table 3: P-values for DI on the Dolma Dataset with 100 suspect samples. We use a 0.01 p-value threshold. We reject the null for all training subsets (p S 0.01) and do not reject it for the test set (p > 0.01). All outcomes are correct (V).
Model
OWM
PeS2o
RFW
AStack
MWika
AX
C4
PP2 (Test)
OLMo 7B
0.0001 V 0.0001 v 0.0003 V 0.0001 v
0.0002 / 0.0001 / 0.0001 V
0.8961 /
Notation: OWM- OpcaWebMath. RFW = RehnndWeb, AStack = Algebraic Stack, MWia = MegaWika, AX AiXiv, PP2 = Proot Pile
Controlled Ablations. We also perform controlled ablations to characterize further how NID-based DI behaves under different design choices. First, compare our NIDs against standard injected canaries, i.e., canaries that do not naturally occur in the training data but must be manually added. Although injected canaries fall outside our post-hoe threat model, this controlled setting helps
9

---

Published as a conference paper at ICLR 2026
contextualize the strength of the NID leakage relative to existing auditing methods. We detail the choice and design of these canaries in Appendix [K.]] Our results in Table[[ó]show that NIDs achieve competitive DI performance, measured in p-values. Second, evaluate the impact of the GIDs being carefully sampled from the same distribution of the NIDs. Remember that DI critically depends on the GID generator matching the NID distribution: misimplementations that change casing produce strong signals for both members and nonmembers, thereby inflating false positives. To quantify this impact, we design GID generations that mismatch the original NIDs to various degrees. We describe our experimental setup in Appendix K.2 Our results show that deviations in distribution between NIDs and GIDs lead false positives, highlighting the importance of our approach to generating GIDs exactly from the same distribution as NIDs. Third, we evaluate the impact of stronger MIAs on DI performance. Specifically, we augment the baseline features with CAMIA (Chang et (024) and SURP (Zhang & Wu 2024). See Appendix|K..
details. Our results, shown in Table 18] indicate that adding more powerful MIAs consistently improves DI results. These results suggest that ongoing advances in MIA techniques further improve our framework s results. Fourth, we quantify whether the identifier structure matters. We construct a synthetic string that follows the format of each NIDs to measure the impact of the identifier structure. In Appendix [.44 detailed the experimental setup. Our findings suggest that longer or more structured formats, such as SHA-512 512 and Java Serialization strings, yield the strongest DI signals, although shorter formats, such as MD5, still produce highly significant results, as shown in Table 19 Finally, we assess the impact of increasing the number
of NIDs on the results of DI in Appendix K.5 Our results in Table 20 suggest that increasing the
number of NIDs in the suspect set monotomically decreases the p-value in DI, illustrating the expected gains in statistical power.
Task-Specific NIDs. In some smaller, task-specific datasets, standard NIDs might be less common. To make DI practical in these settings, new task speciiieiiiicc NIDs can be discovered. As a case study, we consider the GSM8K dataset (Cobbe et al. 2021), math word-problem dataset without standard NIDs. To generate valid and indistinguishable GIDs for DI, we create task sase-specific NIDs by treating each problem as numeric template: for example, in "Natalia sold 48/2 = 248/2=24x24 clips in May. Natalia sold 48+24= = <48+24=72>72 clips altogether in April and May. #### 72.", we replace 48 and all dependent quantities (such as 24 and 72) with variables, resample consistent numbers to obtain new problem, and use these as NIDs and GIDs In Appendix[B] we provide some practical examples of NIDs and the corresponding GIDs See Appendix (rrrendixK.6fforr details on the experimental setup. To assess whether the resulting NIDs and GIDs are suitable for our framework, we finetune Pythia- lb on 100 such NIDs, and run DI. The results in Table A Tsoo produces statistically significant evidence for DI, confirming its effectiveness in various settings.
show that this new task-specific type of NIDs
Table 4: P-values for DI on GSMSK. P-values obtained by our DI test on the GSM8K dataset, illustrating the effectiveness of saec-fp NIDs.
Number of NIDs
50
60
70
80
90
100
P-Vulue
8.43
10
9.56
10
3.35
10 1.63 x 10
2.12 10-1 1.60 10-0
DISCUSSION AND CONCLUSIONS
We introduce the concept of natural identifiers (NIDs) as a practical and scalable solution to central challenge in LLM privacy research: enabling truly post-hoc privacy auditing, i.e., auditing models after training without requiring retraining access dedicated held-out data. This directly addresses a key limitation of most existing approaches, which rely on costly retraining procedures or artificially constructed held-out sets. While we focus leveraging NIDs within the language domain for models trained on datasets containing such identifiers, our analysis shows that NIDs are pervasively present in standard LLM pretraining corpora. Their structured and reproducible nature enables the generation of an unlimited number of non-member samples from the same distribution, which we use to construct effective post-hoe auditing sets. Building on the one-run auditing framework, we demonstrate that NIDs yield tighter DP bounds with reduced sample complexity. By extending the task from binary classification to ranking-based inference, our approach further improves the flexibility and statistical power of privacy attacks. Beyond formal auditing, NIDs also make DI practically feasible using only the suspect data, without requiring access to held-out sets. Our empirical evaluations on open- source LLMs validate the effectiveness and practicality of this approach. In summary, NIDs offer principled, both practical and efficient foundation for real-world host-hoc privacy auditing. advancing the feasibility of scalable and responsible privacy assessments for modern language models.
10

---

Published as a conference paper at ICLR 2026
7 ETHICS STATEMENT
This work develops post-hoc auditing methods for LLMs using NIDs, which raises dual-use concerns: the same techniques that help auditors and regulators assess training-data usage and privacy guarantees could, in principle, be misused to better locate training artifacts or strengthen reconstruction attempts against weakly protected models. We acknowledge this risk, and believe such tools should be deployed only in controlled settings. At the same time, we view this kind of research as necessary: without realistic auditing techniques, is difficult to verify privacy claims, detect misuse of training data, or incentivize stronger protections such as robust DP training.
ACKNOWLEDGEMENTS
Franziska Boenisch received funding from the European Research Council (ERC) under the European Union's Horizon Europe research and innovation programme (grant agreement No 101220235). Additionally, we would like to acknowledge our sponsors, who support our research with financial and in-kind contributions: OpenAl and G-Research. We also thank members of the SprintML group for their feedback. Responsibility for the content this publication lies with the authors.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Viraat Aryabumi, Yixuan Su, Raymond Ma, Adrien Morisot, Ivan Zhang, Acyr Locatelli, Marzich Fadace, Ahmet Üstün, and Sara Hooker. To code or not to code? exploring impact of code in pre-training. In The Thirteenth International Conference on Learning Representations, 2025. URL net foo.oumid=iSSeeNI....
Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning, pp. 2397-2430. PMLR, 2023.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium ( (USENIX Security 19), pp. 267-284, Santa Clara, CA, August 2019. USENIX As- sociation. ISBN 978- 978-1-939133--6-9, URL httpt:://///.. /wwww uswn org/ con ference/ htt.://crrrtyyyyyeeeettaaaaaooom
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Vlerbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pp- 2633-2650, 2021.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897-1914. IEEE, 2022.
Hongyan Chang, Ali Shahin Shamsabadi, Klcomenis Katevas, Hamed Haddadi, and Reza Shokri. Context-aware membership inference attacks against pre-trained large language models. arXiv preprint arXiv:2409.13777 2024.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168 2021.
Matthew Coulter. Aiming for faimess: an exploration into getty images stability ai and its importance in the landscape modern copyright law. DePaul J. Art Tech. Intell. Prop. L, 34: 124, 2024.
11

---

Published as a conference paper at ICLR 2026
Debeshee Das, Jie Zhang, and Florian Tramèr. Blind baselines beat membership inference attacks for foundation models. arXiv preprint PrXi::2406.16211, 2024.
Haonan Duan, Adam Dziedzic, Nicolas Papernot, and Franziska Boenisch. Flocks of stochastic
parrots: Differentially private prompt learning for large language models. Advances in Neural Information Processing Systems, 36:76852-76871. 2023.
Michael Duan, Anshuman Suri, Niloofar Mireshghallah, Sewon Min, Weijia Shi, Luke Zettlemoyer, Yulia Tsvetkov, Yejin Choi, David Evans, and Hamnaneh Hajishirzi. Do membership inference attacks work on large language models? In Conference on Language Modeling (COLM), 2024.
Jan Dubiński, Antoni Kowalczuk, Franziska Boenisch, and Adam Dziedzic. Cdi: Copyrighted data identification in diffusion models. In Proceedings of the Computer Vision and Pattern Recognition Conference, pp. 18674-18684, 2025.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryplography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284 Springer, 2006.
Adam Dziedzic, Haonan Duan, Muhammad Ahmad Kaleem, Nikita Dhawan, Jonas Guan, Yannis Cattan, Franziska Boenisch, and Nicolas Papernot. Dataset inference for sule-supe models. In NeurlPS (Neural Information Processing Systems). 2022.
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang. Horace He, Anish Thite, Noa Nabeshima, et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2101.00022 2020.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Informaionn Processing Systems, 34:11631-11642, 2021.
Dirk Groeneveld, Iz Beltagy, Evan Walsh, Akshita Bhagia, Rodney Kinney, Oyvind Tafjord, Ananya Jha, Hamish Ivison, Ian Magnusson, Yizhong Wang, Shane Arora, David Atkinson, Russell Authur, Khyathi Chandu, Arman Cohan, Jennifer Dumas, Yanai Elazar. Yuling Gu, Jack Hessel, Tushar Khot, William Merrill, Jacob Morrison, Niklas Muennighoff. Aakanksha Naik, Crystal Nam, Matthew Peters, Valentina Pyatkin, Abhilasha Ravichander, Dustin Schwenk, Saurabh Shah, William Smith, Emma Strubell, Nishant Subramani, Mitchell Wortsman, Pradeep Dasigi, Nathan Lambert, Kyle Richardson, Luke Zettlemoyer, Jesse Dodge, Kyle Lo, Luca Soldaini, Noah Smith, and Hannaneh Hajishirzi. OLMo: Accelerating the science of language models. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 15789-15800 Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 18.5835//v1/ 1024.acl-long.841 841. URL.tttpss ac antho oow. www.orgg/2202... 2024 acl ong 841/
Vincent Hanke, Tom Blanchard, Franziska Boenisch, Iyiola Emmanuel Olatunji, Michael Backes, and Adam Dziedzic. Open Ilms are necessary for current private adaptations and outperform their closed alternatives. In Thirty-Eighth Conference on Neural Information Processing Systems (NeurIPS), 2024.
Jonathan Hayase, Alisa Liu, Yejin Choi, Sewoong Oh, and Noah A Smith. Data mixture inference at- tack: Bpe tokenizers reveal training data compositions. Advances in Neural Information Processing Systems, 37:8956-8999 8983, 2024.
Robert Hönig, Javier Rando, Nicholas Carlini, and Florian Tramèr. Adversarial perturbations cannot reliably protect artists from generative ai. arXiv preprint arXiv:2406.. 12027, 2024.
Binyuan Hui, Jian Yang, Zeyu Cui, Jiaxi Yang, Dayiheng Liu, Lei Zhang, Tianyu Liu, Jiajun Zhang, Bowen Yu, Keming Lu, et al. Qwen2. 5-coder technical report. arXiv preprint arXiv:2409. /2186, 2024.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 33: 22205-22216, 2020.
12

---

Published as a conference paper at ICLR 2026
Mishaal Kazmi, Hadrien Lautraite, Alireza Akbari, Qiaoyue Tang, Mauricio Soroco, Tao Wang, Sébastien Gambs, and Mathias Lécuyer. PANORAMIA: Privacy auditing of machine learning models without retraining. In The Thihty- Annual Conference Neural Information Fagg
Processing Systems, 2024. URL /tpttpse///ennrvvieee.
Najoung Kim, Sebastian Schuster, and Shubham Toshniwal. Code pretraining improves entity tracking abilities language models. arXiv preprint urXiv:2405.2 1068, 2024.
Antoni Kowalczuk, Jan Dubiński, Franziska Boenisch, and Adam Dziedzic. Privacy attacks on image autoregressive models. In Forty-second International Conference on Machine Learning, 2025.
Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations, 2022.
Terrance Liu, Matteo Boglioni, Yiwei Fu, Shengyuan Hu, Pratiksha Thaker, and Zhiwei Steven Wu. Enhancing one-run privacy auditing with quantile regression-base membership inference. arXiv preprint arXiv:2506. 15349, 2025.
Saeed Mahloujifar, Luca Melis, and Kamalika Chaudhuri. Auditing f f-differential privacy in one run. In Forty-second International Conference on Machine Learning. 2025.
Pratyush Maini, Mohammad Yaghini, and Nicolas Papernot. Dataset inference: Ownership resolution in machine learning. arXiv preprint 2rXiv:2104.10700 2021.
Pratyush Maini, Hengrui Jia, Nicolas Papernt, and Adam Dziedzic. LLM dataset inference: Did you train on my dataset? In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL
ew fott//orumm?u www.rrummmi=FFFr F=F 1MM377
Justus Mattern, Fatemehsadat Mireshghallah, Zhijing Jin, Bernhard Schoelkopf, Mrinmaya Sachan, and Taylor Berg- Kirkpatrrkt.k.. Membership inference attacks against language models via neigh- bourhood comparison. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACI. 20233 pp. 11330- 11303, Toronto, Canada, July 2023, Association for Computational Linguistics. doi: 10. 1 165316113322222333 htt.66////11003...nnnns==////// URL https: ac www.eannntooooo.oooooooooooo org/ 2023. findings acl. 719
Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 1631-1648, 2023.
Ashwince Panda, Xinyu Tang, Christopher A. Proquette--hhoo Milad Nasr, and Prateck Mittal. Privacy auditing of large language models. In The Thirteenth International Conference on Learning Representations, 2025. URL https::: httt:::://ppnreeieee http//ppnnrriieeee
Setpenreview.neeeEoorree...ee.ee ne: 600
Jackson Petty, Sjoerd van Steenkiste, and Tal Linzen. How does code pretraining affect language model task performance? Transactions on Machine Learning Research, 2025. ISSN 2835-8856.
URL
net. / forum? htt:://ooommmmmmmmmeeeeeee id=pxxmUKKge]
Evani Dixit, Sanghyun Hong. Nicholas Carlini, and Florian Tramer. Data poisoning won't save you from facial recognition. In International Conference on Learning Representations.
Lorenzo Rossi, Bartlomiej Marek, Vincent Hanke, Xun Wang, Michael Backes, Adam Dziedzic, and Franziska Boenisch. Auditing empirical privacy protection of private Ilm adaptations. In Neurips Safe Generative Al Workshop 2024, 2024.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et al. Code llama: Open foundation models for code. arXiv preprint arXiv:2308. 2023.
Weijia Shi, Anirudh Ajith, Mengzhou Xia, Yangsibo Huang, Daogao Liu, Terra Blevins, Danqi Chen, and Luke Zettlemoyer. Detecting pretraining data from large language models. In The Twelfth International Conference on Learning Representations, 2024. /ttpps://ppeeeeeeerr mett/forumid==zgee
13

---

Published as a conference paper at ICLR 2026
R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 3-18, Los Alamitos, CA, USA, may 2017. IEEE Computer Society. doi: 10.1109/SP.201.4411 URL https://dol
issecooppterrocc ottp:/ppperrro......oooooo/....0
2017.41
Luca Soldaini, Rodney Kinney, Akshita Bhagia, Dustin Schwenk, David Atkinson, Russell Authur, Ben Bogin, Khyathi Chandu, Jennifer Dumas, Yanai Elazar, Valentin Hofmann, Ananya Harsh Jha, Sachin Kumar, Li Lucy, Xinxi Lyu, Nathan Lambert, Ian Magnusson, Jacob Morrison, Niklas Muennighoff, Aakanksha Naik, Crystal Nam, Matthew E. Peters, Abhilasha Ravichander, Kyle Richardson, Zejiang Shen, Emma Strubell, Nishant Subramani, Oyvind Tafjord, Pete Walsh, Luke Zettlemoyer, Noah A. Smith, Hannanch Hajishirzi, Iz Beltagy, Dirk Groeneveld, Jesse Dodge, and Kyle Lo. Dolma: an Open Corpus of Three Trillion Tokens for Language Model Pretraining Research. arXiv preprint, 2024.
Thomas Steinke, Milad Nasr, and Matthew Jagielski. Privacy auditing with (1) training run. In Shirty-seventh Conference on Neural Information Processing Systems, 2023. URL https?
7/ /oppnnevvew..et.. ftte://foommmmddd3322.11 /
Florian Tramer, Andreas Terzis, Thomas Steinke, Shuang Song, Matthew Jagielski, and Nicholas Carlini. Debugging differential privacy: A case study for privacy auditing. arXiv preprint arXiv:2202. 12219, 2022.
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American statistical association, 60(30)):63-69, 1965.
Roy Xie, Junlin Wang, Ruomin Huang, Minxing Zhang, Rong Ge, Jian Pei, Neil Zhenqiang Gong, and Bhuwan Dhingra. Recall: Membership inference via relative conditional oog-likelhooods 2024.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In 2018 IEEE 31st computer security foundations symposium (CSF), pp. 268-282. IEEE, 2018.
Anqi Zhang and Chaofeng Wu. Adaptive pre-training data detection for large language models via surprising tokens. arXiv preprint 2rXiv:2407.21245 2024.
Jie Zhang, Debeshee Das, Gautam Kamath, and Florian Tramèr. Membership inference attacks cannot prove that model was trained on your data. arXiv preprint arXiv:2409. 19798, 2024a.
Jingyang Zhang, Jingwei Sun, Eric Yeats, Yang Ouyang, Martin Kuo, Jianyi Zhang, Hao Frank Yang, and Hai Li. Min-k%++ Improved baseline for detecting pre-training data from large language models. arXiv preprint arXiv:2404.0295.0 2024b.
Bihe Zhao, Pratyush Maini, Franziska Boenisch, and Adam Dziedzic. Unlocking post-hoc dataset inference with synthetic data. In Forty-second International Conference on Machine Learning,
A STRUCTURE OF NIDS AND GIDs
To extract the MIA signal, we NIDs and their corresponding GIDs together with the surrounding textual context. Examples are provided in Appendix B For each NID and its context, we generate GID by replacing the NID with a randomly generated string that matches the original format, including structural features and casing patterns. This ensures that there is no distribution shift between the NID and its generated GIDs by construction. Each resulting string, whether it contains a NID or a GID, is limited to maximum of 256 tokens. This includes both the identifier and its surrounding context. Within this limit, the final 64 tokens are reserved as a fixed suffix, and the remaining tokens are used for the prefix and the identifier itself. We ensure that both NIDs and GIDs are included full and never partially truncated. All MIA signals are computed using these context-augmentt strings. We include surrounding context to enhance the MIA signal, prior work (Shi et al.) 2024; Zhang et al. 2024b Xie et al. 2024) has shown that longer input sequences can improve attack effectiveness.
14

---

Published as a conference paper at ICLR 2026
B EXAMPLES OF NIDS AND GIDs
In this section, we show a series of examples to represent common appearances of the NIDs. We bold the parts that differ between the NIDs and GIDs. As shown in these examples, to create a new held-out sample, only replace the NID with GID. From the boxes below, we observe that priori both the NID and the corresponding GID are equally likely to be part the training data.
NID for MD5 from RefinedWeb Dolma (NID: 3/d224
For a future birthday party fairy party favors. But want to figure out different fairy, not Disney...
300x300 pixels
quick, easy project for the kids: playful, pom--oom covered trees.
Carrot & Apple Cinnamon Streusel Muffins cup of mascarpone Strawberry Banana Muffins recipe
PaperVines Vine: Got Kids? Make your own Dinosaur Fossils!
Use modeling clay and some plastic dinosaurs to create dinosaur fossils. Made this last night to test out. Turned out pretty cool. Trying to see if this would work for kids event at work. think it will! You only need 1 oz. of modeling clay per fossil.
GID for MDS from RefinedWed Dolma
3)b9)
For a future birthday party fairy party favors. But want figure out different fairy, not Disney...
300x300 pixels
A quick, easy project for the kids: playful, pom-pom covered trees.
Carrot Apple Cinnamon Streusel Muffins a cup of mascarpone Strawberry Banana Muffins recipe
PaperVine: Got Kids? Make your own Dinosaur Fossils!
Use modeling clay and some plastic dinosaurs create dinosaur fossils. Made this last night to test out. Turned out pretty cool. Trying to see if this would work for a kids event at work. think it will! You only need oz. of modeling clay per fossil.
NID
for SHA-1
from the training
of Dolma
PeS2o
(NID:
fac4 37
Data availability
COPRO-SO and INSeq datasets are deposited at the European Nucleotide Archive (ENA) under study accession: PRJEB38095. Proteomic data are available in the Mas- sIVE database under project number: MSV000085341. COPRO-Seo analysis software and INSeq analysis soft- httphhhhw....mmmmeg.oooooo/tiaaa analysis pepplleeeppppppppp a copy has been
can be accessed at http://ghhaa..oom/bbbmmmCCOOOOO ware at archived at swh:1:rev: fac-4rafoseerdsso0Hiideeeedddddd
Additional information Competing interests Jeffrey Gordon: Co-founder of Matatu, Inc., a company characterizing the role of microboyt interactions in animal health. A provisional patent on the MFAB technology has been submitted (Washington University, assignee; PCT Application PCT/US2020/042679) The other authors declare that no competing interests exist.
15

---

Published as a conference paper at ICLR 2026
GID for SHA-1 from Dolma PeS2o (GID: 9aatccaafooee11ssees5e00........
Data availability
COPRO-Seq and INSeq datasets are deposited the European Nucleotide Archive (ENA) under study accession: PRJEB38095, Proteomic data are available in the Mas- sIVE database under project number: MSV000085341, COPRO-Seo analysis software and INSeq analysis soft-
can be accessed at http:///jiiaa..ccmmmmooommmoooop ware at http://hhh......m.oooooo/o////aa analysis pipeline; a copy has been archived at sre: 9cctcfoffoo031106666644440000003
Additional information Competing interests Jeffrey Gordon: Co-founder of Matatu, Inc., company characterizing the role of byct-by- interactions in animal health. A provisional patent on the MFAB technology has been submitted (Washington University, assignee; PCT Application PCT/US2020/04267B) The other authors declare that competing interests exist.
NID for GSM8K
*QQesstoo***
Natalia sold clips to 48 of her friends April, and then she sold half as many clips May.
How many clips did Natalia sell altogether in April and May?
** *nswwr**
Natalia sold 48/2 <48/2-24 clips in May. Natalia sold 48+24 = - .448+4=72=72 clips altogether in April and May.
#### 72
GID for GSMSK
"Question" **
Natalia sold clips to 46 of her friends in April, and then she sold half as many clips May. How many clips did Natalia sell altogether in April and May?
*nswer**
Natalia sold 46/2 <46/2=23 clips in May. Natalia sold 46+23 = 446+23-69 clips altogether in April and May.
#### 69
C POST-HOC EXTRACTION OF NIDS
We describe how to extract natural identifiers (NIDs) robustly. First, we select series of regular expressions to identify potential natural identifiers. Depending the type of secret, there might be high number of false positives, therefore, we need to further remove invalid samples. We achieve that
by first removing duplicates and then running a blind baseline (Das et al.) 2024 Zhang et al.) 2024a) using the n-grams as features and different types of tabular classifiers. such as Naive Bayes classifier, Gradient Boosting Trees, and Logistic Regression. Via K-Fold, we compute the MIA score of each sample, then we compare the rank of the real sample with respect to the generated ones. If the rank of the generated sample is too low too high, we discard that sample.
We follow this procedure to robustly filter invalid natural identifiers. For instance, strings with "0123456789" unlikely be random strings and are most likely false positives. Finally, check that the final blind baseline performance at the end of the filtering procedure is close to random guessing.
Table summarizee the NID format, structure, and entropy. Additionally, for each type of NID, we have a specific way to generate them to closely resemble the original sample.
MDS. We generate the samples uniformly using this condition [a- f--FAFFFF 9] (32) following the sample casing.
SHA-1. We generate the samples uniformly using this condition [a (a-fA-FF 9] {40) following the same casing of the original sample.
SHA-256. We generate the samples uniformly using this condition [a-fA-FO- (64) following the same casing of the original sample.
SHA-512. We generate the samples uniformly using this condition [a- 1aa-f-FF-999 -9] (128)
16

---

Published as a conference paper at ICLR 2026
following the same casing of the original sample. Ethereum Address. We generate the samples uniformly using this condition (a-a-EA-FO-93 440). We select and generate only samples using case sensitivity as checksum (EIP-55: Mixed-case checksum address encoding).
Java serialization. All serializable Java classes have the serialversi onUID attribute, which is often equal to a random number, for instance, private static final long serialVersionUII
2146619729108122
Table 5: Summary of NID formats, alphabets, and entropy in bits.
NID Type
Length
Alphabet
Entropy
MD5
32 hex
[0-9a-fA- FF-F
128
SHA-1
40 hex
[0-9a-fA-F]
160
SHA-256
64 hex
[0-9a-fA-F]
256
SHA-512
128 hex
[0-9a- (o-
512
Ethereum Address
40 hex
[0-9a 9a fA-F]
160
Java Serialization
-20 digits
[0-9]
64
Although the overall computational cost for processing trillions of tokens is not negligible- approximately one week of processing on a 128-core server-several considerations are important. First, the current implementation has not been optimized, and substantial acceleration could be achieved with relatively modest engineering improvements. Second, the cost of computing each NID only on the order of tens of milliseconds, making the per-instance evaluation highly efficient. Most importantly, this approach is considerably less expensive than retraining large models from scratch. For example, a single training run of Pythia- 12b with a highly optimized implementation requires approximately 72,300 hours of GPU computation. In contrast, our method avoids this prohibitive expense while still providing meaningful insights. Finally, not necessary to process the entire dataset; robust estimates can be obtained by sampling substantially smaller subset, which further reduces the computational burden.
Once the NIDs are extracted, the GPU cost is relatively small, it consists of running the model inference once or twice, depending on the MIA used, for each identifier. All the GPU experiments conducted on Linux server equipped with NVIDIA A100 GPUs.
D DISTRIBUTION OF NATURAL IDENTIFIERS
Table Table shows for each subset and type NID the number of NIDs. We highlight that large subsets, such as Dolma RefinedWeb, have a significant number of NIDs.
E FURTHER THEORY AND PROOFS
First, we state useful definition and Lemma by Steinke et al. (023). 3, and then use them to prove Theorem
Definition (Stochastic Dominance) (Definition 4.8, Steinke et al.
2023 Let X.Y Y E R be ran-
dom variables. We say X stochastically dominated by P
P for all
e R.
Lemma [Lemma 4.9, Steinke et al. (2023)] Suppose X₃ stochastically dominated by Y1. Suppose that, for all x E F, the conditional distribution X2 that Yn and Y2 are independent. Then, X, + X₂ is stochastically dominated by Y1 + Yz.
is stochastically dominated by Yz. Assume
Here, have the proof of Theorem I
Proof: Our analysis similar to Proposition 5.1 by Steinke et al. (2023).
Fix some & Σn x x Eng, and E (1,..., m). a E V., and 8ci V
V. Using Bayes'
17

---

Published as a conference paper at ICLR 2026
Table 6: Natural Identifiers in Different Datasets. We present the number of various natural identifiers (here: SHA-1, MDS, SHA-256, Java Serialization, SHA-512, and Ethereum Address) in the analyzed datasets. The Total Number denotes the total number of natural identifiers in given dataset.
Dataset
Total Number
SHA-1
MD5
SHA-256
Java Serialization
SHA-512
Ethereum Address
dolma RefinedWeh pile train github
16989
8098
6192
21330
42
110
417
13182
5389
1938
4158
819
701
177
pile
stackexchange
121
pile train pile cc
3422
1078
2008
274
8
53
dolma algebraic stack train
2384
1264
464
612
28
pile train hackernews
2268
1340
821
dolma openwebnath train
2207
1212
727
221
20
26
pile train uhuntuire
dolma c4
791
408
301
15
dolma PeS2o
435
235
174
dolma MegaWika
383
115
200
dolma ArXiv
332
239
58
21
2
12
subsets)
pile train pubmedcentral
225
152
pile train ArXiv
207
75
122
pile github
197
pile train wikipediaen
85
1.5
66
pile test stackexchange
2
opensebmath test
46
19
20
algebraic stack test
39
28
dolma wiki
pile rest pile cc
18
pile train philpapers
pile train freelaw
15
pile test hackemews
13
dolma tulu flon
pile rest ubuntuire
pile train enronemails
0
pile test wikipediaen
0
dolma books
trann gutenbergpg 19
pile train pabmedabstracts
0
law and c-DP, we have
P(S: ( sci]
P[M(S) = +|S, = a. Sci = PPS = a
(SM = {|5cs Sci
P[M(S) = S = a, Sei = scil
P[M(() = US: = Vi,j = 8<1
P[. = Visl
([M(S) = t|S, a, Szt s21 M4
(SM = 1|: V 8ci V.
1+ Ka, SI
P P S.
I (IV) 1)ee* Vi l+
Additionally, we can observe that for all (I....mm, we have that P P|rank(t;, St) S rl] E P[S = lig]. Therefore, we can bound
PFrankk(1 S.) > (s)) S, 88c)
e
1 + (1V/) 1)e= SPSS = t.,j M(S) = t, 524 = scol =<ill 'Vvil -1+ e
1zee
1 + (VVil 1)e= < PPrrank(ti, St) S M(S) S =8ci]= 5
VV 11+
18

---

Published as a conference paper at ICLR 2026
rje
Plrank(t,, St) S <r: t, SKt =<c]] E
1 ([Vil 1)
[ l+
Thus, (4, S:) $ M() = Sei =8i) -
ric
With that, we can prove the result
by induction. We inductively assume that Wm-1 == Σ m 1-
i==1 [rank( S.) S ri] is stochastically
dominated by W which is Bernoulli( 1i|-++e- )m-1 As above, [rank(t,, St) S ryl stochastically
dominated by Bernoulli(<<+11 Tm V... VT. By Lemma 4.9 by Steinke et 2023 Wm Wm-1
[rank (Im, S rm] stochastically dominated by Bernoulli [i M
l+e"
1=1
To show the case (e, -D., we will first state Lemma 5.6 by Steinke et al. (023). Then following the analysis of Proposition 5.7 and Theorem 5.2 by [Steinke al. (2023), we prove Theorem 2
Lemma [Lemma 5.6, Steinke et al. (2023) Let P and Q be probability distributions over y Fix e, 8 2 O. Suppose that, for all measurable $ V, have
P(S) S E -((S) + 8 and Q(S) S ef P(S) + 5.
Then there exists randomized function Ep.Q y + {0, 1} with the following properties.
Fix p [0, and suppose X Bernoullip).. If X sample Y P: and,
0, sample
Y ~ Q. Then, for all E V, we have
Xx--erronll(pp) X-XP+(1-X)0 1 = = Y Y== =3] S p+ (1 11-1ppp p
p
Furthermore,
(y<p(Ep.o())22 (Y) and Ey~qlEP.Q(M)5
Theorem Let M V.....
x Vm - Ei .... Em be an (e, 8) DDP mechanism under replacement. Let V12 x Vm be uniformly random. Lei T M(S) E Σ, ... x Eim Then, for all E IR,
all E E1 x ... x Em in the support of T, all rı, I' with r; S [Vi. and [Vsl |vgl-+tee S 1,
reet
[rank S ri) 2 r T $)
8 a8
where
p 2 v),
max Pg - ml).
rie
m
$ - Bernoulli
[v1] -
Theorem shows the analogous result of Theorem Dusing (s, O)-P)
Now, we show the proof of Theorem 2
Proof: Our analysis follows Proposition 5.7 and Theorem 5.2 by Steinke al. 2023
For E (O...., m} and 8cx E V1 x ... x V,, let (sgi) denote the distribution on Σ, x ... X Σm
obtained by conditioning (S) on Szi sgg. We can express this convex combination:
M(5r))= =
Σ SS.EViX-..VV
M(s51.83)
= szd.
19

---

Published as a conference paper at ICLR 2026
Additionally, for all i {l...., m), and Vi, define (sgi, a) as the distribution Σ1 x ... x Em obtained by conditioning on Sg: $z, and Si+1 # a, as follows:
a) DEV, DEV,
E
[V - b).
We define S - V1 Jl.....m., we have that the distributions P and Q on Ei...., Em. and let EpQ Ei...., 2m 7 {0, 1) be the randomized function given by Lemma 2 (using Vi ....... Vi, all Ej x .... Em, and all a E V,, we have
Vm represent uniform sampling over V1 x x Vn- For all
MT). Specifically, all sgi E
Ps- T+ TV
(T) 1|55 =ghh = f)s [
1 +
MGS. (Meca)) (T)]S (s<ir 2010)111 1-8.
For simplicity, for all i (l...., mj. we define (M) = -aavv, MS(S and, for b E Vi we have
Es I.s-M---WW.TT-MMSSS
(s<s. b) [V268
For all E V,, let j rank(li, a), where use 1-based ranks: rank corresponds to the highest-scoring element, rank to the next, and so on. So we can rewrite
(ish)x-WW.T-MS))..l. a Ess(se..)) 115 sci, (Vs-.V....XV.77MMM (rank((t, S.) = 5) ()) 1|5 88g T f].
Note that there is a bijective relationship between and j. Therefore, we have that
riee
S,) & r2 A EM( 1|5gi = sgi,T=
V
1
For E mm,..., SE E V Vms and t E Eg x ... Em. define
W,(,,))= = Σ [rank S smd EM(ee.v))() =
Σ
(rank((4,S)) S., A EM())Lv))() = 1]
K
w5(1) Es.50 S.(1),
iEDI
where, for each E (1....,m) independently, S(t); Bernoulli (va]-1+er
rie"
By induction and Lemma 1 for any j (1. and E En .... Em.. the conditional distribution (S.
1) where S + Vi Vm is stochastically dominated by
(t..
For E V1 X ... x Vm and t E En x .... x Em, define
m
F(s,t) = Σ (EM(se..))() = =0],
so that
W (s, () = Σ
Irank(!;, St) ()) F(,,
Srd
20

---

Published as a conference paper at ICLR 2026
Since the conditional distribution (S. = =). where S + V1 x... Vm is stochastically dominated by Wm (t), W,, is stochastically dominated by the convolution Wn, (T) F(S, T). Finally, F(s,t) t) is supported on {0, 1....,m} and
[[F(s, Σ Mleccc) (T) 0] S 6
V.
Since W., (T) does not depend on S, the input S does contribute to the dependence between F(S, T) and Wm (T), so we can elide this input in the statement, that is, F(T) F(S, 7) for S drawn from an appropriate distribution.
Given these constraints, we can formulate finding the optimal distribution F() for given t e Σ1 X
Em and
linear program:
maximize
PW (W: + F(t) 2) Σ P(F(t) = (t)
subject to
[F[F(t)] = Σ P = ( Σ Vil
1=0
Σ PF(F(t) = = 1, and
Pr ( = 2 0 Vi E {0, 1, (0.1....,,m) m].
where W(t) = Σm (rank S.) S r:] for Bernoulli [M]--++e
By strong duality, the linear program above has the same value its dual:
minimize subject to
8
VI
+
1=1
B-i+B2
+ W
(W())
2 1- Vi
10, lo..,,
220 0.
Any feasible solution to the dual gives upper bound on the primal. So, in particular, the solution provided by
B = Pw-[W** 2 v).
max (0)) u {
(Pw. ( 2 - B - :iE
........m))))
where W is distribution on R that satisfies P [ 2 - 2 Pw(W(() 2 v- i for all i E {0, 1, 1....,m) and all in the support T.
F SAMPLE COMPLEXITY ANALYSIS ON THE CARDINALITY
natural question is what advantage arises from increasing the cardinality =|V] (for simplicity assume that all sets VÚ have the same cardinality). By Theorem [ the probability that a mechanism produces correct guess within the top-r elements is stochastically dominated by Bernoulli random variable with success probability
Te
with S 1.
c-
Thus, if we consider m independent guesses, the total number correct guesses stochastically dominated by Binomial(m, p) random variable.
21

---

Published as a conference paper at ICLR 2026
Applying the Bernstein inequality to this binomial distribution yields the following tail bound: for any 3 E (0, 1).
2p(1 p) log
I
p
log (
+
log" (t)
3,
3m
where S ~ Binomial(m, p) and 8/m represents the empirical accuracy (i.e., the observed fraction of correct guesses).
On the right-hand side of this inequality, the first term p corresponds to the expected accuracy, while the remaining terms form the concentration margin. Among these, the dominant contribution for large m and e is
2p(1 - p) log (
To understand the scaling, observe that for fixed r and s, we have
p O
p(1 p) ( (
Consequently, the concentration margin decays as
This shows that the accuracy concentrates faster as the cardinality innrreases: compared to the binary case (c 2), the deviation shrinks by factor of v2/c. In other words, larger cardinalities yield tighter accuracy concentration bounds, providing a clear sample complexity improvement over the 1-out-of-2 setting.
G RANDOMIZED RESPONSE ANALYSIS
In the following subsections, we analyze in detail our novel auditing method using randomized response.
G.1 RANDOMIZED RESPONSE PORMALIZATION
We now provide the complete derivation of the auditing bound for randomized response in our setting. Formally, we are given m samples, each corresponding to a private integer v; {l,...,ch c}. The randomized response mechanism releases
U; with probability + Y: Va + Usa
with probability
where 7
ensures s-DP.
The auditor ranks the possible values from most to least likely. Since y; is always the most likely input to produce itself, the optimal strategy is to rank y; first and order the remaining values randomly. The probability of correct guess is therefore
[|correct]
which exactly matches the bound Theorem
G.2 ADDITIONAL RANDOMIZED RESPONSE EXPERIMENTS FOR r
Figure 4a and Figure 4b show additional results for the randomized response setting. We highlight that our method is tight for rank threshold r = 1, and the higher the E, the larger the improvement given by a larger cardinality
In the specific case of randomized response, r > 1 is not tight, as there is no further information to exploit, the attacker's best response is to give the mechanism response the first choice and
22

---

Published as a conference paper at ICLR 2026
1.0
0.4
10a
10a
10
10a
10f
Number of samples
Number of samples
-- Ideal
[4, 1)
dee (128. 1)
d (128. 64)
Ideal
[4. 1) +e (128.
-de (128, 64)
Steinke al. (2, 1)
(128,
Steinke
(128.
(a)
Figure 4: Randomized response mechanism with E {1,8). The red dashed line indicates the real e of the mechanism, while other ones indicate the estimated lower bound of with 99% confidence for different choices of cardinality c, and rank threshold The (2,1) case corresponds to the method proposed by [Steinke al. (2023). Each label is written (cardinality c, rank threshold r))
the other ones in random order. The randomized response mechanism returns random value with small bias towards the private one. From the auditor's point of view, the best attack returns the privatized value as the first option and the others in a random permutation. This means that the first value has some information about the private value, while the other ones have information. Specifically, the probability of the first sample being the private sample is c-I+eF while for the other ones it is c-1+t" (these results come from the randomized response output distribution). If we consider certain threshold r, Theorem || roughly states that the probability of being correct is bounded by c-1te However, based on our attack, the probability that the correct value is in the top-r is c-I+e= + r-1
c-1+e= For r 1, we can observe that the two results match, while for r > 1, the attacker's probability is always strictly smaller than the ideal one (except for s = 0). Theorem ] and Theorem[zgiv this additional flexibility of selecting the top-r threshold; however, depending on the setting, this might be more or less useful.
H DP-SGD AUDITING
In the following subsections, we show additional experiments for DP-SGD auditing and the pseu- docode of the auditing procedure.
H.1 FURTHER EXPERIMENTS ON DP-SGD AUDITING
Figure shows results for experiments conducted following settings described in Section 4 for other Pythia models (70m and 160m) (Biderman et al. 2023). The experiments substantiate observa- tions from larger models, and the proposed framework constantly outperforms the baseline method proposed by Steinke et al. (203)).
10a
10
Eexemated
Eaximatted
10a
10a
10
10:
10
1000
10
100
Ereal
Eycal
2 (Steinke et al.)
8
32
(Steinke et al.)
32
(a) 16thia-160m
(b) Pythia-70m
Figure 5: Impact of cardinality (c (2,8,32) estimation for other Pythia models.
23

---

Published as a conference paper at ICLR 2026
Moreover, explore different values of the parameter to estimate the lower bound of The results shown in TigureOconfiing our choice of parameter r = 1, thus providing the tightest and most reliable outcomes for our post-hoc DP auditing framework with NIDs.
10
10
Exntimated
10a
5.0
10.0
100.0
10.0
100.0
r=2
r=
(a)
32
c 8
Figure 6: Impact rank r == [1,2,4] on estimation for Pythia-Ib.
H.2 CONFIDENCE INTERVALS ACROSS 4 RANDOM SEEDS FOR DP AUDITING
Table 7 shows the confidence interval across 4 random seeds using Pythia- The results show low standard deviation across all of the settings.
Table 7: DP auditing across seeds. Mean estimated for Pythia- 1b computed across 4 seeds.
cardinality
Estimated E
2
0.086 +. 0.021
0.979 0.028
2
10
0.106 = 0.020
2
100
0.245 = 0.023
8
0.720 + 0.144
10
0.789 0.144
100
1.094 0.129
8
8
2.329 + 0.058
32
1.761 + 0.226
32
10
1.830 1: 0.231
32
100
2.178
0.218
32
00
3.775 = 0.067
H.3 PSEUDOCODE FOR DP-SGD AUDITING
Algorithm summarizes approach for auditing DP-SGD using the results given by Theorem 2
We highlight that when for all E {l...., ..) we have VV] 2 and r; = 1. the algorithm is equivalent to the fixed-length dataset proposed by Steinke et al. 2023
24

---

Published as a conference paper at ICLR 2026
Algorithm 1: Adapted version of the black-box DP-SGD Auditor algorithm proposed by Steinke
al. (223) for fixed-length dataset with NIDs.
Input: Dataset Do. sets of canaries V (Vi...., V J, the target ranks .1....: :......mm T'n and the
DP-SGD settings
1: for E (I,..., m do
2: S; + ]
3: end for
4: D1 := (Vis, : [1....,m]}
5: D= D1
6: Run DP-SGD on D with given parameters, yielding {wo, we ..... wo)
7: for E {1,.... m) do
8: Yı, < SCORE(V ; Vj [M]]]
9: + arrgorr(ty,..o. M [[]]
10: end for
11: c+0
E (I,..., m) do 13: i; S then
12: for
c+1
15: end if
end for
17: return Compute Élower using the formula given by Theorem
ADDITIONAL EVALUATION OF MIAS PERFORMANCE
Table 8 Table 10 and Table II show the MIA performance of the individual MIAs the subsets of the Pile using the NIDs, where the goal is to distinguish the real from the generated ones. Furthermore, for completeness, we have Table Table 13 Table 14 and Table 15 that show the MIA performance using TPR @ 1% FPR.
Table 8: MIAS on NIDs for Pythia- The AUC for MIAs between the NIDs and the corresponding
GIDs on various subsets of the Pile dataset.
Stack Exchange Train
Ubantu IRC Train
Wiki- pedia(en)
PubMed Central
Hacker News Train
Full Pile
Github
ArXiv Train
Average
MIA
Train
Test
Train
Test
Test
Train
Train
Train
Train
Test
Loss
51.1
50.3
60.5
549
Min-K%
$7.6
51.0
68.4
50.6
50.7
51.2
51.1
50.6
50.7
60.5
52.3
51.0
51.8
50.9
Min KS++
56.9
51.4
71.2
50.3
50.8
51.9
51.1
51.3
51.1
69.7
53.2
50.9
56,2
51.2
ReCALL
53.5
50.6
50.3
50.0
51.1
50.3
51.3
50.2
57.8
50.1
50.2
51.6
50.5
(HCine)
51.3
50.1
53.3
50.4
50.4
51.4
50.5
$1.9
50.8
50.3
50.4
50.0
51.0
50.6
Hinge
58.7
51.5
50.4
50.4
549
50.8
Table 9: MIAs NIDs for OLMo-7B. The AUC for MIAs between the NIDs and the corresponding GIDs on various subsets the Dolma dataset. All but Proof Pile 2 (Test) are part of the training data of Dolma.
Dulma
Average Train
MIA
C4
Pe52o
MegaWika
ArXiv
RetinedWeb
Algebraic Stack
OpenWebbaath
Proof Pile (Test)
Loss
50.1
50.2
50.2
51.2
50.1
$0.0
S0.9
$0.6
50.4
Min-KS
50.1
50.2
30.5
51.3
50. 1
$0.5
51.7
51.3
50
Min-KS-4+
ReCALL
50.2
51,0
50.7
RoCALL (ftinge)
50.3
51.4
50.2
51.9
50.2
50.7
50.
$1.0
50.7
Hingo
50.1
50.2
50.2
50.9
50.1
50.0
507
51.0
5033
J FURTHER EXPERIMENTS ON DI
We evaluate DI on various models and data subsets. More concretely, we experiment with Pythia models 12b, 6.9b, and 2.8b and OLMo-7B. Additionally, we investigate the impact increasing the number of samples in the suspect set. All results summarized in Figure 7
25

---

Published as a conference paper at ICLR 2026
Table 10: MIAs on NIDs for Pythia-6.9b. The AUC for MIAs between the NIDs and the corre- sponding GIDs various subsets of the Pile dataset.
Paal File
Gitbub
NtackBbehungs
UlumtilCC Tian
Wikipedian 17an
PathhledC Trane
Hackorrowe Trats
Pil-CI:
ArSi 13xm
Ateeage
AIA
Trile
Tee
Trass
172in
Tixt
Trads
Loo
$7.5
50.4
65-3
S1.1
50.3
50.5
50.5
50.7
50.3
63.7
30.8
20.6
54.7
SALT
16.0
$1.11
66.3
51.4
9019
90.6
11.
91.7
56.3
51.
ReCALL
52.4
51.4
553
51.0
50.1
50.5
51.3
ReCALL (Higge)
51.3
50.6
13.3
51.3
30.1
50.1
51.0
50.9
50.3
$3.6
30.0
50.0
51.0
50.5
inege
573
307
563
31.6
30.4
3033
302
3011
ML2
03.7
30.
303
34.0
24.
Table 11: MIAs on NIDs for Pythia-2.8h. The AUC for MIAs between the NIDs and the corre- sponding GIDs various subsets of the Pile dataset.
Githab
StackEschugg Viol
UlustalCC Tran
Wikipslian Vrans
PalMMalCrrtal Irane
Hocket News
Pic-CC
ArSi 11xn
MIA
Irun
Iest
Trsas
Toit
Treas
'Int
C2.5
50.0
50.2
51.5
90.6
52.3
50.3
Ming
<3.1
52.4
59.5
82.9
50.6
50.3
91.2
50.1
80.6
61.6
51.6
50.5
53.0
51.8
34.1
52.3
38.2
34.5
93.9
30.1
902
50.2
M0.
73.6
52.8
51.
54.2
5L.
53.3
31.1
64.4
5011
9222
30.8
31.1
53.2
51.2
(lligg)
63.0
93.6
51.1
50.3
902
90.3
91.
53.7
90.6
Table 12: MIAs NIDs for Pythia-12b. The TPR @ 1% FPR for MIAs between the NIDs and the corresponding GIDs on various subsets of the Pile dataset.
Githuh
StckFarrhange
UhantstRC
Wilipedoon
Pat Palllee
New
PlleCCC
Arhiy
Anergge
Lass
010
0.1
1
ReCALL
1.2
0.2
1.5
0.0
1.0
1,5
1.4
0.7
0.8
1.0
1.1
015
1.1
1,2
18
1.5
86
1.1
05
140
0.1
1.5
1.3
28
1.3
1.3
Bings
1.3
03
0.5
Table 13: MIAs on NIDs for Pythia-6.9b. The TPR @ 1% FPR for MIAs between the NIDs and the corresponding GIDs on various subsets of the Pile dataset.
Eall
Littur
Stukktsthange Trii
UltantatIC: Tian
Wiltpedoon Trato
Pahhluut Centiaa Tisln
HackerrNexx Triis
PleeU Trais
Arrkhr Tisis
Amerage
MIA
Tiais
Tex
Tinis
Tox:
Teat
Tixis
Tex
Lou
1L3
1.9
(10)
1.1
044
011
0.5
8/1
1L3
1.8
[1.
1.b
11.
1.5
[1)
0.5
1.11
0.9
11.
1.0
1.3
1.0
[1.
Max
0d
0.7
1.0
0.6
1.2
1.4
0/4
1.3
0.9
1.1
09
0S
000
0.3
010
055
08
1,2
67
63
122
019
06
103
K CONTROLLED ABLATION OF DI
In this section, we investigate how the main design choices affect the behavior of our method. To carry out this controlled amalysis. it is necessary to train model for each configuration under study. Fully training a large model for every variation is computationally infeasible, and therefore, following the procedure described in Section 4 we finetune smaller model that serves practical proxy for evaluating the influence of individual components. This controlled setup enables us to enforce the formatting rules of task-specific NIDs with precision, ensuring that the experiments isolate structural properties rather than reflecting irregularities present in real-world data. The following subsections present the corresponding evaluations conducted within this framework.
K.1 COMPARISON WITH INJECTED CANARIES
In this subsection, we compare the performance of NIDs and commonly used injected canaries. Although injected canaries fall outside our post-hoe threat model, this controlled setting helps contextualize the strength of the NID leakage relative to existing auditing methods. In particular, we consider four types of canaries: (1) random alphabetic strings of length 32, (2) the NIDs (from the GitHub subset of the Pile test set), (3) fully IID strings (in-distibuttio text from the Pile test set), and (4) random hexadecimal strings of length 32. For each type, inject 100 canaries into the training data and run DI. The resulting p-values for each canary type are reported Table [6] Overall, find that NIDs perform competitively with other injected canaries. They capture privacy
26

---

Published as a conference paper at ICLR 2026
Table 14: MIAS on NIDs for Pythia-2.8b. The TPR @ 1% FPR for MIAs between the NIDs and the corresponding GIDs on various subsets of the Pile dataset.
Fall Pila
Lithur
SowSkEachange
UhantalRCC Tran
Willpedann Iten
Pah-leeC Tran
HacherNioss Trats
PlleCC
Artir Trais
Amerage
MIA
Tron
The
Trans
Trus
11an
Loo
1.1
0.0
1.4
100
0.0
1.3
04
04
0.8
0.5
1,0
0.7
114
Min-K
1/4
1.1
ReCALL
0.1
0.5
6.1
000
MelAALL (ttigge)
1.3
0.7
1.8
077
0.3
177
64
1.1
105
lange
051
164
163
114
08
1.3
04
6.2
15
12
019
119
027
11.8
Table 15: MIAs on NIDs for OLMo 7B. The TPR @ 1% FPR for MIAs between the NIDs and the corresponding GIDs on various subsets of the Dolma dataset.
Dolma
Average Train
MIA
C4
PeS2o
MegaWika
ArXiv
RefinedWeh
algebraic stack
opensebmaath
Proot File (
Loss
0.4
0.9
0.4
1.2
0.5
0.9
0.3
0.0
0.7
Min-K%
0.7
0.5
1.5
0.3
0.9
0.5
0.4
0.0
0.7
Min-KSS KS5-
ReCALL
0.7
0.6
0.7
0.7
0.9
0.5
0.7
ReCALL (Hinge)
0.7
0.3
1.1
0.2
0.2
1.1
2.2
0.0
0.8
0.
leakage more effectively than IID canaries and outperform random hexadecimal canaries, though some carefully crafted canaries, such as alphabetic strings, exhibit slightly stronger signals.
Table 16: P-yalues for DI on Injected Canaries. P-values obtained for each injected canary type.
Canary Type
P- P-Vulue
Alphabetic
< 1.00 x 10 300
NIDs (All subsets)
4.17 x 10-21
NIDs (GitHub subset)
3.31 x 10 10-156 156
IID
4.55 x 10
Hex
7.00 x 10
K.2 MISIMPLEMENTED GENERATOR
To study the benefits of our method for operating held-out data from the same distribution, we analyze scenarios in which the held-out data are generated from a distribution that differs from the distribution of the suspect set data. We evaluate the impact of incorrectly implemented generator. If the GID generator is not implemented properly, this induces a distributional shift between NIDs and GIDs. Starting from the correct generator, we construct three misimplemented variants that (1) flip the casing of alphabetic characters, (2) produce identifiers whose length is off by one, and (3) produce identifiers whose length is off by two. We then run DI on models finetuned on correct NIDs, but evaluated using imperfect GIDs, using the same protocol in previous subsections. Table 17 reports the resulting p-values for member and non-member datasets. The results show that DI is sensitive to certain generator failures: for example, incorrect casing yields strong signals for both members and non mon-memmers, substantially inflating false positives. In contrast, modest length mismatches have smaller impact on non-member p-values, likely because Min-K% and Min-K%++ only depend on the -op-k tokens and are therefore relatively insensitive to appending or removing a small number of additional tokens. This analysis complements our microanalysis of NID formats and highlights that both structural differences and shifts in the identifier-generation distribution can meaningfully affect DI outcomes.
Table 17: Misimplemented Generator. P-values for DI on member and non-member datasets under different GID generator failures compared to the correct generator.
Generator Failure
P- V-Vuuee Members
P-Vulee Non-Members
Wrong Case
< 1.00 x 10 10-300 300
1.16 x 10
Length Off By
3.64 10-99
5.39 10 10-02
Length Off By
< 1.00 x 10 300
3.40 x 10
Correct Generator
3.31 10
9.83 10-90
27

---

Published as a conference paper at ICLR 2026
10"
10"
10:2
10.2
pavalue
10:1
10
10-4
10"6
10-1
10
10-10
10-10
Number samples
Number of samples
Pile (All subsets)
Pile-CC
Pile (All subsets)
Pile-CC
PubMedCentral
ArXiv
PubMedCCntral
Pile Github
Pile StackExchange
Pile Github
Pile StackExchange
Pile HackerNews
Pile UbuntuIRC
Pile HackerNews
Pile UbuntuIRC
Pythia 12b
(b) Pythia 6.9b
10
10-2
Pvvalue
10-1
Pavalve
10-
10
10
10
-1
10
25
50
75
100
10
25
50
75
100
Number of samples
Number of samples
Pile (All subsets)
Pile-CC
Dolma algebraic stack
Dolma megawika
Pile ArXiv
Pile PubMedCentral
Dolma arxiv
Dolma open web math
EtccaExc
Dolma pes2o
Pile HackerNews
Pile UbuntuIRC
Dolma refineweb
Proof Test
(c) Pythia 2.8b
(d) OLMo-7B
Figure 7: The p-value for different Pythia models and OLMo on subsets of the Pile or Dolma datasets, respectively. We show results for different numbers of samples in the suspect set. For the Pythia models, the solid lines show the training subsets, while the dashed lines are for test subsets (not included in training). The Proof Pile 2 (Test) subset has fewer than 100 NIDs. Hence, their lines plotted only until the highest number of samples is available. We observe that for training sets, the p-values overall decrease with the number of samples, enabling the detection of the private data in the model's training set. The test set's p-values are constant, suggesting that no false positives are achieved.
K.3 IMPACT OF MIA STRENGTHI
We next investigate how the strength of the underlying membership inference attack affects DI performance with NIDs and, consequently, DP auditing. While our framework treats the MIA as plug-in component, stronger MIA signal should intuitively translate into more powerful DI tests. To validate this, we follow the controlled setup: we finetune Pythia- 1b on 100 NIDs from the GitHub test set and run DI with four MIA feature configurations. Specifically, we use (1) the original MIA feature set, (2) the original features augmented with CAMIA (Chang al. 2024), (3) the original features augmented with SURP (Zhang & Wu 2024), and (4) the combination original features, CAMIA, and SURP. Table reports the resulting p- valuue.. We observe that incorporating stronger MIAs, particularly CAMIA, substantially improves DI effectiveness, as indicated by lower p-values, and that the trend is consistent: the richer the MIA feature set, the stronger the DI signal.
28

---

Published as a conference paper at ICLR 2026
Table 18: MIA Strength. P-values for DI when using different combinations of MIA feature sets, illustrating how stronger MIAs improve the DI signal.
MIA Signal
P-Value
Original Features CAMIA
1.00 x 10 300
Original Features + CAMIA + SURP
< 1.00 x 10 10-300 300
Original Features SURP
4.17 x 10 10-211
Original Features
3.31 x 10-156
K.4 COMPARING DIFFERENT TYPES OF NIDS
We also study how the structure of an identifier affects DI risk in a controlled experiment (see Table 5 for the exact formats). For each NID format (Java serialization strings, SHA-512, SHA-256, SHA-I, MD5, and Ethereum addresses), we generate set of identifiers that follow the corresponding pattern, finetune Pythia-lb on 100 instances that type, and then run DI. Table [9 reports the resulting member p-values. Longer and more structurally complex identifiers, such as SHA-512 hashes, tend to yield stronger DI signals, whereas shorter formats such as MD5 hashes produce weaker but still highly significant results. Beyond length, the character composition also matters: Java serialization strings, which only contains digits, produce a stronger DI signal than SHA-512 despite being shorter. Overall, these results indicate that our framework is robust across range of realistic NID structures, with DI performance improving as identifiers become more informative and distinctive.
Table 19: NID Structures. P-values for DI for different NID formats, showing how identifier length and structure influence the strength of the leakage signal.
NID Structure
P-Vulee
Java Serialization
4.17 x 10 (0-
SHA512
1.67 x 10 1175
SHA1 Ethereum Address SHA256
1.95 10
8.89 10-44
MD5
7.00 10 223
K.5 NUMBER OF NIDS
The number of NIDs significantly affects the statistical power of the DI test. To study this effect, we finetune Pythia- lb on 100 NIDs from the GitHub test set, and then run DI using only subsets of size à E (50, 60, 70, 80, 90, 100) of these NIDs. Table (ablee20ssore shows the resulting member p-values. As expected, the p-values decrease monotonically as the number of NIDs increases, illustrating the sample-complexity benefit of having more identifiers available in the suspect dataset.
Table 20: Number of NIDs. P-values for DI function of the number of NIDs used, demonstrating the sample-complexity benefit of having more identifiers.
Number of NIDs
P- Value
50
1.01 x 10 68
60
7.92 x 10-84 84
70
2.07 x 10 10-101 101
80
2.23 x 10
90
1.16 x 10 137
100
3.31 x 10-166
K.6 TASK-SPECIFIC NIDS
In this subsection, we detail our case study on constructing task-specific NIDs for GSM8K, which consists of grade-school math word problems that require multi-step numerical reasoning. For each selected GSM8K problem, we use G to rewrite the problem as a numeric template by replacing every concrete number in the statement and solution with variable; for example, the original solution
29

---

Published as a conference paper at ICLR 2026
fragment "Natalia sold 48/2 <48/2-24 clips in May. Natalia sold 48+24 <48+24=72m77 clips altogether in April and May. ##### 72" is rewritten as the template "Natalia sold n/2 clips in May. Natalia sold n + n2/2 3n/2 clips altogether in April and May.", where stands for the original 48 and all derived quantities become functions of n. We then sample new values for these variables, update the problem text and solution accordingly, and have GPT-5.1 verify that each instantiated problem-solution pair is logically correct and self-consistent. In our DI setting, we treat one instance per template as the task-specific NID in the suspect set and the remaining instantiated variants as the corresponding GIDs drawn from the same task- specificc distribution. To validate this approach, we finetune Pythia- lb on 100 such GSMSK-derived NIDs and run DI on the resulting suspect sets; as shown in Table in the main paper, these task-specific NIDs enable statistically significant DI on GSM8K. Moreover, the p-values decrease as the number of NIDs increases, reflecting the expected strengthening of the DI signal with additional identifiers.
K.7 COMPARISON WITH EXISTING DI METHODS
To compare the effectiveness of our method, we not only compare the effectiveness of the individual canaries, but also the performance of the DI methods. For each DI method, we finetune Pythia- lb with the corresponding canaries and apply the corresponding statistical test. Following Maini et al. (2024), use IID samples and their corresponding statistical test. For For Zornzhag et al. (2024a),
the Hex and A Alphabetic random strings of length 32 and apply our statistical test, as their method lacks one. For Zhao al. (2025), we still use the entire subset during the generation phase. While this gives an unfair advantage to the method by Zhao et al. (2025). it is necessary to prevent an even larger distribution shift in the resulting generated held-out set. Additionally, the reported time includes both generation and calibration. The generation time is measured in the pre-training setting, on four A100 GPUs, whereas all other experiments use a single A100 GPU.
In Table 21, we report the results from the GitHub subset. We observe that for the member subsets, our method shows strong performance, with lower p-values than Maini et al.] (2024) and /Zhao et al. (2025). For the non-member subsets, the p-values for all methods are close to T.0. Notably, the exccution time of our approach (21.52 minutes) is close to that of Maini et al. (2024) and the implementation of the approach proposed by Zhang et al. (2024)), yet substantially more efficient than Zhao et al. (2025).
Additionally, in Table 22
conduct further evaluation using the whole Pile dataset. In this setting, we are unable to include Zhao et al. (2025). as the method relies on low distributional variability to function effectively. The results show similar trend that in the GutHub subset.
Table 21: DI Comparison (GitHub Subset). Comparison of DI methods including members/non- members p-vauues and execution time (in minutes) on the GitHub subset.
DI Method
P- Value Members
P-Vulue Non-Members
Time
LLM DI (Maini et al.
(2024)
9.79 x 10 122
122
1.05 10-2
20.43
Unlock DI (Zhao al." 2025
5.00 x 10-5
1 x 10
2122.37
Zhang et al. 2024a (Hex)
7.00 x 10 10-23
6.70 x 10-2
21.18
Zhang et al. 2024a Alphabetic)
1.00 x 10 10-300
5.42 10-1
20.83
NID DI (Ours)
3.31 x 10
9.83 10-1
21.52
Table 22: DI Comparison (All Subsets). Comparison of DI methods including members/non-
members p- values and execution time (in minutes) with samples from the Pile.
DI Method
Value Members
V-Vuuue Non-Members
Time
LLM DI (Maini et al. 20244)
8.48 x 10
5.85 x 10
20.73
Zhang et al. 2024a
(Hex)
7.00 x 10-23
6.70 x 10
21.18
Zhang et al. 2024a
(Alphabetic)
1.00 x 10-300 300
5.42 x 10-1
20.83
NID DI (Ours)
4.17 x 10-211
3.76 x 10-1
20.67
30

---

Published as a conference paper at ICLR 2026
L DIRECT COMPARISON WITH ZHAO ET AL. (2025)
To further validate our DI method, we compare against Zhao et al. (2025) in the pretrained settings. For fairness, we replicate their experimental setup, including the number of samples reported in Table A2 of (Zhao et al. 2025). We evaluate three subsets of the Pile dataset using the Pythia-6.9b model to ensure coverage across various settings. As shown in Table 23 our method achieves substantially better performance and efficiency, being more effective and orders of magnitude faster than the method Zhao et (2025).
Table 23: DI Comparison. Comparison of p-values and end-to-end execution time (in minutes) per subset on Pythia-6.90
Subset Pile-CC GitHub
V-Vulue (Zhao al. 2025
P-Value (Ours)
Time (Zhao ef al., 2025
Time (Ours)
5.64 x 10
2.18 10-31
1395.87
46.17
8.50 x 10 10-3
3.65 x 10 10-14
2106.97
34.41
Ubuntu
4.23 x 10-2
3.01 10 10-14
805.22
21.33
M
LIMITATIONS
Our method relies on datasets that contain NIDs. While we have demonstrated that they are widespread, it is possible that not all types of NIDs have been identified; future work may un- cover more, which would only enhance our results by increasing the number of real samples.
N
LLM USAGE
We used LLMs solely polish author-written text (grammar, clarity, concision). All suggestions were reviewed by the authors, who take full responsibility.
31


Reviews:
[{"review_id": "TfcK7Xm57b", "reviewer": "Reviewer_qNYy", "summary": "This work aims to address two of the most significant and challenging research questions in the field of privacy auditing for LLMs: the post-hoc implementation problem of differential privacy (DP) auditing, and the dependence of dataset inference (DI) on independent and identically distributed (IID) held-out sets. The authors identify two core shortcomings of current LLM privacy auditing tools in real-world deployment: the infeasibility of DP auditing and the IID constraint in dataset inference DI. To address both issues, this work introduces a novel and elegant concept: Natural Identifiers.", "questions": "see weakness", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The NID approach provides a clever, elegant, and theoretically sound solution to a long-standing and practically intractable bottleneck in the field of DI: the “IID held-out set” limitation.\n2. The proposed approach seems interesting. It operates post-hoc and is capable of generating IID samples with zero distributional shift.\n3. The empirical results seem promising.", "weaknesses": "1. The proposed method in this work relies entirely on the existence of Natural Identifiers, which are found almost exclusively in technical and code-related corpora (e.g., GitHub, StackExchange) and are virtually absent in general text corpora such as books or news articles. Therefore, this work does not appear to be a general-purpose LLM auditing tool. The authors deliberately avoid discussing this major limitation in the paper.\n2. The core differential privacy claim in this paper is that it audits pre-trained LLMs; however, the differential privacy experiments seems are conducted only on fine-tuning, not on pre-training.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kiEOlBCPyb", "reviewer": "Reviewer_6fad", "summary": "This paper studies post-hoc privacy audits for evaluating and quantifying LLMs privacy risks. \nIt targets (i) auditing differential privacy (DP) claims: empirically estimating a lower bound on the DP budgets and (ii) dataset inference (DI): inferring whether an entire data subset was used to train the model. \n\nThe key idea is to use Natural Identifiers (NIDs)—structured, random-looking strings (e.g., hashes, shortened URLs) that naturally appear in the training set—and to generate additional strings from the same distribution. NIDs enable the generation of unlimited additional random strings from the same distribution, serve both as canaries for DP auditing and as same-distribution held-out data for DI.", "questions": "See above.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Studies an important problem of LLM privacy audit\n\n- Good articulation of the limits of prior privacy audits", "weaknesses": "1. Dedicated injected canaries vs NIDs. It’s unclear how results depend on which NIDs you pick. Prior work uses dedicated canaries injected from out of the training set; yours are random strings within the training set. Please quantify whether in-distribution vs OOD canaries change audit power and bias.\n\n2. Why tighter DP lower bounds / lower sample complexity? You reported \"Our privacy auditing with NIDs improves the lower bounds on the privacy parameters of an algorithm compared to the auditing framework by Steinke et al. (2023). It also significantly reduces the sample complexity, i.e., it requires fewer NID canaries.\"\n\n3. DI performance/gains look modest. Is this because of the inherent limitation of your work in which you infer whether an entire data subset was used to train the model by reasoning only on NIds within the dataset, not the whole dataset?\n\n4. Comparisons missing with Zhang et al., 2024 and Zhao et al., 2025 for DI (both performance and efficiency) to support your claims against these prior works. Also experiments lack the use of more recent MIAs.\n\n5. Scope / external validity. Results rely on Pythia/Pile and OLMo/Dolma. Where do NIDs not exist? Provide a coverage analysis and a failure mode.\n\n6. Over-reach beyond LLMs. You mention DI for Diffusion and Image Autoregressive Models \"Beyond LLMs, DI has also been successfully applied to other types of generative models, including Diffusion Models (Dubinski et al., 2025) and ´ Image Autoregressive Models (Kowalczuk et al., 2025), widening the potential of the method.\" but don’t evaluate them. Either add experiments or tone down claims.\n\n7. Lack significant technical contribution wrt to the closest prior work. As you report \"Zhang et al. (2024a) propose to inject random and meaningless canaries into the data and then test how the LLM ranks the selected canary among all alternatives.\"\nRelative to Zhang et al. (injected random strings), your technical contribution is switching to NIDs that are naturally included in LLMs’ training sets. I would note this earlier in the paper, e.g., in the introduction too.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hdWdmo86dK", "reviewer": "Reviewer_TZKy", "summary": "This work introduces using natural identifiers as a novel way to audit data privacy in large language models. Natural identifiers are structured random strings such as the output of hash algorithms, shortened URLs, and crypto addresses, which are (i) naturally included in datasets such as Pile and Dolma and (ii) easy to generate held-out data from the same distribution. The authors demonstrates the effectiveness of this idea thru post-hoc DP audinting without training and practical dataset inference.", "questions": "See Weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea is clear and well-motivated, smartly tackling the key problem of how to find held-out data from the same distribution.\n2. The authors provide extensive empirical experiments, including ε estimation and dataset inference, to demonstrate the effectiveness of using natural identifiers in real-world scenarios.", "weaknesses": "1. The limitation of natural identifiers is obvious: Will this kind of data continually exist in pretraining data? In other words, if one model developer does not want their models to be audited, it is fairly easy for them to remove the natural identifier without sacrificing the model quality.\n2. For dataset inference, it requires the audited dataset to contain natural identifiers, which could be hard constraint. For example, if someone want to test whether GSM8K is contained in training, it seems hard to use natural identifiers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z76H3cxqwo", "reviewer": "Reviewer_uy2q", "summary": "The paper introduces natural identifiers (NIDs), ie random-looking strings common on the web (such as hashes, short URLs, eth addresses) as a scalable basis for post-hoc privacy auditing and dataset inference in LLMs. As NIDs have known generation rules, the authors mint matched generated identifiers (GIDs) to serve as iid controls, replacing bespoke canaries. This enables a single-run DP audit (picked up from the literature) that ranks NIDs vs. GIDs to yield tighter lower bounds with fewer samples, and a dataset-inference test that flags whether a suspect corpus was in training using only that corpus plus GIDs. Experiments on Pythia/OLMo and standard datasets show accurate hits on true training subsets and no false positives on held-out data. This makes NIDs a practical, general auditing tool.", "questions": "1. How robust is the approach to trivial preprocessing that filters or normalizes NIDs? Today's training pipelines often apply regex-based scrubbing and URL canonicalization; because your extraction relies on highly rigid patterns (e.g., [a-fA-F0-9]{32,128}, 0x[a-fA-F0-9]{40}), a curator could remove or mask these in one pass. Please quantify the drop in NID counts and DI/DP-audit power after simulating common cleaning steps. A table like the distribution-of-NIDs summary, but \"before vs. after\" realistic filters, would show whether the method degrades to impracticality with minimal countermeasures.\n\n2. Are GIDs sampled from the exact same effective distribution as the observed NIDs, not just the generator's support? Many NIDs in the wild reflect non-uniformities (e.g., address casing biases, popular shorteners, repository-specific hash exposure).\n\n3. Is it possible to analyze failure modes where small generator inaccuracies leak membership signal? For example, Ethereum checksums, preferred hash casing patterns, or URL-shortener path semantics might let the model distinguish NIDs from your GIDs.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper repurposes naturally occurring structured random strings as audit beacons and then samples from their known generators to create IID controls; this is a simple but fresh reframing that removes the retraining crutch many prior audits depend on, and I found it genuinely interesting and surprising; the ranking-based adaptation of one-run DP auditing further broadens that idea beyond top-1 decisions and tightens the link to theory.\n\nThe work further formalizes NIDs/GIDs and their sampling assumptions, connects the audit to an epsilon-DP theorem, and then evaluates on models with known training data (Pythia, OLMo) where ground truth is verifiable, reporting consistent DI behavior with no false positives on held-out subsets and showing how cardinality affects statistical power.\n\nIn terms of clarity, the exposition is well structured: the paper motivates why IID held-out data is the bottleneck, illustrates NIDs with concrete examples (e.g hashes, shortened URLs, crypto addresses), and uses clean figures and notation to map the end-to-end pipeline from NID extraction to GID generation to ranked auditing. \n\nOverall I believe the paper's significance is credible, because NIDs are abundant across standard pretraining corpora, making the method deployable in practice and potentially valuable for post-hoc audits or discovery in contentious settings.", "weaknesses": "In my view, the paper's main issue is that it depends on artifacts that are trivially removable at ingest: hashes, wallet addresses, shortened URLs, and similar strings are easy for a data curator to strip, normalize, or mask with a one-line regex during scraping or deduplication. Given that the method's leverage comes from these rigid formats and abundance, a mild shift in preprocessing policy could sharply reduce coverage, making the technique short-lived in practice. The authors show that many current corpora contain thousands of such identifiers (especially code-heavy subsets like GitHub/StackExchange and broad crawls like RefinedWeb) but those same tables also reveal how uneven the distribution is across domains, foreshadowing fragility under even modest curation pressure. A responsible next step would be to measure how counts and audit power change under realistic filtering pipelines (newline/HTML stripping, de-tokenization, heuristic hash removal, URL canonicalization), and to report DI and epsilon lower bounds before/after such defenses on the same models and suspect sets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aVFUnDr3rc", "reviewer": "Reviewer_aZSB", "summary": "This paper introduces Natural Identifiers (NIDs) as a novel mechanism to enable post-hoc privacy and data auditing in large language models (LLMs) without retraining or requiring held-out datasets. The authors define NIDs as structured random strings (e.g., cryptographic hashes, shortened URLs, Ethereum addresses) naturally present in public datasets such as GitHub and StackExchange.\nThe paper demonstrates that these identifiers can act as natural canaries allowing differential privacy (DP) audits and dataset inference (DI) to be performed post training. It adapts the one run DP auditing framework (Steinke et al., 2023) to work with NIDs and introduces a ranking-based inference procedure that computes tighter DP lower bounds. Extensive experiments on Pythia and OLMo models show that NIDs yield reliable post-hoc DP auditing and DI with no retraining and zero false positives, advancing practical LLM privacy auditing.", "questions": "1. How sensitive is DI performance to the number and diversity of NIDs in the suspect dataset?\n2. How does the ranking-based ε-bound compare empirically with the two-alternative case when the same number of samples is used?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Uses real-world random structures (NIDs) as reusable canaries a clever, previously unexplored idea.\n2. Adapts Steinke et al. (2023) into a ranking based auditing theorem (Theorem 1) with rigorous bounds.\n3.  Evaluations across models (Pythia, OLMo) and datasets (Pile, Dolma) confirm the scalability and reliability of the method.\n4. Eliminates retraining and manual canary insertion, reducing the computational barrier for auditing large LLMs.\n5. Directly addresses real world auditing needs in LLM regulation and compliance contexts.", "weaknesses": "1. The method assumes datasets contain sufficient NIDs; domains lacking structured identifiers (e.g., medical text) may not benefit.\n2.  While appendices are comprehensive, code availability is not stated; releasing tooling for NID extraction would improve accessibility.\n4.  Results for smaller ε or limited NIDs could use confidence intervals across more random seeds.\n5. A short discussion of potential misuse (e.g., adversarial data reconstruction) would strengthen the ethics section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)