Conformal Privacy Auditing: Calibrated Re-identification Attacks with Statistical Guarantees¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: Safety
Keywords: Privacy Auditing, Conformal Prediction, Re-identification Attack, LLM Safety, Finite-Sample Guarantees
TL;DR¶
This paper introduces Conformal Privacy Auditing (CPA), a distribution-free black-box calibration framework that wraps LLM-empowered and retrieval-based re-identification attacks into finite-sample conformal ambiguity sets, guaranteeing that the true identity is covered with a user-chosen confidence level \(1-\alpha\) while yielding an interpretable, calibrated privacy risk metric for document release.
Background & Motivation¶
Releasing sensitive natural language dataโsuch as clinical case summaries, judicial court decisions, and online forum disclosuresโis critical for research and software development, but data custodians must ensure that individuals cannot be linked to released records. Common industry practice relies on sanitization and redaction, replacing named entities with symbolic tokens or placeholders. However, combinations of seemingly innocuous quasi-identifiers (such as age, gender, medical specialty, and geographic location) frequently survive redaction and collectively form distinctive linkage signals. The advent of large language models (LLMs) with advanced reasoning and knowledge integration capabilities has further amplified this vulnerability, turning LLMs into potent privacy adversaries capable of inferring implicit attributes and linking sanitized records to candidate profiles in external auxiliary databases.
Existing paradigms for auditing and mitigating release-time privacy risks suffer from an acute disconnect between theory and practice. Differential Privacy (DP) offers formal worst-case mathematical bounds by injecting calibrated noise during training or fine-tuning; however, its guarantees are often overly conservative, drastically degrading generation utility, while failing to provide actionable release-time decisions for individual natural language texts. Conversely, empirical privacy auditing assesses vulnerability through attack-based metrics such as Top-1 re-identification accuracy; while practically informative, empirical success rates lack finite-sample statistical guarantees, leaving practitioners uncertain whether measured risks generalize to unseen distributions, richer registries, or stronger models.
To bridge this gap between uncalibrated empirical attacks and conservative worst-case mechanisms, this paper introduces distribution-free conformal prediction to release-time privacy assessment. Core idea: formulate document re-identification auditing as constructing conformal ambiguity sets under a declared attacker threat model, delivering finite-sample marginal coverage certificates \(\ge 1-\alpha\) over candidate identities and leveraging certified set sizes as an interpretable dial for release and redaction decisions.
Method¶
Overall Architecture¶
CPA operates as a model-agnostic auditing layer that wraps arbitrary black-box attack pipelines without internal model access. An audit instance is evaluated relative to a declared threat configuration specifying candidate-pool construction, attacker auxiliary knowledge (e.g., metadata-only vs. enriched profile registries), query formulation, and sampling interfaces. The auditing pipeline proceeds in two principal phases: in the calibration phase, nonconformity scores based on adaptive prediction set (APS) cumulative mass are computed for true identities across a held-out calibration set to establish an order-statistic cutoff \(\hat{q}_\alpha\); in the test phase, the auditor evaluates candidate profiles for a newly released document, collects all candidates whose nonconformity score falls below \(\hat{q}_\alpha\) into a certified conformal ambiguity set \(C_\alpha(x, w)\), and derives an inverse ambiguity proxy for risk gating.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Released Document x + Candidate Pool U<br/>Declared Threat Configuration W"] --> B["Black-Box Attacker Interface<br/>Logit Probability or Sampling Estimation"]
B --> C["APS Cumulative Mass Scoring<br/>Accumulated Mass to True Identity"]
C --> D["Split Conformal Calibration<br/>Order Statistic Threshold q_alpha"]
D --> E["Conformal Ambiguity Set Synthesis<br/>Candidate Subset with Coverage 1-alpha"]
E --> F["Release Gating & Risk Proxy<br/>Certified Cardinality & L(x,w) Metric"]
Key Designs¶
1. Black-Box Attacker Interface: Unified Adaptation for Logit and Sampling-Only Access
Real-world adversaries vary widely in technical capability, ranging from open-source local models to proprietary commercial APIs lacking probability access. CPA models the attacker as an induced candidate distribution \(p_A(\cdot \mid x, w) \in \Delta(Y(x, w))\). When log-probabilities or normalized retrieval similarities are accessible, CPA normalizes them directly into candidate pseudo-posteriors. When auditing black-box commercial APIs without logit exposure, CPA introduces a sampling-only interface: querying the model \(m\) times under forced-choice decoding over the candidate pool \(Y(x, w)\) to construct empirical frequencies: $\(\hat{p}_m(y \mid x, w) = \frac{1}{m} \sum_{j=1}^m \mathbf{1}\{\tilde{Y}^{(j)} = y\}\)$ The authors establish that under independent per-query sampling randomness, the resulting empirical nonconformity scores preserve sequence exchangeability, ensuring that proprietary closed-source LLMs can be certified with the same finite-sample statistical validity as open-source models.
2. APS Cumulative Mass Scoring: Adaptive Nonconformity for Identity Linkage
Fixed-cutoff or raw Top-\(k\) reporting fails to account for heterogeneous document linkage difficulty. CPA adapts the Adaptive Prediction Sets (APS) mass formulation restricted to candidate pool \(Y(x, w)\). Letting \(\pi_1, \pi_2, \dots\) denote candidates sorted in descending order of attacker probability \(p_A(\cdot \mid x, w)\), the nonconformity score of identity \(y\) is defined as: $\(s(x, y; w) := \sum_{j: p_A(\pi_j \mid x, w) \ge p_A(y \mid x, w)} p_A(\pi_j \mid x, w)\)$ This score maps to \((0, 1]\). When an attacker concentrates probability mass sharply on the correct individual, the accumulated mass remains small (low nonconformity, indicating high re-identification risk); when the attacker is diffuse or ranks the true identity low, the required mass approaches 1. This property allows the resulting prediction set to adapt dynamically: shrinking to small subsets on vulnerable documents while expanding gracefully on ambiguous cases.
3. Split Conformal Calibration and Finite-Sample Guarantees: From Ranking to Certified Ambiguity
Given an exchangeable calibration split of \(n\) documents under threat configuration \(w\), CPA computes scalar nonconformity scores for ground-truth identities and identifies the split conformal threshold via the empirical quantile: $\(k := \lceil (n + 1)(1 - \alpha) \rceil, \quad \hat{q}_\alpha := T_{(k)}\)$ For an incoming document, the certified ambiguity set is constructed as \(C_\alpha(x, w) = \{y \in Y(x, w) : s(x, y; w) \le \hat{q}_\alpha\}\). By exchangeability of calibration and evaluation scores, CPA guarantees exact finite-sample marginal validity: \(\Pr(Y_{n+1} \in C_\alpha(X_{n+1}, w)) \ge 1 - \alpha\). To accommodate open-world settings or computational Top-\(K\) retrieval truncations where the true candidate may be missing with probability \(\rho(w)\), the paper proves an open-world validity lower bound: $\(\Pr(Y \in C_\alpha(X, w)) \ge (1 - \rho(w))(1 - \alpha) \ge 1 - (\rho(w) + \alpha)\)$ The auditor can summarize certified risk via the inverse ambiguity proxy \(L(x, w) := 1 / \max\{1, |C_\alpha(x, w)|\}\), operationalizing concrete regulatory release thresholds (e.g., withholding records where median \(|C_\alpha| < k\)).
Key Experimental Results¶
Main Results¶
CPA was evaluated across four diverse benchmarks: TAB judicial cases (1,268 records), WikiBio structured biographies (1,000 identities), TextWash anonymized bios (1,202 pairs), and the Blog Authorship corpus (19,320 authors). Main evaluations at miscoverage level \(\alpha = 0.05\) (target coverage \(\ge 0.95\)) demonstrate how certified identifiability shifts across side-information levels (K1 metadata-only, K2 keywords, K3 case text):
| Dataset & Attacker Setting | Top-1 Accuracy | Empirical Coverage (Cov.) | Median Set Size (Med. |C|) | Mean Set Size (Mean |C|) | Mean Leakage Proxy (Mean 1/|C|) |
|---|---|---|---|---|---|
| TAB-Direct | |||||
| K1 meta / direct query | 0.052 | 0.929 | 1268 | 1179.5 | 9.57e-04 |
| K2 keywords / direct query | 0.973 | 0.973 | 1 | 1.0 | 1.0000 |
| K3 case-text / direct query | 0.994 | 0.994 | 1 | 1.0 | 1.0000 |
| K2 keywords / LLM-clues | 0.715 | 0.970 | 20 | 20.1 | 0.0499 |
| TAB-Direct (Quasi-ID Release) | |||||
| K1 meta / direct query | 0.003 | 0.932 | 1268 | 1173.6 | 0.0017 |
| K2 keywords / direct query | 0.872 | 0.953 | 4 | 3.7 | 0.2717 |
| K3 case-text / direct query | 0.964 | 0.964 | 1 | 1.0 | 1.0000 |
| K2 keywords / LLM-clues | 0.615 | 0.945 | 27 | 27.1 | 0.0369 |
| WikiBio (1k candidates, \(\alpha=0.05\)) | |||||
| Direct query | 0.362 | 0.956 | 264 | 254.98 | 0.00466 |
| LLM clues (Llama-3.1-8B) | 0.420 | 0.950 | 189 | 186.87 | 0.00562 |
| LLM clues (Qwen3-8B) | 0.380 | 0.958 | 265 | 255.69 | 0.00465 |
Ablation Study¶
The framework was stress-tested across multiple dimensions, including alternative nonconformity score constructors, candidate-pool truncation, and calibration distribution drift:
| Configuration / Stress Test | Key Metrics | Empirical Observation & Notes |
|---|---|---|
| Score Constructor Ablation (WikiBio+Llama, \(\alpha=0.05\)) | ||
| APS mass score (default) | Cov = 0.950, Med |C| = 189 | Achieves target coverage with adaptive, efficient set sizes |
| Rank-based score | Cov = 0.950, Med |C| = 179 | Valid coverage; enables auditing purely ranked black-box outputs |
| Raw probability score | Cov = 0.960, Med |C| = 212 | Marginally more conservative; larger certified sets |
| Top-K Truncation & Open-World Miss (TextWash Fiction, direct) | ||
| Truncation \(K=50\) | Miss=0.160, Cond. Cov=1.000 | Unconditional coverage drops to 0.840, matching \((1-\rho)(1-\alpha)\) |
| Truncation \(K=100\) | Miss=0.080, Cond. Cov=1.000 | Unconditional coverage recovers to 0.920 |
| Truncation \(K=200\) | Miss=0.000, Cond. Cov=0.970 | Zero candidate miss; unconditional coverage reaches 0.970 |
| Exchangeability Drift Stress Tests (Cross-Configuration Audit) | ||
| TAB direct cal. \(\to\) direct test | Coverage = 0.965 | Matched configurations meet nominal \(1-\alpha=0.95\) |
| TAB direct cal. \(\to\) quasi-ID test | Coverage = 0.923 | Release-mechanism drift causes under-coverage |
| Blog W10 cal. \(\to\) W10 test | Coverage = 0.940 | Matched side-information preserves valid statistical bounds |
| Blog W10 cal. \(\to\) W1 test | Coverage = 0.835 | Attacker capability mismatch violates exchangeability |
Key Findings¶
- Privacy risk is a joint property of text and auxiliary side information: On TAB, changing attacker registry knowledge from K1 metadata to K2 keywords or K3 case text collapses median ambiguity sets from 1268 down to 1, illustrating that safe-looking redactions can become completely compromised once auxiliary knowledge expands.
- LLM clue augmentation exhibits category-dependent gains: Augmenting queries with LLM-extracted clues significantly tightens ambiguity sets on famous individuals with abundant external web context (TextWash famous median \(|C_\alpha|\) shrinks from 120 to 90), but yields negligible change on fictional or semi-famous entities where external world knowledge is absent.
- Conformal parameter \(\alpha\) serves as an operational risk dial: Tightening the target guarantee (decreasing \(\alpha\) from 0.1 to 0.01) broadens certified ambiguity sets; when attack accuracy is extremely high, ambiguity sets compress to singletons, causing conformal coverage to smoothly converge toward empirical Top-1 accuracy.
Highlights & Insights¶
- Pioneering conformal prediction for privacy auditing: Transcends the dichotomy between uncalibrated empirical attack accuracy and overly conservative training-time differential privacy, providing finite-sample statistical certificates for document-level release.
- Actionable operationalization for data release guidelines: Certified ambiguity set size \(|C_\alpha(x)|\) directly mirrors regulatory concepts of \(k\)-anonymity cohorts, providing compliance officers with a mathematically principled threshold criterion to withhold or further redact individual records.
- Theoretically sound open-world degradation bounds: Rigorously models candidate-pool misses and retrieval truncations, demonstrating both theoretically and empirically that coverage degrades multiplicatively as \((1-\rho(w))(1-\alpha)\).
Limitations & Future Work¶
- Reliance on declared threat models and exchangeability: CPA certificates are valid specifically relative to a declared candidate pool, attack pipeline, and exchangeable calibration distribution; they do not provide universal immunity against unanticipated, unmodeled future adversaries.
- Computational overhead of large candidate pools: Scoring massive candidate reference populations can be resource-intensive, while Top-\(K\) retrieval filtering introduces candidate-miss errors that bound unconditional coverage.
- Future directions: Extending conformal risk-control guarantees to membership inference attacks (MIA) and designing robust calibration under non-exchangeable distribution shifts represent promising paths forward.
Related Work & Insights¶
- vs Differential Privacy (DP): DP establishes mechanism-level worst-case stability via randomized noise addition during training, often severely degrading text utility and offering no per-document release certificates; CPA audits task-level re-identification risk on arbitrary black-box attackers with finite-sample coverage guarantees.
- vs Empirical Privacy Auditing: Traditional auditing reports point metrics like Top-1 accuracy or attack success rate without finite-sample guarantees; CPA converts empirical attack scores into statistically calibrated prediction sets.
- vs Statistical Disclosure Control (SDC): Classical SDC methods (such as \(k\)-anonymity) rely on structured microdata and parametric frequency assumptions; CPA extends cohort-ambiguity reasoning to unstructured natural language text facing LLM and retrieval adversaries.
Rating¶
- Novelty: โญโญโญโญโญ Pioneering application of conformal prediction to LLM-era text re-identification auditing, bridging empirical security and statistical guarantees.
- Experimental Thoroughness: โญโญโญโญโญ Comprehensive evaluation across 4 benchmark datasets, multiple model architectures (Llama-3.1, Qwen3, GPT-5), and rigorous drift and truncation stress tests.
- Writing Quality: โญโญโญโญโญ Exceptionally structured, mathematically rigorous, and clearly contextualized within both security and statistical disclosure literature.
- Value: โญโญโญโญโญ Delivers an interpretable, operationalized certificate framework directly applicable to real-world data release compliance.