Representative Language Generation
Authors: Charlotte Peale
Vinod Raman
Omer Reingold
Venue: ICML 2025 poster (2025)
Keywords: generation in the limit
generation
representation
fairness
diversity
language generation
Primary area: theory->learning_theory
TL;DR: We introduce "representative generation," a theoretical framework for generative models requiring outputs to be consistent with the target language and proportionally represent groups in the training data, addressing bias and diversity concerns.

Abstract: We introduce "representative generation," extending the theoretical framework for generation proposed by Kleinberg et al. (2024) and formalized by Li et al. (2024), to additionally address diversity and bias concerns in generative models. 
Our notion requires outputs of a generative model to proportionally represent groups of interest from the training data.  We characterize representative uniform and non-uniform generation, introducing the ``group closure dimension'' as a key combinatorial quantity. For representative generation in the limit, we analyze both information-theoretic and computational aspects, demonstrating feasibility for countably infinite hypothesis classes and collections of groups under certain conditions, but proving a negative result for computability using only membership queries. This contrasts with Kleinberg et al.'s (2024) positive results for standard generation in the limit. Our findings provide a rigorous foundation for developing more diverse and representative generative models.

Representative Language Generation
Charlotte Peale"
Vinod Raman $2
Omer Reingold
Abstract
opment of new theoretical frameworks to rigorously analyze their performance, capabilities, and limitations. Recently, Kleinberg & Mullainathan (2024) proposed a theoretical framework that encapsulates the fundamental objective of generative models: after being shown sequence of strings from an unknown target language (such as all valid code snippets in java), generate new, unseen strings from the target language. Informallyy we say that model satisfies generation in the limit if it achieves this goal after seeing finite number of strings from the target language. Kleinberg & Mullainathan (2024) showed that generation in the limit is indeed possible in many scenarios, such as whenever the class of potential target languages is countable, contrasting to classic negative results by Gold and Angluin on identifi- cation, which tell us that no model can identify the target language from sequence of strings for most natural classes of languages (1967; 1979; 1980). This positive result for the task of language generation has spurred flurry of follow- up works further formalizing the landscape of generation tasks and understanding the limits of when generation is possible (Li et al., 2024; Kalavasis et al., 2024b; Charikar Pabbaraju, 2024; Kalavasis et al., 2024a).
We introduce "representative generation." extend- ing the theoretical framework for generation pro- posed by Kleinberg et al. (2024) and formalized by Li et al. (2024), to additionally address diver- sity and bias concerns in generative models. Our notion requires outputs of generative model to proportionally represent groups of interest from the training data. We characterize representative uniform and non-uniform generation, introducing the "group closure dimension" as a key combina- torial quantity. For representative generation in the limit, we analyze both inffommation-thhorrttie and computational aspects, demonstrating feasi- bility for countably infinite hypothesis classes and collections of groups under certain conditions, but proving negative result for computability using only membership queries. This contrasts with Kleinberg et al.'s (2024) positive results for stan- dard generation in the limit. Our findings provide a rigorous foundation for developing more diverse and representative generative models.
While these recent results have demonstrated the possibility of successful generation, concern remains that models that successfully generate in the limit may do so by generating from a restricted subset of the true language. For instance, consider an image generator trained on a diverse set of ani- mal pictures. If this model were to produce only new images of cats, would technically satisfy the criteria for generation in the limit, yet fail to capture the full diversity of the true target set of animal pictures. In the spirit of this example, it is not hard to imagine real-life concerns about the usage of LLMs and other generative models. Training data often includes text or images representing diverse groups, char- acterized by ethnicity, race, gender, and other protected at- tributes. However, the mere presence of diverse data doesn't 't guarantee diverse outputs. Beyond demographics, it's es- sential to ensure that generators intended for widespread use accurately reflect the diverse perspectives found across various communities. Ensuring proportional representation in a generator's 's outputs can significantly enhance its utility, enabling it to accurately reflect the diverse trends, themes, and ideological perspectives present in human discourse. rather than producing homogeneous responses.
1. Introduction
For decades, a central paradigm in machine learning has been prediction, where models are trained to map input data specific output variables or categories. This approach compasses tasks such classification and regression, where the goal is to accurately estimate outcomes based on given inputs. However, recent years have seen significant shift toward generative models, such as Large Language Mod- els (LLMs) and diffusion-basse image generators. These models are designed not to predict specific outcomes, but to create new data that resembles their training sets, offering different approach to machine learning tasks.
This shift towards generative models necessitates the devel-
Equual contribution 'Stanford University University of Michi- gan. Correspondence to: Charlotte Peale <epeale @ stanford.edu>>, Vinod Raman <vkraman& @ @umich.cdu>.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Representative Language Generation
This theoretical concern mirrors practical challenges ob- served in real-world generative models. One significant issue is the potential for these models to exacerbate biases present in their training data, leading to unfair representation across different demographic groups (Sheng et al., 2019;
tive generation in the limit, we analyze feasibility from both information-theorrtie and computational perspectives. We prove strong negative result, demonstrating the impossibil- ity of achieving representative generation in the limit using only membership queries.
Bender et al., 2021; Kirk et al., 2021; Sheng et al., 2021; Mei et al., 2023; Gallegos et al., 2024; Zhou et al., 2024). Beyond fairness considerations, models that fail capture the diversity of their data reduce their effectiveness and prac- tical value. This reduced diversity is commonly observed in generative models and referred to as "mode collapse," in which a learned model focuses only on a limited subset of the true data distribution (Arjovsky et al., 2017; Goodfellow et al., 2020; Thanh- Tung Tran, 2020; Wang et al., 2024).
We give a brief overview of our main contributions below.
Formalizing Representative Generation. We propose new property of generators termed represenlative genera- tion. This property ensures that at each timestep, a genera- tor's s outputs closely approximate the proportions of training data across a collection of groups A C 2* Our definition extends the formal model of generation by Kleinberg & Mullainathan (2024), providing a rigorous framework to understand and address several real-world concerns related to generative models that we highlight below.
In this work, we introduce a new definition of generation that protects against these concerns that we term representa- live generation. Rather than generating single element at each step, representative generator generates a distribution over multiple elements at each step. In addition to the now standard requirement that a generator must eventually be consistent, i.e. the distribution must be supported on new elements from the true language, we additionally require that all of the generator's outputted distributions be repre- sentative, meaning that for each group in set of groups- of-interest, the proportion of elements from that group seen in the training sequence thus far must be close to the prob- ability that the generator outputs a member of that group. Coming back to our animal example, if our training data stream consisted of 1/3 cats, 1/3 dogs, and 1/3 rabbits, then representative generator with respect to groups specified by animal species could not get away with only generating cats, but would be required to generate a roughly even mix of cats. dogs, and rabbits.
First, representative generation can guarantee accurate pro- portional representation of community opinions and per- spectives found in the training data. This is crucial for maintaining the diversity of viewpoints present in the origi- nal dataset. Second, when the training data is highly diverse across the set of groups-of- of-intess, the generator's outputs must also exhibit high diversity. This feature protects against mode collapse and offers a tractable relaxation to existing notions of generation with breadth, which we discuss further in Appendix A.
Representative generation can also be viewed as a theoreti- cal operationalization of some aspects of "alignment," the process of fine-tuning generative models to conform with societal and use-specific values. Imagine feeding repre- sentative generator gold-standard distribution of data that encapsulates a practitioner's 's values and diverse opinions. Unlike standard generators, which may learn to produce correct outputs but offer no guarantees about maintaining alignment with the input data distribution, representative generators designed to both generate accurate outputs and preserve the distribution of values and perspectives found in the alignment data. This approach ensures that the model remains faithful to the intended balance of viewpoints and opinions, even as it generates novel content.
We provide a detailed discussion of related notions and additional related work in Appendix A.
1.1. Main Contributions
The loose goal of "eventually generating consistently" has been taxonomized by prior works into a hierarchy of three notions of generation. The weakest is Kleinberg & Mul- lainathan (2024)'s 's generation in the limit (Definition 2. 22)) followed by the stronger notions of non-uniform genera- tion and uniform generation introduced by Li et al. (2024) (Definitions 2.1 and 2. 10, respectively).
Representative Uniform Generation. We give char- acterization of which pairs of hypothesis classes H and collections of groups A satisfy representative uniform gen- eration, assuming the groups in A form a partition of X. We characterize the representative uniform generatability of a pair (H, A) by a new combinatorial quantity that we term the group closure dimension (Definition 3.1):
Our results consider the feasibility of representative gen- eration with respect to all three goals. For uniform and non-uniform generation, we focus on cntemattion-hhorretie bounds, analogous to sample complexity results in learning theory, without considering computational efficiency. This approach is motivated by the recent barrier to efficiently computable non-uniform generators identified by Charikar & Pabbaraju (2024). For the weaker objective of representa-
Theorem 1.1 (Informal Statement of Theorem 3.3). A hy- pothesis class H and countable partition A can be uniformly generated with representation if and only if the group clo- sure dimension of (H A) is funite.
2

---

Representative Language Generation
We instantiate this result in Corollary 3.5, where we show that any finite hypothesis class H and finite partition A can satisfy representative uniform generation. This corollary can be compared with Theorem 2.2 of Kleinberg & Mul- lainathan (2024), who show that any finite H is uniformly generatable (without concern for representation).
alor can satisfy representative generation in the limit for all finite HH and A, and during each timestep use only finite number of membership queries of the form "x E supp(h)?" or "x E A?" for various h E H. and A E A.
The impossibility contrasts with positive result of Klein- berg & Mullainathan (2024), who show that generation in the limit (without representation) is possible with only a finite number of membership queries each timestep.
While one might wonder if requiring representation with respect to only finite collection of groups is always as casy as uniform generation without representation, we provide counterexample to this conjecture in Corollary 3.6, in which we provide an example of a class H that is uniformly gener- atable, but cannot satisfy representative uniform generation with respect to a partition A containing just two disjoint groups.
2. Preliminaries
We consider a countable example space X', and associate with X' a hypothesis class H S {0, 1)x². Any particular h E H can be thought of as an indicator for a valid element of X' when h(x) 1. In the context of languages, h denotes language with h(x) when æ is valid string in that language.
Representative Non-Uniform Generation. We next con- sider the slightly weaker notion of representative non- uniform generation, and also give a characterization of which pairs of hypothesis classes and collections of disjoint groups can satisfy non-uniform generation with representa- tion.
We define the support of a hypothesis h to be the set of all valid elements of X' according to h, denoted supp(h) == {a E X' : h(z) = 1}. We will also sometimes reference the support of a distribution j E AX, where supp(") == {ar X : u(x) > 0} refers to the set of elements that are drawn from the distribution with positive probability. An enumeration of supp(h) is any infinite sequence z1, Z2, such that Ulen { = supp(h).
Theorem 1.2 (Informal Statement of Theorem 3.7). hy- pothesis class H and countable partition A can be non- uniformly generated with representation if and only if there exists non- non-decreasing sequence of classes Hi S H2 S ...such that H = U Hi and (Hi, is uniformly gen- eratable with representation for all i E N.
We will make the following assumption about hypothesis classes throughout.
We pair this characterization with a practical instantiation in Corollary 3.8, in which we show that all countable H and finite partitions A satisfy representative non-uniform generatability.
Assumption 2.1 (Uniformly Unbounded Support (UUS)).
A hypothesis class H S. {0, 13* satisfies the Uniformly Unbounded Support (UUS) property if [supp(h)] oo for every h H.
Representative Generation in the Limit. Finally, we consider the weakest notion of generation: representative generation in the limit, As all previous possible results also apply to this weaker setting, the results of the preceding sections already establish that any countable H and finite collection of disjoint groups A can be generated in the limit with representation. We show that the requirement that A be finite and disjoint can be significantly relaxed when we only require generation in the limit. In particular, in Theorem 4.4, we show that any countable collection of (possibly overlap- ping) groups and countable H satisfying an assumption we term the finite support assumption (Definition 4.2) can be generated with representation in the limit.
Going beyond the standard model of generation that has been considered in prior works, we also endow the space X' with a countable set of (possibly overlapping) groups-of- interest A S 2* We assume that X' C UAEA A, though this is without loss of generality because any A can be al- tered to satisfy this by adding a single group the collection corresponding to the complement of the union of all existing groups
Our results on representative uniform and non-uniform gen- cration presented in Section focus on the special case where A forms a partition of Xt:
Definition 2.2 (Countable Partition). Let X' be any count- able example space. Then, A := (Ai, Ag.... is a count- able partition of X if and only if the following two con- ditions hold: (1) A, n Aj = 0 for all i * j and (2) U A; X.
We show that this finite support assumption is necessary, and in Lemma 4.3 give an example of finite H. and countable set of disjoint groups A that cannot satisfy representative generation in the limit.
We introduce two operators that will be useful for notation throughout. Note that we occasionally denote a finite se- quenee I1, Fn by Fimn, and use [#1,,.., xr to denote
We finally turn to computability, and show negative result: Lemma 1.3 (Informal Statement of Lemma 4.9). No gener-
3

---

Representative Language Generation
the number of unique elements in Fi:n-
Our choice to focus on the supremum distance draws di- rectly the foundational principles established in algorith- mic fairesss literature, which emphasizes the importance of limiting the error experienced by the worst-off group. This perspective prioritizes ensuring good representation for every group rather than merely optimizing for average per- formance. The supremum distance naturally operationalizes this principle by measuring the maximum disparity across all groups, effectively placing an upper bound on the error that any group might experience.
Definition 2.3 (Set of Consistent Hypotheses). For any finite sequence of samples Fi.m and hypothesis class H. we define notation for the set of hypotheses consistent with the sample: ((11:))= == fhe E H. : {rim} S supp(h)).
Definition 2.4 (Closure). Given a class H and finite se- quence of samples #1,..., define the closure operator as the set of samples consistent with every hypothesis in H(II, ... In):
(11, ... En)N )nep(en.)supp(h supp(h), if [1(mm 2 21
It's worth noting that for finite group settings, different choices of distance measures (L, or L2 distance) are typically within constant factors of one another, making the specific choice less critical. However, as we move to settings with infinite groups, these equivalences break nown-distance measures such as L1 become less infor- mative, potentially obscuring significant disparities among individual groups
if H((1m)] = O.
2.1. Generators
In this paper, we will consider randomized generators. A randomized generator is a map 9 : X + AX. Note that by definition, randomized generators output distributions over examples. Given a finite sequence of examples æ1; #i;...." Zt and randomized generator G. one can always obtain new example by sampling ê. (Z By allowing our generators to output distributions measure "representation" by comparing how close a dis- tribution's 's induced group probabilities are to the empirical probabilities of the groups in the stream. To formalize this, we need a few more definitions, starting with induced group probabilities and group empirical probabilities.
While we selected the supremum distance for its robust guar- antees from an algorithmic fairness perspective, exploring representation guarantees under alternative distance metrics is certainly an interesting direction for future research.
examples,
can
Finally, we are now able to rigorously define what it means to be a-representative.
Definition 2.8 (a-Representative Generator). A randomized generator is a-representative with respect to a countable collection of groups A if for every stream of examples Fτ, .2.... and for all t E N, we have that [[9(z1=)14 कi. AAll S a.
Definition 2.5 (Induced Group Probabilities). Given distribution μ E AX' and countable family of groups A = {A]iE,, let plA denote p's induced probabilities over A such that for any group i E N, we have that (1) == Przza [x E A,].
On its own, a-representativeenss trivial to achieve given any collection of groups A and any finite sequence I Z1y..., Tt, one can always output exactly the empirical distribution, Z1.1- Thus, our goal will be to satisfy represen- tation in addition to existing definitions of correctness for generation, as defined in Section 2.2.
Observe that for any countable partition A {Athen and 1 E AX, A is probability distribution. If A is not partition, the probabilities in م|a may sum to more than 1. Definition 2.6 (Empirical Distribution and Group Empir- ical Probabilities). Let T1,..., Te be a finite sequence of examples, and zi.... xx, denote its subsequence of unique examples. The empirical distribution of unique examples in .I, is denoted by Ti.z. In particular, for every x e X, we have (x) m able collection of groups A [A. the group empirical probabilities of the unique examples in æı...., 2, with re- spect to A are defined analogously as the induced group probabilities of the empirical distribution and denoted by Ji:elA-
2.2. Representative Generation
In this section, we introduce several notions of representa- tive generatability for a tuple (H, A), each varying in the amount of distinct examples that an a-representative gener- ator can observe before it needs to "succeed." In our setting, a a a-representative generator "succeeds" if it is eventually "consistent." Formally, given an a-representative genera- tor G, hypothesis h E H, and any stream T1, T2, C supp(h), we say that G is consistent from time point / e N, if for all s 2 t:
1 - 1(2; = r}. Given count-
The final ingredient is measure of closeness between the induced group probabilities of the output of a randomized generator and the empirical group probabilities:
[ E supp(h) \ R (((.))
Pr
Definition 2.7 (Supremum Distance). Given two vectors T1 T2 E [o, 11 define their supremum distance as ||
We note that generators are allowed some initial inconsistent outputs, provided they eventually achieve consistency. In
T2l 2o = maxen (i) - T2 (i))
4

---

Representative Language Generation
contrast, outputs must be representative of the data stream at every timestep. Thus, our definition implicitly prioritizes group representation over correctness in generation during initial timesteps. While consistency cannot always be ver- ified, it is possible to construct and verify a representative distribution at each time step. This makes it reasonable to require representation throughout, and less reasonable to favor potentially consistent but verifiably unrepresentative alternatives. However, understanding the tradeoffss between representation and consistency is an interesting direction of future research.
with {2), (2,, 22...................... S supp(h), if there exists 1 N where ( Fr } = d', then 9 is consistent from t*.
Finally, we can weaken the requirements even further by allowing the sample complexity to depend on both the hy- pothesis and stream selected by the adversary.
Definition 2.12 (Representative Generation in the Limit), Let H S {0, 11.² be any hypothesis class satisfying the UUS property and A = (Ai)ien be any countable collec- tion of groups over X. Then, (H, A) is representatively generatable in the limit, if for every a >> 0 there exists an a-representative generator G such that for every h E H. and any enumeration , T2, of supp(h), there exists t* E N such that G is consistent from 8*.
Given our definitions of consistency and representativeness, we are now ready to introduce the strongest form of rep- resentative generatability- - a-representative uniform gen- eratability. Roughly speaking, a-representative uniform generatability requires that the amount of unique examples that G needs to observe before being consistent should be uniform over all h E H. and streams P2, ... S supp(h).
We remark that our notions of generatability are direct analogs of those from Li et al. (2024) with an additional representation requirement.
Definition 2.9 (a- Representatiie Uniform Generatabilityy. Let H C 10 be any hypothesis class satisfying the UUS property and A = {Ai)ieN be any collection of groups over X. Then, AH is a-representatively uni- formly generatable if there exists an a-representative gen- erator G and d' E N, such that for every E H and any sequence $1,22.... with {æt, Z2.... S supp(h), if there exists 1* E N where (æ1,..., 2r }| d", then G is consistent from t".
3. Characterizations of Representative Uniform and Non-uniform Generation
In this section, we focus on characterizing representative uniform and non-uniform generatability. In light of the com- putational barriers for uniform and non-uniform generation established by Charikar & Pabbaraju (2024), our characteri- zation is information-theorelt in nature. Moreover, we will only consider collections of groups A which are countable partitions of X' This is still a very general setting, capturing problems like animal image generation, where one consid- ers groups based on class. We leave the characterization of representative uniform and non-uniform for overlapping collections of groups as future work.
A tuple (H, is then representatively uniformly gener- atable if it is e-representatively uniformly generatable for every (0, 1].
Definition 2.10 (Representative Uniform Generatability), Let H _ (0, 1)x be any hypothesis class satisfying the UUS property and A = {Athee be any collection of groups over X. Then, AH) is representatively uniformly generatable, if (H, A)) is a-representatively uniformly gen- eratable for every a E (0, 1].
3.1. Representative Uniform Generation
Our starting point is representative uniform generation. In order to characterize which classes are representatively uni- formly generatable, we extend the Closure dimension from Li et al. (2024) to account for the group-conee conptrconsssaitts induced by A. To do so, we define a new scale-sensitive dimension, termed the Group Closure dimension, which accounts for the complexity induced by both H and A.
Representative uniform generatability is strong property as it requires the sample complexity (i.e. number of distinct examples before consistency is achieved) to be uniform over all choices of the adversary. We can weaken the definition by allowing the sample complexity to depend on the hypothesis, but still be uniform over all possible streams of examples the adversary might pick. This leads to our next notion of representative non-uniform generatability.
Definition 3.1 (Group Closure dimension). Let H. S (0, 1) be any hypothesis class satisfying the UUS prop- erty and A = {Ai)ien be any countable partition of X. The Group Closure dimension of (H. A) at scale a > 0, denoted (C,, is the largest natural number d E N for which there exists distinct 21...., Ed E X such that (II, ...)...a)) H o 11 and either (1) maxies Fi:dl (i) > I..
Definition 2.11 (Representative Non-uniform Generatabil- ity). Let 7 C f0, 1 be any hypothesis class satisfying the UUS property and A = (AN)ie be any countable col- lection of groups over X. Then, (H. is representatively non- unifurrfl generatable, if for every a > 0 there exists an a-representative generator G, such that for every h E H. there exists a d' E N such that for any sequence ZT, ..,...
or (2) a N/S| < Eies Flddl where S == {i E N (Z),..., xa) AAA ( xa) = 6). If this is true for arbitrarily large d E N, then we say that GC (H, A) = co.
On the other hand, if this is not true for 1, we say that
5

---

Representative Language Generation
GC,,H,, = 0.
examples. To prove that the finiteness of GC (H; is suf- ficient, construct an a-representative generator 9 which satisfies consistency after observing GC. (H, A) +1 distinct examples. Unlike uniform generation without representa- tion, our generator 9 for representative uniform generation computes closures at every time point E N. Combining both the necessary and sufficient directions shows that not only does the finiteness of GC. (H, A) characterize a-group constrained uniform generation, but also that the optimal sample complexity is exactly (GC., (H, A)). We defer the full proof of Theorem 3.3 to Appendix C.I.
Remark 3.2. Our definition of the Group Closure dimen- sion is for countable groups A = (A.) One can de- fine the Group Closure dimension for finite groups A = (Aihe(k) by modifying the definition of S and condi- tion (2) in the following way. Define S := {i E [K] : (ri,..... "......TT)) O A, \ fx1.....,fdd Fa) = () and then change (2) to a(K- - (S|) < Lies Tital (i).. We will use this modified definition when proving Corollary 3.5.
At a high-level, for any given error tolerance a > O, one should interpret GC (H, A) as the minimal number of dis- tinct examples that a generator needs to see before it is guaranteed a winning strategy with respect to error level a (i.e. one that is both consistent and a-representative). In- deed, as we will show in this section, GC (H, .A) provides a precise quantitative bound on the sample complexity of representative uniform generation for A). We highlight that unlike the Closure dimension, the Group Closure di- mension depends on both H and A and is scale-sensitive and defined for every a > 0. Scale-sensitive combinato- rial dimensions are not new to learning theory, and have also been defined to characterize learnability for regression problems (Bartlett et al., 1994; Rakhlin et al., 2015).
Another important consequence of Theorem 3.3 is its im- plications on representative uniform generation for finite H and A. Our next result uses the Group Closure dimension and Theorem 3.3 show that all tuples (H, where both H and A are finite are representative uniform generatable. The full proof can be found in Appendix C.2
Corollary 3.5 (All Finite Classes and Finite Partitions Representatively Uniformly Generatable). Let X be count- able, H S {0, 1)x be any finite class satisfying the UUS property, and A = {Aike be any finite partition of X. Then, (H, is representatively uniformly generatable.
As we will show in Lemma 4.3, the finiteness of is in a weak sense necessary for Corollary 3.5 to hold if A is allowed to be countably infinite in size, there exists a hypothesis class of size one that is not even generatable in the limit with representation! Nevertheless, even when A is finite, representative uniform generation is still harder than (unrepresentative) uniform generation as evidenced by the following Corollary, which we prove in Appendix C.3.
Our first result in this section shows that for every a > 0, the finiteness of GC (H, A) provides a qualitative charac- terization of o-group constrained generatability.
Theorem 3.3 (Characterization of a a-Representative Uni- form Generatability). Let X' be countable. H S. {0, 1 be any class satisfying the UUS property. and A = (Athen be any countable partition of X. Then, AH) is a-representatively uniformly generatable if and only if (H, < oc.
Corollary 3.6 (Representative Uniform Generation & Uni- form Generation). Let X be countable. There exists a countable, UUS class H S {0, and a finite partition
An immediate consequence of Theorem 3.3 is characteri- zation for representative uniform generatability.
A = {A (e(k of X' such that H is uniformly generatable but (H, is not representutively uniformly generatable.
Corollary 3.4 (Characterization of Representative Uniform Generatability). Let X be countable, H. S {0, 1)xx be any class satisfying the UUS property, and A = (Ai) be any countable partition of X. Then, A) representatively uniformly generatable if and only if (H, < oo for all O.
In fact, Corollary 3.6 shows something stronger there are trivially uniformly generatable classes which are not representatively uniformly generatable with just two groups This brittleness of generatability when forced to satisfy both consistency and representation is not unique to our notion of diversity, but also shown by existing work on generation with breadth (Kalavasis et al., 2024b; Charikar & Pabbaraju, 2024; Kalavasis et al., 2024a).
Our proof of Theorem 3.3 is constructive. In particular, to show that the finiteness of GC GC, (H. is necessary, we first assume that GC, (H,, = xc. Then, for every gen- erator G. we explicitly choose a hypothesis h E H. and construct a valid stream of examples 21, 22. C supp(h) a-
3.2. Representative Non-uniform Generation
such that G eventually violates either consistency representativeness. In fact, if GC,, A) = d, simple adaption of our proof shows that for any generator G. there exists a hypothesis h E H and a valid stream of exam- ples 1 Ø2, ... S shpp(h) such that g violates either con- sistency or a-representativeness after observing d distinct
We now proceed to give a characterization of representa- tive non-uniform generation. Recall that for non-uniform generation, we allow the sample complexity (i.c., the num- ber of distinct examples needed before consistency) of the generator to depend on the hypothesis chosen by the adver- sary, but not the stream. Similar to the characterization of
6

---

Representative Language Generation
non-uniform generatability from Li et al. (2024) without representation constraints, our main result in this section provides characterization of representative non-uniform generation in terms of representative uniform generation.
Aas
fnLA= =
Σ SEA, Iraes Arsupp(())<<c
In AES
An supp(h)
Theorem 3.7 (Characterization of Representative Non-uni- form Generatability). Let X be countable, H [ {0, 1 be any class satisfying the UUS property, and A = {At Jien X.
In other words, the total size of all arbitrary intersections with subset of groups in A and the support of h. Note that in the case of disjoint groups, this quantity simplifies to the number of individuals in supp(h) that are members of groups that have finite intersection with supp(h). While any finite collection of groups A will always satisfy the finite support assumption, this is not the case for countably infinite sets of groups. A simple example of a collection of groups that does not satisfy the assumption is any infinite collection of groups where the size of every group is finite, such as the collection of all singletons A = {(=} : x E X), or the collection defined in the proof of Lemma 4.3.
be any countable partition of Then, A) is represen- tatively pon-uniformly generatable if and only for every > there exists a non-decreasing sequence of classes Hi C H2 -... such that H = U H4 and (H,,A) is a-representative uniformly generatable Vi N.
The proof of Theorem 3.7 is similar to the proof of Theorem 3.5 Li et al. (2024), hence we defer the details to Appendix C.4. We instantiate Theorem 3.7 with Corollary 3.8 to show that every tuple (H. where H is countably infinite and A is finite is representatively non-uniformly generatable. The proof of Corollary 3.8 is in Appendix C.5. Like for representative uniform generation, the finiteness of A is, in weak sense, necessary for Corollary 3.8 to hold.
Definition 4.2 (Hypothesis Class with Finite Support). We say that a hypothesis class H. has finite support with respect to a collection of groups A if for every h E H. fr.A < co.
While ideally we could show that all classes of countable groups can be generated in the limit with representation without any additional assumptions, the following lemma shows that this finite support assumption is crucially neces- sary for generatability with representation.
Corollary 3.8 (All Countable Classes and Finite Partitions are Representatively Non-uniformly Generatable). Let X be countable, H. S {0. 1}x be any countably infinite class satisfying the UUS property, and A = {Atee be any finite partition of X. Then, (H, A) is representatively non- uniformly generatable and hence, also representatively gen- eratable in the limit.
Lemma 4.3 (Necessity of Finite Support). There exists countably infinite partition of X, A, and a finite hypothesis class H. with [H] = 1 that is not generatable in the limit with representation for any 0 < a << 1.
4. Representative Generation in the Limit
The proof of Lemma 4.3 can be found in Appendix D.I. We contrast this impossibility result with a strong positive result: any countable H and countable, possibly overlapping A satisfying the finite support assumption can be generated in the limit with representation.
We finally consider the weakest definition of successful gen- eration: generation in the limit. As per Definition 2. 12, this requires a generator to output a distribution representative of the data stream at each timestep, and after some finite point in time, all outputs must be consistent with the true lan- guage. We note that as the weakest notion of generation, all positive results from Section 3 for uniform and non-uniform representative generatability apply to representative gener- atability in the limit. Notably, Corollary 3.8 implies that any countably infinite H can be generated in the limit with representation for any finite partition A of X.
Theorem 4.4. Let X be countable, H S. 10,1)* be any countable class satisfying the UUS property, and A = (Ai a countable collection of possibly overlapping sub- sets of X such that H has finite support with respect A. Then, (H, is representative generatable in the limit.
Before providing the proof in full, we provide a sketch of the main ideas. In Kleinberg & Mullainathan (2024), the generator they provide to generate in the limit uses the notion of a critical hypothesis:
In this section, we prove that relaxing to representative generatability in the limit expands the set of feasible A's in two ways: (1) allowing overlapping groups instead of disjoint partitions, and (2) permitting countably infinite sets of groups under a finite support assumption (defined below).
Definition 4.5 (Critical Hypothesis). Given an enumeration of H. hi h2, .q., we say that hypothesis hy is critical at step if n S <t, hn is consistent with the samples seen thus far, i.e. {#1...., . S supp(h,,), and for every i << n with [f1,....,) C supp(h:), we have hh) C (hp)
We maintain that X C U A..
Definition 4.1 (Finite Support Size). For any hypothesis : X + {0, 1} and collection of possibly overlapping groups A, we define h's finite support size with respect to
Given any countable H. the generator constructed by Klein- herg & Mullainathan (2024) works as follows: at time step t
7

---

Representative Language Generation
the generator finds the critical hypothesis hy with the largest index j S i, and outputs arbitrary unseen element from that hypothesis's s support. The correctness of their algorithm follows from key property of the true language:
/ from the right-most a-feasible and critical language guar- antees both consistency and representation after t". Thus, our generator satisfies representative generation in the limit.
With the building blocks of Lemmas 4.6 and 4.8 in place. the proof of Theorem 4.4 follows as described in the proof sketch. The formal proof can be found in Appendix D.3.
Lemma 4.6 (Kleinherg & Mullainathan (2024), Claim 4.3). Given any countable H
hyy..... and enumeration Ii, F2,,.. of some h E H. there exists timepoint t E N such that h is critical for all timesteps s 2 t.
4.1. Barriers to Achieving Representative Generation in the Limit with only Membership Queries
By the definition of a critical language, if h is critical, then the critical hypothesis hj with the largest index at step t must satisfy shpp(h,) S supp(h). Thus, any point output by the generator after step t must be consistent, as it comes from a subset of the true language.
Thus far, we have considered representative generatabil- ity only in an information iioommation-thhorttic sense, without regard for the amount of computation required by our generators. However, Kleinberg & Mullainathan (2024) provide an inter- esting positive result: any countable H can be generated in the limit with generator that only requires a finite number of membership queries of the form "x E (h)p(h)?" ?" for any h E H at each timestep. In contrast to this positive result, Charikar & Pabbaraju (2024) show that no algorithm us- ing only membership queries can be used to non- con-uniformly generate for all hypothesis classes of size two.
While sufficient for generating in the limit, this last line of reasoning exposes an obstacle in satisfying group rep- resentation: while hy is guaranteed to be a subset of the true hypothesis's support, (hpp could consist of only elements from single group, even if the true hypothesis's ' support and the data stream thus far are more diverse. Thus, we will need to ignore some critical hypotheses that do not allow the possibility of representative generation. We define a feasible hypothesis be an h that admits a distri- bution over its unseen elements that approximates the group proportions in the empirical distribution:
With these results in mind, it's natural to ask whether rep- resentative generation in the limit can also be achieved by an algorithm that uses only a membership query oracle. In this new setting where we care about representation as well as consistency, it's natural to assume we can make queries about both group and hypothesis membership. i.e. ask ques- tions of the form "x E supp(h)?? or "x E A₂?" for any h E H or A, E A.
Definition 4.7 (Feasible Hypothesis). Given hypothesis h2 E H. we say that h4 a-feasible at step / if there exists a distribution μ over unseen data points in (h+) "e., 21} such that || Alel S a.
We show that unlike in the standard setting of generation in the limit, the additional representation constraint poses a sig- nificant barrier to generating with only membership queries. This negative result is with respect to the generation in the limit setting, while Charikar & Pabbaraju (2024)'s 's negative result holds only in the stronger non non-uniform generation set- ting without representation. However, both proofs revolve around a similar obstacle: with only membership queries to single groups or single hypotheses, it's difficult to know whether the intersection of a group and a hypothesis's 's sup- port (or in the case of Charikar & Pabbaraju (2024), the intersection of the supports of two hypotheses), contains infinitely many elements, or finitely many.
Note that even the true hypothesis h may not be ee-fesible given timestep. However, like criticality, we can show that there exists a timestep d E N such that for all 2 d, h must be feasible:
Lemma 4.8. Consider any countable, UUS, H S 1) and countable collection of possibly overlapping subsets A = {Ai)ien and assume H has finite support with respect to A. Let I1, D2.... be an enumeration of supp(h) (h) for some h E H. Then, for any a > O, there exists a d E N such that for all s 2 d, h is a-feasible at timestep s.
We prove this lemma in Appendix D.2. By definition, the feasibility of a language guarantees that there exists a distribution /s over unseen elements that satisfies the a- representative requirement. Thus, we can tweak our algo- rithm to only consider the critical and feasible hypothesis hy with the largest index j < t. Combining lemmas 4.6 and 4.8, we can guarantee that for any a 0 there exists some finite point L' = max (d, () such that for all 2 I", the true hypothesis h is both critical and a-feasible. Thus, for all 2 t" at least one such feasible and critical language exists, and by the same reasoning as before, we must have sh,p S (h),(h), and so outputting an a-representative
The following lemma shows that no algorithm that works even just for very simple, finite pairs of H. and A can gener- ate in the limit with representation using only membership queries. The proof proceeds by contradiction, assuming the existence of such generator. We then analyze its behavior to construct an enumeration that forces the generator vi- olate either consistency or representation at each timestep. The complete proof, along with an extended discussion of special cases where representative generation with member- ship queries is feasible, is provided in Appendix D.4.
8

---

Representative Language Generation
Lemma 4.9 (Impossibility of Generating with Group Con- straints with Only Membership Queries), For any < 1/2, there cannot exist (deterministically computed) random- ized generator that satisfies a-representative generation in the limit for any UUS hypothesis class H = {hi and finite partition of X, A = {A1, A2), and uses only a finite num- ber of membership queries of the form "x E supp(h)?" or "r E A,?" for h E H. and i E {1,2] at each step.
all finite and countable classes are representative uniformly and non-uniformly generatable, respectively. In the case of representative generation in the limit, however, our positive results extend to a much richer class of group collections: any countable collection of possibly overlapping groups sat- isfying the finite support assumption. Lemma 4.3 shows that in full generality, this finite support assumption is necessary for representative generation to be possible. However, this still leaves large gap between the collections of groups we show are uniformly and non-uniformly generatable with rep- resentation (finite partitions) vs. the collections of groups we can show are generatable in the limit with represen- tation (countable overlapping groups with finite support). This raises the question of whether this gap can be closed: are all finite and countable classes representative uniformly and non-uniformly generatable respectively if H has finite support with respect to A? If not, what are the minimal assumptions that need to be placed on (H, A) so that all finite and countable H. are representative uniformly and non-une non-uniformly generatable, respectively? More generally, what characterizes representative uniform and non-uniform generation when groups may be overlapping?
5. Discussion and Future Directions
In this paper, we introduced and analyzed the concept of representative generatability, which extends the theoreti- cal framework for generation introduced by Kleinberg & Mullainathan (2024) and Li et al. (2024). This novel prop- erty ensures that the outputs of generative models closely approximate the proportions of certain groups-of oopos-of--nteestt in the training data. We provide complete, information- theoretic characterization of which combinations of hypoth- esis classes and groups are uniformly and non-uniformly generatable with representation. In addition, we study repre- sentative generatability in the limit from both information- theoretic and computational perspectives. Notably, we demonstrate that, unlike the case of non-representative gen- eratability in the limit, membership queries alone are insuf- ficient for computable algorithms to achieve representative generation in the limit.
Representative Generation with Dynamic Groups. Our model of representative generation considers a fixed collec- tion of groups AA. However, in practice, group membership may evolve with time, with existing groups growing and shrinking in size, different features signaling membership in particular groups, and even some new groups forming. We leave it as an important direction of future work to extend our characterizations and study of representative generation to the case where there exists a nime-indezne collection of groups A₁, Ag................... capturing the fact that in practice, group memberships may evolve with time.
Our additional constraint of representational generation highlights key tensions and possibilities between the pos- itive results of Kleinberg & Mullainathan (2024)'s model and real-world approaches to generation. Specifically, while real-world approaches typically aim to develop generative models that closely approximate training distributions- -nd it is indeed natural to expect our generations to resemble training data in certain alpects-Kleinberg & Mullainathan (2024)'s notion of generation in the limit imposes no require- ment that generated data must resemble previously observed data, only that it must belong to the true language. Our work iintriion---tt---innie framework while intro-
Representative Generation Beyond the Supremum Dis- tance. In this paper, we quantified the quality of group representation of a generator's outputs via the supremum distance between the empirical probabilities over groups and the induced group probabilities of the generator's output. However, there are other natural ways of enforcing group representation. For example, one could consider swapping the supremum distance with the fidiittacce between group probabilities, or some other notion of distance that is more appropriate for a particular application in mind. We leave the study of generatability under these alternate notions of group representation as a important direction of future work.
maintains the ducing an additional constraint: generations must resemble training data with respect to simple statistical tests mea- suring the prevalence of certain subpopulations. Arguably, our notion of representation is useful to formalize even a practical setting, as it addresses an important consideration: generative models can potentially under- or over-represent certain subpopulations, even when they demonstrate good overall alignment with the training data. There are still sev- eral directions of future work, three of which we review below.
Impact Statement
This work introduces a theoretical framework for represen- tative generation in machine learning models, addressing critical issues of bias and lack of diversity in generative model outputs. By requiring proportional representation of
Representative Uniform and Non-uniform Generation of Groups. In Sections 3.1 and 3.2, we show that for all finite A that form a partition of X,
for Richer Collections

---

Representative Language Generation
different groups from training data, our approach aims to mitigate risks of underrepresentation and promote more fair and inclusive Al systems.
Gallegos, I. O., Rossi, R. A., Barrow, J., Tanjim, M. M., Kim, S., Dernnncour, F., Yu, T., Zhang, R., and Ahmed, N. K. Bias and faimess in large language models: A survey. Computational Linguistics, pp. 1-79, 2024.
The implementation of representative generation could help reduce societal biases perpetuated by Al systems, potentially leading to more equitable outcomes in machine-learning aided decision-maiee makking processes such as hiring or content recommendation. It may also enhance the utility of gen- erative models by ensuring they capture a wider range of perspectives and experiences.
Gold, E. M. Language identification in the limit. Informa- tion and control, 1065):447-474, 1967.
Goodfellow, I., Pouget-Abadic J., Mirza, M. Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial networks. Communications of the ACM, 63(1 139-1144, 2020.
However, risks exist. Defining and categorizing groups for representation could introduce new biases or oversimplify complex social dynamies. this work is theoretical, prac- tical implementation will require careful consideration of these ethical implications.
Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. Omnipredictors. arXiv preprint arXiv:2109.053e0 2021.
Gopalan, P., Reingold, O., Sharan, V., and Wieder, U. Mul- ticalibrated partitions for importance weights. In Interna- tional Conference on Algorithmic Learning Theory, pp. 408-435, PMLR, 2022.
References
Angluin, D. Finding patterns common to a set of strings. In Proceedings of the eleventh annual ACM Symposium Theory of Computing, pp. 130-141, 1979.
Hébert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. Multicalibration: Calibration for the (computationally identifiable) masses. In International Conference Ma- chine Learning, pp. 1939-1948. PMLR, 2018.
Angluin, D. Inductive inference of formal languages from positive data. Information and control, 4572):117-135, 1980.
Kalavasis, A., Mehrotra, A., and Velegkas, G. Characteriza- tions of language generation with breadth. arXiv preprint 1rXiv:2412.185533 2024a.
Arjovsky, M., Chintala, S., and Bottou, L. Wasserstein gen- erative adversarial networks. International conference on machine learning, pp. 214-223. PMLR, 2017.
Kalavasis, A., Mehrotra, A., and Velegkas, G. On the limits of language generation: Trade-offs between hallucination and mode collapse. arXiv preprint arXiv:2411, 211062211. 2024b.
Bartlett, P. L., Long, P. M., and Williamson, R. C. Fat- shattering and the learnability of real-valued functions. In Proceedings of the seventh annual conference on Com- putational learning theory, pp. 299-310, 1994.
Kearns, M., Neel, S., Roth, A., and Wu, Z. S. Preventing fairness gerrymandering: Auditing and learning for sub- group fairness. In International conference on machine learning, pp. 2564-2572. PMLR, 2018.
Bender, F. M., Gebru, T., McMillan-Major, A., and Shmitchell, S. On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM conference on fairness, accountability, and trans- parency, pp. 610-623, 2021.
Kirk, H. R., Jun, Y., Volpin, F., Iqbal, H., Benussi, E., Dreyer, F,, Shtedritski, A., and Asano, Y. Bias out-of-the- box: An empirical analysis of intersectional occupational biases in popular generative language models. Advances in neural information processing systems, 34:2611-2622 2021.
Bousquet, O., Hanneke, S., Moran, S., Van Handel, R., and Yehudayoff, A. theory of universal learning. Pro- ceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 532-541, 2021.
Kleinberg, J. and Mullainathan, S. Language generation in the limit. arXiv preprint arXiv:2404.0677 2024.
Charikar, M. and Pabbaraju, C. Exploring facets of language generation in the limit. arXiv preprint arXiv:2411.1536 2024.
Li, J., Raman, V., and Tewari, A. Generation through the lens of learning theory. arXiv preprint 4rXiv:2410.13714, 2024.
Dwork, C., Kim, M. P., Reingold, O., Rothblum, N., and Yona, G. Outcome indistinguishability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1095-1108 108, 2021.
Mei, K., Fereidooni, S., and Caliskan, A. Bias against 93 stigmatized groups in masked language models and down- stream sentiment classification tasks, In Proceedings of
10

---

Representative Language Generation
the 2023 ACM Conference on Fairness, Accountability, and Transparency, pp. 1699-1710, 2023.
Rakhlin, A., Sridharan, K., and Tewari, A. Online learning via sequential complexities. Mach. Learn. Res., 16(1):
155-186, 2015.
Sheng, E., Chang, K.-W., Natarajan, P., and Peng, N. The woman worked as babysitter: On biases in language generation. In Proceedings of the 2019 Conference on Em- pirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNLP-IJCNLP), pp. 3407-3412, 2019.
Sheng, E., Chang, K.-W., Natarajan, P., and Peng, N. So- cietal biases language generation: Progress and chal- lenges. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Pro- cessing (Volume 1: Long Papers), pp. 4275-4293, 2021.
Thanh-Tung
Tung, H. and Tran, T. Catastrophic forgetting and mode collapse in gans. In 2020 international joint confer- ence on neural nelworks (ijenn), pp. 1-10. IEEE, 2020.
Wang, P., Xu, D., Fan, Z., Wang, D.. Mohan, S., landola, F, Ranjan, R., Li, Y., Liu, Q. Wang, Z., al. Taming mode collapse in score distillation for text-to-3d generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9037-9047, 2024.
Zhou, M.. Abhishek, V., Derdenger, T., Kim, J., and Srinivasan, K. Bias in generative ai. arXiv preprint arXiv:2403.02726, 2024.

---

Representative Language Generation
A. Related Works
We highlight few existing notions that are closest to our work.
Language Identification and Generation. In his seminal 1967 paper, E Mark Gold introduced the model of "Language Identification in the Limit" (1967). In this model, there is a countable collection of strings U and a language family L= I2,,,., where each L, S U. An adversary plays a sequential game with player over rounds indexed by / E N. Before the game begins, the adversary picks a language K E C and an enumeration w1; W2,,.. of the strings in K, with possible repetitions. In each round t E N, the player observes the string wt K, and outputs index it. The goal of the player is to eventually "identify" the language K by eventually outputting indices in such that L., = K. More formally, the player has identified K in the limit if there exists an E N such that L., = K for all t 2 s. The family L is identifiable in the limit, if every language K E L is identifiable in the limit. Gold proved that while all finite language families L are identifiable in the limit, there exists simple countable language families where this is not the case. Following this work, (Angluin, 1979; 1980) provides a precise characterization of which language families are identifiable in the limit, further emphasizing the impossibility of language identification in the limit.
I.,,..
Very recently, Kleinberg & Mullainathan (2024) revisit the Gold's model of Language Identification in the Limit with twist: suppose in each round & E N, the player is not asked to output the index of K, but rather a string v E U with the hope that á E K' [ww,.... . }. Naming this setting "Language Generation in the Limit", Kleinberg & Mullainathan (2024) show a surprisingly different result. Unlike the case of identification, Kleinberg & Mullainathan (2024) show that all countable language families are generatable in the limit. In a follow-up work, Li et al. (2024) extend Kleinberg & Mullainathan (2024)'s s results beyond language generation in the limit by (1) re-framing the problem in terms of a binary hypothesis classes defined over a countable example space (2) defining new, stronger models of generation termed uniform and mon--niform generation and (3) formalizing an abstract, prompted version of generation. In this paper, we mainly adopt the notation and models of generation from Li et al. (2024). In addition, we highlight connections between representative generation and the model of prompted generation introduced by Li et al. (2024) in Appendix B.
In addition to Li et al. (2024), there have been several follow-up works to Kleinberg & Mullainathan (2024) that study both consistency and breadth in language generation in the limit. We review the consistency results of these papers here, and defer discussion of their results on breadth to the next section. Concurrently with Li et al. (2024), Kalavasis et al. (2024b) study generation in the stochastic setting, where the positive examples revealed to the generator are sampled i.i.d. from some unknown distribution. In this model, Kalavasis et al. (2024b) quantify the error rates for generation with consistency according to the universal rates framework of Bousquet et al. (2021). Charikar & Pabbaraju (2024) study several facets of language generation. First, they show that all countable classes satisfy the stronger property of non- tn--unfform generation. Then, they show a hardness result - the stronger setting of non-uniform generation is not possible using only membership queries. This is in contrast to generatability in the limit, where Kleinberg & Mullainathan (2024) show that every countable class is generatable in the limit using only membership queries. Lastly, Charikar & Pabbaraju (2024) characterize which classes are uniformly generatable when additional feedback is available.
Language Generation with Breadth. In their original paper, Kleinberg & Mullainathan (2024) formally describe a tension between consistency and "breadth," " defined as "producing outputs that represent the full range of valid outputs in some reasonable way." This observation has prompted several follow-up studies proposing and examining various definitions of breadth. Charikar & Pabbaraju (2024) introduce the notion of "exhaustive generation," while Kalavasis et al. (2024b) and Kalavasis et al. (2024a) explore three potential definitions: "generation with breadth." " "generation with approximate breadth," and "unambiguous generation." Although these notions differ slightly, they all essentially require that the generator's 's outputs cover nearly (or exactly) the entirety of the true language in the limit. Both sets of authors demonstrate an inherent tension between consistency and breadth, as theorized by Kleinberg & Mullainathan (2024). Notably, Kalavasis et al. (2024b) show that the strongest notion, "generation with breadth" is as difficult as identification in the limit.
Our notion of representative generation can be contrasted with these definitions of breadth as both stronger and weaker along different axes.
On one hand, representative generation can be viewed as a relaxation of generation with breadth. While it requires the generator to produce diverse outputs with respect to group membership, it doesn't 't demand complete coverage of the entire language. The generator has two key flexibilities: it can ignore groups that appear only in a tiny fraction of the data sequence, and it need not cover the entirety of every group does generate from. These allowances make representative generation less
12

---

Representative Language Generation
stringent than full breadth requirements. Notably, our notion proves much more tractable compared to prior breadth concepts, making it significant relaxation. In particular, Theorem 4.4 demonstrates that any countable collection of languages and countable collection of groups, under a minor assumption, can be generated in the limit with group representation.
On the other hand, representative generation can also be seen as a stronger notion compared to breadth. Previous breadth concepts do not consider how the generated output at each step compares to the data seen thus far. For instance, a valid generator with breadth for our diverse set of animal images might produce all possible animal images in the limit but could do so by generating 1000 cat pictures for every picture of different species. While this approach might achieve coverage in the limit, it would fail capture the diversity of animals seen in the data stream in the short term. Such a generator would lack practical utility,, it wouldn't 't reflect the variety in the input data. Representative generation, in contrast, maintains diversity throughout, offering more immediate value.
Multigroup Fairness. Our notion of o-representativeness is closely related to multigroup fairness notions in the algorith- mic fairness literature that have been studied mainly in the context of prediction, such as multiaccuracy and multicalibra- tion (Hébert-Johnson et al., 2018; Kearns et al., 2018). These notions require that predictor satisfy quality metries like -ecuracy-i--eppeccaaion or calibration not only for the overall population but also for every subset within rich collection of demographic groups. Perhaps closest to our notion is the work of Gopalan et al. (2022), who study notions of multicalibration for distributions. While they focus on the stronger notion of multicalibration for distributions, they do define an analogous notion of "a-multiaccuracy in expectation" for distributions (Gopalan et al. (2022), Definition 9). In their framework, the requirement of an a-representative generator can be equivalently expressed as follows: at each step, the generator must produce distribution that is a-multiaccurate in expectation with respect to both the empirical distribution of points generated thus far and the collection of groups A. Our work, however, diverges from this framework by concentrating on the generative process itself. We explore how group representation can be achieved and maintained throughout the sequential generation of points, in contrast to analyzing the properties of a single estimated distribution.
Outcome Indistinguishabiiiyy. Although presented in terms of group representation, our notion can be reframed in the language of indistinguishabiitt. From this perspective, the goal of representative generation can be interpreted producing generator that is not only consistent in the limit but also, at every step, outputs a distribution indistinguishable from the data seen so far. This indistinguishabiiity is measured with respect to a set of tests, which in our case are precisely the indicator functions for group membership. We see potential in expanding this perspective and extending our results to incorporate richer sets of tests. This direction for future work is particularly promising given the success of related concepts in other domains. For instance, the outcome indistinguishabiliyy framework introduced by Dwork et al. (2021) for the prediction setting has proven to be a powerful notion, enabling powerful guarantees for predictors such omniprediction (Gopalan et al., 2021).
B. Connections to Prompted Generation
Existing works have also explored variants of the generation setting that capture generation tailored to specific prompts at each time step. This concept is referred to as "prompted generation" " by Kleinberg & Mullainathan (2024), and generalized to "multiclass generation" by Li et al. (2024).
Prompted generation modifies the standard generation setting by expanding the representation of a language from binary hypothesis h: X + {0, }} to multiclass hypothesis h X + [k]. At each time step, the adversary provides an element 2x, as well as its associated label h(zz). The generator's 's goal is to generate consistent element with the same label, i.c. an x E X' with Mxx)= = h((zz).
As noted by Remark 5.1 in Li et al. (2024), the multiclass framework could be shaped to be similar to the representative generation setting by selecting a partition A of X' and transforming each h X - {0, 1} into a multiclass hypothesis such that h(x)) = if hzx) and E A,, and 0 otherwise. However, the existence of such a conversion is less clear in the case of overlapping groups. Additionally, whereas representative generation only requires generations that approximate the empirical distribution, prompted generation could require the generator to output an element with a label that has appeared in only a tiny fraction of the data. For this reason, the generation guarantees for these approaches differ in nature. Prompted generation requires a certain number of elements to be seen per group before generating consistently. On the other hand, representative generation offers consistency guarantces that depend solely on the total number of elements seen, regardless of their group membership.
13

---

Representative Language Generation
C. Proofs from Section 3
C.1. Proof of Theorem 3.3
We separate the two directions (necessity and sufficiency) of Theorem 3.3 into two proofs below.
Proof of Necessity in Theorem 3.3. Let be countable, H S {0, 1 be any class satisfying the UUS property, and A {Ai)eN be any countable infinite partition of X. Suppose that (H,, = co. It suffices show that for every generator and d N, there exists d' 2 an H. and a sequence 1 ...... with (2 ....... S supp(h) such that either
(I) for every t where (ai...., ztHl = d", there exists an where
Pr
s supp(h) (sI, (11,,..,,35) 253] <1
B. B.-((a
(2) there exists a & E such that [[9())))4 Tialolloo > a.
To that end, fix generator 9 and a number d E N. Since GC (H, A) = 20, we know there must exist some d' 2 d and a sequence distinct examples ".g. such that either
........... (a) 3i N such that (I1, , za-i n Ai fe1, ................................ Fa 0 and Ti:d" LA(t) >
(b) a N//S| Σ Dies Fi.d (1)) where ii E ( za- nA; fai,...... ............ . = 0].
Consider passing to G the sequence 21....
Ed If
Pr -0
( E (oi,..., xa (.,, 1,
then pick any E such that {oi=- S supp(h) and any completion of the stream 21 Tee .2.... such that {za-+shjen S supp(h) (xi.d }. On the other hand, if
Pr 2 G ((
[ (1),.... xa (.l,....,....... 11
then there must exist h H such that {zi.a C supp(h) while
Pr R ((
( E supp(h) \ (ar:de) }] < 1.
Pick this H and complete the stream like before using this H. To see why such an h E must exist, note that Pra (((aa))))) [ E (zi..... zz )x {.1...., xz- }] 1, then there must exist an & (I1. Fz. 'x {aI...., xz- which (xiad)) puts positive mass on. But because this x (21...., ) { T. }. there must an H which contains V1.d* in its support but not We now show that the selected hypothesis and stream satisfies either condition (1) or (2) in three cases.
Case 1: Suppose on the input Tı, ..... Far, we have that
Pr 2 G (a
[ (o (21,..., ) (fI...., <
Consider the hypothesis h 7l and the stream 21, ...... chosen above for this case. Note that {21, 22, S supp(h) by definition. Moreover, since 11 # xr,,, = d' is the only such time point where (xI,,..,,z)) .....,)))] d', Finally, on round = d 2 t, we have that Pr, (((r..) [a. supp(h) {I < 1, satisfying condition (1).
'An identical proof follows if instead finite partition X.
14

---

Representative Language Generation
Case 2: Suppose on the input Ti, ... wa we have that
Pr 2 (211
( E (Z1 kd-) \ fo1,.... ................................ Fz H
and the input , Tg- satisfies condition (a). Consider the hypothesis h E H. and the stream 21, Ø2.... chosen
above for this case. Note that {Ii, .2,...} S supp(h) by definition. Let i E N be the group satisfying the property in condition (a). Observe that on time point d", we have that [|9(x])))4 - Trallllo 2 Fiala(t) > a because (f1,-... - Fed H \ (I1,...,,2a) n A; 0 and (zn )a puts all its mass on (211--... Fdd )m \ { -.r..... F. ). Thus, condition (2) is met and G violates a-representation.
Case 3: Suppose on the input .., La,, we have that
Pr Bg ((
(āa- E ( Fd-) fai, (a1,..., v..
and the input Ti,.... Fd- satisfies condition (b). Consider the hypothesis h E H. and the stream ø1, 22.... chosen above for this case. Note that {211 T2, S supp(h) by construction. Let t = d' We claim that condition (b) holds, we have TAlool > a. For the sake of contradiction, suppose that [[]((== Tlllallo I a. Then, we have
that [[(())))) that (( (i) I =1)) + a for all i E N/S and (a))))))aa
for all E S, where the latter true by definition of S. If condition (b) holds, it must be the case that [N \ S) co. Thus, we can write:
Σ ((mra)aa(1))== SEN
E g(mra)la()
Σ 3ia x1 + NN/N S/.
EENUS
iENiS
If condition (b) is true, then EieN,s Th. L (1) < < a|N \ S) giving that EIEN ((a))a)la()) 1, contradiction the fact that (Zrr))) La a probability measure (recall that when A a partition of X, the induced group probabilities of any y E AX form a probability measure). Thus, it must be the case that [|((x)))) Fralalloc > a and as in Case 2, g violates a-representation and condition (2) met.
This completes all cases. The overall proof is complete after noting that the generator G and number d E N were picked arbitrarily.
Proof of Sufficiency in Theorem 3.3. Let X' be countable, H C {0, be any class satisfying the UUS property, and A heN be any countable infinite partition of X' Suppose that GC, A) < co for some a > 0. Let == GC, (H, Then, by definition, we have that for every c d and sequence of distinct examples 21, 22, -- Te such that (I1, .2........... zehN # L. both of the following conditions hold true:
(1) maxies T (1) S a and
(2) a [N/S| 2 Σ iES T1:el (i)),
where S Ei .o......... Ie) H A; \ (x1, (Z1,...,,E.) xx]
0}.
We will use this fact to construct an a-representative uniform generator satisfying the properties in Definition 2.9.
Let æ1, ...... be any stream of examples. Consider the following generator G. For each round f until d d+ 1 unique examples have been observed, G computes and plays from any 14 E A such that HelA lA is an a-approximation of the group empirical distribution 7 A. i.e. ||A:|A - T | S a. Note that such a ue is always guaranteed to exist, as we can choose precisely μ -1.-- Suppose on round t*, we have that [=11..... xx- } = d + For all rounds 2 t², checks whether (fI,..., 2x) R = 1. If this is true, then computes and plays from any Pt E AX such that MelA an a-approximation of the group empirical distribution Fr.el A-- Otherwise, G first computes the group empirical distribution T1:4 La(i) and then the set S. = (i E N ( ,I,) R C A; \ (II,,.., 2x 0). If S, = 0, 9 picks E (x1,.... .H) 0 A, (zi,...,., 2x) for all i E N and constructs the distribution E A'' such that ue (z+) = æ (i)) and (x(z) = 0 for all æ E 2') {21, 2..... Otherwise, if S, + U. 9 picks 2; E (z),..., Iz)x (z),... ..,............................. , xx.) for all E N,S, and constructs distribution 14, E AX in the following way. First, 9 picks a measure /¹ :x' [0, 1] such that (1(2)) = Zidd (aii) for all E N \ St and (((x) = 0 for all x E X {21, 22,...) }. At this point, Σ (x) = Eienys (i) and thus, there is still Eies, *1)ela(1)
15

---

Representative Language Generation
amount of to be placed. To complete the distribution, distributes the remaining Σ Eies, 1 ((ii) mass among
{21, #2.... and obtains probability measure Ae A.' such that 0 p4(2;) 3ia ((i) and ExEX 1hr (2t 1. We will prove why this is possible below.
We now show that such a generator is a-representative and consistent after observing d' = (H, + distinct examples. We first prove consistency.
Proof of consistency: Let G be the generator described above. Let h H. be the target hypothesis and 21, P2, ... C (hpp(h) be the stream chosen by the adversary. Without loss of generality, suppose there are at least d distinct examples in the stream and let t* be the first time point such that |TI,..., Lt d We need to show for all 2 tt:
Pr (((())))))
[. E supp(h) \ fxI....,,I, rzm] =
Fix some 2 t². Then, observe that by construction, 9 always picks and plays from a distribution μs E AX' such that supp(u:) C (I))..., \
(ta). Since (x1,...,, T.)H S supp(h), the proof of consistency is complete.
We now prove that G is a-representative.
Proof of o-repreeentaaivvenss: Fix any (not necessarily valid) sequence of examples 1 #2, ........ ..... It suffices to show that for every E N. we have that
[[(())))AA TidlAllo Sa. a.
Let t" N be the smallest time point such that KII,...,, x.. d: By definition, observe that G satisfies representativeness for all t < t* Fix some / 2 1*, There are three cases to consider. Suppose that (#1...., = 1. Then by definition, G plays an a-approximation of æıæelA and hence is a-representative. Suppose that (Z1...., De # T and S. = 0. Then, by construction, 9 picks and plays from a distribution a-representativeness
E AX' such that MelA = IMælA and thus trivially satisfied. Finally, consider the case where (zi,..., * 1 and S. * D. We claimed above that in this scenario, 9 first computes an incomplete measure μá₂ and then distributes the remaining Eies, F1 (1) mass to obtain a probability measure μe such that 0 S pe(zz) (
and Exex (e(x) 1. To see why this possible, first note that since Hæ1,--. ((0i,---. Ht 2 GC, (H,, A) + 1, we know that conditions (1) and (2) hold. Then, consider two cases: (i) LiEs, Aii) >
for all i N Sr. Hence, we can obtain the probability measure μr by adding at most a mass to 21, and then 22, and so on until all of Eies, ( has been accounted for since a IN/S| 2 Eies, ( In case (ii), there must exist an i E N \ S, such that (1) I 1 -iEs, Z (1)..((). Hence we can obtain the probability measure μt, by adding all of the mass of Eies, 3 (1) on 2j since Lies, (i)) S a. The analysis above gives that G plays a measure μr E A'' such that [Pela(t) -1:1 (()) S a for all E N,S, and (i)
and (ii) Eies, FI.llA (i) < a. In case (i), we know that (=:)
1
for all i E S,. However, since [x1,.... ..e. 2 GC, + condition (1) holds and thus maxies, Z1 (a)) S This gives that (pela(() 2a)la((i) & a for all i S, implying that [|(()1.)44 Alloo I a. Since & 2 t", this concludes the proof of a-representativennss and the overall proof.
C.2. Proof of Corollary 3.5
Proof of Corollary 3.5. Let X' be countable, H {0, 1 x be any finite class satisfying the UUS property, and A hek be any finite partition of X. Suppose for the sake of contradiction that GC, = xo for some > 0. Let F = (V: : V C H. V * 0) be the set of all non-empty subsets of H. Since H is finite, F is also finite. We will assign a number to every V E F. In particular, for every V E F, first define and compute:
(0)v = n supp(h).
NEV
Then, let dy be the largest finite number for which there exists 21..... Bdy E (0) such that
(1) maxies T1:dy (i))= > a or
16

---

Representative Language Generation
151) Eies V1:dy La(i)
where = [ 10)v (T1,..., Tdy A - 0}.
We will use the fact that [K] oo to prove that such a finite dy exists for all V F. To that end, fix some V F. Without loss of generality, suppose that [0)vl oc, otherwise, the claim is trivially true (i.e if [0)) < 0o, it must be the case that dv - vl < oo). It suffices to show that there exists d E N such that for every d' 2 d and sequence
,,,..., Fdd E (0) we have that
maxies L1.dd (1) S a and
(2) Eies Liad ((1) & a (K - SS))
where S = {i E [K] A, n (0) \ {xi,.... ] = 0}. To do we need some more notation. First, separate the K
groups into two sets. The set R = ii E K]: IA, (0)vl = 2o contains those groups whose intersection with (0) is unbounded in size. The set R₂ = (i E [K] [4, M (0)vl < oc) are those groups whose intersection with (0) finite. Note that for any 21..... Ld, the groups in R will never appear in S, and so we have that S S R2.. Now, define
p:= max A, n vl
JE
and observe that p < oo because [Ryl < K < co.
We are now ready to show the existence of such d E N. In particular, pick d = Ky and consider any sequence Ti... T1....,22 Fa E v0)v for d' 2 d. In the worst-case, Iı, I1,..., Fa contains A, n (0)v for all E Rg However, for any given i E R2, at most p of the elements from , Za can be from A,. Accordingly, we have that
a Fid La(i) S
S K
Moreover, observe that
S K
Σ TI. A(1) ÉES
S
<a S a(K - 1S1),
where the last inequality is true because the groups form a partition of X' and |S| < K. Accordingly, dy < Ke < 80. Since V E F was chosen arbitrarily, this is true for all such V F. Now, we complete the proof by showing contradiction. Define
d' = max V FJ.
Again, d² < oo because [F] < oo and dy < 0o for all V E F. Because (H,, = oo, we know that there exists 1. 2 d' + 1, and distinct sequence of examples TI,..., 34 such that
Z1: (1)) or (1) max
(2) (5)) EiestHa
where 5 = fi :: (I....., 22) 0 A, \ f x.} = 0}. Take V == H(x,.... xx) and note that (x),... ,,)H =
v... Thus, we have shown that dy. > t 2 d² + 1, which contradicts the fact that d" max(dy E F} since V F. The proof complete, showing that GC,, (H, A) oc.
17

---

Representative Language Generation
C.3. Proof of Corollary 3.6
Proof of Corollary 3.6. Let X' Z be the set of integers. Let H' S 13 be any class that is not uniformly generatable (for example see Lemma 3.9 in Li et al. (2024)). Define
class H _ {0, 1 such that H. f2r + 1(x
supp(h') U 5o h' E H and let A = {N, Zgo Note that A is finite partition of X of size 2.
First, observe that H is trivially uniformly generatable since Supp(h) is not representatively uniformly generatable. For the sake of contradiction, suppose that (H, was representatively uniformly generatable. Then, for every a (0, 1], there exists an a-representative generator 9 and a number d' such that after observing d' distinct examples, the output of g is consistent (see Definition 2.9). Let be such generator for any 1. We will use G in a blackbox manner to construct uniform generator for H!'
Z = cc. We now show that (H,
Consider the following generator G' for H'. On input .1,...,;2 N, g' passes ;1,...;;2 to and receives an representative distribution Pr. G' plays any E sμрр(μu) n N (Z1,...,22) .r if one exists. Otherwise, G' plays any E X. We claim that g' perfectly generates from H'' after observing d' number of distinct examples. To see why, let N E H' and .i,...,II C supp(h') be any sequence such that ( H 2 d". Let h : + {0. 1] be defined as h(x)= = 1( E supp(h') Zgo). Then, h E H. (51,..., S supp(h), and therefore by definition of d' and G, we have that
(I) Precmu [8 E supp(h) \\n o (fi,..., and
(2) ||aelA - 1il4-IraaAlll Allox S a.
Because 21:6 C N and a < 1, in order to satisfy conditions (1) and (2), there must exist an dt E supp(u) fzi..... rt), and hence g", by playing this ét, perfectly generates on round l. Since / E N and .i,... Iy were chosen arbitrarily, we have that G' is a uniform generator for Ht which contradicts the fact that H' was chosen to not be uniformly generatable.
C.4. Proof of Theorem 3.7
We separate the two directions (necessity and sufficiency) of Theorem 3.7 into two proofs below.
Proof of Sufficiency in Theorem 3.7. Let A' be countable, H C {0, 1 be any class satisfying the UUS property, and A = (Ae be any countable partition of X
Fix some a O. Suppose there exists a non-decreasing sequence of classes Hi H2 S such that H U H. and (H,, A) is a-representative uniformly generatable for all N. Then, there exists a-representative uniform generator G, for each (H,, For every E N, let n, be the number of distinct examples that Gi needs to see before it is consistent (i.e. n, is the d' in Definition 2.9). Observe we can assume without loss of generality that n1, 72..... is non-decreasing sequence by using the a-representative uniform generator constructed in the proof of Theorem 3.3.
We will now use G1, G2.... to construct a a-representative non non-uniform generator Q. To that end, let T X2 be any stream of examples. Consider the following generator Q. On time point N, Q first computes the number of distinct examples de- := | } in the stream far. Then, computes
i max (i E [1] n4 S de) (1)
and plays Pú, (21...., .r)). the output of G, on input .1...., Zt.
We now show that Q is a-representative non-uniform generator that satisfies Definition 2.11. Let start by proving that Q is a-representative. Z1, be any (not necessarily valid) stream of examples. It suffices to show that for every t E N, we have that [[Q((1:)] - Tralalloo I a. Recall that Q(x = Gi, (Z1...., v1). Since G, is an a-representative generator for A), it must be the case that
19 (Zn.)A FEAAA aa.
We now complete the proof by establishing the consistency guarantees of Q. To that end, let h E H. and 2 x2, be the hypothesis and stream picked by the adversary. Let j E N be the smallest index such that h Hy. and let
... C supp(h)
18

---

Representative Language Generation
d' max (J", ny-). J. We claim that Q is consistent after observing d' unique examples. To see why, suppose without loss of generality that 2 22 contains at least d' distinct elements and let &* be the smallest time point such that HæI,...,,Z* }1 d². We need to show that for all 2 t", we have that Q [+, supp(h) (xI...., TsY! = 1. Fix some s 2 ta Then, observe that d, 2 Rij and t* 2 j" Accordingly, we have that i, 2 j and hence h E H., Since ni, I ds. we also know that
[. E supp(h) \ 2, 9. (#1s))
Pr
=
Finally, since (Zx1s)) Gi, (211:) by construction, have that Q is consistent on round Since 2 t" is chosen arbitrarily, this is true for all such 8, completing the proof of consistency and the overall. proof that Q is an a-repressenattvee non-uniform generator for (H, A).
Proof of Necessity in Theorem 3.7. Let X' be countable, H S (0, 1)x be any class satisfying the UUS property, and A = {Ai]ee be any countable partition of X' Suppose that (H, A) is representative non-uniformly generatable. We need to show that for every a > O, there exists a non-decreasing sequence of classes H4 S H2 S ... such that H = U H4 and (H, is o-representative uniformly generatable Vi E N. To that end, fix some a > If H is representative non-uniformly generatable, then for this error level a, there exists a-representative non-uniform generator g. For every H. let da N be such that for any sequence F2, ... with {2,, , .... C (h)p if there exists t E N where HxI...., Ze }1 dn then G is consistent from t*. Now, define H, := {h E H. da i} for all i N. Note that Hi S H2 5 ... and that U Hi = H. Finally, observe that G is an a-representative uniform generator for Hi, and hence, (H;, A) is a-representative uniformly generatable.
C.5. Proof of Corollary 3.8
Proof: Let X' be countable, H S (0, 1)x be any countably infinite class satisfying the UUS property, and A = (A,)ie be any finite partition of X. Fix some a > 0. By Theorem 3.7, it suffices to show that there exists a non-decreasing sequence of classes Hi S H2 S ... such that H = U H. and (H4, A) is a-representative uniformly generatable v E N. Let h1, hg. be any enumeration of H. Define H. = {hi..... h for all i E N. Observe that H₂ S H2 S ... and that H = _ H4. Finally, since [H,l = i < co and |A| < co, by Corollary 3.5, we have that (H,, is a-representative uniformly generatable. Since representative non-uniform generatability implies representative generatability in the limit, our proof is complete.
D. Proofs from Section 4
D.I. Proof of Lemma 4.3
Proof of Lemma 4.3. Select any 0- < a < and let 7 [hh, where supp(h) = X (note that this H is trivially generatable in the limit if we do not require group representation). Consider any arbitrary enumeration of supp(h), u1, U2, with each u, distinct. Define countable partition of X, A A2. such that for each E N,
k Sj
k }
A
U
A==
k=
Clearly this is a valid partition as all groups are disjoint, and because I-a > 1 by definition, for every uy, there exists an i N such that Di=O
- كj < Ei
(
Note that for each E N,
)
b
i-1
b 11-a)
A = |A supp((h)
Σ
Σ
(1- 11-a
0=0
0=
Choose U1, U2, be the enumeration of supp(h) selected by the adversary. Consider any E N, and note that at step
t= Σ==
1 1, all elements of A, have been exhausted, and supp(h) n n.A: \ (xI,.... v.) = 0. Moreover, A, takes
[-a
19

---

Representative Language Generation
up more than a-fraction of the distinct elements seen thus far, Frala can be lower-bounded
A n
F1al
Σj j=0
I-o
1-o
formula for sum of geometric series
(T
1-1-
++1
1-a
1-a
1-x
1-a
I-a
This implies that in order to be representative, the generator must output distribution f4, that puts positive mass on some x E As, otherwise
(mrla(1) Iia IIa (A)) FT > a.
However, because all elements of A, have already been exhausted in the sequence, the generator must either violate consistency by putting mass on A; that has already been seen the sequence, or violate representation by putting mass A; despite appearing in greater than o-fraction of the sequence. Thus, the generator cannot satisfy both consistency and representation simultaneously at this timestep (in fact, it cannot generate correctly from any of the groups that have been seen so far).
This happens for each A, and thus any generator must make infinitely many mistakes at timesteps Σj= every i E on this sequence, and thus it cannot satisfy the requirement of representative generation in the limit.
( 1-o
1 for
D.2. Proof of Lemma 4.8
Proof of Lemma 4.8. We introduce the notion of a group vector v(x) E 13 \ (0*), which given X, indicates an x's group membership in all groups in A, with v(z); = 1|x E A:].
Recall that fr.A denotes the finite support size h with respect to A (Definition 4.1), which by assumption satisfies fn,A < oc. We can equivalently write the definition of fh,, terms of group membership vectors, i.e.
Jn
Σ
n VEN,,;11
A suppp(h)))
" fo IneeNomm (h)
Let v C (0, 11 {0*} be the subset of all group membership vectors with finite support, i.c v {0, 13 \ (00) such that
A suppp())
<c.
The remainder of the proof follows in three key steps:
1. We first show that after enough timesteps, the proportion of the data sequence taken up by unique elements with group membership lying in V must shrink to very small quantity and stay below that amount. In particular, less than a/2.
20

---

Representative Language Generation
2. Next, we show that due to how little mass is placed on these vectors, it's possible construct distribution that a-approximates the empirical group probabilities, but places mass any with e(ar) V.
3. It follows that h must be feasible at this point, because all other group vectors have infinite support when intersected with sup.
Step 1: V takes up small proportion of of the empirical distribution. Consider the timestep & at which point the sequence has included d² 2 unique elements. For any 2 t, the proportion of elements in the empirical distribution with o(x) E V is upper bounded by
a
fnA d=
a/2.
Thus, for all 8 2 f, the total proportion of unique elements from V in the sequence must be at most 0/2,, as desired.
Step 2: Constructing an a-approximate distribution that ignores V. We now show that for all s 2 t, because we are guaranteed that the total proportion of unique datapoints from V is at most a/2, group probabilities a-approximate Fi:elA and places mass on any x with v(x) V. For what elements the distribution uses, and just care about their group membership vectors. We construct a distribution over these elements as follows:
construct distribution whose
will ignore exactly
(x) E V or x & T1:s
(x(
Tl:o
otherwise
Clearly by definition n, places no mass on any x with v(x) E V. remains to show that this is actually a valid approximation,
ie || - TAllo S a.
To this end, consider any A E A. We rewrite the proportions of A, appearing in n., and the empirical distribution:
(1) T1:5 A(i)
PEENzi (u(x) E V]
< Pr [x E A,, v(x) V]
Pr [ A,, o(x) $ vl
Pr (T(I) E V
$ Pr (o E A,, v(x) E + Prawei 1n (V(I) E V]
Pr [u(x) V godii
Pr Pra [v(I) E Vl
< 2 Pr [v())
aa
guarantee from Step
Thus, because this holds for any A,, conclude that TalA a-approximates T1:2lA-
Step 3: Constructing a feasible distribution. Ta passes all group representation requirements, but is not quite what we want, because supp(=.) is supported on previously seen points in Ti:e, whereas we want a distribution supported on supp(h) F1.a- Note that it suffices for every x E supp(x,, we can find an x' E supp(h) \ #iss such that u(x) = u(x'). Then, the distribution μ4 defined as μ. (x') n. (z) would exactly match the group vector proportions of ng and thus also satisfy ||
Ii:s |ll as well supp(u.) C supp(h) F1:s-
This is in fact easy do, note that by construction, for every supp(T=)). we must have v(x) & V, and thus
A suppp))))) = xc.
,EN,
This means that even after removing Ti:s, there are infinite number of x' that we can choose from to replace for each E s..
Thus, putting all these steps together, we conclude that at the finite timestep E N after we have seen 2fr. unique elements, for every s 2 t we can find a distribution μa with supp(p.) S supp(h) \ 2i and ||aaaa - T1selalles S a. Thus, is ee-aeaiblee for all 2 1, completing the proof.
21

---

Representative Language Generation
D.3. Proof of Theorem 4.4
Proof of Theorem 4.4. Choose some a 0, and consider the following mapping from a sequence of examples 11, Tt. 1o distribution over X::
1. Given examples 21, Tt, let C. S (/,,...,
}
be the set of critical hypotheses at step t.
2. Let F S C2 be the subset of critical hypotheses that are also a-feasible.
3. if Pt is empty, output the distribution (4: = Tlit-
4. Otherwise, let ha E Fe be the hypothesis in F. with the largest index n. S t. Output the distribution J4r over supp(h,)) \ Zia that witnesses hn 's a-feasibility.
We now show that the generator 9 that follows this mapping and outputs jst at step & for all E N satisfies representative generation in the limit. To do this, we need to verify that G is a-representative, and for any enumeration 21, 22, ... of an h E H and there exists some t" E N such that G is consistent after timestep t".
Property 1: o- a--eeprsentative. We first show that the generator's output is representative at every t E N. This is trivially true G outputs f4 = Tie at Step 3, and by the definition of a-feasibility, the he output at step also a-approximates the empirical distribution of groups. Thus, in either case the pr output satisfies the representation requirement. Because this holds true for any datastream 21, T2, ... conclude that G is a-representative.
Property 2: Consistent. It remains to show that there exists some (* E N such that for all 8 2 1t, supp(u.) C
supp(h) Zi:s- Let t E N be the timestep guaranteed to exist by Lemma 4.6 such that for all 2 t, h is critical hypothesis, iee. E C.. Let d E N be the finite timestep guaranteed to exist by Lemma 4.8 such that for all s 2 d, is a-feasible. Let t" = max (d t}. It follows that for all s 2 t", we have E F,, as it is both critical and a- feasibll..
Thus, for any timestep s 2 t*, we are guaranteed that F, is non-empty. and Pa guaranteed satisfy supp(u,) S supp(h>n) Ti where ha2 E F2 is the hypothesis with the largest index < t. It follows from the definition of a critical hypothesis that must have supp(h,,) supp(h), and thus μı satisfies consistency.
Thus, we have shown that G as described above is an a-representative generator and is consistent for all s 2 t", and thus because > 0 was chosen arbitrarily, we conclude that (H, AA) is generatable in the limit with representation.
D.4. Proof and Discussion of Lemma 4.9
Before providing the proof of Lemma 4.9, we provide some additional discussion of the result and comparison to the positive result of Kleinberg & Mullainathan (2024).
The algorithm of Kleinberg Mullainathan (2024) that generates the limit using only a finite number of membership queries each step crucially relies on the UUS assumption, in particular the fact that finding an element from supp(h) ) Iis always possible because (supp(h)] = co, and thus one can simply enumerate the elements of X' until an unseen point encountered. In the case of representative generation, however, a generator may need to generate from (supp(h) n.A, \ 2ia. which is not always guaranteed to be infinite, making this problem lot more difficult. We note that in the case where A partitions X, if we made the strong assumption that supp(h) n A, is either empty or has infinite size for all A, E A and h E H. then this would be similar to the assumption made by Kleinberg & Mullainathan (2024), and we could use membership queries to generate with representation using an algorithm almost identical to their membership-query algorithm.
However, the Lemma 4.3 shows that weakening this assumption to allow for groups with finite intersection with hypotheses in H introduces some inherent difficulty. In particular, no algorithm that works even just for very simple, finite pairs of H. and A can generate in the limit with representation using only membership queries.
With this in mind, we present the proof below.
Proof of Lemma 4.9. Consider a deterministically computed randomized generator 9 that at step t, sees examples Zi, and can make queries of the form "x E supp(h)" or "x E A₁?". Note that because we only have two groups making up the partition, querying about Ag as well can provide no extra information.
22

---

Representative Language Generation
Assume for contradiction that at each timestep the generator makes a finite number of such membership queries before outputting its generated distribution 14, and satisfies representative generation in the limit.
We examine the execution of this generator and use it to construct a hypothesis h, partition A, and enumeration 21, 22,22.... of shpp(h) that forces the generator to make infinitely many mistakes. Let U1, U2, .... be an enumeration of X.
We now imagine rumning 9 (this can be run offline prior execution as the generator deterministic) and use the run to build up hypothesis h, an enumeration h1 k.... of supp(h), and disjoint groups A1. A2 with A A2 X.
We introduce some variables for keeping track of our constructed example:
A dictionary H + {-1.0,1} that keeps track of the values assigned for the language thus far, with H(x) = h(x) = 1, H()) = 0 (xx) = 0, and (x) = the value has not been assigned. We initialize H (x) = 1 for all x E.
A dictionary A X' 1, that keeps track of the group membership of each æ (with I and 2 responding to A and A2, respectively, and -1 if x has not yet been assigned), We initialize A(x) -1 for all X.
A list K that will keep track of the enumeration of elements. We begin with K 0
A queue Q. to which we can insert elements and pull them off the queue in a first-in, first-out manner.
Now, at each timestep 1,2, we perform three stages of actions. The first is add to the enumeration, the second is answer the queries of the generator, and the last is to handle the generator's outputted distribution He for that timestep.
Stage 1: Adding to the enumeration. If is odd or Q is empty, we find the smallest 2 1 such that A(u,) = - 1. Such a M4 is guaranteed to exist as uı,... is an enumeration of X, which starts with infinitely many un with A(u,) = - and at each step we will only fix the membership of a finite number such u, Having found this u, we set A(u,) = 1, ((:) = 1, and append it to the enumeration K, so set k; = Ug.
Otherwise, if / is even and is non-empty, we pull element x off of the queue, and append it to K, thus setting kG
Stage 2: Answering G's queries. We now run the generator upon seeing k ......,, ky and answer each membership query as follows.
Every time the generator asks "I E supp(h)?" for some x, if H(x) + 11, and the membership has already been fixed, we output the correct membership value. Otherwise, if (x)) )) = 11 we answer "yes," set ((x) = 1, A(x) = 2, and add it to Q.
Every time the generator asks "r A,?," if A(x) + -1, provide the correct answer that has already been fixed. Otherwise, set A(x) = 2, H (x) = 1, and add it to Q. Note that if A(x) 11, necessarily have H -1
Stage 3: Handling G's output. After finite number of queries, G is guaranteed by assumption to output distribution μr: We make no assumptions about the representation of μı, and thus it could have infinite support.
We perform the following actions depending on the contents of supp(p:):
If there exists x E suрp(μ)) with H(x)
(.1,,.,,,1) do nothing and end execution for the timestep.
If there exists an E supp(u:) with H (x) 1, i.e. has not yet been queried by the generator, we H(x) O.
A(x) 2, and finish execution for timestep t.
Otherwise, note that every supp(u:) has (x) 1, A(x) by definition of our construction.
We repeat these three steps for each timestep. This completes the definition of the construction.
We now verify the necessary facts for this H. enumeration, and group partition to be well-defined. In particular, H = (h} must be UUS and K must be a valid enumeration of supp(h). Clearly, each z can be assigned only one of A(x) = 1 or A (x) 2, so we have valid partition.
23

---

Representative Language Generation
We first consider the UUS property of H. We consider two cases. First, if the generator makes finite number of queries each time step as promised, then {I: E X: (a) -1) will have infinite size at all timesteps, and so every timestep are able to find unseen E X' with (x)) = -1 to add to the enumeration, or pull one off the queue. Because this can be repeated indefinitely, supp(h) will be infinite. On the other hand, if at some finite timestep the generator makes an infinite number of queries, either an infinite number of the queries are on elements with (x) = -1 or A(x) = -1, in which case each these elements get set to H (x) = resulting in an infinite support, or there are only a finite number of such queries, and thus the remaining un un-queried portion of must be infinite, and we can set all of to ((r) = to again get an infinite support. Thus, in all cases supp(h) satisfies the UUS property.
Lastly, we show that K is valid enumeration. First, consider the case where at some timestep t, the generator makes an infinite number of queries. We can follow the assignment of H above to construct a UUS H. and then append any enumeration of the remaining unseen elements with H (x) 1 to K to obtain a valid enumcration.
Otherwise, we can assume that at every step, the generator makes finite number of queries. Clearly by definition of the construction, only elements with (x:) = are added to the enumeration, meaning that Usen (A:) S supp(h). Thus, remains to show that the K covers all of supp(h). Consider any I E supp(h), i.. an X such that there exists some finite timestep at which H (a: is set to I. We will show that there exists some j N such that kj x. Note that because supp(h) S X' and u1.... is enumeration of X, there exists some i N such that u, z. At timestep 2i 1, we have three possibilities.
1 Ug.
1 F uss but there exists a < 2i - such that ki = Mj.
12 f Us, and u, has appeared earlier in the enumeration.
If we are in either of the first conditions, we are done because we have guaranteed that there exists a E N such that ky = x. Note that in the third case, this can only happen because u, currently in the queue. Because at each previous step the generator made finite number of membership queries, the position of u, in the queue must be some finite N. Thus, because even timestep outputs an element from the queue if it is nonempty, thus in all cases there exists j E N such that ky and thus K is a valid enumeration of supp(h).
guaranteed that kgi 22i-142--1 Ug and
Construction of Contradiction. We finally consider what happens when the generator is run on enumeration K with group and hypothesis membership defined by A and H as above. Consider any timestep f, where the generator outputs a distribution fr-
We consider the three cases considered in Stage Note that in both of the first two cases, the generator must violate consistency, as there exists an supp(u,) with æ & supp(h) I.,
Otherwise, the only other possibility is given by the third case, which guarantees that every supp( has A(x) 2, and thus x E A2. This means that the generator is not representative of the data sequence thus far, because by definition of the enumeration, Z1:e (1)) 2 1/2 while μ4 (1)) 0, and thus || A Mela loc 2 1/2 >
Thus, the generator fails to generate consistently with group constraints at every timestep. We thus conclude that the assumption was false, and at some iteration the generator must make an infinite number of membership queries.
24


Reviews:
[{"review_id": "3xWUjZLT9o", "reviewer": "Reviewer_g3vz", "summary": "This paper extends the study of the recent model of language generation introduced by Kleinberg and Mullainathan in a 2024 paper. In this model, this paper defines a notion of representative generation where the generator is roughly speaking required to assign similar probability masses to each group A (from a class $\\\\mathcal{A}$) as is assigned by the sequence of examples provided by the adversary. The paper provides several results exploring when different notions of generation (as defined by Li et al. (2024)) can be achieved with the additional representation constraint.  Their first two sets of results consider the case where groups in $\\\\mathcal{A}$ are disjoint. \n\n1. Their first result is a characterization of representative uniform generation under the disjointness assumption. This characterization builds on a characterization of Li et al. (2024). Next, we list some examples and results complementing this characterization:  \n   1. This characterization, in particular, shows that representative uniform generation is always possible with a finite language collection and finitely many groups.   \n   2. Complementing this, they also show that representative uniform generation is strictly harder than uniform generation (by providing a class that is uniform generatable but not representative uniform generatable with even two groups).  \n   3. Further, they also give another example where $\\\\mathcal{A}$ is countably infinite and where a hypothesis class of size 1 cannot be generatable in the limit with representation (a weaker requirement than representative uniform generation).  \n2. Their second result characterizes representative non-uniform generation under the disjointness assumption. This characterization is identical to the characterization of non-uniform generation by Li et al. (2024) except that one needs to substitute the characterization of uniform generation with that for representative uniform generation.  \n   1. This characterization, in particular, shows that all countably infinite classes with a finite partition  $\\\\mathcal{A}$  are representatively non-uniformly generatable.  \n3. Their final set of results for generation in the limit drops the disjointness assumption, but makes a different “finite support” assumption in Definition 4.2.   \n   1. Their main result for generation in the limit is that any countably infinite class with a countably infinite $\\\\mathcal{A}$   satisfying Definition 4.2 is generatable in the limit with representation.   \n   2. Further, they also demonstrate computational barriers to generation with only membership queries by showing that no algorithm can generate in the limit with representation using only finitely many membership queries even when the hypothesis class has a single hypothesis and there are only two two groups.\n\n**Post-rebuttal Update** Dear authors, thank you for your response and for explaining that the group closure dimension has the finite character property. The rebuttal addresses most of my concerns, I maintain my original rating of weak accept. I do not give a stronger accept as I am not 100% sure about the gap in technical novelty compare to prior work of Li et al.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding that our paper studies an interesting and fundamental learning theoretic model for generation. We address the reviewer's comments/questions below. \n\n> Finite Support Size Assumption\n\nWe can certainly add some examples to clarify the definition. We'll highlight a few simple examples here that we can add to the final version to add intuition for the assumption:\n- As you correctly observe, any collection of finite groups will always satisfy the finite support size assumption. \n- When the collection of groups is infinite and disjoint, the assumption simplifies to the requirement that for any $h \\in \\\\mathcal{H}$, only a finite number of groups have a finite size intersection with $\\mathsf{supp}(h)$. \n- A simple example of a collection of groups that does not satisfy the assumption is any infinite collection of groups where the size of every group is finite, such as the collection of all singletons $\\mathcal{A} = \\lbrace{\\lbrace{x\\rbrace} : x \\in \\mathcal{X}\\rbrace}$, or the collection defined in the proof of Lemma 4.3.\n\n> (Q1) Is there an easy way to check if a hypothesis satisfies group closure dimension? How can one interpret it?\"\n\nLike other combinatorial dimensions (e.g VC and Littlestone dimension), it is likely not possible to efficiently compute the group closure dimension at a fixed scale. That said, the group closure dimension does satisfy what is known as the Finite Character Property [1]:  for every $d \\in \\mathbb{N}$ and class $\\mathcal{H}$, the statement $\\operatorname{GC}_{\\alpha}(\\mathcal{H}) \\geq d$ can be demonstrated by a finite set of domain points in $\\mathcal{X}$ and a finite collection of members of $\\mathcal{H}.$ This property is also satisfied by most other combinatorial dimension in learning theory literature. In terms of interpretation, intuitively, one should think of the group closure dimension as measuring the maximum number of samples one needs to see until they are guaranteed a winning strategy. Here, a winning strategy is one where there exists a distribution over examples which is consistent and representative. It turns out that the group closure dimension quantifies exactly this in a way that does not explicitly require quantifiers over distributions of the example space by exploiting the disjoint nature of the groups. \n\n[1] Ben-David, Shai, et al. \"Learnability can be undecidable.\" Nature Machine Intelligence (2019)\n\n> (Q2) Could the authors shed some light on why it is challenging to characterize or provide sufficiency conditions for uniform and non-uniform generation without the disjointness assumption on ?\n\nThere are several issues that arise when one tries to go beyond disjoint groups.\n- For one, the distribution-free definition of the group closure dimension heavily relies on the fact that the groups are disjoint. Thus, while it is possible to define a version of the group closure dimension for arbitrary groups, it is likely that it will be abstract and not satisfy the Finite Character Property [1].\n- The second issue is that when the groups are not a partition of the domain $\\mathcal{X}$, the vector of induced probabilities (Definition 2.5) is no longer guaranteed to be a probability distribution. For example, consider a sequence of examples $x_1, x_2, ..., x_d$ contained in every group. Any dimension that gives a characterization will likely have to have quantifiers iterating over entire group vectors instead of individual groups. This makes the dimension hard to parse and less meaningful. In addition, with overlapping groups, the dimension will need to take into account arbitrary intersections of these groups, which again significantly increases the complexity.\n\n> (Q3) How are the techniques used in this result different from the techniques of Charikar and Pabbaraju? \n\nWe briefly compare the two proofs in the beginning of Section 4.2, but will provide a more detailed discussion here that we will include in the final version of the paper. \n\nBoth proofs employ the same fundamental approach to construct adversarial counterexamples and prove impossibility: they develop strategies that, given a generator, methodically build an adversarial enumeration that forces the generator to violate its promised guarantee. Charikar and Pabbaraju focus on the impossibility of non-uniform generation guarantees, while our work examines representative generation in the limit. Importantly, without the representation requirement, generation in the limit is always achievable with membership queries, as demonstrated by Kleinberg and Mullainathan [2]. Our adversarial construction specifically exploits the additional representation constraint by carefully designing groups that force the generator to violate either representation or consistency. Furthermore, our setting differs in that we consider generators that output distributions rather than single elements.\n\n[2] Kleinberg, Jon, and Sendhil Mullainathan. \"Language generation in the limit.\" (2024)", "claims_and_evidence": "Yes, the claims in the paper are supported by the rigorous proofs.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "I skimmed the proofs but did not check their correctness.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The paper advances a line of work studying language generation in a model recently introduced by Kleinberg and Mullainathan in a 2024 NeurIPS paper. The present paper introduces the task of representative language generation which has not been considered in other works studying this model of language generation.", "essential_references_not_discussed": "To the best of my knowledge, the paper discusses relevant prior works.", "other_strengths_and_weaknesses": "The paper studies an interesting and fundamental learning theoretic model for generation. The problem they study seems like a natural extension of existing works.", "other_comments_or_suggestions": "I found the Finite Support Size assumption (Definition 4.1) hard to parse. As a sanity check, it seems to make sense in the case where there are finitely many groups. I think it would be very useful to include several (simple) examples where the Finite Support Size assumption holds and when it is violated.\n\nTypos:\n\n1. Line 90 “Representative Uniform Generation,” \\-\\> “Representative Uniform Generation.”", "questions_for_authors": "I have some questions for the authors. The most important ones are Q2 and Q3.\n\nFirst, for the closer dimension introduced by Li et al. (2024), it is relatively easy to certify that a hypothesis class satisfies the definition. In some sense, the definition was “interpretable.” The definition of the group closure dimension (which characterizes representative uniform generation under the disjointness assumption) seems less interpretable, at least as currently stated.  (Q1) Is there an easy way to check if a hypothesis satisfies group closure dimension? How can one interpret it?\n\nI understand that the group closure dimension characterizes the sample complexity of the task, but it was not easy to parse what it means. If there is a better way to state it, that would be very useful for the readers.\n\nMy second question is: (Q2) Could the authors shed some light on why it is challenging to characterize or provide sufficiency conditions for uniform and non-uniform generation without the disjointness assumption on $\\\\mathcal{A}$?\n\nFinally, for the result on computationally barriers with only membership queries. (Q3) How are the techniques used in this result different from the techniques of Charikar and Pabbaraju? Are the techniques the same? If not, can I find a discussion about the differences somewhere in the paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AzxtQ8t1dv", "reviewer": "Reviewer_JWgs", "summary": "This work introduces the concept of \"Representative Generation\" and its variants, aiming to provide a theoretical framework that characterizes generators (i.e. generative models) such that, when the training data distribution consists of multiple groups of interest, the generator outputs closely approximate the proportions of data across the groups. In contrast, prior work proposes the \"generation in the limit\" characterization of generators, where generators can get away by generating from a restricted subset of the ground-truth. While prior work shows that generation in the limit, which is much weaker than representative generation, can be achieved in many scenarios, this paper shows that representative generation is impossible using only a finite number of membership queries, i.e. querying whether  an element belongs to a certain group.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. \n\n> Could you use this example to help clarify, for a non-expert like me, how is \"representative generation\" different from \"generation in the limit\" and how to interpret the negative result (Lemma 4.9) proved in this work?\n\nIn the original notion of \"generation in the limit\" proposed by Kleinberg \\& Mullainaithan (2024) the goal of the generator was to only eventually produce new, valid examples. In our model of \"representative generation\", the goal of the generator is to not only produce new, valid examples, but to produce them in a way that is \"representative\" of the input training data. So now, the goal is not only to produce new, valid examples, but to produce new, valid examples that align with the properties/preferences of the training data. The negative result (Lemma 4.9) shows that if one cares about computability, then representative generation is strictly harder than generatability in the limit -- there are cases where once can produce new, valid examples, but not in a way that aligns with the properties/preferences of the training data. \n\nYou raise a good point that the objective of generation in the limit is somewhat different from the standard objective in practice of minimizing distance to training data. Please see our post to Reviewer U9Ez below (Re: Practical applicability of results) addressing this discrepancy between the theoretical model and practice. \n\n> Could you help clarify what \"at each step\" is referring to in Rather than generating a single element at each step, a representative generator generates a distribution over multiple elements at each step.\n\nIn this paper (as well previous papers in this line of work), we consider a game between a generator $G$ and an adversary $A$. This game is played sequentially over rounds $t=1, 2, \\cdots.$ In each round $t \\in \\mathbb{N}$, the adversary reveals to the generator a new example $x_t \\in X$. Upon observing $x_t$, the Generator must output a new example $\\hat{x}_t.$ In previous works, the generator $G$ was deterministic. In our work, $G$ is randomized and thus produces a distribution $\\mu_t \\in \\Delta X$ after observing $x_t$. So, the \"at each step\" is referring to the rounds $t = 1, 2, ...$ .", "claims_and_evidence": "Yes, to the best of my judgement.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I do not have the required expertise to verify the correctness of the proofs.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "As suggested by the author, the theoretical analysis is relevant to the commonly observed/discussed phenomenon of generative models often exacerbating biases presented in training data.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. One common paradigm for training generative models is to minimize KL(ground-truth | generative model), and in this case, it is impossible for a generative model to get away with generating only cat images when the training data consists of 1/3 cats, 1/3 dogs and 1/3 rabbits. Could you use this example to help clarify, for a non-expert like me, how is \"representative generation\" different from \"generation in the limit\" and how to interpret the negative result (Lemma 4.9) proved in this work?\n2. Could you help clarify what \"at each step\" is referring to in `Rather than generating a single element at each step, a representative generator generates a distribution over multiple elements at each step.`", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H5x6grGiCp", "reviewer": "Reviewer_U9Ez", "summary": "The paper defines a new property of generators called “representative generatability” to provide a theoretical framework for comparing a generator's representation (occurrence) of distinct groups present in the training distribution with the representation in the distribution of output sequences. The contribution is well-motivated with real-world bearing on issues observed in practice in generative systems (like LLMs), such as bias propagation and mode collapse. Results are presented in three settings derived from prior works –– uniform generation, non-uniform generation, and generation in the limit.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Re: Practical applicability of results\n\nThank you for your question. While we maintain that this is primarily a theoretical work, we've addressed how our research may or may not relate to practical applications in our global comment to all reviewers above. We will plan to incorporate more of this discussion in the final version of the paper.\n\nTo clarify our position, our work extends the theoretical model introduced by Kleinberg and Mullainathan, which—along with subsequent research discussed in our introduction—examines generation in a worst-case scenario without making assumptions about data distribution or learning methods. This approach deliberately highlights fundamental tensions and possibilities in generative tasks from a theoretical perspective rather than focusing on immediate practical implementations.\n\nThat being said, our work on representative generation can be viewed as an extension of Kleinberg and Mullainathan's model of generation, aiming to align it more closely with real-world generation approaches and values. Specifically, while real-world approaches typically aim to develop generative models that closely approximate training distributions (as reviewer 2 noted)—and it is indeed natural to expect our generations to resemble training data in certain aspects—Kleinberg and Mullainathan's notion of generation in the limit imposes no requirement that generated data must resemble previously observed data, only that it must belong to the true language. Our work maintains the generation-in-the-limit framework while introducing an additional constraint: generations must resemble training data with respect to simple statistical tests measuring the prevalence of certain subpopulations. Arguably, our notion of representation is useful to formalize even in a practical setting, as it addresses an important consideration: generative models can potentially under- or over-represent certain subpopulations, even when they demonstrate good overall alignment with the training data.\n\nAt a high-level, we view the main contributions/takeaways of our work as two-fold, in the context of existing works on generation:\n1) Our additional constraint of representational generation highlights key tensions and possibilities between the positive results of Kleinberg and Mullainathan's model and real-world approaches to generation. In particular, we show that there are many settings where generation in their model is possible, but becomes impossible when the generative model is additionally required to satisfy representation. On the other side, some of our positive results signal that matching training data makeup is not always in conflict with the goal of generation. For instance, we show that requiring representation with respect to any finite set of groups is no more difficult than just generating in the limit for any countable class $\\mathcal{H}$. \n2) Our work is among a recent line of work attempting to understand the trade-offs between obtaining novelty and breadth in language generation. Like these works, some of our results are negative: if one cares about computability, then achieving novelty and representativeness is impossible. However, from a sample-efficiency perspective, in contrast to the many negative results on generating with breadth, our formulation of representation offers a tractable relaxation of breadth that maintains semantic relevance while remaining feasible across many natural classes of languages and groups.\n\n> Re: Choice of supremum distance \n\nOur selection of the supremum distance draws directly on the foundational principles established in algorithmic fairness literature, which emphasizes the importance of limiting the error experienced by the worst-off group. This perspective prioritizes ensuring good representation for every group rather than merely optimizing for average performance. The supremum distance naturally operationalizes this principle by measuring the maximum disparity across all groups, effectively placing an upper bound on the error that any group might experience.\n\nIt's worth noting that for finite group settings, different choices of distance measures (such as $L_1$, $L_2$, or the supremum distance (L$_\\infty$)) are typically within constant factors of one another, making the specific choice less critical. However, as we move to settings with infinite groups, these equivalences break down—distance measures such as $L_1$ become less informative, potentially obscuring significant disparities among individual groups. \n\nAs we highlight in our concluding discussion, while we selected the supremum distance for its robust guarantees from an algorithmic fairness perspective, exploring representation guarantees under alternative distance metrics is certainly an interesting direction for future research. In our revised paper, we will provide a more thorough justification for our choice of the supremum distance as an appropriate measure of closeness within our framework.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Not applicable since the work is a theoretical contribution.", "theoretical_claims": "My reading of the proofs revealed no errors.", "experimental_designs_or_analyses": "Not applicable since the work is a theoretical contribution.", "relation_to_broader_scientific_literature": "This work directly follows from [1], [2], [3], [4], and [5], and provides a useful new lens that has real-world relevance to current generative systems in practice (albeit with no obvious takeaways for practitioners).\n\n[1] Kleinberg, J. and Mullainathan, S. Language generation in the limit.\n[2] Li, J., Raman, V., and Tewari, A. Generation through the lens of learning theory.\n[3] Kalavasis, A., Mehrotra, A., and Velegkas, G. Characterizations of language generation with breadth.\n[4] Charikar, M. and Pabbaraju, C. Exploring facets of language generation in the limit.\n[5] Kalavasis, A., Mehrotra, A., and Velegkas, G. On the limits of language generation: Trade-offs between hallucination and mode collapse.", "essential_references_not_discussed": "I am not aware of any missing related works that have not been cited.", "other_strengths_and_weaknesses": "**Strengths:**\n\nThe paper focuses on the problem of diverse generation, a topic of high-relevance in practice, and presents a theoretical framework to analyze the problem. Given the abundance of iterative methodological contributions in the area, I think this is a useful contribution for the community to assess the theoretical limits of what we want from such systems.\n\n**Weaknesses:**\n\nWhile I understand that the work is a purely theoretical contribution, given that the motivation uses practical systems (such as LLMs) to establish impact, it would have been useful to present a discussion about what the authors think might be the practical (and immediate, if any) implications of their results.", "other_comments_or_suggestions": "None.", "questions_for_authors": "L205-208: Could you discuss the choice of the supremum distance as the measure of \"closeness\" versus other distances? The choice currently seems fairly unjustified.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "D0i9bleAor", "reviewer": "Reviewer_y5Xy", "summary": "This paper introduces a theoretical framework to characterize generative models’ capacities/abilities to produce samples that reflect the diversity seen in the data whose distribution the model is trying to approximate. Such characterizations are of interest to the machine learning community as they let us quantitatively define whether different groups in the support of the data-generating distribution are properly represented by the model of interest. The paper outlines the criteria by which a generator fulfills different degrees of representative-ness (these build off of definitions given in prior work) and then consider the theoretical feasibility of different models to meet these criteria. They provide information-theoretic bounds and computational bounds (where possible). They present both positive and negative results for whether representative generation can be fulfilled for different generator–hypothesis class pairs (e.g, that for a certain hypothesis class + alpha, no generator can achieve representative generation in the limit using only a finite number of membership queries).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments. We address the reviewer's concerns below. \n\n> There are several works on generative model evaluation that use notions of precision and recall (e.g, Sajjadi et. al. 2018, Kynkäänniemi et. al. 2018) in the attempt to assess whether models capture the diversity of the data-generating distribution. These should probably be discussed\n\nWe thank the reviewer for pointing out these relevant works. We will make sure to cite them in the camera-ready version.\n\n> The paper doesn’t offer any insights/recommendations that let the reader bridge the gap...\n\nWe emphasize that our paper primarily offers theoretical contributions by extending and analyzing the model introduced by Kleinberg and Mullainathan. For insights regarding practical applications and recommendations, we direct you to our response to Reviewer U9Ez above (Re: Practical applicability of results) addressing these aspects.\n\nRegarding the specific assumptions in our framework, the UUS assumption is standard across generation literature and serves a fundamental purpose: ensuring generators can indefinitely produce novel elements from the true language. This assumption aligns with practical contexts, where the set of \"valid generations\" is effectively infinite--for instance, the set of all valid English passages is unbounded. The finite support property is similarly incorporated to ensure basic feasibility. As demonstrated in Lemma 4.3, without this assumption, representative generation becomes impossible even when the generator has complete knowledge of the true language.\n\n> Consider using fewer scare quotes\n\nThanks for pointing this out. We will make sure to dial back on the use of scare quotes in the final version. \n\n> Following from the last comment, why is “sample complexity” in quotes throughout the paper?\n\nYes, the notion for uniform and non-uniform generation, is indeed the actual sample complexity. We will remove the scare quotes in these sections.", "claims_and_evidence": "Yes, main claims are stated as theorems, corollaries, and lemmas, which are supported by proofs (outlines of proof are given in body of paper and formal proofs in appendix)", "methods_and_evaluation_criteria": "There aren’t really any evaluations in this paper, as its providing a theoretical framework.", "theoretical_claims": "There are numerous theoretical claims in the paper. I was unable to check all rigorously. The informal arguments given in the paper (formal proofs were in appendix) intuitively made sense", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper expands on other works’ attempts to formalize diversity and representativeness in generative models. They discuss the relationship to concepts such as mode collapse ad notions from algorithmic fairness, such as multiaccuracy and multicalibration. I am unfamiliar with the prior related work but the claimed extension this work offers seems worthwhile", "essential_references_not_discussed": "There are several works on generative model evaluation that use notions of precision and recall (e.g, Sajjadi et. al. 2018, Kynkäänniemi et. al. 2018) in the attempt to assess whether models capture the diversity of the data-generating distribution. These should probably be discussed", "other_strengths_and_weaknesses": "The paper doesn’t offer any insights/recommendations that let the reader bridge the gap between its theoretical results and various practical implementations. To me, this is a major shortcoming. It’s unclear how much the specificity of the assumptions (e.g., UUS and finite support) behind the results limit their direct applicability to real-world systems.", "other_comments_or_suggestions": "Consider using fewer scare quotes. These are typically used to indicate the inaccurate use of a term. Given that the merits of this paper are a theoretical framework, if you need a different term than the one you’re putting scare quotes around, I would recommend defining such a term.", "questions_for_authors": "Following from the last comment, why is “sample complexity” in quotes throughout the paper? Is the notion not actual sample complexity? This wasn’t evident to me", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies representative language generation, extending recent theoretical frameworks. It characterizes conditions under which representative generation can or cannot be achieved, providing insightful theoretical bounds and impossibility results. Reviewers generally agree that the paper addresses an interesting and meaningful extension of prior work and contributes rigorous theoretical analyses. Given the overall positive reviewer consensus, I recommend acceptance for this paper.
Decision: Accept (poster)