WorksComputer Science
Query Feedback and Teaching for Stable and Certifiable Language Generation
Abstract
Language generation in the limit studies whether a learner observing an enumeration of an unknown target language can eventually generate only valid, previously unseen elements. We study stability, introduced by Kalavasis, Mehrotra, and Velegkas (2025), which requires the generator's infinite output set to eventually remain unchanged, and introduce the stronger notion of certifiability, which requires the generator to determine from its observations that its current output is valid. Drawing on teaching sets in learning theory, we introduce a hierarchy of teaching dimensions for generation under three increasingly strict success criteria: correctness, stability, and certifiability. These dimensions measure the minimum number of selected examples whose appearance guarantees the corresponding success condition. We also study stability and certifiability in the membership-query model of Charikar and Pabbaraju (2025). We characterize stable and certifiable generation, both with and without query feedback, and establish their relationships with uniform generation and identification in the limit. In particular, we give a finite-witness characterization of stable generation, analogous to Angluin's tell-tale characterization of identification, resolving a gap left open by Kalavasis, Mehrotra, and Velegkas (2025). We further compare these generation notions with identification in the limit and contrast their teaching requirements on well-studied language families, including regular and erasing pattern languages.
Introduction
Large Language Models (LLMs) exhibit remarkable capabilities across a wide variety of domains. Yet, despite their empirical success, a rigorous theoretical understanding of how and why these models succeed remains elusive. Because modern LLMs are highly complex systems, developing a mathematical foundation necessitates studying them through clean theoretical abstractions that isolate core phenomena of interest [24, 14, 19, 18, 13, 9].
One such abstraction that has recently gained significant traction is the stylized model of language generation in the limit, introduced by Kleinberg and Mullainathan [14]. Inspired by the classical inductive inference framework of Gold [11] and Angluin [3], this model asks a basic question: when a generative model is trained on a stream of examples from an unknown target language belonging to a known countable collection of languages over a domain , is there a finite point after which the model consistently produces novel and valid elements of ? Concretely, the problem is formulated as an online game in which an adversary chooses a target language along with an enumeration of all elements in . At each round , after observing , the learner outputs a guess—either a single unseen element (element-based generation) or an infinite subset of candidate outputs (set-based generation)—and succeeds in the limit if, after some finite round , all subsequent outputs are valid for .1 The main result of Kleinberg and Mullainathan [14], namely that language generation in the limit is possible for all countable collections of languages, stands in stark contrast to the classical negative results for language identification in the limit, where the learner must eventually pinpoint the exact index of in [11, 3]. This separation has sparked a vibrant line of work exploring various facets of language generation, including breadth and density [17, 5, 28, 21, 22], noisy data [32, 4, 25], privacy [26], and memory constraints [15, 7].
Yet, a crucial practical aspect of language generation has remained largely unexplored: the model of Kleinberg and Mullainathan [14] imposes no requirement on the learner to know when it is safe to stop training and start generating. Even though a successful generator is guaranteed to eventually output valid elements after some finite time , this convergence time depends on the unknown target language and enumeration, and the learner itself is never aware of whether has been reached. In real-world machine learning pipelines, however, practitioners do not train blindly; they continuously track training and validation metrics that inform them about the progress of the run and provide a concrete signal of when training is “complete” and the model can be safely deployed. To capture this phenomenon theoretically, we wish to study language generation in the limit by learners that can eventually certify that they are generating correctly; we call this certifiable language generation.
Closely intertwined with certifiability is a previously studied fundamental property of the learning process, namely stability [17, 16]. In the original setting of Kleinberg and Mullainathan [14], the learning algorithm is permitted to change its mind infinitely often, oscillating indefinitely between different candidate generating sets even after all of them are valid subsets of . Stability addresses practical situations in which we would like the training process to eventually converge to a single set to generate from. In fact, stability is a necessary condition for certifiability: once a learner can assess that it is safe to stop training, it can immediately freeze its output and stabilize from that point onward. Conversely, stability alone may not suffice to tell us when to stop training, as a stable generator could converge to a valid set at some finite time without ever knowing that the point of stabilization has been reached. Kalavasis, Mehrotra, and Velegkas [17] established a strict separation between stable and non-stable generation even for countable collections, but left open a characterization of when stable generation is possible. Thus, a central goal of our work is to characterize when both stable and certifiable generation can be achieved.
Moreover, we extend the study of stable and certifiable language generation to two natural settings that were recently introduced in the literature: (i) generation with feedback to active queries by the learner [5, 12] and (ii) generation from size-restricted sets of examples provided by the environment [23], akin to teaching sets [8] in the context of concept learning.
(i) Prior work [5, 12] studied settings in which the learner can actively obtain information about the target language by asking whether strings of its choice are in . Since stability and certifiability impose string requirements on language generation, we ask the question in which way query feedback can help to fulfill these requirements.
(ii) Both stability and certifiability require that on every enumeration of the target language , the learner eventually reaches a point of (certifiable or non-certifiable) stability, though the time and manner in which this point is reached may depend on the specific order in which examples are presented. An even more appealing scenario is when, for every language , there exists a finite “core” set of examples—which we refer to as a teaching set, borrowing terminology from learning theory [8]—such that as soon as all elements of this set appear in the input stream, the generator is guaranteed to have stabilized (or certified correctness) from that point onward, regardless of the rest of the enumeration. Beyond providing an enumeration-independent guarantee of convergence, the existence of such teaching sets is closely tied to designing data-efficient training curricula. In this work, we seek to understand the exact conditions under which stable generation and certifiable generation can be obtained—with or without teaching sets.
Main Contributions. This paper introduces the notion of certifiable language generation as a natural strengthening of stable generation. We show that certifiability is a strictly stronger requirement than stability alone, as part of a set of separation results establishing a strict hierarchy of the notions of uniform [14, 31], certifiable, stable, and unrestricted language generation, with and without query feedback. Interestingly, under query feedback, stability alone is not a restrictive condition, though certifiability is. Notably, some of our separations are witnessed by the well-studied class of pattern languages [2, 33].
To gain a deeper understanding of the additional difficulty that certifiability imposes over stability, we give characterizations of generation under these two notions, thereby answering an open question of Kalavasis, Mehrotra, and Velegkas [17, 16] asking for a characterization of stable generation. We complement these results by analogous characterizations in the query-augmented learning setting.
Our characterizations in the query-free setting rely on the structure of finite witness sets, akin to tell-tales used in characterizations in the identification setting [3]. Such finite witness sets are closely related to teaching sets studied in learning theory [8]. While teaching sets for language generation were implicitly introduced by [23], we initiate their study in the settings of stable and certifiable generation, again establishing a hierarchy across various notions of generation. In contrast to Li et al.’s [23] result, stating that generation for countable language collections can always be achieved with teaching sets of size 1, we use countable classes to exhibit arbitrarily large separations between teaching set sizes for certifiable generation, stable generation, and generation in the limit. This shows that, in general, larger teaching sets are needed to satisfy stronger requirements on the learning process.
Incidentally, we exhibit a relationship between the size of stable generation teaching sets and the size of finite sets with the so-called non-clashing property, which is known in the context of machine teaching [6], identification in the limit [27], and sample compression [20]. This relationship mirrors an analogous relationship between complexity parameters for identification in the limit [27].
Preliminaries
Let be the set of natural numbers and . Fix any countable domain . For any sequence we denote by the set of elements in . A language is consistent with if . For any and finite set , we say contains if . For any infinite sequence and natural number we denote by the prefix of length of . The concatenation of finite sequences and is denoted by .
Let be a collection of infinite languages over . Denote by the collection of all infinite subsets of . A generator is a sequence , where, for every , . For simplicity, we will write for , when is a finite sequence of length .
A repetition-free enumeration of an infinite language is an (infinite) sequence of elements in in which each element of appears exactly once. Every prefix of a repetition-free enumeration is a repetition-free finite sequence. In generation in the limit, we assume that, at each time step, a previously unseen training datum is presented (alternatively, one may allow for repetitions, which can be ignored by the learner). Therefore, for simplicity, when we use the term enumeration, we implicitly refer to a repetition-free enumeration.
Definition 2.1 ([14]). A collection is generatable in the limit if there is a generator such that, for every and every enumeration of , there exists satisfying for every .
Definition 2.2 ([14, 31]). For , a collection is -uniformly generatable if there is a generator such that for every , every enumeration of , and every we have . It is uniformly generatable if it is -uniformly generatable for some .
We contrast the notion of generation with the notion of identification, which requires eventual recovery of the whole target, rather than of an infinite subset.
Definition 2.3 ([11]). A collection is identifiable in the limit if there exists a mapping such that, for every and every enumeration of , there is satisfying for every .
Language collections that are identifiable in the limit can be characterized by assignments of finite sets with a certain structural property, to be defined next.
Definition 2.4 ([3, 6]). Let be a language collection, and let be a family of finite sets such that for every .
(i) is called a tell-tale assignment if implies , whenever .
(ii) is called non-clashing if or for any with .
Theorem 2.5 ([3, 27]). For every countable language collection , the following statements are equivalent:
(i) is identifiable in the limit.
(ii) admits a tell-tale assignment of finite sets.
(iii) admits a non-clashing assignment of finite sets.
These characterizations also connect identification in the limit to machine teaching. In the machine teaching literature, the positive non-clash teaching dimension () measures the smallest uniform bound on the sizes of sets in a non-clashing assignment.
Definition 2.6 ([6]). The positive non-clash teaching dimension of a language collection is defined as
We will later adapt the notion of tell-tale assignment to stable language generation and then show that it is useful to likewise measure the smallest uniform bound on the sizes of such tell-tale sets.
Stable and Certifiable Language Generation
One of our central goals is to model and study language generation with a learner that can eventually certify that it is sufficiently well trained to guarantee correct generation from the target language. Clearly, once such a certificate can be issued, the generator may choose to stabilize on its current output, i.e., no further training is necessary. Stability, which requires the generator to stop changing its output after a finite time, was recently introduced by Kalavasis, Mehrotra, and Velegkas [17]. We will show below that this condition is strictly weaker than our proposed condition of certifiability.
Definition 3.1 ([17]). A collection is stably generatable if there exists a generator such that, for every and every enumeration of , there is such that for every , we have .
Definition 3.2. A collection is certifiably generatable if there exist a generator and a certificate satisfying:
(i) Soundness. For every , if , then for every consistent with .
(ii) Eventual certification. For every and every enumeration of , there is such that .
Remark 3.3. After certification, the generator may retain its certified output on every extension of the prefix on which the certificate was obtained. This preserves soundness, because every language consistent with the extension was also consistent at the time of certification. Thus a certifiable generator can be made stable. Theorem 3.6 will show that the converse is not true in general.
Finite-Witness Characterizations
Pinpointing the structural properties of language classes that are generatable in a given model provides insights into the nature of standardized underlying learning processes. To this end, we derive finite-witness characterizations for stable and certifiable generation, similar to the analogous characterizations for identification, see Theorem 2.5. Our finite witnesses for stable generation satisfy a weakened non-clashing condition, allowing distinct languages to receive the same witness.
Theorem 3.4. A collection is stably generatable if and only if there is an assignment of finite sets , , satisfying:
(i) For every ,
(ii) For every , , .
Proof. If direction. Define the generator as follows. For every finite sequence , choose an arbitrary language with , and define
If no language with exists, define arbitrarily. Fix a target language . Since is finite, every enumeration of has a prefix containing . Consider any extension of such prefix, satisfying . Suppose that some also satisfies . Then . By condition (ii), this implies . Therefore, every language that can be selected by the generator at this point has the same associated set as . Consequently, , which is infinite by condition (i), is contained in , and remains unchanged on every subsequent prefix. Hence, is stably generatable.
Only-if direction. Consider a generator that stably generates . Consider a fixed ordering of . For every , we construct a finite sequence in phases and then take .
Initialize . In phase , let be the first element in according to the ordering , and set . Consider all finite repetition-free sequences over . If there is such a sequence with , let be the first such sequence in the shortlex order on finite sequences induced by the ordering of , and set . Otherwise, stop and define and .
Because each phase includes the least unseen element in the fixed order, an infinite run would enumerate with changing its output infinitely many times, contradicting stable generation. Therefore the process terminates after a finite number of phases, and is finite.
By the stopping condition, no continuation over changes the output. Complete to an enumeration of . The generator outputs on every subsequent prefix, and correctness on this enumeration implies that this set is contained in . Thus
We next compare the constructions for two languages such that . For the sake of contradiction, suppose . Let be the largest index such that . There are two cases. First observe that since , we have . Similarly . Thus, . This indicates that .
Case 1. Construction of or stops at phase . Without loss of generality, suppose that the construction for stops and note that the construction of cannot stop as otherwise . The extension satisfies . It is also consistent with and is a sequence of . Thus, it is also a sequence of . This contradicts stopping.
Case 2. Both constructions continue, but is not equal to . Without loss of generality, suppose comes first in the shortlex order. Observe that and that . Thus, was an available continuation of for that would change the output of as well. Hence, it should have been chosen before contradicting the rule of selecting the first such continuation in shortlex order.
::: Since neither case is possible, the two constructions agree in every phase and thus . Therefore, . This proves condition (ii).
Finally, fix . Whenever , these sets are mutually consistent with and , so the preceding argument gives . Applying (3) to each such yields . Since is infinite, this proves condition (i) and completes the proof. □
The following characterization of certifiable generatability is not difficult to prove (see Appendix A); the standardized generator for the “if” direction always simply outputs the intersection of all languages in that are consistent with the observed data whenever the intersection is infinite.
Theorem 3.5. A collection is certifiably generatable if and only if, for every , there is a finite set such that
These characterizations now help to establish the following hierarchy of requirements on language generation; see also Figure 1 for a complete hierarchy including notions introduced in § 4.

Figure 1. Hierarchy of language generation. A path from to exists if and only if every language family having a generator/learner of type also has a generator/learner of type .
Theorem 3.6. For every collection of infinite languages, the following implications hold.
Every implication is strict.
Proof. (Sketch.) Implications are shown by standardizing generators witnessing so as to satisfy the criteria for . Strictness is shown using the class of all languages for the first implication; the class of all languages for the second implication; and the class of all languages plus the language (which was also used by [16]) for the third implication. See Appendix A for a full proof. □
Separations Witnessed by Families of Pattern Languages
It is not difficult to construct language families that are stably or certifiably generatable, but are not identifiable in the limit. For instance, any language collection with a common infinite intersection is 1-uniformly generatable. Notably though, we will show that similar separations also arise for natural structured language families, specifically, for classes of (erasing) pattern languages, which we will introduce next, following the original definitions by Angluin [2] and Shinohara [33].
Let be a finite alphabet with and let be a countable set of variables disjoint from . A pattern is a finite word containing at least one variable.6 An erasing substitution fixes the symbols of and maps each variable to an arbitrary word in , possibly the empty word . It extends to a homomorphism on patterns. The corresponding erasing pattern language is
We write eP for the collection of these languages, and eTFP for the subcollection defined by nonempty terminal-free patterns . All these languages are infinite.
While uniform generation is a very strong requirement, for binary alphabets, the class is a “natural” language family that is 2-uniformly generatable, but not identifiable in the limit. 2-uniform generatability is shown by constructing an infinite subset of the target language directly from the first non-empty word observed in the enumeration of ; see Appendix § 8 for details.
Theorem 3.7. The collection is certifiably generatable and 2-uniformly generatable, but is not 1-uniformly generatable, and, when , not identifiable in the limit.
Allowing terminal symbols results in a class that is no longer uniformly, but still stably generatable. The proof details are more involved than for Theorem 3.7 and are also provided in Appendix § 8.
Theorem 3.8. The collection is stably generatable, but is not uniformly generatable, and, when , not identifiable in the limit.
Stable and Certifiable Language Generation with Query Feedback
Since stable and certifiable generation is difficult to achieve even for some structurally simple language classes, it is natural to ask whether feedback can help the learner. We therefore define and analyze stability and certifiability in the membership-query model of Charikar and Pabbaraju [5], which was later studied by Hanneke et al. [12]. In this model, at round , the generator observes the initial segment of an enumeration of the target language , chooses a query based on and the previous query answers, and receives . The generator’s output may depend on the full interaction history , where . The query strategy is fixed as part of the generating procedure, and hence the queried points can be reconstructed from the interaction history. We first recall the set-output version of generation with query feedback introduced by Hanneke et al. [12].
Definition 4.1 ([5]). A query-feedback generator consists of a query strategy and a sequence of maps where for every , . It generates in the limit with query feedback if, for every and every enumeration of , there exists satisfying for all .
We generalize this model to stable and certifiable generation with query feedback.
Definition 4.2. A collection is stably generatable with query feedback if there is a query-feedback generator such that, for every and every enumeration of , there exists satisfying for every .
The notion of certifiability is defined analogously to the no-feedback setting, except that the certificate may now depend on both the observed positive examples and the answers to the membership queries. Thus, when certification occurs, the current output must be valid for every language consistent with the entire interaction history, including the answers to the queries. To formalize this, for finite disjoint sets , define the signed version space
At round , let and . Then is exactly the collection of languages in that are consistent with all observed examples and all membership-query answers up to round .
Definition 4.3. A collection is certifiably generatable with query feedback if there exist a query-feedback generator and certificate satisfying:
(i) On every realizable finite interaction, if , then .
(ii) For every and every enumeration of , the induced interaction satisfies for some .
Query-feedback generation was characterized by Hanneke et al. [12] in terms of the existence of a countable inner-cover, defined below. Interestingly, stable query-feedback generation admits the same characterization; the reader is referred to Appendix § 9 for a proof of Theorem 4.5.
Definition 4.4. A countable inner-cover of is a countable family such that every contains some . The sets need not belong to .
Theorem 4.5. For a collection , the following are equivalent:
(i) is stably generatable with query feedback.
(ii) is generatable in the limit with query-feedback generator (with set-valued output).
(iii) has a countable inner-cover.
We next characterize certifiable generation with query feedback in terms of finite positive and negative witnesses; the proof is again provided in Appendix § 9.
Theorem 4.6. A collection is certifiably generatable with query feedback if and only if, for every , there exist finite sets and such that .
Figure 1 summarizes the relationships between the notions studied in this paper. In particular, it shows that certifiable generation with query feedback is fundamentally different from both stable and ordinary query-feedback generation. We show that there exists a collection that is stably generatable in the limit even without feedback (and identifiable in the limit), but not certifiably generatable with query feedback. Thus, although membership queries allow a learner to observe negative examples, they do not suffice to certify every stably generatable collection. See Appendix § 9 for proof details.
Theorem 4.7. In Figure 1, there is a directed path from to if and only if every language family having a generator/learner of type also has a generator/learner of type .
Stable and Certifiable Language Generation with a Teacher
Stability and certifiability conditions require a generator to eventually stabilize, regardless of the input enumeration chosen for the target language. It is natural to ask whether, for any language in a stably or certifiably generatable family , there is a finite set such that, as soon as appears in the input enumeration, a generator can stabilize. We call such a teaching set for (with respect to ). One can then measure the complexity of training a generator for by the supremal size of a smallest teaching set for , where the supremum—called teaching dimension—is taken over all languages . This approach parallels machine teaching for language identification [8], except that the objective here is successful generation rather than exact identification of the target language.
We begin by defining notions of teaching set and teaching dimension for generation in the limit, stable generation in the limit, and finally certifiable generation in the limit. [23] already established that finite teaching sets always exist for generation in the limit, without stability and certifiability conditions. They introduced a parameter called positive separation width, which coincides with our notion of generation teaching dimension (), when the latter is finite.
Definition 5.1. For a generator and , a finite set is a generation teaching set for if for every containing . Let be the collection of all such sets. Define
Here we assume that the infimum taken over the empty set is .
Note that we require the generator to generate successfully on every input that contains the teaching set, rather than only on the teaching set itself. This is analogous in spirit to the collusion-freeness requirements used in machine teaching which prevent the teacher and learner from using coding tricks [10, 6]. Without this requirement, a teacher could, for example, encode a representation of the target language in the teaching set, which the learner (or generator) would be able to decode. Successful learning from any enumeration containing the teaching set prevents such coding tricks.
[23] showed that every collection that is generatable in limit admits a generator with finite generation teaching sets; for countable collections, the size of these sets can be bounded by 1.
Theorem 5.2. ([23]). A language collection is generatable in the limit if and only if there is a generator such that every has a finite generation teaching set with respect to . Moreover, for every countable collection , we have .
We next adapt teaching to stable generation. In addition to guaranteeing correctness after the teaching set has appeared, we require the generator’s output to remain unchanged under every subsequent target-consistent continuation, yielding the notion of Stable Generation Teaching Dimension.
Definition 5.3. For a generator and , a finite set is a stable generation teaching set if, for every containing and every , we have . Let be the collection of these sets. Define
Here we assume that the infimum taken over the empty set is .
Finally, we define a notion of Certifiable Generation Teaching Dimension. Here, a teaching set must provide enough information to certify an infinite set of outputs that is valid for every language consistent with the teaching set.
Definition 5.4. For , a finite set is a certifiable generation teaching set if
Define
Relationships and Basic Properties
It is easy to see that for every language collection . This subsection addresses the question by how much these parameters can differ. Since teaching sets for each of the studied notions of generation bear some conceptual similarity with the non-clashing finite witness sets from our characterization of stable generatability (Theorem 3.4), we will additionally compare our three teaching dimension parameters to the size of the finite witnesses therein:
Definition 5.5. Let be the set of assignments of finite sets satisfying (1) and (2). Define the Stable Non-Clashing Positive Witness Size by
In the identification setting, [27] noted that non-clashing assignments are always tell-tale assignments, and thus that the smallest uniform bound on the tell-tale size never exceeds . Interestingly, in a setting without computability requirements, tell-tales can be construed as teaching sets for identification in the same sense as stable generation teaching sets are teaching sets for stable generation. (If the learner has seen the tell-tale for a consistent language , it is safe to output : If is incorrect, the target cannot be a proper subset of , as it contains the tell-tale for . Hence, some string outside will be enumerated at some point, at which the learner will be allowed to change its mind again.) This motivates the following definition of Teaching Dimension for Identification.
Definition 5.6. , where ranges over all tell-tale assignments for .
Thus, according to [27], ITD never exceeds (but it may be smaller). Theorem 5.7 establishes an analogous relationship between SGTD and .
Theorem 5.7. for every collection . Moreover, there are countable collections such that and , and , as well as and .
Proof. (Partial sketch.) Proving the chain of inequalities is fairly straightforward. The first separation is obtained with . The construction of the classes and is much more intricate; the reader is referred to Appendix § 10.
Knowing that for countable collections, it is natural to ask whether the same holds for SGTD, , and CGTD. The following theorem shows that these parameters can take any positive integer value even for countable classes.
Theorem 5.8. For every integer , there exists a countable collection of infinite languages over a countable domain such that .
Proof. (Sketch.) The claim can be verified by defining disjoint countably infinite sets and , setting , and . See Appendix C for details.
For finite collections, however, we show in Appendix C that all four teaching-related parameters for the generation setting are at most one. By Theorem 5.7, it suffices to prove this bound for CGTD.
Theorem 5.9. For every finite collection , the dimensions , , , and all equal if is infinite, and otherwise.
GTD versus Complexity of Identification and Uniform Generation
We conclude this section by comparing the complexity of teaching for generation with the complexity of uniform generation and the complexity of teaching for identification. As discussed before Theorem 5.7, we use ITD as a notion of teaching dimension for identification; recall that ITD NCTD. We provide very simple arguments showing that, even for finite collections of regular languages, (i) uniform generation and (ii) identification can demand many examples, while certifiable generation requires at most one carefully chosen example for each target.
Theorem 5.10. (i) There exists such that, for every , there exists a family of infinite binary regular languages such that , each is accepted by a DFA with at most states, and is not -uniformly generatable, while .
(ii) For every , there exists a finite family of infinite binary regular languages such that , every is recognizable by a DFA with at most states, and , while and is -uniformly generatable.
Proof. (Sketch.) The first statement can be derived from the proof of Theorem 4.1 by [1]. The second statement is witnessed by the class . One can show that any tell-tale for in this class has size at least . See Appendix C for details.
Conclusion
We introduced certifiable language generation, which requires a generator to eventually recognize that its output is valid. We studied it alongside the stability requirement of [17]. Our finite-witness characterizations of stable and certifiable generation resolve the open question of characterizing stable generation, and they place both notions in a strict hierarchy between uniform generation and generation in the limit. Natural families such as erasing pattern languages witness some of these separations. With queries, stability imposes no restriction beyond generation in the limit. Certifiability remains restrictive: some collections are identifiable in the limit yet cannot be certifiably generated even with queries. We initiated the study of teaching sets for generation, and showed that stronger success criteria can require arbitrarily larger teaching sets, in contrast to the bound of one for generation in the limit. We also showed that, already for finite families of regular languages, teaching for certifiable generation can be far cheaper than uniform generation or identification. Interesting future directions include resource-bounded versions of our notions in the query feedback framework, and certification guarantees under noisy or adversarially corrupted data.
AI Disclosure. Generative AI tools were used to assist with working out details of some of our technical proofs, with drafting small parts of the writing, as well as with checking earlier drafts for technical errors and typos. The authors assume full responsibility for the entire content and presentation of the paper.
References
Proofs Omitted from Section 3
Theorem 3.5. A collection is certifiably generatable if and only if, for every , there is a finite set such that
Proof. For the only-if direction, fix and any enumeration of . Let be a round at which certification occurs, and set . Soundness gives
The left-hand side is infinite, so (4) holds.
For the if direction, suppose that every contains a finite set satisfying (4). For a finite sequence , consider
If at least one language is consistent with and is infinite, define and . Otherwise, define and . This procedure is sound.
Fix and an enumeration of . Since is finite, there is a round such that for every . For every such , any language containing also contains . Therefore,
The right-hand side is infinite by assumption. Hence for every , which proves eventual certification.
Theorem 3.6. For every collection of infinite languages, the following implications hold.
Every implication is strict.
Proof. Suppose first that is -uniformly generatable by . Set whenever , and set otherwise. If has length at least , uniform generation guarantees for every consistent with . Thus this certification rule is sound. Every target is infinite, so its enumeration eventually reaches the threshold. Therefore is certifiably generatable.
Next, suppose that is certifiably generatable. Modify the generator so that, after its first certification, it retains the certified output. On an enumeration of a target , certification occurs after a finite number of rounds, and soundness implies that the retained infinite set is contained in . The modified generator is therefore stable. Finally, a stable generator is eventually correct, so stable generation implies generation in the limit.
A collection that is certifiably generatable but not uniformly generatable can be defined as follows: For every , define . These are infinite sets of odd numbers. They are pairwise disjoint because, for every , the largest power of two dividing is exactly . Now consider
We first show that is certifiably generatable. Fix a target and choose any . If , then, since is odd, it must belong to . Disjointness of the sets implies . Thus the only language in containing is , and . This intersection is infinite. Therefore is a certifying witness for , and Theorem 3.5 gives certifiable generation. On the other hand, notice that for every we have
This implies that is not -uniformly generatable. Thus, is not uniformly generatable.
A collection that is stably generatable but not certifiably generatable is given by over . Define , where . For a target , all of eventually appears, whereas never appears. From that point onward, , so the generator always outputs . Thus is stably generatable. (Since the output eventually equals the target language itself, the same map also identifies in the limit.) On the other hand, for every finite , we have . This intersection is finite, so Theorem 3.5 implies that is not certifiably generatable.
Finally, Theorem 8.7 of Kalavasis, Mehrotra, and Velegkas [16] showed that the collection is not stably generatable, but it is generatable in the limit due to countability [14].
Theorem 3.7. The collection is certifiably generatable and 2-uniformly generatable, but is not 1-uniformly generatable, and, when , not identifiable in the limit.
Proof. Reidenbach [29] proved that, when , the class is not (even non-computably) identifiable in the limit. To see that is not 1-uniformly generatable, note that the first example in an enumeration of a target language may be the empty word , which belongs to every terminal-free erasing pattern language, while . Thus no infinite output can be valid for every language consistent with this first example.
On the other hand, consider the first two examples in any enumeration of any target language . One of these two examples must be a nonempty word for some and . We claim that is an infinite subset of . Indeed, take a substitution generating and replace each letter in its variable images by . Since the pattern is terminal-free, this produces . These words have distinct lengths, so is infinite. The generator can therefore output and certify its validity. Hence the collection is 2-uniformly generatable. Moreover, any nonempty word in a target language forms a singleton certifiable teaching set, implying certifiable generatability. \qed
Theorem 3.8. The collection is stably generatable, but is not uniformly generatable, and, when , not identifiable in the limit.
Proof. For , Reidenbach [30] proved that is not (even non-computably) identifiable in the limit. (Reidenbach’s proof goes through even when excluding patterns that have no variables.) We first prove stable generatability using two-word witnesses, and then prove the impossibility of uniform generation using finite intersections of pattern languages.
Stable generation. Fix a shortlex ordering on . For every , let and denote, respectively, the first and second elements of according to , and define .
We verify the two conditions in Theorem 3.4, starting with the second condition. For , suppose . Since and , by minimality of the first elements we have , and , and hence . Similarly, and . Since these are the smallest elements strictly larger than in the respective languages, . Thus .
Consider any , and any such that and , i.e., . The word obtained by erasing every variable from is the unique shortest word of ; hence it is .
For every variable , let denote the number of occurrences of and let . Every word in has length at least , and this bound is attained by mapping a variable with to a single terminal symbol and erasing every other variable. Therefore, .
Moreover, every substitution producing a word of this length maps exactly one variable with to a single symbol and maps all other variables to the empty word. Thus is obtained from by inserting exactly copies of one symbol .
Write
Then, for uniquely determined with ,
For every , define
Mapping to and every other variable to the empty word shows that for every , . Hence
is an infinite subset of .
Since is chosen arbitrarily, this implies . This proves the first condition.
Impossibility of uniform generation. Choose distinct symbols , and consider , and . We first prove that
A word in the intersection has representations . Comparing lengths gives , and comparing the initial blocks of this length gives . Cancelling the common prefix then gives , which forces to consist only of copies of . Conversely, substituting implies that is in both languages and establishes the displayed equality.
Fix any , and define
where are distinct variables. We claim that . Observe that proving this claim shows that is not -uniformly generatable. Since was chosen arbitrarily this proves that is not uniformly generatable.
For each , map to and erase every other variable. This produces , so .
We now prove . Consider a substitution of producing a word in . The word has exactly one occurrence of , already defined by the terminal in , and all its other symbols are . Every variable must therefore be substituted by for some . The numbers of 's before and after the terminal are, respectively, and . For a word in , their difference must be one. Thus , i.e., exactly one variable for is mapped to , and all other variables are erased. This will imply that the word is in , proving the claim.
Proofs Omitted from Section 4
Theorem 4.5. For a collection , the following are equivalent:
(i) is stably generatable with query feedback.
(ii) is generatable in the limit with query-feedback generator (with set-valued output).
(iii) has a countable inner-cover.
Proof. The equivalence of (ii) and (iii) is Theorem 3.4 of Hanneke et al. [12]. The following proof makes the stable-support conclusion explicit. Furthermore, (i) (ii) follows directly from the definition: a stable output that is contained in the target is, in particular, eventually correct. It remains to prove (iii) (i).
Suppose that has a countable inner-cover . A finite nonempty cover can be listed in this form by repeating its elements. Fix an enumeration of , and query at round . Let
be the set of negatively answered query points. Define
This minimum exists on every realizable interaction. Indeed, the target contains some cover element , and no point of can receive a negative answer. Thus at least one index is always eligible. On an unrealizable interaction for which there is no eligible index, define the output arbitrarily as .
Fix a target , and let
The index is never excluded, so at every round. For each , the minimality of implies . Choose a point . The fixed query sequence eventually queries and receives a negative answer. From that round onward, , so index is permanently excluded.
There are only finitely many indices below . Hence there is a finite round by which all of them have been excluded. Since remains eligible, for every we have
The output is therefore constant and valid from round onward. This proves stable generation.
Theorem 4.6. A collection is certifiably generatable with query feedback if and only if, for every , there exist finite sets and such that .
Proof. For necessity, fix and an enumeration of . Take a finite transcript at which certification occurs. Let consist of the observed positive examples and positive query points, and let consist of the negative query points. Every language in is consistent with this transcript. Soundness therefore places the certified infinite output in their common intersection.
For sufficiency, fix an enumeration of and query at round . Let record all positive and negative information available at that time. Define
Let the output of generator be arbitrary whenever is finite, and whenever it is infinite. Furthermore, certify whenever, is infinite. On every realizable transcript, the target belongs to the version space, so certification is sound.
Fix a target and its finite witnesses . Since the queries exhaust in the fixed order, every element of is eventually queried at a time . At that time,
and hence
The latter intersection is infinite, so certification occurs after finitely many rounds.
Theorem 4.7. In Figure 1, there is a directed path from to if and only if every language family having a generator/learner of type also has a generator/learner of type .
Proof. Theorem 3.6 establishes the three strict inclusions between uniform, certifiable, stable, and generation in the limit. Propositions B.1 and B.2 establish the strict inclusion of certifiable generation with query feedback in stable generation without feedback. The strictness of inclusion of generation in limit in generation in limit with query-feedback is proven in Theorem 3.10 of Hanneke et al. [12]. The equivalence of stable and ordinary generation with query feedback follows from Theorem 4.5.
We establish the remaining relations.
Certifiable generation versus certifiable generation with query feedback. By Theorem 3.6 the collection is not certifiably generatable without feedback. However, for each target , let and . Then . Theorem 4.6 implies that the collection is certifiably generatable with query feedback. The reverse inclusion follows by ignoring queries.
Identification in the limit. Identification implies stable generation by outputting the language hypothesized by the identifier. The inclusion is strict by Theorem 3.8, which gives a stably generatable collection that is not identifiable in the limit. Furthermore, Theorem 3.7 gives a uniformly generatable collection that is not identifiable in the limit. Conversely, the collection in Proposition B.2 is also identifiable in the limit, but is not certifiably generatable even with query feedback.
Therefore, identification is incomparable with uniform generation, certifiable generation, and certifiable generation with query feedback. This proves all the claimed relations.
:::
Proposition B.1. If a collection is certifiably generatable with query feedback, then it is stably generatable even without feedback.
Proof. For finite disjoint sets , let . Define the family of finite pairs that can witness the characterization in Theorem 4.6 as
Observe that since is countable, is also countable. Let be an enumeration of and let . By definition, every is infinite. Moreover, by the characterization of certifiable generation with query feedback, for every there is an index such that and .
We now define the generator without feedback. For a finite sequence , let and define , whenever the defined set is not empty. The generator is defined as
Fix a target language and an enumeration of . Let
Since is finite, every enumeration of eventually contains . Furthermore, no element of appears in the enumeration. Consequently, there will be some round such that is a subset of the instances appeared so far and has empty intersection with the input, meaning that the generator will consider this as an index in the set it is minimizing.
Now consider any . By the minimality of , either or . In the first case, is never contained in the observed examples, so is never considered by the generator. In the second case, choose . Since enumerates , there is a finite round at which appears. From that round onward, , so will never be considered.
There are only finitely many indices smaller than . Thus there is a round such that for every . Since , we have
The output is therefore constant and valid from round onward, proving stable generation without feedback.
We now show that the above implication is strict, namely, there is a countable collection that is stably generatable but not certifiably generatable even with query feedback.
Proposition B.2. There exists a countable collection that is both stably generatable without feedback and identifiable in the limit but not certifiably generatable with query feedback.
Proof. Let and be disjoint countably infinite sets, and let . Define
Note that every language in is infinite.
We first show that is stably generatable. For a finite sequence , define , and let
On every enumeration of , no element from will appear, and hence the generator outputs in every round. For any target , the element eventually appears in the enumeration. Since from that round onward the generator outputs and never changes its output. Thus is stably generatable without feedback. Since the output of the generator eventually equals the target language itself, the same map also identifies in the limit.
We next show that is not certifiably generatable with query feedback. Consider the target and any finite sets and . By construction,
Since excludes and excludes every element from , we obtain
The right-hand side is finite. Therefore no finite sets and can be a witness to the characterization of certifiable generation for . Hence, is not certifiably generatable with query feedback.
Proofs Omitted from Section 5
Theorem 5.7. for every collection . Moreover, there are countable collections such that and , and , as well as and .
Proof. We first prove the chain of inequalities. Every stable generation teaching set is a generation teaching set, giving the first inequality.
Next, consider any admissible assignment . In the if direction of Theorem 3.4, we constructed a generator that satisfies , which proves the second inequality.
To prove , it suffices to consider the case . Fix an enumeration of all finite sets of size at most that satisfy the property in (4). Such sets form a countable family because is countable. For every , assign the first set in this enumeration that is contained in , and denote it by . The definition of CGTD ensures that this choice exists.
We show that the assignment satisfies (1) and (2). Consider any and such that . Then each assigned set was an available choice for both languages. Since we chose the first available set according to a fixed enumeration for both languages, we must have . Therefore, the assignment satisfies (2). Furthermore, we have
Consequently, the assignment satisfies (1). Therefore , proving the last inequality.
For the first separation, use the collection which is also used by Kalavasis, Mehrotra, and Velegkas [16]. This collection is not stably generatable, so . On the other hand, since is countable, Theorem 5.2 gives .
The second and third separations are witnessed by the constructions in Corollary C.3 and Proposition C.1.
Throughout this appendix, the term “admissible assignment” refers to an element of , as in Definition 5.5.
The following construction witnesses the third separation in Theorem 5.7, between and CGTD.
Proposition C.1. There exists a countable collection such that and .
Proof. For , define
and let . This collection is countably infinite, and every language contains an infinite odd tail.
We first show that . Assign . Every language assigned contains the odd tail starting at , so
Thus the languages assigned the same set have infinite intersection. Furthermore, if , then , since the largest even number in is . Hence two languages assigned different sets cannot both contain one another’s assigned set. The assignment is therefore admissible, proving . Since the intersection of languages in the class is not infinite, we have .
We next show that no target has a finite certifiable teaching set. Fix any finite , and choose an integer . Then for every . Consequently,
Indeed, the common even elements are those at most , and every odd number beyond the initial odd segment is excluded once is large enough. The displayed intersection is finite. Since was chosen arbitrarily, this implies that .
The following construction witnesses the second separation in Theorem 5.7, between SGTD and .
Theorem C.2. For every , there is a countably infinite collection of cofinite languages over a countable domain such that
Moreover, the generator witnessing the first equality depends only on the set of observed examples and has exactly two possible outputs.
Proof. Fix , and set
We have . When , the family consists only of the empty set. Define two finite marker sets
where and , are distinct elements, and countably infinite sets such that , , , and are pairwise disjoint. Let and .
For every and , define
Now define families and that are obtained by allowing at most one deletion from and , respectively, as follows:
Set
This collection is countably infinite. Every language omits only finitely many markers and at most one point of , so every language is cofinite. Furthermore, every language in a family contains all of , and every language in a family contains all of .
Proof of SGTD() = 1. For a finite training sequence , define
and let
This generator depends only on the observed set and always outputs one of the two infinite sets .
For a target , use the singleton teaching set . Consider any containing . Observe that
Furthermore, any in any language in satisfies . Therefore . Consequently, . The same reasoning applies for every continuation of in , so the output remains .
For a target , use the singleton teaching set . Every marker that can appear in a sequence consistent with has . Once has appeared, the union subtracted in the definition of contains all of . It therefore contains every possible for any observed , so and . Again, the same argument holds on every consistent continuation, and the output remains . Consequently, every target has a singleton stable generation teaching set, proving SGTD() .
Every is excluded by a language , and every is excluded by a language . It follows that . This intersection is finite, so SGTD() .
Proof of SNC. Assign
The assigned sets are contained in their targets and have size at most . All the languages that are assigned the set contain , and all those assigned to contain . Hence both required intersections are infinite and satisfy the condition (1).
We prove the condition (2). For a pair of languages to be assigned to different sets it must be that one belongs to and the other belongs to . However, for every , every language in contains exactly markers from . Hence, it cannot contain , so mutual consistency is impossible. Therefore the assignment is admissible, and SNC.
Proof of . Suppose, for the sake of contradiction, that there is an admissible assignment with for every . For a finite set , define
Each set has size , and an assigned teaching set contains at most markers from . Therefore
The only instances missing from are the markers for which . Consequently, for every finite set ,
Write . If , condition (2) implies that at least one of and fails. By (7), this means or . Select indices whose teaching sets are pairwise distinct. Each of their pairs requires at least one such membership. On the other hand, each selected contains at most indices and can account for at most pairs. Hence, , which gives . There are therefore at most different teaching sets among the languages .
Since , some teaching set occurs on at least indices. Let
We next show that there must exist some such that receives this same teaching set. The set of indices has size at most , so choose an -element set containing all of these indices. The language contains the corresponding -markers and every point of . Hence . Furthermore, , so there is an index . By (7), . We also know from the definition of that and hence . The two teaching sets are mutually consistent. Condition (2) therefore forces .
Fix any . The language contains and is a subset of . Its own teaching set is contained in , and therefore in . Thus and . Applying (2) again gives .
Similarly, fix any . Since contains and is contained in , we have and . Therefore as well.
Thus, for every , there is some with and . Consequently,
Since is finite, this contradicts the infinite-intersection condition for languages assigned the same teaching set. Hence, no assignment of maximum size is possible and . Combining the upper and lower bounds proves .
Corollary C.3. There is a countably infinite collection over a countable domain such that and .
Proof. For each , let be the domain of the collection constructed in Theorem C.2, and let be its generator. Take disjoint tagged copies of these collections. Formally, let
Both the domain and the collection are countable. We first show that .
On a nonempty training sequence whose elements all have the same tag , remove the tags, apply , and add tag to every element of its output. On the empty sequence output any fixed infinite set. For a target , use the tagged copy of the singleton teaching set for . Every consistent sequence containing this point is nonempty and lies entirely in component . The component generator is stable and correct once its singleton has appeared, so the tagged generator has the same property. Therefore . Languages in different components are disjoint, so their common intersection is empty, ruling out dimension zero.
We next show that . Consider any admissible assignment and restrict it to one tagged component. The no-clash condition continues to hold, since it concerns only pairs of languages. Also, restricting the assignment only removes languages from each collection , so their common intersection remains infinite. Thus the restriction is an admissible assignment on that component. Removing the tags does not change any teaching-set size. Consequently,
No uniform finite bound can satisfy these inequalities, and hence .
Theorem 5.8. For every integer , there exists a countable collection of infinite languages over a countable domain such that .
Proof. Let , be disjoint countably infinite sets, and set . Define
and let . Every language in is infinite. Furthermore, is countable, since a countable set has only countably many finite subsets. By Theorem 5.7, it suffices to show that and .
**Proof of T_A={a_1,\ldots,a_n}$, . Every language in contains at most elements of , so none contains . Therefore,
The last equality holds because every language in contains , and itself belongs to . Similarly, . Both intersections are infinite. Thus certifies every target in and the target , while certifies every target in . Since these sets have size , we conclude that .
Proof of . We first show that, for every finite with ,
Consider the languages , . Since , we have and . Both languages contain , and . Consequently,
proving (8). This already shows that . Next, for the sake of contradiction, suppose there exists a generator which admits stable teaching sets of size at most for every . Let , and let be a sequence listing the elements of . Since is a stable teaching set for , we have
for every continuation over .
We claim that for every containing . To prove this, fix such a language , and let list the elements of . The concatenation is a sequence of distinct elements of and contains . Therefore, the teaching guarantee for gives . On the other hand, (9) gives . Thus , proving the claim.
It follows that . Since , equation (6) implies that the intersection on the right is . Hence , contradicting the requirement that is infinite. Therefore .
Theorem 5.9. For every finite collection , the dimensions , , , and all equal if is infinite, and otherwise.
Proof. Upper bound of 1. For every , let . Fix and define
Since is finite, there are only finitely many subfamilies . Hence is a finite union of finite sets and therefore is finite. Since is infinite, choose and set .
Let . Suppose for the sake of contradiction that is finite. Since , the subfamily appears in the definition of , and hence . On the other hand, by the definition of , . Therefore , contradicting the choice of . Thus . Hence, .
Dimension 0 iff is infinite. If , we may take for every , yielding . Conversely, if , choose a generator with . Then for every , . Thus, . Together with Theorem 5.7 this completes the proof.
Theorem 5.10. (i) There exists such that, for every , there exists a family of infinite binary regular languages such that , each is accepted by a DFA with at most states, and is not -uniformly generatable, while .
(ii) For every , there exists a finite family of infinite binary regular languages such that , every is recognizable by a DFA with at most states, and , while and is -uniformly generatable.
Proof. The first statement follows from Theorem 4.1 of [1]. The family constructed there has the stated DFA complexity and is not -uniformly generatable. Moreover, the common intersection of the languages in the construction is finite. Since is a finite collection of infinite languages, Theorem 5.9 implies that .
For the second statement, let and define . Then
Define and, for every , . Let . Clearly, . Furthermore, , which implies and is 0-uniformly generatable.
The language is recognizable by a one-state DFA. Moreover, for every , the language can be recognized by a DFA with states: the automaton keeps track of the longest prefix of read so far, moves to an accepting sink upon any mismatch, and rejects only when the input ends exactly after reading .
We next prove , which immediately implies . Let be a tell-tale assignment. For every , , so that the tell-tale set for is not a subset of . Thus for all ; in particular, .
References
- [1]Marcelo Arenas, Pablo Barceló, Luis Cofré, and Alexander Kozachinskiy. “Language generation: Complexity barriers and implications for learning”. In: arXiv preprint arXiv:2511.05759 (2025).arxiv.org/abs/2511.05759
- [2]Dana Angluin. “Finding Patterns Common to a Set of Strings”. In: Journal of Computer and System Sciences 21.1 (1980), pp. 46–62.DOI
- [3]Dana Angluin. “Inductive inference of formal languages from positive data”. In: Information and Control 45.2 (1980), pp. 117–135.DOI
- [4]Yannan Bai, Debmalya Panigrahi, and Ian Zhang. “Language generation in the limit: Noise, loss, and feedback”. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2026, pp. 794–816.DOI
- [5]Moses Charikar and Chirag Pabbaraju. “Exploring Facets of Language Generation in the Limit”. In: Proceedings of 38th Conference on Learning Theory (COLT). Vol. 291. Proceedings of Machine Learning Research. 2025, pp. 854–887.arxiv.org/abs/2411.15364
- [6]Shaun M. Fallat, David G. Kirkpatrick, Hans Ulrich Simon, Abolghasem Soltani, and Sandra Zilles. “On Batch Teaching Without Collusion”. In: Journal of Machine Learning Research 24 (2023), 40:1–40:33.
- [7]Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, and Ola Svensson. “Space-Efficient Language Generation in the Limit”. In: arXiv preprint arXiv:2606.25777 (2026).arxiv.org/abs/2606.25777
- [8]Sally A. Goldman and Michael J. Kearns. “On the Complexity of Teaching”. In: Journal of Computer and System Sciences 50.1 (1995), pp. 20–31.
- [9]Noah Golowich, Allen Liu, and Abhishek Shetty. “Provably Learning from Modern Language Models via Low Logit Rank”. In: arXiv preprint arXiv:2512.09892 (2025).arxiv.org/abs/2512.09892
- [10]Sally A. Goldman and H. David Mathias. “Teaching a Smarter Learner”. In: Journal of Computer and System Sciences 52.2 (1996), pp. 255–267.DOI
- [11]E. Mark Gold. “Language identification in the limit”. In: Information and Control 10.5 (1967), pp. 447–474.DOI
- [12]Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. “Language Generation with Feedback: Queries and Mistakes”. In: Proceedings of the 43rd International Conference on Machine Learning (ICML). 2026.
- [13]Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. “A theory of learning with autoregressive chain of thought”. In: arXiv preprint arXiv:2503.07932 (2025).arxiv.org/abs/2503.07932
- [14]Jon Kleinberg and Sendhil Mullainathan. “Language generation in the limit”. In: Advances in Neural Information Processing Systems (NeurIPS) 37 (2024), pp. 66058–66079.arxiv.org/abs/2404.06757
- [15]Jon Kleinberg, Anay Mehrotra, Amin Saberi, and Grigoris Velegkas. “On Language Generation in the Limit with Bounded Memory”. In: arXiv preprint arXiv:2605.30324 (2026).arxiv.org/abs/2605.30324
- [16]Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. “On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability”. In: arXiv preprint arXiv:2412.18530 (2025).arxiv.org/abs/2412.18530
- [17]Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. “On the limits of language generation: Trade-offs between hallucination and mode-collapse”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025, pp. 1732–1743.arxiv.org/abs/2411.09642
- [18]Adam Tauman Kalai, Ofir Nachum, Santosh S. Vempala, and Edwin Zhang. “Why language models hallucinate”. In: arXiv preprint arXiv:2509.04664 (2025).arxiv.org/abs/2509.04664
- [19]Adam Tauman Kalai and Santosh S. Vempala. “Calibrated language models must hallucinate”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC). 2024, pp. 160–171.arxiv.org/abs/2311.14648
- [20]Dima Kuzmin and Manfred K. Warmuth. “Unlabeled Compression Schemes for Maximum Classes”. In: Journal of Machine Learning Research 8 (2007), pp. 2047–2081.
- [21]Jon Kleinberg and Fan Wei. “Density measures for language generation”. In: Proceedings of the 66th Annual Symposium on Foundations of Computer Science (FOCS). 2025, pp. 620–658.arxiv.org/abs/2504.14370
- [22]Jon Kleinberg and Fan Wei. “Language generation and identification from partial enumeration: Tight density bounds and topological characterizations”. In: Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC). 2026, pp. 1684–1691.arxiv.org/abs/2511.05295
- [23]Xiaoyu Li, Andi Han, Jiaojiao Jiang, and Junbin Gao. “Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarch”. In: arXiv preprint arXiv:2609.10525 (2026).arxiv.org/abs/2609.10525
- [24]Eran Malach. “Auto-regressive next-token predictors are universal learners”. In: arXiv preprint arXiv:2309.06979 (2023).arxiv.org/abs/2309.06979
- [25]Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. “Language generation with infinite contamination”. In: arXiv preprint arXiv:2511.07417 (2025).arxiv.org/abs/2511.07417
- [26]Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. “Differentially private language generation and identification in the limit”. In: arXiv preprint arXiv:2604.08504 (2026).arxiv.org/abs/2604.08504
- [27]S. Mahmoud Mousawi and Sandra Zilles. “Positive Characteristic Sets for Relational Pattern Languages”. In: Proceedings of the 49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). 2024, pp. 398–412.arxiv.org/abs/2511.12039
- [28]Charlotte Peale, Vinod Raman, and Omer Reingold. “Representative language generation”. In: arXiv preprint arXiv:2505.21819 (2025).arxiv.org/abs/2505.21819
- [29]Daniel Reidenbach. “A non-learnable class of E-pattern languages”. In: Theoretical Computer Science 350.1 (2006), pp. 91–102.DOI
- [30]Daniel Reidenbach. “Discontinuities in pattern inference”. In: Theoretical Computer Science 397.1 (2008). Forty Years of Inductive Inference: Dedicated to the 60th Birthday of Rolf Wiehagen, pp. 166–193.DOI
- [31]Vinod Raman, Jiaxun Li, and Ambuj Tewari. “Generation through the lens of learning theory”. In: Proceedings of the 38th Conference on Learning Theory (COLT). Vol. 291. Proceedings of Machine Learning Research. 2025, pp. 4740–4776.arxiv.org/abs/2410.13714
- [32]Ananth Raman and Vinod Raman. “Generation from noisy examples”. In: arXiv preprint arXiv:2501.04179 (2025).arxiv.org/abs/2501.04179
- [33]Takeshi Shinohara. “Polynomial Time Inference of Extended Regular Pattern Languages”. In: Proceedings of the RIMS Symposium on Software Science and Engineering. 1982, pp. 115–127.