Representative Language Generation

We thank the reviewer for their helpful comments. We address the reviewer's concerns below.

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

We thank the reviewer for pointing out these relevant works. We will make sure to cite them in the camera-ready version.

The paper doesn’t offer any insights/recommendations that let the reader bridge the gap...

We 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.

Regarding 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.

Consider using fewer scare quotes

Thanks for pointing this out. We will make sure to dial back on the use of scare quotes in the final version.

Following from the last comment, why is “sample complexity” in quotes throughout the paper?

Yes, the notion for uniform and non-uniform generation, is indeed the actual sample complexity. We will remove the scare quotes in these sections.

Re: Practical applicability of results

Thank 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.

To 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.

That 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.

At a high-level, we view the main contributions/takeaways of our work as two-fold, in the context of existing works on generation:

1. 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}$.
2. 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.

Re: Choice of supremum distance

Our 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.

It'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.

As 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.

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.

Finite Support Size Assumption

We 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:

• As you correctly observe, any collection of finite groups will always satisfy the finite support size assumption.
• 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)$.
• 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.

(Q1) Is there an easy way to check if a hypothesis satisfies group closure dimension? How can one interpret it?"

Like 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.

[1] Ben-David, Shai, et al. "Learnability can be undecidable." Nature Machine Intelligence (2019)

(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 ?

There are several issues that arise when one tries to go beyond disjoint groups.

• 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].
• 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.

(Q3) How are the techniques used in this result different from the techniques of Charikar and Pabbaraju?

We 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.

Both 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.

[2] Kleinberg, Jon, and Sendhil Mullainathan. "Language generation in the limit." (2024)

We thank the reviewer for their comments.

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?

In 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.

You 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.

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.

In 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, ...$ .