Language Generation in the Limit
Authors: Jon Kleinberg
Sendhil Mullainathan
Venue: NeurIPS 2024 spotlight (2024)
Keywords: language generation
large language models
enumeration
Primary area: learning_theory
TL;DR: In a theoretical model, we show that language generation is always possible in the limit, in contrast to classical impossibility results for language identification in the limit.

Abstract: Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings from the language that don't already appear in the training data. Here we ask what we can conclude about language generation using only this specification, without further assumptions. In particular, suppose that an adversary enumerates the strings of an unknown target language L that is known only to come from one of a possibly infinite list of candidates. A computational agent is trying to learn to generate from this language; we say that the agent generates from $L$ in the limit if after some finite point in the enumeration of $L$, the agent is able to produce new elements that come exclusively from $L$ and that have not yet been presented by the adversary. Our main result is that there is an agent that is able to generate in the limit for every countable list of candidate languages. This contrasts dramatically with negative results due to Gold and Angluin in a well-studied model of language learning where the goal is to identify an unknown language from samples; the difference between these results suggests that identifying a language is a fundamentally different problem than generating from it.

Language Generation in the Limit
Jon Kleinberg
Sendhil Mullainathan
Departments of Computer Science and Information Sciene
Booth School of Business University of Chicago Chicago
Cornell University Ithaca NY
Abstract
Although current large language models are complex, the most basic specifications the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings from the language that don't already appear the training data. Here we ask what we can conclude about language generation using only this specification, without further assumptions. In particular, suppose that an adversary enumerates the strings of an unknown target language L that is known only to come from one of a possibly infinite list of candidates. A computational agent is trying to learn to generate from this language; say that the agent generates from L in the limit if after some finite point the enumeration of L, the agent is able to produce new elements that come exclusively from T. and that have not yet been presented by the adversary. Our main result is that there is an agent that is able to generate in the limit for every countable list of candidate languages. This contrasts dramatically with negative results due well-studied model of language learning where the goal
to Gold and Angluin is identify an unknown language from samples; the difference between these results suggests that identifying a language is fundamentally different problem than generating from it.
Introduction
The recent advances in large language models (LLMs) have been remarkable, sparking active lines of theoretical work into their performance. These investigations implicitly revolve around two fundamental questions: how do we formally reason about the effectiveness of LLMs; and within such framework, what the ideas mathematical level that enable their performance?
Answers to these questions must begin by formalizing the specification for what a generative algorithm for language should be doing. Here, we propose starting from very basic, assumption Sruum, statement for such a specification: there is an unknown target language L, over time the algorithm sees a sequence of strings from L, and eventually would like the algorithm to generate new strings from that it has not seen before |
Viewed this way. it is also clear why it seems so remarkable for LLMs to be doing well at such problem. The fully general statement of the problem feels vnsolvable: if we know nothing about the unknown target language L., then how can generative algorithm reliably produce valid strings from that it hasn't it seen before?
will formalize these concepts more precisely below, now we can think a language as simply any set of strings over fixed alphabet; for example, the strings of the language could be the set of all grammatical sentences (or all well-formed expressions) according a given grammar.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Language Learning in the Limit. In fact, there is well-established formalism that allows us to phrase this point precisely: the classical model of language learning the limit, formulated by Mark Gold in 1967 and fully characterized by Dana Angluin in 1980 6 2 In this model, there is an unknown language K that is known only to be produced by one of list of candidate representations R1, R2, R,...., where I, is the language produced by representation R. We can think of this list of representations as the set of all possible context-free grammars, or the set of all possible finite automata, or the set of all Turing machines with fixed space bound, or any other generative model that produces strings; in fact, the formal result is much more general than this, in that it is sufficient to suppose that the unknown language K simply comes from countable list of candidate languages L1, L2, Lg...., and we can dispense with explicit representations altogether
In the Gold-Angluin model, an adversary enumerates the strings of K one by one. and the algorithm is required after each new string to guess language I,, from the list such that L. = K. If there is some finite step i after which the algorithm's 's guess is always correct, then we say the algorithm has identified K in the limit. Gold proved that this is impossible in general, even for simple language families such as the regular languages (i.e. those produced by finite automata), and Angluin characterized precisely those families for which it is possible, further establishing how limited they are [1 21. Note, crucially, that in the Gold-Angluin model, the adversary enumerates strings in K, but does not provide examples of strings that do not belong to K, nor does it allow the algorithm to ask questions about string's 's membership in K; their point with this formalism was to focus cases where an agent tries inferring a language purely from seeing a sufficient number of examples of strings that belong to the language. (In Section A.I] we provide self-contained proof of the negative result for identification in the limit; while not strietly necessary for our results, we find it provides useful background and context for the problem.)
Language Generation in the Limit. These negative results of Gold and Angluin feel intuitive - how should we be able to identify a language from a finite sample when we are allowed to make essentially no assumptions about its structure? Because of this intuition, both via the Gold-Angluin model and for more informal reasons as well, the focus in language generation has naturally turned to distributional assumptions; one posits that large language models are so effective because they are able to exploit distributional probabilities of language, and from finite set of samples they are able to estimate conditional probabilities of strings with increasing accuracy. In this way, the question moves from adversaries to probability distributions, and one seeks explanations for the effectiveness of LLMs through underlying probabilistic models.
Our Results:
In this paper, we offer a sharply different view: we show that in the Gold-Angluin model of adversarially produced examples, language generation is always possible. We will provide full details on the result and its proof beginning in the next section, but the key point at high level is that even in an adversarial model with an unknown language K, language generation is fundamentally different task than language identification: where identification asks an algorithm to eventually name a language L, K after seeing a large enough finite sample S from K, generation instead asks an algorithm to eventually output strings in K- - S after seeing a large enough S from K. Our main result that this difference in specifications leads to dramatic differences what is possible in the limit; whereas the Gold-Au Angluin results establish that identification in the limit is impossible except in highly constrained cases, we show that generation in the limit is possible for every countable list of candidate languages.
General Connections to Language Modeling. Our approach emphasizing theoretical properties of language generation and worst-case guarantees, in the style of the Gold-Angluin model, is a source of limitations but also source of generality; it is therefore important to discuss how we draw stylized insights about language modeling from our theoretical formalism. Clearly, methods to design large language models in practice make extensive use of the empirical distributional properties of language, as they should. Our results don't It question this design methodology; when there are genuine empirical regularities in the training data, there is no reason not to use them. Rather, our results argue that if we are looking for the essential reasons why language generation is tractable, we do not fundamentally require any empirical regularities, indeed any probabilistic assumptions at all; there is instead a formal sense in which language generation - unlike broader learning tasks such as language
'In this more general view, we will assume that the family of languages is presented simply via a black box that for string w and an index i can answer the question. "Is L
2

---

identification - is possible even against an adversary presenting positive training examples in worst-case fashion. In some essential way, the generation problem is therefore different from these other learning tasks in crucial ways that more detailed formalisms may potentially obscure.
Despite the generality of the model, producing the generation algorithm that proves our main theorem makes use of subtle structural properties of the given list of candidate languages. Again, we defer any detailed description to the subsequent sections, but the idea a high level is maintain a sequence of "provisional languages" among the candidate languages that are consistent with the finite sample S from K seen so far, and to continually refine this sequence of provisional languages as the adversary adds more strings to the sample S. Since the Gold-Angluin result says that the algorithm can never be sure which is the true language K, there is a sense in which this refinement process essentially needs to continue indefinitely, and in general it leads the algorithm to generate from provisional languages that may be increasingly "thin" subsets of K. This does not cause trouble for the specification of language generation, since it is acceptable to produce any unseen string from K, but it does mean that while the algorithm is able to eventually produce an infinite sequence of unseen strings from K, in general it might do so from narrow part of K.
This property of the solution in the presence of an adversary suggests interesting connections the problem of generation in practice as well. In particular, any method for generation has to deal with an underlying validity problem - producing valid outputs and an underlying breadth problem producing outputs that represent the full range of valid outputs in some reasonable way. The breadth problem notoriously difficult, and manifests itself in numerous ways in the methodology of machine learning and generative models. The approach that proves our main result helps illustrate the tension between validity and breadth even in settings with worst-case assumptions rather than probabilistic ones, and this tension shows up in both the early phases of our algorithm's 's execution and the later phases. In the early phases, before the algorithm has refined its provisional language sufficiently, it is generating too broadly and producing strings that are not part of the target language K an analogue at a high level of a kind of hallucination in which the generated strings belong to some consistent candidate language, but not to the actual target language 77 8 [T] In the later phases, on the other hand, the algorithm continuously shrinks its range of possible outputs so as to ensure that they will be contained within K - sacrificing validity for breadth in manner analogous to the issues that arise in the problem of mode collapse for generative models B 4.. Our model therefore suggests interesting questions about the fundamental trade-offs that may exist between validity and breadth even in settings without an underlying probabilistic model.
2 Formal Model and Results
We now provide formal description of the model and the statement of our results. To begin with, we have a countable list of candidate languages C- [Ta, T,2, .... where each T,; is subset of some countable set U. All we assume about the list of languages is that it is specified through black box that can answer questions of the form "Is w E L;?" for any string w E U and language L, E C. (If the reader finds it helpful for concreteness, they can consider the results that follow in the context of a specific list of languages C, such as the set of all context-free languages or the set of all regular languages; but everything we say applies to general collections of languages.) We will allow the collection C to contain repetitions, in that we may have L, = L, for different indices and j. We will assume that all the languages L, are infinite; while the original Gold-Angluin framework did not require this, it becomes important in specifying the generation problem: if we require an algorithm to output unseen strings forever, then this is not possible from finite language, where the algorithm would eventually run out of new strings to generate.
An adversary and an algorithm now play the following game. The adversary chooses a language K from C without revealing it to the algorithm, and it begins enumerating the strings of K one by one over a sequence of steps & 1, .... The adversary can repeat strings in its enumeration, but crucially, for every string w E K, there must be at least one time step t in which w appears. Let St be the set of strings that the adversary has enumerated in steps I through t.
Identification and Generation. In this framework, we can now specify both the Gold-Angluin problem of identification and the contrasting problem of generation that we study in this paper.
3

---

Identification (from 16 In each step, the algorithm observes S, and must output an index (its guess for the true language K). The algorithm identifies K in the limit if there is some 1." such that for all steps 2 (", the algorithm's ' guess in step & is an index i for which I,, = K.
Generation (from the present paper): In each step, the algorithm observes S. and must output a string the limit if there is some t* such that for all steps t 2 t", the algorithm's 's guess ar belongs to K St.
dt (its guess for an unseen string in K). The algorithm generates from K in
A key point in both problem formulations is that the algorithm is not told if its guesses are correct.
We know from the Gold-Ange Aoglu-n results that there is no algorithm that can achieve identification in the limit for an arbitrary countable collection C languages (or even for specific countable collections, like the set of all regular languages or the set of all context-free languages). Our main result is dramatically different answer for language generation; it is possible for every countable collection:
(2.1) There is algorithm with the property that for any countable collection of languages C C= (-, L2. L......, and any enumeration of one of these languages K, the algorithm generates from K in the limit.
A Result for Finite Collections. We prove a second result as well, focusing on the variant of the problem in which the collection of languages C is finite. In this case, follows from Angluin's characterization that every finite collection C' allows for identification in the limit. Given this, what more might we ask for? A natural question is whether there is a uniform bound on the number of samples needed to ensure that the algorithm can correctly identify the true language K: for any finite collection C, there a bound t(C) and an algorithm with the property that after seeing any tCC) distinct strings from K, the algorithm is guaranteed to report K as its guess for the true language?
It is easy see that for the Gold-Angluin model of learning, this is not possible. For example, supopse that C is the collection consisting of two languages L, and Lg: L, consists of all possible strings, and L2 consists of all strings of even length. Suppose there were a bound ((C) and an algorithm that was guaranteed to guess correctly after seeing (CC) distinct samples. Then an adversary could present (CC) distinct strings of even length, and then ask the algorithm to guess whether the true language Lı or Ly: if the algorithm guesses L2 at this point, then the adversary could announce that the answer is L1, and conversely if the algorithm guesses L1. This does not prevent the algorithm from learning the true language in the limit (since the adversary must eventually output an odd-length string if the true answer is I.); but there is no fixed bound I(C) by which this can be guaranteed.
However, for the problem of generation with a finite collection of candidate languages, we can provide this much stronger type of uniform bound, via algorithm that generates correctly after seeing a finite sample whose size t(C) is specified at the outset. In fact, we can achieve more: after seeing this finite sample, the algorithm can generate an infinite sequence of unseen elements from the true language.
(2.2) There is an algorithm with the property that for any finite collection of languages C, there is a number ((C), such that for any language K in C, and any sequence S of at least t(C) distinct elements from K, the algorithm can produce an infinite sequence of distinct strings from K S.
In subsequent work building on the present paper, Raman and Tewari [T0 have recently proved further results about the type of uniform generation that consider in (..2). when it is possible to put an a priori bound tCC) on the number of distinct strings an algorithm needs to see from K before it can be guaranteed to begin generating unseen strings from K. They also consider variants of this definition, situating their analysis in the framework of classical learning theory.
Extensions and Generalizations. Following these two main results in our basic model of gener- ation, we provide (in Section 7) the following generalization of the model. Specifically, familiar issue from language generation applications the role of the prompt: user provides an input string p, and a generation algorithm is then supposed to produce "continuation" string to come after the prompt, so that the concatenation of p and e valid utterance. We offer an extension that incorporates the notion of prompting, while maintaining the basic structure of the model, and we show how to formulate and prove a generalization of our first main result (2.T) in setting where at each time step the adversary is allowed to specify prompt that must be completed.

---

3 An Approach to Generation that Doesn't Work
The following section is important, because it describes an approach that is arguably the most natural non-trivial attempt at achieving language generation in the limit. It seems at first seems to solve the problem directly, but in fact it fails for a deep reason that is important understand, since motivates the more involved solution that follows.
The strategy to move through the list of languages C [L1, L2, Lg,...) } in order, treating each language L; as hypothesis for K until the sample St proves otherwise. That is, we start with Lt, and we generate strings from I St until encounter (if ever) step / in which S. I Ia- At this point we know that I,2 cannot be the true language K, and so we continue the process from L-2- The nice idea that underpins this strategy is that the true language K is equal Lg for some index 2. (Since C' can contain repetitions, K might appear several times, but we can take L2 as the first appearance.) So if our process were reach L,- at some step t", it would never move on from L., and so we would be generating from K - Sy for all t 2 t".
Unfortunately, there is deep problem with this approach: there may be language L; C with the property that Le comes before L2 and La properly contains L2 (that is, i < z, and 12 Ç Lj). In this case, our procedure would stop at the first such L2 forever, since it would never encounter string in S, that didn't it belong to L.- And when it generated from L - S,, there is no guarantee that it would choose strings from T.g-
This problem is not casily avoided, since if this approach worked as written, it would also solve identification in the limit, which we know is impossible. So need to extract some of the useful ideas from this failed approach- - in particular, the trick that K appears at some finite point in the list C, as the language L but add important further ideas well. Specifically, if the algorithm is maintaining hypotheses for the true language K over time, it can provably never know whether its current hypothesis is correct; instead, it must be always moving further down the collection of languages, potentially considering languages that are not K, but in such a way that it is eventually always generating from K St.. This is what our proof beginning in the next section will have to accomplish.
4 Generation in the Limit via a Function
We prove our main result in two parts. We first give a method for language generation in the limit that is not concerned with the computational power required by the agent performing the generation. Thus, rather than an algorithm to generate the string, we ask whether we can construct a function fc based on the given language collection that maps a finite set of strings to new string; this function takes the strings St seen so far and outputs a string fc(S,) intended to be in K Sy. We will prove the following:
(4.1) For every countable collection of languages C, there is a function fc from finite subsets of U to elements of U, such that for every enumeration of a language K E C, there is a t" such that for all t 2 t", we have fc(S.) E K St-
Note that while this positive result is not concerned with the computational power required to evaluate fc. it already contains the core contrast with language identification, which remains impossible even if we simply ask for function fc. In the next section, we will then go on to prove (2.1) by using an algorithm that only performs standard computational steps and membership queries of the form "w E L,?"
Minimal and critical languages. As before, we will suppose 2 is an index such that Lg K. We say that a language L; is consistent with the sample at step if S; C L,. An important idea, which is implicit in our discussion of the failed approach at the end of Section 2 that if Lg S L, are both consistent with S,, then it is safer for an algorithm to generate from L; than from Ly: if w E L, S, then we must also have w E L, St. This suggests that would be useful to find consistent languages that are minimal with respect to inclusion: we would say that L is minimal if L E C is consistent with S., and also L C L' for every L' E C that is consistent with S.. Unfortunately, this is too much to ask for, since there exist instances of the problem for which there might not be any languages that (In a finite collection of language there would need to be a minimal language, but it is easy to construct infinite collections without one.)
are minimal with respect to inclusion.
5

---

Therefore, we define a related concept that only involves examining the inclusion of a given language with respect to finite set of other languages. Specifically, we look for languages L, that are consistent with St in given step 4, such that T., is subset of every consistent language that precedes it in the indexing of C. We will say that such language critical at step t. To deñine this formally, we first let Cn denote the finite collection of languages [I1,, I2..... I..). We now have the following definition.
(4.2) A language In is critical at step I. if Ln is consistent with St, and for every language I E C.. that is consistent with St, we have Ln S Li-
Properties of critical languages. At any given step there is least one language consistent with St. since the language Lg K is always consistent with S, It follows that there is also at least one critical language at any step for any t. the consistent language L3 with the lowest index i must be critical at step t, as it is the only consistent language in C,
Note that there crucial fact is that Lg will eventually become critical at some step and remain critical forever after that. For reasons of space, we provide complete proofs for this and all subsequent results in the Appendix, in this case in Section A.2
be choices of for which the language L, = K is not critical at step t. But
(4.3) There exists time step t* such for all 2 t+, the language Lg is critical step
There can be multiple critical languages at a given step I; for example, on the step 1+ in 4.3) the first consistent language L, is not equal to I.,, then both L; and I,z will be critical at step t+. Despite the potential multiplicity of critical languages, the collection of all critical languages at step has a useful nested structure: L; and Lj are both critical at step f, with i < j. then since Lj is contained in all consistent languages that precede it, in particular it is contained in Li. We therefore have:
(4.4) Let i < j. and suppose that Li and Ljj are both critical at step t. Then Lj- S Li.
function for generation in the limit. At a given step f, suppose that the critical languages are Legs Lagg Ling: ... where n1 < n2 < na < ..... (This list of critical languages might be finite or infinite.) Then (4.4) tells us that this sequence is nested by inclusion: La, 2 Lnz 2 Lng 2
By (4.3) we know that the language L, will eventually appear on this nested list from some step t* onward, but even then we do not know which index n, it corresponds to at any given step f 2 t+. Indeed, to recall point from earlier, the Gold-Angluin results for learning in the limit tell us that we can never know for sure which index corresponds to L.. But we now arrive at the crucial point, which is that beyond some finite index, all the critical languages are subsets of I.,, it is safe to generate from any of them.
Given this, we are prepared to construct our function fc.
(4.5) fc(Si) defined as follows. We first identify all languages in Ct that are critical at step (If no such languages exist - which can only happen if none of them consistent with St we define fc(S)) arbitrarily.) Among these critical languages, let Ln, be the one with the largest index n4 S t. We define fc(Si) to be the lowest-indexed element of Ln, Sy.
Finally, to establish our initial claim (4.1). is sufficient to prove the following (in Section A.2 (4.6) For any language L2 E C and any enumeration of L,, there is a tt such that for all 2 t", we have fe(S.) E - St-
As a final note, we observe that the current formulation of fe allows to generate the same string more than once, provided that this string is in K St. However, it is not hard to modify fe so that it generates a different string each time, essentially just by defining it so that it generates the lowest-indexed element that it hasn't 't already generated.
The computational power required to produce fe- Our plan was to construct fe without wor- rying about the computational power required to do so (and recalling that for comparison, in the corresponding problem of identification in the limit, no function fc achieving identification could exist regardless of the computational power required to produce it). Now that we've constructed an ask what was in fact required computationally.
appropritate fc,

---

In addition to standard computational steps and membership queries of the form "w E L;?", the definition of fc(S,) requires that we identify the critical languages in C.. From the definition, we can do this provided we can answer finite number of subset queries of the form "I, C T.g?". So an algorithm augmented with the power to perform such subset queries can perform generation in the limit.
In the next section, we will show how to remove the necessity for subset queries, so that generation in the limit can be performed by an algorithm using only standard computational steps and membership queries.
5 Generation in the Limit via an Algorithm
We now prove 2.1 by giving algorithm that generates in the limit for any countable collection of languages C, using only standard computational steps and membership queries the form "w E L,?"
The set of possible strings U can be written as U = {u1, U2 U3 ......J. and for simplicity we will also use the language of the positive integers to describe U, treating u, the number In an enumeration of the true language L = K, let the sequence of strings that are enumerated step by step be denoted W1, W22 W3......
Extending definitions to finite subsets of languages Li- One important idea in designing the algorithm is to work with finite subsets of the languages in C, gradually expanding the size of these subsets. Thus, for a language Li E C and a number m, we will use Li[m] to denote the finite set m]. We extend definition (4.2) of critical languages from the previous section to handle fimite subsets.
L
(5.1) Let and be positive integers. A language L, is (t, m))-riticall if Ln is consistent with S.. and for every language L; E Cn such that Lg is consistent with St, we have L, [m[m] S L.[m].
Since L, L, implies that L, [m]] S [i[m] for any m 1, we have the following analogue of (4.3) (5.2) There exists a time step et such that for all 2 tt and all m 2 1, the language Lg is
(t, critticl...
The analogue of (4.4) also still holds with this definition, using the same proof.
(5.3) Leri < j and suppose that L, and L, are both (t, m)rcritical. Then Lş [m]] S L [.mm].
Finally, there is basic monotonicity property of (t, criitiiaillyyyt that is useful to write down explicitly; we give the proof in Appendix(A.3] (5.4) Suppose that L,, is m)riitil,,,a,,,, and ml m. Then L, is (t, m mm)--ciiticll.
5.1 An algorithm for generation in the limit
We now describe an algorithm for generation in the limit. As before, S, = {W1, W2,..... w/ is the subset of K enumerated through step t, treating the w; as integers. We will consider the languages in C, in step t, and maintain an auxiliary variable m,, m,, roughly corresponding to how large prefix L[[m] we consider from each language L; E C..
At the start of step I, we set m = max(m;-1, w, note that by induction this implies m, > maxp<e Wy. (Later we will increment my, so we should think of it as a variable in the algorithm whose value can be modified.) We then determine which L, C2 are consistent with S,, note that by the definition m, it is sufficient to perform membership queries for only the finite set of elements in Lj [m]] in order to do this. If there no consistent languages in C,, then we output string arbitrarily.
Otherwise, there is at least one language consistent with St, and so there is at least one (t, m)-critical language for any choice of m, since the first consistent language is (1, m))-critccl for all m. Our goal is to imitate the plan from (45) and generate a new string from the highest-indexed critical language. But to do this, we have to And new string, and this will in general require performing additional membership queries.
7

---

Generating string, For any choice of m, let (m)) be the maximum index of (t, -eriiiicll language from C,; as noted above. n2 (m)) is well-defined since we are in the case where at least one language in C is consistent with St, and so the first consistent language is (1, m)rriiill for all m. We now search for a string to generate as follows.
We maintain a counter m that begins at my and gets incremented iteratively, with each iteration doing the following:
Increment by 1.
Perform membership queries determine [i[m] for each L; C.. Note that since m > my 2 maXe<< Wy', the determination of which languages in C2 are consistent with Sy does not change when we do this.
Determine which languages are (t, m)-critical, and from this determine ny (m). Note that this only requires consulting the results of membership queries already performed.
If Um E (m)) then output Um and define my m. Otherwise, continue the next iteration.
Analyzing the algorithm. As written, it is not immediately clear that the algorithm's 's iterations in step f will come to an end with an output string ums rather than running forever. But we can show the algorithm does terminate, via the following claim proved in Section A.3
(5.5) In step t, the algorithm outputs a string after a finite sequence of operations.
Given that (5.5) establishes that the algorithm outputs a string in step t, it is useful to record an additional property of the algorithm that follows directly from its construction.
(5.6) In step t, there is an m, and an ne such that the algorithmn outputs a string from Inn [ma], where Ln, is the (t, mi)-critical language with maximum index in C..
Finally, we have the natural analogue of (46)). proved in Section
A.3 from which our main result
(2.1 directly follows.
(5.7) For any language L, E and any enumeration of T.z, there is a t" such that for all 2 t", the algorithm generates string in I,, - St-
Similar the end of Section 4 it straightforward modify the algorithm it generates strings without repetition.
6 Generation for Finite Collections of Languages
We now turn to second main result, 2.2 which derives stronger conclusion for finite collections
of languages.
The proof of this result takes different approach from what we used in the previous two sections; for the problem in this section, at a given step I, the approach we follow to take the finite sample S, seen so far and ask whether there are any additional strings g S that are common to all the languages in C that are consistent with S,. If so, then we can output such string and be sure of satisfying the specification for generation.
The closure operation. We formalize this plan using the notion of a closure operation, follows. For a sequence of strings S, from a language in C. we define the closure of Se in C, denoted (S.), to be the intersection of all languages in C that are consistent with S.. If there is string in (S)) S. then it is always safe for the algorithm to generate such a string; by definition, it must be an unseen string from the true language L.. The closure operation would not have been useful for us in the case of general infinite collections of languages C, since there are instances of the general problem where (S.) S, and so the closure does not provide with any proposals for strings generate. We give an example of such an instance in Appendix[A.66
However, in the case of finite collections C such as we are considering in this section, the closure operation becomes a powerful tool: the crux of proving (2.2 to show that once S, large enough, (S,) must become infinite, so we will have infinite set of options in (St) St to use.
8

---

Proving the result for finite collections. We start by giving the basic idea behind the proof. and then the proof itself. Let us write the finite collection of candidate languages as C = Lz..... L,, and suppose that after the adversary has enumerated set S of strings, the languages consistent with are Tay; Tig:..... Triy Note that the true language K must be one of these k languages. Now, the closure (S) is equal to the mutual intersection L,, n 74 n. ..... n Tri and there are two possibilities: either (S) is infinite, or it is finite. If it is infinite, then the algorithm can safely generate all of the strings in (5) -S. S, and thus achieve the goal specified by (2.2). On the other hand, if (S) is finite, then it has size equal to some natural number m. in this case, after the adversary enumerates at most m + more distinct strings, the algorithm will learn that at least one of L; L.y............................. Li2 is no longer consistent. We will then have a set of at most k - 1 consistent languages, and we can iterate this argument at most k- 2 more times until (i) there is only single consistent language, which must be K, or (ii) more generally, the set of all consistent languages has a mutual intersection that is infinite, in which case the algorithm can safely generate from this infinite set.
This argument conveys the key point underlying the proof, that as the adversary enumerates strings from K, it cannot prevent itself from reaching point where the set of strings it has enumerated has an infinite closure. To turn this into an argument that produces a uniform bound on how many strings are needed before the closure must become infinite, we replace the iterative argument in the previous paragraph with one that is shorter and more direct. Specifically, consider all sub-collections of languages from C (where we think of sub-collection as any way of choosing some of the languages from C but not others). Note that since C is finite, there are only finitely many possible cub-collection of languages from C. For each sub-collection C', the mutual intersection of the languages in C' is either finite or infinite. Consider the sub-collections that have a finite mutual intersection, and let m be the maximum size of such mutual intersection. Now, suppose the adversary produces set S of m +1 1 distinct strings from K. If we consider the sub-collection of all languages in C that are consistent with S, its mutual intersection must contain S and therefore it has cardinality greater than m". By the definition of m this means that its cardinality must be infinite. So the closure (5) is infinite, and therefore the algorithm can safely generate all the strings in (S) S.
We give a formal version of this argument in Section A.4 providing the complete proof of 2.2
7 Extension: Prompted Generation in the Limit
As discussed in Section 2 a natural generalization is to ask whether we can preserve the basic structure of the model while adding a notion of prompting: the algorithm is provided with a prompt string and it must complete it to a valid output. The overall set-up is as before: an adversary chooses a true language K from C, and it begins enumerating the strings of K in a sequence of steps.
A model of prompting. The new feature of the problem in our generalization is that in every step the adversary provides the algorithm with two things: string w, from the true language K, and string Pt that serves as a prompt. (The adversary is allowed use the same prompt in multiple steps.) The algorithm in step must then produce a string e with the goal that the concatenation of pt and o, is a string belonging to K- - S;; that is, it should be an unseen string from K, In what follows, we will use Pe C to denote the concatenation of pt and ez.
We observe that it leads to an equivalent problem whether we ask the algorithm to output c so that Pt C2 E K S,. or whether we ask the algorithm to output the full contatenated string a, P: Cr. In this latter formulation, we can phrase the algorithm's 's task as follows: given a prompt pt. output string a, with the properties that p. is a prefix of a,, and az E K S.. Because it makes the exposition slightly simpler, we will take this latter formulation as our default way of describing the problem, but the two formulations are equivalent.
To establish a positive result for prompted generation in the limit, we need to impose some type of restriction on the prompts the adversary can provide. For example, if the adversary were simply to provide an arbitrary string ps and ask the algorithm if there exists a string a and a language L, E C for which Pa- C E L,, this is not problem that could be solved by algorithm that must terminate and whose only access to C comes in the form of membership queries of the form "Is w E L,?"
Here we describe a result based on the following restriction on the adversary's 's prompts: We say prompt p is robust if for all languages L, C, there exist arbitrarily long strings e for which e E L,, In the present discussion we will consider ad that only provide robust prompts.

---

We say that the algorithm achieves prompted generation from K in the limit if there is some t* such that for all steps 2 t", the algorithm'ss output a, has the property that Pt is a prefix of a and at E K Sy. We can prove the following.
(7.1) There is an algorithm with the property that for any countable collection of languages C= (L,, I2, Lz,,...,, and any enumeration of one of these languages K accompanied by sequence of robust prompts, the algorithm achieves prompted generation from K in the limil.
We provide a proof of this theorem in Section A.5 in the Appendix. In the full version of the paper we also explore stronger statements that are based on giving the adversary more freedom in the prompts it is allowed to provide.
We close with two initial observations about 7.1 First, 7.1 is a strict generalization of our first main result (2.T), since if the adversary always provides the empty string as its prompt Pt, then the problem of finding continuations e for which Pt a E K S, is simply the problem of finding strings Ct in K - St. as in the original definition of generation in the limit. Moreover, the empty string is robust prompt, since each of the languages L, E C is infinite, and so there are arbitrarily long continuation strings that belong to L; when concatenated to the empty string.
Second, we observe that there is no requirement that the algorithm has ever seen a string beginning with the prefix Pt among the adversary's 's examples S, S K before the first step / in which the adversary provides pt- An important point to notice about (7.1) is that the algorithm can achieve prompted generation in the limit despite this challenge.
8 Concluding Remarks
Generating from language based on observed samples is thus fundamentally different, more tractable problem than identifying the language from observed samples. It is so tractable, in fact, that it can be accomplished provided only that we know the samples come from a language in a known countable collection of languages.
It is therefore interesting to ask what stylized conclusions we might draw from these general results about generation as a task, and its relation to other learning processes. In the case of finite collections of languages, the basic idea underlying the proof is that large "core" to the language (the closure of the sample, in our terminology) emerges at a known time after a finite set of observations, and is then enough to generate from this core even though there might always remain peripheral parts of the language - disjoint from this core- - that we can never be sure about. In the case of infinite collections of languages, the task is even more complex, because there is never known time at which a core to the language emerges. Instead, the algorithm may need to continually shrink the set it is using for generation; through this infinite process of shrinkage, the algorithm can be sure that beyond a certain point, it is always generating from the true language K, even if it can not be sure when it has reached this point or what the true language is.
Thus, as noted earlier, the solutions we develop highlight interesting tensions between the problem of producing valid strings that belong the target language, and the problem of maintaining breadth by not restricting to only a small subset of the target language. Our approaches achieve validity through strategy that implicitly gives up on breadth, and it is interesting to ask if this is essentially necessary for any method that achieves language generation in the limit. In this way, our formalism may also help shed light on a particular broader impact of large language models, which is their implications for the homogenization of text style, in which writing becomes less varied; our results provide further indications that decreased breadth in text output may be crucial feature of successful solutions to text generation.
This tension between validity and breadth, as it arises in our solution, also creates an interesting echo of the human process by which people acquire the vernacular within a new community [5] as with our solution in this abstract model, people encountering the dialect in new community similarly pass through a sequence of conceptually distinct phases: an initial phase in which they are generating too adventurously and producing invalid utterances; then a phase where the utterances aligned with the scope of the language; and finally a phase in which the range of utterances they are willing to generate shrinks further over their lifetime, as they become increasingly conservative in what they consider valid. Again, it is interesting to consider whether this type of structure is inherent in any solution the task of generation in the limit.
approximately
10

---

Acknowledgements. We thank Bobby Kleinberg, Lillian Lee, Marios Papachristou. and Kenny Peng for helpful discussions on these questions and on early drafts of this paper. The work has been supported in part by Vannevar Bush Faculty Fellowship, a Simons Collaboration grant, grant from the MacArthur Foundation, and the Center for Applied Al at the University of Chicago Booth School of Business.
References
[1] Dana Angluin. Finding patterns common to set of strings. In Proceedings of the eleventh anmual ACM Symposium on Theory of Computing, pages 130-141, 1979.
[2] Dana Angluin. Inductive inference of formal languages from positive data. Information and control, 1572)3117-135, 1980.
[3] Martín Arjovsky and Léon Bottou. Towards principled methods for training generative adversar- ial networks. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[4] Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 214-222 PMLR, 2017.
[5] Cristian Danescu-Niculescu-izzzl Robert West, Dan Jurafsky, Jure Leskovec, and Christopher Potts. No country for old members: User lifecycle and linguistic change in online communities. In Proceedings of the 22nd international conference on World Wide Web, pages 307-318, 2013.
[6] E Mark Gold. Language identification in the limit. Information and control, 10(5):447477, 1967.
[7] Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. Survey of hallucination in natural language generation. ACM Computing Surveys, 55(12):1-38, 2023.
[8] Adam Tauman Kalai and Santosh S. Vempala. Calibrated language models must hallucinate. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 160-171. ACM, 2024.
[9] Lillian Lee. Learning of context-free languages: survey of the literature. Technical Report 12-92 Harvard University, 1996.
[10] Vinod Raman and Ambuj Tewari. Generation through the lens of learning theory. arXiv preprint arXiv:2410.13714 2024.
[11] Ziwei Xu, Sanjay Jain, and Mohan Kankanhalli. Hallucination is inevitable: An innate limitation of large language models. arXiv preprint vxXiv:2401111817 2024.

---

A Appendix
A.1 Review of Negative Results for Identification
In the interests of completeness, we provide a self-contained proof of the Gold-Angluin result that language identification the limit is not possible in general. adapting the exposition from (6 9 As noted in the main text, this proof is not necessary for the results in our paper, but it provides useful background and context for thinking about the problem.
There are many ways to show the impossibility of language generation in the limit using very simple language families, and choose the argument, let U be the set of all integers, and let the collection of languages - each of which is subset of U be the set of all infinite arithmetic progressions of integers. (The choice of which countable ground set U we use is not crucial for any of these results, and examples are often easier to describe over the set of integers than over the set of finite strings.) Formally, for an arbitrary integer and a positive integer b, let Po.6 be the arithmetic progression consisting of all integers of the form {a + bi i 0, 1, 2, and let Qa,b be the "bidirectional" arithmetic progression consisting of all integers of the form {a + bi ; =.... -2. -,, 1, 2, .... Let the collection C' consist of all arithmetic progressions Pa.b and Qa,b-
that highlights some intuitive contrasts with generation. For
Now, suppose by way of contradiction that there is an algorithm that can identify in the limit an adversarially chosen arithmetic progression K C. We construct enumeration of K that causes the algorithm to fail, as follows. First, for integers a S b, let [a, b] be the interval of all integers e for which a S b. We enumerate elements of U in stages, where each stage > 0 consists of a set of consecutive steps. If by induction stage & has enumerated the elements of the interval 7[-8, j()) for some j(s) 2 0, then stage s + 1 will enumerate additional elements so that by the end of the stage we have enumerated exactly (s + [),j(s + 1)] for some j(s + 1) > j(s). In particular, stage + first enumerates (ss + 1) and (ss + 1, and then begins enumerating j(s) + (.) 3,... in increasing order. At some point during this process, the algorithm must output P- 1-(++1).1 as its guess for K, since we can continue this way to produce a full enumeration of P 1, which point the true language is K = P- (x+11), Once the algorithm outputs P 11.1).1 1).1 as its guess during stage + 1, we end stage s + 1, defining j(s + 1) to be largest integer we've enumerated up to that point, and we begin stage s 2.
In this way, the successive stages extend the interval [s)) unboundedly in both directions. We therefore enumerating Q U, and so in fact K = Qa,1- But have also produced an unbounded sequence of steps to < t1 < t2 <... such that the algorithm guesses P-j,1 at step ty. Thus, there is no time step t" for which the algorithm outputs the (correct) guess Qu,1 at every 2 t².
As final note, we observe that for this simple collection of languages, the problem of generation in the limit is knows from the arithmetic progression structure that by setting d = j - i, it can safely output j+ j j 2d, j 3d,... ... and all of these will belong to K. The generation task for this language family is thus particularly simple (for others it is much more subtle, as in the example from Appendix A.6). but this contrast with the negative result for identification provides some initial intuition about the differences between the two problems that we will need to exploit in a generation algorithm.
once the algorithm has seen two elements and j from K, with i < j.
A.2 Proofs from Section 4
In the next three subsections of the Appendix, we provide proofs of the results stated in the main text.
Proof of (4.3) Let K be the indices < z for which L2 g Li For each i E K, let oy be an element of L, Li- Let 1, be the step in which v, first appears in the enumeration of L,, and let t+ = m t,.
Now, suppose by way of contradiction that for some t 2 tt, the language Lg is not critical at step t. In this case, there must be some L,, E C, such that L, is consistent with S, and L,g g I But we know that V/2 E St and v L,, contradicting the consistency of L, with S..
Proof of 4.6). In the given enumeration of I.z, 4.3 tells us that there will come a step 1+ such that for all t t", the language Lg is critical at step t. Let t" max(2, (t) In every step t 2 tt.
12

---

our construction of fc will include L3 among its critical languages in Ct. Therefore, the highest- indexed critical language Ln. E C, satisfies n4 2 2, and so by (4.4) we have Li, S Lz. Since (c() E Tm,, - Sr, we have fc(St) E l,- St as required.
A.3 Proofs from Section 5
Proof of (5.4). Since L,, is (t, m) m--criiiall, we know it consistent with St, and that Ln [m]] S [,[m] for all languages L; E C, such that L; is consistent with Sy. Now, if L, is language in C, that is
consistent with St, then since L, [m] S L [m]m and m' < m, we have I. [m]mm'] S Ty [m*].
I It follows
that Ta [m²] [ Iz[m"] for all languages T E Cn such that Lę is consistent with Sr, and so In is
(t, m/) eerttcclil
Proof of 5.5 We identify each iteration with the value of m after the initial increment of the iteration; so the iterations begin at m, + 1 and continue upward from there. Suppose by way of contradiction that the algorithm performs an infinite sequence of iterations.
Let us call an iteration m disruptive if (m) + n 1). Since (m) is the maximum index of a (t, m 1) -riitical language, and since our monotonicity property (5.4) implies that L.. (m) is also (t, m - 1) )eriticall, it follows that ne (m) < nz (m 1). Since ny (m() starts at a value bounded by f and decreases by at least one with every disruptive iteration, there can be at most t disruptive iterations.
The sequence of iterations must therefore contain last disruptive iteration m². For all iterations m > m², the language Ln,(m) does not change. Since the language is infinite, we must eventually reach an iteration > m for which tmm Ln,(m)) and the algorithm will stop and output um at this point.
Proof of (57 In the given enumeration of La, 5.2 tells that there is a tt such that for all t t2 t and all m 2 1, the language Lg is (t, m Let t" ma ). In every step f 2 t", by (5.6) there is an my such that the algorithm generates string from Im, [m:]. where Ten, is the
(t, my m.)--riiical Jeriticall language with maximum index in C. In each such step f, L2 is a (f, (.)y)rrriiii language in C., and so n4 2 2. From (.3). it follows that L,, [m]] S Lg [me] Lz- Since the
algorithm's 's output comes from Ln, [m]] - St. it follows that it comes from L S, as well.
A.4 Proofs from Section 6
Proof of (2.2) We begin with some additional definitions. For any subset A of the indices (1,2..... n.. let ((A) be the intersection of the languages whose indices are in A; in other words,
D(A)= n T.. For any sequence S of strings from language in C, let T(S) be the set of indices of ieA
the languages in C that contain S; that is, ((S) (i: SC L.). We observe that the closure operator can be written in terms of this notation, in that (S) D((())..
If D D(,,2, n)) is infinite, then the algorithm output without seeing any sample of strings at all; since D C L, for every language L3 E C. in particular D L, for the true language L,, and this satisfies the requirements of (2.2).
generate arbitrary strings from D as its
For the rest of the proof, we therefore suppose D([1, 2...., n)) ))))) finite. Let be the collection all sets of indices A C (1,2..... n with ((A) finite. Finally, let m max ([A)]; since |JF] 2", AEF observe that m is the maximum of finite set of positive integers, and hence positive integer. We now define t(C* = m + and claim that this choice of t(C) satisfies the required guarantee of (2.2). Indeed, consider the true language L, E C and any sequence S, of t(C) distinct elements from L.. Recall that I(S.) denotes the set of indices of all languages in C that contain S.. We have S, C (S.) (()()))) If D(I(S))) were finite, then by the definition of m". the cardinality of D(I(S)) would be at most m But this would contradict the fact that ((I(S)) contains S,, which has cardinality mn*
Therefore (S.) = (TT())) is infinite, and is a subset of the true language I.g. To conclude the proof, we therefore need only show that there is an algorithm that can enumerate all of (S.) St
13

---

using only membership queries. To do this, the algorithm begins by querying whether each wy E St belongs to each Lj E C. From this, can determine the set [(,) of indices of languages that contain S. Now, it enumerates every string E U in ascending order, skipping the elements of S., For each such string u4, it queries whether u, E T. for each j E T(St), and it outputs u, if belongs to each of these languages. In this way. the algorithm enumerates the infinite set (Si) S. C Lug S. after seeing a sample of t(C) strings in Lg.
A.5 Proofs from Section 7
We now describe how prove our result (7.1) on prompted generation with robust prompts. The proof is direct adaptation of the proof of 2.1) from Section 5 as we will see, the structure of critical languages built up there is sufficiently strong that not much more is needed to handle the prompted version of the problem with robust prompts.
As in Section 5] we will work with a specific enumeration u1, 122 ua. ......... of all strings in U, and work with finite subsets of the languages Li, defined via the notation L3 [g[m] L; n {ui, u2, Um J. The algorithm for prompted generation will closely follow the algorithm from Section [ in that in every step E, it will increment a counter m and maintain knowledge of the maximum index ny n²(m) of a (t, m) m)-critical language from C.. Maintaining knowledge of ni (m)) does not require knowledge of the prompts, and so this part of the algorithm is the same as before. What changes is the stopping condition for the algorithm in step t: rather than continue increasing m until any valid output is found the algorithm must increase m potentially even further, until it finds a string Um for which p: is prefix of um, and um E (m, - St. However, since Pe is a robust prompt, the algorithm is guaranteed to eventually find such string, and so we can be sure that its iterations in step will terminate. If we let mn be the value of m at the end of step 4, then once is large enough, we know that (m.)) [mm.] C Lz [me]] where L,- K is the true language, and so the S, as required.
that is, until Um E (m))
string unn that it outputs has pt as a prefix and belongs to K
The discussion above provides the entire set of modifications to the algorithm; for completeness we now describe these in more detail, together with a proof of correctness.
First, the facts (.2) through (5.4) still hold in the prompted case, since they are structural properties of the language that not affected by the adversary's 's use of prompts. The algorithm for generating an output string uses an iteration in step t for which parts (i), (ii), and (iii) of each iteration are the same as in Section 5 Step (iv) of each iteration is replaced by
(iv') If there is any string for i S m such that u; has pt as prefix and u; E Ln((m) S,, then choose the minimum with this property; output the string u, and define m, = m. If there is no such u;, then continue to the next iteration.
Now, the proof of termination works as before, by establishing that there are only finitely many disruptive iterations in which the identity of n, (m) changes; this part does not depend the structure of prompts but only on the definition of a (t, m))critical language, and so it uses (5.2) through 5.4) exactly as before. After the last disruptive iteration, either there is string u, E (m)) S. with i < m for which pt is a prefix, or else the algorithm will eventually reach one, since the prompt p: is robust. It declares this un to be its output string. We therefore have
(A.1) In step t, if at least one language in C, is consistent with S,, then there is an my and an n. such that the algorithu terminates with a string at for which pt is a prefix of aj and ag E L.n,(me)) [mm] S, where Lnngm)) is the (1, me) -e)-critical language with maximum index in C..
Finally, we establish the basic correctness property of the algorithm, from which 7.1 follows directly. (A.2) For any language T,z E C and any enumeration of I., with robust prompts PL, P2. Pa...., there is a tt such that for all t 2 t", the algorithm generates a string as for which pt is a prefix of at and at E Sp.
Proof. In the given enumeration of Lg, 5.2 tells us that there is a et such that for all > + and all m 1, the language L; is (t, m)m critical. Let t" max(2, In every step > t", by (A.I) there is an my such that the algorithm generates a string a such that ps is prefix of az and a, (m. [mm]] St, where (m,,) is the (t, me)-critical language with maximum index in C,
In each such step t, L, is a (t, mz) -critical language in C,, and so ne(mm) 2 z. From 5.3) it follows
14

---

that (m [ma] S Ly[me] S Ly. Since E [m.(m.)mml) St. it follows that ds E Lg -S as well.
A.6
An Example Where Closure is Not Helpful
In Section we introduced the notion of closure: For sequence of strings S. from a language in C, the closure of S, in C, denoted (St), is the intersection of all languages in C. that are consistent with St.
We observed in Section 6 that in any step t where (Si) contains element not in St. the algorithm can always safely output an element in (St) S, and be sure that it is outputting a new element in the true language K This is simply because for every consistent language T. E C, we have (S.) - St S L St by the definition of the closure operation, and in particular this holds for the true language K.
This strategy is key to the proof in Section when we were dealing with finite collections C, and would have been an effective strategy in the case of infinite collections C as well provided we could be sure that (S²) S, was always non-empty. Unfortunately, there are instances the problem with infinite collections C for which (St) St is empty for arbitrarily large t, and therefore the closure provides us with no new strings to generate.
To see how this can happen in an example, we go back to the collection of arithmetic progresions over the integers as the ground set U, and we consider more complicated collection that builds on this. In particular, we let Pa.b as before be the arithmetic progression consisting of all integers of the form {a bi 0, 2,.,,...J and now, for any finite set of integers V, we define the language L(a, b, V)- Pa. U V. Our collection C consists of every L(a, b, V) for arbitrary integer a, an arbitrary positive integer b, and an arbitrary finite set of integers V. (Think of L(a, b, V) as a copy of the arithmetic progression Pa.s that has been obscured by an arbitrarily large finite set V so that its structure harder to discern.)
Now, suppose the adversary is enumerating language K = L(a, b, V) E C, and consider the set Se of samples after t steps. We claim that (S.) S,. Intuitively, this is because S, might have come completely from the finite set V that is part of I(a, b, V); more formally, there cannot be any element j E (St) S. because L(j + 1, 1, St) consistent with S,, and it does not contains j.
This example illustrates the sense in which we mean that closure by itself is insufficient to provide a strategy for generation in the limit when the collection of languages C is infinite: in this instance, the algorithm has to repeatedly output elements outside the closure of S, and yet somehow eventually generate from K. We know that the algorithm that proves our main result (2.T) is able to do this, but it is also interesting to ask if there is simpler way to directly describe a method for generation in the limit for this particular example. In fact, there is direct solution to this example, as follows: in any step t, the algorithm finds the two largest elements < j in St, and with b = j i, it outputs j + b. The point is that if the true language K is [a b, V), there will come a time when the adversary has enumerated every element of V, and within finite number of steps after this, the two largest elements of S, will have come from Pa.b- From this step onward, the algorithm's strategy of outputting + b is guaranteed to produce element in K - S.. This particular strategy of course seems highly specific the particular example we are discussing here, but at a very high level it does contain reflections of some of the ideas we saw in the general solution from Sections and
15

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The paper's s main contributions are to formulate a model of language generation in the limit, by analogy with the Gold-Angluie model of language identification in the limit, and to prove set of theoretical results in this model. These contributions are described in the abstract and introduction.
Justification:
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 contributions made the paper and important assumptions and limitations. A No or NA answer to 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.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
The paper's main limitation, similar to the classical Gold-Angluin model, that it is theoretical model based on worst-case guarantees, and as such does not try to capture the role of distributional assumptions in the design of language models. This is both source of limitations but also (as mitigation of these limitations) source of insights distinct from traditional probabilistic models. These issues are discussed the paper's subsection entited General Connections Language Modeling.
Justification:
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 separate "LLimitttions" section in 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-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a few runs. In 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it 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.
16

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to 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]
Justification:
The model and its underlying assumptions are fully described, and all proofs
are provided in the Appendix.
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 the statement of any theorems.
The proofs 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 provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results 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 not)?
Question:
Answer: [NA]
The paper consists entirely of theoretical results. Due to the emphasis on guarantees against adversary in the limit, there is not natural opening for demonstrating the results experimentally (as there similarly isn't in the work that introduced the Gold- Angluin model).
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer 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.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to 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 a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
17

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to 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 new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The results of the paper do not make use of data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
(esllic/guies///ee wttggggddddddsuuunneeee wwweeeoiiiissiooooooooooo Polocylylly for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //ipsscc/public/guiieee Sttp://Coeeeeeeeeeeeeeeee wwwssisssiiiiinooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only 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) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
As noted above, the paper does not include computational experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

The experimental setting should be presented in the core of the paper to 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:
As noted above, the paper does include computational 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, confi- dence 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 (c.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma eгтоr bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of 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 out range (c.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
As noted above, the paper does not include computational experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttpp////aarrppppc//p//////aata
19

---

Answer: [Yes]
The NeurlPS Code of Ethics was reviewed in the course of writing the paper, and has been fully adhered to.
Justification:
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.. if there special consid- eration due to laws or 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: [Yes]
The paper studies theoretical questions motivated by the dramatic recent advances in the performance of large language models (LLMs). As such, connects the broader and rapidly growing discussion about the potentially disruptive societal implications LLMs and their widespread use, although does so only through the formulation of theoretical models. One point in the discussion of LLM broader impacts that our theoretical results may address most directly is concerns over the homogenization of text style the ways in which language modeling may lead to decreased variety in the text that is produced and we discuss this in the section entitled Concluding Remarks.
Justification:
Guidelines:
The answer NA means that there 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 or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness 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 tied to particular applications, let alone deployments. However, if there is direct path to 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, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
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 is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If 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, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
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 (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not develop data implementations that could be released.
20

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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 to usage guidelines or restrictions to 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 is challenging, and many papers do not require this, but we 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 the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing computational assets; does cite the theoretical models that serve the underlying motivation for the work.
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 or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paw.ersi.aaassiiiiiiai thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: The paper does not release new assets; does provide complete self-contained descriptions of the theoretical models that it introduces.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
21

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not make use of crowdsourcing or any human-subject research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included 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 in the country of the data collector.
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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: As noted above, the paper does not involve any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If 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, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "LfXGXL62n5", "reviewer": "Reviewer_4Kah", "summary": "This paper revisits a classic topic with a new angle that reveals a more positive outlook on a classically pessimistic result.\n\nNamely, the paper that while identification of a formal language from positive examples is generally not possible, even given countably infinite examples, one *can* always learn a (under) approximation of the language which for non-finite languages is itself infinite!\n\nThe paper starts by reviewing why the obvious approach cannot work -- and also reminds the reader why it would violate Gold's classic negative result on language identification.\n\nThe paper then constructively proves that language generation is possible in the limit. Further analysis is done for finite collections of formal languages where the learning of the under approximation has an upperbound (specific to the finite collection) independent of the adversaries example strategy.", "questions": "* Are there any implications on this result for common families of languages such as regular languages which have a natural notion of complexity? e.g., representation size. It seems like one could bound how many examples it would take by additionally ordering candidates by complexity.", "limitations": "Handled well in the concluding remarks of the paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper does an excellent job of treating a classic technical subject while still being approachable. In particular, the treatment of the review of the negative results is very well handled and serves a great pedagogical launching point for the constructive proof.\n\nThe language generation problem itself is also interesting and the connection to the recent craze in generative AI makes it timely and appropriate for the Neurips audience. While modern LLMs likely exploit more structure afforded by distributional properties, the fact that a stochastic parrot need not in general is interesting.\n\nMy reading of the proofs revealed no errors.", "weaknesses": "While I overall find the paper to be well paced and easy to read, the final analysis of the algorithm and section 6 felt very curt. This is something that I'm sure could be addressed with an additional page in the camera ready.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review of the paper; we appreciate the comments about the work and the interesting questions. \n\nWe agree that with the length constraints of the submission, Section 6 is written in a very compressed format. Indeed, we would plan to provide a more extended discussion of the result and the proof in Section 6 in a version with a higher page limit. \n\nWe also agree that there are a number of interesting open directions for considering quantitative versions of the results here for language families with specific structure, like regular languages and context-free languages. For example, when the result of Section 6 is specialized to a set of regular languages or context-free languages, it raises an interesting set of language-theoretic questions about how large the bound $t({\\cal C})$ on the required number of examples needs to be as a function of an upper bound $k$ on the number of states in the finite automata that generate the languages in the collection $\\cal C$ (with similar questions for corresponding measures of complexity for context-free languages). \n\nSimilarly, in the case of the result for infinite collections of languages in Sections 4 and 5, when specialized to regular or context-free languages we agree that your suggestion of ordering languages by increasing complexity may make possible quantitative bounds on the number of examples needed as a function of the position of the true language $K$ in the list. \n\nWe would plan to mention these interesting open directions for regular and context-free languages in a revised version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eg75KaLtTW", "reviewer": "Reviewer_v4Eq", "summary": "In the classical model of language learning in the limit proposed by Gold and Angluin, there is a countable sequence of candidate languages L_1,L_2, ... and a language L* that is equal to L_i for some unknown i. At each time step t, Player 1 draws a string w_t from L*, and Player 2 is required to guess a number i. The language L* is said to be learned in the limit if there is some t* such that for every t>=t*, the language L_i is equal to L*. When stated in this general form, learning in the limit is an impossible task, unless the list of languages satisfies some strong properties. \n\nIn this work, the authors propose a similar approach in the case of language generation. At each time step t, Player 1 draws a string w_t from L*, and Player 2 is required to guess a string w in L* - {w_1,...,w_t}. That is, instead of identifying the language L*, all that is required is to generate a string w that belongs to the language L* but not to the list of examples provided by Player 1. The authors claim that in this setting, generation in the limit is always possible, no matter what sequence of languages L_1,L_2,...,", "questions": "Please address the comments above.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The result, although being of a purely theoretical nature, may have applications to prove further results in learning theory.", "weaknesses": "The explanation of the key ideas of the paper seem to be much longer than necessary. It may be the case that the paper is more adequate to a conference specialized in computational learning theory, such as COLT. \n\nI reviewed this paper before. As far as I can see, I could not find discussions in this version that address issues pointed in my previous review. So, at this point in time, I'm only able to suggest the same rating as before (weak reject). Depending on the answers from the authors I may increase my score slightly. \n\n-------------------\n\n If Player 1, can ask questions of the form w \\in L_i then the strategy for generating in the limit seems to be quite simple.\n\n1) First, at Step t, Player 1 keeps track of all languages up to language L_t that are consistent with S_t. This can be done by using the membership oracle. \n\n2) Once this has been done, Player 1 enumerates the strings in {0,1}^* \\backslash S_t in order of length. For each of these strings w, Player 1 checks whether w belongs to the first consistent language in the list. If yes answer w. If no proceed to the next string in the enumeration.\n\nThis algorithm always generates some w in a finite amount of time, because the languages are assumed to be infinite. In particular, the first consistent language is infinite, and therefore, at some finite length, it will have strings of that length that does not belong to S_t. On the other hand, at some point in time (which may be unknown), the target language K will be the first language in the list. This is because of the assumption that for each w in K there is a t such that w belongs to S_t. In particular, at some finite point, none of the languages that precedes K in the list will be consistent with S_t. Additionally, by assumption K is always consistent with S_t.\n\nTherefore, essentially, the core of the argument for proving theorem (2.1) is in the discussion of statement (4.3) in Section 4, and the membership test is used to implement this argument in practice. The argument mentioned above also gives Theorem (2.2) immediately. Just let t(C) be the number of strings of length at most r, where r is the smallest number such that each language preceding K in the list has a string u of length at most r that does not belong to K. At this point, K is guaranteed to have become the first consistent language in the list, and anything generated by the algorithm will belong to K.\n\nI still think that the main claims of the paper are interesting from a conceptual point of view because they sound counter-intuitive at first glance. Nevertheless, at this current point in time the paper has two main drawbacks. First, it much longer than necessary when it comes to explaining the main ideas to prove 2.1 and 2.2. The argument 4.3 could be made directly after 2.1 and the discussion about membership test as synthesized above is also straightforward. The second drawback is that the paper does not provide any \"application\" for their result. Please note that while the bout t(C) is finite, from what I could understand, the authors provide no bound on the time necessary to generate the next string (and this may not be possible at all). Therefore, from an algorithmic point of view, the contribution of the paper is weak. The algorithm generates the next string in the list at some point in time which seems to be completely unbounded.\n\nPlease also note that the discussion in 125-129 is a bit fallacious. Of course, if the target language is finite, then the algorithm would run out of strings to generate. So it is indeed natural to assume that the target language is infinite. However, the paper is assuming that all languages in the list are infinite. This is a very strong assumption. My impression is that this assumption is only being made so that the algorithm described above (item 2) stops in finite time. If the first language in the list of consistent languages were exactly S_t, then the the enumeration process in item 2 would run forever. So, in my opinion, it is important to highlight that the assumption that all languages are infinite is being made so that the proof goes through.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review; we would very much like to discuss these points with you, because the simpler argument you propose for the main result --- generation in the limit --- is not correct. Furthermore, our submitted paper contains a description of the approach you describe and an explanation for why it does not work (in Section 3, entitled \"An Approach to Generation that Doesn’t Work\"). Based on the earlier review you mention, we gave that discussion a prominent place in our current submission; this is a change to the current submission in response to your earlier review.\n\nWe encourage you to look at this section, but we also summarize here why your simpler argument is not correct. We agree with the portion of the argument in which you describe how to generate a new string not belonging to $S_t$ from the first language in the list of all languages that are consistent with $S_t$. The problem arises with your claim that, \"at some point in time (which may be unknown), the target language K will be the first language in the list. This is because of the assumption that for each w in K there is a t such that w belongs to S_t. In particular, at some finite point, none of the languages that precedes K in the list will be consistent with S_t.\" \n\nTo see why this argument is not correct, consider (as we discuss in Section 3) the case in which $K = L_z$ for some index $z$, and there is an earlier language $L_i$ that comes before $K$ (i.e. $i < z$) such that $L_i$ is a proper superset of $K$.  (That is, we are supposing $L_i$ contains all of $K$ as well as strings not in $K$.) In this case, for every time step $t$, every string in $S_t$ must belong to $L_i$, because every string in $S_t$ belongs to $K$ by definition, and $L_i$ is a superset of $K$. Therefore, $L_i$ will always be consistent with $S_t$, for all $t$, and $K$ will never become the first consistent language in the list (because $L_i$ precedes $K$ and is always consistent). And this means that an algorithm that simply generates a string from the first consistent language on the list has no way to avoid generating a string in $L_i - K$ infinitely often, which means that the algorithm is not successfully generating from $K$ in the limit. \n\nThere is a concrete sense in which there cannot be a simple \"fix\" to this argument that might get it to work. The reason is that if we could be sure that after a finite time $K$ was the first consistent language on the list, then we could solve the problem of language identification in the limit, not just language generation in the limit, by simply guessing that the identity of the adversary's language is the first consistent language in the list. But this would contradict Gold's Theorem, that language identification in the limit is not possible. \n\nIt is because this approach cannot work that we are forced to embark on the more involved proof that requires the definition of critical languages. And once we do that, we require the further arguments in Section 5, because determining whether a language is critical (according to the definition we introduce) is not algorithmically decidable. As a result, we need -- in Section 5 -- to work with a weakened version of criticality that is both decidable and also sufficient for generation in the limit. \n\nWe very much hope you go through these arguments, because they should show you why your claim about a simpler proof is not correct, and why small variations on this attempt at a simpler proof will not work (because they would provide a solution to language identification in the limit, which is not possible by Gold's Theorem). You can also see the discussion in Section 3 of the paper, which addressed these points in the submission. \n\nOn the other points in your review, we agree that the presence of arbitrarily large \"gaps\" in some of the languages $L_i$ --- that is, arbitrarily large intervals $[a,b]$ such that $L_i$ contains no strings of length between $a$ and $b$ --- means that we cannot put an upper bound on how long (in terms of basic computational steps) the algorithm needs to generates a next string. As noted in the paper, the key issue of interest to us in this paper is to show that certain tasks are possible at all. However, we do note (as we also mention in replying to Reviewer 4Kah) that many of the cases of interest, dating back to Gold and Angluin's work, are settings in which the languages $L_i$ are regular or context-free. In these cases, the relevant pumping lemmas for these language families constrain the kinds of intervals of lengths $[a,b]$ for which a language can contain no strings of that length. This suggests the potential to extend our work to address interesting further questions of a more quantitative nature for these families of languages, and we would note these further directions in a revised version of the paper.\n\nWe also agree that if some of the languages $L_i$ are finite, then an algorithm cannot know at any given time step $t$ if $L_i - S_t$ is non-empty; i.e., it cannot know if there are more strings in $L_i$ left to generate. We can note this in a revised version of the paper. We also observe, however, that the challenges in language generation tend to arise much more from uncertainty about the nature of the true language than about the risk of \"running out\" of strings to generate; there are for example many informal arguments suggesting why natural languages will contain arbitrarily long sentences. We believe that the assumption that the languages $L_i$ are infinite captures this point. \n\nYou mentioned in your review that you were prepared to raise your score based on our response. Please let us know if we can clarify anything in the above discussion, and given our points about why simpler proofs for the main result do not appear to work, we would appreciate if you were willing to raise your score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uRQupLOsUO", "reviewer": "Reviewer_8y2i", "summary": "This paper introduces a new theoretical framework for language generation", "questions": "hard to judge", "limitations": "hard to judge", "rating": 5, "confidence": 1, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "Novel theoretical perspective", "weaknesses": "hard to judge", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would be happy to answer any questions you have about the submission. Given that the current review says, \"hard to judge\" as the full reply for the Weaknesses, Questions, and Limitations, we do not currently have enough information to proactively provide more, but we would be able to share more information if you were able to add questions to your review.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper address the language generation problem within the theoretical framework of PAC learning. It shows that according to their definition, language generation is possible in the limit while language learning (old results by Angluin et. al) is not. The reviewing scene was not ideal. One reviewer strongly argued for acceptance, another gave a borderline rank but provided no information,  the 3rd reviewer
suggests  rejection claiming that the paper has an error. This reviewer reviewed an earlier submission of the paper and claimed his previous complaints were not addressed. There was a discussion between the authors and the reviewer. I read the paper I think the paper is important as it bring the foundational theoretical perspective into current LLM culture.
Decision: Accept (spotlight)