Differentially Private Language Generation and Identification in the Limit

Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix ZhouarXiv 2026 · arXiv

TL;DR

This paper establishes the theoretical boundaries of language generation and identification under the strict constraint of differential privacy (DP) in a continual release model. The authors reveal a fascinating asymmetry: while private language generation is qualitatively "free" for any countable collection of languages, private language identification faces severe fundamental barriers in adversarial settings, though it remains fully viable when data arrives stochastically.

What Problem Does This Paper Address?

Large language models (LLMs) are trained on massive datasets that often contain sensitive or private user data, risking memorization and data leakage. To understand the fundamental limits of privacy in this domain, this paper analyzes language processing through a classical theoretical lens: learning "in the limit" (originally proposed by E. Mark Gold in 1967).

Specifically, it builds on a recent framework by Kleinberg and Mullainathan (2024) that shifts the goal from exact language identification (naming the target language out of a collection) to language generation (producing new, valid strings from the target language). The authors introduce differential privacy—specifically the stringent continual release model, where privacy must be maintained over an infinite stream of outputs—to determine which language collections can be safely generated or identified without exposing individual training exemplars.

Methods

The authors employ several sophisticated privacy mechanisms tailored to infinite data streams:

  • Laplace Mechanism with Sparse/Lazy Updates: For private generation (Algorithm 1), the algorithm computes noisy consistency counts at sparse intervals ($t_k = k^6$) using the Laplace mechanism. This "lazy update" paradigm controls the privacy budget over an infinite horizon.
  • Exponential Mechanism with Epochs: For private identification (Algorithms 2 and 3), the authors use the exponential mechanism run in epochs of exponentially increasing size ($t_s = 2^s$). They design custom score functions with low sensitivity that penalize incorrect languages based on error counts and "tell-tale" sets.
  • Group Privacy and Packing Arguments: To prove lower bounds and impossibility results, the authors leverage DP group privacy properties and packing arguments (using Sperner families) to demonstrate unavoidable sample complexity inflation.

Datasets

Not discussed in the paper. As a purely theoretical work, it uses mathematical formulations of abstract language collections (e.g., countable collections, finite collections with specific closure dimensions) rather than empirical datasets.

Key Insights and Ideas

  • Privacy is "Free" Qualitatively for Generation: Remarkably, requiring $\varepsilon$-DP in the strict continual release model does not restrict which countable language collections can be generated. If a collection is generatable non-privately, it remains generatable privately.
  • But Privacy Demands a Quantitative Tax: While privacy doesn't block learnability for generation, it slows it down. For a collection of size $k$, a non-private algorithm needs just 1 sample after reaching its closure dimension, whereas a private one requires $\Omega(k/\varepsilon)$ samples.
  • The Identification Barrier: Naming the language is fundamentally harder than generating from it under privacy. If two languages overlap infinitely but differ by only a finite number of strings, an adversary can trick any private identifier into making infinite mistakes.
  • Adversarial vs. Stochastic Separation: Privacy forces a sharp wedge between adversarial streams and stochastic (i.e., i.i.d. sampled) streams. In the non-private world, these two settings are equivalent for identification. Under DP, stochastic identification completely bypasses the adversarial impossibility result.

Key Results

  • Theorem 1.1 (Private Generation): Proves that an $\varepsilon$-DP algorithm exists that can successfully generate in the limit from any countable collection of languages.
  • Sample Complexity Bounds: For a finite collection of size $k$ and closure dimension $d$, the private sample complexity is upper-bounded by $d + \tilde{O}((k/\varepsilon) \cdot \log(1/\beta))$ and lower-bounded by $d + \Omega(k/\varepsilon)$, establishing a tight trade-off.
  • Theorem 1.5 (Identification Impossibility): Proves that no $\varepsilon$-DP algorithm can identify a collection in the limit if it contains two distinct languages $L_i, L_j$ where $|L_i \cap L_j| = \infty$ and $|L_i \setminus L_j| < \infty$.
  • Theorem 1.6 (Stochastic Feasibility): Shows that in the stochastic setting, a countable collection is privately identifiable if and only if it satisfies Angluin’s classical non-private condition.

Limitations and Future Work

  • Countable vs. Uncountable Collections: The positive results are restricted to countable collections of languages. The authors explicitly note that exploring whether private algorithms can be designed for uncountable collections remains an open question.
  • Strictness of Pure DP: The paper focuses entirely on pure $\varepsilon$-DP in the continual release model. The authors suggest that investigating more lenient or relaxed variants of differential privacy (like approximate DP or Rényi DP) might mitigate some of the harsh lower bounds found in adversarial identification.
  • Interplay with Breadth: The connection between privacy constraints and the "breadth" (diversity) of generated language remains an open area for deeper exploration.

Summary updated

Abstract

We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy. We consider the continual release model, where a generator must eventually output a stream of valid strings while protecting the privacy of the entire input sequence. Our first main result is that for countable collections of languages, privacy comes at no qualitative cost: we provide an $\varepsilon$-differentially-private algorithm that generates in the limit from any countable collection. This stands in contrast to many learning settings where privacy renders learnability impossible. However, privacy does impose a quantitative cost: there are finite collections of size $k$ for which uniform private generation requires $Ω(k/\varepsilon)$ samples, whereas just one sample suffices non-privately. We then turn to the harder problem of language identification in the limit. Here, we show that privacy creates fundamental barriers. We prove that no $\varepsilon$-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference, a condition far stronger than the classical non-private characterization of identification. Next, we turn to the stochastic setting where the sample strings are sampled i.i.d. from a distribution (instead of being generated by an adversary). Here, we show that private identification is possible if and only if the collection is identifiable in the adversarial model. Together, our results establish new dimensions along which generation and identification differ and, for identification, a separation between adversarial and stochastic settings induced by privacy constraints.
BibTeX
@misc{mehrotra2026differentially,
  author = {Anay Mehrotra and Grigoris Velegkas and Xifan Yu and Felix Zhou},
  title = {{Differentially Private Language Generation and Identification in the Limit}},
  year = {2026},
  eprint = {2604.08504},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.08504},
}
Figure