# The Sample Complexity of Membership Inference and Privacy Auditing

arXiv: https://arxiv.org/abs/2508.19458 · HTML: https://mlsanity.com/paper/2508.19458/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Membership inference attacks, one of 12 directions in LLM safety and security.
- First posted on arXiv 26 Aug 2025.

## Placed in

- LLM safety and security / [Membership inference attacks](https://mlsanity.com/safety/membership-inference-attacks/)

## Built on by (most cited first, 4 of 4)

- [ContextLeak: Auditing Leakage in Private In-Context Learning Methods](https://mlsanity.com/paper/2512.16059/) (2025)
- [Efficient Public Verification of Private ML via Regularization](https://mlsanity.com/paper/2512.04008/) (2025)
- [Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots](https://mlsanity.com/paper/2608.27782/) (2026)
- [Performative Privacy: When Differential Privacy Maximizes Utility](https://mlsanity.com/paper/2608.28198/) (2026)

## Abstract (arXiv)

A membership-inference attack gets the output of a learning algorithm, and a target individual, and tries to determine whether this individual is a member of the training data or an independent sample from the same distribution. A successful membership-inference attack typically requires the attacker to have some knowledge about the distribution that the training data was sampled from, and this knowledge is often captured through a set of independent reference samples from that distribution. In this work we study how much information the attacker needs for membership inference by investigating the sample complexity-the minimum number of reference samples required-for a successful attack. We study this question in the fundamental setting of Gaussian mean estimation where the learning algorithm is given n samples from a Gaussian distribution N(μ,Sigma) in d dimensions, and tries to estimate hatμ up to some error mathbbE[|hat μ - μ|2Sigma]≤ ρ2 d. Our result shows that for membership inference in this setting, Omega(n + n2 ρ2) samples can be necessary to carry out any attack that competes with a fully informed attacker. Our result is the first to show that the attacker sometimes needs many more samples than the training algorithm uses to train the model. This result has significant implications for practice, as all attacks used in practice have a restricted form that uses O(n) samples and cannot benefit from ω(n) samples. Thus, these attacks may be underestimating the possibility of membership inference, and better attacks may be possible when information about the distribution is easy to obtain.