Language Generation in the Limit

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.

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.

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

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

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

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

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

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

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

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

Dear Reviewer: please see a comment from the authors to me addressing your review:

Comment: The instructions for the use of official comments suggest that we should write an official comment about reviews that contain inaccuracies about the submission. As such, we would like call your attention to significant technical errors in the review of our paper by Reviewer v4Eq.

The bulk of Reviewer v4Eq's review is a sketch of a proof of our main result that, if correct, would be simpler than the proof in our paper. The reviewer's proof, however, is not correct, and it is based on an approach that --- in a concrete sense --- cannot work, because it would also prove a stronger result that is known to be false.

Reviewer v4Eq notes that they reviewed our submission for an earlier conference. For that conference, they proposed the same simple, incorrect proof in a review comment written after the conference's rebuttal period had ended, and so we were not able to point out the error in their proposed proof. As a result, we included a section (Section 3) in the main text of our current submission that describes their proposed proof and explains why it does not work.

In this way, not only is Reviewer v4Eq incorrect in their proposed proof, they are also incorrect in their point that the current submission does not address their earlier review. Rather, we highlighted the error in their proposed proof in a full section of the current submission. We did this in case we got a reviewer who made a similar error; as it turns out, we got the same reviewer, but this reviewer appears not to have seen the section that explains the error they are making.

We are including a discussion of the reviewer's error in our response to them on OpenReview, but given the reviewer's persistence in making this error we wanted to include an official comment as well; we are not sure what else we can do given that we already devoted a section of the submission to alert the reviewer, unsuccessfully as it turns out, to the error they are making.

Dear Authors,

thank you very much for the reply, and for adding a discussion explaining why the most straightforward approach does not work. The problem is that there can be some language with a smaller index which strictly contains the target language.

Now, to avoid misunderstandings, let me state that my low score on the paper is grounded on four main reasons, which are detailed below.

REASON 1) The theorem does indeed have a very short proof. Please note that while the naive approach described in my previous review does not work as pointed out by the authors, the argument has indeed a direct fix using a variant of the notion of criticality used defined by the authors. Lets call it simple-criticality.

Definition (Simple Criticality): Let L_1,...,L_t be the first t languages in the list of languages, we say that a language L_j with j<=t is simply-critical if L_j is consistent with S_t and L_j\subset L_i for every other i<=t such that S_i is consistent with S_t.

Generation in the Limit with Inclusion Queries and Membership Queries.

1. At each step t, Let C_t be the set of all languages up to L_t that are simply-critical for t. The construction of C_t can be realized with inclusion queries.

2. If C_t is empty, output any string. Otherwise, let L_x be the language in C_t with the smallest index. In this case, output the smallest (and lexicographically first) string w in Lx - S_t as an answer.

Proof of correctness: Let L_z be the target language from which the samples S_t are observed. Since L_z is consistent with S_t for every t, we have that for any t\geq z, there is at least one simply-critical language. Now, let t\geq z. Then any language L_j that is simply-critical for t is contained in L_z. Otherwise, this would contradict minimality. Since L_j is infinite, L_j-S_t is non-empty. Therefore the string w is well defined and can be obtained with membership queries only. Since L_j \subsetq L_z we have that w\in L_z as required. QED.

The inclusion queries in Item 1 can be replaced by membership tests (as done by the authors) simply by considering slices of the languages up to L_t containing only strings up to a certain length. Now the "trap" of language identification is avoided with this approach because, for each t>z, the chosen language L_x may be strictly contained in L_z. Additionally there may be an infinite chain of languages where one is a superset of the next.

Please note that the own proof by the authors can be simplified significantly by using their own definition of criticality provided the statements are presented in a more natural order (as suggested in my previous review). More specifically,

Statement of Theorem 2.1 Definition of Criticality Proof with Inclusion tests Argument to replace inclusion tests by membership tests.

In this sense, I do consider that the paper has a presentation problem because at its current stage it is difficult to read due to the unnecessary length of the explanations used in the proof. A simple and direct formal argumentation would be preferable to check correctness as opposed to length discussions involving intuitive, but imprecise, concepts. The space used for the proof could be used to provide additional results, such as exploring consequences of the main theorem. See Below.

REASON 2) The paper does not describe concrete applications of the language generation problem. This is what I mean when I write "The second drawback is that the paper does not provide any "application" for their result." There are two lines of results that I would expect to be discussed in such a paper.

2a) First, Language Identification is an important primitive in computational learning theory. There are certainly several problems of theoretical/practical interest that reduce to Language Identification. What are the analogs of these problems in the context of Language Generation? The caveat is that while reducing a problem to language identification does not help in general, the analog problems in the context of language generation would have a solution.

2b) Second, since you are selling the paper in the context of LLMs, I would expect a more specialized discussion of results specialized to the realm of LLMs. For example, what models of computation would be used to instantiate the languages L_1, L_2,... in the context of LLMs? What consequences could you derive from this specialization? Could you establish complexity bounds on the process of generating the next token (word)? Who is the generator of the set S_t? There are many more questions that are unanswered here. So In my opinion, the use of LLMs to justify the applicability of the result is very handwaived in this current version.

Thank you for the review of the paper; we appreciate the comments about the work and the interesting questions.

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

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

Similarly, 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.

We would plan to mention these interesting open directions for regular and context-free languages in a revised version of the paper.

Writing to acknowledge I have read the rebuttal and other reviews.

I still stand by advocating for acceptance and also respectfully disagree with the correctness of reviewer v4Eq’s proposed protocol. It falls for the (alluring) trap laid out in section 3.