# Differentially Private Language Generation and Identification in the Limit

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 19 references that are in the map.
- First posted on arXiv 9 Apr 2026.

## Builds on (most cited first, 11 of 11)

- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Generation through the lens of learning theory](https://mlsanity.com/paper/2410.13714/) (2024)
- [Generation from Noisy Examples](https://mlsanity.com/paper/2501.04179/) (2025)
- [VaultGemma: A Differentially Private Gemma Model](https://mlsanity.com/paper/2510.15001/) (2025)
- [Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations](https://mlsanity.com/paper/2511.05295/) (2025)
- [Language Generation: Complexity Barriers and Implications for Learning](https://mlsanity.com/paper/2511.05759/) (2025)
- [Safe Language Generation in the Limit](https://mlsanity.com/paper/2601.08648/) (2026)
- [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024)
- [Differentially Private Histogram, Predecessor, and Set Cardinality under Continual Observation](https://mlsanity.com/paper/2306.10428/) (2023)

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

- [Contrastive Identification and Generation in the Limit](https://mlsanity.com/paper/2605.06211/) (2026)
- [Hallucination Rates in Language Generation](https://mlsanity.com/paper/2607.23361/) (2026)
- [GenLimitLib: A Formal Library for Language Generation in the Limit and AI-Assisted Mathematical Research](https://mlsanity.com/paper/2609.36663/) (2026)

## Abstract (arXiv)

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 Omega(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.