Research map / Learning theory and algorithms / Sample complexity
Representative Language Generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends language generation in the limit (Kleinberg & Mullainathan 2024) with a representation requirement, characterizing representative uniform and non-uniform generation via a new group closure dimension and showing limit results and a membership-query impossibility.
Problem
Generative models that achieve consistent generation may still output from a narrow subset of the true language, failing to proportionally represent groups in the training data (diversity and bias concerns, mode collapse).
Approach
Requires each output distribution at every step to match the group proportions of unique training examples seen so far (sup-norm alpha-representativeness), combined with eventual consistency; introduces the group closure dimension to characterize representative uniform generation and critical-and-feasible hypotheses for generation in the limit.
Key results
- Representative uniform generation is characterized by finiteness of the group closure dimension; every finite hypothesis class with a finite partition is representatively uniformly generatable.
- Every countable hypothesis class with a finite partition is representatively non-uniformly generatable.
- Any countable collection of possibly overlapping groups satisfying the finite support assumption can be generated in the limit with representation, while no generator can do so using only finitely many membership queries per step for all finite classes.
Surprising findings
- A trivially uniformly generatable class can fail representative uniform generation with just two disjoint groups.
- Representative generation in the limit fails for a single-hypothesis class with a countably infinite partition that violates finite support.
Limitations
- Characterizations for uniform and non-uniform generation are information-theoretic and ignore computational efficiency.
- Results for uniform and non-uniform generation assume groups form a partition; overlapping groups are left open.
- Supremum-distance representation with asymmetric consistency/representation requirements may not match practical trade-offs.
Experimental setup
Builds on: language generation in the limit (Kleinberg & Mullainathan 2024) uniform and non-uniform generation (Li et al. 2024 / Raman & Raman 2024) multicalibration for distributions (Gopalan et al. 2022)
Closest papers by meaning
- On Union-Closedness of Language Generation (NeurIPS 2025 · similarity 0.88)
- Language Generation in the Limit (NeurIPS 2024 · similarity 0.85)
- Generative Monoculture in Large Language Models (ICLR 2025 · similarity 0.84)
- Generating in the Limit with Infinitely Many Hallucinations (NeurIPS 2026 · similarity 0.84)
- Towards a Theoretical Understanding of Synthetic Data in LLM Post-Training: A Reverse-Bottleneck Perspective (ICLR 2025 · similarity 0.84)
- SimpleStrat: Diversifying Language Model Generation with Stratification (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.