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

CardsList
  1. Differentially Private Language Generation and Identification in the Limit

    Apr 9, 2026Anay Mehrotra, Grigoris Velegkas, Xifan Yu +1Text GenerationDifferential Privacy

  2. On the Price of Privacy for Language Identification and Generation

    Apr 8, 2026Xiaoyu Li, Andi Han, Jiaojiao Jiang +1Privacy-Preserving Language ModelsLanguage Identification

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

    Aug 2, 2026Ziyi Cai, Shuangping Li, Yiheng Shen +2Text Generation