acceptodds
Under review as a conference paper at ICLR 2027

Is Preventing Model Distillation Possible? A Theoretical Perspective

19 views

Abstract

Proprietary AI models are publicly accessible via an API. Third parties can use this limited black-box access to help develop their own AI models by extracting training data. This practice is known as distillation and measures to prevent it are known as anti-distillation. We study this problem from a theoretical perspective and ask is it possible to provably prevent distillation of the entire model? We formalize this problem in the language of learning theory. We show that the feasibility of anti-distillation depends critically on the computational hardness of the underlying agnostic PAC learning problem and on the statefulness of the server. For some model classes and query distributions, provable defenses exist; for others, undetectable attacks exist.

Primary area:
learning theory
Keywords:
Distillation, Model Stealing, Hardness

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_Bs1QOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The authors consider an attacker aiming to reverse engineer a model via query-level access to it from a theoretical perspective. They connect stateful and stateless defenders to prior learning theory concepts (namely PAC and its adjacent concepts). In addition to a variety of formal results, they present a positive and negative example which provide further intuition.

In total, the paper serves to develop the foundation of adversarial learning theory.

Critical strengths

The paper leans on existing learning theory and makes ties to already well-established theoretical frameworks.

The authors provide a thorough and clear treatment of various quantifier orderings.

The result of section 4 ("anti-distillation defenses must exploit the fact that the attacker is computationally bounded") is profound. It reminds me of the work out there (that doesn't often get used in adversarial learning) where you consider a polynomial-time bounded attacker. I could see the theoretical foundations laid by this work leading to a rich set of works further diving into how one can exploit an attacker's computational limitations.

Critical weaknesses

Unless I missed something, all results are for a finite model class. The term |H| shows up in the bounds, but for practical models (the authors use the example of LLMs under 1TB in size), that's very big (2^2^40). Even sqrt(log(|H|)) is still extremely large, making me question the vacuousness of the bounds.

Separately: Oh how I would benefit from a notation table.

Questions for authors
  1. Can you plug in some numbers? Namely, for the example you provide (LLMs less than 1TB in size), for particular loss functions (e.g., TV as you suggest) and reasonable numbers of queries, what do the bounds actually state?

  2. I'm struggling with Theorem 4.1: Let H be the set of all linear classifiers using 2^40 bits of precision. Being \gamma-insecure (with the gamma value you state) means there exists an h such that the risk is greater than 2(alpha + 2^40/sqrt(n))? (What) am I doing wrong?

  3. Do any of your results apply to infinite hypothesis classes (say, with finite VC dimension)?

2 comments

Thank you for your positive review and constructive feedback. We answer your questions and respond to the weaknesses below.

1. Vacuousness of the ∣H∣|\mathcal{H}| Bound & Plugging in Numbers (Weakness 1 & Questions 1–2)

"The term |H| shows up in the bounds, but for practical models (... LLMs under 1TB in size), that's very big (2^2^40). Even sqrt(log(|H|)) is still extremely large, making me question the vacuousness of the bounds."

"1. Can you plug in some numbers? Namely, for the example you provide (LLMs less than 1TB in size), for particular loss functions (e.g., TV as you suggest) and reasonable numbers of queries, what do the bounds actually state?"

Plugging in numbers. Consider a 1TB model, i.e. ∣H∣=2243|\mathcal{H}| = 2^{2^{43}}. Under TV loss, Theorem 4.1 gives Risk≤2α+21nln⁡∣H∣.\mathrm{Risk} \le 2\alpha + 2\sqrt{\tfrac{1}{n}\ln|\mathcal{H}|}. This bound is non-trivial once n≳2.4×1013n \gtrsim 2.4 \times 10^{13}, and the additive error drops to 0.10.1 at n≈2.4×1015n \approx 2.4 \times 10^{15}.

Counting each generated token as one query, OpenRouter alone produced roughly 5×10135 \times 10^{13} output tokens in October 2026 (7.9×10147.9 \times 10^{14} total, about 6% of which are output). So the threshold n≈2.4×1013n \approx 2.4 \times 10^{13} is a few weeks of one router's output. So even this worst-case bound, which ignores all structure in the model, becomes meaningful at deployment scale.

In general, the log⁡∣H∣\log|\mathcal{H}| dependence cannot be improved: identifying the model requires log⁡2∣H∣\log_2|\mathcal{H}| bits, and each query reveals only O(1)O(1) bits. Real models have far more structure than an arbitrary BB-bit function -- we are not making any assumptions about the model architecture, precision, etc. -- so in practice distillation needs far fewer queries. For classes of finite VC dimension, Remark C.4 already replaces ln⁡∣H∣\ln|\mathcal{H}| with dVCd_{\mathrm{VC}}. (See our response to the second question below.)

The point of this generic result is that there is no fundamental barrier to distillation. But the attack itself is not practical, since it runs in time polynomial in ∣H∣|\mathcal{H}|; this is why any real defense must rely on computational hardness.

2. Infinite Hypothesis Classes with Finite VC Dimension (Questions 2 & 3)

"3. Do any of your results apply to infinite hypothesis classes (say, with finite VC dimension)?"

Yes—Theorem 4.1 extends to infinite hypothesis classes with finite VC dimension. Specifically, for any infinite class of deterministic binary classifiers H⊆0,1X\mathcal{H} \subseteq \\{0,1\\}^{\mathcal{X}} with finite VC dimension dVC≥1d_{\mathrm{VC}} \ge 1, honest-query ERM achieves universal γ\gamma-distillation insecurity with an explicit bound γ=2α+2dVCln⁡(en/dVC)n\gamma = 2\alpha + \sqrt{\frac{2 d_{\mathrm{VC}} \ln(e n / d_{\mathrm{VC}})}{n}} for n≥dVCn \ge d_{\mathrm{VC}} or an asymptotic bound γ=2α+O(dVC/n)\gamma = 2\alpha + O(\sqrt{d_{\mathrm{VC}}/n}) even against stateful servers (added in Section 4 and Remark C.4).

If H\mathcal{H} is the class of linear classifiers in low dimension dd (over Rd\mathbb{R}^d), then even if each number uses 10001000 bits of precision (or infinite real precision), its VC dimension is dVC=d+1d_{\mathrm{VC}} = d + 1, so this bound gives a non-trivial guarantee independent of bit precision. For example, with d=100d = 100 (dVC=101d_{\mathrm{VC}} = 101), α=0.05\alpha = 0.05, and n=106n = 10^6 queries, the explicit bound above gives 2dVCln⁡(en/dVC)n≈0.045\sqrt{\frac{2 d_{\mathrm{VC}} \ln(e n / d_{\mathrm{VC}})}{n}} \approx 0.045, yielding Risk<0.15\mathrm{Risk} < 0.15.

3. Remark on the Direction of γ\gamma (Question 2)

"2. I'm struggling with Theorem 4.1: Let H be the set of all linear classifiers using 2^40 bits of precision. Being \gamma-insecure (with the gamma value you state) means there exists an h such that the risk is greater than 2(alpha + 2^40/sqrt(n))? (What) am I doing wrong?"

The theorem says all α\alpha-accurate servers are γ\gamma-insecure i.e. there exists a computationally unbounded attacker that can attack any accurate server and find a hh such that the risk is less than the stated bound. (Note that the log⁡∣H∣\log|\mathcal{H}| term is also inside the square root so it would be γ=2(α+220/n)\gamma=2(\alpha+2^{20}/\sqrt{n}).)

4. Notation Table (Weakness 2)

"... I would benefit from a notation table."

We have added a notation table (Table 3.1) in Section 3.

I thank the authors for their response and I maintain my positive assessment of the work.

Reviewer_GtXwOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper investigates whether active output perturbation can provably prevent model extraction via knowledge distillation in a setting of API-accessed models. The authors formalize interactive, noisy anti-distillation as a multi-round game called the Distillation Game between an API provider holding a secret model hh and honest query distribution D,D, and an adaptive adversary, who's trying to steal the latter. They establish formal definitions for alpha-accuracy on honest queries and various tiers of anti-distillation security organized across a strict quantifier hierarchy. The paper proves that memoryless distillation security is computationally equivalent to Gap PAC learning, constructs a provably secure fixed-server stateful defense using Learning Parity with Noise (LPN) and cryptographic hashing, and demonstrates an undetectable distillation attack under the Planted XOR assumption.

Critical strengths
  1. Rigorous Formalization of the Distillation Game: The paper introduces a multi-round game-theoretic framework with a clear taxonomy of quantifier hierarchies, distinguishing fixed-server vs. distribution-free, and worst-case vs. average-case security. Also this paper establishes a connection between anti-distillation and well-established primitives in learning theory (Gap PAC learning) and cryptographic assumptions (LPN, Planted XOR), thereby enabling these fields to be integrated within a single study.

  2. Constructive Positive and Negative Results: The authors provide a concrete positive example with stateful LPN caching for hashed parities, and a sophisticated negative example with undetectable Planted XOR attack on unhashed parities, highlighting the exact structural boundaries where defenses succeed (or fail).

Critical weaknesses
  1. Restrictive Scope to Boolean and Hashed Parity Concept Classes: Both the positive cryptographic example and the negative example are proven exclusively for Boolean parities and hashed parities over F2F_2. Modern frontier models are rich generative sequence models involving continuous token spaces, so it remains an open question how these cryptographic hardness barriers translate to neural network classes or autoregressive generation.

  2. Oversimplifyed Query Distributions: The analysis assumes specific uniform query distributions (D=U(0,1)d)D=\mathcal{U}(0,1)^d)). Real-world API adversaries query natural language distributions, which possess complex linguistic structure and are non-uniform.

Questions for authors

How can the core insights from hashed parities and LPN-based stateful caching be extended or adapted to continuous vector spaces or transformer-based sequence generation models? What are the practical storage, lookup, and memory overhead implications of maintaining a stateful query cache when scaled to massive sequence and prompt spaces in production APIs?

2 comments

Thank you for your positive review and constructive feedback. We respond to your points below.

1. Non-Uniform Query Distributions

"2. Oversimplifyed Query Distributions: The analysis assumes specific uniform query distributions (D=U(0,1)d)D = \mathcal{U}(0, 1)^d))..."

First, our general framework (Section 3), information-theoretic bound (Section 4), and memoryless PAC equivalence (Section 5) hold for general discrete domains X\mathcal{X} and distributions D\mathcal{D}.

Second, although Theorem 6.3 is stated for D=Uniform(0,1d)\mathcal{D} = \mathrm{Uniform}(\\{0,1\\}^d) to match Section 7, both the construction and proof extend directly to any domain X\mathcal{X} and non-uniform distribution D\mathcal{D} under the assumption that every input has negligible probability. We have added this extension at the end of Section 6 and in Remark E.3 (Appendix E).

However, the undetectable attack in Section 7 is specific to the uniform distribution. This requirement is inherited from the structured hardness assumption we use. It is quite plausible that this could be extended to other distributions, but then we would be "rolling our own" hardness assumption.

2. Stateful Cache Storage and Lookup Overhead

"What are the practical storage, lookup, and memory overhead implications of maintaining a stateful query cache when scaled to massive sequence and prompt spaces in production APIs?"

Explicitly storing past queries in a table T[x]T[x] would require memory and lookup overhead growing with nn. However, against computationally bounded adversaries, the server does not need to store past queries: it can record a single secret key kk (of length polynomial in dd, e.g., k∈0,1dk \in \\{0,1\\}^d) at initialization and generate the noise on query xx pseudorandomly from (k,x)(k, x) (via a pseudorandom function Fk(x)F_k(x) or a keyed hash). Repeated queries to xx then deterministically receive the same perturbed response without any table lookup, and the server's memory only needs to record kk—so it does not grow with nn.

3. Continuous Vector Spaces and Sequence Models

"1. Restrictive Scope to Boolean..."

"How can the core insights from hashed parities and LPN-based stateful caching be extended or adapted to continuous vector spaces or transformer-based sequence generation models?"

  • Autoregressive sequence generation: Suppose a sequence model generates output tokens y=(y1,y2,… )y = (y_1, y_2, \dots) one token at a time given a prompt xx, where at step tt the next token yty_t is predicted given xx and the prefix y<t=(y1,…,yt−1)y_{<t} = (y_1, \dots, y_{t-1}) of tokens generated so far. Following Point 2 above, the server can apply a pseudorandom function Fk(x,y<t)F_k(x, y_{<t}) to the prefix (x,y<t)(x, y_{<t}) to deterministically generate the perturbation at step tt. Repeating the same prompt xx then always produces the same perturbed sequence, preventing an attacker from averaging out "noise" via exact query repetition.
  • Challenges for obtaining provable security: Extending provable security beyond hashed parities to natural models over continuous vector spaces and language models faces a core structural obstacle. In Section 6, the cryptographic hash H(x)H(x) destroys all similarity between distinct inputs. By contrast, useful models over continuous spaces and natural language are smooth: nearby vectors x′≈xx' \approx x in Rd\mathbb{R}^d, or semantically similar prompts (e.g., paraphrases of xx), produce similar outputs. Because hashing treats any distinct input x′≠xx' \ne x independently, an attacker can query slightly perturbed vectors or paraphrased prompts x′≈xx' \approx x to average out the "noise" without ever repeating an exact query. Designing provable stateful defenses whose perturbations are correlated across geometric or semantic neighborhoods—or proving impossibility results for smooth continuous and sequence models—remains an important open problem, which we discuss in Section 8.

Ultimately, the main thrust of our paper is to examine distillation attacks and defenses from a theoretical angle. Alas, LLMs are not amenable to direct theoretical analysis, so instead many of our results are for much simpler models. Nonetheless, we hope that this provides a useful viewpoint on an important practical problem.

Reviewer_GtXwOpenReview ↗

Response to authors

I thank authors for their feedback, and adhere to my mostly positive assessment of the work.

Reviewer_LdEDOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper models distillation as a two player interactive protocol between a sever and a client. Security is against an adversarial client would like to interact and recover a hypothesis close to the original hypothesis. Several different order of quantifiers are given, and reations to PAC learning are established. Both positive and negative results for limited concept classes under cryptographic hardness assumptions are given.

This work begins by giving a basline information-theroetic distillation algorithm that shows that an unbounded adversary can recover a model up to O(\alpha) error where \alpha is the initial error parameter with O(n/α2)O(n / \alpha^2) queries when the hypothesis space has size bounded by 2O(n)2^O(n). Then, they show distribution-free "universal" distillation in the setting of a stateless server is equivalent to agnostic PAC learning. Distribution-free security states that for all adversaries, there exists a sample distribution D and a server S for which A cannot recover an approximate hypothesis. This is rather weak, and one would prefer that there exists a sample distribution D and a server S for which all poly-time adversaries cannot distill in the average over the hypothesis space. This is naturally given by the hardness of learning with noise, e.g. LPN (though they need to work in the RO model).

Finally, they show that for Boolean parities under the uniform distribution D, there exists an efficient distillation attack that succeeds against any computationally bounded server that has sufficicently accuract answers. The queries the malicious client makes is indistinguishable true draws from D.

Critical strengths

The clean statements and organization each point out a fundamental observation. As a theory paper goes, this is nice work.

Critical weaknesses
  • None.
Questions for authors

None.

1 comment

Thank you for your positive review and supportive evaluation of our paper!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.