Beyond Indistinguishability: Measuring Extraction Risk in LLM APIs
Ruixuan Liu, David Evans, Li Xiong
Abstract
Indistinguishability properties such as differential privacy bounds or low empirically measured membership inference are widely treated as proxies to show a model is sufficiently protected against broader memorization risks. However, we show that indistinguishability properties are neither sufficient nor necessary for preventing data extraction in LLM APIs. We formalize a privacy-game separation between extraction and indistinguishability-based privacy, showing that indistinguishability and inextractability are incomparable: upper-bounding distinguishability does not upper-bound extractability. To address this gap, we introduce -inextractability as a definition that requires at least expected queries for any black-box adversary to induce the LLM API to emit a protected -gram substring. We instantiate this via a worst-case extraction game and derive a rank-based extraction risk upper bound for targeted exact extraction, as well as extensions to cover untargeted and approximate extraction. The resulting estimator captures the extraction risk over multiple attack trials and prefix adaptations. We show that it can provide a tight and efficient estimation for standard greedy extraction and an upper bound on the probabilistic extraction risk given any decoding configuration. We empirically evaluate extractability across different models, clarifying its connection to distinguishability, demonstrating its advantage over existing extraction risk estimators, and providing actionable mitigation guidelines across model training, API access, and decoding configurations in LLM API deployment. Our code is publicly available at: https://github.com/Emory-AIMS/Inextractability.
AI Impact Assessments
(3 models)Scientific Impact Assessment: "Beyond Indistinguishability: Measuring Extraction Risk in LLM APIs"
1. Core Contribution
This paper makes a fundamental conceptual contribution by formally separating data extraction risk from indistinguishability-based privacy notions (differential privacy, membership inference, reconstruction, attribute inference). The authors prove that the standard privacy reducibility chain (DPD ⪯ RC ⪯ MI ≈ AI) does not extend to data extraction (DE), meaning that bounding distinguishability does not bound extractability, and vice versa (Theorems 2 and 3). This is significant because the ML privacy community has widely assumed—often implicitly—that DP guarantees or low MIA signals provide adequate protection against training data extraction.
To fill this gap, the authors introduce *(l, b)-inextractability*, a definition requiring at least 2^b expected queries for any black-box adversary to extract a protected l-gram from an LLM API. They derive a rank-based extraction risk upper bound (Theorem 4) that is independent of decoding configuration and propose efficient estimation algorithms (Algorithms 2 and 3). The framework extends to untargeted extraction (Theorem 5) and approximate matching (via a local log-Lipschitz regularity assumption).
2. Methodological Rigor
Theoretical foundations. The separation theorems (2 and 3) are clean and well-constructed. The proof of Theorem 2 identifies precise conditions (p₀ > (e^ε - 1)/(3e^ε - 1)) under which DP resilience fails to imply extraction resilience—this is not merely an existence argument but provides interpretable thresholds. The connection to min-entropy (Lemma 2) is elegant and grounds the definition in information-theoretic security.
The rank-based upper bound (Theorem 4) is derived by considering the worst-case adversary who optimally selects truncation size k and temperature T per token position. The proof is sound: setting k = r_t and T → 0 yields the 1/r_t bound per position, and the product across positions gives the overall bound. The teacher-forcing assumption is acknowledged and appropriate for worst-case analysis.
Empirical validation. The experiments are well-designed and use standard benchmarks (GPT-2/Enron, LLaMA-3.1-8B/Pile/BookSum). Figure 2 provides compelling visual evidence of the separation, showing samples with high extractability but low distinguishability (and vice versa). The comparison of MIA signals (calibrated vs. uncalibrated) in Figure 3 and Figure 8 offers a nuanced explanation of why prior work has found seemingly contradictory results about MIA-extraction correlation.
Potential concerns. The teacher-forcing assumption in the rank estimation means the bound may not be tight for autoregressive generation where errors propagate. The paper acknowledges this but doesn't quantify the gap rigorously. The log-Lipschitz regularity assumption (Assumption 1) for approximate extraction is empirically validated but may not hold uniformly across all text domains. The experiments are limited to models up to 8B parameters.
3. Potential Impact
Immediate practical impact. The paper provides actionable tools for LLM API providers: Algorithm 2 enables efficient extraction risk auditing via a single teacher-forced forward pass, and the framework produces concrete b-values that map to query costs (and thus dollar costs). The defense evaluation (Section 5, Figure 14) demonstrates that combining instruction-tuning, preference optimization, and API access control can reduce extractable portions from ~20% to 0.03%.
Policy and governance. The (l, b)-inextractability definition could serve as a compliance metric for regulations requiring demonstration of privacy protection. The cost-based framing (2^b queries) translates naturally into economic feasibility assessments.
Research impact. This work challenges a widespread assumption in the privacy-ML community and could redirect research effort toward extraction-specific defenses rather than relying solely on DP training. The observation that calibrated MIA signals decorrelate from extraction risk while uncalibrated signals correlate (because they proxy for absolute posterior confidence) is an important insight that clarifies confusion in the literature.
4. Timeliness & Relevance
This paper is highly timely. LLM APIs are the dominant deployment paradigm, and extraction risks (copyright, PII leakage, contextual integrity) are at the center of ongoing legal and regulatory debates. The gap between DP guarantees and practical extraction risk has been empirically noted but not formally characterized. The paper fills this need precisely when the community requires principled extraction risk metrics for auditing production systems.
5. Strengths & Limitations
Key strengths:
Notable limitations:
Overall assessment. This is a strong theoretical and empirical contribution that identifies and formalizes a genuine gap in the privacy-ML landscape. The separation results are clean and the practical implications are substantial. The work is likely to influence how extraction risk is measured and reported in both academic and industrial settings.
Generated Apr 22, 2026
Comparison History (79)
Paper 1 addresses a foundational conceptual gap by formally separating indistinguishability from extractability, challenging a widely-held assumption in privacy research (differential privacy as memorization proxy). This theoretical contribution has broad implications across the entire privacy-preserving ML field and provides a new rigorous definition with practical estimators. Paper 2 presents a valuable, well-engineered auditing tool for a timely problem (model substitution in gateways), but its impact is more application-specific and incremental. Paper 1's reframing of privacy definitions offers deeper, more durable theoretical influence across fields.
Paper 1 offers higher scientific impact by challenging a fundamental theoretical assumption: that indistinguishability implies protection against data extraction. By formalizing the mathematical separation between the two and introducing a novel (l, b)-inextractability framework, it establishes a new foundational metric for LLM privacy. While Paper 2 addresses the critical issue of jailbreaking with an impressive evolutionary framework, its empirical attack-defense loop is likely to be superseded in the fast-paced safety arms race. Paper 1's theoretical contributions will have a more enduring influence on how privacy and memorization are mathematically evaluated across the field.
Paper 1 introduces a foundational formal separation between indistinguishability-style privacy guarantees and extraction, plus a new inextractability definition and practical, decoding-aware risk estimator with mitigation guidance. This is methodologically rigorous, highly timely for real-world LLM API deployment, and broadly impactful across ML privacy, security, and governance. Paper 2 is timely and exciting, but is primarily a benchmark with early empirical findings; its broader scientific impact depends on adoption and on validating “novel” attacks, and it is more domain-specific to cryptography.
Paper 2 addresses a critical, highly timely issue in the dominant field of LLMs: data extraction. By formally proving that traditional differential privacy (indistinguishability) is insufficient for preventing extraction and proposing a novel framework, it offers a paradigm shift in AI safety and privacy evaluation. While Paper 1 presents an elegant hardware-software co-design for RRAM edge AI, Paper 2 has broader, more immediate real-world applications for LLM deployments, fundamentally influencing a much wider cross-section of current AI research, policy, and commercial practices.
Paper 2 offers a foundational theoretical contribution by proving that indistinguishability properties (like differential privacy) do not guarantee protection against data extraction in LLMs. By challenging a core assumption in ML privacy and introducing a novel, rigorous mathematical framework for inextractability, it will likely catalyze widespread follow-up research. While Paper 1 provides an innovative and timely systems-security solution for agentic workflows, Paper 2's methodological rigor and paradigm-shifting implications for copyright and privacy across the broader AI field give it higher potential for fundamental scientific impact.
Paper 2 has higher likely scientific impact due to a clear conceptual advance: it formalizes a separation between indistinguishability-based privacy and extraction, introduces a new, query-complexity–style definition ((l,b)-inextractability), and provides estimators/bounds with broad applicability to LLM API deployment and privacy evaluation. This offers a reusable theoretical framework and practical measurement methodology across many models and settings. Paper 1 is timely and important for AI-for-science integrity, but is more scenario-specific and mitigation-driven, with narrower generalization beyond agentic data pipelines.
Paper 2 likely has higher scientific impact due to its broad, timely relevance to LLM privacy and deployment. It introduces a new formal notion ((l,b)-inextractability), proves separations from indistinguishability, and provides practical estimators and mitigation guidance applicable across many models and API settings—impacting ML, privacy, security, and policy. Paper 1 is highly novel and rigorous in systems security with serious real-world implications, but its scope is narrower (specific GPU architectures/rowhammer conditions) and may affect a smaller set of researchers/practitioners than LLM API extraction risk.
Paper 2 addresses a fundamental gap in privacy/security theory for LLMs by formalizing the separation between indistinguishability and extractability—two concepts widely conflated in practice. Its theoretical contributions (new privacy definitions, formal game-based separations, rank-based estimators) are broadly applicable across the LLM deployment ecosystem and challenge prevailing assumptions about differential privacy's sufficiency. Paper 1 (VIGIL) is a solid engineering contribution for runtime policy enforcement in agentic systems, but is more narrowly scoped. Paper 2's theoretical foundations and practical implications for LLM API safety give it broader and more lasting impact across privacy, security, and ML communities.
Paper 2 addresses a critical and timely problem at the intersection of privacy and LLM deployment, which is of enormous current relevance. It provides a novel theoretical framework (the separation between indistinguishability and inextractability) that challenges a widespread assumption in the field, offers practical definitions and estimators, and provides actionable mitigation guidelines. Its breadth of impact spans privacy, security, ML, and policy. Paper 1, while technically strong in blockchain throughput optimization, addresses a more mature and narrower domain with comparatively less cross-disciplinary impact potential.
FloatDoor introduces an entirely novel attack surface—platform-triggered backdoors exploiting floating-point non-determinism—that is fundamentally new to the security community. This class of attack has broad implications for LLM supply chain trust, model auditing, and deployment security across diverse hardware. Its novelty is high because no prior work has demonstrated input-independent, platform-dependent backdoors. Paper 2 makes solid theoretical contributions formalizing extraction vs. indistinguishability, but operates within a more established research direction (memorization/privacy in LLMs). FloatDoor's surprising and practical threat model is likely to generate more follow-up research and industry response.