cs.LGOct 31, 2026

Private Uniform Language Generation

Authors: Di Wang, Peng Ye

Organizations: King Abdullah University of Science and Technology.

Abstract

We study uniform language generation under approximate differential privacy. Given a uniformly bounded number of distinct examples from an unknown target language, a generator must produce infinitely many new examples from that language with probability one while protecting the privacy of its input. We introduce a new combinatorial dimension termed the nested branching dimension and prove that a language class is privately uniformly generatable if and only if both its closure dimension and nested branching dimension are finite. Previous work characterizes non-private uniform generation by the finiteness of the closure dimension alone. Our results therefore identify an additional combinatorial obstruction imposed by privacy.

Explore similar work

Apr 9, 2026

Differentially Private Language Generation and Identification in the Limit

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 kk for which uniform private generation requires Ω(k/ε)Ω(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.
Apr 8, 2026

On the Price of Privacy for Language Identification and Generation

Large language models train on sensitive user data, so we ask what differential privacy (DP) costs in language learning. We study private language identification and generation in the agnostic statistical setting. For identification, privacy is free: at every fixed ε\varepsilon, pure DP and (ε,δ)(\varepsilon,δ)-DP with δ≥n−O(1)δ\ge n^{-O(1)} keep the non-private rate exp⁡(−r(n))\exp(-r(n)) for every r(n)=o(n)r(n)=o(n). For generation, the price depends on what is public. With a public witness bound, pure DP loses at most a factor Θ(min⁡{1,ε})Θ(\min\{1,\varepsilon\}) in the exponent, and on suitable two-language collections the optimal rate is exp⁡(−Θ(min⁡{1,ε} n))\exp(-Θ(\min\{1,\varepsilon\}\,n)). Without such a bound, pure DP can lose the exponential rate itself, already for two languages: every rate exp⁡(−o(n))\exp(-o(n)) stays achievable, but no exponential rate is. On these collections, (ε,δ)(\varepsilon,δ)-DP keeps an exponential rate if and only if log⁡(1/δ)=o(n)\log(1/δ)=o(n). Three facts about pure DP drive the proofs. It turns a robustness margin into an exponentially small error. It obeys a private form of Le Cam's two-point bound. And it cannot see the absence of a string.
Aug 2, 2026

Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms

Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order, while the generator must eventually output only elements of the language that have not yet appeared in the enumeration. Reliable generation is thus formalized through two eventual guarantees: validity and novelty relative to the observed data. To further quantify the breadth of the generator's outputs, Kleinberg and Wei (FOCS 2025, STOC 2026) introduced lower density as a measure of output coverage. Given an order representing the importance or relevance of possible outputs, lower density is the asymptotic lower bound, as nn grows, on the fraction of the first nn elements of the target language that the generator outputs before they appear in the data. Kleinberg and Wei showed that 1/21/2 is the optimal lower-density guarantee for deterministic algorithms. We develop a simple and unified framework for obtaining optimal lower-density guarantees. We first give a deterministic algorithm that recovers the optimal guarantee of 1/21/2 with a significantly simpler analysis than prior work. We then demonstrate the flexibility of our framework through two extensions. First, against an oblivious adversary, randomization raises the optimal guarantee to 1−1/e1-1/e. Second, for any finite collection of orders, the optimal deterministic and randomized guarantees can be achieved simultaneously with respect to every order, so accommodating multiple notions of importance or relevance entails no loss in the optimal guarantee.