On Union-Closedness of Language Generation
Authors: Steve Hanneke
Amin Karbasi
Anay Mehrotra
Grigoris Velegkas
Venue: NeurIPS 2025 poster ()
Keywords: language generation
union-closedness
online learning
learning theory
Primary area: theory
TL;DR: We show that language generation in the limit is not closed when we take finite unions of collections of languages.

Abstract: We investigate language generation in the limit – a model by Kleinberg and Mullainathan and extended by Li, Raman, and Tewari. While Kleinberg and Mullainathan proved generation is possible for all countable collections, Li, Raman, and Tewari defined a hierarchy of generation notions (uniform, non-uniform, and generatable) and explored their feasibility for uncountable collections.
    Our first set of results resolve two open questions of Li et al. by proving finite unions of generatable or non-uniformly generatable classes need not be generatable. These follow from a stronger result: there is non-uniformly generatable class and a uniformly generatable class  whose union is non-generatable.
    This adds to the aspects along which language generation in the limit is different from traditional tasks in statistical learning theory like classification, which are closed under finite unions. 
    In particular, it implies that given two generators for different collections, one cannot combine them to obtain a single "more powerful" generator, prohibiting this notion of boosting. Our construction also addresses a third of Li et al.'s open questions on whether there are uncountable classes that are non-uniformly generatable and do not satisfy the eventually unbounded closure (EUC) condition introduced by Li et al.
    Our approach utilizes carefully constructed classes along with a novel diagonalization argument that could be of independent interest in the growing area of language generation.

On Union-Closedness of Language Generation
Steve Hanneke
Anay Mehrotra
Purdue University
Yale University
steve. . www.ekee@gaiil.com
mlaymehrotral@gaill.. com
Amin Karbasi
Grigoris Velegkas
Yale University amin. kwrbaaarbbiiaae cerrbas@@gmail.com
Google Research gvelegkas@google.c
Abstract
We investigate language generation in the limit model by Kleinberg and Mul- lainathan 20224, NeurlPS) and extended by [ii, Raman, and Tewari [2025]. While Kleinberg and Mullainathan proved generation is possible for all countable col- lections, [Li et al. 2025] defined a hierarchy of generation notions (uniform, non-uniform, and generatable) and explored their feasibility for uncountable col-
lections. Our first set of results resolve two open questions of [Li et al., 2025) by proving finite unions of generatable or non-uniformly generatable classes need not be generatable. These follow from stronger result: there is non -on-uniformly generatable class and a uniformly generatable class whose union non gonn-eeerattble. This adds to the aspects along which language generation in the limit is different from traditional tasks statistical learning theory like classification, which are closed under finite unions. In particular, it implies that given two generators for different collections, one cannot combine them to obtain single "more powerful" generator, prohibiting this notion of boosting. Our construction also addresses a third of [Li et al. 2025]'s open questions on whether there are uncountable classes that are non-uniformly generatable and do not satisfy the eventually unbounded closure (EUC) condition introduced by Li, Raman, and Tewari. Our approach utilizes carefully constructed classes along with novel diagonalization argument that could be of independent interest in the growing area of language generation.
Introduction
The algorithmic problem the core of language generation both humans and large language models (LLMs) - is deceptively simple: given sequence of examples from some target language, generate new and previously unseen strings that also belong this language. Despite the remarkable capabilities of humans and, perhaps, more so of LLMs, to generate coherent text, thorough understanding of the theoretical underpinnings of language generation has remained elusive.
Language Generation the Limit. Kleinberg and Mullainathan 2024 recently formalized this problem model resembling online learning: First, adversary fixes target language K E L and an enumeration of K At each round > 1, the adversary presents the n-th element v, of the enumeration to the generator. The generator, given the strings S, {II,..., [n) seen so far, outputs a new string w,, & S, - its guess for an unseen string in K. The generator wins this game it eventually learns "to generate from K." Formally, a generator G is said generate from & in
Part the work was done while author was a PhD student Yale University.
Formally, en enumeration of K is an infinite sequence of elements Ø2, (possibly including duplicates) such that each E K, and for every element K there is some position in the sequence where appears.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the limit if for all K E L and any enumeration of K, there exists finite time n² such that for any subsequent round n 2 n². the generated string wn, is an unseen element of K, i.e., Wn. K S...
This model is closely connected to the seminal work of Gold [1967] which studied the problem with the harder goal of identifying the target language K from a collection of languages - and sparked long line of work both in linguistics and computer science, culminating in complete characterization by Angluin 1979 1980]. This characterization revealed profound paradox: while language generation is readily accomplished by humans (and now, LLMs), language identification in the Gold-Angluin model proves intractable for virtually all non-trivial collections even collections of regular languages, which are considerably simpler than human languages. This intractability persists despite Gold's model imposing no constraints on the computational power of the learner.
Kleinherg and Mullainathan [024] offer a striking resolution to this paradox: they demonstrated that subtle shift in the problem formulation from identification to generation renders the problem tractable. Their main result is that language generation in the limit is achievable for any countable collection of languages. This remarkable finding sparked significant interest within the learning theory community, spawning a growing line of works (e.g., Li et al. [2025] Kalavasis et al. [2055] see Section
Charikar and Pabbaraju 2025 Raman and Raman
[025
detailed discussion.
Most relevant to our work is the work of Li et al. [2025] - who take a learning theory perspective on language generation in the limit (henceforth, simply language generation) allowing & to be an uncountable collection - and characterizing which collections & are amenable to different forms of generation. In particular, they define a hierarchy of generation notions which differ in whether the number of samples n² that are needed to achieve consistent generation depends on the target language K E L or its enumeration. In decreasing order of hardness, these notions are:
Uniform Generation where n² neither depends on K nor its enumeration; it only depends on C
Non-uniform Generation where n² can depend on & and K but not K's enumeration
Generation where n² can depend on &, K, and K's enumeration
Here, the weakest notion, generation, is the one studied by Kleinberg and Mullainathan 2024
Our Main Questions. In their work, Li et al. 2025) demonstrated that the problem of generation,
under any of these notions, is fundamentally distinct from prediction and the PAC learning framework: they constructed several classes that are generatable but not PAC learnable and vice versa, establishing clear separation between these paradigms. While these examples illustrate specific differences between prediction and generation, they raise a more profound question: do the conceptual properties of generation differ significantly from those of prediction? One of the most fundamental properties of traditional prediction tasks (such as binary, multiclass, or online classification) is closure under finite unions if classes H, and He can be learned (under any of the aforementioned notions of prediction) then so can H, U Hy. However, establishing the closure of generatability has remained elusive so far. Indeed, the challenge of effectively combining generators also appears in the work of Kalavasis et al.) (025). where it is a crucial obstacle in establishing tight sample complexity bounds for generation in statistical settings. Although Kalavasis et al. [2025] ultimately circumvent this challenge through alternative techniques, the following fundamental question remains:
Q1. Is generation closed under finite unions?
This was also explicitly posed as a key open problem by Li et al. 2025 (as Questions 6.2) and as a first step in addressing this broader question, they also posed the following more specific variant."
Q2. Are finite unions of non-unifornly generatable classes always generatable?
Apart from differences between generation and prediction, main results Li et al. (025]
complete characterizations of uniform generation and non-uniform generation, respectively. A natural and important question is develop a complete characterization of generation in the limit. Toward this goal. Li et al. (2025) provide several sufficient conditions. Perhaps the most natural one of these based on the Eventually Unbounded Closure (EUC) property (see Definition 2.7). Informally, a
Li et al. 2025] show finite unions of uniformly generatable classes are generatable but need not be unifoory generatable.

---

collection & satisfies the EUC property if for any target language, K E L, after seeing finite number of elements 21 21, In E K, all languages L E L consistent with 21, 22, 2n share infinitely many elements. (In other words, all languages in the "version space" defined by 11; 22, ........ &n share infinitely many elements for large enough n.. Further, et al. [2025] observed that the EUC property is connected to a certain "autoregressive" property where, after seeing finitely many samples, the generator no longer needs to observe further samples to generate new and unseen examples in the future. Given the central role of EUC in current approaches to characterizing generatability and its connection to the autoregressive property, [i et al. [025 pose the following question:
Q3. Is there a non-uniformly generatable and uncountable class violating the EUC property?
1.1 Our Contributions
We present a family of constructions and corresponding techniques that resolve three open questions of Li et al. [025 in the model of language generation of Kleinberr and Mullainathan (2024).
Our first result constructs two collections &1 and C2 that are generatable individually, while their union & U L2 is not, answering Question 1 negatively (Theorem 3.1. This construction relies on specific properties relating the two collections (which we explain later; Section (.4]. allowing us develop family of counterexamples demonstrating that the failure of union-closednes: is not isolated but an inherent property of language generation that fundamentally distinguishes it from traditional prediction tasks. In particular, we can also ensure that L and L2 are both non -niforrlyyly generatable, hence, also resolving Question 2.
Non-Closure Under Finite Unions:
A Minimal Pair of Classes Whose Union Is Not Generatable: Next, we investigate the spectrum between known extremes: at one end, Kleinberg and Mullainathan] [2024) showed that unions of countable collections are generatable; at the other end, our first result (Theorem (3.2) shows that unions of uncountable generatable collections need not be generatable. Our second result, refines this understanding by constructing a countable collection & and an uncountable collection Cú2 whose union is not generatable. Notably, in this construction, & is non-uniformly generatable and L/ is uniformly generatable (both without requiring to get any examples from the target language), yet their union & U U,222 is not generatable (Theorem 3.2). This observation shows that the construction is minimal in the sense that simplifying either collection further (by, e.g., making 2 to be uniformly generatable or L/2 countable) would make the union generatable, due to results of Li et al. [2025), Kleinberg and Mullainathan (2024).
Non- Uniforrfyyyyy Generatable Collections without EUC: Our third result (Theorem 3.3 answers Question 3 by identifying an uncountable collection that is non-uniformly generatable but violates the Eventually Unbounded Closure (EUC) property. This result provides insight into the relationship between non non-uniform generatability and the autoregressive property, suggesting that current sufficient conditions for characterizing generation in the limit need to be expanded.
Technical Novelty. We now highlight the key technical challenges and innovations in obtaining our re- sults. The problem of studying generatability of unions of classes was previously examined by Li et al. (2025). who showed that countable unions of uniformly generatable classes need not be generatable in the limit. As they note, their result "showcases the hardness of characterizing generatability in the limit." " Their construction highly sophisticated, involving a countable list of collections L1, C2.... .... each defined by a different prime number. In this construction, they are able to ensure that the union, U.A. was sufficiently complex that it ends up being non- non-generatable. This is achievable because they take unions of countably many classes an operation under which even standard prediction tasks in learning theory (such as binary and multi-class classification) are not closed f
A key challenge in our work is that we consider unions of just two classes. These two classes must simultancously possess enough structure to be individually generatable, yet become sufficiently complex when combined that their union is not generatable in the limit. Our result in Theorem 3.2 is even more surprising, as demonstrates this phenomenon with one class being (trivially) uniformly generatable and the other being countable. Our construction relies on several careful choices that we outline below and elaborate on in Section 3.4
Overview of Diagonalization. The only method for proving non non-generatabilityy is diagonaliza- tion [Li al. 2025 Charikar and Pabbaraju 2025 Kalavasis et al. 2024). This approach is
'Iddedd, one can construct countable union of classes where the i-th class has VC dimension i, so that the countable union necessarily has infinite VC dimension, rendering it unlearnable.
3

---

also fundamental in computational complexity theory [Arora and Barak 2009]. At a very high level, using diagonalization one constructs, for any consistent generator, an adversarial enumeration of the target language with distinct "phases" 11 22.... .. such that in the i-th phase, the generator must generate from language T, (and not from languages T4+1, T4+22...... Iix K). Conse- quently, either the generator fails to be consistent in one phase (failing to generate from L,), or we identify infinite steps where it fails to generate from K L.g0
Challenges in Using Diagonalization with Finite Unions. When applying this argument to two collections, we must partition the languages L1, Lz,... between our collections, L1 and L2. However, this causes problem: by the Pigeonhole principle, at least one collection must contain infinitely many of these languages. Typically, this would allow us to reproduce similar diagonalization argument. showing that the corresponding collection (say L1) is itself not generatable contradicting our goal. (Note that et al. 2025] avoid this problem by using countably many collections, assigning language L to collection L; ensuring that each collection only has a single language from L1, I2,....)
Idea I (Embedding A Shared Structure). To overcome this challenge. we divide the languages into two sets L1, La, Li.... and L2, L4, Le..... ................................ embed a shared structure across each set of languages, and assign the sets to the collections &1 { La, Lg....) and L2 {22, L4, Lo....) respec- tively. For instance, one form of structure is to ensure that L1, L3, Ls. 2 24 (all odd-indexed languages contain all positive integers) and L2, L1, Lo... 2 Z_ (all even-indexed languages con- tain all negative integers). This structure prevents the diagonalization argument from working independently on either 1 or L2.
Lo.
This approach, however, introduces a new challenge: it potentially prevents diagonalization from working on L1 J L2 well. For example, generator could determine whether it is in the "even world" (where K 2 z__ or the "odd world" (where K 2 2+) by comparing the length of observed prefixes of negative integers versus positive integers. (We make this argument formal in Section 3.4
Idea 2 (Omitting Shared Elements). To prevent such identification, we need to ensure that after seeing only finitely many elements, every even-indexed language consistent with the enumerated stream is sufficiently similar to some odd-indexed language, and vice-versa. In the context of our running example, to do that allow each language L, to omit finitely many elements from its shared set (either Z. or Z_). This turns out to be sufficient to ensure that the generator cannot identify whether K E L1 or K L2-
This idea, however, creates an additional technical hurdle because standard diagonalization leads to the language K (= Lox) missing infinitely many elements from both shared sets (positive and negative integers for & and L2 respectively), meaning it could not belong to either collection, otherwise the corresponding collection would be non-generatable.
Idea 3 (A Variant of Diagonalization). Our third innovation is a novel form of diagonalization where, counter-intuitiven the adversary forces the generator to make mistakes only in alternate rounds. This approach carefully balances the constraints to ensure that (1) both collections remain generatable individually, (2) their union is not generatable, and (3) the final language K enumerated during diagonalization belongs to one of the collections.
We believe this novel diagonalization technique will have broader applications in the study of language generation, potentially paving the way toward complete characterization of generatability in the limit - addressing the main open question in this research area identified by Li et al. (2025).
1.2 Related Work
Our work directly builds on the framework of Kleinberg and Mullainathan 2024]] who introduced the model of language generation in the limit. Since then, growing line of research has explored
various aspects of language generation (e.g..
Li et al. [2025]. Kalavasis et al. [2025]. Charikar and
Pabbaraju 2025 Raman and Raman 2025 Peale et al. 2025
Kleinberg and Wei (2255 Here,
we discuss the most relevant prior works.
Uniform and Non-Uniform Generation. Li et al. [025 introduced hierarchy of three notions of
generation uniform, non-uniform, and generatable and provided characterizations for uniform and non-uniform generation along with sufficient conditions for generatability. Charikar and Pabbaraju [2025) also, independently and concurrently, studied non-uniform generation and showed that all countable collections can be non-uniformly generated, strengthening the results of Kleinberg

---

and Mullainataa [2024] (which only showed that countable collections are generatable and finite collections are uniformly generatable).
Language Generation with Breadth. While Kleinberg and Mullainathan's 's algorithm eventually ceases outputting elements outside of K after finite time (i.e. it eventually stops hallucinating), this property comes at a cost: the algorithm sacrifices breadth - ie., the ability to generate diverse strings from the target language. A number of works study language generation with different notions of breadth and demonstrate that requiring many natural notions of breadth makes generation significantly harder, almost as hard as language identification Kalavasis et al. 2025], Charikar and Pabbaraju 2025
Kalavasis et al. [2024] Peale et al. 2025 Kleinberg and Wei [025]]
Further work on Language Generation. Recent works have also explored several other aspects of
language generation. |aaaan and Raman [2025] investigated language generation in model where
an adversary can introduce errors the inputs, developing robust framework for noisy settings.
Karbasi et al. 2025 explored the complexity of determining if a specific generator G is hallucinating.
Union-Closedness of Prediction. Understanding the behavior of learning problems such as binary classification and online learning under various natural operations on the underlying hypothesis class, egg. finite unions, intersections, and products, is fundamental challenge that is now well-understood e.g.,Van
in the literature see, e.g., Van Der Vaart and Wellner [2009], Alon et al.] [2020), Ghazi et al. (202T) and references therein. Notably, these properties also reveal natural learning strategies: one can decompose the underlying class into simpler ones, learn them separately, and "combine" the learners.
2 Preliminaries
In this section, we present some background on language generation in the limit.
Notation. Let Σ be a finite alphabet (e.g., {a. ba..,..., 2)), and E the set of all finite-length strings formed by concatenating symbols from E. We define a language L as an infinite subset of "*. collection of languages denoted by L. We define generating algorithm g nG.) as sequence of mappings G.: (E*)a - Σ" parametrized by the input size n. In words, the generator maps a finite training set to a (potentially infinite) set of elements
Language Generation in the Limit. We begin with the formal definition of language generation in the limit, introduced by Kleinberg and Mullainathan [2024).
Definition 2.1 (Language Generation in the Limit [Kleinberg and Mullainathan, 2024]). Fix some K from the language collection & and a generating algorithm G = (Gn) ). At each step n, let S, C K be the set of all strings that the algorithmm G has seen so far. G must output a string Wn. & Sn (its guess for an unseen string in K). The algorithm G is said to generate from K in the limit if. for all enumerations of K, there some belongs to K. \ Sn (or KV \. Sn is empty). The collection & allows for generation in the limit if there an algorithm G that generates from K in the limit for any K E C.
N such that for all steps n 2 n², the algorithm's guess wn
To gain some intuition about this definition, consider the collection & L= (Z, In, I- To, T- of thresholds over integers where, for each E Z, Iu = {i, i + i + 2, 2...... Suppose the target language is some K E L and the adversary first enumerates string 31. The generator can deduce that K = Lg for some = < Il, i.e., K E {Z, ba, these languages is non-empty and is strict superset of the strings enumerated far (namely, the intersection is {01 + 1, I + 2.....) }). the generator can generate an element that is guaranteed to be in K: for instance, it is sufficient to output 31 + More generally, after seeing strings x1, 22 . Tig the generator can output any integer larger than max I1, II...... ........... 24}.
Since the intersection of all of
Remark 2.2. For the problem to be interesting, we assume that each language in the collection has infinite cardinality, i.e., LL| = oc for all L E L. (Otherwise, \ S, eventually becomes empty.)
Remark 2.3 (Repetitions). For simplicity. we throughout also assume that the adversary is not allowed to repeat strings in its enumeration. Otherwise, to define uniform and non-uniform generatability, we have to count the number of unique elements listed by the adversary [Li et al. 2025
'While Kleinberg and Mullainathan 22024] required outputting only one element at a time, Kalavasis et al.
2025 Charikar and Pabbaraju| [2025] relaxed this to allow for case where, at some finite point, one can stop training and generate rich set of responses.
5

---

Kleinberg and Mullainathan (2024) showed that language generation in the limit is possible for all countable collections of languages starkly contrasting results in language identification.
Uniform and Jon-Uniform Generation the Limit. Next, we present two strengthenings of the notion of generation in the limit introduced by Li et al. (2025]. The first notion is the strongest, it requires the number ni* Definition 2.1 (which is the number of samples required by the generator before it starts generating consistently) be independent of the target language and its enumeration.
Definition 2.4 (Uniform Generation [Li et al. (025]). A collection & is said to be uniformly generat- able, if there is algorithm G and n' such that, for each K E & and each (adversarially chosen) enumeration EK of K, G generates from K in the limit after seeing n 2 n examples from K.
The non-uniform generation weakens this notion by allowing n² to depend on the target language. Definition 2.5 (Non-Uniform Generation (Li et al. 2025)) A collection & is said to be non-uniformly generatable, there is an algorithm G such that, for each K E L, there is a number n = n (K) such that for any (adversarially chosen) enumeration E of K, G generates from K in the limit after seeing n 2 n² examples from K.
provide characterizations for both the collections that are uniformly and non-uniformly generatable, respectively. These, in particular, show that all countable collections are non-uni uniformlfy generatable; a result independently and concurrently also shown by Charikar and Pabbaraju (2025). They also show that all finite collections are uniformly generatable in the limit; a result that was also earlier shown by Kleinberg and Mullainathan [2024].
ai 2025
key remaining question, after these works, is a characterization for the weakest notion of generation in the limit in Definition 2.1] where n" can depend on both K and Ex. Next, we define the eventually unbounded closure property, which forms the basis of sufficient condition for generatability proposed by Li et al. (2025).
Definition 2.6 (Version Space). Given a finite sequence of strings X [xI1...,,Tal and collection A, let (4, X) be the set of languages L E L containing X.
Definition 2.7 (Eventually Unbounded Closure). Unbounded Closure (EUC) property if. for every L E & and enumeration T2,.. of L, there is finite time t, at which all languages in (CC, (2.., share infinitely many elements.
collection L is said have the Eventually
is not too hard to show that all uniformly generatable collections possess the EUC property, while some generatable collections do not (Li et al. 2025]. The relationship between EUC and non-uniform generatability is less clear, and Li et al. 20255 constructed a countable class that was non-uniformly generatable without the EUC property, but left open whether uncountable such class exists. Our work resolves this question by demonstrating an uncountable class that is non-uniformly generatable yet lacks the EUC property.
3 Our Results and Technical Overview
In this section, we present our results on language generation in the limit, addressing three open questions of et al. (0255]
3.1 Non- Cin-CClsure Under Finite Unions
Our first result demonstrates that generation is not closed under finite unions.
Theorem 3.1. There uncountable collections L1, L2 that are non-uniformly generatable while L C2 is not generatable.
We stress that while each collection is non- non-uniformly generatable, their union does not just violate non-uniform generatability, also violates generatability. Thus, Theorem resolvve both Questions I and 2 negatively. Further, the construction in Theorem 3.1 relies on a certain properties between L, and L2 (see Appendix A.2), which enable us to generalize this approach to a family of counterexamples. This demonstrates that the failure of union-closedness is not an isolated phenomenon but rather an inherent property of language generation.
3.2 On Finite Union of Non-Uniformly Generatable Collections
Both collections in Theorem 3.T are uncountable, This is necessary in part: at least one collection must be uncountable since, otherwise, if both are countable collections, then their union remains

---

countable and, hence, generatable by the results of oleinbbb and Mullainathan 2024]. This naturally raises the question: must both collections be uncountable for the union be non- non-generatable?
Our second result shows that both collections need not be uncountable. From our family of coun- terexamples, we identify a pair (2) where L is countable, L2 is uncountable, and their union is not generatable.
Theorem 3.2. There are collections &n and for which &1 U L2 is not generatable such that:
L1 is countable and non-uniformly generatable, without requiring any elements from the adversary
22 is uncountable and uniformly generatable, without requiring any elements from the adversary.
Thus, Theorem 3.2 establishes that unions of non-uniformly and uniformly generatable classes not guaranteed to be generatable. Moreover, these collections are minimally complex in the following precise sense: if either collection is any simpler (i.e., if 1 is uniformly generatable or L2 is countable), then C U L2 would be generatable. When & is uniformly generatable this is due to result Li et al. [025]] which shows that unions of uniformly generatable classes are generatable. When 22 countable, this is due to result of Kleinberg and Mullainathan (2024) showing that all countable collections are generatable.
Furthermore, even among non-uniformly generatable and uniformly generatable classes, L1 and La represent the simplest collections because they can be generated without observing any elements from the adversary. In the terminology of Li et al. 22225,, this enables "autoregressive" generation where the generator can produce new elements without requiring input from the adversary.
Finally, since &1 is countable it can be expressed as a union of singletons &₁ = - {L:}. Since each singleton is trivially uniformly generatable, Theorem 3.2 provides list of countably many classes (L2, {L1b, {
) that are each uniformly generatable without requiring any elements from the adversary but their union L2 {L1 U {L2] U... is not generatable. This, in particular,
recovers a result of et al. [2025]. namely their Lemma 4.3.
3.3 On the EUC Property and Non-Uniform Generation
Our third result resolves Question 3 direct consequence of our construction in Theorem
Theorem 3.3. There is an uncountable collection & that is non-uniformly generatable and violates the EUC property (Definition) 2.7
Specifically, the collection 1 from Theorem 3.1 is non-uniformly generatable but violates the EUC property, providing a concrete counterexample that addresses this open question.
3.4 Technical Overview
In this section, give detailed overview of our approach; for a higher-level summary, refer readers to Section 1.1 Our goal is to show that finite unions of generatable classes need not be generatable. Toward this, it instructive to build some intuition about how show that a class not generatable. Recall that Kleinberg and Mullainathan [2024] showed that any countable collection is generatable, thus we must necessarily work with uncountable collections.
Warm-Up: A Non-generatable Collection. Let the domain E' be N. A natural candidate to consider is the collection of all infinite subsets of N Given a generator G, will pick some K E C and enumeration of K, both tailored to G. so that it makes mistake in every step. Let us denote the element enumerated at step IN by æ; and the element generated by y/4 = G. (II,... 2.). We begin by setting Ií = 1. Then, for each & E N we define I = max (max;=1.....- F4;
step N
2, 1. We let K = ULeN {2.} and E (21, Notice that d; # xę for i of L. hence K contains infinitely many elements. Moreover, K L and E a valid enumeration of K] Why does the learner make a mistake in every step? Consider two cases: it fails to output an unseen element, or it outputs some yA & { J.J. In the latter case, by the definition of E, all the elements we
at step either the learner outputs some y/ .. ar
'Recall that all languages in the collection are infinite. In fact, is an "easy" enumeration since it lists elements in increasing order.
problem generation to be well-defined Kleinberg and Mullainathan
2024 require that
7

---

enumerate in subsequent rounds (the unseen elements of K), are greater than y/s which means that y/ not an unseen element of K.
Unfortunately, the collection & is very complex so it is not clear at all if it is possible to split it into two collections L1; L2 such that both of them are generatable and &1 U L2 L. Nevertheless, this idea of constructing hard enumerations and target languages as a function of the underlying generator a.k.a. diagonalizing against the underlying generator will be the first ingredient towards our main result. Next, we explore the crucial question: Can we construct 1, 22 that are individually easy to generate from but L1 U L2 is (almost) as complex as the previous collection?
First Attempt (which Fails). Our first idea is to create &1 and L2 in a symmetric way. Both defined over Z, L1 contains languages that are "easy" on the negative integers and "hard" on the positive integers, while &a contains languages that are "hard" on the negative integers and "easy" on the positive integers. Taking this approach to the extreme, we define
L1 = (LA = z- UA A S Z+, |A| = %o} and L2 = [LB = UB,
B oo)
In words, every language in &1 contains all the negative integers and some infinite subset of the positive integers (and for every such subset there exists a corresponding language in L1). The collection L2 is defined in a symmetric way where the roles of positive and negative integers are flipped. Both &1 and L2 are uniformly generatable in a trivial way: for &1 it suffices to generate any unseen negative number and symmetrically for L2.
Can single generator successfully generate &1 U2? Since there is systematic way generate from uncountable collections (unlike countable collections), we explore natural heuristics. Perhaps the most intuitive approach is to track the positive and negative integers observed so far and generate from the "heavier" side (the side with more observed elements). This approach fails: an adversary can select language from & and ensure any finite prefix of the enumeration contains more positive than negative integers - fooling the learner into generative positive integers and, then, selecting the set A using our warm-up technique to force mistakes. However, a more sophisticated generator does exist for &1 U L2: the generator keeps track of the longest prefix enumerated on the positive and negative side separately, and outputs an unseen number from the side with the longer prefix.
Why does this work? If K = Z. then the generator is always correct. Otherwise, K either contains Z_ and misses least one element from Z.4 or it contains Z., and misses at least one element from E_. In either case, since the adversary must completely enumerate K the prefix of one of the two sides will stop growing, while the other increases indefinitely. Thus, in the limit, this generator will output valid and unseen elements from K.
An A Attempt (which Works). The core reason why our previous attempt fails is that (in the limit), a sufficiently clever generator can identify if K & or K 2- To get our result, we need to ensure that no generator can make this determination. We therefore modify our collections L1, L2 to make them even more similar while keeping them individually generatable:
f == (LA.B == (Z_ \ A) U (Z+ B), A Z-, |4| < oc, B B = x0) 2/2 = (LAB (z_ (Z+ B
|A| = 0c, BC [B] 30)
In this construction, languages in L contain almost all negative integers (missing only finitely many in A) and only some positive integers (missing infinitely many in B). The collection L3 is defined symmetrically, with finite/infinite exclusions reversed. First, notice that 41 Cb are non-uniformly generatable in a trivial way: there exists a generator that generates from &, (and (b) without seeing any examples from the target language and the number of mistakes it makes depends only on K P
The crux of the difficulty with the new collections is that, while they have a clear asymmetry (one side missing finitely many elements, the other missing infinitely many). this asymmetry cannot be detected at any finite time. Indeed, it is not hard to see that the sophisticated generator that kept track of continuous prefixes of both positive and negative integers and generated according the longer-prefix side fails for & U C/. It turns out that every generator fails for the union of this pair of collections.
To show this, a tempting approach is to try to replicate our strategy from the warm-up construction and force a mistake in every round. For instance, we can start enumerating positive integers, and
A prefix of length from _- is the set {-i, -i L..... 113 and symmetrically from Σ- "Indeed, for A1 the generator can start outputting negative integers in decreasing order and since any K misses only finitely many of them it will eventually start generating correctly (symmetrically for L32))
8

---

the generator ever outputs an unseen positive number Ti,, switch to enumerating negative integers ensuring that we do not enumerate any negative number the generator has generated. Indeed, &' U U.2 is sufficiently complex to ensure that for every E N the elements S, enumerated up to timestep & are consistent with some language K2 E L. Unfortunately, this property does not imply that we present a complete enumeration of some K E L. Indeed, it is not hard to construct generators for which the stated approach ends up enumerating some K that does not contain infinitely many negative integers and infinitely many positive integers; such languages are not part of & U L'z. Hence, to show the non-generatability of & U L/2 we must use more involved argument.
Modified Diagonalization Argument. We now present a lower bound construction that proceeds in (potentially infinitely) many phases, which are now broken into two subphases, and is tailored to the underlying generator G. Let us introduce some notation: let S, denote the elements enumerated by the adversary up to (and including) step l. We also denote by P. the set of positive integers the generator has outputted up to (and including) step t and N, set of negative integers the adversary has enumerated up to (and including) step t. We now describe our construction inductively:
Phase I-A: During this phase, the adversary enumerates the negative integers starting from -1 in sequential, decreasing order (-1, -2, .....) ) until the generator outputs an unseen negative integer. If this never happens, the adversary ends up enumerating K = Z_ E & and the generator makes a mistake in every timestep. hence the adversary wins the game. Thus, let us assume that 11,, is the first timestep the generator outputs an unseen negative integer. At this point, we switch phase 1-B.
The adversary now enumerates positive integers starting from max A + 1 in a sequen- tial increasing order. Let f1,8 > 4 the first timestep when the generator outputs a positive integer. Using similar reasoning, if this never happens, the adversary enumerates a valid language from L32 and the generator makes infinitely many mistakes. Otherwise, we proceed to phase 2.
Phase I-B:
For 2 2, the E-th phase follows:
Phase A-A: Upon entering this phase, the adversary enumerates the largest negative integer not yet enumerated, i.e., the number min N₂- 1, and in the subsequent rounds of this phase it continues in decreasing order. Importantly, some of these negative integers might coincide with elements the generator has previously outputted, thus "correcting" some of its tentative mistakes. As explained, this is unavoidable since there are G such that if the adversary forces G to make a mistake in every step it necessarily enumerates a language that is not in 4 C/ Let Le, 1,-118 I,B be the first timestep when the generator outputs an unseen negative integer. At this point, we move to subphase É-B.
Phase (-B: Similar to subphase 1-B, the adversary enumerates positive integers starting from max P + until the generator outputs a positive integer, at which point this subphase ends.
Having described the construction, we now argue its correctness. As we argued already, if the construction terminates after finitely many phases, then the learner makes infinitely many mistakes and the adversary enumerates a valid language. Alternatively if the construction proceeds for infinitely many phases, then the adversary enumerates Z_ along with an infinite subset of Z+, producing a valid language from L/. What about the generator's 's mistakes? The crucial observation is that every time we move from subphase Ê-B to (e 1)-A the adversary forces mistake for the generator. With infinitely many phases, the generator necessarily makes infinitely many mistakes. The formal details are in Appendix B.T
Remark 3.4 (Connection to EUC). This construction yields an additional insight: there are uncount- able classes that are non-uniformly generatable (in a trivial way), yet do not satisfy the Eventually Unbounded Closure (EUC) property. Indeed, both & and C3 are uncountable and non-uniformly generatable, but we can prove they violate EUC (Appendix [B.2), thus addressing Question 3.
Remark 3.5 (Stronger Lower Bound). The ideas we described in this section can be utilized to derive the stronger lower bound from Theorem 3.2 The formal details are in Appendix [.2
4 Concluding Remarks
In this paper we have continued studying the emerging line of work on language generation in the limit, resolving three open questions from Li et al. [2025). While the work of Kleinberg and Mullainathan 20244 showed a remarkable tractability of the problem when the collection of languages

---

is countable, our results and the results of Li et al. [2025] show that this learning task is significantly more involved when we move uncountable collections and exhibits behaviors that are qualitatively different from traditional learning problems such as binary classification [Valiant 1984 Vapnik and Chervonenkis 2015) or online learning [[ittlestone] 1988]. Our results further highlight the difficulty of coming up with characterization of generatibility, since there are collections that are generatable (in a strong sense), yet even taking the union two of them yields a -onggenertt collection. Nevertheless, we hope that the technique we introduce to show non-generatability will help pave the way to the solution of this challenging problem.
Acknowledgments
This research was supported (in part) by the Al Institute for searning-enables Optimization at Scale (TILOS)..
10

---

References
Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure properties for private classification and online prediction. In Conference Learning Theory, pages 119-152, PMLR, 2020.
Dana Angluin. Finding patterns common to a set of strings (extended abstract). In Proceedings of the Eleventh Annual ACM Symposium Theory of Computing, STOC '79, page 130-141, New York, NY, USA, 1979. Association for Computing Machinery. ISBN 978 1450374385. doi: 10.1145/800135.. 804406.
URL htLLhttp://do// org 10. 1ww.1111588130 804406
Dana Angluin. Inductive inference of formal languages from positive data. Information and Control, 45(2): 17--135, 1980. ISSN 0019-9958. doi: http:////..aaaaccactt/////////// URL htttps://wwet
Sanjeev Arora and Boaz Barak. Computational Complexity: Modern Approach. Cambridge University Press, 2009.
Moses Charikar and Chirag Pabbaraju. Exploring facets of language generation in the limit. In Nika Haghtalab and Ankur Moitra, editors, Tiirty- Conference Learning Theory (COLT 2025), Proceedings of Machine Learning Research. PMLR, 2025. URL hwtph::tt///rrtti htt.//.rxxvoo///////// abs bbs/2411.09642
Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Near-tight closure bounds for the littlestone and threshold dimensions. In Algorithmic learning theory, pages 686-696. PMLR,
2021.
E. Mark Gold. Language identification in the limit. Information and Control, 10(5):4474774 1967. ISSN 0019-9958. doi: http:://oooooolloooooosssssssss9 // h/www.scittt www.::/cwccaiiiicc...cc..c..tata
URL https
Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. Characterizations of language generation with breadth, 2024. URL.httts://aaxii
abs/ 18530 https://arxiv.orr /bs/
2412. 18530
Alkis Kalavasis, Anay Mchrotra, and Grigoris Velegkas, On the limits of language generation: Trade-off's between hallucination and mode collapse. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC'25), New York, NY, USA, 2025. Association for Computing Machinery. URL
Amin Karbasi, Omar Montasser, John Sous, and Grigoris Velegkas. (im)possibillity of automated hallucination detection in large language models, 2025. URL /ttp: wts..rgg/bbb///a/// 2504 17004 attps://arxiv orgooog//a/oo /tgg/bs///a 220../2544..4 17004
Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. Advances in Neural Information Processing Systems, 37:66058-66079, 2024.
Jon Kleinberg and Fan Wei. Density measures for language generation. 2025. URL attps://arxiv
org/abs/ ab//a///..20...///////// 2504. 14370 attps://arxivv.rrg// 22wpg//b//550..... 14370
Jiaxun Li, Vinod Raman, and Ambuj Tewari. Generation through the lens of learning theory. In Nika Haghtalab and Ankur Moitra, editors, Tiigtt Conference on Learning Theory (COLT 2025), Proceedings of Machine Learning Research. PMLR, 2025. bttp:ttss://axxx abs/2411.00 09642
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2(4):285-318, 1988. doi: 10.1007/BFO0 16827. URL https wtt.://////..10////000000 10000000000001201
//doi.org/// 1007
Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation. In Forty- second International Conference Machine Learning, 2025.
Ananth Raman and Vinod Raman. Generation from noisy examples. Forty-second International Conference on Machine Learning, 2025.
11

---

Lestie G Valiant. A theory of the learnable. Commun. ACM. 27(1)) 1142, 11 1984. ISSN 0001-0782. doi: 10.1 10.1199/1968. 1972. httts://///d org/ 10. 11w./111111.... 1972
Aad Van Der Vaart and Jon A Wellner. A note on bounds for ve dimensions. Institute of Mathematical Stalistics collections, 5:103, 2009.
V. N. Vapnik and A. Ya. Chervonenkis. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities, pages 11-30. Springer International Publishing, Cham, 2015. ISBN 978-3-319-21852-66 doi: 00.1007/97--3-31922185 3. URL https://doi org/10.10077 118-3-311-21882--62
12

---

A Further Results
A.1 Formal Lower Bound of Non-Generatability
In this section we show formally that the class of all infinite languages over N is not generatable in the limit. is worth mentioning that this result follows from result of et al. [2025]. Here, we give simpler proof which also generalizes to randomized learners (Proposition A.2).
Proposition A.1. Let E = M and & be the set of all infinite subsets of N. Then, no deterministic algorithm can generate from & in the limit.
Proof. Let G = (Gn: N - MEN be a deterministic generating algorithm and, for each n, let be the string outputted by Gn when provided the strings I1, I2. .......,,,, 2n as input. We will show that there is a language K E & and an enumeration E of K, both of which depend on G, for which G fails to generate from in the limit. We will construct the enumeration and the target language inductively. For all n E N, we denote by E,, the first elements of E.
T2:..,....
Let 21 = 1 and E = (1) We then define x2 = max {2), Gi (x1)} + and E2 (2). Continuing in the same fashion, for any n E N, we define In max {maxxen Bj maxj<n Gj (r1,..... {z1]} + and En = (FI,,.., Fn). Lastly, we let URENEn-
First, notice that since 2; * 2j, Vi.j Nii jt holds that |K| = oo, hence K E &. Moreover, notice that E' is a valid enumeration of K. Finally, notice that for every n E N, the algorithm either outputs number that does not belong to K or a number that has already been enumerated. To prove that formally, it suffices to show that for all n E N it holds that Ga(,,,.... ..n) [In+1 Fn. This follows by two observations: for all N holds that Ta41 > Ga( ................................ ............. Fn) and In+1+) > En+1, Vj E N.
It is natural to consider whether randomization can help circumvent the result of Proposition Our next result shows that this not the case.
A.
Proposition A.2. Let " N and & be the set of all infinite subsets N. Then, for every randomized algorithum G = (Gn: N" - A(N)) meN there exists a language E L and an enumeration E of K such that, with probability 1, will produce unseen elements of K only finitely many times.
Proof. Let G = (Gn: N - A(N)) nEN be a (potentially randomized) generating algorithm. We will show that there is a language K E & and enumeration E of K, both of which depend on G. for which G fails to generate from K in the limit, with probability 1. We will construct the enumeration and the target language inductively. For all N, we denote by En the first elements of E.
Let # = 1 and E = (1). . For any n E N, n 2 2 we define the random variable
max R max Gj Gz(Z1 (z(,.....,,,) 22)) Jan
X, = max
jen
and we let
1 n²
En min JEN: Pr[X,, 2 1 5
We also define F,, = (x1, (........7. ,,)) and UnENTn-
First, notice that, with probability 1, x; # ky, Vi,j E N # j. hence it holds that |K| co, thus K C. Moreover, notice that E is valid enumeration of K. Next, we argue that with probability the algorithm outputs unseen elements of K only finitely many times. For all n E N, let é, be the event that Gn, (x .,, xnn) E K (ai,..... (n... Notice that, by definition of the enumeration E and the target language K,
Pr [60] = Pr Pr xn) E 2n42...........
Moreover, since with probability In+1 Inn2 ..., , it holds that
Pr (T) 10nt1,2n42.... H} < 1 - ..,,... 2n) < xntil.
13

---

By definition of 2n+1 it holds that
1
Pr End < xn+1l 2 1-
(n 1)2
Chaining the previous inequalities, we get
Pr [6n] S (n+ 1)2
thus,
Σ Pr < <0.
nEN
By the Morel-Cantelle lemma we deduce that with probability only finitely many of the events { will occur.
A.2 Extensions to a Family of Constructions
We first explain some high-level properties of our lower bound construction and illustrate how they can be used to show non -on-generatability in other settings. In our construction, we can split the underlying collection & into two parts, say L L2 that allow for the following lower bound argument: the adversary can start enumerating some language Lı from L1, if at some point the generator generates an unseen element of L1 adversary moves to enumerating a language L2 from 22, and then if the generator generates unseen elements of L2 the adversary moves back again to enumerating some language L3 of 1. Crucially, the adversary can ensure that when switching from L2 to & the generator makes mistake, and if there infinitely many switches the adversary enumerates some language Loo that is the collection.
To illustrate the generality of these conditions, present another family of language collections C2, C2,..... . oo that are individually generatable, but whose union not generatable. Let the domain be X = N x N. Fix an index E N. We begin by defining L; Each language L E L; is parameterized by i finite subsets A AI, ,
AA 1 A "ill....,,AA],, < oo and A-1, A1 A,1 N)
Given the finite sets A 1, Al, Ag, A S N, the corresponding language L in &; is defined as follows:
U
U
(1:00)
U (OM) U {(-1,)) REA_1
L
k=1 tEA,
Next, define Loo: Each language Loo parameterized by a countable collection finite subsets
A2l. A1, |A-1, / < oo and A-1, A2, C N).
Given finite sets A A1, A2,
C N, the corresponding language L in ooo is defined as follows
L
U 1=1 REA;
((s,0) u U {(-1,8)
Note that the last union is over elements not belonging to A- Hence, each language Loc- contains all but finitely many elements of the form (-1,j) (for N). This, in particular, ensures that Loo can be trivially generates: e.g., it suffices to output element (-1,t) in the (-th iteration.
Remark A.3. Consider the collection L = U A U Loe Having described this collection, it is not hard to show that a direct adaptation of our approach in the main result goes through. We can group these collections in a natural way, e.g., by having Loc, L1, L3, Ls...., in one group and L2, L4...., the other. Then, the lower bound follows by picking an enumeration that alternates between these two collections, as described above.
14

---

B Proofs
B.1 Proof of Theorem 3.1
In this section, we prove Theorem 3.1 We first state a more detailed version of the theorem.
Theorem B.1. Let Σ- and & = 1 U22 where
xc, B 2+, B 20) == (LAB = (Z- (2-))=)ZZ ( A
L1 (LA. = = A A5
oc, B C E+, [ < x0)
Then, L1 are trivially non ciin-unffrrlly generatable and & is not generatable.
Proof. Notice that every language A, in &1 contains all the negative integers except for the finite set A and all of the positive integers except for the infinite set B. The languages in L2 are defined symmetrically. Hence, the algorithm simply by just omitting increasing prefixes the positive integers (symmetrically for L2-)
generate from L2 without observing any input samples
Next, show that & L1 U L2 is not generatable. Assume, towards contradiction, that there exists a deterministic generating algorithm
G = ( .2...)
that generates from & in the limit. We now describe an adversarial strategy that constructs an enumeration = [1, W2.... of a target language K such that the generator makes infinitely many mistakes.
To simplify the notation define the following sets:
Sia and ST denote the sets of positive and negative numbers enumerated up to time t, respec- tively, i.e., S {wi,.... W. n Z4; S = {wI..... W.} } n Z_:
Pr be the set of positive integers outputted by the generator in rounds through t.
The adversary's 's construction is organized into phases, each divided into two subphases.
Phase 1. This phase is divided into two sub-phases,
1. Subphase 1-A: In every round t, the adversary enumerates the positive integer t, i.e.,
W/ = t.
This subphase continues as long as the generator's output, given the current prefix 21, not integer greater than t. If there is first round t for which
,,,,,
(1, 21., .) Z+ (1)....t).
then subphase 1-A ends, and we move to Subphase 1-B. If the generator never deviates (i.e., never outputs integer greater that (1....,f()) f.), then the enumeration F. for the language K = N, and N L2. Moreover, by definition, the generator makes infinitely many mistakes (because it
is complete
produces unseen element of K).
2. Subphase 1-B: Let t denote the first time step which we enter this subphase. In every round that we are this phase, the adversary enumerates the negative integer
W:
t
This subphase continues until the first time t at which the generator outputs negative number that is smaller than the current wt. i.e.,
(S E Z_ and (St)) < wt.
If no such round occurs, then the final enumeration E will be complete for some K E L1, since it consists of all negative integers and finite number of positive integers, and the generator will have made infinitely many mistakes.
15

---

Phase 1s (k 2 2), After the end of Subphase (k-1))B, the adversary alternates the strategy as follows:
Subphase k-A: Let & be the first time of Subphase k-A. The adversary first enumerates fresh positive number defined by
Ph + max : a E S P
Then, in every round = 1x, le 1, during this subphase, the adversary enumerates
W/ Pk + ( 166-ta) tx),
thereby listing an increasing sequence of fresh positive numbers. This subphase ends when, for the first time, the generator outputs positive number (given the current prefix) that exceeds the maximum of the current enumerated positives. An identical argument to the one we used for subphase 1-A shows that if this subphase never terminates, then the generator makes infinitely many mistakes and the adversary gives a complete enumeration of a language from L2-
Subphase k-B: After completing Subphase k-A, the adversary enters Subphase k-B. In every round during this subphase, the adversary enumerates the number
Wi min S, 11,
introducing fresh negative number. This subphase ends the first round when the generator outputs a negative number that less than wy. An identical argument to the one we used for subphase 1-B shows that if this subphase never terminates, then the generator makes infinitely many mistakes and the adversary gives a complete enumeration of a language from L1.
Let assume that infinitely many of the phases executed. Then, the target language is K z_ U A, where A C N, is determined by the elements enumerated during the subphases k-A, N, hence it is valid language from & Moreover, notice that every time we transition from subphase k-B to (k + 1)-A, then the generator makes a mistake because the element outputted is included the constructed enumeration.
Since there are infinitely many phases, and in each phase the generator forced to err at least once, the deterministic generating algorithm makes infinitely many mistakes. This contradicts the definition of generation the limit.
Remark B.2 (Language Identification Not Closed under Finite Unions Either). It worth high- lighting that identification in the limit is not closed under finite unions either and it exhibits very similar behavior: there is a finite collection &, that is trivially uniformly identifiable and countable collection L2 that is trivially non-uniformly identifiable such that & U L2 is not identifiable in the limit. To see that, let L1 = [N} and L2 {4 = (l,...,,7 i), N}.
B.2 Proof of Theorem
We first restate a more detailed version of the theorem for completeness. Theorem B.3. Let E and let = L1 U L2 where
L (LA Z A: A 3
L2 =
- 1} (Z+ - B < <0)
:)
Then,
L is uncountable and trivially uniformly generatable,
L2 is countable and trivially non non-uniformly generatable, and
no deterministic generating algorithm G = (G1, G2....) can generate from & in the limit.
Proof. Notice that every language LA in 11 contains all the negative integers and some subset A of the positive integers. Hence, Dree, Z_. which implies that an algorithm can generate from L without using any input samples, by simply outputting negative integers. Regarding L2. notice that every language T.,B contains the first negative integers and all positive integers except for the finite set B. We claim that for any such language L,B, the algorithm that just outputs number
16

---

(1.2....) achieves generation in the limit, without requiring any imput samples from L. To see that, notice that since B is finite has some maximum element, denoted by zn. Notice that +11 the algorithm will generate a valid element
(24 \ (1..... xn)) S B. Thus, at timestep / and will keep generating valid elements from that point on. Hence, L2 is trivially non-uniformly generatable. He next show that & &1 U Lg is not generatable. The proof of this uses an analog of the diagonalization argument in Theorem 3.1 We produce the complete argument below.
Assume, towards a contradiction, that there exists deterministic generating algorithm
G (G), G
that generates from & in the limit. We now describe an adversarial strategy that constructs enumeration = W1 W2,... } of a target language K such that the generator makes infinitely many mistakes. For clarity, let:
- and St denote the sets of positive and negative numbers enumerated up to time t, respec- tively, i.e., S [wi..... w/} n Z+, S = {wi..... W/ n Z-;
Pt be the set of positive integers outputted by the generator in rounds through t.
The adversary's construction is organized into phases, each divided into two subphases.
Phase
1. Subphase 1-A: In every round the adversary enumerates the positive integer i,, i.e.,
We
This subphase continues as long as the generator's output, given the current prefix (1, (1.2...., ,)), is not integer greater than f. If there first round for which
.., 1) E Z+ (1,...,,)
then subphase 1-A ends, and we move to Subphase 1-B. If the generator never deviates (i.e., never outputs an integer greater that {1...., t)), then the enumeration E = {1,2,3, ......... is complete for the language K N, and L2. Moreover, by definition, the generator makes infinitely many mistakes (because it never produces unseen element of K).
2. Subphase 1-B: Let 1 denote the first time step at which we enter this subphase. In every round that we are in this phase, the adversary enumerates the negative integer
Wt = - 1
This subphase continues until the first time at which the generator outputs negative number that is smaller than the current Wt, ie..
Go (S,) Z_ and (S,) < wt-
If such round occurs, then the final enumeration E will be complete for some K Lr, since it consists of all negative integers and a finite number of positive integers, and the generator will have made infinitely many mistakes.
Phase ls (k 2 2). After the end of Subphase (I--) the adversary alternates the strategy as follows:
1. Subphase k-A:
Let to be the first time of Subphase k-A. The adversary first enumerates a fresh positive number defined by
Pk = 1 + max x E St U P.,)
Then, in every round = lx. l + 1,... during this subphase, the adversary enumerates
P + (t - tx),
thereby listing an increasing sequence of fresh positive numbers.
17

---

This subphase ends when, for the first time, the generator outputs positive number (given the current prefix) that exceeds the maximum the current enumerated positives. identical argument to the one we used for subphase 1-A shows that if this subphase never terminates, then the generator makes infinitely many mistakes and the adversary gives complete enumeration of a language from L2-
2. Subphase k-B:
After completing Subphase k-A, the adversary enters Subphase k-B, In every round during this subphase, the adversary enumerates the number
te min ST - 1,
introducing fresh negative number.
This subphase ends at the first round when the generator outputs negative number that is less than wt. An identical argument to the one we used for subphase 1-B shows that this subphase never terminates, then the generator makes infinitely many mistakes and the adversary gives a complete enumeration of a language from L1.
Let now assume that infinitely many of the phases executed. Then, the target language is K = z_ U A, where A C N, is determined by the elements enumerated during the subphases k-A, N, hence it is valid language. Moreover, notice that every time transition from subphase k-B to (k + A),A, then the generator makes mistake because the element it outputted is not included the constructed enumeration.
Since there are infinitely many phases, and in each phase the generator forced to err at least once, the deterministic generating algorithm makes infinitely many mistakes. This contradicts the definition of generation the limit.
B.3 Proof of Theorem 3.3
In this section, prove Theorem 3.3
We begin by stating more detailed version of Theorem 3.3
Theorem B.4. Let E = Z and let
= (==
Then, is is uncountable and trivially non-uniformly generatable but it does not satisfy the EUC property.
Proof. For each one of uncountably many subsets B Z & contains a language (e.g., Z_ B) and, hence, L is uncountable collection. To see that & is trivially non-uniformly generatable notice that, since every E C omits only finitely many negative integers the algorithm that in every round I generates the largest element from the set O, {i __, i -t, g S, generates in the limit. In fact, this algorithm generates in the limit in the modified setting where S, = for all rounds t, hence it is trivially uniformly generatable.
We now show that & does not satisfy the EUC property. Consider any target language K and S any set of elements of K. Consider the induced version space V(C, St), i.e., the set of languages from L containing S.- Assume that OLeV(c,s.) + S, for some Then, there exists some Te NLEViC.S.) L such that v, & Sy. Consider the language L = Z__ \ {xr) Then, S, C L and Ie L, hence this show that (E.S.) = S₁ (violating the EUC property).
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide proofs of the claims make in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contri- butions made in the paper and important assumptions and limitations. A No or NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals motivation as long it is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss how our results operate a stylized mathematical model and how a complete characterization of learnability within this model is still lacking.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificatton, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
19

---

Justification:
We have defined precisely the mathematical model under which our results hold and have given proof sketches of the approaches to get the results. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems. The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
No experiments are included.
Guidelines:
The answer NA means that the paper does not include experiments. the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e-g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may be
While NeurIPS does not require releasing code. the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
20

---

Answer:
[NA]
Justification:
No data or code is used.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https
Sawpaidde//odeeuumiissseseee onPoiccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyperparame- ters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main
claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar the standard deviation or the standard error the mean.
21

---

It is OK to report 1- 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, if the hypothesis Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are of range (e.g. negative error rates). error bars are reported tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Answer: [NA]
Justification: Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
We have followed the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is special consideration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is theoretical and the results hold under mathematical model. Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), faimeess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
22

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We do not release any models or data.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do not use such assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ hommdatasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
23

---

Researchers should communicate the details of the dataset/code/model part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: No such study was conducted for the paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements your country institution) were obtained?
Answer: [NA]
Justification: The paper does not invlove such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage LLMs if it an important, original, non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We only used LLMs for text editing.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https://neuriin http:/pppsppppooooeee/neee/////a 22MMLLMM) for what should or should not be described.


Reviews:
[{"review_id": "acrmfkYI2N", "reviewer": "Reviewer_dkh6", "summary": "This paper investigates the theoretical foundations of language generation in the limit, a setting introduced by Kleinberg and Mullainathan (2024) and extended by Li et al. (2024). The authors focus on the union-closedness properties of generatable language classes, addressing three open questions posed by Li et al. Specifically, they show that the class of generatable (and even non-uniformly generatable) languages is not closed under finite unions, disproving the possibility of combining generators to construct a more powerful one. They further construct a minimal example where the union of a uniformly and a non-uniformly generatable class is not generatable, despite each being generatable individually. Finally, they provide a concrete uncountable class that is non-uniformly generatable but violates the Eventually Unbounded Closure (EUC) condition. This work novelty lies in a new diagonalization technique that ensures individual generatability while rendering the union non-generatable.", "questions": "Clarification on Practical Implications:\nWhile the theoretical contribution is strong, could the authors comment on whether similar non-union-closedness phenomena might manifest in practical language generation systems (e.g., autoregressive LLMs)? Any intuition or empirical proxy would help ground the theory.\n\nVisualization or Simplified Example:\nEven a toy example illustrating how a generator fails under the constructed union could greatly aid intuition. Would the authors consider including such a figure or pseudocode in the final version?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper resolves three open questions in the theory of language generation in the limit, demonstrating both depth and relevance.\n- The construction of counter examples is technically elegant and novel, especially the diagonalization argument.\n- The results reveal fundamental differences between generation and traditional learning frameworks (e.g., lack of union-closedness), which is conceptually significant.\n\nWeaknesses\n- No empirical or illustrative examples are provided to help visualize the main ideas.", "was_revised": true, "final_justification": "Thank you for the clear and constructive rebuttal. The added discussion on how finite-union non-closedness relates to practical LLM merging challenges satisfactorily addresses my earlier question on real-world relevance.\n\nI particularly welcome the plan to include an intuitive “majority-vote generator” example with figures and pseudocode. A minimal, self-contained demonstration will make the core idea far more accessible to readers outside the immediate subfield, and will strengthen the paper’s pedagogical value.\n\nGiven the strength of the theoretical contribution, the resolution of multiple open questions, and the authors’ commitment to improving clarity with concrete examples, I am raising my score from 4 (borderline accept) to 5 (accept).", "rebuttal": "Thank you for supporting our paper. We are very happy to see that you appreciated the depth and elegance of our techniques. We answer your specific questions below and hope you will strengthen your support for the paper. \n\n> While the theoretical contribution is strong…practical language generation systems (e.g., autoregressive LLMs)?\n\n That is an excellent question. Since the Kleinberg–Mullainathan model places no restrictions on generators, our impossibility result applies to autoregressive LLMs and other language generation systems. While practical data is non-adversarial (so our results don't directly apply), LLM merging has proven challenging in practice. A recent survey [1] notes that \"guaranteeing the performance of model merging remains challenging\" and requires \"[all models to be] fine-tuned based on the same pre-trained model, with careful control over parameters.\" Even then, \"there is still a significant gap between the merged and independent models.\" Our results provide principled grounds for why merging LLMs is much more challenging than merging classifiers, where methods like XGBoost and random forests succeed and are supported by theoretical results showing classification is closed under finite unions. We will include these points in the final version.\n\n[1] Model Merging in LLMs, MLLMs, and Beyond: Methods, Theories, Applications and Opportunities. Enneng Yang, Li Shen, Guibing Guo, Xingwei Wang, Xiaochun Cao, Jie Zhang, Dacheng Tao.\n\n> Would the authors consider including such a figure or pseudocode in the final version?\n\nThank you for the suggestion. We will add examples with figures and pseudocode illustrating how natural generators fail on the constructed union. Here's one example:\n\n*Majority-Vote Based Generator.* A natural strategy for generating from $\\mathcal{L}_1\\cup \\mathcal{L}_2$ is combining generators for $\\mathcal{L}_1$ and $\\mathcal{L}_2$, similar to how boosting combines weak learners in classification.\nThis can be done in several ways. For instance, one approach is to run the generators independently and define a “scoring” function which is used as a proxy for which generator is “most successful” so far and using the output of the “most successful” generator. Since one generator makes infinitely many mistakes and the other only finitely many, one would hope that there exists a natural scoring function that will detect the one that makes finitely many mistakes. A concrete example of such a function is to count the number of (provably) correct generations a generator has made so far. Indeed, whenever a generator outputs a valid string, this string will appear at a finite time in the input stream, so we can compute such a function from data. Unfortunately, this scoring function and its natural variants failed. In fact, that result shows that no such scoring function could exist. We will include details on this (along with figures and pseudocode) in the final version."}, {"review_id": "Cf6sMWMbIf", "reviewer": "Reviewer_HnRj", "summary": "This paper shows that generatable language classes are not closed under union, and resolves other open questions about the nature of language generation in the limit.", "questions": "Typo on Line 82 (extra period inserted after \"language\")\n\nEquations after 366 defining $L_1'$ and $L_2'$ \nshould have $A \\subseteq Z_-$ and $B \\subseteq Z_+$ (signs are flipped).\n\nThe authors posit that the non-closure under union has consequences for the generation equivalent of boosting. This seems like an important finding, but it is not yet clear to me what \"combining generators\" looks like. Does this apply to *learning* generators, e.g., training LLMs? Or does it have implications for things like ensembling pretrained LLMs at inference time? I'd love to see more discussion here.\n\nI would also like to hear more about how this results shows how hard *characterizing* generatibility is... does this mean that generatability might not be a very useful framework for understanding language learning because it has difficult properties? Or is it still useful despite its challenging properties?", "limitations": "The authors might include a section clarifying their views on how *practically* useful their results are. Overall, I do not see negative societal impact from this kind of theoretical work.", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The paper is surprisingly easy to follow, and is well organized pedagogically. I enjoyed reading it.\n\nIn terms of significance, this paper is exciting because it establishes an important difference between statistical learning and language generation. This has important theoretical implications, though it is unclear what the practical implications will be. \n\nThe proof sketch provided in the main text appears to be correct, as far as I can tell.", "was_revised": true, "final_justification": "My questions were adequately addressed (specifically, questions about the implications of the findings) and I am happy to recommend this paper for publication.", "rebuttal": "Thank you for the strong support of our paper. We are happy to see that you found the paper easy to read and significant. We respond to your specific comments and questions below and will include this information in the final version.\n\n> Typos.\n\nThank you for reading the paper carefully, we will fix all of them.\n\n> Does this apply to learning generators, e.g., training LLMs? Or does it have implications for things like ensembling pretrained LLMs at inference time?\n\nOur view is that our result's main implication is for training LLMs: it shows that unlike classification, LLM training cannot always be divided into simpler sub-tasks where we train separate models and then combine them (as is possible with XGBoost and Random Forests in classification). For instance, to train a model for $\\mathcal{L_1} \\cup \\mathcal{L_2}$, one might train two models in parallel – one for $\\mathcal{L_1}$ and one for $\\mathcal{L_2}$ – then merge them.  Our result shows this approach isn't feasible in general. \n\nPerhaps the most closely related practical instance involves challenges in \"merging\" LLMs. A recent survey [1] notes: \n\"In practical settings, guaranteeing the performance of model merging remains challenging\" and requires \"[all models to be] fine-tuned based on the same pre-trained model, with careful control over [parameters].\" Moreover, \"[even after careful parameter selection] there is still a significant gap between the merged and independent models.\" \nOur results offer a principled explanation for these challenges.\n\n[1] Model Merging in LLMs, MLLMs, and Beyond: Methods, Theories, Applications and Opportunities. Enneng Yang, Li Shen, Guibing Guo, Xingwei Wang, Xiaochun Cao, Jie Zhang, Dacheng Tao.\n\n> How this result shows how hard characterizing generatibility is.\n\nOur results show that any characterization of generatability must ensure that generatability is not closed under finite unions. This prohibits one from using most of the existing characterizations/dimensions in statistical learning theory (e.g., the VC dimension, the Littlestone dimension, the recent DS dimension, and many others) or their variations because all of them ensure closure under finite unions.\n\n> Does this mean that generatability might not be…useful…because it has difficult properties? Or is it still useful…?\n\nWe believe generatability is a useful notion despite having difficult properties (e.g., not being closed under finite-unions) because:\n- It arises from a simple and (arguably) natural definition (given a sequence of strings from a language, can the generator learn to generate valid and unseen strings?), and\n- It turns out to have different properties than standard prediction tasks, which suggests that studying generatability could lead to new theoretical techniques that can have other applications. \n\n> The authors might include a section clarifying their views on how practically useful their results are.\n\nThanks for the suggestion, we will use the additional page provided in the final version to include this section; please see our response to ``Does this apply … inference time?’’ above."}, {"review_id": "Z6qYgTBLxi", "reviewer": "Reviewer_B1o9", "summary": "The paper studies language generation in the limit (LGitL), the on-line model introduced by Kleinberg & Mullainathan (2024) and refined by Li et al. (2024).\n\nWhere previous work showed that every countable collection of languages is generatable, the authors focus on finite unions of (possibly uncountable) collections and prove three main theorems:\n\n1. Non-closure under finite unions (Thm 3.1). They construct two uncountable, non-uniformly-generatable collections L1,L2L1​,L2​ whose union is not generatable.\n\n2. A \"minimal\" counter-example (Thm 3.2). They sharpen the above by making L1L1​ countable and L2L2​ uniformly generatable (and generatable without seeing any data) while their union remains non-generatable.\n\n3. Non-uniform generation without EUC (Thm 3.3). They give an uncountable class that is non-uniformly generatable yet violates the Eventually-Unbounded-Closure property, answering an open question of Li et al.\n\nTechnically, the work introduces a two-sided, phased diagonalisation argument that alternates mistakes across even/odd rounds, carefully ensuring that each collection on its own is easy, yet their union defeats any generator. The construction relies on highly artificial languages such as \"(almost) all negative integers union an infinite co-finite subset of the positives.\"", "questions": "I'm not really an expert in this space, so my questions aren't great. \n\nPrimarily I'm interested in if there is going to be more discussion of the claim that ensembling LLMs doesn't work.", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n\nThis paper tackles a natural and previously open question in the theory of language generation in the limit: whether the class of generatable collections is closed under finite union. The authors answer this in the negative and, in doing so, settle three distinct open problems posed by Li et al. (2024). The work is technically original! the 'phase-split' diagonalisation that alternates mistakes across odd and even rounds is genuinely clever and, to my knowledge, new to the literature. That technique not only establishes the main non-closure result but is also likely to be useful in future lower-bound constructions for language-generation theory. The paper demonstrates solid depth too... the constructions simultaneously keep each collection individually easy to generate from while making their union provably impossible. The authors situate their results well within the recent surge of work on LGitL, giving readers a clear map of what was known and what remained mysterious.\n\nWeaknesses\n\nThe paper operates in an extremely stringent model that demands eventual perfect generation. After some unknown time every output must belong to the target language. Real-world language-model ensembles are inherently probabilistic and tolerate small error rates, so it remains unclear whether the impossibility result persists in a more forgiving, approximate-generation setting. A related concern is the artificial nature of the language families used in the proofs. They are built from sets such as 'all non-positive integers plus an infinite co-finite subset of the positives', which bear little resemblance to natural language or even to the customary formal languages of automata theory. It is therefore an open question whether the same pathology could occur for structured families like regular or context-free languages. In addition, while the authors motivate their study with the prospect of combining large language models, the perfect-generation assumption severs most practical connections, and the paper does not examine approximate or probabilistic ensemble strategies that practitioners actually use. Finally, presentation could be smoother: notation for phase indices is heavy, several typos remain, and some late-section forward references disrupt the reading flow. Addressing these points would significantly strengthen both the accessibility and the practical relevance of the contribution.\"", "was_revised": true, "final_justification": "I raised my scores in response to the thoughtful feedback from the author. I acknowledge my relative ignorance in this space compared to others (low confidence)", "rebuttal": "Thank you for your careful review. We are happy to see that you found the techniques clever and likely to be useful in the future. Please find our responses to your comments below.\n\n> Stringent model that demands eventual perfect generation.\n\nWhile we agree that the model might initially seem stringent, there have been several surprising positive results in this model: [KM’24] showed that all countable collections are generatable, [RR’25] extended this to the “noisy” setting, and [PRR’25, KW’25] demonstrated that generation “with breadth” can be achieved in this model. Given these positive results, one might expect that finite unions of generatable classes are generatable, but our result shows that this is not the case. We believe this reveals a fundamental limitation that is relevant to the NeurIPS community, especially given the recent positive results on language generation published at NeurIPS and ICML.\n\n[KM’24] Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. In Advances in Neural Information Processing Systems, Volume 37, 2024\n\n[RR’25] Ananth Raman and Vinod Raman. Generation from noisy examples. In Forty-second International Conference on Machine Learning, 2025\n\n[PRR’25] Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation. In Forty-second International Conference on Machine Learning, 2025\n\n[KW’25] Jon Kleinberg and Fan Wei. Density Measures for Language Generation. In IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS).\n\n> Whether the same pathology could occur for structured families like regular or context-free languages.\n\n Exploring whether non-union closeness could occur for more structured families and understanding which properties of the language collections lead to closeness under unions is an interesting open question left by our work. That said, the complicated nature of the families in our lower bound is perhaps expected since the model of language generation gives generators substantial power: there are no computational restrictions and no bound on the amount of training data used by them. It is possible that once one places computational restrictions and bounds on the training data, then non-union closeness could be witnessed by simple families; and this is also an interesting open question.   \n\n> Perfect-generation assumption.\n\nPlease see our response to the first question above.\n\n> Presentation … addressing these points would significantly strengthen … accessibility.\n\nThank you for the suggestions, we will fix the typos, referencing errors, and simplify notation in the final version.\n\n\n> In addition, while the authors motivate their study with the prospect of combining large language models, the perfect-generation assumption severs most practical connections, and the paper does not examine approximate or probabilistic ensemble strategies that practitioners actually use\n\nA strength of the Kleinberg–Mullainathan model is that it places no assumptions on the generators – neither architectural nor computational. At this level of generality, theoretical results inevitably require assumptions like perfect-generation. \nNevertheless, we believe our core insight that \"merging\" LLMs is fundamentally difficult could remain valid in practice: here, our result shows that unlike classification (where methods like XGBoost and Random Forests can divide tasks into simpler sub-problems), LLM training cannot always be decomposed this way. For instance, one might hope to train separate models on $\\mathcal{L_1}$ and $\\mathcal{L_2}$, then merge them to handle $\\mathcal{L_1} \\cup \\mathcal{L_2}$ – but our result shows this approach is not feasible in general.\n\nThis, perhaps, offers a principled explanation for challenges in “merging” LLMs in practice. For instance, a recent survey [1] notes that \"guaranteeing the performance of model merging remains challenging\" and requires models to be \"fine-tuned based on the same pre-trained model, with careful control over parameters.\" Even then, \"there is still a significant gap between the merged and independent models.\n\n[1] Model Merging in LLMs, MLLMs, and Beyond: Methods, Theories, Applications and Opportunities. Enneng Yang, Li Shen, Guibing Guo, Xingwei Wang, Xiaochun Cao, Jie Zhang, Dacheng Tao."}]

Author rebuttal:

Meta-review: This is a theory paper that proves that in the Kleinberg-Mullainathan model of language generation in the limit, generatable classes are not closed under finite union, resolving three open questions. The technical core, a two‑sided phased diagonalization that forces mistakes on alternating rounds while keeping each side individually easy, seems potentially useful beyond this work. Reviewers converged positive but with low confidences, but strong substantive praise. The authors' rebuttal addressed clarity and implications and committed to adding an intuitive toy example and tightening presentation. The main drawback is external relevance: the model is exacting, the languages are artificial.
Decision: Accept (poster)