Differentially Private Language Generation and Identification in the Limit

arXiv:2604.08504v1 Announce Type: cross 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 arepsilon-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/arepsilon) 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 arepsilon-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.

Related

• Diffusion Language Models Know the Answer Before Decoding
• Cross-Tokenizer LLM Distillation through a Byte-Level Interface
• Double: Breaking the Acceleration Limit via Double Retrieval Speculative Parallelism
• DIVERSED: Relaxed Speculative Decoding via Dynamic Ensemble Verification
• Entropy-Gradient Grounding: Training-Free Evidence Retrieval in Vision-Language Models
• See the Forest for the Trees: Loosely Speculative Decoding via Visual-Semantic Guidance for Efficient Inference of Video LLMs

Source: arXiv cs.CL | 2026-04-10